数据结构期末复习提要.pdf

《数据结构期末复习提要.pdf》由会员分享，可在线阅读，更多相关《数据结构期末复习提要.pdf（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构期末复习提要中央电大理工部计算机教研室数据结构是中央电大计算机应用专业门统设必修课和专业基础课，它主要研究数据的各种逻辑结构，在计算机中的存储结构，对数据进行的插入、查找、删除、排序、遍历等运算，这些运算在存储结构上具体实现的算法。学习好该课程将为学好整个计算机专业打下坚实的基础。第一部分各章复习要求下面按照主教材中各章次序给出每章的具体复习要求，以便指导同学们更好地进行期末复习。第 一 章 绪论重点掌握的内容：1.数据结构的二元组表示，对应的图形表示，序偶利边之间的对应关系。2.集合结构、线性结构、树结构和图结构的特点。3.抽象数据类型的定义和表示方法。4.一维和二维数组中元素的按下

2、标和按地址的访问方式以及相互转换，元素地址和数组地址的计算，元素占用存储空间大小和数组占用存储空间大小的计算。5.普通函数重裁和操作符函数重载的含义，定义格式和调用格式。6.函数定义中值参数和引用参数的说明格式及作用，函数被调用执行时对传送来的实际参数的影响。7.算法的时间复杂度和空间复杂度的概念，计算方法，数量级表示。8.一个简单算法的最好、最差和平均这三种情况的时间复杂度的计算。对于本章的其余内容均作一般掌握。第 二 章 线性表重点掌握的内容：1.线性表的定义和抽象数据类型的描述，线性表中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。2.线性表的顺序存储结构的类型定义

3、，即 L is t类型的定义和每个域的定义及作用。3.线性表的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。4.链接存储的概念，线性表的单链接和双链接存储的结构，向单链表中一个结点之后插入新结点或从单链表中删除一个结点的后继结点的指针链接过程。5.单链表中结点的结构，每个域的定义及作用，即 LNodc类型的定义及结构。6.带表头附加结点的链表、循环链表、双向链表的结构特点。7.线性表的每一种运算在单链表上实现的算法及相应的时间复杂度。8.在顺序存储或链接存储的线性表上实现指定功能的算法的分析和设计。对于本章的其余内容均作一般掌握。第 三 章 稀疏矩阵和广义表重点掌握的内容：1.稀疏

4、矩阵的定义和三元组线性表表示。2.稀疏矩阵的顺序存储、带行指针向量的链接存储、卜字链接存储的类型定义，在每一种存储中非零元素结点的结构。3.广义表的定义和表示，广义表长度和深度的计算。4.广义表的链接存储结构中结点类型的定义，分别求广义表长度和深度的递归算法，它们对应的时间复杂度。一般掌握的内容：L稀疏矩阵的转置运算和算法描述。2.两个稀疏矩阵的做加法的过程和算法描述。对于本章的其余内容均作一般了解。第四章栈和队列重点掌握的内容：1.栈的定义和抽象数据类型的描述，栈中每种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。2.栈的顺序存储结构的类型定义，即 Stack类型的定义和每个

5、域的定义及作用。3.栈的每一种运算在顺序存储结构.上实现的算法，及相应的时间复杂度。4.栈的每一种运算在链接存储结构上实现的算法及相应的时间复杂度。5.算术表达式的中缀表示和后缀表示，以及相互转换的规则，后缀表达式求值的方法。6.队列的定义和抽象数据类型的描述，队列中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。7.队列的顺序存储结构的类型定义，即 Queue类型的定义和每个域的定义及作用。8.队列的每一种运算在顺序存储结构上实现的算法及相应的时间复杂度。9.利用栈和队列解决简单问题的算法分析和设计。一般掌握的内容：1.后缀表达式求值的算法，把中缀表达式转换为后缀表达式的

6、算法。2.求解阶乘问题和迷宫问题的方法和算法。3.队列的链接存储结构，以及实现每一种队列运算的算法和相应的时间复杂度。第 五 章 树和二叉树重点掌握的内容：1 .树和二叉树的定义，对于一棵具体树和二叉树的二元组表示及广义表表2 .树和二叉树的概念，如结点的度、树的度、树的层数、树的深度等。3 .树和二叉树的性质，如己知树或二叉树的深度h可求出相应的最多结点数，已知结点数n可求出对应树或二叉树的最大和最小高度。4 .二叉树中结点的编号规则和对应的顺序存储结构。5 .二叉树的链接存储结构及存储结点的类型定义，即 B T r e e N o de 类型的定义和每个域的定义及作用。6 .二叉树的先序、

7、中序、后序遍历的递归过程和递归算法，中序遍历的非递归算法，按层遍历的过程和算法，每种算法的时间复杂度。7 .普通树的链接存储结构,GT r e e N o de 类型的定义和每个域的定义及作用。8 .普通树的先根、后根和按层遍历的过程及算法。9 .在链接存储的二叉树上 实现指定功能的算法分析和设计。对于本章的其余内容均作一般掌握。第 六 章 二叉树的应用重点掌握的内容：1 .二叉搜索树的定义和性质。2 .二叉搜索树查找的递归算法和非递归算法，相应的时间复杂度，查找一个元素的查找长度，即从树根结点到该结点的路径上的结点数。3 .二叉搜索树插入的递归算法和非递归算法，相应的时间复杂度，根 据-组数

8、据生成一棵二叉搜索树的过程。4 .堆的定义和顺序存储结构，小根堆和大根堆的异同。5 .向堆中插入元素的过程、算法描述及时间复杂度。6 .从堆中删除元素的过程、算法描述及时间复杂度。7 .哈夫曼树的定义，树的带权路径长度的计算，根据若干个叶子结点的权构造哈夫曼树的过程。对本章的其余内容均作一般了解。第 七 章 图重点掌握的内容：1 .图的顶点集和边集的表示。2 .图的一些概念的含义，如顶点、边、度、完全图、子图、路径、路径长度、连通图、权、网等。3 .图的邻接矩阵、邻接表和边集数组三种存储结构及相应的空间复杂度。4 .存储图使用的 v e x l i s t,a dj ma t r i x,a

9、dj l i s t,e dg e n o de,e dg e s e t,e dg e 等类型的定义及用途。5 .图的深度优先和广度优先搜索遍历的过程。6 .对分别用邻接矩阵和用邻接表表示的图进行深度优先搜索遍历的过程、算法描述以及相应的时间复杂度。7 .对分别用邻接矩阵和用邻接表表示的图进行广度优先搜索遍历的过程、算法描述以及相应的时间复杂度。8 .图的生成树、生成树的权、最小生成树等的定义。9 .根据普里姆算法求图的最小生成树的过程和算法描述。1 0 .根据克鲁斯卡尔算法求图的最小生成树的过程和算法描述。1 1 .图的拓扑序列和拓扑排序的概念，求图的拓扑序列的方法，对用邻接表表示的图进行

10、拓扑排序的过程和算法。对本章的其余内容均作一般掌握。它包括建立图的邻接矩阵、邻接表、边集数组算法，建立图的逆邻接表和卜字邻接表等内容。第 八 章 查找重点掌握的内容：1 .在一维数组上进行顺序查找的过程、算法、平均查找长度和时间复杂度。2 .在一维数组上进行二分查找的过程、递归和非递归算法、平均查找长度和时间复杂度，二分查找一个给定值元素的查找长度（即查找路径上的元素数）,二分查找对应的判定树的性质。3 .索引存储的概念，索引表的存储结构和索引项的存储结构，索引查找一个元素的过程、平均查找长度和时间复杂度。4 .散列存储的概念，散列函数、散列表、冲突、同义词、装填因子等术语的含义。5 .利用除

11、留余数法建立散列函数求元素散列地址的方法。6 .利用开放定址法中的线性探查法处理冲突进行散列存储和查找的过程,利用链接法处理冲突进行散列存储和查找的过程。7 .根据除留余数法构造散列函数，采用线性探查法或链接法处理冲突，把一组数据散列存储到散列表中，计算出个给定值元素的查找长度和查找所有元素的平均查找长度。8 .B 树中每个结点的结构，树根结点或非树根结点中关键字的个数范围和子树的个数范围，B-的结构特性，从 B _ 树上查找一个给定值元素的过程。一般掌握的内容：1 .索引查找和分块查找算法。2 .B树查找算法。3.向B树中插入元素的过程。对本章的其余内容均作一般了解。第 九 章 排序重点掌握

12、的内容：1 .直接插入、直接选择和冒泡排序的方法，排序过程及时间复杂度。2 .在堆排序中建立初始堆的过程和利用堆排序的过程，对一个分支结点进行筛运算的过程、算法及时间复杂度，整个堆排序的算法描述及时间复杂度。3 .快速排序的方法，对一组数据的排序过程，对应的二叉搜索树，快速排序过程中划分的层数和递归排序区间的个数。4 .快速排序的递归算法，它在平均情况下的时间和空间复杂度，在最坏情况 F 的时间和空间复杂度。5 .二路归并排序的方法和对数据的排序过程，每趟排序前、后的有序表长度，二路归并排序的趟数、时间复杂度和空间复杂度。一般掌握的内容：1 .每一种排序方法的稳定性。2 .直接插入排序和直接选

13、择排序的算法。一般了解的内容：1 .二路归并排序过程中涉及的每个算法。2 .冒泡排序算法。第二 部 分 期末复习题示例一、单 选 题(每小题2 分，共 8分)1 .在 个单链表H L 中，若要向表头插入一个由指针p指向的结点，则执行。A HL=p;p-ne x t=HL;B p-ne x t=HL;HL=p;C p-ne x t=HL;p=HL;D p-ne x t=HL-ne x t;HL-ne x t=p;2 .在一个顺序队列中，队首指针指向队首元素的 位置。A前一个 B后一个 C当前3 .从二叉搜索树中查找一个元素时，其时间复杂度大致为 oA 0(n)B 0(1)C O(l o g2n)

14、D 0(n2)4 .由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为。A 2 4B 4 8C 7 2D 5 3二、填 空 题(每 空 1 分，共 3 2 分)1 .一个算法的时间复杂度为(3/+2 l o g 2 加4 k7)/(5 )，其数量级表示为O2 .在以H L 为表头指针的带表头附加结点的单链表和循环单链表中，链衣为空的条件分别为一 一 和 。3 .个广义表中的元素分为 元素和 元素两类。4 .从一个链栈中删除一个结点时，需要把栈顶结点的 域的值赋_ o5 .在进行函数调用时，需要把每个实参的值和调用后的 传送给被调用的函数中。6 .对于一棵具有n个结点的

15、二叉树，若一个结点的编号为i(l i Wn),则 它 的 左 孩 子 结 点 的 编 号 为，右 孩 子 结 点 的 编 号 为，双亲结点的编号为 o7 .在一棵高度为5的理想平衡树中，最少含有_ _ _ 个结点，最多含有个结点。8 .在一个堆的顺序存储中，若一个元素的下标为i(OWi Wn-l),则它的左 孩 子 元 素 的 下 标 为,右孩子元素的下标为 o9 .在一个具有n 个顶点的无向完全图中，包含有 条边，在一个具有 n 个顶点的有向完全图中，包含有 条边。1 0 .对于一个具有n个顶点和e 条边的有向图和无向图，若采用边集数组表示，则存于数组中的边数分别为一 和 条。1 1 .以二

16、分查找方法从长度为1 2 的有序表中查找一个元素时，平均查找长度为。1 2 .假定一个线性表为(1 2,2 3,7 4,5 5,6 3,4 0,8 2,3 6),若按K ey%3 条件进行划分，使得同一余数的元素成为一个子表，则得到的三个子表分别为、和。1 3 .在线性表的散列存储中，装填因子a 又称为装填系数，若 用 m表示散列表的长度，n 表示待散列存储的元素的个数，贝皈等于。1 4 .在一棵m阶也树上，每个非树根结点的关键字数目最少为一 个,最多为 个，其 子 树 数 目 最 少 为，最多为。1 5 .在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为整 个 堆 排 序 过 程 的

17、 时 间 复 杂 度 为。1 6 .快速排序在平均情况下的时间复杂度为，在最坏情况下的时间复杂度为。三、运算题(每小题6 分，共 2 4 分)1.假定一棵二叉树广义表表示为a(b(c),d(e,f),分别写出对它进行先序、中序、后序、按层遍历的结果。先序：中序：后序：按层：2 .已知一个图的顶点集V和边集G分别为：V=0,1,2,3,4,5,6,7);E=(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)2 5,(2,4)1 3,(3,5)9,(3,6)1 0,(4,6)4,(5,7)2 0 ;按照普里姆算法从顶点0出发得到最小生成树，试写出在最小生成树中依次得到的各条边。3

18、.已知一个图的顶点集V和边集G分别为：V=0,1,2,3,4,5,6,7,8);E=,;若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，则按主教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列(提示：先画出对应的图形，然后再运算)。拓扑序列：4.假 定 一组记录的排序码为(4 6,7 9,5 6,3 8,4 0,8 0,2 5,3 4),则对其进行快速排序的第一次划分的结果为 o四、阅读算法，回答 问 题(每小题8分，共16分)1.voi d AE(Stac kf t S)(Ini tStac k(S);Push (S,3 0);Push (S,4 0):

19、Push(S,5 0);i nt x=Pop(S)+2*Pop(S);Push(S,x);i nt i,a4 =5,8,12,15);f or(i=0;i 4;i+)Push ai);wh i le(JStac kEmpty(S)c out Pop(S)ad j ve x;i f(!vi si te d j)c out j,J;vi si te d j=true;QInse rt(Q,j);p=p-ne xt;)该算法的功能为：五、算法填空，在画有横线的地方填写合适的内容(10 分)。向以BST为树根指针的二叉搜索树上插入值为i te m的结点的递归算法。voi d Inse rt(BTre

20、e Nod e*&BST,c onst Ele mTy pe f t i te m)i f(BST二 二 NULL)BTre e Nod e*p=ne w BTre e Nod e;p-data=item;BST=p;)else if(itemdata);else;)六、编写算法(10分)编写向类型为L is t的线性表L 中第i 个元素位置插入一个元素的算法，假定不需要对i 的值进行有效性检查，同时不需要检查存储空间是否用完。void Insert(List&L,int i,ElemType x)第三 部 分 期末复习题示例解答及评分标准一、单选题(每小题2 分，共 8 分)评分标准：选对者

21、得2 分，否则不得分。1.B 2.A 3.C 4.D二、填 空 题(每 空 1 分，共 32分)评分标准：每空得2 分，否则不得分。1.O(n)2.HL-next=NULL HL-next=HL3.单 表4.指 针 栈 顶 指 针5.返回地址6.2i 2i+l i/2(或Li/2)7.16 318.2i+l 2i+29.n(n-l)/2 n(nl)10.e e11.37/1212.(12,63,36)(55,40,82)(23,74)13.n/m1 4.m/21T m-l m/2|m15.O(log2n)O(nlog2n)16.O(nlog2n)O(n2)三、运算题(每小题6 分，共 24分)

22、3.拓扑序列：1,3,6,0,2,5,4,7,84.4 0 3 4 2 5 3 8 4 6 8 0 5 6 7 9 1.先序：a,b,c,d,e,f2分中序：c,b,a,e,d,f2分后序：c,b,e,f,d,a1分按层：a,b,d,c,e,f1分2.(0,3)2,(0,2)5,(0,1)8,(1,5)6,(3,6)10,(6,4)4,(5,7)2 0评分标准：每小题若有任何错误则应得分全扣。四、阅读算法，回答问题(每小题8分，共16分)1.15 12 8 5 13 0 3 0评分标准：有一处错扣4分，两处及以上错8分全扣。2 .从初始点火出发广度优先搜索由邻接表G L所表示的图。评分标准：请

23、根据叙述情况酌情给分。五、算法填空，在画有横线的地方填写合适的内容(10分)。p-le f t=p-ri g h t=NULLInse rt(BST-le f t,i te m)Inse rt(BST-ri g h t,i te m)评分标准：每空对给3分，全对给10分。六、编写算法(10分)评分标准：请根据编程情况酌情给分。voi d Inse rt(Li st&L,i nt i,Ele mTy pe x)(f or(i nt j=L.si z e T;j=i-l;j-)L.li stj+l=L.;L.li sti-l=x;L.si z e+;第四部分教材第二章部分习题参考解答一、单选题1.

24、B 2.A 3.C 4.B 5.D 6.C二、填空题1.值指针2.(3 8,5 6,2 5,6 0,4 2,7 4)3.0(n)0(1)4.0(1)0(n)5.i-1 i+16.p-ne xt ap.ne xt7.表头8.前驱后继9.表尾表头10.HL-n e x t=N U L L H L-n e x t=H L1 1.ai,n e x t=al.n e x t;al.n e x t=i;1 2.i=al,n e x t;al.n e x t=ai,n e x t;1 3.p=ai,n e x t;ai,n e x t=ap,n e x t;i=p;1 4.aj.n e x t=ai,n e

25、 x t;ai,n e x t=j;三、普通题第1小题1.(7 9,6 2,2.(2 6,3 4,3.(4 8,5 6,4.(5 6,5 7,5.(2 6,3 4,第2小题3 4,5 7,2 6,4 8)4 8,5 7,6 2,7 9)5 7,6 2,7 9,3 4)7 9,3 4)3 9,4 8,5 7,6 2)分析：为了排版方便,假定采用以下输出格式表示单链表示意图：每个括号内的数据表示一个元素结点，其中第一个数据为元素值，第二个数据为后继结点的指针，第一个元素结点前的数值为表头指针。1.(7(7 9,6),(6 2,5),2.(3(2 6,5),(3 4,2),3.(2(4 8,8),(

26、5 6,4),4.(8(5 6,4),(5 7,7),(3 4,4),(5 7,3),(2 6,2),(4 8,4),(5 7,6),(6 2,7),(5 7,6),(6 2,7),(7 9,5),(7 9,5),(3 4,0)(4 8,0)(7 9,0)(3 4,0)第3小题1.E l e m T y p e D M V al u e(L i s t&L)从线性表中删除具有最小值的元素并山函数返回，空出的位置由最后个元素填补，若线性表为空则显示出错信息并退出运行。(i f(L i s t E m p t y(L)c e r r z，L i s t i s E m p t y!z/e n dl

27、;e x i t (1);E l e m T y p e x;x=L.l i s t 0;i n t k=0;f o r(i n t i=l;i L.s i z e;i+)E l e m T y p e y=L.l i s t i;i f (y x)x=y;k=i;)L.l i s t k=L.l i s t L.s i z e-1;L.s i z e ;r e t u r n x;)2.i n t D e l e t e l (L i s t&L,i n t i)从线性表中删除第i 个元素并由函数返回。(i f(i L.s i z e)ce r r ，I n de x i s o u t r

28、 an g e!/z e n dl;e x i t (1);)E l e m T y p e x;x=L.l i s t i-1;f o r(i n t j=i-l;j L.s i z e-1;j+)L.l i s t j=L.l i s t j+l;L.s i z e 一；r e t u r n x;3.v o i d I n s e r t l(L i s t&L,i n t i,E l e m T y p e x)向线性表中第i 个元素位置插入一个元素。(i f(i L.s i z e+1)ce r r I n de x i s o u t r an g e!z/e n d 1;e x

29、i t (1);)i f(L.s i z e 二 二 M ax S i z e)ce r r，L i s t o v e r f l o w!=i-l;j 一)L.l i s t j+l=L.l i s t j;L.l i s t i-l=x;L.s i z e+;)4.v o i d D e l e t e 2 (L i s t&L,E l e m T y p e x)从线性表中删除具有给定值x的所有元素。(i n t i=0;w h i l e(i L.s i z e)i f (L.l i s t i=x)f o r(i n t j=i+l；j L.s i z e;j+)L.l i s t

30、 j-l=L.l i s t j;L.s i z e 一；)e l s ei+；)5.v o i d D e l e t e 3(L i s t&L,E l e m T y p e s,E l e m T y p e t)从线性表中删除其值在给定值s 和 t 之间的所有元素。(i n t i=0;w h i l e(i =s)&(L.l i s t i =t)f o r(i n t j=i+l;j L.s i z e;j+)L.l i s t j-l=L.l i s t j;L.s i z e 一；)e l s ei+；)6.v o i d D e l e t e 4(L i s t&L,E

31、l e m T y p e s,E l e m T y p e t)从有序表中删除其值在给定值s 和 t 之间的所有元素。i n t i=0;w h i l e(i L.s i z e)/从有序表L 中查找出大于等于s 的第一个元素。i f(L.l i s t i s)i+;e l s e br e ak;i f (i L.s i z e)(i n t j=l;w h i l e(i+j L.s i z e)&(L.l i s t i+j =t)j+；求出s 和 t 之间元素的个数。f o r(i n t k=i+j;k M ax S i z e)ce r r/L i s t o v e r

32、f l o w!z/e n dl;e x i t (1);)i n t i=0,j=0,k=0;w h i l e(i L l.s i z e)&(j L 2.s i z e)i f(L I.l i s t i =L 2.l i s t j)将口中的元素赋给L。L.l i s t k=L l.l i s t i;i+；)e l s e 将L 2 中的元素赋给L。L.l i s t k=L 2.l i s t j;j+；)k+;)w h i l e(i L l.s i z e)将L I 中剩余的元素赋给L。L.l i s t k=L l.l i s t i;i+;k+;w h i l e(j L

33、 2.s i z e)将L 2 中剩余的元素赋给L。L.l i s t k=L 2.l i s t j;j+；k+;)L.s i z e=k;)8.v o i d D e l e t e 5(L i s t&L)从线性表中删除所有其值重复的元素，使所有元素的值均不同。|i n t i=0;w h i l e(i L.s i z e)i n t j=i+l;w h i l e(j L.s i z e)删除重复值为L J i s t i 的所有元素i f (L.l i s t j=L.l i s t i)f o r(i n t k=j+l;k n e x t;/p 指向下一个待逆序的结点。将q结点

34、插入到已逆序单链表的表头。q-n e x t=H L;H L=q;2.v o i d D e l e t e 1 (L N o de*&H L,i n t i)删除单链表中的第i 个结点。(i f(i l|H L=N U L L)ce r r，I n de x i s o u t r an g e!，n e x t;j+；)i f(cp=N U L L)ce r r z，I n de x i s o u t r an g e!/z n e x t;e l s eap-n e x t=cp-n e x t;de l e t e cp;3.E l e m T y p e M ax V al u e

35、(L N o de*H L)从单链表中查找出所有元素的最大值，该值由函数返回。i f(H L=N U L L)ce r r dat a;L N o de*p=H L-n e x t;w h i l e(p!=N U L L)i f (m ax dat a)m ax=p-dat a;p=p-n e x t;)r e t u r n m ax;)4.i n t C o u n t (L N o de*H L,E l e m T y p e x)统计出单链表中结点的值等于给定值x的结点数。(i n t n=0;w h i l e(H L!=N U L L)i f(H L-dat a=x)n+;H L

36、=H L-n e x t;)r e t u r n n;5.v o i d C r e at e(L N o de*&H L,E l e m T y p e a,i n t n)根据一维数组a n 建立一个单链表(I n i t L i s t(H L);f o r(i n t i=n T;i =0;i)I n s e r t F r o n t(H L,ai);)6.v o i d O r de r L i s t(L N o de*&H L)将一个单链表重新链接成有序单链表。L N o de*p=H L;/p 指向待处理的第一个结点，初始指向原表头结点。H L 二 N U L L;/H L

37、 仍为待建立的有序表的表头指针，初始值为空。w h i l e (p!=N U L L)把原单链表中的结点依次进行有序链接。L N o de*q 二 p;q 指向待处理的结点。p=p-n e x t;/p 指向下一个待处理的结点。L N o de *ap=N U L L,*cp=H L;cp 指向有序表中待比较的结点，ap 指向其前驱结点。w h i l e(cp!=N U L L)为插入q结点寻找插入位置。i f(q-dat a dat a)br e ak;e l s e ap=cp;cp=cp-n e x t;)将q结点插入到ap 和 cp 结点之间。q-n e x t=cp;i f(ap

38、=N U L L)H L=q;e l s eap-n e x tz=q;)7.L N o de*M e r g e 1(L N o de*&p l,L N o de*&p 2)/将两个有序单链表合并成一个有序单链表。(L N o de a;/a结点作为结果有序单链表的表头附加结点，这样便于处理，处理结束后返回a 结点的指针域的值。L N o de*p 二&a;p 指向结果有序单链表的表尾结点，p-n e x t=N U L L;初始指向表头附加结点。w h i l e(p l!=N U L L)&(P2!=N U L L)处理两个表非空时的情况。i f(p l-dat a dat a)p-n

39、e x t=p l;p l=p l-n e x t;)e l s e p-n e x t=p 2;p 2=p 2-n e x t;)p=p-n e x t;)i f(p l!=N U L L)p-n e x t=p l;i f(p 2!=N U L L)p-n e x t=p 2;p l=p 2=N U L L;r e t u r n a.n e x t;)8.L N o de*M e r g e 2(L N o de*p l,L N o de*p 2)根据两个有序单链表生成一个新的有序单链表。(L N o de a;用a 作为新的有序单链表的表头附加结点。L N o de*p=&a;p 指向

40、结果有序单链表的表尾结点，p-n e x t=N U L L;初始指向表头附加结点。w h i l e (p l!=N U L L)&(p 2!=N U L L)处理两个表非空时的情况。L N o de*n e w p t r=n e w L N o de;i f(p l-dat a dat a)由p l-dat a建立新结点，然后p l 指针后移。n e w p t r-dat a=p 1-dat a;p l=p l-n e x t;)e l s e由p 2-dat a建立新结点，然后p 2 指针后移。n e w p t r-dat a=p 2-dat a;p 2=p 2-n e x t;)

41、将n e w p t r 结点插入到结果有序表的表尾。p-n e x t=n e w p t r;p 二 n e w p t r;w h i l e(p l!=N U L L)继续处理p l 单链表中剩余的结点。L N o de*n e w p t r 二 n e w L N o de;n e w p t r-dat a=p l-dat a;p l=p l-n e x t;p-n e x t=n e w p t r;p=n e w p t r;)w h i l e(p 2!=N U L L)继续处理p 2 单链表中剩余的结点。L N o de*n e w p t r=n e w L N o d

42、e;n e w p t r-dat a=p 2-dat a;p 2=p 2-n e x t;p-n e x t=n e w p t r;p=n e w p t r;)p-n e x t=N U L L;r e t u r n a.n e x t;9.v o i d S e p ar at e(L N o de*H L,L N o de*&p l,L N o de*&p 2)根据一个单链表H L 按条件拆分生成为两个单链表p l 和 p 2(L N o 加 a,b;/a和 b 结点分别作为p l 和 p 2 单链表的表头附加结点。L N o de *t l=&a,*t 2=&b;/t l 和 t

43、 2 分别作为指向p l 和 p 2 单链表的表尾结点，初始指向表头附加结点。L N o de*p=H L;w h i l e(p!=N U L L)(每循环一次产生一个新结点，并把它加入到p l 或 p 2 单链表的末尾。L N o de*n e w p t r=n e w L N o de;i f(p-dat a%2=l)n e w p t r-dat a=p-dat a;t l-n e x t=n e w p t r;t l=n e w p t r;)e l s e n e w p t r-dat a=p-dat a;t 2-n e x t=n e w p t r;t 2=n e w p

44、 t r;)p=p-n e x t;t l-n e x t=t 2-n e x t=N U L L;p l=a.n e x t;p 2=b.n e x t;把指向两个单链表的表头结点的/指针分别赋给p l 和 p 2 返回。第 6小题参考算法如下：vo i d Jo s ep h u s (i n t n,i n t m,i n t s)使用带表头附加结点的循环单链表解决约瑟夫问题。生成表头附加结点，此时循环单链表为空。LN o de*HL二 n ew LN o de;HL-n ex t=HL;i n t i;生成含有n个结点的、结点值依次为1,2,.,n的带表头附加结点的循环单链表。fo r

45、(i=n;i=l;i 一)生成新结点。LN o de*n ew p t r=n ew LN o de;n ew p t r-da t a=i;把新结点插入到表头。n ew p t r-n ex t=HL-n ex t;HL-n ex t=n ew p t r;)从表头开始顺序查找出第S 个结点，对应第一个开始报数的人。LN o de*a p=HL,*c p=HL-n ex t;fo r(i=l;i n ex t;若 c p 指向了表头附加结点，则仍需后移a p 和 c p 指针，/使之指向表头结点。i f(c p=HL)a p=HL;c p=HL-n ex t;依次使n-1 个人出列。fo r

46、(i=l;i n;i+)顺序查找出待出列的人，即为循环结束后c p 所指向的结点。fo r(i n t j=l;j n ex t;i f(c p=HL)a p=HL;c p=HL-n ex t;)输出c p 结点的值，即出列的人。c o u t da t a z，；从单链表中删除c p 结点。a p-n ex t=c p-n ex t;del et e c p;/使 c p 指针指向被删除结点的后继结点。c p=a p-n ex t;若c p 指向了表头附加结点,则后移a p 和 c p 指针。i f(c p=HL)a p=HL;c p=HL-n ex t;)使最后一个人出列。c o u t

47、n ex t-da t a en dl;删除表头结点和表头附加结点。del et e HL-n ex t;del et e HL;)第 9 小题参考算法如下：vo i d O r der Li s t(S LN o de*S L)假定S LN o de类型为按题目要求所定义的结点类型，S L为指向表头附加结点的指针。(S L-r a n ge=N U LL;fo r(S LN o de*p=S L-n ex t;p!=N U LL;p=p-n ex t)(每循环一次把P 所指向的结点按序插入到以r a n ge域链接的有序表中S LN o de*a p,*c p;为P 结点寻找合适的插入位置。

48、a p=S L;c p=a p-r a n ge;w h i l e(c p!=N U LL)i f(p-da t a da t a)b r ea k;el s e a p=c p;c p=c p-r a n ge;)插入位置在a p 和 c p 之间，把 p结点插入其中。p-r a n ge=c p;a p-r a n ge=p;)第 1 0 小题参考程序如F：/l x 2-7.c p p#i n c l u de#i n c l u det y p edef i n t E l em T y p e;规定元素类型为整型。s t r u c t S LN o de 定义单链表结点。(E l

49、em T y p e da t a;S LN o de*n ex t;S LN o de*r a n ge;)；vo i d O r der Li s t(S LN o de*S L)(S L-r a n ge=N U LL;fo r(S LN o de*p=S L-n ex t;p!=N U LL;p=p-n ex t)S LN o de*a p,*c p;为P 结点寻找合适的插入位置。a p=S L;c p=a p-r a n ge;w h i l e(c p!=N U LL)i f(p-da t a da t a)b r ea k;el s e a p=c p;c p=c p-r a n

50、 ge;)插入位置在a p 和 c p 之间，把 p 结点插入其中。p-r a n ge=c p;a p-r a n ge=p;)vo i d m a i n()(按 n ex t 域链接生成具有1 0 个整数元素结点的链表。S LN o de*a=n ew S LN o de;a-n ex t=N U LL;i n t i;S LN o de*p;fo r(i=0;i da t a=r a n d()%3 0;假定产生3 0 以内的随机整数。p-n ex t=a-n ex t;a-n ex t=p;)按 n ex t 域链接的次序输出单链表。fo r(p:=a-n ex t;p!=N U L