《数据结构-C语言描述》习题及答案-耿国华

第1章绪论习题ー、问答题.什么是数据结构?.四类基本数据结构的名称与含义。.算法的定义与特性。.算法的时间复杂度。.数据类型的概念。.线性结构与非线性结构的差别。.面向对象程序设计语言的特点。.在面向对象程序设计中,类的作用是什么?.参数传递的主要方式及特点。.抽象数据类型的概念。二、判断题.线性结构只能用顺序结构来存放,非线性结构只能用非顺序结构来存放。.算法就是程序。.在髙级语言(如C、或PASCAL)中,指针类型是原子类型。三、计算下列程序段中X=X+1的语句频度for(i=l;i<=n;i++)for(j=l;j<=i;j++)for(k=l;k<=j;k++)x=x+l;[提示]:i=l时:1=(1+1)X1/2=(1+12)/2i=2时:1+2=(1+2)X2/2=(2+2?)/2i=3时：1+2+3=(1+3)X3/2=(3+32)/2i=n时：1+2+3+ +n=(1+n)Xn/2=(n+n2)/2f(n)=[(1+2+3+……+n)+(I2+22+32+……+n2)]/2=[(1+n)n/2+n(n+l)(2n+l)/6]/2=n(n+l)(n+2)/6=n3/6+n2/2+n/3区分语句频度和算法复杂度:0(f(n))=0(n3)四、试编写算法求一元多项式Pn(x)=a<)+aix+a2x2+a3x3+…Mx"的值Pn(xo),并确定算法中的每ー语句的执行次数和整个算法的时间复杂度,要求时间复杂度尽可能的小,规定算法中不能使用求嘉函数。注意:本题中的输入出入=0,1,…,n),x和n,输出为Pn(xo).通常算法的输入和输出可采用下列两种方式之一:通过参数表中的参数显式传递;通过全局变量隐式传递。试讨论这两种方法的优缺点,并在本题算法中以你认为较好的ー种方式实现输入和输出。[提示]:floatPolyValue(floata[],floatx,intn){……}核心语句:P=l；(x的零次舞)s=0;i从0到n循环s=s+a[i]*p；P=P*x;或:P=x；(X的一次霧)s=a[0]:i从1到n循环s=s+a[i]*p;P=P*x;实习题设计实现抽象数据类型“有理数”。基本操作包括有理数的加法、减法、乘法、除法,以及求有理数的分子、分母。第一章答案3计算下列程序中x=x+l的语句频度for(i=l;iく=n;i++)for(j=l;jく=i;j++)for(k=l;k<=j;k++)x=x+l;【解答】X=x+1的语句频度为:T(n)=1+(1+2)+(1+2+3)+ + (1+2+ +n)=n(n+1)(n+2)/64试编写算法,求Pn(x)=ao+aix+a2x2+ +aH的值pn(x0),并确定算法中每ー语句的执行次数和整个算法的时间复杂度,要求时间复杂度尽可能小,规定算法中不能使用求裏函数。注意:本题中的输入为ai(i=0,1,…n)、x和n,输出为Pn(x0)〇算法的输入和输出采用下列方法(1)通过参数表中的参数显式传递(2)通过全局变量隐式传递。讨论两种方法的优缺点,并在算法中以你认为较好的ー种实现输入输出。【解答】(1)通过参数表中的参数显式传递优点:当没有调用函数时,不占用内存,调用结束后形参被释放,实参维持,函数通用性强,移置性强。缺点：形参须与实参对应,且返回值数量有限。(2)通过全局变量隐式传递优点:减少实参与形参的个数,从而减少内存空间以及传递数据时的时间消耗缺点:函数通用性降低,移植性差算法如下:通过全局变量隐式传递参数PolyValue(){inti,n;floatx,a[],p;printf("\nn=");scanf("%f",&n);printf("\nx=")；scanf(“％f”，&x);for(i=0;i<n;i++)scanf("%f”,&a[i]); /*执行次数:n次・/P=a[〇];for(i=l;iく=n;i++){p=p+a[i]*x; /*执行次数:n次・/x=x*x；}printf( ,p);)算法的时间复杂度:T(n)=O(n)通过参数表中的参数显式传递floatPolyValue(floata[],floatx,intn)(floatp,s;inti;P=x;s=a[0];for(i=l;i<=n;i++){s=s+a[i]*p; /*执行次数:n次・/P=P*x;}return(p);}算法的时间复杂度：T(n)=0(n)第2章线性表习题!描述以下三个概念的区别:头指针,头结点,首元素结点。填空：（1）在顺序表中插入或删除ー个元素,需要平均移动 一半元素,具体移动的元素个数与 插入或删除的位置一有关。（2）在顺序表中,逻辑上相邻的元素,其物理位置 相邻。在单链表中,逻辑上相邻的元素,其物理位置 ー相邻。（3）在带头结点的非空单链表中,头结点的存储位置由 一指示,首元素结点的存储位置由 指示,除首元素结点外,其它任一元素结点的存储位置由一其直接前趋的next域指示。已知L是无表头结点的单链表,且P结点既不是首元素结点,也不是尾元素结点。按要求从下列语句中选择合适的语句序列。a.在P结点后插入S结点的语句序列是: 在）、（点。b.在P结点前插入S结点的语句序列是:（7）、（11）、（8）、（4）、（1）。c,在表首插入S结点的语句序列是:（5）、（12）。d,在表尾插入S结点的语句序列是:（11）、（9）、（1）、（6）。供选择的语句有:P->next=S;P->next=P->next->next;P->next=S->next;S->next=P->next;S->next=L;S->next=NULL;Q=P;while（P->next!=Q）P=P->next;while(P->next!=NULL)P=P->next;P=Q;P=L;L=S;L=P;2.4已知线性表L递增有序。试写ー算法,将X插入到L的适当位置上,以保持线性表L的有序性。[提ホ]:voidinsert(SeqList*L;ElemTypex)<方法1>(1)找出应插入位置i,(2)移位,(3)……<方法2〉参P.2292.5写ー算法,从顺序表中删除自第i个元素开始的k个元素。[提示]:注意检查i和k的合法性。(集体搬迁,“新房”、“旧房”)く方法1》以待移动元素下标m(“旧房号”)为中心,计算应移入位置(“新房号”)：for(m=i—1+k;m<=L—>last;m++)L->elem[m-k]=L->elem[m];く方法2>同时以待移动元素下标m和应移入位置j为中心:く方法3》以应移入位置j为中心,计算待移动元素下标:

2.6已知线性表中的元素（整数）以值递增有序排列,并以单链表作存储结构。试写一高效算法,删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素）,分析你的算法的时间复杂度（注意:mink和maxk是给定的两个参变量,它们的值为任意的整数）。［提示］:注意检查mink和maxk的合法性:minkくmaxk不要一个ー个的删除（多次修改next域）。找到第一个应删结点的前驱pre找到最后ー个应删结点的后继s,边找边释放应删结点(3)pre(3)pre—>next=s;试分别以不同的存储结构实现线性表的就地逆置算法,即在原表的存储空间将线性表（a1,a2...,an）逆置为（a»,an,...,aj。以ー维数组作存储结构,设线性表存于a（l:arrsize）的前elenum个分量中。以单链表作存储结构。［方法1］:在原头结点后重新头插一遍［方法2］:可设三个同步移动的指针p,q,r,将q的后继r改为P假设两个按元素值递增有序排列的线性表A和B,均以单链表作为存储结构,请编写算法,将A表和B表归并成一个按元素值递减有序的排列的线性表C,并要求利用原表（即A表和B表的）结点空间存放表C.［提示］:参P.28例2-1く方法1〉voidmerge（LinkListA;LinkListB;LinkList*C）pa=A—>next;pb=B—>next;*C=A;(*C)—>next=NULL;while(pa!=NULL&&pb!=NULL){if(pa—>data<=pb—>data){smaller=pa;pa=pa—>next;smaller—>next=(*C)—>next; /・头插法・/(*C)—>next=smaller;}else{smaller=pb;pb=pb—>next;(*C)—>next=smaller;)while(pa!=NULL){smaller=pa;pa=pa—>next;smaller—>next=(*C)—>next;(*C)—>next=smaller;)while(pb!=NULL){smaller=pb;pb=pb—>next;smaller—>next=(*C)—>next;(*C)—>next=smaller;)<方法2〉LinkListmerge(LinkListA;LinkListB)LinkListC；pa=A->next;pb=B—>next;C=A;C—>next=NULL;returnC;2.9假设有一个循环链表的长度大于1,且表中既无头结点也无头指针。已知s为指向链表某个结点的指针,试编写算法在链表中删除指针s所指结点的前趋结点。［提示］:设指针P指向s结点的前趋的前趋,则p与s有何关系?2.10已知有单链表表示的线性表中含有三类字符的数据元素(如字母字符、数字字符和其它字符),试编写算法来构造三个以循环链表表示的线性表,使每个表中只含同一类的字符,且利用原表中的结点空间作为这三个表的结点空间,头结点可另辟空间。2.11设线性表A=(ai,a2, a.),B=(bbb2,•••,bn),试写ー个按下列规则合并A、B为线性表C的算法,使得:C=(abbb•••,a.,bB,b吁し•••,bj当mWn时;或者C=(abレ,…,へ,bn,a„+i,…，a.)当m>n时。线性表A、B、C均以单链表作为存储结构,且C表利用A表和B表中的结点空间构成。注意:单链表的长度值m和n均未显式存储。［提ホ］:voidmerge(LinkListA;LinkListB;LinkList*0或:LinkListmerge(LinkListA;LinkListB)2.12将一个用循环链表表示的稀疏多项式分解成两个多项式,使这两个多项式中各自仅含奇次项或偶次项,并要求利用原链表中的结点空间来构成这两个链表。［提示］:注明用头指针还是尾指针。2.13建立一个带头结点的线性链表,用以存放输入的二进制数,链表中每个结点的data域存放一个二进制位。并在此链表上实现对ニ进制数加1的运算。［提示］:可将低位放在前面。2.14设多项式P(x)采用课本中所述链接方法存储。写ー算法,对给定的x值,求P(x)的值。［提示］:floatPolyValue(Polylistp;floatx){ }实习题将若干城市的信息存入ー个带头结点的单链表,结点中的城市信息包括城市名、城市的位置坐标。要求：(1)给定一个城市名,返回其位置坐标;(2)给定一个位置坐标P和一个距离D,返回所有与P的距离小于等于D的城市。约瑟夫环问题。约瑟夫问题的ー种描述是:编号为1,2,…，n的n个人按顺时针方向围坐ー圈,每人持有一个密码（正整数）。ー开始任选ー个整数作为报数上限值叫从第一个人开始顺时针自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有的人全部出列为止。试设计ー个程序,求出出列顺序。利用单向循环链表作为存储结构模拟此过程,按照出列顺序打印出各人的编号。例如m的初值为20；n=7,7个人的密码依次是:3,1,7,2,4,8,4,出列的顺序为6,1,4,7,2,3,5〇第二章答案约瑟夫环问题约瑟夫问题的ー种描述为:编号1,2,•••,n的n个人按顺时针方向围坐ー圈,每个人持有一个密码（正整数）。ー开始任选ー个报数上限值叫从第一个人开始顺时针自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下ー个人开始重新从1报数,如此下去,直至所有的人全部出列为止。试设计ー个程序,求出出列顺序。利用单向循环链表作为存储结构模拟此过程,按照出列顺序打印出各人的编号。例如m的初值为20；n=7,7个人的密码依次是:3,1,7,2,4,8,4,出列顺序为6,1,4,7,2,3,5〇【解答】算法如下:typedefstructNodeintpassword;intnum;structNode*next;}Node,*Linklist;voidJosephus(){LinklistL;Node*p,*r,*q;intm,n,C,j;L=(Node*)malloc(sizeof(Node)); /*初始化单向循环链表・/if(L—NULL){printf("\n链表申请不到空间!”)；return;}L->next=NULL;r=L;printf("请输入数据n的值(n>0):");scanf("%d",&n);for(j=l;j〈=n;j++)/・建立链表・/{p=(Node*)malloc(sizeof(Node));if(p!=NULL)(printf("请输入第％d个人的密码:",j)；scanf("%d",&C);p->password=C;pー〉num=j;r->next=p;r-p;))r->next=Lー〉next;printf(〃请输入第一个报数上限值m(m〉0):〃)；scanf("%d",&m);printf(〃*****************************************\n〃),printf("出列的顺序为:\n");q=L;p=Lー〉next;while(n!=l)/・计算出列的顺序*/{j=l；while(j<m)/・计算当前出列的人选p*/{q=p;/*q为当前结点p的前驱结点・/p=pー〉next;j++；}printf,p->num);m=p->password;/・获得新密码・/n一;q->next=p->next; /*p出列*/r=p;p=p->next;free(r);)printf("%d\n”,p->num);}2.y试分别以不同的存储结构实现单线表的就地逆置算法,即在原表的存储空间将线性表(aba2,-,an)逆置为⑸,ス,…,aノ。【解答】(1)用ー维数组作为存储结构voidinvert(SeqList*L,int*num){intj;ElemTypetmp;for(j=0;j<=(*num-l)/2;j++){tmp=L[j];L[j]=L[*num-j-l];L[*num-j-l]=tmp;}}(2)用单链表作为存储结构voidinvert(LinkListL)Node*p,*q,*r;if(L->next==NULL)return; /・链表为空*/p=L->next;q=pー〉next;p->next=NULL; /・摘下第一个结点,生成初始逆置表・/while(q!=NULL) /・从第二个结点起依次头插入当前逆置表・/{r=q->next;qー〉next二L->next;Lー〉next=q;q=r;2.11将线性表A=(al,a2,……am),B=(bl,b2,……bn)合并成线性表C,C=(al,bl, am,bm,bm+1, bn) 当mく=n时,或C=(al,bl, an,bn,an+1, am)当m〉n时,线性表A、C以单链表作为存储结构,且C表利用A表和B表中的结点空间构成。注意:单链表的长度值m和n均未显式存储。【解答】算法如下:LinkList merge(LinkList A, LinkListB,LinkListC){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!=NULL) p->next=pb; /*B的长度大于A的长度・/C=A;Return(C);第3章限定性线性表ー栈和队列习题.按图3.1（b）所示铁道（两侧铁道均为单向行驶道）进行车厢调度,回答:（1）如进站的车厢序列为!23,则可能得到的出站车厢序列是什么?123、213、132、231、321（312）⑵如进站的车厢序列为!23456,能否得到435612和135426的出站序列,并说明原因。（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。SXSSXSSXXXSX或S1X1S2S3X3S4S5X5X4X2S6X6.设队列中有A、B、C、D、E这5个元素,其中队首元素为A。如果对这个队列重复执行下列4步操作:（1）输出队首元素;（2）把队首元素值插入到队尾;（3）删除队首元素;（4）再次删除队首元素。直到队列成为空队列为止,则是否可能得到输出序列:（1）A、C、E、C、C （2）A、C、EA、C、E、C、C、C （4）A、C、E、C［提示］: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）.给出栈的两种存储结构形式名称,在这两种栈的存储结构中如何判别栈空与栈满?.按照四则运算加、减、乘、除和嘉运算（t）优先关系的惯例,画出对下列算术表达式求值时操作数栈和运算符栈的变化过程:A—B*C/D+EtF.试写ー个算法,判断依次读入的ー个以@为结束符的字母序列,是否为形如‘序列1&序列2，模式的字符序列。其中序列1和序列2中都不含字符'&',且序列2是序列1的逆序列。例如,'a+b&b+a’是属该模式的字符序列,而’1+3&3—1’则不是。［提示］:(1)边读边入栈,直到&(2)边读边出栈边比较,直到…….假设表达式由单字母变量和双目四则运算算符构成。试写ー个算法,将一个通常书写形式(中缀)且书写正确的表达式转换为逆波兰式(后缀)。［提示］:例:中缀表达式:a+b 后缀表达式:ab+中缀表达式:a+bXc 后缀表达式:abcX+中缀表达式:a+bXc-d 后缀表达式：abcX+d-中缀表达式:a+bXc-d/e 后缀表达式：abcX+de/-中缀表达式:a+bX(c-d)-e/f 后缀表达式:abcd-X+ef/-・后缀表达式的计算过程:(简便)顺序扫描表达式,(1)如果是操作数,直接入栈;(2)如果是操作符op,则连续退栈两次,得操作数X,Y,计算XopY,并将结果入栈。•如何将中缀表达式转换为后缀表达式?顺序扫描中缀表达式,(1)如果是操作数,直接输出;(2)如果是操作符。P2,则与栈顶操作符。小比较:如果op，>0P1,则叩2入栈;如果。P2=0P1,则脱括号;如果0P2<0P1,则输出0P1；.假设以带头结点的循环链表表示队列,并且只设ー个指针指向队尾元素结点(注意不设头指针),试编写相应的队列初始化、入队列和出队列的算法。［提示］:参P.56P.70先画图.typedefLinkListCLQueue;intInitQueue(CLQueue*Q)intEnterQueue(CLQueueQ,QueueElementTypex)intDeleteQueue(CLQueueQ,QueueElementType*x).要求循环队列不损失一个空间全部都能得到利用,设置ー个标志域tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满,请编写与此结构相应的入队与出队算法。［提示］:初始状态:front==0,rear==O,tag==O队空条件:front==rear,tag==O队满条件:front==rear,tag==l其它状态:front!=rear,tag==0（或1、2）入队操作：••…（入队）if（front==rear）tag=l；（或直接tag=l）出队操作：••（出队）tag=0；［问题］:如何明确区分队空、队满、非空非满三种情况?9.简述以下算法的功能（其中栈和队列的元素类型均为int）：voidproc_l（StackS）{inti,n,A［255］;n=0;while(!EmptyStack(S)){n++;Pop(&S,&A[n]);}for(i=l;i<=n;i++)Push(&S,A[i]);)将栈S逆序。voidproc_2(StackS,inte){StackT;intd;InitStack(&T);while(!EmptyStack(S)){Pop(&S,&d);if(d!=e)Push(&T,d);)while(!EmptyStack(T)){Pop(&T,&d);Push(&S,d);))删除栈S中所有等于e的元素。voidproc_3(Queue*Q){StackS;intd;InitStack(&S);whiledEmptyQueue(*Q))DeleteQueue(Q,&d);Push(&S,d);}whiledEmptyStack(S)){Pop(&S,&d);EnterQueue(Q,d)})将队列Q逆序。实习题回文判断。称正读与反读都相同的字符序列为“回文’‘序列。试写ー个算法,判断依次读入的ー个以@为结束符的字母序歹!b是否为形如‘序列1&序列牙模式的字符序列。其中序列1和序列2中都不含字符且序列2是序列1的逆序列。例如,'a+b&b+a，是属该模式的字符序列,而’1+3&3—'1'则不是。停车场管理。设停车场是ー个可停放n辆车的狭长通道,且只有一个大门可供汽车进出。在停车场内,汽车按到达的先后次序,由北向南依次排列(假设大门在最南端)。若车场内已停满n辆车,则后来的汽车需在门外的便道上等候,当有车开走时,便道上的第一辆车即可开入。当停车场内某辆车要离开时,在它之后进入的车辆必须先退出车场为它让路,待该辆车开出大门后,其它车辆再按原次序返回车场。每辆车离开停车场时,应按其停留时间的长短交费（在便道上停留的时间不收费）。试编写程序,模拟上述管理过程。要求以顺序栈模拟停车场,以链队列模拟便道。从终端读入汽车到达或离去的数据,每组数据包括三项:①是“到达”还是“离去”；②汽车牌照号码;③'‘到达”或“离去”的时刻。与每组输入信息相应的输出信息为:如果是到达的车辆，则输出其在停车场中或便道上的位置;如果是离去的车辆,则输出其在停车场中停留的时间和应交的费用。（提示:需另设ー个栈,临时停放为让路而从车场退出的车。）车库暂时退车道 あ 便道商品货架管理。商品货架可以看成一个栈,栈顶商品的生产日期最早,栈底商品的生产日期最近。上货时,需要倒货架,以保证生产日期较近的商品在较下的位置。用队列和栈作为周转,实现上述管理过程。第三章答案3.1按3.1(b)所示铁道(两侧铁道均为单向行驶道)进行车厢调度,回答:(1)如进站的车厢序列为123,则可能得到的出站车厢序列是什么?(2)如进站的车厢序列为!23456,能否得到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的出站序列。因为有S(1)X(1)S(2)S(3)X(3)S(4)S(5)X(5)X(4)X(2)X(1)。3.3给出栈的两种存储结构形式名称,在这两种栈的存储结构中如何判别栈空与栈满?【解答】(1)顺序栈 (top用来存放栈顶元素的下标)判断栈S空:如果Sー＞top==T表示栈空。判断栈S满:如果S-＞top==Stack_Size-l表示栈满。(2)链栈(top为栈顶指针,指向三前栈顶元素前面的头结点)判断栈空:如果topー＞next==NULL表示栈空。判断栈满:当系统没有可用空间时,申请不到空间存放要进栈的元素,此时栈满。3. 4照四则运算加、减、乘、除和裏运算的优先惯例,画出对下列表达式求值时操作数栈和运算符栈的变化过程:A-B*C/D+EtF【解答】

'+'=OPTR；＜生成A-T(2)>运篁结果T(3)OPTR为空’+，'+'=OPTR；＜生成A-T(2)>运篁结果T(3)OPTR为空’+，进後运算结果T(4)T(3)运算结果T(5)右边界<OPTR；t'生成EtF右边界'#,vOPTR：+'生成T(3)+T(4)3. 5写ー个算法,判断依次读入的ー个以@为结束符的字母序列,是否形如‘序列1&序列2，的字符序列。序列1和序列2中都不含且序列2是序列1的逆序列。例如,'a+b&b+a’是属于该模式的字符序列,而’1+3&3T’则不是。【解答】算法如下:intIsHuiWen(){Stack*S;Charch,temp;InitStack(&S);Printf("\n请输入字符序列:")；Ch=getchar();While(ch!=&) /・序列1入栈・/{Push(&S,ch);ch=getchar();}do /・判断序列2是否是序列1的逆序列・/{ch=getchar();Pop(&S,&temp);if(ch!=temp) /・序列2不是序列1的逆序列・/{return(FALSE);printf(a\nN0");}}while(ch!&&!IsEmpty(&S))if(ch==@ &&IsEmpty(&S)){return(TRUE);printf("\nYES");} /*序列2是序列1的逆序列・/else{return(FALSE);printf("\nNO");}}/*IsHuiWen()*/3.8要求循环队列不损失一个空间全部都能得到利用,设置ー个标志tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满,请编写与此相应的入队与出队算法。【解答】入队算法:intEnterQueue(SeqQueue*Q,QueueElementTypex){/・将元素x入队・/if(Q->front==Qー>front&&tag==l)/・队满・/return(FALSE);if(Q-〉front==Qー〉front&&tag==0) /*x入队前队空,x入队后重新设置标志・/tag=l;Q->elememt[Q-〉rear]=x;Qー〉rear=(Q-〉rear+l)%MAXSlZE; /・设置队尾指针・/Return(TRUE);出队算法:intDeleteQueue(SeqQueue*Q,QueueElementType*x){/・删除队头元素,用x返回其值・/if(Q-〉front==Qー〉rear&&tag==0) /・队空・/return(FALSE);*x=Q-〉element[Q-〉front];Qー〉front=(Qー〉front+l)%MAXSlZE; /・重新设置队头指针・/if(Qー〉front==Qー〉rear)tag=0;/・队头元素出队后队列为空,重新设置标志域・/Return(TUUE);编写求解Hanoi问题的算法,并给出三个盘子搬动时的递归调用过程。

【解答】算法:voidhanoi(intn,charx,chary,charz){/・将塔座X上按直径由小到大且至上而下编号为1到n的n个圆盘按规则搬到塔座Z上,丫可用做辅助塔座・/if(n==1)move(x,1,z);else{Hanoi(n-l,x,z,y);move(x,n,z);Hanoi(n-l,y,x,z);Hanoi(2,A,C,B):Hanoi(2,A,C,B):Hanoi(1,A,B,C)Move(A->B)Hanoi(1,C,A,B)Move(A->C)Hanoi(2,B,A,C)Hanoi(1,B,C,A)Move(B->C)Hanoi(1,A,B,C)move(A->C) 1号搬到C2号搬到Bmove(C->B) 1号搬到B3号搬到Cmove(B->A) 1号搬到A2号搬到C

move(A->C) 1号搬到C第4章 串习题.设s='IAMASTUDENT),t='GOOD*,q='WORKER,〇给出下列操作的结果:StrLength(s); SubString(subl,s,1,7);SubString(sub2,s,7,1);StrIndex(s,fA',4);StrReplace(s,rSTUDENT*,q);StrCat(StrCat(subl,t),StrCat(sub2,q));［参考答案］StrLength(s)=14;subl=*IAMA_';sub2=* ;Strindex(s,*A',4)=6;StrReplace(s,'STUDENT',q)='IAMAWORKER';StrCat(StrCat(subl,t),StrCat(sub2,q))=*IAMAGOODWORKER';.编写算法,实现串的基本操作StrReplace(S,T,V)。.假设以块链结构表示串,块的大小为L且附设头结点。试编写算法,实现串的下列基本操作:StrAsign(S,chars)；StrCopy(S,T)；StrCompare(S,T)；StrLength(S)；StrCat(S,T)；SubString(Sub,S,pos,len)〇［说明］:用单链表实现。叙述以下每对术语的区别:空串和空格串;串变量和串常量;主串和子串;串变量的名字和串变量的值。已知:S="(xyz)*",T="(x+z)*y"〇试利用联接、求子串和置换等操作,将S转换为T.S和T是用结点大小为1的单链表存储的两个串,设计一个算法将串S中首次与T匹配的子串逆置。S是用结点大小为4的单链表存储的串,分别编写算法在第k个字符后插入串T,及从第k个字符删除len个字符。以下算法用定长顺序串:写下列算法:（1）将顺序串r中所有值为chi的字符换成ch2的字符。（2）将顺序串r中所有字符按照相反的次序仍存放在r中。<3）从顺序串r中删除其值等于ch的所有字符。从顺序串rl中第index个字符起求出首次与串r2相同的子串的起始位置。（5）从顺序串r中删除所有与串rl相同的子串。写ー个函数将顺序串si中的第i个字符到第j个字符之间的字符用s2串替换。［提示］:（1）用静态顺序串 （2）先移位,后复制写算法,实现顺序串的基本操作StrCompare（s,t）。写算法,实现顺序串的基本操作StrReplace（&s,t,v）〇［提示］：被替换子串定位（相当于第9题中i）被替换子串后面的字符左移或右移（为替换子串准备房间）替换子串入住（复制）重复上述,直到……第四章答案4.1设s='IAMASTUDENT',t='GOOD',q='WORKER,〇给出下列操作的结果:【解答】StrLength(s)=14;SubString(subl,s,1,7) subl='IAMA';SubString(sub2,s,7,1) sub2='';Strindex(s,4,'A')=6;StrReplace(s,'STUDENT',q); s='IAMAWORKER';StrCat(StrCat(subl,t),StrCat(sub2,q))subl='IAMAGOODWORKER,〇4.2编写算法,实现串的基本操作StrReplace(S,T,V)〇【解答】算法如下:intStrReplace(SStringS,SStringT,SStringV){/・用串V替换S中的所有子串T*/intpos,i;pos=strlndex(S,1,T); /*求S中子串T第一次出现的位置・/if(pos==0)return(0);while(pos!=0) /・用串V替换S中的所有子串T*/{switch(T.len-V.len)(case0: /・串T的长度等于串V的长度・/for(i=0;i〈=V.len;i++) /*用V替换WS->ch[pos+i]=V.ch[i];case>0: /・串T的长度大于串V的长度・/for(i=pos+t.ien;iくS-〉len;i-) /*将S中子串T后的所有字符S->ch[i-t.len+v.len]=S->ch[i];前移T.len-V.len个位置・/for(i=0;i<=V.len;i++)/・用V替换T*/S->ch[pos+i]=V.ch[i];S->len=S->len-T.len+V.len;case<0: /・串T的长度小于串V的长度・/if(S->len-T.len+V.len)<=MAXLEN /・插入后串长小于MAXLEN*/{/・将S中子串T后的所有字符后移V.len-T.len个位置・/for(i=S->len-T.len+V.len;i>=pos+T.len;i—)S->ch[i]=S->ch[i-T.len+V.len];for(i=0;i<=V.len;i++)/・用V替换T*/S->ch[pos+i]=V.ch[i];S->len=Sー〉len-T.len+V.len;}else{ /・替换后串长)MAXLEN,但串V可以全部替换・/if(pos+V.len<=MAXLEN){for(i=MAXLENT;i〉=pos+T.len;i一)S->ch[i]=s->ch[i-T.len+V.len]for(i=0;i<=V.len;i++)/・用V替换WS->ch[pos+i]=V.ch[i];S->len=MAXLEN;}else /・串V的部分字符要舍弃・/{for(i=0;iくMAXLEN-pos;i++)S->ch[i+pos]=V.ch[i];S->len=MAXLEN;}}/"switch〇*/pos=Strlndex(S,pos+V.len,T); /・求S中下一个子串T的位置・/}/*while()*/return(1);}/*StrReplace()*/附加题:用链式结构实现定位函数。【解答】typedefstructNode{chardata;structNode*next;}Node,*Lstring;intstrindex(LstringS,intpos,LstringT)/・从串S的pos序号起,串T第一次出现的位置・/{Node*p,*q,*Ppos;inti=0,,j=0;if(T->next==NULL||S->next==NULL)return(0);p=Sー)next;q=Tー)next;while(p!=NULL&&j<pos)/*p指向串S中第pos个字符・/{p=pー〉next;j+