将链表的记录进行就地排序

王朝c/c++·作者佚名  2006-01-06
窄屏简体版  字體: |||超大  

【题目】设一单向链表的头指针为head,链表的记录中包含着整数类型的key域,试设计算法,

将此链表的记录按照key递增的次序进行就地排序.(不允许使用数组做辅助存储)

【来源】中科院计算机技术研究所1999年第五(1)题 (10’)

华中理工大学2000年第八(2)题 (13’)

【解答】

typedef struct CircleList{ // 定义循环链表

int key;

struct CircleList *next;

}*listnode;

ListSort(listnode head)

{

int k,min,i,j;

listnode p,q,t;

p=head->next;

while(p->next!=head->next){p=p->next;k+=1;} // 统计链表中元素个数,保存在 K 中

p=head;j=1;

for(i=1;i<k;i++){

while(j<=i){p=p->next;j++;} // 找应填入当前最小元素的位置,该位置保存在 q 中

min=p->key;q=p; // 将当前位置元素的值设为初始最小值

while(p->next!=head->next){

if(min>p->key){min=p->key;t=p;} // 找当前最小元素,并保存在 t 所指位置中

p=p->next;

}

t->key=q->key;q->key=min;j=1; // 交换 q 位置元素和最小元素的值

}

}

【分析】本题不需要修改链表中的各个指针。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航