耿国华数据结构课后习题答案.pdf

《耿国华数据结构课后习题答案.pdf》由会员分享，可在线阅读，更多相关《耿国华数据结构课后习题答案.pdf（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第 1 1 章章绪绪 论论2.(1)(2)(3)3.（1）A（2）C（3）C5.计算下列程序中 x=x+1 的语句频度for(i=1;i=n;i+)for(j=1;j=i;j+)for(k=1;k=j;k+)x=x+1;【解答】x=x+1 的语句频度为：T(n)=1+(1+2)+（1+2+3）+（1+2+n）=n(n+1)(n+2)/66.编写算法，求 一元多项式 pn(x)=a0+a1x+a2x2+.+anxn的值 pn(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为ai(i=0,1,n)、x 和 n,

2、输出为 Pn(x0)。算法的输入和输出采用下列方法（1）通过参数表中的参数显式传递（2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。【解答】（1）通过参数表中的参数显式传递优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。（2）通过全局变量隐式传递优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗缺点：函数通用性降低，移植性差算法如下：通过全局变量隐式传递参数PolyValue()int i,n;float x,a,p;printf(“nn=”);sc

3、anf(“%f”,&n);printf(“nx=”);scanf(“%f”,&x);for(i=0;in;i+)scanf(“%f”,&ai);/*执行次数：n 次*/p=a0;for(i=1;i=n;i+)p=p+ai*x;/*执行次数：n 次*/x=x*x;printf(“%f”,p);算法的时间复杂度：T(n)=O(n)通过参数表中的参数显式传递floatPolyValue(floata,floatx,intn)float p,s;int i;p=x;s=a0;for(i=1;inext=S;B P-next=P-next-next;C P-next=S-next;D S-next=P-

4、next;E S-next=L;F S-next=NULL;G Q=P;H while(P-next!=Q)P=P-next;I while(P-next!=NULL)P=P-next;J P=Q;K P=L;L L=S;M L=P;(3)D(4)D(5)D(6)A7 试分别以不同的存储结构实现单线表的就地逆置算法，即在原表的存储空间将线性表（a1,a2,an）逆置为(an,an-1,a1)。【解答】（1）用一维数组作为存储结构void invert(SeqList*L,int*num)int j;ElemType tmp;for(j=0;jnext=NULL)return;/*链表为空*/p

5、=L-next;q=p-next;p-next=NULL;/*摘下第一个结点，生成初始逆置表*/while(q!=NULL)/*从第二个结点起依次头插入当前逆置表*/r=q-next;q-next=L-next;L-next=q;q=r;11将 线 性 表A=(a1,a2,am),B=(b1,b2,bn)合 并 成 线 性 表C,C=(a1,b1,am,bm,bm+1,.bn)当 mn 时,线性表 A、B、C 以单链表作为存储结构，且C 表利用 A 表和 B 表中的结点空间构成。注意：单链表的长度值m 和 n 均未显式存储。【解答】算法如下：LinkList merge(LinkList A,

6、LinkList B,LinkList C)Node*pa,*qa,*pb,*qb,*p;pa=A-next;/*pa 表示 A 的当前结点*/pb=B-next;p=A;/*利用 p 来指向新连接的表的表尾，初始值指向表A 的头结点*/while(pa!=NULL&pb!=NULL)/*利用尾插法建立连接之后的链表*/qa=pa-next;qb=qb-next;p-next=pa;/*交替选择表 A 和表 B 中的结点连接到新链表中；*/p=pa;p-next=pb;p=pb;pa=qa;pb=qb;if(pa!=NULL)p-next=pa;/*A 的长度大于 B 的长度*/if(pb!=

7、NULL)p-next=pb;/*B 的长度大于 A 的长度*/C=A;Return(C);实习题实习题约瑟夫环问题约瑟夫问题的一种描述为：编号 1,2,n的 n 个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个报数上限值m,从第一个人开始顺时针自 1 开始顺序报数，报到m 时停止报数。报 m 的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开始重新从1 报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。例如m的初值为20；n=7，7个人的密码依次是：3,1,7,2

8、,4,8,4,出列顺序为6,1,4,7,2,3,5。【解答】算法如下：typedef struct Nodeint password;int num;struct Node*next;Node,*Linklist;void Josephus()Linklist L;Node*p,*r,*q;int m,n,C,j;L=(Node*)malloc(sizeof(Node);/*初始化单向循环链表*/if(L=NULL)printf(n 链表申请不到空间!);return;L-next=NULL;r=L;printf(请输入数据 n 的值(n0):);scanf(%d,&n);for(j=1;jp

9、assword=C;p-num=j;r-next=p;r=p;r-next=L-next;printf(请输入第一个报数上限值m(m0):);scanf(%d,&m);printf(*n);printf(出列的顺序为:n);q=L;p=L-next;while(n!=1)/*计算出列的顺序*/j=1;while(jnext;j+;printf(%d-,p-num);m=p-password;/*获得新密码*/n-;q-next=p-next;/*p 出列*/r=p;p=p-next;free(r);printf(%dn,p-num);第 3 章 限定性线性表 栈和队列第三章答案1 按 3.1(

10、b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：（1）如进站的车厢序列为 123，则可能得到的出站车厢序列是什么？（2）如进站的车厢序列为 123456，能否得到435612 和 135426 的出站序列，并说明原因（即写出以“S”表示进栈、“X”表示出栈的栈序列操作）。【解答】（1）可能得到的出站车厢序列是：123、132、213、231、321。(2)不能得到 435612 的出站序列。因为有 S(1)S(2)S(3)S(4)X(4)X(3)S(5)X(5)S(6)S(6)，此时按照“后进先出”的原则，出栈的顺序必须为 X(2)X(1)。能得到 135426 的出站序列。因为有

11、S(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1)。3 给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？【解答】（1）顺序栈（top 用来存放栈顶元素的下标）判断栈 S 空：如果 S-top=-1 表示栈空。判断栈 S 满：如果 S-top=Stack_Size-1表示栈满。(2)链栈（top 为栈顶指针，指向当前栈顶元素前面的头结点）判断栈空：如果 top-next=NULL 表示栈空。判断栈满：当系统没有可用空间时，申请不到空间存放要进栈的元素，此时栈满。4 照四则运算加、减、乘、除和幂运算的优先惯例，画出对下列表达式求值时操作

12、数栈和运算符栈的变化过程：A-B*C/D+EF【解答】5 写一个算法，判断依次读入的一个以为结束符的字母序列，是否形如序列1&序列 2的字符序列。序列 1 和序列 2 中都不含&，且序列 2 是序列 1 的逆序列。例如，a+b&b+a是属于该模式的字符序列，而1+3&3-1则不是。【解答】算法如下：intIsHuiWen()Stack*S;Charch,temp;InitStack(&S);Printf(“n 请输入字符序列：”);Ch=getchar();While(ch!=&)/*序列 1 入栈*/Push(&S,ch);ch=getchar();do/*判断序列 2 是否是序列 1 的逆

13、序列*/ch=getchar();Pop(&S,&temp);if(ch!=temp)/*序列 2 不是序列 1 的逆序列*/return(FALSE);printf(“nNO”);while(ch!=&!IsEmpty(&S)if(ch=&IsEmpty(&S)return(TRUE);printf(“nYES”);/*序列 2 是序列 1 的逆序列*/elsereturn(FALSE);printf(“nNO”);/*IsHuiWen()*/8要求循环队列不损失一个空间全部都能得到利用，设置一个标志tag,以 tag 为 0 或 1 来区分头尾指针相同时的队列状态的空与满，请编写与此相应的

14、入队与出队算法。【解答】入队算法：intEnterQueue(SeqQueue*Q,QueueElementTypex)/*将元素 x 入队*/if(Q-front=Q-front&tag=1)/*队满*/return(FALSE);if(Q-front=Q-front&tag=0)/*x 入队前队空，x 入队后重新设置标志*/tag=1;Q-elememtQ-rear=x;Q-rear=(Q-rear+1)%MAXSIZE;/*设置队尾指针*/Return(TRUE);出队算法：intDeleteQueue(SeqQueue*Q,QueueElementType*x)/*删除队头元素，用 x

15、 返回其值*/if(Q-front=Q-rear&tag=0)/*队空*/return(FALSE);*x=Q-elementQ-front;Q-front=(Q-front+1)%MAXSIZE;/*重新设置队头指针*/if(Q-front=Q-rear)tag=0;/*队头元素出队后队列为空，重新设置标志域*/Return(TUUE);第第4 4章章 串串第四章答案1 设 s=I AM A STUDENT，t=GOOD，q=WORKER。给出下列操作的结果：【解答】StrLength(s)=14;SubString(sub1,s,1,7)sub1=I AM A;SubString(sub2

16、,s,7,1)sub2=;StrIndex(s,4,A)=6;StrReplace(s,STUDENT,q);s=I AM A WORKER;StrCat(StrCat(sub1,t),StrCat(sub2,q)sub1=I AM A GOOD WORKER。2 编写算法，实现串的基本操作StrReplace(S,T,V)。【解答】算法如下：intstrReplace(SString S,SString T,SString V)/*用串 V 替换 S 中的所有子串 T*/intpos,i;pos=strIndex(S,1,T);/*求 S 中子串 T 第一次出现的位置*/if(pos=0)r

17、eturn(0);while(pos!=0)/*用串 V 替换 S 中的所有子串 T*/switch(T.len-V.len)case0:/*串 T 的长度等于串 V 的长度*/for(i=0;ichpos+i=V.chi;case0:/*串 T 的长度大于串 V 的长度*/for(i=pos+t.ien;ilen;i-)/*将 S 中子串 T 后的所有字符S-chi-t.len+v.len=S-chi;前移 T.len-V.len个位置*/for(i=0;ichpos+i=V.chi;S-len=S-len-T.len+V.len;caselen-T.len+V.len)len-T.len+

18、V.len;i=pos+T.len;i-)S-chi=S-chi-T.len+V.len;for(i=0;ichpos+i=V.chi;S-len=S-len-T.len+V.len;else/*替换后串长MAXLEN,但串 V 可以全部替换*/if(pos+V.len=pos+T.len;i-)S-chi=s-chi-T.len+V.lenfor(i=0;ichpos+i=V.chi;S-len=MAXLEN;else/*串 V 的部分字符要舍弃*/for(i=0;ichi+pos=V.chi;S-len=MAXLEN;/*switch()*/pos=StrIndex(S,pos+V.len

19、,T);/*求 S 中下一个子串 T 的位置*/*while()*/return(1);/*StrReplace()*/第五章第五章数组和广义表数组和广义表第五章答案1.假设有 6 行 8 列的二维数组 A，每个元素占用 6 个字节，存储器按字节编址。已知 A 的基地址为 1000，计算：（1）数组 A 共占用多少字节；（288）（2）数组 A 的最后一个元素的地址；（1282）（3）按行存储时，元素 A36 的地址；（1126）（4）按列存储时，元素 A36 的地址；（1192）4.设有三对角矩阵 Ann,将其三条对角线上的元素逐行的存于数组B1.3n-2中，使得Bk=aij，求：（1）用

20、i,j 表示 k 的下标变换公式；（2）用 k 表示 i、j 的下标变换公式。【解答】（1）k=2(i-1)+j(2)i=k/3+1,j=k/3+k%3（取整，%取余）5.在稀疏矩阵的快速转置算法5.2 中，将计算 positioncol的方法稍加改动，使算法只占用一个辅助向量空间。【解答】算法（一）FastTransposeTSMatrix(TSMartrixA,TSMatrix*B)/*把矩阵 A 转置到 B 所指向的矩阵中去，矩阵用三元组表表示*/int col,t,p,q;int positionMAXSIZE;B-len=A.len;B-n=A.m;B-m=A.n;if(B-len0

21、)position1=1;for(t=1;t=A.len;t+)positionA.datat.col+1+;/*positioncol存放第 col-1 列非零元素的个数,即利用 poscol来记录第 col-1 列中非零元素的个数*/*求 col 列中第一个非零元素在B.data 的位置，存放在 positioncol中*/for(col=2;col=A.n;col+)positioncol=positioncol+positioncol-1;for(p=1;pdataq.row=A.datap.col;B-dataq.col=A.datap.row;B-dataq.e=A.datap.e

22、;Positioncol+;算法(二)FastTransposeTSMatrix(TSMartrixA,TSMatrix*B)int col,t,p,q;int positionMAXSIZE;B-len=A.len;B-n=A.m;B-m=A.n;if(B-len0)for(col=1;col=A.n;col+)positioncol=0;for(t=1;t0;col-)t=t-positioncol;positioncol=t+1;for(p=1;pdataq.row=A.datap.col;B-dataq.col=A.datap.row;B-dataq.e=A.datap.e;Posit

23、ioncol+;8.画出下面广义表的两种存储结构图示：(a),b),(),d),(e,f)【解答】第一种存储结构第二种存储结构第二种存储结构9.求下列广义表运算的结果：（1）HEAD(a,b),(c,d);(a,b)（2）TAIL(a,b),(c,d);(c,d)（3）TAILHEAD(a,b),(c,d);(b)（4）HEADTAILHEAD(a,b),(c,d);b（5）TAILHEADTAIL(a,b),(c,d);(d)第六章第六章答案6 1分别画出具有 3 个结点的树和 3 个结点的二叉树的所有不同形态。【解答】具有 3 个结点的树具有 3 个结点的二叉树6.3 已知一棵度为 k 的

24、树中有 n1个度为 1 的结点，n2个度为 2 的结点，nk个度为 k的结点，则该树中有多少个叶子结点？【解答】设树中结点总数为n,则 n=n0+n1+nk树中分支数目为 B,则 B=n1+2n2+3n3+knk因为除根结点外，每个结点均对应一个进入它的分支，所以有n=B+1即 n0+n1+nk=n1+2n2+3n3+knk+1由上式可得叶子结点数为：n0=n2+2n3+(k-1)nk+16.5 已知二叉树有 50 个叶子结点，则该二叉树的总结点数至少应有多少个？【解答】n0表示叶子结点数，n2表示度为 2 的结点数，则 n0=n2+1所以 n2=n01=49，当二叉树中没有度为1 的结点时，

25、总结点数 n=n0+n2=996.6 试分别找出满足以下条件的所有二叉树:(1)前序序列与中序序列相同;(2)中序序列与后序序列相同;(3)前序序列与后序序列相同。【解答】(1)前序与中序相同：空树或缺左子树的单支树；(2)中序与后序相同：空树或缺右子树的单支树；(3)前序与后序相同：空树或只有根结点的二叉树。6.9假设通讯的电文仅由 8 个字母组成，字母在电文中出现的频率分别为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10请为这 8 个字母设计哈夫曼编码。【解答】构造哈夫曼树如下：哈夫曼编码为：I1：11111I5：1100I2：11110I6：10I3：1

26、110 I7：01I4：1101 I8：006.11 画出如下图所示树对应的二叉树。【解答】6.16 分别写出算法，实现在中序线索二叉树T 中查找给定结点*p 在中序序列中的前驱与后继。在先序线索二叉树 T 中，查找给定结点*p 在先序序列中的后继。在后序线索二叉树 T中，查找给定结点*p 在后序序列中的前驱。（1）找结点的中序前驱结点BiTNode*InPre(BiTNode*p)/*在中序线索二叉树中查找p 的中序前驱结点，并用pre 指针返回结果*/if(p-Ltag=1)pre=p-LChild;/*直接利用线索*/else/*在 p 的左子树中查找“最右下端”结点*/for(q=p-

27、LChild;q-Rtag=0;q=q-RChild);pre=q;return(pre);（2）找结点的中序后继结点BiTNode*InSucc(BiTNode*p)/*在中序线索二叉树中查找p 的中序后继结点，并用succ 指针返回结果*/if(p-Rtag=1)succ=p-RChild;/*直接利用线索*/else/*在 p 的右子树中查找“最左下端”结点*/for(q=p-RChild;q-Ltag=0;q=q-LChild);succ=q;return(succ);(3)找结点的先序后继结点BiTNode*PreSucc(BiTNode*p)/*在先序线索二叉树中查找p 的先序后继

28、结点，并用succ 指针返回结果*/if(p-Ltag=0)succ=p-LChild;elsesucc=p-RChild;return(succ);(4)找结点的后序前驱结点BiTNode*SuccPre(BiTNode*p)/*在后序线索二叉树中查找p 的后序前驱结点，并用pre 指针返回结果*/if(p-Ltag=1)pre=p-LChild;elsepre=p-RChild;return(pre);6.20 已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。【解答】VoidPreOrder(BiTreeroot)/*先序遍历二叉树的非递归算法*/InitSt

29、ack(&S);p=root;while(p!=NULL|!IsEmpty(S)if(p!=NULL)Visit(p-data);push(&S,p);p=p-Lchild;elsePop(&S,&p);p=p-RChild;6.26 二叉树按照二叉链表方式存储，编写算法将二叉树左右子树进行交换。【解答】算法(一)Voidexchange(BiTreeroot)p=root;if(p-LChild!=NULL|p-RChild!=NULL)算法(二)Voidexchange(BiTreeroot)p=root;if(p-LChild!=NULL|p-RChild!=NULL)exchange(

30、p-LChild);exchange(p-RChild);temp=p-LChild;p-LChild=p-RChild;p-RChild=temp;第八章temp=p-LChild;p-LChild=p-RChild;p-RChild=temp;exchange(p-LChild);exchange(p-RChild);第八章答案81【解答】5ASLsucc=（1+2X2+3X4+4X3）/10=2.98.5【解答】(1)ASLSUCC=(1+2 X2+3 X3+4X3+5X2+6)/12=3.5(2)排序为：Apr,Aug,Dec,Feb,Jan,July,June,Mar,May,Nov

31、,Oct,Sep折半查找 ASLSUCC=(1+2 X2+3 X4+4X5)/12=37/128.12【解答】ASLSUCC=(1 X4+2 X3+6)/8=2ASLUNSUCC=(2+1+8+7+6+5+4+3+2+1+1)/11=40/11f87第一章绪论一、问答题1.什么是数据结构？2.叙述四类基本数据结构的名称与含义。3.叙述算法的定义与特性。4.叙述算法的时间复杂度。5.叙述数据类型的概念。6.叙述线性结构与非线性结构的差别。7.叙述面向对象程序设计语言的特点。8.在面向对象程序设计中，类的作用是什么？9.叙述参数传递的主要方式及特点。10.叙述抽象数据类型的概念。二、判断题（在各题

32、后填写“”或“”）1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（）2.算法就是程序。（）3.在高级语言（如 C 或 PASCAL）中，指针类型是原子类型。（）三、计算下列程序段中X=X+1 的语句频度for(i=1;i=n;i+)for(j=1;j=i;j+)for(k=1;k=j;k+)x=x+1;【解答】i=1 时：1=(1+1)1/2=(1+12)/2i=2 时：1+2=(1+2)2/2=(2+22)/2i=3 时：1+2+3=(1+3)3/2=(3+32)/2i=n 时：1+2+3+n=(1+n)n/2=(n+n2)/2x=x+1 的语句频度为：f(n)=(1+

33、2+3+n)+(12+22+32+n2)/2=(1+n)n/2+n(n+1)(2n+1)/6 /2=n(n+1)(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法复杂度：O(f(n)=O(n3)四、试编写算法，求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+anxn的值 Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1,n),x 和 n，输出为 Pn(x0)。通常算法的输入和输出可采用下列两种方式之一：（1）通过参数表中的参数显式传递。（2）通过全局变量隐式传递。试讨

34、论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出【解答】（1）通过参数表中的参数显式传递优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。（2）通过全局变量隐式传递优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗缺点：函数通用性降低，移植性差算法如下：通过全局变量隐式传递参数PolyValue()int i,n;float x,a,p;printf(“nn=”);scanf(“%f”,&n);printf(“nx=”);scanf(“%f”,&x);for(i=0;i

35、n;i+)scanf(“%f”,&ai);/*执行次数：n 次*/p=a0;for(i=1;i=n;i+)p=p+ai*x;/*执行次数：n 次*/x=x*x;printf(“%f”,p);算法的时间复杂度：T(n)=O(n)通过参数表中的参数显式传递floatPolyValue(floata,floatx,intn)float p,s;int i;p=x;s=a0;for(i=1;inext=S;（2）P-next=P-next-next;（3）P-next=S-next;（4）S-next=P-next;（5）S-next=L;（6）S-next=NULL;（7）Q=P;（8）while(

36、P-next!=Q)P=P-next;（9）while(P-next!=NULL)P=P-next;（10）P=Q;（11）P=L;（12）L=S;（13）L=P;2.4 已知线性表 L 递增有序。试写一算法，将 X 插入到 L 的适当位置上，以保持线性表 L的有序性。Status Insert_SqList(SqList&va,int x)/把 x 插入递增有序表 va 中if(va.length+1va.listsize)return ERROR;va.length+;for(i=va.length-1;va.elemix&i=0;i-)va.elemi+1=va.elemi;va.ele

37、mi+1=x;return103fOK;/Insert_SqList2.5 写一算法，从顺序表中删除自第i 个元素开始的 k 个元素。提示：注意检查 i 和 k 的合法性。（集体搬迁，“新房”、“旧房”）以待移动元素下标 m（“旧房号”）为中心，计算应移入位置（“新房号”）：for(m=i1+k;mlast;m+)Lelem mk =Lelem m;同时以待移动元素下标 m 和应移入位置 j 为中心：以应移入位置 j 为中心，计算待移动元素下标：2.6 已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink 且小于 maxk 的元素（若表中存

38、在这样的元素），分析你的算法的时间复杂度（注意：mink 和 maxk 是给定的两个参变量，它们的值为任意的整数）。Status Delete_Between(Linklist&L,int mink,int maxk)/删除元素递增排列的链表 L 中值大于mink 且小于 maxk 的所有元素p=L;while(p-next-datanext;/p是最后一个不大于 mink 的元素if(p-next)/如果还有比 mink 更大的元素q=p-next;while(q-datanext;/q是第一个不小于 maxk 的元素p-next=q;/Delete_Between2.7 试分别以不同的存储

39、结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1,a2.,an）逆置为（an,an-1,.,a1）。（1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前 elenum 个分量中。（2）以单链表作存储结构。方法 1:在原头结点后重新头插一遍方法 2:可设三个同步移动的指针p,q,r，将 q 的后继 r 改为 p2.8 假设两个按元素值递增有序排列的线性表 A 和 B，均以单链表作为存储结构，请编写算法，将 A 表和 B 表归并成一个按元素值递减有序的排列的线性表C，并要求利用原表（即A 表和 B 表的）结点空间存放表C.提示：参 P.28例 2-1voidmerge

40、(LinkListA;LinkListB;LinkList*C)pa=Anext;pb=Bnext;*C=A;(*C)next=NULL;while(pa!=NULL&pb!=NULL)if(padata data)smaller=pa;pa=panext;smallernext=(*C)next;/*头插法*/(*C)next=smaller;else smaller=pb;pb=pbnext;smallernext=(*C)next;(*C)next=smaller;while(pa!=NULL)smaller=pa;pa=panext;smallernext=(*C)next;(*C)n

41、ext=smaller;while(pb!=NULL)smaller=pb;pb=pbnext;smallernext=(*C)next;(*C)next=smaller;LinkListmerge(LinkListA;LinkListB)LinkListC；pa=Anext;pb=Bnext;C=A;Cnext=NULL;returnC;while(pa|pb)if(pa-datadata|!pb)pc=pa;q=pa-next;pa-next=pre;pa=q;/将 A 的元素插入新表elsepc=pb;q=pb-next;pb-next=pre;pb=q;/将 B 的元素插入新表pre=

42、pc;C=A;A-next=pc;/构造新表头/reverse_merge分析:本算法的思想是,按从小到大的顺序依次把A 和 B 的元素插入新表的头部pc 处,最后处理 A 或 B 的剩余元素.2.9 假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s 为指向链表某个结点的指针，试编写算法在链表中删除指针s 所指结点的前趋结点。提示：设指针 p 指向 s 结点的前趋的前趋，则p 与 s 有何关系？Status Delete_Pre(CiLNode*s)/删除单循环链表中结点 s 的直接前驱p=s;while(p-next-next!=s)p=p-next;/找到 s 的前驱的前

43、驱 pp-next=s;return OK;/Delete_Pre2.10 已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。Status LinkList_Divide(LinkList&L,CiList&A,CiList&B,CiList&C)/把单链表 L 的元素按类型分为三个循环链表.CiList 为带头结点的单循环链表类型.s=L-next;A=(CiList*)malloc(sizeof(CiLNode);p=A;

44、B=(CiList*)malloc(sizeof(CiLNode);q=B;C=(CiList*)malloc(sizeof(CiLNode);r=C;/建立头结点while(s)if(isalphabet(s-data)p-next=s;p=s;else if(isdigit(s-data)q-next=s;q=s;elser-next=s;r=s;/whilep-next=A;q-next=B;r-next=C;/完成循环链表/LinkList_Divide2.11 设线性表 A=(a1,a2,am)，B=(b1,b2,bn)，试写一个按下列规则合并A、B 为线性表 C 的算法，使得：C=

45、(a1,b1,am,bm,bm+1,bn)当 mn 时；或者C=(a1,b1,an,bn,an+1,am)当 mn 时。线性表 A、B、C 均以单链表作为存储?103f峁梗褻表利用 A 表和 B 表中的结点空间构成。注意：单链表的长度值m 和 n 均未显式存储。提示：voidmerge(LinkListA;LinkListB;LinkList*C)或：LinkListmerge(LinkListA;LinkListB)void merge1(LinkList&A,LinkList&B,LinkList&C)/把链表 A 和B 合并为C,A 和B 的元素间隔排列,且使用原存储空间p=A-next

46、;q=B-next;C=A;while(p&q)s=p-next;p-next=q;/将 B 的元素插入if(s)t=q-next;q-next=s;/如 A 非空,将 A 的元素插入p=s;q=t;/while/merge12.12 将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。提示：注明用头指针还是尾指针。void Divide_LinkedPoly(LinkedPoly&L,&A,&B)/把循环链表存储的稀疏多项式 L 拆成只含奇次项的 A 和只含偶次项的 Bp=L-next;A=(PolyNode

47、*)malloc(sizeof(PolyNode);B=(PolyNode*)malloc(sizeof(PolyNode);pa=A;pb=B;while(p!=L)if(p-data.exp!=2*(p-data.exp/2)pa-next=p;pa=p;elsepb-next=p;pb=p;p=p-next;/whilepa-next=A;pb-next=B;/Divide_LinkedPoly2.13 建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data 域存放一个二进制位。并在此链表上实现对二进制数加1 的运算。提示：可将低位放在前面。2.14 设多项式 P(

48、x)采用课本中所述链接方法存储。写一算法，对给定的x 值，求P(x)的值。提示：floatPolyValue(Polylistp;floatx)第三章栈和队列1.按图 3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：如进站的车厢序列为123，则可能得到的出站车厢序列是什么？如进站的车厢序列为 123456，能否得到435612 和 135426 的出站序列，并说明原因。（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。【解答】（1）可能得到的出站车厢序列是：123、132、213、231、321。(2)不能得到 435612 的出站序列。因为有 S(1)S(2)S(3

49、)S(4)X(4)X(3)S(5)X(5)S(6)S(6)，此时按照“后进先出”的原则，出栈的顺序必须为 X(2)X(1)。能得到 135426 的出站序列。因为有 S(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1)。2.设队列中有 A、B、C、D、E 这 5 个元素，其中队首元素为A。如果对这个队列重复执行下列 4 步操作：（1）输出队首元素；（2）把队首元素值插入到队尾；（3）删除队首元素；（4）再次删除队首元素。直到队列成为空队列为止，则是否可能得到输出序列：（1）A、C、E、C、C（2）A、C、E（3）A、C、E、C、C、C（4）A、C、E、C提示

50、：A、B、C、D、E（输出队首元素 A）A、B、C、D、E、A（把队首元素 A 插入到队尾）B、C、D、E、A（删除队首元素 A）C、D、E、A（再次删除队首元素B）C、D、E、A（输出队首元素 C）C、D、E、A、C（把队首元素 C 插入到队尾）D、E、A、C（删除队首元素 C）E、A、C（再次删除队首元素D）3.给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？4.按照四则运算加、减、乘、除和幂运算（）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：AB【解答】5.试写一个算法，判断依次读入的一个以为结束符的字母序列，是否为形如序列 1&序列