一道百度笔试题的解决方案

 编程题：30分 共1题

惭愧，写了挺久才写出来的程序：

#include
#include
#include

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，最后做一次冒泡排序，多简单

#include
#include
#include

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

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],num[10];
node_t *head,*p;
node_t *temp;

void main()
{
 int i,j,k,t;

 p = new node_t();
 head = p;
 init(p);
 p = head->pnext;
 while(p)
 {
  top[p->group][num[p->group]] = p->value;
  num[p->group] = (num[p->group]+1)%10;
  total[p->group] = total[p->group] == 10 ? 10 : total[p->group]+1;
  p = p->pnext;
 }

 for(i=0; i<10; i++)
 {
  for(j=0; j  {
   for(k=total[i]-1; k>0; k--)
   {
    if(top[i][k] < top[i][k-1])
    {
     t = top[i][k];
     top[i][k] = top[i][k-1];
     top[i][k-1] = t;
    }
   }
  }
 }

 for(i=0 ;i<10; i++)
 {
  cout << "Group " << i << endl;
  for(j=0; j  {
   cout << top[i][j] << "  ";
  }
  cout << endl;
 }

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