百度笔试题.txt

软件测试越来越热门

 while(head!=NULL)
 {
  p1=head;
  head=head->pnext;
  free(p1);
 }
 for(i=0;i<10;i++)//释放10个数组
 {
  for(i=0;i<10;i++)
  {
  tmp=p[i];
  p[i]=p[i]->pnext;
  free(tmp);
  }
 }

}
 
int main()
{
 
 init();
 sort();
 return 0;
}
 


计算机复杂度：N，遍历此数为N，辅助存储空间为100；这是一个满意的结果！ 
 
创建于： 2006-09-22 14:10:32，修改于： 2006-09-22 14:16:43，已浏览1076次，有评论8条  
 
网友评论 
 网友：carleo  时间：2006-09-23 02:34:00 IP地址：219.239.227.★ 
 
 
 while(p1!=NULL)
 {
  for(i=0;i<10;i++)
  {
   if((p1->group)==i)
...
用这样的结构岂不是对每个节点都在 for 循环中再进行 if 判断，跳转太多效率肯定大打折扣，
while(p1 != NULL) {
   i = p1->group;
   if ( i < 0 || i > 9)
       continue;

   if (b[i] < 10) 
         .....
   else
       ......
  .....
}
这样不就行了嘛 
 
 
 
 网友：xly  时间：2006-09-23 11:02:00 IP地址：202.198.31.★ 
 
 
 没有理解对程序的意图,group值是0-9之间的一个随机数
这里的for(i=0;i<10;i++)
  {
   if((p1->group)==i)
相当于一个switch语句
只是让语句变得简练了，开销和switch是相同的 
 
 
 
 网友：本站网友  时间：2006-09-28 22:54:14 IP地址：60.216.184.★ 
 
 
 程序写的错误真多
太垃圾了 
 
 
 
 网友：骂他两句  时间：2006-09-29 13:32:51 IP地址：219.133.5.★ 
 
 
 这哪里是面试题，如果没有见过做过这样的题目，我不相信百度会有人当场写对。 
 
 
 
 网友：Merlin Ran  时间：2006-10-02 14:42:20 IP地址：125.213.91.★ 
 
 
 怎么都用动态分配的数据结构啊。要充分利用链表有序的特点。直接用10个循环队列，每个都是10个元素的空间，从小到大放当前的top10。每个节点要是这个group，它肯定比原来的top10中的最大值还大，于是把这个值放到当前最大值的后一个，同时循环队列头往前挪一个。比较都不需要做。
扫描完了，数值里存的就是递增的top10了。
int top10[10][10]; // the current top 10 value of each group, impletemented by circular queue
int htop10[10]; // the head(next pos to write) of each circular queue
// to do: initialize each htop10 element to 0
node_t* p = head;
while (p=p->next) {
    top10[p->group][htop10[p->group]] = value;
    htop10[p->group] = (htop10[p->group]+1)%10;
}
for (int i = 0; i < 10; ++i) {
    printf("Printing group %d...\n", i);
    hprint = htop10[i];
    do {
        printf("%d\t", top10[i][hprint]);
        hprint = (hprint+1)%10;
    } while (hprint <> htop10[i]);
    putc('\n');
}
忽略了每组值小于10个的情况。 
 
 
 
 网友：路人甲  时间：2006-10-05 19:13:59 IP地址：59.58.199.★ 
 
 
 楼上正解 
 
 
 
 网友：本站网友  时间：2006-10-11 16:30:33 IP地址：125.33.175.★ 
 
 
    typedef struct top10
   {
		char p;
		node_t *link[10];
   }top10;

	findoutTop10(){
		top10 t[10];
		node_t *tnode;

		tnode = head;
		while(tnode!=null){
			tnode=tnode.pnext;
			
			t[tnode.group].link[t[tnode.group].p] = tnode;
			t[tnode.group].p++;

			if(t[tnode.group].p==10){
				t[tnode.group].p==0;
			}
		}

	} 
 
 
 
 网友：thinkingDeeply  时间：2006-10-13 18:09:59 IP地址：220.231.40.★ 
 
 
 #include <stdlib.h>
#include <iostream.h>
#include <string.h>

typedef struct node_t {
	int value;
	int group;
	struct node_t *pnext;
}node_t;

typedef struct queueNode {
	int value;
	struct queueNode *next;
}queueNode;

typedef struct queue_t {
	queueNode *front;
	queueNode *rear;
	int size;
}queue_t;

void initQueueNode(queueNode *node,int value)
{	
	node->value = value;
	node->next = NULL;
}

void initQueue(queue_t *q)
{
	q->front = q->rear = NULL;
	q->size = 0;
}

bool isFullQueue(queue_t *q)
{
	return q->size == 10;
}

void destroyQueue(queue_t *q)
{
	while(q->front)
	{
		queueNode *node = q->front;
		q->front = q->front->next;
		delete node;
	}
	q->front = q->rear = NULL;
	q->size = 0;
	delete q;
}

int pushQueue(queue_t *q,int value)
{
	if(q->size == 10)
	{
		cout << "queue is full" << endl;
		exit(1);
	}
	queueNode *node = new queueNode();
	initQueueNode(node,value);
	if(q->rear == NULL)
		q->rear = node;
	else
	{
		q->rear->next = node;
		q->rear = q->rear->next;
	}
	if(q->front == NULL)
		q->front = node;
	q->size++;
	return 1;
}

int popQueue(queue_t *q)
{
	if(q->front == q->rear)
	{
		cout << "queue is null" << endl;
		exit(1);
	}
	queueNode *node;
	node = q->front;
	q->front = q->front->next;
	delete node;
	q->size--;
	return 1;
}

void init(node_t *p)
{
	node_t *temp;
	for(int i=0; i<1000000; i++)
	{
		temp = new node_t();
		temp->value = i;
		temp->group = rand()%10;
		temp->pnext = NULL;
		p->pnext = temp;
		p = p->pnext;
	}
}

int top[10][10],total[10];
node_t *head,*p;
node_t *temp;
int num;
queue_t *q[10];



void main()
{
	for(int i=0; i<10; i++)
	{
		q[i] = new queue_t();
		initQueue(q[i]);
	}

	p = new node_t();
	head = p;
	init(p);
	p = head->pnext;
	while(p)
	{
		num = total[p->group] == 10 ? 9 : total[p->group];
		if(isFullQueue(q[p->group]))
		{
			popQueue(q[p->group]);			
		}
		pushQueue(q[p->group],p->value);
		total[p->group] = total[p->group] == 10 ? 10 : total[p->group]+1;
		p = p->pnext;
	}

	for(i=0; i<10; i++)
	{
		cout << "Group " << i << endl;
		q[i]->rear = q[i]->front;
		while(q[i]->rear)
		{
			cout << q[i]->rear->value << "  ";
			if(q[i]->rear->next)
				q[i]->rear = q[i]->rear->next;
			else
				break;
		}
		cout << endl;
	}

	p = head->pnext;
	while(p)
	{
		temp = p;
		p = p->pnext;
		delete temp;
	}
	delete head;

	for(i=0; i<10; i++)
	{
		destroyQueue(q[i]);
	}
}
用队列来存储top10应该是最好的解决方案