数据结构期末复习提要
中央电大理工部计算机教研室
数据结构是中央电大计算机应用专业一门统设必修课和专业基础课,它主要研究数据的各种逻辑结构,在计算机中的存储结构,对数据进行的插入,查找,删除,排序,遍历等运算,这些运算在存储结构上具体实现的算法.学习好该课程将为学好整个计算机专业打下坚实的基础.
第一部分 各章复习要求
下面按照主教材中各章次序给出每章的具体复习要求,以便指导同学们更好地进行期末复习.
第一章 绪论
重点掌握的内容:
1. 数据结构的二元组表示,对应的图形表示,序偶和边之间的对应关系.
2. 集合结构,线性结构,树结构和图结构的特点.
3. 抽象数据类型的定义和表示方法.
4. 一维和二维数组中元素的按下标和按地址的访问方式以及相互转换,元素地址和数组地址的计算,元素占用存储空间大小和数组占用存储空间大小的计算.
5. 普通函数重载和操作符函数重载的含义,定义格式和调用格式.
6. 函数定义中值参数和引用参数的说明格式及作用,函数被调用执行时对传送来的实际参数的影响.
7. 算法的时间复杂度和空间复杂度的概念,计算方法,数量级表示.
8. 一个简单算法的最好,最差和平均这三种情况的时间复杂度的计算.
对于本章的其余内容均作一般掌握.
第二章 线性表
重点掌握的内容:
1. 线性表的定义和抽象数据类型的描述,线性表中每一种操作的功能,对应的函数名,返回值类型和参数表中每个参数的作用.
2. 线性表的顺序存储结构的类型定义,即List类型的定义和每个域的定义及作用.
3. 线性表的每一种运算在顺序存储结构上实现的算法,及相应的时间复杂度.
4. 链接存储的概念,线性表的单链接和双链接存储的结构,向单链表中一个结点之后插入新结点或从单链表中删除一个结点的后继结点的指针链接过程.
5. 单链表中结点的结构,每个域的定义及作用,即LNode类型的定义及结构.
6. 带表头附加结点的链表,循环链表,双向链表的结构特点.
7. 线性表的每一种运算在单链表上实现的算法及相应的时间复杂度.
8. 在顺序存储或链接存储的线性表上实现指定功能的算法的分析和设计.
对于本章的其余内容均作一般掌握.
第三章 稀疏矩阵和广义表
重点掌握的内容:
1. 稀疏矩阵的定义和三元组线性表表示.
2. 稀疏矩阵的顺序存储,带行指针向量的链接存储,十字链接存储的类型定义,在每一种存储中非零元素结点的结构.
3. 广义表的定义和表示,广义表长度和深度的计算.
4. 广义表的链接存储结构中结点类型的定义,分别求广义表长度和深度的递归算法,它们对应的时间复杂度.
一般掌握的内容:
1. 稀疏矩阵的转置运算和算法描述.
2. 两个稀疏矩阵的做加法的过程和算法描述.
对于本章的其余内容均作一般了解.
第四章 栈和队列
重点掌握的内容:
1. 栈的定义和抽象数据类型的描述,栈中每一种操作的功能,对应的函数名,返回值类型和参数表中每个参数的作用.
2. 栈的顺序存储结构的类型定义,即Stack类型的定义和每个域的定义及作用.
3.栈的每一种运算在顺序存储结构上实现的算法,及相应的时间复杂度.
4. 栈的每一种运算在链接存储结构上实现的算法及相应的时间复杂度.
5. 算术表达式的中缀表示和后缀表示,以及相互转换的规则,后缀表达式求值的方法.
6. 队列的定义和抽象数据类型的描述,队列中每一种操作的功能,对应的函数名,返回值类型和参数表中每个参数的作用.
7. 队列的顺序存储结构的类型定义,即Queue类型的定义和每个域的定义及作用.
8. 队列的每一种运算在顺序存储结构上实现的算法及相应的时间复杂度.
9. 利用栈和队列解决简单问题的算法分析和设计.
一般掌握的内容:
1. 后缀表达式求值的算法,把中缀表达式转换为后缀表达式的算法.
2. 求解阶乘问题和迷宫问题的方法和算法.
3. 队列的链接存储结构,以及实现每一种队列运算的算法和相应的时间复杂度.
第五章 树和二叉树
重点掌握的内容:
1. 树和二叉树的定义,对于一棵具体树和二叉树的二元组表示及广义表表示.
2. 树和二叉树的概念,如结点的度,树的度,树的层数,树的深度等.
3. 树和二叉树的性质,如已知树或二叉树的深度h可求出相应的最多结点数,已知结点数n可求出对应树或二叉树的最大和最小高度.
4. 二叉树中结点的编号规则和对应的顺序存储结构.
5. 二叉树的链接存储结构及存储结点的类型定义,即BTreeNode类型的定义和每个域的定义及作用.
6. 二叉树的先序,中序,后序遍历的递归过程和递归算法,中序遍历的非递归算法,按层遍历的过程和算法,每种算法的时间复杂度.
7. 普通树的链接存储结构,GTreeNode类型的定义和每个域的定义及作用.
8.普通树的先根,后根和按层遍历的过程及算法.
9. 在链接存储的二叉树上实现指定功能的算法分析和设计.
对于本章的其余内容均作一般掌握.
第六章 二叉树的应用
重点掌握的内容:
1. 二叉搜索树的定义和性质.
2. 二叉搜索树查找的递归算法和非递归算法,相应的时间复杂度,查找一个元素的查找长度,即从树根结点到该结点的路径上的结点数.
3. 二叉搜索树插入的递归算法和非递归算法,相应的时间复杂度,根据一组数据生成一棵二叉搜索树的过程.
4. 堆的定义和顺序存储结构,小根堆和大根堆的异同.
5. 向堆中插入元素的过程,算法描述及时间复杂度.
6. 从堆中删除元素的过程,算法描述及时间复杂度.
7. 哈夫曼树的定义,树的带权路径长度的计算,根据若干个叶子结点的权构造哈夫曼树的过程.
对本章的其余内容均作一般了解.
第七章 图
重点掌握的内容:
1. 图的顶点集和边集的表示.
2. 图的一些概念的含义,如顶点,边,度,完全图,子图,路径,路径长度,连通图,权,网等.
3. 图的邻接矩阵,邻接表和边集数组三种存储结构及相应的空间复杂度.
4. 存储图使用的vexlist, adjmatrix, adjlist, edgenode, edgeset, edge等类型的定义及用途.
5. 图的深度优先和广度优先搜索遍历的过程.
6. 对分别用邻接矩阵和用邻接表表示的图进行深度优先搜索遍历的过程,算法描述以及相应的时间复杂度.
7. 对分别用邻接矩阵和用邻接表表示的图进行广度优先搜索遍历的过程,算法描述以及相应的时间复杂度.
8. 图的生成树,生成树的权,最小生成树等的定义.
9. 根据普里姆算法求图的最小生成树的过程和算法描述.
10.根据克鲁斯卡尔算法求图的最小生成树的过程和算法描述.
11. 图的拓扑序列和拓扑排序的概念,求图的拓扑序列的方法,对用邻接表表示的图进行拓扑排序的过程和算法.
对本章的其余内容均作一般掌握.它包括建立图的邻接矩阵,邻接表,边集数组算法,建立图的逆邻接表和十字邻接表等内容.
第八章 查找
重点掌握的内容:
1. 在一维数组上进行顺序查找的过程,算法,平均查找长度和时间复杂度.
2. 在一维数组上进行二分查找的过程,递归和非递归算法,平均查找长度和时间复杂度,二分查找一个给定值元素的查找长度(即查找路径上的元素数),二分查找对应的判定树的性质.
3. 索引存储的概念,索引表的存储结构和索引项的存储结构,索引查找一个元素的过程,平均查找长度和时间复杂度.
4. 散列存储的概念,散列函数,散列表,冲突,同义词,装填因子等术语的含义.
5. 利用除留余数法建立散列函数求元素散列地址的方法.
6. 利用开放定址法中的线性探查法处理冲突进行散列存储和查找的过程,利用链接法处理冲突进行散列存储和查找的过程.
7. 根据除留余数法构造散列函数,采用线性探查法或链接法处理冲突,把一组数据散列存储到散列表中,计算出一个给定值元素的查找长度和查找所有元素的平均查找长度.
8. B_树中每个结点的结构,树根结点或非树根结点中关键字的个数范围和子树的个数范围,B_的结构特性,从B_树上查找一个给定值元素的过程.
一般掌握的内容:
1. 索引查找和分块查找算法.
2. B_树查找算法.
3. 向B_树中插入元素的过程.
对本章的其余内容均作一般了解.
第九章 排序
重点掌握的内容:
1. 直接插入,直接选择和冒泡排序的方法,排序过程及时间复杂度.
2. 在堆排序中建立初始堆的过程和利用堆排序的过程,对一个分支结点进行筛运算的过程,算法及时间复杂度,整个堆排序的算法描述及时间复杂度.
3. 快速排序的方法,对一组数据的排序过程,对应的二叉搜索树,快速排序过程中划分的层数和递归排序区间的个数.
4. 快速排序的递归算法,它在平均情况下的时间和空间复杂度,在最坏情况下的时间和空间复杂度.
5. 二路归并排序的方法和对数据的排序过程,每趟排序前,后的有序表长度,二路归并排序的趟数,时间复杂度和空间复杂度.
一般掌握的内容:
1. 每一种排序方法的稳定性.
2. 直接插入排序和直接选择排序的算法.
一般了解的内容:
1. 二路归并排序过程中涉及的每个算法.
2. 冒泡排序算法.
第二部分 期末复习题示例
一,单选题(每小题2分,共8分)
1. 在一个单链表HL中,若要向表头插入一个由指针p指向的结点,则执行________.
A HL=p; p->next=HL; B p->next=HL; HL=p;
C p->next=HL; p=HL; D p->next=HL->next; HL->next=p;
2. 在一个顺序队列中,队首指针指向队首元素的________位置.
A 前一个 B 后一个 C 当前
3. 从二叉搜索树中查找一个元素时,其时间复杂度大致为________.
A O(n) B O(1) C O(log2n) D O(n2)
4. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为________.
A 24 B 48 C 72 D 53
二,填空题(每空1分,共32分)
1. 一个算法的时间复杂度为(3n2+2nlog2n+4n-7)/(5n),其数量级表示为________.
2. 在以HL为表头指针的带表头附加结点的单链表和循环单链表中,链表为空的条件分别为________和________.
3.一个广义表中的元素分为________元素和________元素两类.
4.从一个链栈中删除一个结点时,需要把栈顶结点的_________域的值赋给________.
5.在进行函数调用时,需要把每个实参的值和调用后的________传送给被调用的函数中.
6.对于一棵具有n个结点的二叉树,若一个结点的编号为i(1≤i≤n),则它的左孩子结点的编号为________,右孩子结点的编号为________,双亲结点的编号为________.
7.在一棵高度为5的理想平衡树中,最少含有________个结点,最多含有________个结点.
8.在一个堆的顺序存储中,若一个元素的下标为i(0≤i≤n-1),则它的左孩子元素的下标为______,右孩子元素的下标为________.
9.在一个具有n个顶点的无向完全图中,包含有________条边,在一个具有n个顶点的有向完全图中,包含有________条边.
10.对于一个具有n个顶点和e条边的有向图和无向图,若采用边集数组表示,则存于数组中的边数分别为________和________条.
11.以二分查找方法从长度为12的有序表中查找一个元素时,平均查找长度为________.
12.假定一个线性表为(12,23,74,55,63,40,82,36),若按Key % 3条件进行划分,使得同一余数的元素成为一个子表,则得到的三个子表分别为_____________,_____________和_____________.
13.在线性表的散列存储中,装填因子又称为装填系数,若用m表示散列表的长度,n表示待散列存储的元素的个数,则等于________.
14.在一棵m阶B_树上,每个非树根结点的关键字数目最少为________个,最多为________个,其子树数目最少为________,最多为________.
15.在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为________,整个堆排序过程的时间复杂度为________.
16. 快速排序在平均情况下的时间复杂度为________,在最坏情况下的时间复杂度为________.
三,运算题(每小题6分,共24分)
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)25,(2,4)13,(3,5)9,(3,6)10,
(4,6)4,(5,7)20};
按照普里姆算法从顶点0出发得到最小生成树,试写出在最小生成树中依次得到的各条边.
________, ________, ________, ________, ________, ________, ________.
3. 已知一个图的顶点集V和边集G分别为:
V={0,1,2,3,4,5,6,7,8};
E={,,,,,,,,,
,,};
若存储它采用邻接表,并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的,则按主教材中介绍的进行拓扑排序的算法,写出得到的拓扑序列(提示:先画出对应的图形,然后再运算).
拓扑序列:
4. 假定一组记录的排序码为(46,79,56,38,40,80,25,34),则对其进行快速排序的第一次划分的结果为________________.
四,阅读算法,回答问题(每小题8分,共16分)
1. void AE(Stack& S)
{
InitStack(S);
Push(S,30);
Push(S,40);
Push(S,50);
int x=Pop(S)+2*Pop(S);
Push(S,x);
int i,a[4]={5,8,12,15};
for(i=0;i<4;i++) Push(S,a[i]);
while(!StackEmpty(S)) cout< }
该算法被调用后得到的输出结果为:
2. void AJ(adjlist GL, int i, int n)
{
Queue Q;
InitQueue(Q);
cout< cout< }
}
}
该算法的功能为:
______________________________________________________________.
五,算法填空,在画有横线的地方填写合适的内容(10分).
向以BST为树根指针的二叉搜索树上插入值为item的结点的递归算法.
void Insert(BTreeNode*& BST, const ElemType& item)
{
if(BST==NULL)
{ BTreeNode* p=new BTreeNode;
p->data=item;
_______________________;
BST=p;
}
else if(itemdata) ___________________;
else ________________________;
}
六,编写算法(10分)
编写向类型为List的线性表L中第i个元素位置插入一个元素的算法,假定不需要对i的值进行有效性检查,同时不需要检查存储空间是否用完.
void Insert(List& L, int i, ElemType x)
第三部分 期末复习题示例解答及评分标准
一,单选题(每小题2分,共8分)
评分标准:选对者得2分,否则不得分.
1. B 2. A 3. C 4. D
二,填空题(每空1分,共32分)
评分标准:每空得2分,否则不得分.
1. O(n)
2. HL->next==NULL HL->next==HL
3. 单 表
4. 指针 栈顶指针
5. 返回地址
6. 2i 2i+1 i/2(或i/2)
7. 16 31
8. 2i+1 2i+2
9. n(n-1)/2 n(n-1)
10. e e
11. 37/12
12. (12,63,36) (55,40,82) (23,74)
13. n/m
14. m/2-1 m-1 m/2 m
15. O(log2n) O(nlog2n)
16. O(nlog2n) O(n2)
三,运算题(每小题6分,共24分)
1. 先序: a,b,c,d,e,f 2分
中序: c,b,a,e,d,f 2分
后序: c,b,e,f,d,a 1分
按层: a,b,d,c,e,f 1分
2. (0,3)2, (0,2)5, (0,1)8, (1,5)6, (3,6)10, (6,4)4, (5,7)20
3. 拓扑序列:1,3,6,0,2,5,4,7,8
4. [40 34 25 38] 46 [80 56 79]
评分标准:每小题若有任何错误则应得分全扣.
四,阅读算法,回答问题(每小题8分,共16分)
1. 15 12 8 5 130 30
评分标准:有一处错扣4分,两处及以上错8分全扣.
2. 从初始点vi出发广度优先搜索由邻接表GL所表示的图.
评分标准:请根据叙述情况酌情给分.
五,算法填空,在画有横线的地方填写合适的内容(10分).
p->left=p->right=NULL
Insert(BST->left, item)
Insert(BST->right, item)
评分标准:每空对给3分,全对给10分.
六,编写算法(10分)
评分标准:请根据编程情况酌情给分.
void Insert(List& L, int i, ElemType x)
{
for(int j=L.size-1; j>=i-1; j--)
L.list[j+1]=L.list[j];
L.list[i-1]=x;
L.size++;
}
第四部分 教材第二章部分习题参考解答
一,单选题
1. B 2. A 3. C 4. B 5. D 6. C
二,填空题
1.值 指针
2.(38,56,25,60,42,74)
3. O(n) O(1)
4. O(1) O(n)
5. i-1 i+1
6. p->next a[p].next
7. 表头
8.前驱 后继
9.表尾 表头
10.HL->next==NULL HL->next==HL
11. a[i].next=a[1].next; a[1].next=i;
12. i=a[1].next; a[1].next=a[i].next;
13. p=a[i].next; a[i].next=a[p].next; i=p;
14. a[j].next=a[i].next; a[i].next=j;
三,普通题
第1小题
1. (79, 62, 34, 57, 26, 48)
2. (26, 34, 48, 57, 62, 79)
3. (48, 56, 57, 62, 79, 34)
4. (56, 57, 79, 34)
5. (26, 34, 39, 48, 57, 62)
第2小题
分析:为了排版方便,假定采用以下输出格式表示单链表示意图:每个括号内的数据表示一个元素结点,其中第一个数据为元素值,第二个数据为后继结点的指针,第一个元素结点前的数值为表头指针.
1. (7(79,6), (62,5), (34,4), (57,3), (26,2), (48,0))
2. (3(26,5), (34,2), (48,4), (57,6), (62,7), (79,0))
3. (2(48,8), (56,4), (57,6), (62,7), (79,5), (34,0))
4. (8(56,4), (57,7), (79,5), (34,0))
第3小题
1. ElemType DMValue(List& L)
//从线性表中删除具有最小值的元素并由函数返回,空出的位置
//由最后一个元素填补,若线性表为空则显示出错信息并退出运行.
{
if(ListEmpty(L)) {
cerr<<"List is Empty!"< exit(1);
}
ElemType x;
x=L.list[0];
int k=0;
for(int i=1; i ElemType y=L.list[i];
if (y }
L.list[k]=L.list[L.size-1];
L.size--;
return x;
}
2. int Delete1(List& L, int i)
//从线性表中删除第i个元素并由函数返回.
{
if(iL.size) {
cerr<<"Index is out range!"< exit(1);
}
ElemType x;
x=L.list[i-1];
for(int j=i-1; j L.list[j]=L.list[j+1];
L.size--;
return x;
3. void Insert1(List& L, int i, ElemType x)
//向线性表中第i个元素位置插入一个元素.
{
if(iL.size+1) {
cerr<<"Index is out range!"< exit(1);
}
if(L.size==MaxSize)
{
cerr<<"List overflow!"<=i-1; j--)
L.list[j+1]=L.list[j];
L.list[i-1]=x;
L.size++;
}
4. void Delete2(List& L, ElemType x)
//从线性表中删除具有给定值x的所有元素.
{
int i=0;
while(i if(L.list[i]==x) {
for(int j=i+1; j L.list[j-1]=L.list[j];
L.size--;
}
else
i++;
}
5. void Delete3(List& L, ElemType s, ElemType t)
//从线性表中删除其值在给定值s和t之间的所有元素.
{
int i=0;
while(i=s) && (L.list[i]<=t)) {
for(int j=i+1; j L.list[j-1]=L.list[j];
L.size--;
}
else
i++;
}
6. void Delete4(List& L, ElemType s, ElemType t)
//从有序表中删除其值在给定值s和t之间的所有元素.
{
int i=0;
while(i if(L.list[i] else break;
if(i int j=1;
while((i+j j++; //求出s和t之间元素的个数.
for(int k=i+j; kMaxSize) {
cerr<<"List overflow!"< exit(1);
}
int i=0, j=0, k=0;
while((i if(L1.list[i]<=L2.list[j])
{ //将L1中的元素赋给L.
L.list[k]=L1.list[i];
i++;
}
else { //将L2中的元素赋给L.
L.list[k]=L2.list[j];
j++;
}
k++;
}
while(i L.list[k]=L1.list[i];
i++; k++;
}
while(j L.list[k]=L2.list[j];
j++; k++;
}
L.size=k;
}
8. void Delete5(List& L)
//从线性表中删除所有其值重复的元素,使所有元素的值均不同.
{
int i=0;
while(i int j=i+1;
while(j { //删除重复值为L.list[i]的所有元素
if(L.list[j]==L.list[i]) {
for(int k=j+1; knext; //p指向下一个待逆序的结点.
//将q结点插入到已逆序单链表的表头.
q->next=HL;
HL=q;
}
}
2. void Delete1(LNode*& HL, int i)
//删除单链表中的第i个结点.
{
if(i<1 || HL==NULL) {
cerr<<"Index is out range!" j++;
}
if(cp==NULL) {
cerr<<"Index is out range!" else
ap->next=cp->next;
delete cp;
}
3. ElemType MaxValue(LNode* HL)
//从单链表中查找出所有元素的最大值,该值由函数返回.
{
if(HL==NULL) {
cerr<<"Linked list is empty!" LNode* p=HL->next;
while(p!=NULL) {
if (maxdata) max=p->data;
p=p->next;
}
return max;
}
4. int Count(LNode* HL, ElemType x)
//统计出单链表中结点的值等于给定值x的结点数.
{
int n=0;
while(HL!=NULL) {
if(HL->data==x) n++;
HL=HL->next;
}
return n;
}
5. void Create(LNode*& HL, ElemType a[], int n)
//根据一维数组a[n]建立一个单链表
{
InitList(HL);
for(int i=n-1; i>=0; i--)
InsertFront(HL,a[i]);
}
6. void OrderList(LNode*& HL)
//将一个单链表重新链接成有序单链表.
{
LNode* p=HL; //p指向待处理的第一个结点,初始指向原表头结点.
HL=NULL; //HL仍为待建立的有序表的表头指针,初始值为空.
while(p!=NULL)
{ //把原单链表中的结点依次进行有序链接.
LNode* q=p; //q指向待处理的结点.
p=p->next; //p指向下一个待处理的结点.
LNode *ap=NULL, *cp=HL;
//cp指向有序表中待比较的结点,ap指向其前驱结点.
while(cp!=NULL)
{ //为插入q结点寻找插入位置.
if(q->datadata)
break;
else {
ap=cp;
cp=cp->next;
}
}
//将q结点插入到ap和cp结点之间.
q->next=cp;
if(ap==NULL)
HL=q;
else
ap->next=q;
}
}
7. LNode* Merge1(LNode*& p1, LNode*& p2)
// 将两个有序单链表合并成一个有序单链表.
{
LNode a; //a结点作为结果有序单链表的表头附加结点,这样
//便于处理, 处理结束后返回a结点的指针域的值.
LNode* p=&a; //p指向结果有序单链表的表尾结点,
p->next=NULL; //初始指向表头附加结点.
while((p1!=NULL)&&(p2!=NULL))
{ //处理两个表非空时的情况.
if(p1->datadata) {
p->next=p1; p1=p1->next;
}
else {
p->next=p2; p2=p2->next;
}
p=p->next;
}
if(p1!=NULL) p->next=p1;
if(p2!=NULL) p->next=p2;
p1=p2=NULL;
return a.next;
}
8. LNode* Merge2(LNode* p1, LNode* p2)
//根据两个有序单链表生成一个新的有序单链表.
{
LNode a; //用a作为新的有序单链表的表头附加结点.
LNode* p=&a; //p指向结果有序单链表的表尾结点,
p->next=NULL; //初始指向表头附加结点.
while((p1!=NULL)&&(p2!=NULL))
{ //处理两个表非空时的情况.
LNode* newptr=new LNode;
if(p1->datadata)
{ //由p1->data建立新结点,然后p1指针后移.
newptr->data=p1->data;
p1=p1->next;
}
else
{ //由p2->data建立新结点,然后p2指针后移.
newptr->data=p2->data;
p2=p2->next;
}
//将newptr结点插入到结果有序表的表尾.
p->next=newptr;
p=newptr;
}
while(p1!=NULL)
{ //继续处理p1单链表中剩余的结点.
LNode* newptr=new LNode;
newptr->data=p1->data;
p1=p1->next;
p->next=newptr;
p=newptr;
}
while(p2!=NULL)
{ //继续处理p2单链表中剩余的结点.
LNode* newptr=new LNode;
newptr->data=p2->data;
p2=p2->next;
p->next=newptr;
p=newptr;
}
p->next=NULL;
return a.next;
}
9. void Separate(LNode* HL, LNode*& p1, LNode*& p2)
//根据一个单链表HL按条件拆分生成为两个单链表p1和p2.
{
LNode a,b; //a和b结点分别作为p1和p2单链表的表头附加结点.
LNode *t1=&a, *t2=&b; //t1和t2分别作为指向p1和p2单链表
//的表尾结点,初始指向表头附加结点.
LNode* p=HL;
while(p!=NULL)
{ //每循环一次产生一个新结点,并把它加入到
//p1或p2单链表的末尾.
LNode* newptr=new LNode;
if(p->data%2==1) {
newptr->data=p->data;
t1->next=newptr;
t1=newptr;
}
else {
newptr->data=p->data;
t2->next=newptr;
t2=newptr;
}
p=p->next;
}
t1->next=t2->next=NULL;
p1=a.next; p2=b.next; //把指向两个单链表的表头结点的
//指针分别赋给p1和p2返回.
}
第6小题
参考算法如下:
void Josephus(int n, int m, int s)
//使用带表头附加结点的循环单链表解决约瑟夫问题.
{
//生成表头附加结点,此时循环单链表为空.
LNode* HL=new LNode;
HL->next=HL;
int i;
//生成含有n个结点的,结点值依次为1,2,...,n的带表头附加结点
//的循环单链表.
for(i=n; i>=1; i--) {
//生成新结点.
LNode* newptr=new LNode;
newptr->data=i;
//把新结点插入到表头.
newptr->next=HL->next;
HL->next=newptr;
}
//从表头开始顺序查找出第s个结点,对应第一个开始报数的人.
LNode *ap=HL, *cp=HL->next;
for(i=1; inext;
//若cp指向了表头附加结点,则仍需后移ap和cp指针,
//使之指向表头结点.
if(cp==HL) {ap=HL; cp=HL->next; }
}
//依次使n-1个人出列.
for(i=1; i //顺序查找出待出列的人,即为循环结束后cp所指向的结点.
for(int j=1; jnext;
if(cp==HL) {ap=HL; cp=HL->next; }
}
//输出cp结点的值,即出列的人.
coutnext;
delete cp;
//使cp指针指向被删除结点的后继结点.
cp=ap->next;
//若cp指向了表头附加结点,则后移ap和cp指针.
if(cp==HL) {ap=HL; cp=HL->next; }
}
//使最后一个人出列.
coutdata delete HL;
}
第9小题
参考算法如下:
void OrderList(SLNode* SL)
//假定SLNode类型为按题目要求所定义的结点类型,SL为指向
//表头附加结点的指针.
{
SL->range=NULL;
for(SLNode* p=SL->next; p!=NULL; p=p->next)
{ //每循环一次把p所指向的结点按序插入到以range域
//链接的有序表中
SLNode *ap, *cp;
//为p结点寻找合适的插入位置.
ap=SL; cp=ap->range;
while(cp!=NULL)
if(p->datadata)
break;
else {
ap=cp;
cp=cp->range;
}
//插入位置在ap和cp之间,把p结点插入其中.
p->range=cp;
ap->range=p;
}
}
第10小题
参考程序如下:
//lx2-7.cpp
#include
#include
typedef int ElemType; //规定元素类型为整型.
struct SLNode //定义单链表结点.
{
ElemType data;
SLNode* next;
SLNode* range;
};
void OrderList(SLNode* SL)
{
SL->range=NULL;
for(SLNode* p=SL->next; p!=NULL; p=p->next)
{
SLNode *ap, *cp;
//为p结点寻找合适的插入位置.
ap=SL; cp=ap->range;
while(cp!=NULL)
if(p->datadata)
break;
else {
ap=cp;
cp=cp->range;
}
//插入位置在ap和cp之间,把p结点插入其中.
p->range=cp;
ap->range=p;
}
}
void main()
{
//按next域链接生成具有10个整数元素结点的链表.
SLNode* a=new SLNode;
a->next=NULL;
int i;
SLNode* p;
for(i=0; idata=rand()%30; //假定产生30以内的随机整数.
p->next=a->next;
a->next=p;
}
//按next域链接的次序输出单链表.
for(p=a->next; p!=NULL; p=p->next)
cout coutrange)
cout cout< }