實(shí)驗(yàn)1求兩個(gè)多項(xiàng)式的相加運(yùn)算（線性表）編寫一個(gè)程序用單鏈表存儲多項(xiàng)式，并實(shí)現(xiàn)兩個(gè)多項(xiàng)式相加的函數(shù)。/*文件名:實(shí)驗(yàn)1.cpp*/#include<stdio.h>#include<malloc.h>#defineMAX20 /*多項(xiàng)式最多項(xiàng)數(shù)*/typedefstruct /*定義存放多項(xiàng)式的數(shù)組類型*/{ floatcoef; /*系數(shù)*/ intexp; /*指數(shù)*/}PolyArray[MAX];typedefstructpnode /*定義單鏈表結(jié)點(diǎn)類型*/{ floatcoef; /*系數(shù)*/ intexp; /*指數(shù)*/ structpnode*next;}PolyNode;voidDispPoly(PolyNode*L) /*輸出多項(xiàng)式*/{ PolyNode*p=L->next; while(p!=NULL) { printf("%gX^%d",p->coef,p->exp); p=p->next; } printf("\n");}voidCreateListR(PolyNode*&L,PolyArraya,intn)/*尾插法建表*/{ PolyNode*s,*r;inti; L=(PolyNode*)malloc(sizeof(PolyNode)); /*創(chuàng)建頭結(jié)點(diǎn)*/ L->next=NULL; r=L; /*r始終指向終端結(jié)點(diǎn),開始時(shí)指向頭結(jié)點(diǎn)*/ for(i=0;i<n;i++) { s=(PolyNode*)malloc(sizeof(PolyNode));/*創(chuàng)建新結(jié)點(diǎn)*/ s->coef=a[i].coef; s->exp=a[i].exp; r->next=s; /*將*s插入*r之后*/ r=s; } r->next=NULL; /*終端結(jié)點(diǎn)next域置為NULL*/}voidSort(PolyNode*&head) /*按exp域遞減排序*/{ PolyNode*p=head->next,*q,*r; if(p!=NULL) /*若原單鏈表中有一個(gè)或以上的數(shù)據(jù)結(jié)點(diǎn)*/ { r=p->next; /*r保存*p結(jié)點(diǎn)后繼結(jié)點(diǎn)的指針*/ p->next=NULL; /*構(gòu)造只含一個(gè)數(shù)據(jù)結(jié)點(diǎn)的有序表*/ p=r; while(p!=NULL) { r=p->next; /*r保存*p結(jié)點(diǎn)后繼結(jié)點(diǎn)的指針*/ q=head; while(q->next!=NULL&&q->next->exp>p->exp) q=q->next; /*在有序表中找插入*p的前驅(qū)結(jié)點(diǎn)*q*/ p->next=q->next; /*將*p插入到*q之后*/ q->next=p; p=r; } }}voidAdd(PolyNode*ha,PolyNode*hb,PolyNode*&hc)/*求兩有序集合的并*/{ PolyNode*pa=ha->next,*pb=hb->next,*s,*tc; floatc; hc=(PolyNode*)malloc(sizeof(PolyNode)); /*創(chuàng)建頭結(jié)點(diǎn)*/ tc=hc; while(pa!=NULL&&pb!=NULL) { if(pa->exp>pb->exp) { s=(PolyNode*)malloc(sizeof(PolyNode)); /*復(fù)制結(jié)點(diǎn)*/ s->exp=pa->exp;s->coef=pa->coef; tc->next=s;tc=s; pa=pa->next; } elseif(pa->exp<pb->exp) { s=(PolyNode*)malloc(sizeof(PolyNode)); /*復(fù)制結(jié)點(diǎn)*/ s->exp=pb->exp;s->coef=pb->coef; tc->next=s;tc=s; pb=pb->next; } else /*pa->exp=pb->exp*/ { c=pa->coef+pb->coef; if(c!=0) /*系數(shù)之和不為0時(shí)創(chuàng)建新結(jié)點(diǎn)*/ { s=(PolyNode*)malloc(sizeof(PolyNode)); /*復(fù)制結(jié)點(diǎn)*/ s->exp=pa->exp;s->coef=c; tc->next=s;tc=s; } pa=pa->next; pb=pb->next; } } if(pb!=NULL)pa=pb; /*復(fù)制余下的結(jié)點(diǎn)*/ while(pa!=NULL) { s=(PolyNode*)malloc(sizeof(PolyNode)); /*復(fù)制結(jié)點(diǎn)*/ s->exp=pa->exp;s->coef=pa->coef; tc->next=s;tc=s; pa=pa->next; } tc->next=NULL;}voidmain(){ PolyNode*ha,*hb,*hc; PolyArraya={{1.2,0},{2.5,1},{3.2,3},{-2.5,5}}; PolyArrayb={{-1.2,0},{2.5,1},{3.2,3},{2.5,5},{5.4,10}}; CreateListR(ha,a,4); CreateListR(hb,b,5); printf("原多項(xiàng)式A:");DispPoly(ha); printf("原多項(xiàng)式B:");DispPoly(hb); Sort(ha); Sort(hb); printf("有序多項(xiàng)式A:");DispPoly(ha); printf("有序多項(xiàng)式B:");DispPoly(hb); Add(ha,hb,hc); printf("多項(xiàng)式相加:");DispPoly(hc);}實(shí)驗(yàn)2求解迷宮問題的所有路徑

及最短路徑程序（堆棧）改進(jìn)教材中3.2.4節(jié)中的求解迷宮問題程序，要求輸出如圖所示的迷宮的所有路徑，并求出最短路徑成都及最短路徑。0012340123455入口出口/*文件名:實(shí)驗(yàn)2.cpp*/#include<stdio.h>#defineM6 /*行數(shù)*/#defineN6 /*列數(shù)*/#defineMaxSize100 /*棧最多元素個(gè)數(shù)*/intmg[M+1][N+1]={ /*一個(gè)迷宮,其四周要加上均為1的外框*/{1,1,1,1,1,1},{1,0,0,0,1,1},{1,0,1,0,0,1},{1,0,0,0,1,1},{1,1,0,0,0,1},{1,1,1,1,1,1}};struct{ inti;intj;intdi;}Stack[MaxSize],Path[MaxSize]; /*定義棧和存放最短路徑的數(shù)組*/inttop=-1; /*棧指針*/intcount=1; /*路徑數(shù)計(jì)數(shù)*/intminlen=MaxSize; /*最短路徑長度*/voidmgpath() /*路徑為:(1,1)->(M-2,N-2)*/{ inti,j,di,find,k; top++; /*進(jìn)棧*/ Stack[top].i=1; Stack[top].j=1; Stack[top].di=-1;mg[1][1]=-1;/*初始結(jié)點(diǎn)進(jìn)棧*/ while(top>-1) /*棧不空時(shí)循環(huán)*/ { i=Stack[top].i;j=Stack[top].j;di=Stack[top].di; if(i==M-2&&j==N-2) /*找到了出口,輸出路徑*/ { printf("%4d:",count++); for(k=0;k<=top;k++) { printf("(%d,%d)",Stack[k].i,Stack[k].j); if((k+1)%5==0)printf("\n\t");/*輸出時(shí)每5個(gè)結(jié)點(diǎn)換一行*/ } printf("\n"); if(top+1<minlen) /*比較找最短路徑*/ { for(k=0;k<=top;k++) Path[k]=Stack[k]; minlen=top+1; } mg[Stack[top].i][Stack[top].j]=0;/*讓該位置變?yōu)槠渌窂娇勺呓Y(jié)點(diǎn)*/ top--; i=Stack[top].i;j=Stack[top].j;di=Stack[top].di; } find=0; while(di<4&&find==0)/*找下一個(gè)可走結(jié)點(diǎn)*/ { di++; switch(di) { case0:i=Stack[top].i-1;j=Stack[top].j;break; case1:i=Stack[top].i;j=Stack[top].j+1;break; case2:i=Stack[top].i+1;j=Stack[top].j;break; case3:i=Stack[top].i,j=Stack[top].j-1;break; } if(mg[i][j]==0)find=1; } if(find==1) /*找到了下一個(gè)可走結(jié)點(diǎn)*/ { Stack[top].di=di; /*修改原棧頂元素的di值*/ top++;Stack[top].i=i;Stack[top].j=j;Stack[top].di=-1;/*下一個(gè)可走結(jié)點(diǎn)進(jìn)棧*/ mg[i][j]=-1; /*避免重復(fù)走到該結(jié)點(diǎn)*/ } else /*沒有路徑可走,則退棧*/ { mg[Stack[top].i][Stack[top].j]=0;/*讓該位置變?yōu)槠渌窂娇勺呓Y(jié)點(diǎn)*/ top--; } } printf("最短路徑如下:\n"); printf("長度:%d\n",minlen); printf("路徑:"); for(k=0;k<minlen;k++) { printf("(%d,%d)",Path[k].i,Path[k].j); if((k+1)%5==0)printf("\n\t");/*輸出時(shí)每5個(gè)結(jié)點(diǎn)換一行*/ } printf("\n");}voidmain(){ printf("迷宮所有路徑如下:\n"); mgpath();}/實(shí)驗(yàn)3求一個(gè)串中出現(xiàn)的第一個(gè)

最長重復(fù)字符串（串）編寫一個(gè)程序，求串s中出現(xiàn)的第一個(gè)最長重復(fù)字符串的下標(biāo)和長度。*文件名:實(shí)驗(yàn)3.cpp*/#include<stdio.h>#include<string.h>#include<malloc.h>#defineMaxSize100typedefstruct{ charch[MaxSize]; intlen; /*串長*/}SqString;externvoidStrAssign(SqString&,char[]);/*在algo4-1.cpp文件中*/externvoidDispStr(SqString);SqString*MaxSubstr(SqStrings){ SqString*sp; intindex=0,length=0,length1,i=0,j,k; while(i<s.len) { j=i+1; while(j<s.len) { if(s.ch[i]==s.ch[j])/*找一子串,其序號為i,長度為length1*/ { length1=1; for(k=1;s.ch[i+k]==s.ch[j+k];k++) length1++; if(length1>length)/*將較大長度者賦給index與length*/ { index=i; length=length1; } j+=length1; } else j++; } i++;/*繼續(xù)掃描第i字符之后的字符*/ } sp=(SqString*)malloc(sizeof(SqString)); sp->len=length; for(i=0;i<length;i++) sp->ch[i]=s.ch[index+i]; returnsp;}voidmain(){ charstr[MaxSize]; SqStrings,*sp; printf("輸入串:"); gets(str); StrAssign(s,str); /*創(chuàng)建串s*/ sp=MaxSubstr(s); printf("求最長重復(fù)子串:\n"); printf("原串:"); DispStr(s); printf("最長重復(fù)子串:"); /*輸出最長重復(fù)子串*/ DispStr(*sp);}實(shí)驗(yàn)4求解背包問題（遞歸）背包問題：設(shè)有不同價(jià)值、不同重量的物品n件，求從這n件物品中選取一部分物品的方案，使選中物品的總重量不超過指定的限制重量，但選中物品的價(jià)值之和為最大。編寫一個(gè)程序求解背包問題。/*文件名:實(shí)驗(yàn)4.cpp*/#include<stdio.h>#defineN100intlimitw; /*限制的總重量*/inttotv; /*全部物品的總價(jià)*/intmaxv;intoption[N],cop[N];struct{ intweight; intvalue;}a[N];intn; /*物品種數(shù)次*/voidfind(inti,inttw,inttv){ intk; if(tw+a[i].weight<=limitw) { cop[i]=1; if(i<n-1) find(i+1,tw+a[i].weight,tv); else { for(k=0;k<n;k++) option[k]=cop[k]; maxv=tv; } cop[i]=0; } if(tv-a[i].value>maxv) if(i<n-1) find(i+1,tw,tv-a[i].value); else { for(k=0;k<n;k++) option[k]=cop[k]; maxv=tv-a[i].value; }}voidmain(){ intk,w,v; printf("物品種數(shù):"); scanf("%d",&n); for(totv=0,k=0;k<n;k++) { printf("第%d種物品(重量,價(jià)值):",k+1); scanf("%d,%d",&w,&v); a[k].weight=w; a[k].value=v; totv+=v; } printf("背包所能承受的總重量:"); scanf("%d",&limitw); maxv=0; for(k=0;k<n;k++) cop[k]=0; find(0,0,totv); printf("最佳裝填方案是:\n"); for(k=0;k<n;k++) if(option[k]) printf("第%d種物品\n",k+1); printf("總價(jià)值=%d\n",maxv);}實(shí)驗(yàn)5求二叉樹中從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑對一棵二叉樹，編寫程序完成下述功能：輸出所有的葉子結(jié)點(diǎn)輸出所有從葉子結(jié)點(diǎn)到根節(jié)點(diǎn)的路徑輸出上述路徑中的第一條最長的路徑/*文件名:實(shí)驗(yàn)5.cpp*/#include<stdio.h>#include<malloc.h>#defineMaxSize100typedefcharElemType;typedefstructnode{ ElemTypedata; /*數(shù)據(jù)元素*/ structnode*lchild; /*指向左孩子*/ structnode*rchild; /*指向右孩子*/}BTNode;externvoidCreateBTNode(BTNode*&b,char*str);/*在algo7-1.cpp文件中*/externvoidDispBTNode(BTNode*b);voidAllPath(BTNode*b){ structsnode { BTNode*node; /*存放當(dāng)前結(jié)點(diǎn)指針*/ intparent; /*存放雙親結(jié)點(diǎn)在隊(duì)列中的位置*/ }Qu[MaxSize]; /*定義順序隊(duì)列*/ intfront,rear,p; /*定義隊(duì)頭和隊(duì)尾指針*/front=rear=-1; /*置隊(duì)列為空隊(duì)列*/ rear++;Qu[rear].node=b; /*根結(jié)點(diǎn)指針進(jìn)入隊(duì)列*/ Qu[rear].parent=-1; /*根結(jié)點(diǎn)沒有雙親結(jié)點(diǎn)*/while(front<rear) /*隊(duì)列不為空*/{ front++; b=Qu[front].node; /*隊(duì)頭出隊(duì)列*/ if(b->lchild==NULL&&b->rchild==NULL) /**b為葉子結(jié)點(diǎn)*/ { printf("%c到根結(jié)點(diǎn)路徑:",b->data); p=front; while(Qu[p].parent!=-1) { printf("%c",Qu[p].node->data); p=Qu[p].parent; } printf("%c\n",Qu[p].node->data); } if(b->lchild!=NULL) /*左孩子入隊(duì)列*/ { rear++; Qu[rear].node=b->lchild; Qu[rear].parent=front; } if(b->rchild!=NULL) /*右孩子入隊(duì)列*/ { rear++; Qu[rear].node=b->rchild; Qu[rear].parent=front; } }}voidAllPath1(BTNode*b,ElemTypepath[],intpathlen){ inti; if(b!=NULL) { if(b->lchild==NULL&&b->rchild==NULL) /**b為葉子結(jié)點(diǎn)*/ { printf("%c到根結(jié)點(diǎn)路徑:%c",b->data,b->data); for(i=pathlen-1;i>=0;i--) printf("%c",path[i]); printf("\n"); } else { path[pathlen]=b->data; /*將當(dāng)前結(jié)點(diǎn)放入路徑中*/ pathlen++; /*路徑長度增1*/ AllPath1(b->lchild,path,pathlen); /*遞歸掃描左子樹*/ AllPath1(b->rchild,path,pathlen); /*遞歸掃描右子樹*/ pathlen--; /*恢復(fù)環(huán)境*/ } }}voidLongPath(BTNode*b,ElemTypepath[],intpathlen,ElemTypelongpath[],int&longpathlen){ inti; if(b==NULL) { if(pathlen>longpathlen) /*若當(dāng)前路徑更長,將路徑保存在longpath中*/ { for(i=pathlen-1;i>=0;i--) longpath[i]=path[i]; longpathlen=pathlen; } } else { path[pathlen]=b->data; /*將當(dāng)前結(jié)點(diǎn)放入路徑中*/ pathlen++; /*路徑長度增1*/ LongPath(b->lchild,path,pathlen,longpath,longpathlen); /*遞歸掃描左子樹*/ LongPath(b->rchild,path,pathlen,longpath,longpathlen); /*遞歸掃描右子樹*/ pathlen--; /*恢復(fù)環(huán)境*/ }}voidDispLeaf(BTNode*b){ if(b!=NULL) { if(b->lchild==NULL&&b->rchild==NULL) printf("%c",b->data); else { DispLeaf(b->lchild); DispLeaf(b->rchild); } }}voidmain(){ BTNode*b; ElemTypepath[MaxSize],longpath[MaxSize]; inti,longpathlen=0; CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"); printf("\n二叉樹b:");DispBTNode(b);printf("\n\n"); printf("b的葉子結(jié)點(diǎn):");DispLeaf(b);printf("\n\n"); printf("AllPath:\n");AllPath(b);printf("\n"); printf("AllPath1:\n");AllPath1(b,path,0);printf("\n"); LongPath(b,path,0,longpath,longpathlen); printf("第一條最長路徑長度:%d\n",longpathlen); printf("第一條最長路徑:"); for(i=longpathlen;i>=0;i--) printf("%c",longpath[i]); printf("\n\n");}實(shí)驗(yàn)6構(gòu)造哈夫曼樹構(gòu)造一棵哈夫曼樹，輸出對應(yīng)的哈夫曼編碼和平均查找長度。并對下表所示的數(shù)據(jù)進(jìn)行驗(yàn)證。單詞TheofatoandinthatheisatonforHisarebe出現(xiàn)頻度1192677541518462450242195190181174157138124123/*文件名:實(shí)驗(yàn)6.cpp*/#include<stdio.h>#include<string.h>#defineN50 /*葉子結(jié)點(diǎn)數(shù)*/#defineM2*N-1 /*樹中結(jié)點(diǎn)總數(shù)*/typedefstruct{ chardata[5]; /*結(jié)點(diǎn)值*/ intweight; /*權(quán)重*/ intparent; /*雙親結(jié)點(diǎn)*/ intlchild; /*左孩子結(jié)點(diǎn)*/ intrchild; /*右孩子結(jié)點(diǎn)*/}HTNode;typedefstruct{ charcd[N]; /*存放哈夫曼碼*/ intstart;}HCode;voidCreateHT(HTNodeht[],intn){ inti,k,lnode,rnode; intmin1,min2; for(i=0;i<2*n-1;i++) /*所有結(jié)點(diǎn)的相關(guān)域置初值-1*/ ht[i].parent=ht[i].lchild=ht[i].rchild=-1; for(i=n;i<2*n-1;i++) /*構(gòu)造哈夫曼樹*/ { min1=min2=32767; /*lnode和rnode為最小權(quán)重的兩個(gè)結(jié)點(diǎn)位置*/ lnode=rnode=-1; for(k=0;k<=i-1;k++) if(ht[k].parent==-1) /*只在尚未構(gòu)造二叉樹的結(jié)點(diǎn)中查找*/ { if(ht[k].weight<min1) { min2=min1;rnode=lnode; min1=ht[k].weight;lnode=k; } elseif(ht[k].weight<min2) { min2=ht[k].weight;rnode=k; } } printf("%d\n",rnode); ht[lnode].parent=i;ht[rnode].parent=i; ht[i].weight=ht[lnode].weight+ht[rnode].weight; ht[i].lchild=lnode;ht[i].rchild=rnode; }}voidCreateHCode(HTNodeht[],HCodehcd[],intn){ inti,f,c; HCodehc; for(i=0;i<n;i++) /*根據(jù)哈夫曼樹求哈夫曼編碼*/ { hc.start=n;c=i; f=ht[i].parent; while(f!=-1) /*循序直到樹根結(jié)點(diǎn)*/ { if(ht[f].lchild==c) /*處理左孩子結(jié)點(diǎn)*/ hc.cd[hc.start--]='0'; else /*處理右孩子結(jié)點(diǎn)*/ hc.cd[hc.start--]='1'; c=f;f=ht[f].parent; } hc.start++; /*start指向哈夫曼編碼最開始字符*/ hcd[i]=hc; }}voidDispHCode(HTNodeht[],HCodehcd[],intn){ inti,k; intsum=0,m=0,j; printf("輸出哈夫曼編碼:\n");/*輸出哈夫曼編碼*/ for(i=0;i<n;i++) { j=0; printf("%s:\t",ht[i].data); for(k=hcd[i].start;k<=n;k++) { printf("%c",hcd[i].cd[k]); j++; } m+=ht[i].weight; sum+=ht[i].weight*j; printf("\n"); } printf("\n平均長度=%g\n",1.0*sum/m);}voidmain(){ intn=15,i; char*str[]={"The","of","a","to","and","in","that","he","is","at","on","for","His","are","be"}; intfnum[]={1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123}; HTNodeht[M]; HCodehcd[N]; for(i=0;i<n;i++) { strcpy(ht[i].data,str[i]); ht[i].weight=fnum[i]; } printf("\n"); CreateHT(ht,n); CreateHCode(ht,hcd,n); DispHCode(ht,hcd,n); printf("\n");}實(shí)驗(yàn)7采用克魯斯卡爾算法求最小生成樹編程序?qū)o向帶權(quán)圖G采用克魯斯卡爾算法輸出該圖的最小生成樹/*文件名:實(shí)驗(yàn)7.cpp*/#include<stdio.h>#include"graph.h"#defineINF32767/*INF表示∞*/#defineMAXE100 /*最多邊數(shù)*/typedefstruct{ intu; /*邊的起始頂點(diǎn)*/intv; /*邊的終止頂點(diǎn)*/intw; /*邊的權(quán)值*/ }Edge;externvoidDispMat(MGraph); /*外部函數(shù)在algo9-1.cpp中*/voidSortEdge(MGraphg,EdgeE[]) /*從鄰接矩陣產(chǎn)生權(quán)值遞增的邊集*/{ inti,j,k=0; Edgetemp; for(i=0;i<g.vexnum;i++) for(j=0;j<g.vexnum;j++) if(g.edges[i][j]<INF) { E[k].u=i; E[k].v=j; E[k].w=g.edges[i][j]; k++; } for(i=1;i<k;i++) /*按權(quán)值遞增有序進(jìn)行直接插入排序*/ { temp=E[i]; j=i-1; /*從右向左在有序區(qū)E[0..i-1]中找E[i]的插入位置*/ while(j>=0&&temp.w<E[j].w) { E[j+1]=E[j];/*將權(quán)值大于E[i].w的記錄后移*/ j--; } E[j+1]=temp;/*在j+1處插入E[i]*/ }}voidKruskal(EdgeE[],intn,inte){ inti,j,m1,m2,sn1,sn2,k; intvset[MAXE]; for(i=0;i<n;i++)vset[i]=i; /*初始化輔助數(shù)組*/ k=1; /*k表示當(dāng)前構(gòu)造最小生成樹的第幾條邊,初值為1*/ j=0; /*E中邊的下標(biāo),初值為0*/ while(k<n) /*生成的邊數(shù)小于n時(shí)循環(huán)*/ { m1=E[j].u;m2=E[j].v;/*取一條邊的頭尾頂點(diǎn)*/ sn1=vset[m1];sn2=vset[m2]; /*分別得到兩個(gè)頂點(diǎn)所屬的集合編號*/ if(sn1!=sn2) /*兩頂點(diǎn)屬于不同的集合,該邊是最小生成樹的一條邊*/ { printf("(%d,%d):%d\n",m1,m2,E[j].w); k++;/*生成邊數(shù)增1*/ for(i=0;i<n;i++) /*兩個(gè)集合統(tǒng)一編號*/ if(vset[i]==sn2) /*集合編號為sn2的改為sn1*/ vset[i]=sn1; } j++; /*掃描下一條邊*/ }}voidmain(){ inti,j,u=3; MGraphg; EdgeE[MAXE]; intA[MAXV][11]; g.vexnum=6;g.arcnum=10; for(i=0;i<g.vexnum;i++) for(j=0;j<g.vexnum;j++) A[i][j]=INF; A[0][1]=5;A[0][2]=8;A[0][3]=7;A[0][5]=3; A[1][2]=4; A[2][3]=5;A[2][5]=9; A[3][4]=5; A[4][5]=1; for(i=0;i<g.vexnum;i++) for(j=0;j<g.vexnum;j++) A[j][i]=A[i][j]; for(i=0;i<g.vexnum;i++) /*建立圖9.15的鄰接矩陣*/ for(j=0;j<g.vexnum;j++) g.edges[i][j]=A[i][j]; SortEdge(g,E); printf("\n"); printf("圖G的鄰接矩陣:\n"); DispMat(g); printf("\n"); printf("克魯斯卡爾算法求解結(jié)果:\n"); Kruskal(E,g.vexnum,g.arcnum); printf("\n");}實(shí)驗(yàn)8統(tǒng)計(jì)一個(gè)字符串中出現(xiàn)的字符及其次數(shù)編寫一個(gè)程序讀入一個(gè)字符串，統(tǒng)計(jì)該字符串中出現(xiàn)的字符及其次數(shù)，然后輸出結(jié)果。要求用一個(gè)二叉樹保存處理結(jié)果，字符串中的每個(gè)不同的字符用樹描述，每個(gè)結(jié)點(diǎn)包含4個(gè)域，格式為：字符該字符的出現(xiàn)次數(shù)指向ASCII碼小于該字符的左子樹指針指向ASCII碼大于該字符的右子樹指針/*文件名:實(shí)驗(yàn)8.cpp*/#include<stdio.h>#include<string.h>#include<malloc.h>#defineMAXWORD100typedefstructtnode{ charch;/*字符*/ intcount;/*出現(xiàn)次數(shù)*/ structtnode*lchild,*rchild;}BTree;voidCreaTree(BTree*&p,charc)/*采用遞歸方式構(gòu)造一棵二叉排序樹*/{ if(p==NULL) /*p為NULL,則建立一個(gè)新結(jié)點(diǎn)*/ { p=(BTree*)malloc(sizeof(BTree)); p->ch=c; p->count=1; p->lchild=p->rchild=NULL; } elseif(c==p->ch) p->count++; elseif(c<p->ch) CreaTree(p->lchild,c); else CreaTree(p->rchild,c);}voidInOrder(BTree*p) /*中序遍歷BST*/{ if(p!=NULL) { InOrder(p->lchild); /*中序遍歷左子樹*/ printf("%c(%d)\n",p->ch,p->count);/*訪問根結(jié)點(diǎn)*/ InOrder(p->rchild); /*中序遍歷右子樹*/ }}voidmain(){ BTree*root=NULL; inti=0; charstr[MAXWORD]; printf("\n"); printf("輸入字符串:"); gets(str); while(str[i]!='\0') { CreaTree(root,str[i]); i++; } printf("字符及出現(xiàn)次數(shù):\n"); InOrder(root); printf("\n");}實(shí)驗(yàn)9實(shí)現(xiàn)可變長度的字符串序列快速排序算