数据结构:将链表的记录进行就地排序
添加时间: 2007-4-9 2:02:02 作者: 程序员认证参考 阅读次数:45 来源: http://www.d9soft.com
【题目】设一单向链表的头指针为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 位置元素和最小元素的值
}
}
【分析】本题不需要修改链表中的各个指针。
上一篇文章: C++箴言：理解inline的介入和排除 下一篇文章: C++箴言：让=返回一个*this的引用
相关文章:
相关软件: