数据�l�构�W�二章算法设计题 [6]_跨考网

　1. �?/span>L为单链表的头�l�点地址�Q�其数据�l�点的数据都是正整数且无相同的，试设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。�?a target="_blank">东北大学 1996 �?/span> (14�?/span>)�?/span>

　　�c�M��本题的另外叙�q�有�Q?/span>

　　设一单向链表的头指针�?/span>head,链表的记录中包含着整数�c�d���?/span>key�?/span>,试设计算�?/span>,���此链表的记录按�?/span>key递增的次序进行就地排�?/span>.【中�U�院计算所 1999 五�?/span>1�Q?/span>10分）(j��)�?/span>

　　【参考答案�?/span>

　　[题目分析]本题明确指出单链表带头结点，其结�Ҏ(gu��)��据是正整��C��不相同，要求利用直接插入原则把链表整理成递增有序链表。这���p��求从�W�二�l�点开释，���各�l�点依次插入到有序链表中�?/span>

　　LinkedList LinkListInsertSort(LinkedList la)

　　�?/span>la是带头结点的单链表，其数据域是正整数。本���法利用直接插入原则���链表整理成递增的有序链表�?/span>

　　{if(la->next!=null)∥链表不为空表�?/span>

　　{p=la->next->next;�?/span>p指向�W�一�l�点的后�l��?/span>

　　la->next->next=null;∥直接插入原则认为第一元素有序�Q�然后从�W�二元素起依�ơ插入�?/span>

　　while(p!=null)

　　{r=p->next;∥暂�?/span>p的后�l��?/span>

　　q=la;

　　while(q->next!=null&&q->next->data<p->data)q=q->next;∥查找插入位�|��?/span>

　　p->next=q->next;∥将p�l�点铑օ�链表�?/span>

　　q->next=p;

　　p=r; }

　　与本题有�c�M��叙述的题的解�{�：(x��)

　　本题也是链表排序问题�Q�虽没象上题那样明确要求“利用直接插入的原则”来排序�Q�仍可用上述���法求解�Q�这里不再赘�q��?/font>