LinkBiTree.h 头文件怎么写【qt吧】_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：33,041贴子：
LinkBiTree.h 头文件怎么写收藏
谢谢吧里各位大爷，爱你们~
登录百度帐号推荐应用拒绝访问 |
| 百度云加速
请打开cookies.
此网站 () 的管理员禁止了您的访问。原因是您的访问包含了非浏览器特征(8e4394-ua98).
重新安装浏览器，或使用别的浏览器数据结构课后习题答案
数据结构习题集答案第 1 章 绪论1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结 构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入 到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位， 在计算机程序中通常作为一个整体 进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。 是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据 类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据 类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提 供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据1类型通常由编程者定义， 包括定义它所使用的数据和在这些数据上所 进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求 只定义到数据的逻辑结构和操作说明， 不考虑数据的存储结构和操作 的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接 口。 1.3 设有数据结构(D,R)，其中D ? ?d1, d 2, d 3, d 4? ， R ? ?r?， r ? ??d1, d 2?, ?d 2, d 3?, ?d 3, d 4??试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有 理数的定义（有理数是其分子、分母均为自然数且分母不为零的分 数） 。 解：ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={&r,i&} 基本操作： InitComplex(&C,re,im) 操作结果：构造一个复数 C，其实部和虚部分别为 re 和 im DestroyCmoplex(&C) 操作结果：销毁复数 C Get(C,k,&e)2操作结果：用 e 返回复数 C 的第 k 元的值 Put(&C,k,e) 操作结果：改变复数 C 的第 k 元的值为 e IsAscending(C) 操作结果：如果复数 C 的两个元素按升序排列，则返 回 1，否则返回 0 IsDescending(C) 操作结果：如果复数 C 的两个元素按降序排列，则返 回 1，否则返回 0 Max(C,&e) 操作结果：用 e 返回复数 C 的两个元素中值较大的一 个 Min(C,&e) 操作结果：用 e 返回复数 C 的两个元素中值较小的一 个 }ADT Complex ADT RationalNumber{ 数据对象：D={s,m|s,m 为自然数，且 m 不为 0} 数据关系：R={&s,m&} 基本操作： InitRationalNumber(&R,s,m) 操作结果：构造一个有理数 R，其分子和分母分别为 s3和m DestroyRationalNumber(&R) 操作结果：销毁有理数 R Get(R,k,&e) 操作结果：用 e 返回有理数 R 的第 k 元的值 Put(&R,k,e) 操作结果：改变有理数 R 的第 k 元的值为 e IsAscending(R) 操作结果：若有理数 R 的两个元素按升序排列，则返 回 1，否则返回 0 IsDescending(R) 操作结果：若有理数 R 的两个元素按降序排列，则返 回 1，否则返回 0 Max(R,&e) 操作结果：用 e 返回有理数 R 的两个元素中值较大的一个 Min(R,&e) 操作结果：用 e 返回有理数 R 的两个元素中值较小的一个 }ADT RationalNumber 1.5 试画出与下列程序段等价的框图。 (1) product=1; i=1; while(i&=n){ product *=4i++; } (2) i=0; do { i++; } while((i!=n) && (a[i]!=x)); (3) switch { case x&y: z=y-x; case x=y: z=abs(x*y); default: z=(x-y)/abs(x)*abs(y); } 1.6 在程序设计中，常用下列三种不同的出错处理方式： (1) 用 exit 语句终止执行并报告错误； (2) 以函数的返回值区别正确返回或错误返回； (3) 设置一个整型变量的函数参数以区别正确返回或某种错误返 回。 试讨论这三种方法各自的优缺点。 解：(1)exit 常用于异常错误处理，它可以强行中断程序的执行， 返回操作系统。 (2)以函数的返回值判断正确与否常用于子程序的测试，便于实 现程序的局部控制。 (3)用整型函数进行错误处理的优点是可以给出错误类型，便于5迅速确定错误。 1.7 在程序设计中，可采用下列三种方法实现输出和输入： (1) 通过 scanf 和 printf 语句； (2) 通过函数的参数显式传递； (3) 通过全局变量隐式传递。 试讨论这三种方法的优缺点。 解：(1)用 scanf 和 printf 直接进行输入输出的好处是形象、直观， 但缺点是需要对其进行格式控制，较为烦琐，如果出现错误，则会引 起整个系统的崩溃。 (2)通过函数的参数传递进行输入输出，便于实现信息的隐蔽， 减少出错的可能。 (3)通过全局变量的隐式传递进行输入输出最为方便，只需修改 变量的值即可，但过多的全局变量使程序的维护较为困难。 1.8 设 n 为正整数。试确定下列各程序段中前置以记号@的语句的频 度： (1) i=1; k=0; while(i&=n-1){ @ k += 10*i; i++; } (2) i=1; k=0; do {6@ k += 10*i; i++; } while(i&=n-1); (3) i=1; k=0; while (i&=n-1) { i++; @ k += 10*i; } (4) k=0; for(i=1; i&=n; i++) { for(j=i; j&=n; j++) @ k++; } (5) for(i=1; i&=n; i++) { for(j=1; j&=i; j++) { for(k=1; k&=j; k++) @ x += } (6) i=1; j=0; while(i+j&=n) { @ if(i&j) j++; else i++;7} (7) x=n; y=0; // n 是不小于 1 的常数while(x&=(y+1)*(y+1)) { @ } (8) x=91; y=100; while(y&0) { @ if(x&100) { x -= 10; y--; } else x++; } 解：(1) n-1 (2) n-1 (3) n-1 (4) n+(n-1)+(n-2)+...+1=n( n ? 1) 2ny++;(5) 1+(1+2)+(1+2+3)+...+(1+2+3+...+n)= ?i ?1i(i ? 1) 2= = (6) n (7)1 n 1 n 2 1 n 2 1 n i ( i ? 1 ) ? ( i ? i ) ? i ? ? ?i ? 2 ? 2 i ?1 2 i ?1 2 i ?1 i ?11 1 1 n(n ? 1)( 2n ? 1) ? n(n ? 1) ? n(n ? 1)( 2n ? 3) 12 4 12? n?向下取整(8)
假设 n 为 2 的乘幂，并且 n&2，试求下列算法的时间复杂度及变8量 count 的值（以 n 的函数形式表示） 。 int Time(int n) { count = 0; x=2; while(x&n/2) { x *= 2; count++; } } 解： o(log2 n) count= log2 n ? 2 1.11 已知有实现同一功能的两个算法，其时间复杂度分别为 O?2 n ? 和 ，又每 O n10 ，假设现实计算机可连续运算的时间为 107 秒（100 多天） 秒可执行基本操作（根据这些操作来估算算法时间复杂度） 105 次。 试问在此条件下，这两个算法可解问题的规模（即 n 值的范围）各为 多少？哪个算法更适宜？请说明理由。 解： 2 n ? 1012n10 ? 1012? ?n=40 n=16则对于同样的循环次数 n，在这个规模下，第二种算法所花费的 代价要大得多。故在这个规模下，第一种算法更适宜。 1.12 设有以下三个函数：f ?n? ? 21n 4 ? n 2 ? 1000， g ?n? ? 15n 4 ? 500n 3 ， h?n? ? 500n 3.5 ? n log n请判断以下断言正确与否：9(1) f(n)是 O(g(n)) (2) h(n)是 O(f(n)) (3) g(n)是 O(h(n)) (4) h(n)是 O(n3.5) (5) h(n)是 O(nlogn) 解：(1)对 (2)错 (3)错 (4)对 (5)错 1.13 试设定若干 n 值，比较两函数 n 2 和 50n log2 n 的增长趋势，并确定 n 在什么范围内，函数 n 2 的值大于 50n log2 n 的值。 解： n 2 的增长趋势快。但在 n 较小的时候， 50n log2 n 的值较大。 当 n&438 时， n 2 ? 50n log2 n 1.14 判断下列各对函数 f ?n ? 和 g ?n? ， 当 n ? ? 时， 哪个函数增长更快？ (1) f ?n? ? 10n 2 ? ln n!?10n ， g ?n? ? 2n 4 ? n ? 73??(2) f ?n? ? ?ln?n!? ? 5?2 ， g ?n? ? 13n 2.5 (3) f ?n? ? n 2.1 ? n 4 ? 1 ， g ?n? ? ?ln?n!??2 ? n (4) f ?n? ? 2 ?n ? ? ?2 n ? ， g ?n? ? n ?n ? ? n5322解：(1)g(n)快 (2)g(n)快 (3)f(n)快 (4) f(n)快 1.15 试用数学归纳法证明： (1) (2) (3)?ii ?1 n i ?0 nn2? n?n ? 1??2n ? 1? / 6 ? 1 / ?x ? 1??n ? 0? ?x ? 1, n ? 0?? x ? ?xin ?1??2i ?1i ?1? 2n ? 1?n ? 1?10(4)? ?2i ? 1? ? ni ?1n2?n ? 1?1.16 试写一算法， 自大至小依次输出顺序读入的三个整数 X，Y 和 Z 的值 解： int max3(int x,int y,int z) { if(x&y) if(x&z) else if(y&z) } 1.17 已知 k 阶斐波那契序列的定义为f 0 ? 0 ， f1 ? 0 ，…， f k ?2 ? 0 ， f k ?1 ? 1 ； f n ? f n?1 ? f n?2 ? ? ? f n?k ， n ? k , k ? 1,?试编写求 k 阶斐波那契序列的第 m 项值的函数算法，k 和 m 均 以值调用的形式在函数参数表中出现。 解：k&0 为阶数，n 为数列的第 n 项 int Fibonacci(int k,int n) { if(k&1) exit(OVERFLOW);11int *p,x; p=new int[k+1]; if(!p) exit(OVERFLOW); int i,j; for(i=0;i&k+1;i++){ if(i&k-1) p[i]=0; else p[i]=1; } for(i=k+1;i&n+1;i++){ x=p[0]; for(j=0;j&k;j++) p[j]=p[j+1]; p[k]=2*p[k-1]-x; } return p[k]; } 1.18 假设有 A，B，C，D，E 五个高等院校进行田径对抗赛，各院校 的单项成绩均已存入计算机，并构成一张表，表中每一行的形式为 项目名 称 性别 校名 成绩 得分编写算法，处理上述表格，以统计各院校的男、女总分和团体总分， 并输出。 解： typedef enum{A,B,C,D,E} SchoolN12typedef enum{Female,Male} SexT typedef struct{ char event[3]; //项目 SexT SchoolN } C typedef struct{ int MaleS int FemaleS //男团总分 //女团总分int TotalS //团体总分 } S Sum SumScore(SchoolName sn,Component a[],int n) { S temp.MaleSum=0; temp.FemaleSum=0; temp.TotalSum=0; for(i=0;i&n;i++){ if(a[i].school==sn){ if(a[i].sex==Male) temp.MaleSum+=a[i].13if(a[i].sex==Female) temp.FemaleSum+=a[i]. } } temp.TotalSum=temp.MaleSum+temp.FemaleS } 1.19 试编写算法，计算 i!*2 i 的值并存入数组 a[0..arrsize-1]的第 i-1 个 分量中(i=1,2,…,n)。假设计算机中允许的整数最大值为 maxint，则当 n&arrsize 或对某个 k ?1 ? k ? n? ，使 k!?2 k ? max int 时，应按出错处理。注 意选择你认为较好的出错处理方法。 解： #include&iostream.h& #include&stdlib.h& #define MAXINT 65535 #define ArrSize 100 int fun(int i);int main() { int i,k; int a[ArrSize]; cout&&&Enter k:&;14cin&&k; if(k&ArrSize-1) exit(0); for(i=0;i&=k;i++){ if(i==0) a[i]=1; else{ if(2*i*a[i-1]&MAXINT) exit(0); else a[i]=2*i*a[i-1]; } } for(i=0;i&=k;i++){ if(a[i]&MAXINT) exit(0); else cout&&a[i]&&& &; } return 0; } 1.20 试编写算法求一元多项式的值 Pn ?x ? ? ? ai x i 的值 Pn ?x0 ? ， 并确定算i ?0 n法中每一语句的执行次数和整个算法的时间复杂度。 注意选择你认为 较好的输入和输出方法。本题的输入为 ai ?i ? 0,1,?, n? ，x0 和 n ，输出为Pn ?x0 ? 。解： #include&iostream.h& #include&stdlib.h&15#define N 10 double polynomail(int a[],int i,double x,int n); int main() { int n,i; int a[N]; cout&&&输入变量的值 x:&; cin&&x; cout&&&输入多项式的阶次 n:&; cin&&n; if(n&N-1) exit(0); cout&&&输入多项式的系数 a[0]--a[n]:&; for(i=0;i&=n;i++) cin&&a[i]; cout&&&The polynomail value is &&&polynomail(a,n,x,n)&& return 0; } double polynomail(int a[],int i,double x,int n) { if(i&0) return a[n-i]+polynomail(a,i-1,x,n)*x; else return a[n]; }16本算法的时间复杂度为 o(n)。 第 2 章 线性表 2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个 元素结点） 。 解：头指针是指向链表中第一个结点的指针。首元结点是指链表 中存储第一个数据元素的结点。 头结点是在首元结点之前附设的一个 结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要 是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操 作进行统一处理。 2.2 填空题。 解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。(2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中 逻辑上相邻的元素的物理位置不一定紧邻。 (3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。(4) 在单链表中设置头结点的作用是 插入和删除首元结点时不用进行特殊处理。2.3 在什么情况下用顺序表比链表好？ 解：当线性表的数据元素在物理位置上是连续存储的时候，用顺 序表比用链表好，其特点是可以进行随机存取。172.4 对以下单链表分别执行下列各程序段，并画出结果示意图。解：2.5 画出执行下列各行语句后各指针及链表的示意图。 L=(LinkList)malloc(sizeof(LNode)); P=L; for(i=1;i&=4;i++){ P-&next=(LinkList)malloc(sizeof(LNode)); P=P-& P-&data=i*2-1;18} P-&next=NULL; for(i=4;i&=1;i--) Ins_LinkList(L,i+1,i*2); for(i=1;i&=3;i++) Del_LinkList(L,i); 解：【2.6】 已知 L 是无表头结点的单链表，且 P 结点既不是首元结点， 也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 a. 在 P 结点后插入 S 结点的语句序列是__________________。 b. 在 P 结点前插入 S 结点的语句序列是__________________。 c. 在表首插入 S 结点的语句序列是__________________。 d. 在表尾插入 S 结点的语句序列是__________________。 (1) P-&next=S; (2) P-&next=P-&next-& (3) P-&next=S-& (4) S-&next=P-&19(5) S-&next=L; (6) S-&next=NULL; (7) Q=P; (8) while(P-&next!=Q) P=P-& (9) while(P-&next!=NULL) P=P-& (10) P=Q; (11) P=L; (12) L=S; (13) L=P; 解：a. (4) (1) b. (7) (11) (8) (4) (1) c. (5) (12) d. (9) (1) (6) 【2.7】 已知 L 是带表头结点的非空单链表，且 P 结点既不是首元结 点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 a. 删 除 P 结 点 的 直 接 后 继 结 点 的 语 句 序 列 是 ____________________。 b. 删 除 P 结 点 的 直 接 前 驱 结 点 的 语 句 序 列 是 ____________________。 c. 删除 P 结点的语句序列是____________________。 d. 删除首元结点的语句序列是____________________。 e. 删除尾元结点的语句序列是____________________。20(1) P=P-& (2) P-&next=P; (3) P-&next=P-&next-& (4) P=P-&next-& (5) while(P!=NULL) P=P-& (6) while(Q-&next!=NULL) { P=Q; Q=Q-& } (7) while(P-&next!=Q) P=P-& (8) while(P-&next-&next!=Q) P=P-& (9) while(P-&next-&next!=NULL) P=P-& (10) Q=P; (11) Q=P-& (12) P=L; (13) L=L-& (14) free(Q); 解：a. (11) (3) (14) b. (10) (12) (8) (3) (14) c. (10) (12) (7) (3) (14) d. (12) (11) (3) (14) e. (9) (11) (3) (14) 2.8 已知 P 结点是某双向链表的中间结点，试从下列提供的答案中选 择合适的语句序列。 a. 在 P 结点后插入 S 结点的语句序列是(7) (3) (6) (12)。21b. 在 P 结点前插入 S 结点的语句序列是(8) (4) (5) (13)。 c. 删除 P 结点的直接后继结点的语句序列是(15) (1) (11) (18)。 d. 删除 P 结点的直接前驱结点的语句序列是(16) (2) (10) (18)。 e. 删除 P 结点的语句序列是(14) (9) (17)。 (1) P-&next=P-&next-& (2) P-&priou=P-&priou-& (3) P-&next=S; (4) P-&priou=S; (5) S-&next=P; (6) S-&priou=P; (7) S-&next=P-& (8) S-&priou=P-& (9) P-&priou-&next=P-& (10) P-&priou-&next=P; (11) P-&next-&priou=P; (12) P-&next-&priou=S; (13) P-&priou-&next=S; (14) P-&next-&priou=P-& (15) Q=P-& (16) Q=P-& (17) free(P); (18) free(Q);22【2.9】 简述以下算法的功能。 (1) Status A(LinkedList L) { //L 是无表头结点的单链表 if(L && L-&next) { Q=L; L=L-& P=L;while(P-&next) P=P-& P-&next=Q; } return OK; } (2) void BB(LNode *s, LNode *q) { p=s; while(p-&next!=q) p=p-& p-&next =s; } void AA(LNode *pa, LNode *pb) { //pa 和 pb 分别指向单循环链表中的两个结点 BB(pa,pb); BB(pb,pa); } 解：(1) 如果 L 的长度不小于 2，将 L 的首元结点变成尾元结点。 (2) 将单循环链表拆成两个单循环链表。 2.10 指出以下算法中的错误和低效之处，并将它改写为一个既正确23Q-&next=NULL;又高效的算法。 Status DeleteK(SqList &a,int i,int k) { //本过程从顺序存储结构的线性表 a 中删除第 i 个元素起的 k 个元素 if(i&1||k&0||i+k&a.length) return INFEASIBLE;//参数不合法 else { for(count=1;count&k;count++){ //删除第一个元素 for(j=a.j&=i+1;j--) a.elem[j-i]=a.elem[j]; a.length--; } return OK; } 解： Status DeleteK(SqList &a,int i,int k) { //从顺序存储结构的线性表 a 中删除第 i 个元素起的 k 个元素 //注意 i 的编号从 0 开始 if(i&0||i&a.length-1||k&0||k&a.length-i) return INFEASIBLE; for(j=0;j&=k;j++)24a.elem[j+i]=a.elem[j+i+k]; a.length=a.length-k; return OK; } 【2.11】 设顺序表 va 中的数据元素递增有序。试写一算法，将 x 插 入到顺序表的适当位置上，以保持该表的有序性。 解： Status InsertOrderList(SqList &va,ElemType x) { //在非递减的顺序表 va 中插入元素 x 并使其仍成为顺序表的算 法 if(va.length==va.listsize)return(OVERFLOW); for(i=va.i&0,x&va.elem[i-1];i--) va.elem[i]=va.elem[i-1]; va.elem[i]=x; va.length++; return OK; } 2.12 设 A ? ?a1 ,?, am ? 和 B ? ?b1 ,?, bn ?均为顺序表， A? 和 B ? 分别为 A 和 B 中除去最大共同前缀后的子表。若 A? ? B ? ? 空表，则 A ? B ；若 A? =空 表，而 B ? ? 空表，或者两者均不为空表，且 A? 的首元小于 B ? 的首元，25则 A ? B ；否则 A ? B 。试写一个比较 A ， B 大小的算法。 解： Status CompareOrderList(SqList &A,SqList &B) { int i,k,j; k=A.length&B.length?A.length:B. for(i=0;i&k;i++){ if(A.elem[i]&B.elem[i]) j=1; if(A.elem[i]&B.elem[i]) j=-1; } if(A.length&k) j=1; if(B.length&k) j=-1; if(A.length==B.length) j=0; } 2.13 试 写 一 算 法 在 带 头 结 点 的 单 链 表 结 构 上 实 现 线 性 表 操 作 Locate(L,x); 解： int LocateElem_L(LinkList &L,ElemType x) { int i=0; LinkList p=L;26while(p&&p-&data!=x){ p=p-& i++; } if(!p) return 0; } 【 2.14 】 试写一算法在带头结点的单链表结构上实现线性表操作 Length(L)。 解： //返回单链表的长度 int ListLength_L(LinkList &L) { int i=0; LinkList p=L; if(p) p=p- while(p){ p=p-& i++; } }272.15 已知指针 ha 和 hb 分别指向两个单链表的头结点，并且已知两 个链表的长度分别为 m 和 n。试写一算法将这两个链表连接在一起， 假设指针 hc 指向连接后的链表的头结点，并要求算法以尽可能短的 时间完成连接运算。请分析你的算法的时间复杂度。 解： void MergeList_L(LinkList &ha,LinkList &hb,LinkList &hc) { LinkList pa, pa= pb= while(pa-&next&&pb-&next){ pa=pa-& pb=pb-& } if(!pa-&next){ hc= while(pb-&next) pb=pb-& pb-&next=ha-& } else{ hc= while(pa-&next) pa=pa-&28pa-&next=hb-& } } 2.16 已知指针 la 和 lb 分别指向两个无头结点单链表中的首元结点。 下列算法是从表 la 中删除自第 i 个元素起共 len 个元素后，将它们插 入到表 lb 中第 i 个元素之前。 试问此算法是否正确？若有错，请改正 之。 Status DeleteAndInsertSub(LinkedList la,LinkedList lb,int i,int j,int len) { if(i&0||j&0||len&0) return INFEASIBLE; p= k=1; while(k&i){ q=p; while(k&=len){ s= k=1; while(k&j){ s-&next=p; return OK; } 解： Status DeleteAndInsertSub(LinkList &la,LinkList &lb,int i,int j,int29p=p-& k++;}q=q-& k++;}s=s-& k++; q-&next=s-&}len) { LinkList p,q,s,prev=NULL; int k=1; if(i&0||j&0||len&0) return INFEASIBLE; // 在 la 表中查找第 i 个结点 p= while(p&&k&i){ prev=p; p=p-& k++; } if(!p)return INFEASIBLE; // 在 la 表中查找第 i+len-1 个结点 q=p; k=1;while(q&&k&len){ q=p-& k++; } if(!q)return INFEASIBLE; // 完成删除，注意，i=1 的情况需要特殊处理 if(!prev) la=q-&30else prev-&next=q-& // 将从 la 中删除的结点插入到 lb 中 if(j=1){ q-&next= lb=p; } else{ s= k=1;while(s&&k&j-1){ s=s-& k++; } if(!s)return INFEASIBLE; q-&next=s-& s-&next=p; //完成插入 } return OK; } 2.17 试写一算法，在无头结点的动态单链表上实现线性表操作 Insert(L,i,b)，并和在带头结点的动态单链表上实现相同操作的算法进 行比较。 2.18 试写一算法，实现线性表操作 Delete(L,i)，并和在带头结点的动31态单链表上实现相同操作的算法进行比较。 2.19 已知线性表中的元素以值递增有序排列，并以单链表作存储结 构。试写一高效的算法，删除表中所有值大于 mink 且小于 maxk 的 元素（若表中存在这样的元素） ，同时释放被删结点空间，并分析你 的算法的时间复杂度（注意，mink 和 maxk 是给定的两个参变量，它 们的值可以和表中的元素相同，也可以不同） 。 解： Status ListDelete_L(LinkList &L,ElemType mink,ElemType maxk) { LinkList p,q,prev=NULL; if(mink&maxk)return ERROR; p=L; prev=p; p=p-& while(p&&p-&data&maxk){ if(p-&data&=mink){ prev=p; p=p-& } else{ prev-&next=p-& q=p;32p=p-& free(q); } } return OK; } 2.20 同 2.19 题条件，试写一高效的算法，删除表中所有值相同的多 余元素（使得操作后的线性表中所有元素的值均不相同） ，同时释放 被删结点空间，并分析你的算法的时间复杂度。 解： void ListDelete_LSameNode(LinkList &L) { LinkList p,q, p=L; prev=p; p=p-& while(p){ prev=p; p=p-& if(p&&p-&data==prev-&data){ prev-&next=p-& q=p;33p=p-& free(q); } } } 【2.21】 试写一算法，实现顺序表的就地逆置，即利用原表的存储 空间将线性表 ?a1 ,?, an ? 逆置为 ?an ,?, a1 ? 。 解： // 顺序表的逆置 Status ListOppose_Sq(SqList &L) { ElemT for(i=0;i&L.length/2;i++){ x=L.elem[i]; L.elem[i]=L.elem[L.length-1-i]; L.elem[L.length-1-i]=x; } return OK; } 【2.22】 试写一算法，对单链表实现就地逆置。 解：34// 带头结点的单链表的逆置 Status ListOppose_L(LinkList &L) { LinkList p,q; p=L; p=p-& L-&next=NULL; while(p){ q=p; p=p-& q-&next=L-& L-&next=q; } return OK; } 2.23 设线性表 A ? ?a1 , a2 ,?, am ? ，B ? ?b1 , b2 ,?, bn ? ，试写一个按下列规则 合并 A，B 为线性表 C 的算法，即使得C ? ?a1 , b1 ,?, am , bm , bm?1 ,?, bn ? 当 m ? n 时； C ? ?a1 , b1 ,?, an , bn , an?1 ,?, am ? 当 m ? n 时。线性表 A，B 和 C 均以单链表作存储结构，且 C 表利用 A 表和 B 表 中的结点空间构成。注意：单链表的长度值 m 和 n 均未显式存储。 解：35// 将合并后的结果放在 C 表中，并删除 B 表 Status ListMerge_L(LinkList &A,LinkList &B,LinkList &C) { LinkList pa,pb,qa, pa=A-& pb=B-& C=A; while(pa&&pb){ qa= qb=pa=pa-& pb=pb-& qb-&next=qa-& qa-&next= } if(!pa)qb-&next= pb=B; free(pb); return OK; } 【2.24】 假设有两个按元素值递增有序排列的线性表 A 和 B，均以 单链表作存储结构，请编写算法将 A 表和 B 表归并成一个按元素值 递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性 表 C，并要求利用原表（即 A 表和 B 表）的结点空间构造 C 表。36解： // 将合并逆置后的结果放在 C 表中，并删除 B 表 Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C) { LinkList pa,pb,qa, pa=A; pb=B; qa= // 保存 pa 的前驱指针 qb= // 保存 pb 的前驱指针 pa=pa-& pb=pb-& A-&next=NULL; C=A; while(pa&&pb){ if(pa-&data&pb-&data){ qa= pa=pa-& qa-&next=A-& A-&next= } else{ qb=37//将当前最小结点插入 A 表表头pb=pb-& qb-&next=A-& A-&next= } } while(pa){ qa= pa=pa-& qa-&next=A-& A-&next= } while(pb){ qb= pb=pb-& qb-&next=A-& A-&next= } pb=B; free(pb); return OK; } 2.25 假设以两个元素依值递增有序排列的线性表 A 和 B 分别表示两38//将当前最小结点插入 A 表表头个集合（即同一表中的元素值各不相同） ，现要求另辟空间构成一个 线性表 C，其元素为 A 和 B 中元素的交集，且表 C 中的元素有依值 递增有序排列。试对顺序表编写求 C 的算法。 解： // 将 A、B 求交后的结果放在 C 表中 Status ListCross_Sq(SqList &A,SqList &B,SqList &C) { int i=0,j=0,k=0; while(i&A.length && j&B.length){ if(A.elem[i]&B.elem[j]) else if(A.elem[i]&B.elem[j]) else{ ListInsert_Sq(C,k,A.elem[i]); i++; k++; } } return OK; } 2.26 要求同 2.25 题。试对单链表编写求 C 的算法。 解：39i++;j++;// 将 A、B 求交后的结果放在 C 表中，并删除 B 表 Status ListCross_L(LinkList &A,LinkList &B,LinkList &C) { LinkList pa,pb,qa,qb, pa=A; pb=B; qa= // 保存 pa 的前驱指针 qb= // 保存 pb 的前驱指针 pa=pa-& pb=pb-& C=A; while(pa&&pb){ if(pa-&data&pb-&data){ pt= pa=pa-& qa-&next= free(pt); } else if(pa-&data&pb-&data){ pt= pb=pb-&40qb-&next= free(pt); } else{ qa= pa=pa-& } } while(pa){ pt= pa=pa-& qa-&next= free(pt); } while(pb){ pt= pb=pb-& qb-&next= free(pt); } pb=B; free(pb);41return OK; } 2.27 对 2.25 题的条件作以下两点修改，对顺序表重新编写求得表 C 的算法。 (1) 假设在同一表（A 或 B）中可能存在值相同的元素，但要求新 生成的表 C 中的元素值各不相同； (2) 利用 A 表空间存放表 C。 解： (1) // A、B 求交，然后删除相同元素，将结果放在 C 表中 Status ListCrossDelSame_Sq(SqList &A,SqList &B,SqList &C) { int i=0,j=0,k=0; while(i&A.length && j&B.length){ if(A.elem[i]&B.elem[j]) else if(A.elem[i]&B.elem[j]) else{ if(C.length==0){ ListInsert_Sq(C,k,A.elem[i]); k++; }42i++;j++;else if(C.elem[C.length-1]!=A.elem[i]){ ListInsert_Sq(C,k,A.elem[i]); k++; } i++; } } return OK; } (2) // A、B 求交，然后删除相同元素，将结果放在 A 表中 Status ListCrossDelSame_Sq(SqList &A,SqList &B) { int i=0,j=0,k=0; while(i&A.length && j&B.length){ if(A.elem[i]&B.elem[j]) else if(A.elem[i]&B.elem[j]) else{ if(k==0){ A.elem[k]=A.elem[i];43i++;j++;k++; } else if(A.elem[k]!=A.elem[i]){ A.elem[k]=A.elem[i]; k++; } i++; } } A.length=k; return OK; } 2.28 对 2.25 题的条件作以下两点修改，对单链表重新编写求得表 C 的算法。 (1) 假设在同一表（A 或 B）中可能存在值相同的元素，但要求新 生成的表 C 中的元素值各不相同； (2) 利用原表（A 表或 B 表）中的结点构成表 C，并释放 A 表中 的无用结点空间。 解： (1) // A、B 求交，结果放在 C 表中，并删除相同元素44Status ListCrossDelSame_L(LinkList &A,LinkList &B,LinkList &C) { LinkList pa,pb,qa,qb, pa=A; pb=B; qa= // 保存 pa 的前驱指针 qb= // 保存 pb 的前驱指针 pa=pa-& pb=pb-& C=A; while(pa&&pb){ if(pa-&data&pb-&data){ pt= pa=pa-& qa-&next= free(pt); } else if(pa-&data&pb-&data){ pt= pb=pb-& qb-&next=45free(pt); } else{ if(pa-&data==qa-&data){ pt= pa=pa-& qa-&next= free(pt); } else{ qa= pa=pa-& } } } while(pa){ pt= pa=pa-& qa-&next= free(pt); } while(pb){46pt= pb=pb-& qb-&next= free(pt); } pb=B; free(pb); return OK; } (2) // A、B 求交，结果放在 A 表中，并删除相同元素 Status ListCrossDelSame_L(LinkList &A,LinkList &B) { LinkList pa,pb,qa,qb, pa=A; pb=B; qa= // 保存 pa 的前驱指针 qb= // 保存 pb 的前驱指针 pa=pa-& pb=pb-& while(pa&&pb){ if(pa-&data&pb-&data){47pt= pa=pa-& qa-&next= free(pt); } else if(pa-&data&pb-&data){ pt= pb=pb-& qb-&next= free(pt); } else{ if(pa-&data==qa-&data){ pt= pa=pa-& qa-&next= free(pt); } else{ qa= pa=pa-&48} } } while(pa){ pt= pa=pa-& qa-&next= free(pt); } while(pb){ pt= pb=pb-& qb-&next= free(pt); } pb=B; free(pb); return OK; } 2.29 已知 A，B 和 C 为三个递增有序的线性表，现要求对 A 表作如 下操作：删去那些既在 B 表中出现又在 C 表中出现的元素。试对顺 序表编写实现上述操作的算法， 并分析你的算法的时间复杂度 （注意：49题中没有特别指明同一表中的元素值各不相同） 。 解： // 在 A 中删除既在 B 中出现又在 C 中出现的元素，结果放在 D 中 Status ListUnion_Sq(SqList &D,SqList &A,SqList &B,SqList &C) { SqList T InitList_Sq(Temp); ListCross_L(B,C,Temp); ListMinus_L(A,Temp,D); } 2.30 要求同 2.29 题。试对单链表编写算法，请释放 A 表中的无用结 点空间。 解： // 在 A 中删除既在 B 中出现又在 C 中出现的元素，并释放 B、C Status ListUnion_L(LinkList &A,LinkList &B,LinkList &C) { ListCross_L(B,C); ListMinus_L(A,B); } // 求集合 A-B，结果放在 A 表中，并删除 B 表 Status ListMinus_L(LinkList &A,LinkList &B)50{ LinkList pa,pb,qa,qb, pa=A; pb=B; qa= // 保存 pa 的前驱指针 qb= // 保存 pb 的前驱指针 pa=pa-& pb=pb-& while(pa&&pb){ if(pb-&data&pa-&data){ pt= pb=pb-& qb-&next= free(pt); } else if(pb-&data&pa-&data){ qa= pa=pa-& } else{ pt=51pa=pa-& qa-&next= free(pt); } } while(pb){ pt= pb=pb-& qb-&next= free(pt); } pb=B; free(pb); return OK; } 2.31 假设某个单向循环链表的长度大于 1， 且表中既无头结点也无头 指针。已知 s 为指向链表中某个结点的指针，试编写算法在链表中删 除指针 s 所指结点的前驱结点。 解： // 在单循环链表 S 中删除 S 的前驱结点 Status ListDelete_CL(LinkList &S) {52LinkList p,q; if(S==S-&next)return ERROR; q=S; p=S-& while(p-&next!=S){ q=p; p=p-& } q-&next=p-& free(p); return OK; } 2.32 已知有一个单向循环链表，其每个结点中含三个域： pre，data 和 next，其中 data 为数据域，next 为指向后继结点的指针域，pre 也 为指针域，但它的值为空，试编写算法将此单向循环链表改为双向循 环链表，即使 pre 成为指向前驱结点的指针域。 解： // 建立一个空的循环链表 Status InitList_DL(DuLinkList &L) { L=(DuLinkList)malloc(sizeof(DuLNode)); if(!L) exit(OVERFLOW);53L-&pre=NULL; L-&next=L; return OK; } // 向循环链表中插入一个结点 Status ListInsert_DL(DuLinkList &L,ElemType e) { DuLinkL p=(DuLinkList)malloc(sizeof(DuLNode)); if(!p) return ERROR; p-&data=e; p-&next=L-& L-&next=p; return OK; } // 将单循环链表改成双向链表 Status ListCirToDu(DuLinkList &L) { DuLinkList p,q; q=L; p=L-& while(p!=L){54p-&pre=q; q=p; p=p-& } if(p==L) p-&pre=q; return OK; } 2.33 已知由一个线性链表表示的线性表中含有三类字符的数据元素 （如：字母字符、数字字符和其他字符） ，试编写算法将该线性表分 割为三个循环链表， 其中每个循环链表表示的线性表中均只含一类字 符。 解： // 将单链表 L 划分成 3 个单循环链表 Status ListDivideInto3CL(LinkList &L,LinkList &s1,LinkList&s2,LinkList &s3) { LinkList p,q,pt1,pt2,pt3; p=L-& pt1=s1; pt2=s2; pt3=s3; while(p){55if(p-&data&='0' && p-&data&='9'){ q=p; p=p-& q-&next=pt1-& pt1-&next=q; pt1=pt1-& } else if((p-&data&='A' && p-&data&='Z') || (p-&data&='a' && p-&data&='z')){ q=p; p=p-& q-&next=pt2-& pt2-&next=q; pt2=pt2-& } else{ q=p; p=p-& q-&next=pt3-& pt3-&next=q; pt3=pt3-&56} } q=L; free(q); return OK; } 在 2.34 至 2.36 题中，“异或指针双向链表”类型 XorLinkedList 和 指针异或函数 XorP 定义为： typedef struct XorNode { struct XorNode *LRP } XorNode, *XorP typede struct { //无头结点的异或指针双向链表 //分别指向链表的左侧和右端XorPointer Left, R } XorLinkedLXorPointer XorP(XorPointer p, XorPointer q); // 指针异或函数 XorP 返回指针 p 和 q 的异或值 2.34 假设在算法描述语言中引入指针的二元运算“异或”，若 a 和 b 为指针，则 ab 的运算结果仍为原指针类型，且 a(ab)=(aa)b=b (ab)b=a(bb)=a 则可利用一个指针域来实现双向链表 L。 链表 L 中的每个结点只含两57个域：data 域和 LRPtr 域，其中 LRPtr 域存放该结点的左邻与右邻结 点指针（不存在时为 NULL）的异或。若设指针 L.Left 指向链表中的 最左结点，L.Right 指向链表中的最右结点，则可实现从左向右或从 右向左遍历此双向链表的操作。 试写一算法按任一方向依次输出链表 中各元素的值。 解： Status TraversingLinkList(XorLinkedList &L,char d) { XorPointer p,left, if(d=='l'||d=='L'){ p=L.L left=NULL; while(p!=NULL){ VisitingData(p-&data); left=p; p=XorP(left,p-&LRPtr); } } else if(d=='r'||d=='R'){ p=L.R right=NULL;58while(p!=NULL){ VisitingData(p-&data); right=p; p=XorP(p-&LRPtr,right); } } else return ERROR; return OK; } 2.35 采用 2.34 题所述的存储结构，写出在第 i 个结点之前插入一个 结点的算法。 2.36 采用 2.34 题所述的存储结构，写出删除第 i 个结点的算法。 2.37 设以带头结点的双向循环链表表示的线性表 L ? ?a1, a2 ,?, an ? 。试 写一时间复杂度 O(n)的算法，将 L 改造为 L ? ?a1, a3 ,?, an ,?, a4 , a2 ?。 解： // 将双向链表 L=(a1,a2,...,an)改造为(a1,a3,...,an,...,a2) Status ListChange_DuL(DuLinkList &L) { DuLinkList p,q,r; p=L-& r=L-&59i=1; while(p!=r){ if(i%2==0){ q=p; p=p-& // 删除结点 q-&pre-&next=q-& q-&next-&pre=q-& // 插入到头结点的左面 q-&pre=r-&next-& r-&next-&pre=q; q-&next=r-& r-&next=q; } else p=p-& i++; } return OK; } 2.38 设有一个双向循环链表，每个结点中除有 pre，data 和 next 三个 域外， 还增设了一个访问频度域 freq。 在链表被起用之前， 频度域 freq 的值均初始化为零，而每当对链表进行一次 Locate(L,x)的操作后，被60访问的结点（即元素值等于 x 的结点）中的频度域 freq 的值便增 1， 同时调整链表中结点之间的次序， 使其按访问频度非递增的次序顺序 排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符 合上述要求的 Locate 操作的算法。 解： DuLinkList ListLocate_DuL(DuLinkList &L,ElemType e) { DuLinkList p,q; p=L-& while(p!=L && p-&data!=e) p=p-& if(p==L) return NULL; else{ p-&freq++; // 删除结点 p-&pre-&next=p-& p-&next-&pre=p-& // 插入到合适的位置 q=L-& while(q!=L && q-&freq&p-&freq) q=q-& if(q==L){ p-&next=q-& q-&next=p;61p-&pre=q-& q-&pre=p; } else{ // 在 q 之前插入 p-&next=q-&pre-& q-&pre-&next=p; p-&pre=q-& q-&pre=p; } } } 在 2.39 至 2.40 题中，稀疏多项式采用的顺序存储结构 SqPoly 定 义为 typedef struct { } PolyT typedef struct { PolyTerm *62//多项式的顺序存储结构} SqP 2.39 已 知 稀 疏 多 项 式 Pn ?x? ? c1xe ? c2 xe ? ? ? cm xe1 2 m， 其 中n ? em ? em?1 ? ? ? e1 ? 0 ， ci ? 0?i ? 1,2,?, m? ， m ? 1 。试采用存储量同多项式项数 m 成正比的顺序存储结构， 编写求 Pn ?x0 ? 的算法 （ x0 为给定值） ， 并分析你的算法的时间复杂度。 解： typedef struct{ } PolyT typedef struct{ PolyTerm * } SqP // 建立一个多项式 Status PolyInit(SqPoly &L) { PolyTerm *p; cout&&&请输入多项式的项数:&; cin&&L. L.data=(PolyTerm *)malloc(L.last*sizeof(PolyTerm));63if(!L.data) return ERROR; p=L. for(i=0;i&L.i++){ cout&&&请输入系数:&; cin&&p-& cout&&&请输入指数:&; cin&&p-& p++; } return OK; } // 求多项式的值 double PolySum(SqPoly &L,double x0) { double Pn,x; int i,j; PolyTerm *p; p=L. for(i=0,Pn=0;i&L.i++,p++){ for(j=0,x=1;j&p-&j++) x=x*x0; Pn=Pn+p-&coef*x; }64return Pn; } 2.40 采用 2.39 题给定的条件和存储结构， 编写求 P?x? ? Pn1 ?x? ? Pn2 ?x? 的 算法，将结果多项式存放在新辟的空间中，并分析你的算法的时间复 杂度。 解： // 求两多项式的差 Status PolyMinus(SqPoly &L,SqPoly &L1,SqPoly &L2) { PolyTerm *p,*p1,*p2; p=L. p1=L1. p2=L2. int i=0,j=0,k=0; while(i&L1.last&&j&L2.last){ if(p1-&exp&p2-&exp){ p-&coef=p1-& p-&exp=p1-& p++; k++;p1++; i++; } else65if(p1-&exp&p2-&exp){ p-&coef=-p2-& p-&exp=p2-& p++; k++;p2++; j++; } else{ if(p1-&coef!=p2-&coef){ p-&coef=(p1-&coef)-(p2-&coef); p-&exp=p1-& p++; } p1++; p2++; i++; } } if(i&L1.last) while(i&L1.last){ p-&coef=p1-& p-&exp=p1-& p++; k++; j++; k++;p1++; i++;66} if(j&L2.last) while(j&L2.last){ p-&coef=-p2-& p-&exp=p2-& p++; k++;p2++; j++; } L.last=k; return OK; } 在 2.41 至 2.42 题中，稀疏多项式采用的循环链表存储结构 LinkedPoly 定义为 typedef struct PolyNode { PolyT struct PolyNode * } PolyNode, *PolyL typedef PolyLink LinkedP 2.41 试以循环链表作稀疏多项式的存储结构，编写求其导函数的方 法，要求利用原多项式中的结点空间存放其导函数多项式，同时释放 所有无用结点。 解：67Status PolyDifferential(LinkedPoly &L) { LinkedPoly p,q, q=L; p=L-& while(p!=L){ if(p-&data.exp==0){ pt=p; p=p-& q-&next=p; free(pt); } else{ p-&data.coef=p-&data.coef*p-&data. p-&data.exp--; q=p; p=p-& } } return OK; } 2.42 试编写算法，将一个用循环链表表示的稀疏多项式分解成两个68多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原 链表中的结点空间构成这两个链表。 解： // 将单链表 L 划分成 2 个单循环链表 Status ListDivideInto2CL(LinkedPoly &L,LinkedPoly &L1) { LinkedPoly p,p1,q, q=L; p=L-& p1=L1; while(p!=L){ if(p-&data.exp%2==0){ pt=p; p=p-& q-&next=p; pt-&next=p1-& p1-&next= p1=p1-& } else{ q=p; p=p-&69} } return OK; } 第 3 章 栈和队列 【3.1】 若按教科书 3.1.1 节中图 3.1(b)所示铁道进行车厢调度 （注意： 两侧铁道均为单向行驶道） ，则请回答： (1) 如果进站的车厢序列为 123， 则可能得到的出站车厢序列是什 么？ (2) 如果进站的车厢序列为 123456， 则能否得到 435612 和 135426 的出站序列，并请说明为什么不能得到或者如何得到（即写出以 ?S? 表示进栈和以 ?X?表示出栈的栈操作序列） 。 解：(1) 123 231 321 213 132 (2) 可以得到 135426 的出站序列，但不能得到 435612 的出站序 列。因为 4356 出站说明 12 已经在栈中，1 不可能先于 2 出栈。 3.2 简述栈和线性表的差别。 解：线性表是具有相同特性的数据元素的一个有限序列。栈是限 定仅在表尾进行插入或删除操作的线性表。 【3.3】 写出下列程序段的输出结果（栈的元素类型 SElemType 为 char） 。 void main()70{ Stack S; char x,y; InitStack(S); x= ?c?; y= ?k?; Push(S,x); Push(S, ?a?); Pop(S,x); Push(S, ?t?); Pop(S,x); Push(S, ?s?); while(!StackEmpty(S)) { Pop(S,y); printf(y); } printf(x); } 解：stack 【3.4】 简述以下算法的功能（栈的元素类型 SElemType 为 int） 。 (1) status algo1(Stack S) { int i,n,A[255]; n=0; while(!StackEmpty(S)) { n++; Pop(S,A[n]); } for(i=1;i&=n;i++) Push(S,A[i]); } (2) status algo2(Stack S,int e) {71Push(S,y); Push(S,x);Stack T; InitStack(T); while(!StackEmpty(S)){ Pop(S,d); if(d!=e) Push(T,d); } while(!StackEmpty(T)){ Pop(T,d); Push(S,d); } } 解：(1) 栈中的数据元素逆置 从栈中清除 3.5 假设以 S 和 X 分别表示入栈和出栈的操作， 则初态和终态均为空 栈的入栈和出栈的操作序列可以表示为仅由 S 和 X 组成的序列。称 可以操作的序列为合法序列（例如，SXSX 为合法序列，SXXS 为非 法序列） 。试给出区分给定序列为合法序列或非法序列的一般准则， 并证明：两个不同的合法（栈操作）序列（对同一输入序列）不可能 得到相同的输出元素 （注意： 在此指的是元素实体， 而不是值） 序列。 解：任何前 n 个序列中 S 的个数一定大于 X 的个数。 设两个合法序列为： T1=S……X……S……72(2) 如果栈中存在元素 e，将其T2=S……X……X…… 假定前 n 个操作都相同，从第 n+1 个操作开始，为序列不同的起 始操作点。由于前 n 个操作相同，故此时两个栈（不妨为栈 A、B） 的存储情况完全相同，假设此时栈顶元素均为 a。 第 n+1 个操作不同，不妨 T1 的第 n+1 个操作为 S，T2 的第 n+1 个操作为 X。T1 为入栈操作，假设将 b 压栈，则 T1 的输出顺序一定 是先 b 后 a；而 T2 将 a 退栈，则其输出顺序一定是先 a 后 b。由于 T1 的输出为……ba……，而 T2 的输出顺序为……ab……，说明两个 不同的合法栈操作序列的输出元素的序列一定不同。 3.6 试 证 明 ： 若 借 助 栈 由 输 入 序 列 12…n 得 到 的 输 出 序 列 为p1 p2 ? pn (它是输入序列的一个排列)，则在输出序列中不可能出现这样的情形：存在着 i&j&k 使 p j & pk & pi 。 解：这个问题和 3.1 题比较相似。因为输入序列是从小到大排列 的，所以若 p j & pk & pi ，则可以理解为通过输入序列 p j pk pi 可以得到 输出序列 pi p j pk ， 显然通过序列 123 是无法得到 312 的， 参见 3.1 题。 所以不可能存在着 i&j&k 使 p j & pk & pi 。 3.7 按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例，并仿 照教科书 3.2 节例 3-2 的格式，画出对下列算术表达式求值时操作数 栈和运算符栈的变化过程： A-B×C/D+E↑F 解：BC=G G/D=H A-H=I E^F=J I+J=K 步 骤 OPTR 栈 OPND 栈 输入字符73主要操作1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17# # ###-* #-* ##-/ #-/ ## #+ #+ #+^ #+^ #+ # A A AB AB ABC AG AG AGD AH I I IE IE IEF IJ KA-B*C/D+ E^F# -B*C/D+E^ F# B*C/D+E^ F# *C/D+E^F# C/D+E^F# /D+E^F# /D+E^F# D+E^F# +E^F# +E^F# +E^F# E^F# ^F# F# # # #PUSH(OPND,A) PUSH(OPTR,-) PUSH(OPND,B) PUSH(OPTR,*) PUSH(OPND,C) Operate(B,*,C) PUSH(OPTR,/) PUSH(OPND,D) Operate(G,/,D) Operate(A,-,H) PUSH(OPTR,+) PUSH(OPND,E) PUSH(OPTR,^) PUSH(OPND,F) Operate(E,^,F) Operate(I,+,J) RETURN3.8 试推导求解 n 阶梵塔问题至少要执行的 move 操作的次数。 解： 2 n ? 1 【3.9】 试将下列递推过程改写为递归过程。 void ditui(int n) { i = while(i&1) cout&&i--; } 解： void ditui(int j)74{ if(j&1){ cout&&j; ditui(j-1); } } 【3.10】 试将下列递归过程改写为非递归过程。 void test(int &sum) { cin&&x; if(x==0) sum=0; else { test(sum); sum+=x; } cout&& } 解： void test(int &sum)75{ S InitStack(s); do{ cin&&x; Push(s,x); }while(x&0); while(!StackEmpty(s)){ Pop(s,x); sum+=x; cout&&sum&& } DestoryStack(s); } 3.11 简述队列和堆栈这两种数据类型的相同点和差异处。 解：栈是一种运算受限的线性表，其限制是仅允许在表的一端进 行插入和删除运算。 队列也是一种运算受限的线性表，其限制是仅允许在表的一端进 行插入，而在表的另一端进行删除。 3.12 写出以下程序段的输出结果（队列中的元素类型 QElemType 为 char） 。76void main() { Queue Q; InitQueue(Q); char x= ?e?, y= ?c?; EnQueue(Q, ?h?); EnQueue(Q, ?r?); EnQueue(Q, y); DeQueue(Q, x); EnQueue(Q, x); DeQueue(Q, x); EnQueue(Q, ?a?); While(!QueueEmpty(Q)) { DeQueue(Q,y); cout&&y; } cout&&x; } 解：char 3.13 简述以下算法的功能（栈和队列的元素类型均为 int） 。 void algo3(Queue &Q)77{ Stack S; InitStack(S); while(!QueueEmpty(Q)) { DeQueue(Q, d); Push(S, d); } while(!StackEmpty(S)) { Pop(S, d); EnQueue(Q, d); } } 解：队列逆置 3.14 若以 1234 作为双端队列的输入序列，试分别求出满足以下条件 的输出序列： (1) 能由输入受限的双端队列得到，但不能由输出受限的双端队 列得到的输出序列。 (2) 能由输出受限的双端队列得到，但不能由输入受限的双端队 列得到的输出序列。78(3) 既不能由输入受限的双端队列得到，也不能由输出受限的双 端队列得到的输出序列。 3.15 假设以顺序存储结构实现一个双向栈，即在一维数组的存储空 间中存在着两个栈，它们的栈底分别设在数组的两个端点。试编写实 现这个双向栈 tws 的三个操作： 初始化 inistack(tws)、 入栈 push(tws,i,x) 和出栈 pop(tws,i)的算法，其中 i 为 0 或 1，用以分别指示设在数组两 端的两个栈， 并讨论按过程(正/误状态变量可设为变参)或函数设计这 些操作算法各有什么有缺点。 解： class DStack{ ElemType *top[2]; ElemType *p; public: DStack(int m) { p=new ElemType[m]; if(!p) exit(OVERFLOW); top[0]=p+m/2; top[1]=top[0]; stacksize=m;79} ~DStack(){} void Push(int i,ElemType x) { di=i; if(di==0){ if(top[0]&=p) *top[0]--=x; else cerr&&&Stack overflow!&; } else{ if(top[1]&p+stacksize-1) *++top[1]=x; else cerr&&&Stack overflow!&; } } ElemType Pop(int i) { di=i; if(di==0){ if(top[0]&top[1]) return *++top[0]; else cerr&&&Stack empty!&; }else{ if(top[1]&top[0]) return *top[1]--;80else cerr&&&Stack empty!&; } return OK; } };// 链栈的数据结构及方法的定义 typedef struct NodeType{ ElemT NodeType * }NodeType,*LinkT typedef struct{ LinkT }Svoid InitStack(Stack &s) { s.top=NULL; s.size=0; }81void DestroyStack(Stack &s) { LinkT while(s.top){ p=s. s.top=p-& s.size--; } }void ClearStack(Stack &s) { LinkT while(s.top){ p=s. s.top=p-& s.size--; } }82int StackLength(Stack s) { return s. }Status StackEmpty(Stack s) { if(s.size==0) return TRUE; else return FALSE; }Status GetTop(Stack s,ElemType &e) { if(!s.top) return ERROR; else{ e=s.top-& return OK; } }Status Push(Stack &s,ElemType e) {83LinkT p=new NodeT if(!p) exit(OVERFLOW); p-&next=s. s.top=p; p-&data=e; s.size++; return OK; }Status Pop(Stack &s,ElemType &e) { LinkT if(s.top){ e=s.top-& p=s. s.top=p-& s.size--; } return OK; }84// 从栈顶到栈底用 Visit()函数遍历栈中每个数据元素 void StackTraverse(Stack s,Status (*Visit)(ElemType e)) { LinkT p=s. while(p) Visit(p-&data); } 3.16 假设如题 3.1 所属火车调度站的入口处有 n 节硬席或软席车厢 （分别以 H 和 S 表示）等待调度，试编写算法，输出对这 n 节车厢 进行调度的操作（即入栈或出栈操作）序列，以使所有的软席车厢都 被调整到硬席车厢之前。 解： int main() { S char Buffer[80]; int i=0,j=0; InitStack(s); cout&&&请输入硬席(H)和软席车厢(S)序列：&; cin&&B cout&&Buffer&& while(Buffer[i]){85if(Buffer[i]=='S'){ Buffer[j]=Buffer[i]; j++; } else Push(s,Buffer[i]); i++; } while(Buffer[j]){ Pop(s,Buffer[j]); j++; } cout&&Buffer&& return 0; } 3.17 试写一个算法，识别一次读入的一个以 @为结束符的字符序列 是否为形如?序列 1&序列 2?模式的字符序列。 其中序列 1 和序列 2 中 都不含字符?&?，且序列 2 是序列 1 的逆序列。例如，?a+b&b+a?是属 该模式的字符序列，而?1+3&3-1?则不是。 解： BOOL Symmetry(char a[]) { int i=0;86S InitStack(s); ElemT while(a[i]!='&' && a[i]){ Push(s,a[i]); i++; } if(a[i]) return FALSE; i++; while(a[i]){ Pop(s,x); if(x!=a[i]){ DestroyStack(s); return FALSE; } i++; } return TRUE; } 3.18 试写一个判别表达式中开、闭括号是否配对出现的算法。 解： BOOL BracketCorrespondency(char a[])87{ int i=0; S InitStack(s); ElemT while(a[i]){ switch(a[i]){ case '(': Push(s,a[i]); case '[': Push(s,a[i]); case ')': GetTop(s,x); if(x=='(') Pop(s,x); else return FALSE; case ']': GetTop(s,x); if(x=='[') Pop(s,x); else return FALSE;88
default: } i++; } if(s.size!=0) return FALSE; return TRUE; } 3.20 假设以二维数组 g(1…m, 1…n)表示一个图像区域，g[i,j]表示该 区域中点(i,j)所具颜色， 其值为从 0 到 k 的整数。 编写算法置换点(i0,j0) 所在区域的颜色。约定和(i0,j0)同色的上、下、左、右的邻接点为同色 区域的点。 解： #include &iostream.h& #include &stdlib.h&typedef struct{ }PosT typedef struct{89int C int V PosT }ElemT#include &d:\VC99\Stack.h&#define M 8 #define N 8ElemType g[M][N];void CreateGDS(ElemType g[M][N]); void ShowGraphArray(ElemType g[M][N]); void RegionFilling(ElemType g[M][N],PosType CurPos,int NewColor);int main() { CreateGDS(g); ShowGraphArray(g);PosType StartP90StartPos.x=5; StartPos.y=5; int FillColor=6; RegionFilling(g,StartPos,FillColor); cout&& ShowGraphArray(g); return 0; }void RegionFilling(ElemType g[M][N],PosType CurPos,int FillColor) { S InitStack(s); ElemT int OldColor=g[CurPos.x][CurPos.y].CPush(s,g[CurPos.x][CurPos.y]); while(!StackEmpty(s)){ Pop(s,e); CurPos=e. g[CurPos.x][CurPos.y].Color=FillC g[CurPos.x][CurPos.y].Visited=1;91if(CurPos.x&M && !g[CurPos.x+1][CurPos.y].Visited && g[CurPos.x+1][CurPos.y].Color==OldColor ) Push(s,g[CurPos.x+1][CurPos.y]); if(CurPos.x&0 && !g[CurPos.x-1][CurPos.y].Visited && g[CurPos.x-1][CurPos.y].Color==OldColor ) Push(s,g[CurPos.x-1][CurPos.y]); if(CurPos.y&N && !g[CurPos.x][CurPos.y+1].Visited && g[CurPos.x][CurPos.y+1].Color==OldColor ) Push(s,g[CurPos.x][CurPos.y+1]); if(CurPos.y&0 && !g[CurPos.x][CurPos.y-1].Visited && g[CurPos.x][CurPos.y-1].Color==OldColor ) Push(s,g[CurPos.x][CurPos.y-1]); }92}void CreateGDS(ElemType g[M][N]) { int i,j; for(i=0;i&M;i++) for(j=0;j&N;j++){ g[i][j].seat.x=i; g[i][j].seat.y=j; g[i][j].Visited=0; g[i][j].Color=0; } for(i=2;i&5;i++) for(j=2;j&4;j++) g[i][j].Color=3; for(i=5;i&M-1;i++) for(j=3;j&6;j++) g[i][j].Color=3; }void ShowGraphArray(ElemType g[M][N]) {93int i,j; for(i=0;i&M;i++){ for(j=0;j&N;j++) cout&&g[i][j].C cout&& } } 3.21 假设表达式有单字母变量和双目四则运算符构成。试写一个算 法，将一个通常书写形式且书写正确的表达式转换为逆波兰表达式。 解： // 输入的表达式串必须为#...#格式 void InversePolandExpression(char Buffer[]) { S InitStack(s); int i=0,j=0; ElemTPush(s,Buffer[i]); i++; while(Buffer[i]!='#'){ if(!IsOperator(Buffer[i])){ // 是操作数94Buffer[j]=Buffer[i]; i++; j++; } else{ // 是操作符 GetTop(s,e); if(Prior(e,Buffer[i])){// 当栈顶优先权高于当前序列时，退 栈 Pop(s,e); Buffer[j]=e; j++; } else{ Push(s,Buffer[i]); i++; } } } while(!StackEmpty(s)){ Pop(s,e); Buffer[j]=e; j++;95} }Status IsOpertor(char c) { char *p=&#+-*/&; while(*p){ if(*p==c) return TRUE; p++; } return FALSE; }Status Prior(char c1,char c2) { char ch[]=&#+-*/&; int i=0,j=0; while(ch[i] && ch[i]!=c1) i++; if(i==2) i--; if(i==4) i--; // 加和减可认为是同级别的运算符 // 乘和除可认为是同级别的运算符while(ch[j] && ch[j]!=c2) j++;96if(j==2) j--; if(j==4) j--; if(i&=j) return TRUE; else return FALSE; } 3.22 如题 3.21 的假设条件，试写一个算法，对以逆波兰式表示的表 达式求值。 解： char CalVal_InverPoland(char Buffer[]) { Stack O InitStack(Opnd); int i=0; ElemType e1,e2;while(Buffer[i]!='#'){ if(!IsOperator(Buffer[i])){ Push(Opnd,Buffer[i]); } else{ Pop(Opnd,e2);97Pop(Opnd,e1); c=Cal(e1,Buffer[i],e2); Push(Opnd,c); } i++; } }char Cal(char c1,char op,char c2) { int x,x1,x2; char ch[10]; ch[0]=c1; ch[1]='\0'; x1=atoi(ch);ch[0]=c2; ch[1]='\0'; x2=atoi(ch);switch(op){98case '+': x=x1+x2; case '-': x=x1-x2; case '*': x=x1*x2; case '/': x=x1/x2; default: } itoa(x,ch,10); return ch[0]; } 3.23 如题 3.21 的假设条件，试写一个算法，判断给定的非空后缀表 达式是否为正确的逆波兰表达式，如果是，则将它转化为波兰式。 解： #include &iostream.h&99#include &stdlib.h& #include &string.h& #include &d:\VC99\DSConstant.h&typedef char ARRAY[30]; typedef ARRAY ElemT typedef struct NodeType{ ElemT NodeType * }NodeType,*LinkT typedef struct{ LinkT }Svoid InitStack(Stack &s); Status Push(Stack &s,ElemType e); Status Pop(Stack &s,ElemType e); Status IsOperator(char c); Status StackEmpty(Stack s);Status InvToFroPoland(char a[]);100int main() { char a[30]; cout&&&请输入逆波兰算术表达式字符序列：&; cin&&a; if(InvToFroPoland(a)) cout&&a&& else cout&&&输入逆波兰算术表达式字符序列错误!&; return 0; }Status InvToFroPoland(char a[]) { S InitStack(s); int i=0; ElemT ElemType c1; ElemType c2;while(a[i]!='#'){ if(!IsOperator(a[i])){101if(a[i]&='0' && a[i]&='9'){ ch[0]=a[i]; ch[1]='\0'; Push(s,ch); } else return FALSE; } else{ ch[0]=a[i]; ch[1]='\0'; if(!StackEmpty(s)){ Pop(s,c2); if(!StackEmpty(s)){ Pop(s,c1); strcat(ch,c1); strcat(ch,c2); Push(s,ch); } else return FALSE; } else return FALSE; } i++;102} if(!StackEmpty(s)){ Pop(s,c1); strcpy(a,c1); } else return FALSE; if(!StackEmpty(s)) return FALSE; return OK; } void InitStack(Stack &s) { s.top=NULL; s.size=0; }Status Push(Stack &s,ElemType e) { LinkT p=new NodeT if(!p) exit(OVERFLOW); p-&next=s. s.top=p;103strcpy(p-&data,e); s.size++; return OK; }Status Pop(Stack &s,ElemType e) { LinkT if(s.top){ strcpy(e,s.top-&data); p=s. s.top=p-& s.size--; } return OK; }Status StackEmpty(Stack s) { if(s.size==0) return TRUE; else return FALSE;104}Status IsOperator(char c) { char *p=&#+-*/&; while(*p){ if(*p==c) return TRUE; p++; } return FALSE; } 【3.24】 试编写如下定义的递归函数的递归算法，并根据算法画出 求 g(5,2)时栈的变化过程。0 m ? 0, n ? 0 ? g ?m, n? ? ? ? g ?m ? 1,2n? ? n m ? 0, n ? 0解： int g(int m,int n); int main() { int m,n; cout&&&请输入 m 和 n 的值：&; cin&&m&&n;105if(n&=0) cout&&g(m,n)&& else cout&&&No Solution!&; return 0; } int g(int m,int n) { if(m&0) return(g(m-1,2*n)+n); else return 0; } 假设主函数的返回地址为 0，递归函数 3 条语句的地址分别为 1、 2、3。 3 3 3 3 3 0 0 1 2 3 4 5 64 32 16 8 4 23.25 试写出求递归函数 F(n)的递归算法，并消除递归：? ? n ?1 F ?n ? ? ? n?F n ? 2 ?? ?n?0 n?0解： #include &iostream.h& #define N 20 int main()106{ int a[N]; cout&&&请输入 n:&; cin&&n; for(i=0;i&n+1;i++){ if(i&1) a[i]=1; else a[i]=i*a[i/2]; } cout&&a[n]&& return 0; } 3.26 求解平方根 A 的迭代函数定义如下：? p ? sqrt? A, p, e ? ? ? ? 1? A? ? ? ? ? sqrt A , p ? ? ?, e ? ? 2? ? p ? ? ? ? ? p2 ? A ? e p2 ? A ? e其中，p 是 A 的近似平方根，e 是结果允许误差。试写出相应的递归 算法，并消除递归。 解： #include &iostream.h& double Sqrt(double A,double p,double e); int main()107{ double A,p,e; cout&&&请输入 A p e:&; cin&&A&&p&&e; cout&&Sqrt(A,p,e)&& return 0; } double Sqrt(double A,double p,double e) { if((p*p-A)&-e && (p*p-A)&e) else return Sqrt(A,(p+A/p)/2,e); } 3.27 已知 Ackerman 函数的定义如下：n ?1 m?0 ? ? akm?m, n ? ? ? akm?m ? 1,1? m ? 0, n ? 0 ?akm?m ? 1, akm?m, n ? 1?? m ? 0, n ? 0 ?(1) 写出递归算法； (2) 写出非递归算法； (3) 根据非递归算法，画出求 akm(2,1)时栈的变化过程。 解： unsigned int akm(unsigned int m,unsigned int n)108{ if(m==0) return n+1; else if(n==0) return akm(m-1,1); else{ g=akm(m,n-1); return akm(m-1,g); } } 非递归算法： int akm1(int m,int n) { S InitStack(s); ElemType e,e1,d; e.mval=m; Push(s,e); do{ while(e.mval){ while(e.nval){109e.nval=n;e.nval--; Push(s,e); } e.mval--; e.nval=1; } if(StackLength(s)&1){ e1.nval=e. Pop(s,e); e.mval--; e.nval=e1.nval+1; } }while(StackLength(s)!=1||e.mval!=0); return e.nval+1; }0,akm(2,1) 1,akm(2,0) 2,akm(1,1) 3,akm(1,0) 4,akm(0,1)021 620 411 610 401g=akm(2,0) akm=akm(m-1,1)=akm(1,1) g=akm(m,n-1)=akm(1,0) akm=akm(m-1,1)=akm(0,1) akm=n+1=2 退栈0,akm(2,1)021g=akm(2,0)1101,akm(2,0) 2,akm(1,1) 3,akm(1,0)620 411 610akm=akm(m-1,1)=akm(1,1) g=akm(m,n-1)=akm(1,0) akm=akm(m-1,1)=akm(0,1)=2 退栈0,akm(2,1) 1,akm(2,0) 2,akm(1,1)021 620 411g=akm(2,0) akm=akm(m-1,1)=akm(1,1) g=akm(m,n-1)=akm(1,0)=2;akm=akm(m-1,g)=akm(0,2); 3,akm(0,2) 702 akm=n+1=3 退栈0,akm(2,1) 1,akm(2,0) 2,akm(1,1)021 620 411g=akm(2,0) akm=akm(m-1,1)=akm(1,1) g=akm(m,n-1)=akm(1,0)=2;akm=akm(m-1,g)=akm(0,2)=3; 退栈0,akm(2,1) 1,akm(2,0)021 620g=akm(2,0) akm=akm(m-1,1)=akm(1,1)=3 退栈0,akm(2,1) 1,akm(1,3) 2,akm(1,2)021 613 612g=akm(2,0)=3; akm=akm(1,3) g=akm(1,2); akm(m-1,g) g=akm(1,1); akm(m-1,g)1113,akm(1,1) 4,akm(1,0) 5,akm(0,1)611 610 401g=akm(1,0); akm(m-1,g) akm=akm(0,1) akm(0,1)=2 退栈0,akm(2,1) 1,akm(1,3) 2,akm(1,2) 3,akm(1,1) 4,akm(1,0)021 613 612 611 610g=akm(2,0)=3; akm=akm(1,3) g=akm(1,2); akm(m-1,g) g=akm(1,1); akm(m-1,g) g=akm(1,0); akm(m-1,g) akm=akm(0,1)=2 退栈0,akm(2,1) 1,akm(1,3) 2,akm(1,2) 3,akm(1,1) 4,akm(0,2)021 613 612 611 702g=akm(2,0)=3; akm=akm(1,3) g=akm(1,2); akm(m-1,g) g=akm(1,1); akm(m-1,g) g=akm(1,0)=2; akm(m-1,g)=akm(0,2) akm=n+1=3 退栈0,akm(2,1) 1,akm(1,3) 2,akm(1,2) 3,akm(1,1)021 613 612 611g=akm(2,0)=3; akm=akm(1,3) g=akm(1,2); akm(m-1,g) g=akm(1,1); akm(m-1,g) g=akm(1,0)=2; akm(m-1,g)=akm(0,2)=3 退栈0,akm(2,1)021g=akm(2,0)=3; akm=akm(1,3)1121,akm(1,3) 2,akm(1,2) 3,akm(0,3)613 612 703g=akm(1,2); akm(m-1,g) g=akm(1,1)=3; akm(m-1,g)=akm(0,3) akm=n+1=4 退栈0,akm(2,1) 1,akm(1,3) 2,akm(1,2)021 613 612g=akm(2,0)=3; akm=akm(1,3) g=akm(1,2); akm(m-1,g) g=akm(1,1)=3; akm(m-1,g)=akm(0,3)=4 退栈0,akm(2,1) 1,akm(1,3) 2,akm(0,4)021 613 704g=akm(2,0)=3; akm=akm(1,3) g=akm(1,2)=4; akm(m-1,g)=akm(0,4) akm=n+1=5 退栈0,akm(2,1) 1,akm(1,3)021 613g=akm(2,0)=3; akm=akm(1,3) g=akm(1,2)=4; akm(m-1,g)=akm(0,4)=5 退栈0,akm(2,1)021g=akm(2,0)=3; akm=akm(1,3)=5 退栈akm(2,1)=5; 3.28 假设以带头结点的循环链表表示队列，并且只设一个指针指向 队尾元素结点（注意不设头指针） ，试编写相应的队列初始化、入队 列何处队列的算法。 解：113typedef int ElemT typedef struct NodeType{ ElemT NodeType * }QNode,*QP typedef struct{ QP }Q Status InitQueue(Queue& q) { q.rear=NULL; q.size=0; return OK; } Status EnQueue(Queue& q,ElemType e) { QP p=new QN if(!p) return FALSE; p-&data=e; if(!q.rear){114q.rear=p; p-&next=q. } else{ p-&next=q.rear-& q.rear-&next=p; q.rear=p; } q.size++; return OK; } Status DeQueue(Queue& q,ElemType& e) { QP if(q.size==0)return FALSE; if(q.size==1){ p=q. e=p-& q.rear=NULL; } else{115p=q.rear-& e=p-& q.rear-&next=p-& } q.size--; return OK; } 3.29 如果希望循环队列中的元素都能得到利用，则需设置一个标志 域 tag，并以 tag 的值为 0 和 1 来区分，尾指针和头指针值相同时的 队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队列的 算法， 并从时间和空间角度讨论设标志和不设标志这两种方法的使用 范围（如当循环队列容量较小而队列中每个元素占的空间较多时，哪 一种方法较好） 。 解： #define MaxQSize 4 typedef int ElemT typedef struct{ ElemType * S116}Q Status InitQueue(Queue& q) { q.base=new ElemType[MaxQSize]; if(!q.base) return FALSE; q.front=0; q.rear=0; q.tag=0; return OK; } Status EnQueue(Queue& q,ElemType e) { if(q.front==q.rear&&q.tag) return FALSE; else{ q.base[q.rear]=e; q.rear=(q.rear+1)%MaxQS if(q.rear==q.front)q.tag=1; } return OK; } Status DeQueue(Queue& q,ElemType& e) {117if(q.front==q.rear&&!q.tag)return FALSE; else{ e=q.base[q.front]; q.front=(q.front+1)%MaxQS q.tag=0; } return OK; } 设标志节省存储空间，但运行时间较长。不设标志则正好相反。 3.30 假设将循环队列定义为:以域变量 rear 和 length 分别指示循环队 列中队尾元素的位置和内含元素的个数。 试给出此循环队列的队满条 件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回 队头元素） 。 解： #define MaxQSize 4 typedef int ElemT typedef struct{ ElemType * }Q Status InitQueue(Queue& q)118{ q.base=new ElemType[MaxQSize]; if(!q.base) return FALSE; q.rear=0; q.length=0; return OK; } Status EnQueue(Queue& q,ElemType e) { if((q.rear+1)%MaxQSize==(q.rear+MaxQSize-q.length)%MaxQSize) return FALSE; else{ q.base[q.rear]=e; q.rear=(q.rear+1)%MaxQS q.length++; } return OK; } Status DeQueue(Queue& q,ElemType& e) { if((q.rear+MaxQSize-q.length)%MaxQSize==q.rear) return FALSE;119else{ e=q.base[(q.rear+MaxQSize-q.length)%MaxQSize]; q.length--; } return OK; } 3.31 假设称正读和反读都相同的字符序列为“回文”，例如，?abba?和 ?abcba?是回文，?abcde?和?ababab?则不是回文。试写一个算法判别读 入的一个以?@?为结束符的字符序列是否是“回文”。 解： Status SymmetryString(char* p) { Q if(!InitQueue(q)) return 0; S InitStack(s); ElemType e1,e2; while(*p){ Push(s,*p); EnQueue(q,*p); p++; }120while(!StackEmpty(s)){ Pop(s,e1); DeQueue(q,e2); if(e1!=e2) return FALSE; } return OK; } 3.32 试利用循环队列编写求 k 阶菲波那契序列中前 n+1 项的算法， 要求满足：fn ? max 而 f n ?1 ? max， 其中 max 为某个约定的常数。 （注意： 本题所用循环队列的容量仅为 k，则在算法执行结束时，留在循环队 列中的元素应是所求 k 阶菲波那契序列中的最后 k 项） 解： int Fibonacci(int k,int n) { if(k&1) exit(OVERFLOW); Q InitQueue(q,k); ElemType x,e; int i=0; while(i&=n){ if(i&k-1){ if(!EnQueue(q,0)) exit(OVERFLOW);121} if(i==k-1){ if(!EnQueue(q,1)) exit(OVERFLOW); } if(i&=k){ // 队列求和 x=sum(q); DeQueue(q,e); EnQueue(q,x); } i++; } return q.base[(q.rear+q.MaxSize-1)%q.MaxSize]; } 3.33 在顺序存储结构上实现输出受限的双端循环队列的入列和出列 （只允许队头出列）算法。设每个元素表示一个待处理的作业，元素 值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个 新提交的作业的预计执行时间小于队头和队尾作业的平均时间， 则插 入在队头，否则插入在队尾。 解： // Filename:Queue.h typedef struct{122ElemType * S int MaxS }DQ Status InitDQueue(DQueue& q,int size) { q.MaxSize= q.base=new ElemType[q.MaxSize]; if(!q.base) return FALSE; q.front=0; q.rear=0; q.tag=0; return OK; } Status EnDQueue(DQueue& q,ElemType e) { if(q.front==q.rear&&q.tag) return FALSE; if(q.front==q.rear&&!q.tag){ // 空队列 q.base[q.rear]=e; q.rear=(q.rear+1)%q.MaxS123if(q.rear==q.front)q.tag=1; } else{ // 非空非满if(e&(q.base[q.front]+q.base[(q.rear+q.MaxSize-1)%q.MaxSize])/2){ // 从队头入队 q.front=(q.front+q.MaxSize-1)%q.MaxS q.base[q.front]=e; if(q.rear==q.front)q.tag=1; } else{ // 从队尾入队 q.base[q.rear]=e; q.rear=(q.rear+1)%q.MaxS if(q.rear==q.front)q.tag=1; } } return OK; } Status DeDQueue(DQueue& q,ElemType& e) { if(q.front==q.rear&&!q.tag)return FALSE; else{ // 非空队列124e=q.base[q.front]; q.front=(q.front+1)%q.MaxS q.tag=0; } return OK; } // Filename:XT333.cpp 主程序文件 #include &iostream.h& #include &stdlib.h& typedef int ElemT #include &D:\VC99\Queue.h&int main() { int t1,t2,t3,t4; ElemT cout&&&请输入作业 a1、a2、a3、a4 的执行时间: &; cin&&t1&&t2&&t3&&t4; DQ InitDQueue(dq,5); EnDQueue(dq,t1); EnDQueue(dq,t2);125EnDQueue(dq,t3); EnDQueue(dq,t4); while(dq.front!=dq.rear||dq.tag){ DeDQueue(dq,e); cout&&e&& } return 0; } 3.34 假设在如教科书 3.4.1 节中图 3.9 所示的铁道转轨网的输入端有 n 节车厢：硬座、硬卧和软卧（分别以 P,H 和 S 表示）等待调度，要 求这三种车厢在输出端铁道上的排列次序为：硬座在前，软卧在中， 硬卧在后。试利用输出受限的双端队列对这 n 节车厢进行调度，编写 算法输出调度的操作序列：分别以字符?E?和?D?表示对双端队列的头 端进行入队列和出队列的操作；以字符 A 表示对双端队列的尾端进 行入队列的操作。 解： int main() { ElemT DQ InitDQueue(dq,20); char ch[20];126cout&&&请输入待调度的车厢字符序列(仅限 PHS)：&; cin&& int i=0; while(ch[i]){ if(ch[i]=='P') cout&&ch[i]; if(ch[i]=='S') EnDQueue(dq,ch[i],0);// 从队头入队 if(ch[i]=='H') EnDQueue(dq,ch[i],1);// 从队尾入队 i++; } while(dq.front!=dq.rear||dq.tag){ DeDQueue(dq,e); cout&&e; } cout&& return 0; }127第4章 串 4.1 解：空格串是指一个或多个空格字符(ASCII 码为 20H)组成的串， 而空串中没有任何字符。 4.2 解：串赋值(StrAssign)、串比较(StrCompare)、求串长(StrLength)、 串连接(Concat)、 求子串(SubString)这五种基本操作构成串类型的最小 操作子集。 4.6 解： s1=SubString(s,3,1) s2=SubString(s,6,1) Replace(s,s1,s2) Concat(s3,s,s1) Concat(t,SubString(s3,1,5),SubString(s3,7,2)) 算法设计题： // Filename: String.h #include &stdlib.h& #include &string.h& #define MaxSize 128 class String{ char * public:128String(const String& ob); String(const char* init); String(); ~String(); void StrAssign(String t); int StrCompare(String t); int StrLength(); void Concat(String t); String SubString(int start,int len); void show(); }; String::String(const String& ob) { ch=new char[MaxSize+1]; if(!ch) exit(1); curlen=ob. strcpy(ch,ob.ch); } String::String(const char* init) { ch=new char[MaxSize+1]; if(!ch) exit(1);129curlen=strlen(init); strcpy(ch,init); } String::String() { ch=new char[MaxSize+1]; if(!ch) exit(1); curlen=0; ch[0]='\0'; } String::~String() { curlen=0; } void String::StrAssign(String t) { strcpy(ch,t.ch); curlen=t. } int String::StrCompare(String t) {130return strcmp(ch,t.ch); } int String::StrLength() { } void String::Concat(String t) { strcat(ch,t.ch); curlen=curlen+t. } String String::SubString(int start,int len) { S int i,j; if(start&=0 && start+len&=curlen && len&0){ temp.curlen= for(i=0,j=i&i++,j++) temp.ch[i]=ch[j]; temp.ch[len]='\0'; }131} void String::show() { cout&&ch&& } 4.10 解： void StrReverse(String& s) { S int i,j; j=s.StrLength(); for(i=j-1;i&=0;i--) t.Concat(s.SubString(i,1)); s.StrAssign(t); } 4.11 解：第 5 章 数组与广义表 5.1 解： (1) 6× 8× 6=288 Byte (2) LOC(5,7)=1000+(5× 8+7)× 6=1282 (3) LOC(1,4)=1000+(1× 8+4)× 6=1072132(4) LOC(4,7)=1000+(7× 6+4)× 6= 解： (1) LOC(0,0,0,0)=100 (2) LOC(1,1,1,1)=100+(1× 3× 5× 8 + 1× 5× 8 + 1× 8 + 1)× 4=776 (3) LOC(3,1,2,5)=100+(3× 3× 5× 8 + 1× 5× 8 + 2× 8 + 5)× 4=1784 (4) LOC(8,2,4,7)=100+(8× 3× 5× 8 + 2× 5× 8 + 4× 8 + 7)× 4= 解： (0,0,0,0) (1,0,0,0) (0,1,0,0) (1,1,0,0) (0,0,1,0) (1,0,1,0) (0,1,1,0) (1,1,1,0) (0,0,2,0) (1,0,2,0) (0,1,2,0) (1,1,2,0) (0,0,0,1) (1,0,0,1) (0,1,0,1) (1,1,0,1) (0,0,1,1) (1,0,1,1) (0,1,1,1) (1,1,1,1) (0,0,2,1) (1,0,2,1) (0,1,2,1) (1,1,2,1) (0,0,0,2) (1,0,0,2) (0,1,0,2) (1,1,0,2) (0,0,1,2) (1,0,1,2) (0,1,1,2) (1,1,1,2) (0,0,2,2) (1,0,2,2) (0,1,2,2) (1,1,2,2) 5.4 解： k ?a (a ? 1) ?b 2其中，a=Max(i,j)，b=Min(i,j) 5.5 解： k ? ni ? (n ? j) ?1 1 f 1 (i) ? (n ? )i ? i 2 2 2 i(i ? 1) ?1 ( i ? 1， j ? 1，i ? j) 2f ( j) ? jc ? ?(n ? 1)5.6 解：u=i-j+1v=j-1 ( i ? j ? 1)5.7 解：(1) k=2(i-1)+j-1(2) i=(k+1) DIV 3 + 1 ( 0 ? k ? 3n ? 1 ) j=k+1-2(k DIV 3) 5.8 解：i 为奇数时，k=i+j-2 j 为偶数时，k=i+j-1133k=2(i DIV 2)+j-1 5.9 解： 设稀疏矩阵为 n 行 n 列， 其中的非零元为 m 个， m 远小于 n 2 。 从时间上来说， 采用二维数组存储稀疏矩阵需要 n 2 -1 次加法运算， 而 用三元组只需 m-1 次加法运算。 从空间上来说， 用二维数组需要 n 2 个 基本存储单元， 而三元组需要 m 个基本存储单元外加 2m 个整型存储 单元。由于 n 2 远远大于 m，故实际存储空间也较大。 5.10 解： (1) GetHead【(p,h,w)】= p (2) GetTail【(b,k,p,h)】= (k,p,h) (3) GetHead【((a,b),(c,d))】= (a,b) (4) GetTail【((a,b),(c,d))】= ((c,d)) (5) GetHead【GetTail【((a,b),(c,d))】 】= GetHead【((c,d))】= (c,d) (6) GetTail【GetHead【((a,b),(c,d))】 】= GetTail【(a,b)】= (b) (7) GetHead【GetTail【GetHead【((a,b),(c,d))】 】 】= GetHead【(b)】 =b (8) GetTail【GetHead【GetTail【((a,b),(c,d))】 】 】= GetTail【(c,d)】 = (d) 5.11 解： (1) GetHead【GetTail【GetTail【L1】 】 】 (2) GetHead【GetHead【GetTail【L2】 】 】 (3) GetHead【GetHead【GetTail【GetTail【GetHead【L3】 】 】 】 】 (4) GetHead【GetHead【GetHead【GetTail【GetTail【L4】 】 】 】 】134(5) GetHead【GetHead【GetTail【GetTail【L5】 】 】 】 (6) GetHead【GetTail【GetHead【L6】 】 】 (7) GetHead【GetHead【GetTail【GetHead【GetTail【L7】 】 】 】 】 5.12 解：5.13 解： (1) List=((x,(y)),(((())),(()),(z))) (2) List=(((a,b,()),()),(a,(b)),()) 5.14 解： s(n) ? s(n ? 1) ? a n ? s(n ? 1) ? a1 ? (n ? 1)d (n&=1) ElemType s(int i) { if(i&1) return s(i-1)+a1+(i-1)*d; else return a1; }1355.16 解： add(a, b) ? ? 5.17 解：? a ?add(? ? a,? ? b)b?0 b?0int Max(SqList &L,int k) { if(k&L.length-1) if(L.elem[k]&Max(L,k+1)) return Max(L,k+1); else return L.elem[k]; else return L.elem[k]; } int Min(SqList &L,int k) { if(k&L.length-1) if(L.elem[k]&Min(L,k+1)) return Min(L,k+1); else return L.elem[k]; else return L.elem[k]; }136int Sum(SqList &L,int k) { if(k==0) return L.elem[0]; else return L.elem[k]+Sum(a,k-1); } int Product(SqList &L,int k) { if(k==0) return L.elem[0]; else return L.elem[k]*Sum(a,k-1); } double Avg(SqList &L,int k) { if(k==0) return L.elem[0]; else return (Avg(a,k-1)*k+L.elem[k])/(k+1); } 5.18 解：算法的基本思想是将数组分成 k 组，将第一组与第二组进137行两两交换， 再将第一组与第三组进行两两交换， ...， 总共需进行 n-k 次交换。注意最后一组可能出现不足 k 个元素的情况，此时最后一组 为剩余元素加第一组的前几个元素共 k 个构成最后一组。 void RRMove(ElemType A[],int k,int n) { ElemT int i=0,j,p; while(i&n-k){ p=i/k+1; for(j=0;j&k;j++){ e=A[j]; A[j]=A[(p*k+j)%n]; A[(p*k+j)%n]=e; i++; } } } 5.19 解： #include &iostream.h& #define RS 4 #define CS 4138typedef int ElemT typedef struct{ ElemT int i,j; int F }NodeTvoid Initialize(NodeType a[RS][CS],ElemType A[RS][CS]); void SaddlePoint(NodeType a[RS][CS]); ElemType RowMin(NodeType a[RS][CS],int k); ElemType ColMax(NodeType a[RS][CS],int k); void Show(NodeType a[RS][CS]);int main() { ElemType A[RS][CS]={ {2,1,3,4}, {1,3,1,2}, {2,7,1,3}, {3,2,4,1} }; NodeType a[RS][CS];139Initialize(a,A); SaddlePoint(a); Show(a); return 0; }void Initialize(NodeType a[RS][CS],ElemType A[RS][CS]) { int i,j; for(i=0;i&RS;i++){ for(j=0;j&CS;j++){ a[i][j].e=A[i][j]; a[i][j].i=i; a[i][j].j=j; a[i][j].Flags=0; } } }void SaddlePoint(NodeType a[RS][CS]) { int i,j;140ElemType x,y; for(i=0;i&RS;i++){ x=RowMin(a,i); for(j=0;j&CS;j++){ y=ColMax(a,j); if(a[i][j].e==x&&a[i][j].e==y) a[i][j].Flags=1; } } }ElemType RowMin(NodeType a[RS][CS],int k) { ElemT x=a[k][0].e; for(i=1;i&CS;i++) if(x&a[k][i].e){ x=a[k][i].e; } }141ElemType ColMax(NodeType a[RS][CS],int k) { ElemT x=a[0][k].e; for(i=1;i&RS;i++) if(x&a[i][k].e){ x=a[i][k].e; } }void Show(NodeType a[RS][CS]) { for(int i=0;i&RS;i++) for(int j=0;j&CS;j++) if(a[i][j].Flags) cout&&i&&& &&&j&&& is a saddle point&&& } 5.21 解： typedef int ElemT142class Triple{ public: ElemTTriple(){} virtual ~Triple(){} BOOL operator&(Triple b); BOOL operator==(Triple b); };BOOL Triple::operator&(Triple b) { if(row&b.row) return TRUE; if(row==b.row&&col&b.col) return TRUE; return FALSE; } BOOL Triple::operator==(Triple b) { if(row==b.row && col==b.col) return TRUE;143else return FALSE; }class CSparseMat { public: CSparseMat(){} virtual ~CSparseMat(){} CSparseMat(int r,int c,int n); CSparseMat operator+(CSparseMat B); void ShowSparse(CDC* pDC);Triple *m_ // 指向非零元的指针 int m_nC int m_nR int m_nT }; // 矩阵列数 // 矩阵行数 // 非零元个数CSparseMat::CSparseMat(int r, int c, int n) { m_nRow=r;144m_nCol=c; m_nTrs=n; m_pt=new Triple[m_nTrs];// 输入矩阵的所有三元组 for(i=0;i&m_nTi++){ CInputDlg dlg1; if(dlg1.DoModal()==IDOK){ m_pt[i].row=dlg1.m_nR m_pt[i].col=dlg1.m_nC m_pt[i].e=dlg1.m_nE } } }void CSparseMat::ShowSparse(CDC *pDC) { char str[10]; int k=0; for(int i=0;i&m_nRi++){ for(int j=0;j&m_nCj++){145if(m_pt[k].row==i && m_pt[k].col==j){ itoa(m_pt[k].e,str,10); k++; } else itoa(0,str,10); pDC-&TextOut(0+j*20,0+i*20,str,strlen(str)); } } }// 矩阵相加的运算符重载函数 CSparseMat CSparseMat::operator+(CSparseMat B) { CSparseMat temp(m_nRow,m_nCol,0); if(m_nRow!=B.m_nRow || m_nCol!=B.m_nCol)temp.m_pt=new Triple[m_nTrs+B.m_nTrs]; if(!temp.m_pt) temp.m_nTrs=m_nTrs+B.m_nTint i=0;146int j=0; int k=0; while(i&m_nTrs && j&B.m_nTrs){ if(m_pt[i]&B.m_pt[j]){ temp.m_pt[k].row=m_pt[i]. temp.m_pt[k].col=m_pt[i]. temp.m_pt[k].e=m_pt[i].e; i++; } else{ if(m_pt[i]==B.m_pt[j]){ temp.m_pt[k].row=m_pt[i]. temp.m_pt[k].col=m_pt[i]. temp.m_pt[k].e=m_pt[i].e+B.m_pt[j].e; i++; } else{ temp.m_pt[k].row=B.m_pt[j]. temp.m_pt[k].col=B.m_pt[j]. temp.m_pt[k].e=B.m_pt[j].e; j++; }147j++;} k++; } while(i&m_nTrs){ temp.m_pt[k].row=m_pt[i]. temp.m_pt[k].col=m_pt[i]. temp.m_pt[k].e=m_pt[i].e; i++; k++; } while(j&B.m_nTrs){ temp.m_pt[k].row=B.m_pt[j]. temp.m_pt[k].col=B.m_pt[j]. temp.m_pt[k].e=B.m_pt[j].e; j++; k++; } temp.m_nTrs=k; } 5.23 解： #include&iostream.h&148#include&stdlib.h& #define Max 128typedef int ElemT typedef struct{ ElemT }Tclass CSparseMat { public: CSparseMat(){} CSparseMat(int r,int c,int n); virtual ~CSparseMat(){} void ShowSparse(int i,int j);Twin* m_ // 指向非零元的指针 int rpos[Max]; int m_nC int m_nR int m_nT // 矩阵列数 // 矩阵行数 // 非零元个数149};CSparseMat::CSparseMat(int r, int c, int n) { m_nRow=r; m_nCol=c; m_nTws=n; m_pt=new Twin[m_nTws]; if(!m_pt)// 输入矩阵的所有二元组 for(i=0;i&m_nTi++){ cout&&&请输入非零元二元组的列标和值：&; cin&&m_pt[i].col&&m_pt[i].e; } for(i=0;i&m_nRi++){ cout&&&请输入每行第一个非零元在二元组中的序号(没有输入 -1)：&; cin&&rpos[i]; // 该行没有非零元输入-1 } }150void CSparseMat::ShowSparse(int i,int j) { if(i&m_nRow||j&m_nCol)ElemType x=0; int s,d; if(i==m_nRow){ s=rpos[i]; d=m_nT } else{ s=rpos[i]; int m=1; d=rpos[i+m]; while(d&0){ if(i+m&m_nRow){ m++; d=rpos[i+m]; } else d=m_nT151} } if(s&=0){ int k=s; while(k&d){ if(m_pt[k].col==j) x=m_pt[k].e; k++; } } cout&&x&& }int main() { CSparseMat A(3,3,5); A.ShowSparse(2,1); return 0; } 5.26 解： typedef int ElemT typedef struct OLNode{152
ElemT struct OLNode *right,* }OLNode,*OLclass CCrossListMat { public: OLink *RHead,*CH // 行与列指针向量的头指针 int m_nC int m_nR int m_nN public: CCrossListMat(){} CCrossListMat(int r,int c,int n); virtual ~CCrossListMat(){} void ShowMat(int i,int j); }; // 矩阵列数 // 矩阵行数 // 非零元个数CCrossListMat::CCrossListMat(int r, int c, int n) {153m_nRow=r; m_nCol=c; m_nNum=n;RHead=new OLink[m_nRow]; if(!RHead) exit(-2); CHead=new OLink[m_nCol]; if(!CHead) exit(-2); for(i=0;i&m_nRi++) RHead[i]=NULL; for(i=0;i&m_nCi++) CHead[i]=NULL;OLink p,q, for(i=0;i&m_nNi++){ p=new OLN if(!p) exit(-2); cout&&&请输入非零元的行标、列标和值：&; cin&&p-&row&&p-&col&&p-&e; q=RHead[p-&row]; if(!q){154RHead[p-&row]=p; p-&right=NULL; } else{ qf=q; while(q && q-&col&p-&col){ qf=q; q=q-& } p-&right=qf-& qf-&right=p; } q=CHead[p-&col]; if(!q){ CHead[p-&col]=p; p-&down=NULL; } else{ qf=q; while(q && q-&row&p-&row){ qf=q; q=q-&155} p-&down=qf-& qf-&down=p; } } }void CCrossListMat::ShowMat(int i,int j) { ElemType x=0; OL p=RHead[i]; while(p && p-&col!=j) p=p-& if(p) x=p-&e; cout&&x&& } 5.27 解： #include&iostream.h& #include&stdlib.h&156typedef int ElemT typedef struct OLNode{ ElemT struct OLNode *right,* }OLNode,*OLclass CCrossListMat { public: OLink *RHead,*CH // 行与列指针向量的头指针 int m_nC int m_nR int m_nN public: CCrossListMat(){} virtual ~CCrossListMat(){} CCrossListMat(int r,int c,int n); void Add(CCrossListMat B); void ShowMat(); };157// 矩阵列数 // 矩阵行数 // 非零元个数CCrossListMat::CCrossListMat(int r, int c, int n) { m_nRow=r; m_nCol=c; m_nNum=n;RHead=new OLink[m_nRow]; if(!RHead) exit(-2); CHead=new OLink[m_nCol]; if(!CHead) exit(-2); for(i=0;i&m_nRi++) RHead[i]=NULL; for(i=0;i&m_nCi++) CHead[i]=NULL;OLink p,q, for(i=0;i&m_nNi++){ p=new