《严蔚敏《数据结构》习题集算法答案.pdf》由会员分享，可在线阅读，更多相关《严蔚敏《数据结构》习题集算法答案.pdf（121页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、严 蔚 敏 数据结构(C语言版)习题集算法设计题答案第一章绪论1.16void print_descending(int xjnt y,int z)按从大到小顺序输出三个数(scanf(u%d,%d,%dH,&x,&y,&z);if(xy;v-为表示交换的双目运算符,以下同if(yz)yz;if(xy)xy;冒泡排序printf(H%d%d%d,x,y,z);/print_descending1.17Status fib(int k,int m,int&f)求k 阶斐波那契序列的第m 项的值f(int tempd;if(k2llm0)return ERROR;if(mk-l)f=0;else
2、if(m=k-l)f=l;else(for(i=0;i=k-2;i+)tempi=0;tempk-l=l;初始化for(i=k;iv=m;i+)求出序歹U 第 k 至第m 个元素的值(sum=0;for(j=i-k;ji;j+)sum+=temp|jj;tempi=sum;)f=tempm;)return OK;/fib分析:通过保存已经计算出来的结果，此方法的时间复杂度仅为O(m八 2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达0(k八 m).1.18typedef struct char 求 sport;enum male,female gender;char
3、schoolname;校名为 或Echar*result;int score;resulttype;typedef struct(int malescore;int femalescore;int totalscore;scoretype;void summary(resulttype result)求各校的男女总分和团体总分,假设结果已经储存在result数组中(scoretype score;i=0;while(resulti.sport!=NULL)(switch(resulti.schoolname)(case A:score 0.total score+=resul t i J.sc
4、 ore;if(resulti.gender=O)score 0 1.malescore+=resu 1 1i.score;else score 0.femalescore+=resulti.score;break;case B:score.totalscore+=resulti.score;if(resulti.gender=O)score.malescore+=resulti.score;else score.femalescore+=resulti.score;break;i+;)for(i=0;i5;i+)(printf(MSchool%d:n*,i);printf(nTotal sc
5、ore of male:%dn”,scoreij.malescore);printf(nTotal score of female:%dn,scorei.femalescore);printf(nTotal score of al 1:%dnn,scorei.totalscore);)/summary1.19Status algol 19(int aARRSIZE)求 i!*2Ai 序列的值且不超过 maxintlast=l;for(i=l;i=ARRSIZE;i+)ai-l=last*2*i;if(ai-l/last)!=(2*i)reurn OVERFLOW;last=ai-l;retur
6、n OK;)/algoll9分析:当某一项的结果超过了 maxint时,它除以前面一项的商会发生异常.1.20void polyvalue()(float ad;float*p=a;printf(nInput number of terms:1 1);scanf(n%d,&n);printf(Input the%d coefficients from aO to a%d:n,n,n);for(i=0;i=n;i+)scanf(1,%f,p+);printf(MInput value of x:u);scanf(n%f;&x);p=a；xp=l;sum=0;/xp用于存放x 的 i 次方for(
7、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(illlka.length)return INFEASIBLE;for(count=1 ;i+count-1 v=a.length-k;count+)注意循环结束的条件a.elemi+count-1 =a.elemi4-count+k-1 ;a.length-=k;return OK;/DeleteK2.11Status
8、Inseil_SqList(SqList&va,int x)把 x 插入递增有序表 va 中(if(va.length+1 va.listsize)return ERROR;va.length+;for(i=va.length-l;va.elemix&i=0;i)va.elemfi+l=va.elemi;va.elemi+l=x;return OK;/Insert_SqList2.12int ListComp(SqList A,SqList B)比较字符表A 和 B,并用返回值表示结果，值为正，表示AB;值为负，表示AvB;值为零，表示A=B(for(i=l;A.elemiIIB.elemi;
9、i+)if(A.elemi!=B.elemi)return A.elemi-B.elemi;return 0;/ListComp2.13LNode*Locate(LinkList L,int x)链表上的元素查找，返回指针(for(p=l-next;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 ListConcat(LinkList ha,LinkList hb,LinkList&hc)
10、把链表 hb 接在 ha 后面形成链表 he(hc=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 个元素之前插入元素b(p=L;q=(LinkList*)malloc(sizeof(LNode);q.data=b;if(i=l)(q.next=p;L=q;插入在链表头部)else(while(-il)p=p-next;q-next=p-next;p-next二 q;插入在第i 个元素的位置 /Insert2.18
11、Status Delete(LinkList&L,int i)在无头结点链表L 中删除第i 个元素(if(i=l)L=L-next;删除第个元素else(P=L;while(il)p=p-next;p-next二 p-nexl-next;删除第 i 个元素)/Delete2.19Status Delete_Between(Linklist&L,int minkjnt maxk)/删除元素递增排列的链表 L 中值大于mink且小于maxk的所有元素(p=L;while(p-next-datanext;/p 是最后一个不大于 mink 的元素if(p-next)如果还有比mink更大的元素(q=p
12、-next;while(q-datanext;/q 是第一个不小于 maxk 的元素p-next=q;)/Delete_B etween2.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都向后推一步)else(while(q-data=p-data)(free(q);q=q-next;)p-next=q;p=q;q=p-next;/当相邻元素
13、相等时删除多余元素/else/while/Delete_Equal2.21void reverse(SqList&A)顺序表的就地逆置(for(i=l,j=A.length;ij;i+,j-)A.elemiA.elemj;/reverse2.22void LinkList_reverse(Linklist&L)链表的就地逆置;为简化算法,假设表长大于2(p=L-next;q=p-next;s=q-next;p-next=NULL;while(s-next)(q-next=p;p=q;q=s;s=s-next;把L 的元素逐个插入新表表头)q-next=p;s-next=q;L-next=s;/
14、LinkList_reverse分析:本算法的思想是，逐个地把L 的当前元素q 插入新的链表头部,p 为新表表头.2.23void mergel(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;/W B 的元素插入if(s)(t=q-next;q-next=s;/$n A 非空，将 A 的元素插入)p=s;q=t;/while/merge 12.24void reverse_merge(LinkLi
15、st&A,LinkList&B,LinkList&C)把元素递增排列的链表 A 和 B 合并为C,且 C 中元素递减排列，使用原空间(pa=A-next;pb=B-next;pre=NULL;/pa 和 pb 分别指向 A,B 的当前元素while(pallpb)if(pa-datadatall!pb)pc=pa;q=pa-next;pa-next=pre;pa=q;/A 的元素插入新表)else(pc=pb;q=pb-next;pb-next=pre;pb=q;/W B 的元素插入新表)pre=pc;)C=A;A，next二 pc;构造新表头/reverse_merge分析:本算法的思想是，
16、按从小到大的顺序依次把A 和 B 的元素插入新表的头部p c处,最后处理 A 或 B 的剩余元素.2.25void SqList_Intersect(SqList A,SqList B,SqList&C)求元素递增排列的线性表 A 和 B 的元素的交集并存入C 中(i=l;j=l;k=O;while(A.elemi&B.elemj)(if(A.elemiB.elemj)j+;if(A.elemi=B.elemjJ)(C.elem+k=A.elemi;当发现了一个在A,B中都存在的元素，i+；j+；就添加到C 中)/while/SqList_Intersect2.26void LinkList_
17、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;else(s=(LNode*)malloc(sizeof(LNode);s-data=p-data;pc-next=s;pc=s;p=p-next;q=q-next;/whileC=pc;/LinkList_Intersect2.27void SqList_Int
18、ersect_True(SqList&A,SqList B)求元素递增排列的线性表A 和 B 的元素的交集并存回A 中(i=l；j=l；k=O;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+4-=0;/SqList_Intersect_True2.28void LinkList_Intersect_Tnie(LinkList&A,Link
19、List 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_In tersect_True2.29void SqList_Intersect_Delete(SqList&A,SqList B,SqList C)(i=0；j=0；k=0;m=0;i 指示A 中元素原来的位置,m
20、为移动后的位置while(iA.length&jB.length&kC.length)(if(B.elemjC.elemk)k+;elsesame=B.elemj;找 至!j 了相同元素 samewhile(B.elemj=same)j+;while(C.elemk=same)k+;j,k 后移到新的元素while(iA.length&A.elemisame)A.elem|m+=A.elemi+;需保留的元素移动到新位置while(iA.length&A.elemi=same)i+;跳过相同的元素)/whilewhile(inext;q=C-next;r=A-next;while(p&q&r)
21、(if(p-datadata)p=p-next;else if(p-dataq-data)q=q-next;else(u=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;确定第一个大于u 的元素指针s/whiler-next=s;删除r 和 s 之间的元素/ifwhile(p-data=u)p=p-next;while(q-data=u)q=q-next;/else/while/LinkList_Intersect_
22、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_Pre2.33Status LinkList_Divide(LinkList&L,CiList&A,CiLi
23、st&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-data)(q-next=s;q=s;)else(r-next=s;r=s;)/whilep-next=
24、A;q-next=B;r-next=C;完成循环链表/LinkList_Divide2.34void Print_XorLinkedList(XorLinkedList L)从左向右输出异或链表的元素值p=L.left;pre=NULL;while(p)printf(d”,pdata);q=XorP(p-LRPtr,pre);pre=p;p=q;任何一个结点的LRPtr域值与其左结点指针进行异或运算即得到其右结点指针)/Print_XorLinkedList2.35Status Insert_XorLinkedList(XorLinkedList&L,int x,int i)在异或链表 L 的
25、第 i 个元素前插入元素 x(p=L.left;pre=NULL;r=(XorNode*)malloc(sizeof(XorNode);r-data=x;if(i=l)当插入点在最左边的情况(p-LRPtr=XorP(p.LRPtr,r);r-LRPtr=p;L.left=r;return OK;)j=l；q=p-LRPtr;当插入点在中间的情况while(+jLRPtr,pre);pre=p;p=q;/while 在p,q两结点之间插入if(!q)return INFEASIBLE;/i 不可以超过表长p-LRPtr=XorP(XorP(p-LRPtr,q),r);q-LRPtr=XorP(
26、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=p-LRPtr;while(+jLRPtr,pre);pre=p;p=q;/while 找到待删结点q
27、if(!q)return INFEASIBLE;/i 不可以超过表长if(L.right=q)/q为最右结点的情况(p-LRPlr=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-LRPlr,q),p);修改指针free(q);return OK;/Delete_XorLinkedList2.37void OEReform(DuLinkedList&L)按 1,3,5
28、,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;/按题目要求调整了 next链的结构，此时pre链仍为原状for(p=L;p-next!=L;p=p-next)p-next-pre=
29、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;没找到p-freq+;q=p-pre;while(q-freqfreq)q=q-pre;查找插入位置if(q!=p-pre)(p-pre-nex
30、t=p-next;p-next-pre=p-pre;q-next-pre=p;p-next=q-next;qnext=p;ppre=q;调整位置)return p;/Locate_DuList2.39float GetValue_SqPoly(SqPoly P,int x0)求升冢顺序存储的稀疏多项式的值(PolyTerm*q;xp=1 ;q=P.data;sum=0;ex=0;while(qcoef)(while(exexp)xp*=xO;sum+=q-coef*xp;q+；)return sum;/GetValue_SqPoly2.40void Subtract_SqPoly(SqPoly
31、 Pl,SqPoly P2,SqPoly&P3)求稀疏多项式 Pl 减 P2 的差式 P3(PolyTerm*p,*q,*r;Create_SqPoly(P3);建立空多项式 P3p=Pl.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;q+;r+;Ielse(if(p-coef-q-coef)!=0)只有同次项相减不为零时才需要存入P 3中(r-coef=p-coef-q
32、-coef;r-exp=p-exp;r+;/ifp+;q+;/else/whilewhile(p-coef)处理P l或 P 2的剩余项(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-next;if(!p-data.exp)(L-next=p-next;p=p-next;跳过常数项)while(p!=L)(p-data
33、.coef*=p-data.exp;/M每,项求导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;while(p!=L)(if(p-data.exp!=2*(pdata.exp/2)(pa-next=p;pa=p;)else(pb-next=p;p
34、b=p;)p=p-next;/whilepa-next=A;pb-next=B;/Divide_LinkedPoly第三章栈与队列3.15typedef struct(Elemtype*base2;Elemtype*top2;BDStacktype;双向栈类型Status Init_Stack(BDStacktype&tws,int m)初始化一个大小为 m 的双向栈 tws(tws.base0=(Elemtype*)malloc(sizeof(Elemtype);tws.base 1 =tws.baseO+m;tws.top0=tws.base0;tws.top 1 =tws.base 1
35、;return OK;/Init_StackStatus push(BDStacktype&tws,int i,Elemtype x)/x 入栈,i=0 表示低端栈,i=l 表示高端栈(if(tws.top0tws,top 1 )return OVERFLOW;注意此时的栈满条件if(i=0)*tws.toplOJ+=x;else if(i=l)*tws.topl=x;else return ERROR;return OK;/pushStatus pop(BDStacktype&tws,int i,Elemtype&x)/x 出栈,i=0 表示低端栈,i=l 表示高端栈if(i=O)(if(t
36、ws.top0=tws.base0)return OVERFLOW;x=*tws.topfO;else if(i=l)if(tws.top 1 =tws.base 1 )return OVERFLOW;x=*+tws.topl;else return ERROR;return OK;/pop3.16void Train_arrange(char*train)这里用字符串train表示火车,H 表示硬席,S，表示软席(p=train;q=train;InitStack(s);while(*p)(if(*p=H)push(s,*p);把H 存入栈中else*(q+)=*p;把S 调到前部P+；wh
37、ile(!StackEmpty(s)(pop(s,c);*(q+)=c;把H 接在后部)/Train_arrange3.17intIsReverse()判断输入的字符串中国前和&后部分是否为逆串，是则返回1,否则返回0(InitStack(s);while(e=getchar()!=*&*)push(s,e);whi le(e=getchar()!=*)if(StackEmpty(s)return 0;pop(s,c);if(e!=c)return 0;)if(!StackEmpty(s)return 0;return 1;/IsRe verse3.18Status Bracket_Test(
38、char*str)判别表达式中小括号是否匹配(count=0;for(p=str;*p;p+)if(*p=()count+;else if(*p=,)1)count;if(count0)return ERROR;)if(count)return ERROR;注意括号不匹配的两种情况return OK;/Bracket_Test3.19Status AllBrackets_Test(char*str)判别表达式中三种括号是否匹配(InitStack(s);for(p=str;*p;p+)(if(*p=*(*|*p=,|*p=lr push(s,*p);else if(*p=)|*p=TII*P=
39、)(if(StackEmpty(s)return ERROR;pop(s,c);if(*p=y&c!=(,)return ERROR;if(*p=7&c!=,)return ERROR;if(*p=,&c!=*)return ERROR;必须与当前栈顶括号匹配)/forif(!StackEmpty(s)return ERROR;return OK;/A11B rackets_Test3.20t y p e d e f s t r u c t .i n t x;i n t y;c o o r d i n a t e;v o i d R e p a i n t _ C o l o r(i n t
40、g m n ,i n t i,i n t j,i n i c o l o r)把点(i,j湘邻区域的颜色置换为 c o l o r(o l l)i f(g x-l y =o l d)(g x-l y =c o l o r;E n Q u e u e(Q,x-1 ,y );/修改左邻点的颜色)i f(y D f(g x y-l =o l d)(g x j y-l =c o l o r;E n Q u e u e(Q,x,y-l );修改上邻点的颜色)i f(x m)i f(g x+l y =o l d)g x+l y =c o l o r;E n Q u e u e(Q,x+1 ,y );/修改
41、右邻点的颜色)i f(y=0)s=0;else if(m0&n=0)s=n+g(m-l,2*n);else return ERROR;return OK;/g3.25Status F_recursive(int n,int&s)递归算法(if(n0)return ERROR;if(n=0)s=n+l;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+l;else(InitStack(s);/s 的元素类型为
42、 struct int a;int b;while(n!=0)(a=n;b=n/2;push(s,a,b);n=b;/whiles=l;while(!StackEmpty(s)(pop(s,t)；s*=t.a;/while)return OK;/F_nonrecursive3.26float Sqrt_recursive(float A,float p,float e)求平方根的递归算法(if(abs(pA2-A)=e)p=(p+A/p)/2;return p;/Sq第四章申4.10void String_Reverse(Stringtype s,Stringtype&r)求 s 的逆串 r(
43、Str Assign,);初始化r 为空串for(i=Strlen(s);i;i-)(StrAssign(c,SubString(s,i,1);StrAssign(r,Concat(r,c);把s 的字符从后往前添加到r 中)/String_Reverse4.11void String_Subtract(Stringtype s,Stringtype t,Stringtype&r)求所有包含在串 s 中而 t 中没有的字符构成的新串r(StrAssign(r,H);for(i=l;i=Strlen(s);i+)(StrAssign(c,SubString(s,i,1);for(j=l;jvi&
44、StrCompare(c,SubString(s,j);j+);判断 s 的当前字符 c 是否第一次出现if(i=j)(for(k=l;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=l;i=Strlen(S)-Strlen(T)+l;i+)/?4M i 的取值范围if(!StrCompare(SubString(S,i,Strlen(T),T)找
45、到了与 T 匹配的子串 分别把T 的前面和后面部分保存为head和 tailStr Assign(head,SubString(S,1 ,i-1 )；StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+l);StrAssign(S,Concat(head,V);StrAssign(S,Concat(S,tai1);把 head,V,tail 连接为新串i十 二 StHen(V);当前指针跳至Ij插入串以后n+;/ifreturn n;/Replace分析:i+=Strlen(V);这一句是必需的，也是容易忽略的.如省掉这一句
46、,则在某些情况卜.，会引起不希望的后果，虽然在大多数情况下没有影响.请思考:设SWplace；T=ace,V士 face；则省掉i+二 Strlen(V);运行时会出现什么结果？4.13int Delete_SubString(Stringtype&s,Stringtype t)从串s 中删除所有V t相同的子串，并返回删除次数(for(n=0,i=1;i=Strlen(s)-Strlen(t)+1;i+)if(!StrCompare(SubString(s,i,Strlen(t),t)(StrAssign(head,SubString(S,1 ,i-1);StrAssign(tail,Sub
47、String(S,i+Strlen(t),Strlen(s)-i-Strlen(t)+l);StrAssign(S,Concat(head,tail);把 head,tail 连接为新申n+;/ifreturn n,/Delete_SubString4.14Status NiBoLan_to_BoLan(Stringtype str,Stringtype&new)把前缀表达式 str 转换为后缀式new(Initstack(s);/s 的元素为 Stringtype 类型for(i=l;it 时返回正数,s=t 时返回 0,svt 时返回负数(for(i=l;i=sO&isO&itO)retu
48、rn 0;else if(isOJ)returnelse if(itO)return si;else return si-tij;/StrCompare4.17int String_Replace(Stringtype&S,Stringtype T,Stringtype V);将串 S 中所有子串 T 替换为 V,并返回置换次数(for(n=0,i=l;iT0)找到了与T 匹配的子串:分三种情况处理(if(T0=V0)for(l=1 ;1=TIOJ;1+)新子串长度与原子串相同时:直接替换Si+l-l=Vl;else if(T0=i+TOJ;l-)S1+VO-TO=S1;for(l=l;l=V
49、0;l+)Si+l-l=Vl;)else 新子串长度小于原子串时:先将后部左移(for(l=i+V 0;1=S 0+V0-T|0;1+)Sl=Sl-V0+T0;for(l=l;l=V0;l+)Si+l-l=Vl;)S0=S0-T0+V0;i+=V0;n+;/if/forreturn n;/String_Replace4.18typedef struct char ch;int num;mytype;void StrAnalyze(Stringtype S)统计串S 中字符的种类和个数mytype TMAXSIZE;用结构数组T 存储统计结果for(i=l;i=S0;i+)(c=Sli;j=O;
50、while(Tjl.ch&Tfjl.ch!=c)j+;查找当前字符c 是否已记录过if(Tj.ch)Tj.num+4-;else Tj=c,l;/forfor(j=0;T|j.ch;j+)printf(u%c:%dnn,Tj.ch,Tj.num);/Str Analyze4.19void Subtract_String(Stringtype s,Stringtype t,Stringtype&r)求所有包含在串 s 中而 t 中没有的字符构成的新串rr0=0;for(i=l;i=sO;i+)(c=sil;for(j=l;ji&sj!=c;j+);判断s 的当前字符c 是否第一次出现if(i=j