算法所需时间与链表长度无关,只有使用带尾指针的循环单链表,这样最容易找到链表的首、 尾结点,将该结点序列插入到单向链表第一元素之前即可 其核心算法片段如下(设两链表均有头结点) ∥单向循环链表的表头指针 hb->next=ha->next;∥将循环单链表最后元素结点接在ha第一元素前。 ha->next=q->next;∥将指向原单链表第一元素的指针指向循环单链表第一结 free(g) ∥释放循环链表头结点 若两链表均不带头结点,则算法片段如下 g=hb->next ∥q指向hb首元结点 hb->next=ha ∥hb尾结点的后继是ha第一元素结点。 ∥头指针指向hb的首元结点 4.[题目分析]顺序存储结构的线性表的插入,其时间复杂度为0(n),平均移动近 半的元素。线性表LA和LB合并时,若从第一个元素开始,一定会造成元素后移,这不符合 本题“高效算法”的要求。另外,题中叙述“线性表空间足够大”也暗示出另外合并方式 即应从线性表的最后一个元素开始比较,大者放到最终位置上。设两线性表的长度各为m 和n,则结果表的最后一个元素应在mn位置上。这样从后向前,直到第一个元素为止。 PROC Union(VAR LA: SeqList; LB: SeqList) ∥LA和LB是顺序存储的非递减有序线性表,本算法将LB合并到LA中,元素仍非递减 有序。 m:=LA.last;n:=LB.last;∥m,n分别为线性表LA和LB的长度。 k:=m+ ∥k为结果线性表的工作指针(下标)。 i:=m;j:=n;∥i,j分别为线性表LA和LB的工作指针(下标) WHILE(i>0)AND (j>0)DO IF LA elem[i]>=LB elem[jl THEN[LA. elem[k]: =LA elem[i]: k: =k-1; i: =i-1 ELSE [LA elem[k]: =LB. elem[j]: k: =k-1:j: =j-1; 1 WHILE(j>O)DO [LA elem[k]: =LB elem[j]: k: =k-1;j: =j-1:] LA last: =m+n ENDP [算法讨论]算法中数据移动是主要操作。在最佳情况下(LB的最小元素大于LA的最大 元素),仅将LB的n个元素移(拷贝)到LA中,时间复杂度为0(n),最差情况,LA的所 有元素都要移动,时间复杂度为0(m+n)。因数据合并到LA中,所以在退出第一个 WHILE 循环后,只需要一个IE循环,处理BB中剩余元素。第二个循环只有在LB有剩余元素时 才执行,而在LA有剩余元素时不执行。本算法利用了题目中“线性表空间足够大”的条件, “最大限度的避免移动元素”,是“一种高效算法” 5.[题目分析]本题实质上是一个排序问题,要求“不得使用除该链表结点以外的任何链 结点空间”。链表上的排序采用直接插入排序比较方便,即首先假定第一个结点有序,然后 从第二个结点开始,依次插入到前面有序链表中,最终达到整个链表有序。 LinkedList LinkList Sort(LinkedList list) ∥1ist是不带头结点的线性链表,链表结点构造为data和link两个域,data是数据 域,link是指针域。本算法将该链表按结点数据域的值的大小,从小到大重新链接 p=list-link;∥p是工作指针,指向待排序的当前元素 list-link=nul;∥假定第一个元素有序,即链表中现只有一个结点
算法所需时间与链表长度无关，只有使用带尾指针的循环单链表，这样最容易找到链表的首、 尾结点，将该结点序列插入到单向链表第一元素之前即可。 其核心算法片段如下（设两链表均有头结点） q=hb->next; ∥单向循环链表的表头指针 hb->next=ha->next; ∥将循环单链表最后元素结点接在 ha 第一元素前。 ha->next=q->next; ∥将指向原单链表第一元素的指针指向循环单链表第一结 点 free(q); ∥释放循环链表头结点。 若两链表均不带头结点，则算法片段如下： q=hb->next; ∥q 指向 hb 首元结点。 hb->next=ha; ∥hb 尾结点的后继是 ha 第一元素结点。 ha=q; ∥头指针指向 hb 的首元结点。 4．[题目分析]顺序存储结构的线性表的插入，其时间复杂度为 O（n），平均移动近一 半的元素。线性表 LA 和 LB 合并时，若从第一个元素开始，一定会造成元素后移，这不符合 本题“高效算法”的要求。另外，题中叙述“线性表空间足够大”也暗示出另外合并方式， 即应从线性表的最后一个元素开始比较，大者放到最终位置上。设两线性表的长度各为 m 和 n ，则结果表的最后一个元素应在 m+n 位置上。这样从后向前，直到第一个元素为止。 PROC Union(VAR LA:SeqList;LB:SeqList) ∥LA 和 LB 是顺序存储的非递减有序线性表，本算法将 LB 合并到 LA 中，元素仍非递减 有序。 m:=LA.last;n:=LB.last;∥m，n 分别为线性表 LA 和 LB 的长度。 k:=m+n; ∥k 为结果线性表的工作指针（下标）。 i:=m;j:=n; ∥i，j 分别为线性表 LA 和 LB 的工作指针（下标）。 WHILE(i>0)AND(j>0)DO IF LA.elem[i]>=LB.elem[j] THEN[LA.elem[k]:=LA.elem[i];k:=k-1;i:=i-1;] ELSE[LA.elem[k]:=LB.elem[j];k:=k-1;j:=j-1;] WHILE(j>0) DO [LA.elem[k]:=LB.elem[j];k:=k-1;j:=j-1;] LA.last:=m+n; ENDP; [算法讨论]算法中数据移动是主要操作。在最佳情况下（LB 的最小元素大于 LA 的最大 元素），仅将 LB 的 n 个元素移（拷贝）到 LA 中，时间复杂度为 O（n），最差情况，LA 的所 有元素都要移动，时间复杂度为 O（m+n）。因数据合并到 LA 中，所以在退出第一个 WHILE 循环后，只需要一个 WHILE 循环，处理 LB 中剩余元素。第二个循环只有在 LB 有剩余元素时 才执行，而在 LA 有剩余元素时不执行。本算法利用了题目中“线性表空间足够大”的条件， “最大限度的避免移动元素”，是“一种高效算法”。 5．[题目分析]本题实质上是一个排序问题，要求“不得使用除该链表结点以外的任何链 结点空间”。链表上的排序采用直接插入排序比较方便，即首先假定第一个结点有序，然后， 从第二个结点开始，依次插入到前面有序链表中，最终达到整个链表有序。 LinkedList LinkListSort(LinkedList list) ∥list 是不带头结点的线性链表，链表结点构造为 data 和 link 两个域，data 是数据 域，link 是指针域。本算法将该链表按结点数据域的值的大小，从小到大重新链接。 {p=list->link; ∥p 是工作指针，指向待排序的当前元素。 list->link=null;∥假定第一个元素有序，即链表中现只有一个结点
while(p!=null) ∥r是p的后继 list if(q->data>p->data)∥处理待排序结点p比第一个元素结点小的情况 (p->link=list list=p;∥/链表指针指向最小元素。 else∥查找元素值最小的结点 Iwhile(q->link!=null&&q->link->data(p->data)q=q->link p>1ink=q->link;∥/将当前排序结点链入有序链表中 p=r;∥p指向下个待排序结点。 [算法讨论]算法时间复杂度的分析与用顺序存储结构时的情况相同。但顺序存储结构将 第i(i》1)个元素插入到前面第1至第i-1个元素的有序表时,是将第i个元素先与第i-1 个元素比较。而在链表最佳情况均是和第一元素比较。两种存储结构下最佳和最差情况的比 较次数相同,在链表情况下,不移动元素,而是修改结点指针。 另一说明是,本题中线性链表Iist不带头结点,而且要求“不得使用除该链表以外的 任何链结点空间“,所以处理复杂,需要考虑当前结点元素值比有序链表第一结点的元素值 还小的情况,这时要修改链表指针list。如果list是头结点的指针,则相应处理要简单些, 其算法片段如下: p=list-link;∥p指向第一元素结点。 list-link=nu1l;∥有序链表初始化为空 hile (p=null {r=p-1ink;∥/保存后继 gRist: while(q->link!=null & q-link->data<p->data)q=q->link p->link=g->link g->link=p 6.[题目分析]本题明确指出单链表带头结点,其结点数据是正整数且不相同,要求利 用直接插入原则把链表整理成递增有序链表。这就要求从第二结点开释,将各结点依次插入 到有序链表中。 LinkedList LinkListInsert Sort (LinkedList la) ∥1a是带头结点的单链表,其数据域是正整数。本算法利用直接插入原则将链表整理成递 增的有序链表。 if(1a->next!=null)∥链表不为空表 p=1a->next->next;∥p指向第一结点的后继 la-next->next=nu1l;∥直接插入原则认为第一元素有序,然后从第二元素起依次插 while(p! =null) r=p->next;∥/暂存p的后继
while(p!=null) {r=p->link; ∥r 是 p 的后继。 q=list; if(q->data>p->data)∥处理待排序结点 p 比第一个元素结点小的情况。 {p->link=list; list=p;∥链表指针指向最小元素。 } else∥查找元素值最小的结点。 {while(q->link!=null&&q->link->data<p->data)q=q->link; p->link=q->link;∥将当前排序结点链入有序链表中。 q->link=p; } p=r;∥p 指向下个待排序结点。 } } [算法讨论]算法时间复杂度的分析与用顺序存储结构时的情况相同。但顺序存储结构将 第 i(i>1)个元素插入到前面第 1 至第 i-1 个元素的有序表时，是将第 i 个元素先与第 i-1 个元素比较。而在链表最佳情况均是和第一元素比较。两种存储结构下最佳和最差情况的比 较次数相同，在链表情况下，不移动元素，而是修改结点指针。 另一说明是，本题中线性链表 list 不带头结点，而且要求“不得使用除该链表以外的 任何链结点空间“，所以处理复杂，需要考虑当前结点元素值比有序链表第一结点的元素值 还小的情况，这时要修改链表指针 list。如果 list 是头结点的指针，则相应处理要简单些， 其算法片段如下： p=list->link;∥p 指向第一元素结点。 list->link=null;∥有序链表初始化为空 while(p!=null) {r=p->link;∥保存后继 q=list; while(q->link!=null && q->link->data<p->data)q=q->link; p->link=q->link; q->link=p; q=r; } 6．[题目分析]本题明确指出单链表带头结点，其结点数据是正整数且不相同，要求利 用直接插入原则把链表整理成递增有序链表。这就要求从第二结点开释，将各结点依次插入 到有序链表中。 LinkedList LinkListInsertSort(LinkedList la) ∥la 是带头结点的单链表，其数据域是正整数。本算法利用直接插入原则将链表整理成递 增的有序链表。 {if(la->next!=null)∥链表不为空表。 {p=la->next->next;∥p 指向第一结点的后继。 la->next->next=null;∥直接插入原则认为第一元素有序，然后从第二元素起依次插 入。 while(p!=null) {r=p->next;∥暂存 p 的后继