神马文学网一道百度笔试题的解决方案
来源：百度文库 编辑：神马文学网 时间：2024/04/28 18:14:50
一道百度笔试题的解决方案编程题：30分 共1题
注意：要求提供完整代码，如果可以编译运行酌情加分。
1. 一条1百万节点的单向链表，链表所有节点是按value字段从小到大的顺序链接；下面是一个节点的结构
typedef struct node_t{
int value; /* 节点排序字段 */
int group; /* 组号: 0,1,2,3,4,5,6,7,8,9 */
struct node_t *pnext; /* 下个节点的指针 */
}node_t;
node_t head; /*该单向链表的头节点，全局变量 */
试设计程序：针对各个group(0-->9)，根据value字段排序，输出各组top 10的节点。（top10是从小到大，取后面的大值top10.）
要求：尽量减少计算复杂度、遍历次数，不允许大量的辅助内存
惭愧，写了挺久才写出来的程序：
#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;
}