2023年树的实验报告

２023-２023学年第一学期数据结构课内实验报告学院：计算机学院专业：计算机科学与技术姓名:学号:指导老师:实验题目实验目的1．掌握二叉树的建立,递归遍历（先序，中序,后序），打印树状二叉树，计算叶子节点的个数。２.二叉树的非递归遍历3.掌握哈夫曼树的基本算法。实验内容1.树的递归与非递归遍历（1)从键盘接受输入先序序列，以二叉链表作为存储结构,建立二叉树(以先序来建立）,(2)将此二叉树按照“树状形式”打印输出,(3)对其进行遍历(先序、中序和后序)，(4)最后将遍历结果打印输出在遍历算法中（5)规定至少有一种遍历采用非递归方法2.哈夫曼基本规定:(１)从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树；(２)打印每一个字符相应的哈夫曼编码。(3)对从终端读入的字符串进行编码，并显示编码结果。四:模块化分各个模块具体的功能描述。ｖｏｉdPrｅＯrｄer(BTreeｒoot)；先序遍历ｖoｉdＩnＯrｄer（BTreeｒooｔ)；中序遍历vｏidPostOrder（BTreerｏot);后序遍历voidPｒeleaf(BTreｅｒoot);先序求叶子节点个数ｖoidPrinｔfTreｅ(BTｒｅeroot，iｎth）;打印二叉树intPoｓtHeｉgｈt(ＢＴreeｒoot）);后序求树的深度voiｄIｎitTree（BiTｒee*bｔ）;初始化树intＩniｔＳtaｃｋ(Sｔack*ｔｏp)；初始化栈BiＴｎoｄｅ*Creａte();//扩展结点创建二叉树intPush（Sｔacｋ＊top,BiTｒeep);入栈intPoｐ(Sｔaｃk＊tｏp,BｉTree*p);出栈iｎtＧetＴｏp(Stacktoｐ,BiTrｅep);取栈顶元素vｏｉdPrｅＳtａck(BTreｅrｏot);//非递归先序遍历ｖoidSｅleｃt(HＴreeht,intpos/＊寻找的范围＊/，inｔ*s1,int*ｓ２)／/查找最小的两个节点的下标voidCｒeatHuｆfmａｎTree（ＨTｒｅｅhｔ，intｗ[],iｎｔn）/／创建哈夫曼树vｏiOutpｕｔ(ＨＴreeht，intｎ)/／输出哈夫曼树ｖoidＣodeHuffmanＴreｅ(HTｒeeht,HCｏdｅhc,ｉntn）／/编码vｏｉdOutpuｔCode（HCodｅｈc,intｗ[]，ｉnｔｎ)//输出编码具体设计及运营结果voｉdprｅＯrder(BiTreｅbt）ﻩ//先序遍历。{ﻩiｆ（bt!=ＮULＬ) ｛ﻩﻩpriｎtf("％c＂，bｔ->data）;ﻩﻩprｅＯｒder(bｔ->LChｉld); ﻩpｒeOrder（bt->RＣhiｌd）; ｝｝voiｄIｎOrder(BiTreｅｂt） //中序遍历。{ﻩif(ｂt！=NUＬL) ｛ﻩ InOrｄｅｒ（bt->ＬChild); ﻩｐｒinｔf（＂％ｃ",bt->dａｔa); ﻩＩnOｒｄｅr(bt->RChild)；ﻩ｝}voidPoｓtOｒder(BiＴrｅebt) /／后序遍历。{ ｉf（ｂt!=NULL）ﻩ{ ﻩPostOrdeｒ(ｂｔ->LＣhｉld); ﻩPostOrder(bt－>RChilｄ）; ﻩprintf("%c＂,bt->data);ﻩ}}voidTｒavｅr(BiTreebt)｛ }iｎtPoｓtTreｅＤeptｈ(ＢｉTｒeｅbt)｛ﻩinｔhl，ｈr,ｍax; if(bt！=ＮULL) { ﻩhl=PoｓtTreeDepｔｈ(ｂt->LＣｈild); ﻩhr=PostTrｅeDeｐth(bt-＞RCｈｉld); ﻩmax=hｌ>hｒ?hl:hｒ; ｒｅtｕrn(mａx+1); ｝ﻩｅlseﻩﻩｒｅｔurn0;｝voidPrｅStack(ＢｉTreｅbt) //非递归遍历｛ BiTrｅep; LinkStａcks; InitSｔａck(&s);ﻩ/／p=bt; PushStaｃｋ(ｓ,ｂt); wｈｉlｅ(！Iseｍpty(s)) ｛ﻩﻩPoｐSｔacｋ（s,&ｐ）；ﻩﻩ priｎtｆ("％c",p->daｔa); if(p-＞ＲChild!=NUＬL) PuｓhＳtack(s,p->RChｉld);ﻩﻩﻩif(p－＞LChilｄ!=ＮULL)ﻩﻩ ﻩPｕshStaｃk(s，ｐ->LChilｄ); ﻩ｝}/＊voidPreStａｃｋ(BｉＴreebt) //非递归先序遍历｛ﻩBｉＴｒｅep; ＬinｋStａcks; IｎitStacｋ(＆s);ﻩｐ=ｂt；ﻩｗhile(ｐ|｜！Isempty(s）） ｛ ｉｆ(ｐ）ﻩ {ﻩ prinｔｆ（"%ｃ＂,p-＞ｄata）; ﻩＰusｈＳｔack(s，p);ﻩ ｐ=p-＞ＬChild； }ﻩ else { ﻩＰopStaｃk（s,&p)；ﻩﻩ ｐ=p->ＲCｈild; ﻩ}ﻩ}}*/voidPrｉntＴree(BiＴreebｔ,ｉntnLaｙer）｛ ｉnti; if（bt==NＵLL） ﻩreturｎ;ﻩPrinｔTｒee(ｂt-＞RChiｌd,nLayer＋1）；ﻩfor(ｉ=0;i<ｎLayer;i++）ﻩﻩprinｔf(＂＂）；ﻩpｒｉntf(＂%ｃ\n",bt-＞dａta); PｒintＴrｅe(ｂt－＞LＣhild,nLayer+１);}voｉdLｅａfＴree(BｉTreｅbt)ﻩ／／树的叶子结点遍历｛ ｉｆ（bt!=NUＬL)ﻩ{ if(bt-＞ＬChild==NＵＬL&＆ｂt－>RChｉlｄ＝＝NＵＬＬ) ﻩpｒintf("%c"，bt->dａta);ﻩ LeafTree(ｂｔ->LChｉld);ﻩ LeａfＴrｅe(bt->RChild);ﻩ}}voiｄＴrａvｅｌ(ＢiTreｅbt)ﻩ ﻩ／/树的按层遍历{ BiTrｅep; LinｋＱuｅｕeQ; IｎiｔQueuｅ(＆Q); iｆ(ｂｔ＝＝NULＬ) ﻩreturn;ﻩp=bt; EnterQueｕe(&Ｑ,ｐ）; while(Q.front!=Q.rｅar)ﻩ｛ ﻩDeｌｅteQuｅue(&Ｑ,＆p);ﻩﻩprinｔｆ（"%c＂,p->ｄａta);ﻩ if(p－>ＬChild） ﻩEnterQuｅuｅ(&Q,p－>LChｉld);ﻩ if(p-＞ＲChild)ﻩﻩ EnｔerQueｕe(&Ｑ,p->RCｈild）;ﻩ}｝2:哈弗曼voidＣｒｅat(HｕｆfmanTreｅｈt，intｗ[],chaｒp[]，intn)/／构造哈弗曼树。{ﻩints1,s2,i; fｏr（i=1;i<=n;ｉ＋+）／／前n个叶子结点的初始化 ｛ﻩﻩht［i].weigｈt=ｗ[i]； ﻩhｔ[i].ｐaｒent=0； hｔ[i].LChild＝0;ﻩ ht［i］.RChild＝０; ｝ﻩfor(i=n+1；i<=2*ｎ-1;i＋+)/／权值的初始化。ﻩ｛ﻩ select(ht，i-1,＆s１，&ｓ2）；ﻩﻩhｔ［i].weｉghｔ=ht[ｓ１].weigｈｔ+ht[s2］.ｗeigｈt;ﻩﻩht[i］.pａｒeｎｔ=0；ﻩﻩｈｔ[s１].parenｔ=i;ﻩﻩｈｔ[s2］.pａreｎt=i; ht［i].LＣｈild＝s1; ｈt[i］.RChild=ｓ2;ﻩ}}//生成哈弗曼树的函数编码。voiｄOｒdeｒHuffmaｎ(HuｆｆｍanTreｅｈt,Ｈuffｍａncodehc,chａｒｓtｒ[]，iｎtm)//根据哈弗曼树构成哈弗曼编码表ｈｃ。{ﻩiｎtq[N]；ﻩchａｒ*cd；/／临时存放编码串。ﻩinｔc,p，i;//ｃ,ｐ分别为孩子和双亲。 iｎtstaｒt;//制定编码cd的起始位置。ﻩcd=(cｈaｒ*)mａlloc（m*sizeof(chａr）);ﻩcd[ｍ-1]＝'\0';／/最后一位置放上字符串的结束标志。 ｉ＝0；ﻩｗｈile（i<m) {ﻩﻩsｗitcｈ(str［i]）ﻩﻩ{ ｃａｓe's＇:q[i］=3;break; ﻩcase＇ｔ'：q[i]=4;ｂreak;ﻩﻩcase'a＇:q[i］=2;break;ﻩﻩcａｓe'e'：q［i]=6；brｅak; deｆａult：ｂｒeak;ﻩ ｝ start＝m-１;ﻩ c=q[i];ﻩ p=ht[q[ｉ]].ｐａｒent; ﻩwhile（p!＝０)ﻩ { ﻩﻩ--stａrｔ; ﻩiｆ（ｈt[ｐ].ＬＣhild==c)ﻩ ﻩｃd[ｓｔart]=＇0';//左孩子生成0 ﻩeｌsｅﻩﻩ ﻩ//右孩子生成1ﻩ ﻩ cd[sｔarｔ］='１'; ﻩc=p; ﻩp=ht［p］.pａｒent; } hｃ[i]=(char*)malｌoc((ｍ－staｒt)*sizｅof（chaｒ)); strcpｙ(hc[ｉ],＆cd[stａrｔ]）；ﻩ prｉｎtf("%s",hc[i])； i＋＋；ﻩ｝ﻩﻩｆｒee(cd);｝ｖoidpｒｉnt（HｕffmanTreeht，ｉｎtｎ){ intｉ; ｆoｒ(i=１;i<=2*n-1；i++) ﻩpｒinｔf（"％４d％4d％4d\n"，ht［i].weｉght，ｈt［i]．LChild,ht[i]．RＣhｉld）；}调试情况，设计技巧及体会1.对自己的设计进行评价,指出合理和局限性之处，提出改善方案；打印树状二叉树的模块没有能按照自然数的形式打印，有待改善。２．对设计及调试过程的心得体会。源程序清单（电子版)／*建立一棵用二叉链表方式存储的二叉树，并对其进行遍历(先序、中序和后序）,打印输出遍历结果。1:从键盘接受输入先序序列,以二叉链表作为存储结构,建立二叉树（以先序来建立)，2:将此二叉树按照“树状形式”打印输出,3：对其进行遍历(先序、中序和后序)，4:最后将遍历结果打印输出在遍历算法中５:规定至少有一种遍历采用非递归方法。*／#iｎclude<ｓtdｉo．h＞#includｅ＜ｓtrｉng.h>＃ｉncludｅ<stdlｉb．h>#deｆｉｎeFAＬSE0#defｉnｅTRＵＥ1ｔyｐｅdｅfstruｃtＮoｄｅ{ﻩｃhａrｄaｔa; strucｔNodｅ*ＬChild; sｔrｕctNode*RChild;}BitNoｄｅ，*BｉTree;ｔｙpｅdefstruｃtｎod{ BiTreｅelem;ﻩｓtructnod*ｎｅxｔ;}SeqStacｋ,*LｉnｋStａck;voiｄIｎitStａcｋ(LinkＳｔaｃk*top）{ (*ｔｏｐ)=(LｉｎkStaｃｋ）malloc(sizeof(ＳeqStack)); (*top)－>nｅxt=NULＬ;}ｉntIsempty(LiｎkStａｃｋｔop)｛ﻩiｆ(tｏp-＞neｘt＝=NULL) rｅturnTRUE； reｔurnFALSE;}intＰｕshSｔａck（LinkStａcktｏp,BiTreex){ LｉｎkStａｃktemp； temp＝(SeqStacｋ＊)ｍalｌoc（sizｅｏf(SeqＳtack)); iｆ(teｍp=＝ＮULL)ﻩﻩreturnFＡLSE; teｍp->elｅm=x; temp->next=top->nｅxｔ;ﻩtop－>nｅxt=teｍp;ﻩrｅturnＴＲUE;}intPｏpStack(LｉnkＳtacktop，BiTree＊x）{ LinkSｔackteｍp;ﻩtemp=ｔｏp－>nｅxt;ﻩｉｆ(temｐ＝＝NULL)ﻩﻩretuｒnFALSＥ; *x＝temp-＞ｅｌeｍ;ﻩtｏp->ｎexｔ=ｔeｍp－>ｎeｘt; ｆrｅｅ(temｐ)；ﻩﻩreturｎTRUE;}ｉntCreatBiＴrｅe（BiTreｅ＊bｔ)//树的先序建立｛ charch; ｃh=getｃhaｒ(); iｆ(ch=='#')ﻩ ＊ｂｔ＝NULL; elsｅ ｛ﻩ *bt=(BｉｔNｏde*）ｍａlｌｏc(sｉzeｏf(ＢｉtNｏde)）; ﻩif(*bt==NULＬ) ﻩﻩretuｒn0; ﻩ（*bt)->dａｔa=ｃh; ＣreatBｉＴrｅe(&（(*bt)->LChｉｌd)）; ﻩＣreａtBｉＴree(&((*bｔ)->RChｉld)); }ﻩreturn１;}tyｐedefsｔｒｕｃtnode｛ﻩＢｉTreew； sｔructnode*ｎｅxt;}LinkNode;ｔyｐedefstｒucｔ{ﻩLinkNode*front;ﻩＬinkＮodｅ*rｅar;｝LｉnkQｕeue;ｉｎtＩnitＱuｅue(LｉｎkQuｅｕｅ＊Ｑ）｛ Ｑ->fronｔ=(LinｋNode*)maｌloc(siｚeof(LｉｎkNode)）; if(Q-＞froｎt!＝NＵLＬ) { ﻩQ->rear=Q－>fｒoｎt;ﻩﻩQ->ｆｒoｎｔ->ｎext=NULL;ﻩ reｔuｒnＴRＵE; ｝ﻩelseﻩﻩreｔurnFALSＥ;}intＥntｅrQueｕe(LiｎkQueｕe*Q,BiTreex){ﻩLinkNodｅ*ＮeｗNoｄe;ﻩNeｗNｏdｅ＝(LinkNode*)malloc(sizeof(LiｎｋＱueue)); if(NewＮode!=NULL) { ﻩNｅwNｏde-＞ｗ＝x; ﻩNｅwＮode->next＝NＵＬL;ﻩﻩQ-＞reａｒ->nexｔ=NｅwＮｏｄe;ﻩ Ｑ->rear＝NｅwNｏｄe; ｒeturnTRUＥ;ﻩ}ﻩelｓｅﻩ ｒetｕrnFＡＬSE;}intＤelｅteQuｅｕe（LinｋQｕeue*Q，ＢiTreｅ*x){ﻩLｉnkNoｄe*ｐ; if(Q->ｆrｏnt==Q->reaｒ） returnＦALSE；ﻩp=Q-＞froｎt-＞next; Q->front->nexｔ=ｐ-＞ｎｅxt;ﻩif(Q－>ｒｅar==p) ﻩQ-＞rear=Q-＞froｎｔ;ﻩ*ｘ=p->w；ﻩfreｅ(p）；ﻩreturnTＲUＥ;｝voｉｄpreOrdeｒ（BiTreeｂｔ)ﻩ/／先序遍历。{ﻩiｆ（bt！=NULL) { prｉｎｔｆ("%c＂,bt->ｄata)；ﻩﻩｐrｅOrder(bt-＞ＬＣhild);ﻩ pｒｅＯrder(bt->RＣｈilｄ）； }}voidInＯrdｅr(ＢｉTｒeebt)ﻩ//中序遍历。｛ if（ｂｔ！＝NULＬ) { ﻩInＯrder（ｂt->LChｉld); ｐrintf(＂%ｃ",bt->daｔa)； InOrｄer(ｂt->RChild);ﻩ}}voiｄPoｓtOrder(BiTｒeeｂt）ﻩ／/后序遍历。｛ﻩif(bt!＝NULL） { PostOｒdeｒ(ｂt->ＬChiｌd); PosｔOrdeｒ（bt-＞RChild）;ﻩ prinｔf("%ｃ"，ｂｔ-＞daｔa);ﻩ}}voidTｒaver(ＢｉTｒeebt)｛ﻩ}iｎtＰｏstTreeDepth(BiTｒeｅbt)｛ﻩｉnthｌ,hｒ,ｍａx；ﻩｉｆ（bｔ!=ＮULL) ｛ hｌ＝PosｔTreeＤｅｐth(bt->ＬChｉld);ﻩﻩhr=ＰoｓtTreeDeptｈ(bt->RCｈｉlｄ);ﻩ max＝hl>hr？ｈl:ｈr;ﻩﻩｒetuｒｎ(mａx+1）；ﻩ}ﻩｅｌseﻩﻩrｅturn0；}ｖoidPｒeSｔacｋ(BiTrｅebt） //非递归遍历｛ﻩBiＴreep； ＬinkSｔacks;ﻩInitStack(&s)； //p＝bt；ﻩPuｓhStack（ｓ，bt);ﻩwhｉle(!Iｓｅmpty(s))ﻩ{ PｏpStack(ｓ,&p）;ﻩﻩﻩprｉnｔf（"%c＂，ｐ－>dａta)；ﻩ ﻩif(p->ＲChiｌd!=NUＬL)ﻩ ﻩﻩPｕsｈStack(ｓ,p->RChilｄ)； ｉf(ｐ->LChild!=NＵLＬ)ﻩﻩﻩﻩPusｈSｔack(s，p->LCｈilｄ)； ﻩ}}/*vｏidPreStack(ＢiTreebt）ﻩ/／非递归先序遍历｛ﻩＢiTreep;ﻩLinkStackｓ; InitStaｃk(&s）;ﻩｐ＝ｂt;ﻩwｈilｅ(p||！Isempｔy(s))ﻩ{ ﻩｉf（p） {ﻩ ｐｒintｆ(＂%c",p->ｄata）;ﻩ PushSｔack(s，ｐ）;ﻩﻩﻩｐ=p->LＣhiｌｄ； } ｅlse ﻩ{ﻩﻩ PｏpStacｋ(s,&p）; ﻩﻩp=p->ＲＣｈild; } }}*／voidPrintＴｒee（BiＴreeｂt，intｎＬayer){ﻩｉnti；ﻩｉf(ｂt=＝NULL） ﻩretuｒn;ﻩＰｒintTreｅ(ｂt->RChild,nLayｅr＋1); foｒ(ｉ＝0;ｉ<nＬａyer;i+＋）ﻩﻩprintf("＂);ﻩpｒintf("%c\n",bt->datａ); ＰｒｉntTreｅ（bt－>ＬChｉlｄ，nLayer＋1);}vｏidLｅaｆTrｅe(BiTreebt) //树的叶子结点遍历{ if(bt!=ＮＵLL）ﻩ{ ﻩｉf(bt－＞ＬChilｄ=＝NULL＆&bt－＞RＣｈild＝=NULＬ）ﻩﻩ ｐrintf(＂％c＂,bt－>ｄａta)； LeafTrｅe(bt->ＬChild); ＬｅafTrｅｅ(bt->ＲChｉｌd）； }｝ｖoidTraｖel(BiTｒeｅｂt) ﻩﻩ//树的按层遍历{ ＢiTreep；ﻩLinkQｕｅｕeQ;ﻩInitQueue(&Q); if（ｂｔ＝=NULL)ﻩ retｕｒn;ﻩp=bt; EnteｒQueuｅ(&Q,p)； while(Q．froｎt！=Ｑ.reａr) { DｅｌeteQueue（&Ｑ,&p);ﻩﻩｐrintｆ("%c",p->data）;ﻩ if(p->LChiｌd) ﻩ EｎｔerＱueue（&Q,p->LCｈild);ﻩﻩiｆ(ｐ-＞ＲCｈｉｌd) ﻩEｎｔeｒQｕeue（&Q,p-＞RChild); ｝｝vｏｉdmａin()｛ BiTreｅｂt； inｔnLayer; CreatＢｉTree(&bt);ﻩｎＬayer=PｏstTreeDepth(bt); prｉntf("树的深度：%d\n"，nLａyｅr); printf（"树的树状打印：＼n"); ＰrintTree(bt，nＬayer);ﻩpｒｉntf("前序访问：\n");ﻩprｅＯrｄer(bt); ｐrinｔｆ("\n");ﻩprintｆ（"中序访问:\ｎ"）; InＯrdeｒ(bt);ﻩprintf("＼n"）；ﻩprintf("后序访问：＼n");ﻩPoｓtOｒder（bｔ); pｒiｎｔf(＂\n＂)； ｐｒintf("非递归访问：\n")； PreStack(bt);ﻩpriｎtf(＂＼ｎ"）; prinｔf(＂树的叶子结点有:＼n")；ﻩLeafTｒee(bｔ）； ｐrintｆ（"\n＂）;ﻩｐriｎtf(＂树的按层遍历:\ｎ");ﻩＴravel(bt);ﻩprinｔf("\n"）；}2：//huｆfman#iｎｃｌｕde<stｄio.ｈ＞#ｉｎcｌude＜sｔdlib.h＞#ｉnｃluｄｅ<strinｇ.h>#deｆｉnｅN20#definｅM2＊N－1ｔｙpｅdefchaｒ＊Huffｍaｎcoｄe[N+１];ｔｙpedefｓtｒucｔ{ﻩinｔwｅight; intparent; iｎtLChiｌd;ﻩｉntRChiｌd;｝HTNodｅ,ＨuｆfmanTreｅ[M+1];/／建立哈弗曼树的几个函数。voｉｄｓelect(HufｆｍanＴrｅｅht,iｎtpos,int*s1，int*s2)／/寻找最小孩子形成最优二叉树。{ﻩinｔm1,m2; iｎｔi； m1＝m2=32７６7;ﻩfor（i=1;ｉ<＝poｓ;i＋+)ﻩ{ﻩﻩif(hｔ[ｉ].ｐarent==0&＆ht[i].ｗeighｔ<m1）ﻩ { ﻩ ｍ2=m1; ﻩm1=ht［i］.weｉght; *s2=*s1; ﻩ ＊s1＝i;ﻩﻩ} ﻩｅｌseiｆ（hｔ[i]．ｐａｒｅｎt==0&＆ht[i]．weiｇht<m2)ﻩ { ﻩ m2＝hｔ[i]．weight;ﻩ *s2=i;ﻩ } } if（*s1>*s2)ﻩ{ i＝*s1; *ｓ1=*s2; ＊s2=i;ﻩ｝}voｉdＣreat（HuffmaｎTrｅｅｈt,intｗ[]，ｃｈarp[],intn)//构造哈弗曼树。{ﻩｉｎts1,s２,ｉ;ﻩfor(i＝1;ｉ<=n;i++)//前n个叶子结点的初始化 ｛ hｔ[ｉ].weight=w[i］; ﻩht[ｉ].ｐａreｎt=0； ﻩｈt[ｉ].LChild=0; ﻩht[i].RChilｄ=0；ﻩ｝ foｒ(i＝n+1;i＜=２*n-1;ｉ++）／/权值的初始化。ﻩ{ ﻩsｅlect(hｔ,ｉ－1，&s1,＆s2);ﻩﻩht[i]．weighｔ=ht［s1]．weight+hｔ[ｓ２].weighｔ; ht[ｉ］.parｅnt=０; ﻩhｔ[s1].pａreｎt=i;ﻩ hｔ[s２].ｐaｒeｎt=i; ﻩht[i].LＣｈｉld=ｓ1; ﻩhｔ［i].RChild＝ｓ２；ﻩ}}／/生成哈弗曼树的函数编码。voidOｒｄｅrHｕffman(HuffmanTreeｈt,Hｕffmancodehｃ,cｈarsｔr［]，iｎtm)//根据哈弗曼树构成哈弗曼编码表ｈｃ。{ﻩintｑ[N］; char*cd;//临时存放编码串。ﻩintc，p，i;//c，p分别为孩子和双亲。ﻩiｎtstart;//制定编码cｄ的起始位置。 cｄ=(ｃhar*）malｌoｃ(m*sizeoｆ(chaｒ）)；ﻩcd［ｍ-１]=＇\0';//最后一位置放上字符串的结束标志。ﻩi=０;ﻩwhｉle（ｉ<m)ﻩ｛ sｗitcｈ（sｔr[i])