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

1. 已知不带头结点的�U�性链�?/span>list�Q�链表中�l�点构造�ؓ(f��)�Q?/span>data�?/span>link�Q�，其中data为数据域�Q?/span>link为指针域。请写一���法�Q�将该链表按�l�点数据域的值的大小从小到大重新链接。要求链接过�E�中不得使用除该链表以外的�Q何链�l�点�I�间。�?a target="_blank">北京航空航天大学 1998 五（15分）�?/span>

　　【参考答案�?/span>

　　[题目分析]本题实质上是一个排序问题，要求“不得��用除该链表结点以外的��M��铄���点空间”。链表上的排序采用直接插入排序比较方便，即首先假定第一个结�Ҏ(gu��)��序，然后�Q�从�W�二个结点开始，依次插入到前面有序链表中�Q�最�l�达到整个链表有序�?/span>

　　LinkedList LinkListSort(LinkedList list)

　　�?/span>list是不带头�l�点的线性链表，链表�l�点构造�ؓ(f��)data�?/span>link两个域，data是数据域�Q?/span>link是指针域。本���法���该链表按结�Ҏ(gu��)��据域的值的大小�Q�从���到大重新链接�?/span>

　　{p=list->link; �?/span>p是工作指针，指向待排序的当前元素�?/span>

　　list->link=null;∥假定第一个元素有序，即链表中现只有一个结炏V�?/span>

　　while(p!=null)

　　{r=p->link; �?/span>r�?/span>p的后�l��?/span>

　　q=list;

　　if(q->data>p->data)∥处理待排序�l�点p比第一个元素结点小的情��c(di��n)�?/span>

　　{p->link=list;

　　list=p;∥链表指针指向最���元素�?/span>

　　}

　　else∥查扑օ�素值最���的�l�点�?/span>

　{while(q->link!=null&&q->link->data<p->data)q=q->link;

　　p->link=q->link;∥将当前排序�l�点铑օ�有序链表中�?/span>

　　q->link=p; }

　　p=r;�?/span>p指向下个待排序结炏V�?/span>

　　}

　　}

　　[���法讨论]���法旉���复杂度的分析与用��序存储�l�构时的情况相同。但��序存储�l�构���第i(i>1)个元素插入到前面�W?/span>1至第i-1个元素的有序表时�Q�是���第i个元素先与第i-1个元素比较。而在链表最��x��况均是和�W�一元素比较。两�U�存储结构下最�?j��ng)_��最差情�늚�比较�ơ数相同�Q�在链表情况下，不移动元素，而是修改�l�点指针。另一说明是，本题中线性链�?/span>list不带头结点，而且要求“不得��用除该链表以外的��M��铄���点空间“，所以处理复杂，需要考虑当前�l�点元素值比有序链表�W�一�l�点的元素��D�����的情况�Q�这时要修改链表指针list。如�?/span>list是头�l�点的指针，则相应处理要���单些�Q�其���法片段如下�Q?/span>

　　p=list->link;�?/span>p指向�W�一元素�l�点�?/span>

　　list->link=null;∥有序链表初始化为空

　　while(p!=null)

　　{r=p->link;∥保存后�l?/span>

　　q=list;

　　while(q->link!=null && q->link->data<p->data)q=q->link;

　　p->link=q->link;

　　q->link=p;

　　q=r;

　　}