数据结构（C语言版）1800道题及答案

数据结构1800例题与答案

第一章 绪 论

一、选择题（每小题2分）

1．算法的计算量的大小称为计算的（ B ）。 【北京邮电大学2000 二、3 （20/8分）】 A．效率 B．复杂性 C．现实性 D．难度 2．算法的时间复杂度取决于（C）。 【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B．待处理数据的初态 C．A和B D．都不是 3．计算机算法指的是（① C ），它必须具备（② B ） 这三个特性。

① A．计算方法 B．排序方法 C．解决问题的步骤序列 D．调度方法

② A．可执行性、可移植性、可扩充性 B．可执行性、确定性、有穷性

C．确定性、有穷性、稳定性 D．易读性、稳定性、安全性 【南京理工大学 1999 一、1（2分） 【武汉交通科技大学 1996 一、1（ 4分）】 4．一个算法应该是（ B ）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述

C．要满足五个基本特性 D．A和C. 5．下面关于算法说法错误的是（ D ）【南京理工大学 2000 一、1（1.5分）】

A．算法最终必须由计算机程序实现

B.为解决某问题的算法同为该问题编写的程序含义是相同的

C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（ C ）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间

（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低

A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（ C ）两大类。【武汉交通科技大学 1996 一 、4（2分）】

A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（ D ）。【北方交通大学 2000 二、1（2分）】

A．循环队列 B. 链表 C. 哈希表 D. 栈

9．以下数据结构中，哪一个是线性结构（ D ）？【北方交通大学 2001 一、1（2分）】

A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（ Ａ ）【北方交通大学 2001 一、2（2分）】

A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（ Ｃ ）【北京工商大学 2001 一、10（3分）】

FOR i:=1 TO n DO

FOR j:=1 TO n DO x:=x+1;

A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段 FOR i:=n-1 DOWNTO 1 DO

FOR j:=1 TO i DO

IF A[j]>A[j+1]

THEN A[j]与A[j+1]对换；

其中 n为正整数，则最后一行的语句频度在最坏情况下是（Ｄ ）

A. O（n） B. O(nlogn) C. O(n3) D. O(n2) 【南京理工大学1998一、1(2分)】

13．以下哪个数据结构不是多型数据类型（ Ｄ ）【中山大学 1999 一、3（1分）】

A．栈 B．广义表 C．有向图 D．字符串 14．以下数据结构中，（ Ａ ）是非线性数据结构【中山大学 1999 一、4】

A．树 B．字符串 C．队 D．栈 15. 下列数据中，（ Ｃ ）是非线性数据结构。【北京理工大学 2001 六、1（2分）】

A．栈 B. 队列 C. 完全二叉树 D. 堆 16．连续存储设计时，存储单元的地址（ Ａ ）。【中山大学 1999 一、1（1分）】

A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续 17．以下属于逻辑结构的是（ Ｃ ）。【西安电子科技大学应用 2001一、1】

A．顺序表 B. 哈希表 C.有序表 D. 单链表

二、判断题

1. 数据元素是数据的最小单位。( ２ )

【北京邮电大学 1998 一、1（2分）】【青岛大学 2000 一、1 （1分）】 【上海交通大学 1998 一、1】 【山东师范大学 2001 一、1 （2分）】 2. 记录是数据处理的最小单位。 ( ２ ) 【上海海运学院 1998 一、5（1分）】

3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；( ２ )【北京邮电大学2002 一、1（1分）】

4．算法的优劣与算法描述语言无关，但与所用计算机有关。( ２ )

【大连海事大学 2001 一、10（1分）】

5．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( １ )

【大连海事大学 2001 一、11（1分）】

6．算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。( ２ )【西安交通大学 1996 二、7（3分）】 7．程序一定是算法。( ２ )【燕山大学 1998 二、2（2分）并改错】

8．数据的物理结构是指数据在计算机内的实际存储形式。( １ )【山东师范大学2001 一、2（2分）】

9. 数据结构的抽象操作的定义与具体实现有关。( ２ )【华南理工大学 2002 一、1（1分）】 10. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。( ２ )

【华南理工大学 2002 一、2 （1分）】

11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( ２ )

【上海海运学院 1999 一、1（1分）】

12. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。(１ )

【华南理工大学 2002 一、5（1分）】

13. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. ( ２ )

【上海海运学院 1998 一、1（1分）】 三、填空

1．数据的物理结构包括 数据元素 的表示和 数据元素间关系 的表示。【燕山大学 1998 一、1（2分）】

2. 对于给定的n个元素,可以构造出的逻辑结构有 集合 ， 线性结构 ， 树形结构 ，__图状结构或网状结构_四种。

【中科院计算所 1999 二、1（4分）】

3．数据的逻辑结构是指 数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是指数据元素之间的关联方式或程“邻接关系”【北京邮电大学 2001 二、1（2分）】 4．一个数据结构在计算机中 表示（又称映像）称为存储结构。【华中理工大学 2000 一、1（1分）】 5．抽象数据类型的定义仅取决于它的一组_逻辑特性_，而与_在计算机内部如何表示和实现_无关，即不论其内部结构如何变化，只要它的_数学特性不变，都不影响其外部使用。【山东大学 2001 三、3（2分）】

6．数据结构中评价算法的两个重要指标是 算法的时间复杂度和空间复杂度 【北京理工大学 2001 七、1（2分）】

7. 数据结构是研讨数据的_逻辑结构_和_物理结构_，以及它们之间的相互关系，并对与这种结构定义相应的_操作（运算）_，设计出相应的算法_。【西安电子科技大学 1998 二、2（3分）】

8． 一个算法具有5个特性: 有穷性 、 确定性、 可行性 ，有零个或多个输入、有一个或多个输出。

【华中理工大学 2000 一、2（5分）】 【燕山大学 1998 一、2（5分）】 9．已知如下程序段

FOR i:= n DOWNTO 1 DO {语句1} BEGIN

x:=x+1； {语句2} FOR j:=n DOWNTO i DO {语句3} y:=y+1; {语句4} END；

语句1执行的频度为 n+1 ；语句2执行的频度为 n ；语句3执行的频度为 n(n+3)/2 ；语句4执行的频度为 n(n+1)/2 。【北方交通大学 1999 二、4（5分）】

10．在下面的程序段中，对ｘ的赋值语句的频度为_1+(1+2++(1+2+3)+?+(1+2+3+?+n)=n(n+1)(n+2)/6 0（n的立方）____（表示为n的函数）

FOR i：＝１ TO n DO FOR j：＝１ TO i DO

FOR k：＝1 TO j DO

ｘ：＝ｘ＋delta；

【北京工业大学 1999 一、6（2分）】

11.下面程序段中带下划线的语句的执行次数的数量级是： 【合肥工业大学1999三、1（2分）】

i：=1； WHILE i

12. 下面程序段中带下划线的语句的执行次数的数量级是( )。【合肥工业大学 2000 三、1（2分）】

i:=1;

WHILE i

13. 下面程序段中带有下划线的语句的执行次数的数量级是( ) 【合肥工业大学 2001 三、1（2分）】

i：=n*n WHILE i<>1 DO i:=i div 2;

14. 计算机执行下面的语句时，语句s的执行次数为 _______ 。【南京理工大学2000二、1（1.5分）】

FOR(i=l；i=i;j--) s;

15. 下面程序段的时间复杂度为________。(n>1) sum=1；

for (i=0;sum

16．设m.n均为自然数，m可表示为一些不超过n的自然数之和，f(m,n)为这种表示方式的数目。例f(5,3)=5，有5种表示方式：3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。 ①以下是该函数的程序段，请将未完成的部分填入，使之完整

int f(m,n) int m,n; { if(m==1)

return (1) ; if(n==1){

return (2) ;} if(m

{return f(m,m);} if (m==n)

{return 1+ (3) ;}

return f(m.n-1)+f(m-n, (4) ); }

②执行程序，f(6,4)= 。 【中科院软件所 1997 二、1 （9分）】 17. 在有n个选手参加的单循环赛中，总共将进行______场比赛。【合肥工业大学1999三、8（2分）】

四、应用题

1. 数据结构是一门研究什么内容的学科？【燕山大学 1999 二、1 （4分）】 2. 数据元素之间的关系在计算机中有几种表示方法？各有什么特点？【燕山大学1999 二、2（4分）】

3. 数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？【北京邮电大学 1994 一（8分）】 4. 回答问题（每题2分）【山东工业大学 1997 一 （8分）】

（1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？

（2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明之。

（3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。

（4）评价各种不同数据结构的标准是什么？ 5．评价一个好的算法，您是从哪几方面来考虑的？

【大连海事大学 1996 二、3 （2分）】【中山大学 1998 三、1 （5分）】 6．解释和比较以下各组概念【华南师范大学 2000 一（10分）】

（1）抽象数据类型及数据类型 （2）数据结构、逻辑结构、存储结构 （3）抽象数据类型【哈尔滨工业大学 2000 一、1（3分）】 （4）算法的时间复杂性 【河海大学 1998 一、2（3分）】 （5）算法【吉林工业大学1999 一、1（2分）】 （6）频度【吉林工业大学 1999 一、2（2分）】

7. 根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？

【北京科技大学 1998 一、1】【同济大学 1998】

8．对于一个数据结构，一般包括哪三个方面的讨论？【北京科技大学 1999 一、1（2分）】 9. 当你为解决某一问题而选择数据结构时，应从哪些方面考虑？【西安电子北京科技大学 2000】

10. 若将数据结构定义为一个二元组（D，R）,说明符号D，R 应分别表示什么？

【北京科技大学 2001 一、1（2分）】

11．数据结构与数据类型有什么区别？【哈尔滨工业大学 2001 三、1（3分）】

12．数据的存储结构由哪四种基本的存储方法实现？【山东科技大学 2001 一、1（4分）】 13．若有100个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便，写出这些结构？

【山东师范大学 1996 二、2（2分）】 14. 运算是数据结构的一个重要方面。试举一例，说明两个数据结构的逻辑结构和存储方式完全相同，只是对于运算的定义不同。因而两个结构具有显著不同的特性，是两个不同的结构。

【北京大学 1998一、1（5分）】

15. 在编制管理通讯录的程序时, 什么样的数据结构合适? 为什么?【 长沙铁道学院1998四、3(6分)】

16. 试举一例，说明对相同的逻辑结构,同一种运算在不同的存储方式下实现，其运算效率不同。

【北京理工大学 2000 三、1（4.5分）】

n

17. 有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为Tl=O(2)，A2的时间复

2

杂度为T2=O(n)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。【北京航空航天大学 2000 二（10分）】

18．设计一数据结构，用来表示某一银行储户的基本信息： 账号、姓名、开户年月日、储蓄类型、存入累加数、利息、帐面总数。【浙江大学 1994 一 、3（5分）】 19. 写出下面算法中带标号语句的频度。

TYPE ar=ARRAY[1..n] OF datatype;

PROCEDURE perm ( a: ar; k, n: integer); VAR x: datatype; i:integer; BEGIN

（1）IF k=n THEN BEGIN

（2）FOR i:=1 TO n DO （3）write (a[i]); writeln; END ELSE BEGIN

（4） FOR i:=k TO n DO

(3)L=p; ∥头指针仍为L

32. (1) p^.next<>p0 (2)r:= p^.next (3) p^.next:= q0; (4) q0:= p; (5) p:=r

33. (1)r (2)NIL (3)x=x; (7)r (8)p (9)r (10)NIL (11)NIL 34．(1)pa!=ha ∥或pa->exp!=-1

(2)pa->exp==0 ∥若指数为0，即本项为常数项 (3)q->next=pa->next ∥删常数项 (4)q->next ∥取下一元素 (5)=pa->coef*pa->exp

(6)-- ∥指数项减1

(7)pa ∥前驱后移,或q->next (8)pa->next ∥取下一元素 35．(1)q:=p; ∥q是工作指针p的前驱

(2)p^.data>m ∥p是工作指针

(3)r:=q; ∥r 记最大值的前驱， (4)q:=p; ∥或q:=q^.next;

(5)r^.next:=q^.next; ∥或r^.next:=r^.next^.next 删最大值结点 36．(1)L->next=null ∥置空链表,然后将原链表结点逐个插入到有序表中 (2)p!=null ∥当链表尚未到尾，p为工作指针

(3)q!=null ∥查p结点在链表中的插入位置，这时q是工作指针。 (4)p->next=r->next ∥将p结点链入链表中

(5)r->next=p ∥r是q的前驱，u是下个待插入结点的指针。 37．程序（a） PASCAL部分(编者略）

程序（b） C部分

(1)(A!=null && B!=null) ∥两均未空时循环

(2)A->element==B->element ∥两表中相等元素不作结果元素 (3)B=B->link ∥向后移动B表指针

(4)A!=null ∥将A 表剩余部分放入结果表中 (5)last->link=null ∥置链表尾

四、 应用题 1．（1）选链式存储结构。它可动态申请内存空间，不受表长度（即表中元素个数）的

影响，插入、删

除时间复杂度为O（1）。

（2）选顺序存储结构。顺序表可以随机存取，时间复杂度为O（1）。

2．链式存储结构一般说克服了顺序存储结构的三个弱点。首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。

3．采用链式存储结构，它根据实际需要申请内存空间，而当不需要时又可将不用结点空间返还给系统。在链式存储结构中插入和删除操作不需要移动元素。

4．线性表 栈 队列 串 顺序存储结构和链式存储结构。

顺序存储结构的定义是：

CONST maxlen=线性表可能达到的最大长度； TYPE sqlisttp=RECORD

elem:ARRAY[1..maxlen] OF ElemType; last:0..maxlen; END; 链式存储结构的定义是： TYPE pointer=↑nodetype; nodetype=RECORD

data:ElemType; next:pointer; END;

linklisttp=pointer;

5.顺序映射时，ai与ai+1的物理位置相邻；链表表示时ai与ai+1的物理位置不要求相邻。 6．在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等），有头结点后，对在第一元素结点前插入结点和删除第一结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。

7．见上题6。

8．(1)将next域变为两个域: pre和next，其值域均为0..maxsize。初始化时，头结点（下标为0的元素）其next域值为1，其pre域值为n（设n是元素个数，且n

9. 在单链表中不能从当前结点（若当前结点不是第一结点）出发访问到任何一个结点，链表只能从头指针开始，访问到链表中每个结点。在双链表中求前驱和后继都容易，从当前结点向前到第一结点，向后到最后结点，可以访问到任何一个结点。

10．本题是链表的逆置问题。设该链表带头结点，将头结点摘下，并将其指针域置空。然后从第一元素结点开始，直到最后一个结点为止，依次前插入头结点的后面，则实现了链表的逆置。 11．该算法的功能是判断链表L是否是非递减有序，若是则返回“true”；否则返回“false“。pre指向当前结点，p指向pre的后继。

12．q=p->next; p->next=q->next; free(q);

13. 设单链表的头结点的头指针为head,且pre=head； while(pre->next!=p) pre=pre->next; s->next=p; pre->next=s;

14.设单链表带头结点，工作指针p初始化为p=H->next;

(1) while(p!=null && p->data!=X) p=p->next;

if(p= =null) return(null);∥查找失败 else return(p);∥查找成功

(2) while(p!=null && p->datanext;

if(p==null || p->data>X) return(null);∥查找失败 else return(p);

(3) while(p!=null && p->data>X) p=p->next;

if(p==null || p->data

15.本程序段功能是将pa和pb链表中的值相同的结点保留在pa链表中（pa中与pb中不同结点删除），pa是结果链表的头指针。链表中结点值与从前逆序。S1记结果链表中结点个数（即pa与pb中相等的元素个数）。S2记原pa链表中删除的结点个数。 16．设 q:=p^.llink; 则

q^.rlink:=p^.rlink; p^.rlink^.llink:=q; p^.llink:=q^.llink;

q^.llink^.rlink:=p; p^.rlink:=q; q^.llink:=p 17.(1)前两个语句改为：

p.llink^.rlink<- p^.rlink; p^.rlink^.llink<- p^.llink;

(2)后三个语句序列应改为：

q^.rlink<- p^.rlink;∥以下三句的顺序不能变

p^.rlink^.llink<- q; p^.rlink<- q;

18．mp是一个过程，其内嵌套有过程subp。

subp(s,q)的作用是构造从s到q的循环链表。

subp(pa,pb)调用结果是将pa到pb的前驱构造为循环链表。

subp(pb,pa)调用结果是将pb到pa的前驱（指在L链表中，并非刚构造的pa循环

链表中）构造为循环链表。

总之，两次调用将L循环链表分解为两个。第一个循环链表包含从pa到pb的前驱,L中除刚构造的pa到pb前驱外的结点形成第二个循环链表。 19．在指针p所指结点前插入结点s的语句如下：

s->pre=p->pre; s->next=p; p->pre->next=s; p->pre=s;

20．(A) f1<>NIL并且f2<>NIL

(B) f1↑.data < f2↑.data (C) f2↑.data

(E) f1<- f1↑.link 或f2=f2↑.link;

21. 1）本算法功能是将双向循环链表结点的数据域按值自小到大排序，成为非递减（可能包括数据域值相等的结点）有序双向循环链表。

2）(1)r->prior=q->prior;∥将q结点摘下，以便插入到适当位置。

(2)p->next->prior=q;∥（2）（3）将q结点插入 (3)p->next=q;

(4)r=r->next;或r=q->next;∥后移指针，再将新结点插入到适当位置。

五、 算法设计题

1．[题目分析]因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比较，将小的链入链表中，同时后移链表工作指针。该问题要求结果链表按元素值递减次序排列。故在合并的同时，将链表结点逆置。 LinkedList Union(LinkedList la,lb)

∥la,lb分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列，本算法

将两链表合并成一个按元素值递减次序排列的单链表。

{ pa=la->next; pb=lb->next;∥pa，pb分别是链表la和lb的工作指针

la->next=null; ∥la作结果链表的头指针，先将结果链表初始化为空。

while(pa!=null && pb!=null) ∥当两链表均不为空时作 if(pa->data<=pb->data)

{ r=pa->next; ∥将pa 的后继结点暂存于r。

pa->next=la->next; ∥将pa结点链于结果表中，同时逆置。

la->next=pa;

pa=r; ∥恢复pa为当前待比较结点。 }

else

{r=pb->next;∥ 将pb 的后继结点暂存于r。

pb->next=la->next; ∥将pb结点链于结果表中，同时逆置。 la->next=pb;

pb=r; ∥恢复pb为当前待比较结点。 }

while(pa!=null) ∥将la表的剩余部分链入结果表，并逆置。 {r=pa->next; pa->next=la->next; la->next=pa; pa=r; } while(pb!=null)

{r=pb->next; pb->next=la->next; la->next=pb; pb=r; } }∥算法Union结束。

［算法讨论］上面两链表均不为空的表达式也可简写为while(pa&&pb),两递增有序表合并成递减有序表时，上述算法是边合并边逆置。也可先合并完，再作链表逆置。后者不如前者优化。算法中最后两个while语句，不可能执行两个，只能二者取一，即哪个表尚未到尾，就将其逆置到结果表中，即将剩余结点依次前插入到结果表的头结点后面。 与本题类似的其它题解答如下： （１）［问题分析］与上题类似，不同之处在于：一是链表无头结点，为处理方便，给加上头结点，处理结束再删除之；二是数据相同的结点，不合并到结果链表中；三是hb链表不能被破坏，即将hb的结点合并到结果链表时，要生成新结点。 LinkedList Union(LinkedList ha, hb)

∥ha和hb是两个无头结点的数据域值递增有序的单链表，本算法将hb中并不出现在ha

中的数据合并到ha中，合并中不能破坏hb链表。 ｛LinkedList la;

la=(LinkedList)malloc(sizeof(LNode)); la->next=ha;∥申请头结点，以便操作。 pa=ha; ∥pa是ha链表的工作指针

pb=hb; ∥pb是hb链表的工作指针

pre=la; ∥pre指向当前待合并结点的前驱。 while(pa&&pb)

if(pa->datadata)∥处理ha中数据 {pre->next=pa;pre=pa;pa=pa->next;}

else if(pa->data>pb->data)∥处理hb中数据。

{r=(LinkedList)malloc(sizeof(LNode));∥申请空间 r->data=pb->data; pre->next=r;

pre=r;∥将新结点链入结果链表。

pb=pb->next;∥hb链表中工作指针后移。 }

else∥处理pa->data=pb->data; {pre->next=pa; pre=pa;

pa=pa->next;∥两结点数据相等时，只将ha的数据链入。 pb=pb->next;∥不要hb的相等数据 }

if(pa!=null)pre->next=pa;∥将两链表中剩余部分链入结果链表。 else pre->next=pb;

free(la);∥释放头结点.ha,hb指针未被破坏。 }∥算法nion结束。

(2)本题与上面两题类似，要求结果指针为lc，其核心语句段如下： pa=la->next;pb=hb->next;

lc=(LinkedList )malloc(sizeof(LNode)); pc=lc;∥pc是结果链表中当前结点的前驱 while(pa&&pb)

if(pa->datadata)

{pc->next=pa;pc=pa;pa=pa->next;} else {pc->next=pb;pc=pb;pb=pb->next;} if(pa)pc->next=pa; else pc->next=pb;

free(la);free(lb);∥释放原来两链表的头结点。 算法时间复杂度为O（m+n），其中m和n分别为链表la和lb的长度。

2．[题目分析]本组题有6个，本质上都是链表的合并操作，合并中有各种条件。与前组题不同的是，叙述上是用线性表代表集合，而操作则是求集合的并、交、差（A∪B，A∩B，A-B）等。

本题与上面1．（2）基本相同，不同之处1．（2）中链表是“非递减有序”，（可能包含相等元素），本题是元素“递增有序”（不准有相同元素）。因此两表中合并时，如有元素值相等元素，则应删掉一个。

LinkedList Union(LinkedList ha,hb)

∥线性表A和B代表两个集合，以链式存储结构存储，元素递增有序。ha和hb分别

是其链表的头指针。本算法求A和B的并集A∪B，仍用线性表表示，结果链表元素也是递增有序。

{ pa=ha->next;pb=hb->next;∥设工作指针pa和pb。 pc=ha;∥pc为结果链表当前结点的前驱指针。 while(pa&&pb)

if(pa->datadata)

{pc->next=pa;pc=pa;pa=pa->next;} else if(pa->data>pb->data)

{pc->next=pb;pc=pb;pb=pb->next;} else∥处理pa->data=pb->data.

{pc->next=pa;pc=pa;pa=pa->next; u=pb;pb=pb->next;free(u);}

if(pa) pc->next=pa;∥ 若ha表未空，则链入结果表。

else pc->next=pb;∥若hb表未空，则链入结果表。 free(hb); ∥释放hb头结点 return(ha);

}∥算法Union结束。

与本题类似的其它几个题解答如下： (1) 解答完全同上2。

(2) 本题是求交集，即只有同时出现在两集合中的元素才出现在结果表中。其核心语句段如下：

pa=la->next;pb=lb->next;∥设工作指针pa和pb； pc=la;∥结果表中当前合并结点的前驱的指针。 while(pa&&pb)

if(pa->data==pb->data)∥交集并入结果表中。 { pc->next=pa;pc=pa;pa=pa->next;

u=pb;pb=pb->next;free(u);}

else if(pa->datadata) {u=pa;pa=pa->next;free(u);}

else {u=pb; pb=pb->next; free(u);}

while(pa){ u=pa; pa=pa->next; free(u);}∥ 释放结点空间 while(pb) {u=pb; pb=pb->next; free(u);}∥释放结点空间 pc->next=null;∥置链表尾标记。

free(lb); ∥注： 本算法中也可对B表不作释放空间的处理

（3）本题基本与（2）相同，但要求无重复元素，故在算法中，待合并结点数据要与其前驱比较，只有在与前驱数据不同时才并入链表。其核心语句段如下。 pa=L1->next;pb=L2->next;∥pa、pb是两链表的工作指针。 pc=L1;∥L1作结果链表的头指针。 while(pa&&pb)

if(pa->datadata) {u=pa;pa=pa->next;free(u);}∥删除L1表多余元素 else if (pa->data>pb->data) pb=pb->next; ∥pb指针后移 else ∥处理交集元素

{if(pc==L1) {pc->next=pa;pc=pa;pa=pa->next;} ∥处理第一个相等的元

素。

else if(pc->data==pa->data){ u=pa;pa=pa->next;free(u);} ∥重复元

素不进入L1表。

else{ pc->next=pa;pc=pa;pa=pa->next;} ∥交集元素并入结果表。

} ∥while

while(pa) {u=pa;pa=pa->next;free(u);} ∥ 删L1表剩余元素

pc->next=null; ∥置结果链表尾。

注： 本算法中对L2表未作释放空间的处理。

（4） 本题与上面（3）算法相同，只是结果表要另辟空间。

（5） [题目分析]本题首先求B和C的交集，即求B和C中共有元素，再与A求并集，同时删除重复元素，以保持结果A递增。

LinkedList union(LinkedList A,B,C)

∥A,B和C均是带头结点的递增有序的单链表，本算法实现A= A∪（B∩C），使求解结构保持递增有序。

{pa=A->next;pb=B->next;pc=C->next;∥设置三个工作指针。

pre=A; ∥pre指向结果链表中当前待合并结点的前驱。

if(pa->datadata||pa->datadata)∥A中第一个元素为结果表的第一元素。

{pre->next=pa;pre=pa;pa=pa->next;}

else{while(pb&&pc) ∥找B表和C表中第一个公共元素。 if(pb->datadata)pb=pb->next;

else if(pb->data>pc->data)pc=pc->next;

else break; ∥找到B表和C表的共同元素就退出while循环。 if(pb&&pc)∥ 因共同元素而非B表或C表空而退出上面while循环。 if(pa->data>pb->data)∥A表当前元素值大于B表和C表的公共元素，先将B

表元素链入。

{pre->next=pb;pre=pb;pb=pb->next;pc=pc->next;}∥ B，C公共元素为结果

表第一元素。

}∥结束了结果表中第一元素的确定 while(pa&&pb&&pc) {while(pb&&pc)

if(pb->datadata) pb=pb->next;

else if(pb->data>pc->data) pc=pc->next; else break; ∥B表和C表有公共元素。 if(pb&&pc)

{while(pa&&pa->datadata) ∥先将A中小于B，C公共元素部分链入。 {pre->next=pa;pre=pa;pa=pa->next;}

if(pre->data!=pb->data){pre->next=pb;pre=pb;pb=pb->next;pc=pc->next;} else{pb=pb->next;pc=pc->next;}∥ 若A中已有B，C公共元素，则不再存入结果表。 }

}∥ while(pa&&pb&&pc) if(pa) pre->next=pa; ∥当B，C无公共元素（即一个表已空），将A中剩余链入。 }∥算法Union结束

[算法讨论]本算法先找结果链表的第一个元素，这是因为题目要求结果表要递增有序（即删除重复元素）。这就要求当前待合并到结果表的元素要与其前驱比较。由于初始pre=A（头结点的头指针），这时的data域无意义，不能与后继比较元素大小，因此就需要确定第一个元素。当然，不要这样作，而直接进入下面循环也可以，但在链入结点时，必须先判断pre是否等于A，这占用了过多的时间。因此先将第一结点链入是可取的。 算法中的第二个问题是要求时间复杂度为O（|A|+|B|+|C|）。这就要求各个表的工作指针只能后移（即不能每次都从头指针开始查找）。本算法满足这一要求。 最后一个问题是，当B，C有一表为空（即B和C已无公共元素时），要将A的剩余部分链入结果表。

3．[题目分析]循环单链表L1和L2数据结点个数分别为m和n ，将二者合成一个循环单链表时，需要将一个循环链表的结点（从第一元素结点到最后一个结点）插入到另一循环链表的第一元素结点前即可。题目要求“用最快速度将两表合并“，因此应找结点个数少的链表查其尾结点。

LinkedList Union(LinkedList L1,L2;int m,n)

∥L1和L2分别是两循环单链表的头结点的指针，m和n分别是L1和L2的长度。 ∥本算法用最快速度将L1和L2合并成一个循环单链表。 {if(m<0||n<0) {printf(“表长输入错误\\n”)；exit(0);}

if(m

while(p->next!=L1) p=p->next;∥查最后一个元素结点。

p->next=L2->next;∥将L1循环单链表的元素结点插入到L2的第一元素结点前。

L2->next=L1->next;

free(L1);∥释放无用头结点。 }

}∥处理完m

else∥ 下面处理L2长度小于等于L1的情况 {if(n==0)return(L1);∥L2为空表。 else{p=L2;

while(p->next!=L2) p=p->next;∥查最后元素结点。

p->next=L1->next;∥将L2的元素结点插入到L1循环单链表的第一元素结点前。

L1->next=L2->next;

free(L2);∥释放无用头结点。

}

}∥算法结束。

类似本题叙述的其它题解答如下：

（1）[题目分析]本题将线性表la和lb连接，要求时间复杂度为O（1），且占用辅助空间尽量小。应该使用只设尾指针的单循环链表。

LinkedList Union(LinkedList la,lb)

∥la和lb是两个无头结点的循环单链表的尾指针，本算法将lb接在la后，成为一

个单循环链表。

{ q=la->next; ∥q指向la的第一个元素结点。

la->next=lb->next; ∥将lb的最后元素结点接到lb的第一元素。

lb->next=q; ∥将lb指向la的第一元素结点，实现了lb接在la后。 return(lb); ∥返回结果单循环链表的尾指针lb。 }∥算法结束。

[算法讨论]若循环单链表带有头结点，则相应算法片段如下： q=lb->next; ∥q指向lb的头结点；

lb->next=la->next; ∥lb的后继结点为la的头结点。

la->next=q->next; ∥la的后继结点为lb的第一元素结点。 free(q); ∥释放lb的头结点

return(lb); ∥返回结果单循环链表的尾指针lb。 （2）[题目分析]本题要求将单向链表ha和单向循环链表hb合并成一个单向链表，要求算法所需时间与链表长度无关，只有使用带尾指针的循环单链表，这样最容易找到链表的首、尾结点，将该结点序列插入到单向链表第一元素之前即可。 其核心算法片段如下（设两链表均有头结点）

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->link; ∥r是p的后继。 q=list;

if(q->data>p->data)∥处理待排序结点p比第一个元素结点小的情况。 {p->link=list;

list=p;∥链表指针指向最小元素。 }

else∥查找元素值最小的结点。

{while(q->link!=null&&q->link->datadata)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->datadata)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的后继。 q=la;

while(q->next!=null&&q->next->datadata)q=q->next;∥查找插入位置。 p->next=q->next;∥将p结点链入链表。

q->next=p; p=r; }

与本题有类似叙述的题的解答：

（1）本题也是链表排序问题，虽没象上题那样明确要求“利用直接插入的原则”来排序，仍可用上述算法求解，这里不再赘述。

7．[题目分析]本题要求将一个链表分解成两个链表，两个链表都要有序，两链表建立过程中不得使用NEW过程申请空间，这就是要利用原链表空间，随着原链表的分解，新建链表随之排序。

PROC discreat(VAR listhead,P,Q:linkedlist)

∥listhead是单链表的头指针，链表中每个结点由一个整数域DATA和指针域NEXT组成。本算法将链表listhead分解成奇数链表和偶数链表，分解由P和Q指向，且P和Q链表是有序的。

P:=NIL;Q:=NIL;∥P和Q链表初始化为空表。 s:=listhead; WHILE(s<>NIL)DO

[r:=s^.NEXT; ∥暂存s的后继。 IF s^.DATA DIV 2=0 ∥处理偶数。

THEN IF P=NIL THEN[P:=s;P^.NEXT:=NIL;] ∥第一个偶数链结点。

ELSE[pre:=P;

IF pre^.DATA>s^.DATA THEN[s^.NEXT:=pre;P:=s;∥插入当前最小值结

点修改头指针]

ELSE[WHILE pre^.NEXT<>NIL DO

IF pre^.NEXT^.DATA

s^.NEXT:=pre^.NEXT; ∥链入此结点。 pre^.NEXT:=s; ]

]

ELSE∥处理奇数链。

IF Q=NIL THEN[Q:=s;Q^.NEXT:=NIL;] ∥第一奇数链结点。 ELSE[pre:=Q;

IF pre^.DATA>s^.DATA THEN[s^.NEXT:=pre; Q:=s; ]∥修改头指针。

ELSE[WHILE pre^.NEXT<>NIL DO ∥查找插入位置。

IF pre^.NEXT^.DATA

]∥结束奇数链结点

s:=r;∥s指向新的待排序结点。 ]∥结束“WHILE(s<>NIL)DO” ENDP；∥结束整个算法。 [算法讨论]由于算法要求“不得使用NEW过程申请空间，也没明确指出链表具有头结点，所以上述算法复杂些，它可能需要在第一个结点前插入新结点，即链表的头指针会发生变化。

如有头结点，算法不必单独处理在第一个结点前插入结点情况，算法会规范统一，下面的（1）是处理带头结点的例子。算法中偶数链上结点是靠数据整除2等于0（DATA DIV 2=0）判断的。

类似本题的其它题解答如下：

（1）[题目分析]本题基本类似于上面第7题，不同之处有二。一是带头结点，二是分解后的两个链表，一个是数据值小于0，另一个是数据值大于0。由于没明确要求用类PASCAL书写算法，故用C书写如下。

void DisCreat1(LinkedList A)

∥A是带头结点的单链表，链表中结点的数据类型为整型。本算法将A分解成两个单链表B和C，B中结点的数据小于零，C中结点的数据大于零。 {B=A;

C=(LinkedList )malloc(sizeof(LNode));∥为C申请结点空间。 C->next=null ∥C初始化为空表。 p=A->next; ∥p为工作指针。 B->next=null; ∥B表初始化。 while(p!=null)

{r=p->next; ∥暂存p的后继。

if (p->data<0)∥小于0的放入B表。

{p->next=B->next; B->next=p; }∥将小于0的结点链入B表。 else {p->next=C->next; C->next=p; } p=r;∥p指向新的待处理结点。 }

}∥算法结束。

[算法讨论]因为本题并未要求链表中结点的数据值有序，所以算法中采取最简单方式：将新结点前插到头结点后面（即第一元素之前）。 （2） 本题同上面第7题，除个别叙述不同外，本质上完全相同，故不再另作解答。

（3）[题目分析]本题中的链表有头结点，分解成表A和表B，均带头结点。分解后的A表含有原表中序号为奇数的元素，B表含有原A表中序号为偶数的元素。由于要求分解后两表中元素结点的相对顺序不变，故采用在链表尾插入比较方便，这使用一指向表尾的指针即可方便实现。

void DisCreat3(LinkedList A)

∥A是带头结点的单链表，本算法将其分解成两个带头结点的单链表，A表中含原表中序号为奇数

∥的结点，B表中含原表中序号为偶数的结点。链表中结点的相对顺序同原链表。 {i=0;∥i记链表中结点的序号。

B=(LinkedList)malloc(sizeof(LNode);∥创建B表表头。 B->next=null; ∥B表的初始化。

LinkedList ra,rb;∥ra和rb将分别指向将创建的A表和B表的尾结点。 ra=A;rb=B;

p=A->next; ∥p为链表工作指针，指向待分解的结点。 A->next=null; ∥置空新的A表 while(p!=null)

{r=p->next; ∥暂存p的后继。 i++;

if(i%2==0) ∥处理原序号为偶数的链表结点。

{p->next=rb->next;∥在B表尾插入新结点； rb->next=p; rb=p;∥rb指向新的尾结点； }

else∥处理原序号为奇数的结点。

{p->next=ra->next; ra->next=p; ra=p; }

p=r; ∥将p恢复为指向新的待处理结点。 }∥算法结束

8．[题目分析]题目要求重排n个元素且以顺序存储结构存储的线性表，使得所有值为负数的元素移到正数元素的前面。这可采用快速排序的思想来实现，只是提出暂存的第一个元素（枢轴）并不作为以后的比较标准，比较的标准是元素是否为负数。 int Rearrange（SeqList a; int n)

∥a是具有n个元素的线性表，以顺序存储结构存储，线性表的元素是整数。本算法重

排线性表a，

∥使所有值为负数的元素移到所有值为正数的数的前面。 {i=0; j=n-1; ∥ i,j为工作指针（下标），初始指向线性表a的第1个和第n个元

素。

t=a[0]; ∥暂存枢轴元素。 while(i

{while(i=0) j--; ∥ 若当前元素为大于等于零，则指针前移。 if(i

while(i

a[i]=t; ∥将原第一元素放到最终位置。 }

[算法讨论] 本算法时间复杂度为O（n）。算法只是按题目要求把正负数分开，如要求统计负数和大于等于零的个数，则最后以t来定。如t为负数，则0至i共i+1个负数，n-1-i个正数（包括零）。另外，题目并未提及零的问题，笔者将零放到正数一边。对此问题的扩充是若元素包含正数、负数和零，并要求按负数、零、正数的顺序重排线性表，统计负数、零、正数的个数。请读者利用上面解题思想自行解答。 类似本题的选了5 个题，其解答如下：

（1）与上面第8题不同的是，这里要求以an为参考元素，将线性表分成左右两部分。左半部分的元素都小于等于an，右半部分的元素都大于an，an位于分界位置上。其算法主要片段语句如下:

i=1;j=n;

t=a[n]; ∥暂存参考元素。 while(i

{while(i

while(it) j--; ∥当前元素大于参考元素时指针前移。 if(i

a[i]=t; ∥参考元素置于分界位置。

(2) [题目分析]本题要求将线性表A分成B和C两个表，表B和表C不另占空间，而是利用表A的空间，其算法与第8题相同。这里仅把表B和表C另设空间的算法解答如下： void Rearrange2(int A[],B[],C[])

∥线性表A有n个整型元素，顺序存储。本算法将A拆成B和C 两个表，B中存放

大于

∥等于零的元素，C中存放小于零的元素。

{i=0; ∥i，j，k是工作指针，分别指向A、B和C表的当前元素。 j=k=-1; ∥j，k初始化为-1。 while(i

{if(A[i]<0) C[++k]=A[i++]; ∥将小于零的元素放入C表。 else B[++j]=A[i++]; ∥将大于零的元素放入B表。

[算法讨论]本题用一维数组存储线性表，结果线性表B和C中分别有j+1和k+1个元素。若采用教材中的线性表，则元素的表示作相应改变，例如A.elem[i]，而最后B和C表应置上表的长度，如B.length=j和C.length=k。

(3) 本题与第8题本质上相同，第8题要求分开正数和负数，这里要求分开奇数和偶数，判别方式是a[i]%2==0，满足时为偶数，反之为奇数。 (4) 本题与第8题相同，只是叙述不同。

(5) 本题与第8题基本相同，不同之处在于这里的分界元素是整数19（链表中并不要

求一定有19）。本题要求用标准pascal描述算法，如下所示。 TYPE arr=ARRAY[1..1000] OF integer； VAR a：arr；

PROCEDURE Rearrange5（VAR a：arr）；

∥a是n（设n=1000）个整数组成的线性表，用一维数组存储。本算法将n个元素

中所有大于等于19的整数放在所有小于19的整数之后。

VAR i,j,t：integer； BEGIN

i:=1；j:=n；t:=a[1] ；∥i,j指示顺序表的首尾元素的下标，t暂存分界元素 WHILE（i

WHILE （i=19） DO j:=j-1；

IF（i

IF（i

[算法讨论] 分界元素t放入a[i]，而不论它的值如何。算法中只用了一个t中间变量，符合空间复杂度O(1)的要求。算法也满足时间复杂度O(n)的要求。

9．[题目分析] 本题要求在单链表中删除最小值结点。单链表中删除结点，为使结点删除后不出现“断链”，应知道被删结点的前驱。而“最小值结点”是在遍历整个链表后才能知道。所以算法应首先遍历链表，求得最小值结点及其前驱。遍历结束后再执行删除操作。

LinkedList Delete（LinkedList L）

∥L是带头结点的单链表，本算法删除其最小值结点。

{p=L->next； ∥p为工作指针。指向待处理的结点。假定链表非空。

pre=L； ∥pre指向最小值结点的前驱。

q=p； ∥q指向最小值结点，初始假定第一元素结点是最小值结点。 while（p->next!=null）

{if（p->next->datadata）{pre=p；q=p->next；} ∥查最小值结点 p=p->next； ∥指针后移。 }

pre->next=q->next；∥从链表上删除最小值结点 free（q）； ∥释放最小值结点空间 }∥结束算法delete。

[算法讨论] 算法中函数头是按本教材类C描述语言书写的。原题中void delete（linklist &L），是按C++的“引用”来写的，目的是实现变量的“传址”，克服了C语言函数传递只是“值传递”的缺点。

10．[题目分析] 本题要求将链表中数据域值最小的结点移到链表的最前面。首先要查找最小值结点。将其移到链表最前面，实质上是将该结点从链表上摘下（不是删除并回收空间），再插入到链表的最前面。

LinkedList delinsert（LinkedList list）

∥list是非空线性链表，链结点结构是（data，link），data是数据域，link是链域。

∥本算法将链表中数据域值最小的那个结点移到链表的最前面。 {p=list->link；∥p是链表的工作指针

pre=list； ∥pre指向链表中数据域最小值结点的前驱。 q=p； ∥q指向数据域最小值结点，初始假定是第一结点 while （p->link!=null）

{if（p->link->datadata）{pre=p；q=p->link；} ∥找到新的最小值结点； p=p->link； }

if (q!=list->link) ∥若最小值是第一元素结点，则不需再操作 {pre->link=q->link； ∥将最小值结点从链表上摘下； q->link= list->link；∥将q结点插到链表最前面。 list->link=q；

}

}∥算法结束

[算法讨论] 算法中假定list带有头结点，否则，插入操作变为q->link=list；list=q。 11．[题目分析] 知道双向循环链表中的一个结点，与前驱交换涉及到四个结点（p结点，前驱结点，前驱的前驱结点，后继结点）六条链。

void Exchange（LinkedList p）

∥p是双向循环链表中的一个结点，本算法将p所指结点与其前驱结点交换。 {q=p->llink；

q->llink->rlink=p； ∥p的前驱的前驱之后继为p p->llink=q->llink； ∥p的前驱指向其前驱的前驱。 q->rlink=p->rlink； ∥p的前驱的后继为p的后继。 q->llink=p； ∥p与其前驱交换

p->rlink->llink=q； ∥p的后继的前驱指向原p的前驱 p->rlink=q； ∥p的后继指向其原来的前驱

本文来源：https://www.bwwdw.com/article/td3a.html