数据结构(c语言版)习题集全答案.pdf

《数据结构(c语言版)习题集全答案.pdf》由会员分享，可在线阅读，更多相关《数据结构(c语言版)习题集全答案.pdf（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、说明:1.本文是对严蔚敏数据结构(c 语言版)习题集一书中所有算法设计题目的解决方案,主要作者为 计算机版版主一具.以下网友:siice,龙抬头,iamkent,zames,birdthinking 等为答案的修订和完善工作提出了宝贵意见,在此表示感谢;2.本解答中的所有算法均采用类 c 语言描述,设计原则为面向交流、面向阅读,作者不保证程序能够上机正常运行(这种保证实际上也没有任何意义);3.本解答原则上只给出源代码以及必要的注释,对于一些难度较高或思路特殊的题目将给出简要的分析说明,对于作者无法解决的题目将给出必要的讨论.目前尚未解决的题目有:5.20,10.40;4.请读者在自己已经解决

2、了某个题目或进行了充分的思考之后,再参考本解答,以保证复习效果;5.由于作者水平所限,本解答中一定存在不少这样或者那样的错误和不足,希望读者们在阅读中多动脑、勤思考,争取发现和纠正这些错误,写出更好的算法来.请将你发现的错误或其它值得改进之处向作者报告:yi-第一章 绪论1.16void print_descending(int x,int y,int z)/按从大到小顺序输出三个数scanf(%d,%d,%d,&x,&y,&z);if(xy)xy;/为表示交换的双目运算符,以下同if(yz)yz;if(xy)xy;/冒泡排序printf(%d%d%d,x,y,z);/print_descen

3、ding1.17Status fib(int k,int m,int&f)/求 k 阶斐波那契序列的第 m 项的值 fint tempd;if(k2|m0)return ERROR;if(mk-1)f=0;else if(m=k-1)f=1;elsefor(i=0;i=k-2;i+)tempi=0;tempk-1=1;/初始化for(i=k;i=m;i+)/求出序列第 k 至第 m 个元素的值sum=0;for(j=i-k;ji;j+)sum+=tempj;tempi=sum;f=tempm;return OK;/fib分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为 O(m2).如果

4、采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(km).1.18typedef structchar*sport;enummale,female gender;char schoolname;/校名为A,B,C,D或Echar*result;int score;resulttype;typedef structint malescore;int femalescore;int totalscore;scoretype;void summary(resulttype result)/求各校的男女总分和团体总分,假设结果已经储存在 result 数组中scoretype sco

5、re;i=0;while(resulti.sport!=NULL)switch(resulti.schoolname)case A:score 0.totalscore+=resulti.score;if(resulti.gender=0)score 0.malescore+=resulti.score;else score 0.femalescore+=resulti.score;break;case B:score.totalscore+=resulti.score;if(resulti.gender=0)score.malescore+=resulti.score;else score.

6、femalescore+=resulti.score;break;i+；for(i=0;i5;i+)printf(School%d:n,i);printf(Total score of male:%dn,scorei.malescore);printf(Total score of female:%dn,scorei.femalescore);printf(Total score of all:%dnn,scorei.totalscore);/summary1.19Status algo119(int aARRSIZE)/求 i!*2i 序列的值且不超过 maxintlast=1;for(i=

7、1;i=ARRSIZE;i+)ai-1=last*2*i;if(ai-1/last)!=(2*i)reurn OVERFLOW;last=ai-1;return OK;/algo119分析:当某一项的结果超过了 maxint 时,它除以前面一项的商会发生异常.1.20void polyvalue()float ad;float*p=a;printf(Input number of terms:);scanf(%d,&n);printf(Input the%d coefficients from a0 to a%d:n,n,n);for(i=0;i=n;i+)scanf(%f,p+);print

8、f(Input value of x:);scanf(%f,&x);p=a;xp=1;sum=0;/xp 用于存放 x 的 i 次方for(i=0;i=n;i+)sum+=xp*(*p+);xp*=x;printf(Value is:%f,sum);/polyvalue第二章 线性表2.10Status DeleteK(SqList&a,int i,int k)/删除线性表 a 中第 i 个元素起的 k 个元素if(i1|ka.length)return INFEASIBLE;for(count=1;i+count-1va.listsize)return ERROR;va.length+;fo

9、r(i=va.length-1;va.elemix&i=0;i-)va.elemi+1=va.elemi;va.elemi+1=x;return OK;/Insert_SqList2.12int ListComp(SqList A,SqList B)/比较字符表 A 和 B,并用返回值表示结果,值为正,表示 AB;值为负,表示 Anext;p&p-data!=x;p=p-next);return p;/Locate2.14int Length(LinkList L)/求链表的长度for(k=0,p=L;p-next;p=p-next,k+);return k;/Length2.15void L

10、istConcat(LinkList ha,LinkList hb,LinkList&hc)/把链表 hb接在 ha 后面形成链表 hchc=ha;p=ha;while(p-next)p=p-next;p-next=hb;/ListConcat2.16见书后答案.2.17Status Insert(LinkList&L,int i,int b)/在无头结点链表 L 的第 i 个元素之前插入元素 bp=L;q=(LinkList*)malloc(sizeof(LNode);q.data=b;if(i=1)q.next=p;L=q;/插入在链表头部elsewhile(-i1)p=p-next;q-

11、next=p-next;p-next=q;/插入在第 i 个元素的位置/Insert2.18Status Delete(LinkList&L,int i)/在无头结点链表 L 中删除第 i 个元素if(i=1)L=L-next;/删除第一个元素elsep=L;while(-i1)p=p-next;p-next=p-next-next;/删除第 i 个元素/Delete2.19Status Delete_Between(Linklist&L,int mink,int maxk)/删除元素递增排列的链表 L 中值大于 mink 且小于 maxk 的所有元素p=L;while(p-next-data

12、next;/p 是最后一个不大于 mink的元素if(p-next)/如果还有比 mink 更大的元素q=p-next;while(q-datanext;/q 是第一个不小于 maxk 的元素p-next=q;/Delete_Between2.20Status Delete_Equal(Linklist&L)/删除元素递增排列的链表 L 中所有值相同的元素p=L-next;q=p-next;/p,q 指向相邻两元素while(p-next)if(p-data!=q-data)p=p-next;q=p-next;/当相邻两元素不相等时,p,q 都向后推一步elsewhile(q-data=p-d

13、ata)free(q);q=q-next;p-next=q;p=q;q=p-next;/当相邻元素相等时删除多余元素/else/while/Delete_Equal2.21void reverse(SqList&A)/顺序表的就地逆置for(i=1,j=A.length;ij;i+,j-)A.elemiA.elemj;/reverse2.22void LinkList_reverse(Linklist&L)/链表的就地逆置;为简化算法,假设表长大于 2p=L-next;q=p-next;s=q-next;p-next=NULL;while(s-next)q-next=p;p=q;q=s;s=s

14、-next;/把 L 的元素逐个插入新表表头q-next=p;s-next=q;L-next=s;/LinkList_reverse分析:本算法的思想是,逐个地把 L 的当前元素 q插入新的链表头部,p 为新表表头.2.23void merge1(LinkList&A,LinkList&B,LinkList&C)/把链表 A 和 B 合并为 C,A 和 B 的元素间隔排列,且使用原存储空间p=A-next;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;

15、q=t;/while/merge12.24void reverse_merge(LinkList&A,LinkList&B,LinkList&C)/把元素递增排列的链表 A 和 B 合并为 C,且 C 中元素递减排列,使用原空间pa=A-next;pb=B-next;pre=NULL;/pa和 pb 分别指向 A,B 的当前元素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=pc;C=A

16、;A-next=pc;/构造新表头/reverse_merge分析:本算法的思想是,按从小到大的顺序依次把 A 和 B 的元素插入新表的头部 pc 处,最后处理 A 或 B 的剩余元素.2.25void SqList_Intersect(SqList A,SqList B,SqList&C)/求元素递增排列的线性表 A 和 B 的元素的交集并存入 C 中i=1;j=1;k=0;while(A.elemi&B.elemj)if(A.elemiB.elemj)j+;if(A.elemi=B.elemj)C.elem+k=A.elemi;/当发现了一个在 A,B 中都存在的元素,i+;j+;/就添加

17、到 C 中/while/SqList_Intersect2.26void LinkList_Intersect(LinkList A,LinkList B,LinkList&C)/在链表结构上重做上题p=A-next;q=B-next;pc=(LNode*)malloc(sizeof(LNode);while(p&q)if(p-datadata)p=p-next;else if(p-dataq-data)q=q-next;elses=(LNode*)malloc(sizeof(LNode);s-data=p-data;pc-next=s;pc=s;p=p-next;q=q-next;/whil

18、eC=pc;/LinkList_Intersect2.27void SqList_Intersect_True(SqList&A,SqList B)/求元素递增排列的线性表 A 和 B 的元素的交集并存回 A 中i=1;j=1;k=0;while(A.elemi&B.elemj)if(A.elemiB.elemj)j+;else if(A.elemi!=A.elemk)A.elem+k=A.elemi;/当发现了一个在 A,B 中都存在的元素i+;j+;/且 C 中没有,就添加到 C 中/whilewhile(A.elemk)A.elemk+=0;/SqList_Intersect_True2

19、.28void LinkList_Intersect_True(LinkList&A,LinkList B)/在链表结构上重做上题p=A-next;q=B-next;pc=A;while(p&q)if(p-datadata)p=p-next;else if(p-dataq-data)q=q-next;else if(p-data!=pc-data)pc=pc-next;pc-data=p-data;p=p-next;q=q-next;/while/LinkList_Intersect_True2.29void SqList_Intersect_Delete(SqList&A,SqList B,

20、SqList C)i=0;j=0;k=0;m=0;/i 指示 A 中元素原来的位置,m 为移动后的位置while(iA.length&jB.length&kC.length)if(B.elemjC.elemk)k+;elsesame=B.elemj;/找到了相同元素 samewhile(B.elemj=same)j+;while(C.elemk=same)k+;/j,k 后移到新的元素while(iA.length&A.elemisame)A.elemm+=A.elemi+;/需保留的元素移动到新位置while(iA.length&A.elemi=same)i+;/跳过相同的元素/whilew

21、hile(inext;q=C-next;r=A-next;while(p&q&r)if(p-datadata)p=p-next;else if(p-dataq-data)q=q-next;elseu=p-data;/确定待删除元素 uwhile(r-next-datanext;/确定最后一个小于 u 的元素指针 rif(r-next-data=u)s=r-next;while(s-data=u)t=s;s=s-next;free(t);/确定第一个大于 u 的元素指针 s/whiler-next=s;/删除 r 和 s 之间的元素/ifwhile(p-data=u)p=p-next;while

22、(q-data=u)q=q-next;/else/while/LinkList_Intersect_Delete2.31Status Delete_Pre(CiLNode*s)/删除单循环链表中结点 s 的直接前驱p=s;while(p-next-next!=s)p=p-next;/找到 s 的前驱的前驱 pp-next=s;return OK;/Delete_Pre2.32Status DuLNode_Pre(DuLinkList&L)/完成双向循环链表结点的 pre 域for(p=L;!p-next-pre;p=p-next)p-next-pre=p;return OK;/DuLNode_

23、Pre2.33Status LinkList_Divide(LinkList&L,CiList&A,CiList&B,CiList&C)/把单链表 L的元素按类型分为三个循环链表.CiList为带头结点的单循环链表类型.s=L-next;A=(CiList*)malloc(sizeof(CiLNode);p=A;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-d

24、ata)q-next=s;q=s;elser-next=s;r=s;/whilep-next=A;q-next=B;r-next=C;/完成循环链表/LinkList_Divide2.34void Print_XorLinkedList(XorLinkedList L)/从左向右输出异或链表的元素值p=L.left;pre=NULL;while(p)printf(%d,p-data);q=XorP(p-LRPtr,pre);pre=p;p=q;/任何一个结点的 LRPtr 域值与其左结点指针进行异或运算即得到其右结点指针/Print_XorLinkedList2.35Status Insert

25、_XorLinkedList(XorLinkedList&L,int x,int i)/在异或链表 L 的第 i 个元素前插入元素 xp=L.left;pre=NULL;r=(XorNode*)malloc(sizeof(XorNode);r-data=x;if(i=1)/当插入点在最左边的情况p-LRPtr=XorP(p.LRPtr,r);r-LRPtr=p;L.left=r;return OK;j=1;q=p-LRPtr;/当插入点在中间的情况while(+jLRPtr,pre);pre=p;p=q;/while/在 p,q 两结点之间插入if(!q)return INFEASIBLE;/

26、i 不可以超过表长p-LRPtr=XorP(XorP(p-LRPtr,q),r);q-LRPtr=XorP(XorP(q-LRPtr,p),r);r-LRPtr=XorP(p,q);/修改指针return OK;/Insert_XorLinkedList2.36Status Delete_XorLinkedList(XorlinkedList&L,int i)/删除异或链表 L 的第 i 个元素p=L.left;pre=NULL;if(i=1)/删除最左结点的情况q=p-LRPtr;q-LRPtr=XorP(q-LRPtr,p);L.left=q;free(p);return OK;j=1;q

27、=p-LRPtr;while(+jLRPtr,pre);pre=p;p=q;/while/找到待删结点 qif(!q)return INFEASIBLE;/i 不可以超过表长if(L.right=q)/q 为最右结点的情况p-LRPtr=XorP(p-LRPtr,q);L.right=p;free(q);return OK;r=XorP(q-LRPtr,p);/q 为中间结点的情况,此时 p,r 分别为其左右结点p-LRPtr=XorP(XorP(p-LRPtr,q),r);r-LRPtr=XorP(XorP(r-LRPtr,q),p);/修改指针free(q);return OK;/Dele

28、te_XorLinkedList2.37void OEReform(DuLinkedList&L)/按 1,3,5,.4,2 的顺序重排双向循环链表 L 中的所有结点p=L.next;while(p-next!=L&p-next-next!=L)p-next=p-next-next;p=p-next;/此时 p 指向最后一个奇数结点if(p-next=L)p-next=L-pre-pre;else p-next=l-pre;p=p-next;/此时 p 指向最后一个偶数结点while(p-pre-pre!=L)p-next=p-pre-pre;p=p-next;p-next=L;/按题目要求调

29、整了 next 链的结构,此时 pre 链仍为原状for(p=L;p-next!=L;p=p-next)p-next-pre=p;L-pre=p;/调整 pre 链的结构,同 2.32 方法/OEReform分析:next 链和 pre 链的调整只能分开进行.如同时进行调整的话,必须使用堆栈保存偶数结点的指针,否则将会破坏链表结构,造成结点丢失.2.38DuLNode*Locate_DuList(DuLinkedList&L,int x)/带 freq 域的双向循环链表上的查找p=L.next;while(p.data!=x&p!=L)p=p-next;if(p=L)return NULL;/

30、没找到p-freq+;q=p-pre;while(q-freqfreq)q=q-pre;/查找插入位置if(q!=p-pre)p-pre-next=p-next;p-next-pre=p-pre;q-next-pre=p;p-next=q-next;q-next=p;p-pre=q;/调整位置return p;/Locate_DuList2.39float GetValue_SqPoly(SqPoly P,int x0)/求升幂顺序存储的稀疏多项式的值PolyTerm*q;xp=1;q=P.data;sum=0;ex=0;while(q-coef)while(exexp)xp*=x0;sum+

31、=q-coef*xp;q+;return sum;/GetValue_SqPoly2.40void Subtract_SqPoly(SqPoly P1,SqPoly P2,SqPoly&P3)/求稀疏多项式 P1 减 P2 的差式 P3PolyTerm*p,*q,*r;Create_SqPoly(P3);/建立空多项式 P3p=P1.data;q=P2.data;r=P3.data;while(p-coef&q-coef)if(p-expexp)r-coef=p-coef;r-exp=p-exp;p+;r+;else if(p-expexp)r-coef=-q-coef;r-exp=q-exp

32、;q+;r+;elseif(p-coef-q-coef)!=0)/只有同次项相减不为零时才需要存入P3 中r-coef=p-coef-q-coef;r-exp=p-exp;r+;/ifp+;q+;/else/whilewhile(p-coef)/处理 P1 或 P2 的剩余项r-coef=p-coef;r-exp=p-exp;p+;r+;while(q-coef)r-coef=-q-coef;r-exp=q-exp;q+;r+;/Subtract_SqPoly2.41void QiuDao_LinkedPoly(LinkedPoly&L)/对有头结点循环链表结构存储的稀疏多项式 L 求导p=L

33、-next;if(!p-data.exp)L-next=p-next;p=p-next;/跳过常数项while(p!=L)p-data.coef*=p-data.exp-;/对每一项求导p=p-next;/QiuDao_LinkedPoly2.42void Divide_LinkedPoly(LinkedPoly&L,&A,&B)/把循环链表存储的稀疏多项式 L 拆成只含奇次项的 A 和只含偶次项的 Bp=L-next;A=(PolyNode*)malloc(sizeof(PolyNode);B=(PolyNode*)malloc(sizeof(PolyNode);pa=A;pb=B;whil

34、e(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_LinkedPoly第三章 栈与队列3.15typedef structElemtype*base2;Elemtype*top2;BDStacktype;/双向栈类型Status Init_Stack(BDStacktype&tws,int m)/初始化一个大小为 m 的双向栈 twstws.base0=(Elemtype*)malloc(sizeof(Elemtyp

35、e);tws.base1=tws.base0+m;tws.top0=tws.base0;tws.top1=tws.base1;return OK;/Init_StackStatus push(BDStacktype&tws,int i,Elemtype x)/x 入栈,i=0 表示低端栈,i=1 表示高端栈if(tws.top0tws.top1)return OVERFLOW;/注意此时的栈满条件if(i=0)*tws.top0+=x;else if(i=1)*tws.top1-=x;else return ERROR;return OK;/pushStatus pop(BDStacktype

36、&tws,int i,Elemtype&x)/x 出栈,i=0 表示低端栈,i=1 表示高端栈if(i=0)if(tws.top0=tws.base0)return OVERFLOW;x=*-tws.top0;else if(i=1)if(tws.top1=tws.base1)return OVERFLOW;x=*+tws.top1;else return ERROR;return OK;/pop3.16void Train_arrange(char*train)/这里用字符串 train 表示火车,H表示硬席,S表示软席p=train;q=train;InitStack(s);while(*

37、p)if(*p=H)push(s,*p);/把H存入栈中else*(q+)=*p;/把S调到前部p+;while(!StackEmpty(s)pop(s,c);*(q+)=c;/把H接在后部/Train_arrange3.17int IsReverse()/判断输入的字符串中&前和&后部分是否为逆串,是则返回 1,否则返回 0InitStack(s);while(e=getchar()!=&)push(s,e);while(e=getchar()!=)if(StackEmpty(s)return 0;pop(s,c);if(e!=c)return 0;if(!StackEmpty(s)retu

38、rn 0;return 1;/IsReverse3.18Status Bracket_Test(char*str)/判别表达式中小括号是否匹配count=0;for(p=str;*p;p+)if(*p=()count+;else if(*p=)count-;if(count1)if(gx-1y=old)gx-1y=color;EnQueue(Q,x-1,y);/修改左邻点的颜色if(y1)if(gxy-1=old)gxy-1=color;EnQueue(Q,x,y-1);/修改上邻点的颜色if(xm)if(gx+1y=old)gx+1y=color;EnQueue(Q,x+1,y);/修改右邻

39、点的颜色if(y=0)s=0;else if(m0&n=0)s=n+g(m-1,2*n);else return ERROR;return OK;/g3.25Status F_recursive(int n,int&s)/递归算法if(n0)return ERROR;if(n=0)s=n+1;elseF_recurve(n/2,r);s=n*r;return OK;/F_recursiveStatus F_nonrecursive(int n,int s)/非递归算法if(n0)return ERROR;if(n=0)s=n+1;elseInitStack(s);/s 的元素类型为 struc

40、t int a;int b;while(n!=0)a=n;b=n/2;push(s,a,b);n=b;/whiles=1;while(!StackEmpty(s)pop(s,t);s*=t.a;/whilereturn OK;/F_nonrecursive3.26float Sqrt_recursive(float A,float p,float e)/求平方根的递归算法if(abs(p2-A)=e)p=(p+A/p)/2;return p;/Sqrt_nonrecursive3.27这一题的所有算法以及栈的变化过程请参见数据结构(pascal 版),作者不再详细写出.3.28void Ini

41、tCiQueue(CiQueue&Q)/初始化循环链表表示的队列 QQ=(CiLNode*)malloc(sizeof(CiLNode);Q-next=Q;/InitCiQueuevoid EnCiQueue(CiQueue&Q,int x)/把元素 x 插入循环链表表示的队列Q,Q 指向队尾元素,Q-next 指向头结点,Q-next-next 指向队头元素p=(CiLNode*)malloc(sizeof(CiLNode);p-data=x;p-next=Q-next;/直接把 p 加在 Q 的后面Q-next=p;Q=p;/修改尾指针Status DeCiQueue(CiQueue&Q,

42、int x)/从循环链表表示的队列 Q 头部删除元素 xif(Q=Q-next)return INFEASIBLE;/队列已空p=Q-next-next;x=p-data;Q-next-next=p-next;free(p);return OK;/DeCiQueue3.29Status EnCyQueue(CyQueue&Q,int x)/带 tag 域的循环队列入队算法if(Q.front=Q.rear&Q.tag=1)/tag 域的值为 0 表示空,1 表示满return OVERFLOW;Q.baseQ.rear=x;Q.rear=(Q.rear+1)%MAXSIZE;if(Q.fron

43、t=Q.rear)Q.tag=1;/队列满/EnCyQueueStatus DeCyQueue(CyQueue&Q,int&x)/带 tag 域的循环队列出队算法if(Q.front=Q.rear&Q.tag=0)return INFEASIBLE;Q.front=(Q.front+1)%MAXSIZE;x=Q.baseQ.front;if(Q.front=Q.rear)Q.tag=1;/队列空return OK;/DeCyQueue分析:当循环队列容量较小而队列中每个元素占的空间较多时,此种表示方法可以节约较多的存储空间,较有价值.3.30Status EnCyQueue(CyQueue&Q

44、,int x)/带 length 域的循环队列入队算法if(Q.length=MAXSIZE)return OVERFLOW;Q.rear=(Q.rear+1)%MAXSIZE;Q.baseQ.rear=x;Q.length+;return OK;/EnCyQueueStatus DeCyQueue(CyQueue&Q,int&x)/带 length 域的循环队列出队算法if(Q.length=0)return INFEASIBLE;head=(Q.rear-Q.length+1)%MAXSIZE;/详见书后注释x=Q.basehead;Q.length-;/DeCyQueue3.31int

45、Palindrome_Test()/判别输入的字符串是否回文序列,是则返回 1,否则返回 0InitStack(S);InitQueue(Q);while(c=getchar()!=)Push(S,c);EnQueue(Q,c);/同时使用栈和队列两种结构while(!StackEmpty(S)Pop(S,a);DeQueue(Q,b);if(a!=b)return ERROR;return OK;/Palindrome_Test3.32void GetFib_CyQueue(int k,int n)/求 k 阶斐波那契序列的前 n+1 项InitCyQueue(Q);/其 MAXSIZE 设

46、置为 kfor(i=0;ik-1;i+)Q.basei=0;Q.basek-1=1;/给前 k 项赋初值for(i=0;ik;i+)printf(%d,Q.basei);for(i=k;i=n;i+)m=i%k;sum=0;for(j=0;j=avr)/根据 x 的值决定插入在队头还是队尾Q.baseQ.rear=x;Q.rear=(Q.rear+1)%MAXSIZE;/插入在队尾elseQ.front=(Q.front-1)%MAXSIZE;Q.baseQ.front=x;/插入在队头return OK;/EnDQueueStatus DeDQueue(DQueue&Q,int&x)/输出受

47、限的双端队列的出队操作if(Q.front=Q.rear)return INFEASIBLE;/队列空x=Q.baseQ.front;Q.front=(Q.front+1)%MAXSIZE;return OK;/DeDQueue3.34void Train_Rearrange(char*train)/这里用字符串 train 表示火车,P表示硬座,H表示硬卧,S表示软卧,最终按 PSH 的顺序排列r=train;InitDQueue(Q);while(*r)if(*r=P)printf(E);printf(D);/实际上等于不入队列,直接输出 P 车厢else if(*r=S)printf(E

48、);EnDQueue(Q,*r,0);/0 表示把 S 车厢从头端入队列elseprintf(A);EnDQueue(Q,*r,1);/1 表示把 H 车厢从尾端入队列/whilewhile(!DQueueEmpty(Q)printf(D);DeDQueue(Q);/while/从头端出队列的车厢必然是先 S 后 H 的顺序/Train_Rearrange第四章 串4.10void String_Reverse(Stringtype s,Stringtype&r)/求 s 的逆串 rStrAssign(r,);/初始化 r 为空串for(i=Strlen(s);i;i-)StrAssign(c

49、,SubString(s,i,1);StrAssign(r,Concat(r,c);/把 s 的字符从后往前添加到 r 中/String_Reverse4.11void String_Subtract(Stringtype s,Stringtype t,Stringtype&r)/求所有包含在串 s 中而 t 中没有的字符构成的新串 rStrAssign(r,);for(i=1;i=Strlen(s);i+)StrAssign(c,SubString(s,i,1);for(j=1;ji&StrCompare(c,SubString(s,j,1);j+);/判断 s 的当前字符 c 是否第一次出

50、现if(i=j)for(k=1;kStrlen(t)StrAssign(r,Concat(r,c);/for/String_Subtract4.12int Replace(Stringtype&S,Stringtype T,Stringtype V);/将串 S 中所有子串 T 替换为 V,并返回置换次数for(n=0,i=1;i=Strlen(S)-Strlen(T)+1;i+)/注意 i 的取值范围if(!StrCompare(SubString(S,i,Strlen(T),T)/找到了与 T 匹配的子串/分别把 T 的前面和后面部分保存为 head 和 tailStrAssign(hea