數(shù)據(jù)結(jié)構(gòu)實(shí)習(xí)報(bào)告

數(shù)據(jù)結(jié)構(gòu)實(shí)習(xí)報(bào)告班級(jí) XXXXXX 學(xué)生姓名 XXXXXX 學(xué)號(hào)XXXX 指導(dǎo)教師 XXXXXX日期2012年11月10日?qǐng)?bào)告簡(jiǎn)介：整篇實(shí)習(xí)報(bào)告主要分為三部分：實(shí)習(xí)一，實(shí)習(xí)二以及實(shí)習(xí)困惑。其中每個(gè)實(shí)習(xí)報(bào)告涉及6個(gè)部分：需求分析，設(shè)計(jì)，調(diào)試分析，用戶手冊(cè)，測(cè)試結(jié)果，源程序清單。具體報(bào)告內(nèi)容如下：實(shí)習(xí)一：一元稀疏多項(xiàng)式運(yùn)算器的設(shè)計(jì)1、 需求分析【問題描述】設(shè)計(jì)一個(gè)一元稀疏多項(xiàng)式簡(jiǎn)單計(jì)算器?！净疽蟆枯斎氩⒔蓚€(gè)多項(xiàng)式；多項(xiàng)式a與b相加，建立和多項(xiàng)式c；多項(xiàng)式a與b相減，建立和多項(xiàng)式d；輸出多項(xiàng)式a,b,c,d。輸出格式：比如多項(xiàng)式a為：A(x)二clxel+c2xe2+…+cmxem，其中，ci和ei分別為第i項(xiàng)的系數(shù)和指數(shù)，且各項(xiàng)按指數(shù)的升冪排列，即0WelVe2V???Vem。2、 設(shè)計(jì)(1)設(shè)計(jì)思想存儲(chǔ)結(jié)構(gòu)：以帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式。算法主要思想：?首先定義單鏈表中每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)體類型，設(shè)計(jì)能夠生成多項(xiàng)式鏈表的函數(shù)，這個(gè)函數(shù)的功能是可以根據(jù)給定的多項(xiàng)式來創(chuàng)建存儲(chǔ)它的單鏈表。?然后需要設(shè)計(jì)兩個(gè)多項(xiàng)式相加的函數(shù)與兩個(gè)多項(xiàng)式相減的函數(shù)。?要檢驗(yàn)多項(xiàng)式的運(yùn)算結(jié)果以及初始的多項(xiàng)式鏈表正確與否，需要將其打印輸出，故還需要設(shè)計(jì)打印輸出函數(shù)。?主函數(shù)的設(shè)計(jì)：依次調(diào)用多項(xiàng)式鏈表生成的函數(shù)、多項(xiàng)式相加減的函數(shù)，最后將結(jié)果打印輸出。(2)概要設(shè)計(jì)整個(gè)算法需要設(shè)計(jì)五個(gè)函數(shù)，分別是：多項(xiàng)式鏈表生成的函數(shù)、兩個(gè)多項(xiàng)式相加的函數(shù)、兩個(gè)多項(xiàng)式相減的函數(shù)、打印輸出的函數(shù)以及主函數(shù)。在設(shè)計(jì)各個(gè)函數(shù)之前，要定義單鏈表結(jié)點(diǎn)的結(jié)構(gòu)體類型。每個(gè)結(jié)點(diǎn)應(yīng)該包括指數(shù)code、系數(shù)exp和指向下一個(gè)結(jié)點(diǎn)的指針next。

多項(xiàng)式鏈表生成的函數(shù)：函數(shù)的返回值應(yīng)該為定義的結(jié)構(gòu)體類型，不需要設(shè)置參數(shù)。函數(shù)內(nèi)部，需要有多項(xiàng)式指數(shù)和系數(shù)的輸入，直至輸入的系數(shù)為零時(shí)結(jié)束，將每一對(duì)輸入的指數(shù)和系數(shù)保存到新結(jié)點(diǎn)中，并將結(jié)點(diǎn)插入到鏈表中。輸入結(jié)束后，就生成了所要求的多項(xiàng)式鏈表。兩個(gè)多項(xiàng)式相加的函數(shù)：函數(shù)的返回值應(yīng)該為定義的結(jié)構(gòu)體類型，參數(shù)包括：兩個(gè)多項(xiàng)式鏈表的頭指針。函數(shù)的功能是當(dāng)兩個(gè)鏈表中的兩個(gè)結(jié)點(diǎn)的指數(shù)相等時(shí)，將二者的系數(shù)相加，存入新的結(jié)點(diǎn)中，并將此結(jié)點(diǎn)插入到新的多項(xiàng)式鏈表中，當(dāng)指數(shù)不相等時(shí)，將指數(shù)較小的一項(xiàng)復(fù)制成新結(jié)點(diǎn)插入到新的多項(xiàng)式鏈表中。多項(xiàng)式相減的函數(shù)與相加函數(shù)類似，這里不再贅述。打印輸出函數(shù)：設(shè)計(jì)成無返回值類型，參數(shù)為所需打印輸出的單鏈表的頭指針，這里需要注意輸出格式，要分情況討論。主函數(shù)：調(diào)用兩次創(chuàng)建多項(xiàng)式鏈表的函數(shù)，創(chuàng)建頭結(jié)點(diǎn)分別為heada,headb的兩個(gè)多項(xiàng)式鏈表，然后依次調(diào)用多項(xiàng)式相加、多項(xiàng)式相減的函數(shù)，將結(jié)果存入頭結(jié)點(diǎn)為headc，headd的多項(xiàng)式鏈表中。最后將初始的兩條單鏈表以及新生成的鏈表打印輸出。3）詳細(xì)設(shè)計(jì)主函數(shù)3、3、調(diào)試分析生成兩個(gè)多］將兩個(gè)多項(xiàng)（將兩個(gè)多項(xiàng)（將初始的兩將計(jì)算結(jié)果項(xiàng)式鏈表式相加式相減條鏈表打印輸出打印輸出★問題的解決：在程序設(shè)計(jì)過程中遇到了很多的錯(cuò)誤，一元稀疏多項(xiàng)式運(yùn)算器的設(shè)計(jì)，第一次上機(jī)打印輸出函數(shù)的設(shè)計(jì)并未完成，好在第二次上機(jī)時(shí)有老師的幫助，得以順利完成。在調(diào)試過程中，主要的問題體現(xiàn)在打印輸出函數(shù)中輸出格式的設(shè)計(jì)?！锘仡櫽懻撆c分析：剛開始我在打印輸出函數(shù)中，沒有分情況討論輸出格式，輸出語句為：printf("%dx%d+",pl->code,pl->exp)，輸出的多項(xiàng)式最后一項(xiàng)后仍跟著一個(gè)“+”，顯然這樣的格式并不是我們想要的，后來經(jīng)過思考后調(diào)整了輸出格式，分了兩種情況，如下：出語句為：voidlistprintf(structpnode*head){structpnode*p,*p1;p=head;while(p!=NULL){p1=p;p=p->next;if(pl->next!二NULL&&p->code>0)//情況一：非末尾元素printf("%dx%d+",pl->code,pl->exp);elseprintf("%dx%d",pl->code,pl->exp);//情況二：當(dāng)輸出最后一個(gè)元素時(shí)}printf("\n");}經(jīng)過調(diào)整，就得到了我們所需要的輸出格式如圖：1x1+1x1?^1x1+2x1^9+1x2001x1-1x28^Pr-ess：an9keytocontinue其中的測(cè)試數(shù)據(jù)為：(x+xl00)+(xl00+x200)=(x+2xl00+x200)次要問題是：兩個(gè)多項(xiàng)式相減函數(shù)的設(shè)計(jì)中，當(dāng)兩個(gè)結(jié)點(diǎn)的指數(shù)不相等時(shí)，將指數(shù)較小的結(jié)點(diǎn)復(fù)制成一個(gè)新的結(jié)點(diǎn)插入到鏈表C中，這時(shí)如果和多項(xiàng)式相加時(shí)編寫的語句一樣就會(huì)出現(xiàn)問題，應(yīng)該注意符號(hào)的正負(fù)，具體的程序設(shè)計(jì)將在源程序清單中給出。★時(shí)間復(fù)雜度的分析：創(chuàng)建多項(xiàng)式鏈表相加、減函數(shù)打印輸出函數(shù)整體時(shí)間復(fù)雜度O(n)O(n)O(n)O(n)★改進(jìn)設(shè)想：(1)在上機(jī)實(shí)習(xí)期間，時(shí)間比較緊，只是單純的將一元稀疏多項(xiàng)式的運(yùn)算器用算法實(shí)現(xiàn)，并沒有設(shè)計(jì)，將其設(shè)計(jì)出可視化的界面。(2)在C程序的設(shè)計(jì)中，我將全部的程序?qū)懺谕粋€(gè)界面上，其實(shí)可以講涉及到需要調(diào)用的函數(shù)寫在頭文件中，主函數(shù)在調(diào)用時(shí)，只許將此頭文件包括進(jìn)來即可，這樣閱讀起來方便簡(jiǎn)潔?！锝?jīng)驗(yàn)與體會(huì)：一個(gè)良好的算法需要滿足5個(gè)目標(biāo)：正確性、可讀性、健壯性、高時(shí)間效率、高空間效率。程序設(shè)計(jì)過程中，在健壯性的處理上尚不能得心應(yīng)手，常常會(huì)考慮不充分，造成不良后果，這說明僅僅掌握書本上的知識(shí)是遠(yuǎn)遠(yuǎn)不夠的。此外，我發(fā)現(xiàn)了自己一個(gè)很嚴(yán)重的問題，即便是取得了計(jì)算機(jī)二、三級(jí)證書，在程序的設(shè)計(jì)實(shí)現(xiàn)上能力還很匱乏。我所擅長(zhǎng)的更大程度上是閱讀程序，編寫單個(gè)的函數(shù)，在遇到一個(gè)涉及到多個(gè)函數(shù)的調(diào)用，多個(gè)功能的算法時(shí)，往往思維不夠全面，分析不夠到位，這就讓我不得不邊寫程序邊調(diào)整思路，后果就是效率低下，這讓我十分苦惱。4、 用戶手冊(cè)因?yàn)檎麄€(gè)算法均采用c語言設(shè)計(jì)，所以操作簡(jiǎn)單易懂，現(xiàn)在就具體說明：在創(chuàng)建多項(xiàng)式鏈表的函數(shù)中采用的輸入語句為：scanf("%d,%d",&n,&m)，所以輸入的系數(shù)與指數(shù)需要以“，”隔開。在輸入過程中，輸入結(jié)束時(shí)，將系數(shù)輸入“0”,就完成了一個(gè)多項(xiàng)式鏈表的創(chuàng)建。接著就依次輸入下一個(gè)多項(xiàng)式的系數(shù)和指數(shù)，同樣以系數(shù)為“0”結(jié)束。按要求輸入后整個(gè)程序就會(huì)運(yùn)行，依次打印出初始的兩條鏈表以及運(yùn)算后的兩條鏈表中的元素。示例：(x+x100)+(x100+x200)=(x+2x100+x200)輸入：1,11,1000,01,1001,2000,05、 測(cè)試結(jié)果測(cè)試數(shù)據(jù)如下：(1)(x+x100)+(x100+x200)=(x+2x100+x200)(x+x100)-(x100+x200)=(x-x200)LA殺數(shù)n祁涓魏nilJ認(rèn)索數(shù)麻咄認(rèn)索數(shù)謫酣認(rèn)索藪謫酣認(rèn)索藪屏呵認(rèn)索數(shù)需時(shí)ixl+1x10Sixl0B+lx2Gfi1x1+3xlE)B+lx26fjlxl-lx26fj^rcssan^pIce5,t;ocontinue旨數(shù)ml,100旨數(shù)嗣胡a?in：l,16￡t□?ml,200疥數(shù)!n過詡2)(1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5)(1+x+x2+x3+x4+x5)-(-x3-x4)=(1+x+x2+2x3+2x4+x5)兇n~nJo■>4兇n~nJo■>401-0*-1* 0:-0數(shù)數(shù)數(shù)數(shù)數(shù)數(shù)數(shù)數(shù)數(shù)數(shù)匕呂已日已日已日匕日匕日匕日匕日匕日匕曰_-<-?_-<-?■扌■扌■扌.nnnnnnnnnn示弄弄弄牙牙云云云二Jn數(shù)數(shù)數(shù)數(shù)數(shù)數(shù)數(shù)數(shù)數(shù)數(shù)奈系系系系系系系系系TAAAAAAAAkMIXMIXMIXMIXMIX^\.亠^\.亠^\.亠0*121*>-11Hu3)(2x+5x8-3x11)+(7-5x8+11x9)=(7+2x+11x9-3x11)(2x+5x8-3x11)-(7-5x8+11x9)=(-7+2x+10x8-11x9-3x11)1^-894QD4y444回43一7呂1一呼悶廠因m:m-.il吶蝕數(shù)數(shù)數(shù)數(shù)數(shù)數(shù)數(shù)

可日匕日匕臼匕臼匕臼匕臼匕日匕日T.T;T:「■■r.T.T.T.■扌1-nnnnnnnnl1匚*匚tr-1r-1匚t匚l匚Ic-X數(shù)數(shù)數(shù)數(shù)數(shù)數(shù)數(shù)數(shù)4親系系系系系系系5X6、 源程序清單#include<stdio.h>#include<malloc.h>structpnode/*定義結(jié)點(diǎn)的結(jié)構(gòu)體*/{intcode;/*系數(shù)*/intexp;//指數(shù)structpnode*next;};structpnode*poly()/*生成多項(xiàng)式鏈表的函數(shù)*/{structpnode*head,*r,*s;intm,n;head=(struetpnode*)malloc(sizeof(struetpnode));/*建立一個(gè)頭結(jié)點(diǎn)*/r=head;printf("輸入系數(shù)n和指數(shù)m:");scanf("%d,%d",&n,&m);while(n!=0){s=(struetpnode*)malloc(sizeof(struetpnode));/*建立結(jié)點(diǎn)*/s->code=n;s->exp=m;r->next二s;/*把結(jié)點(diǎn)s連接到r所指向的頭結(jié)點(diǎn)之后，然后把指針r后移，r指向s結(jié)點(diǎn)*/r=s;printf("輸入系數(shù)n和指數(shù)m");seanf("%d,%d",&n,&m);}r->next=NULL;/*刪除掉頭結(jié)點(diǎn)*/head=head->next;return(head);}structpnode*padd(heada,headb)/*兩個(gè)多項(xiàng)式相加的函數(shù)*/structpnode*heada,*headb;{structpnode*headc,*p,*q,*r,*s;intx;p=heada;q=headb;headc=(structpnode*)malloc(sizeof(structpnode));r=headc;while(p!=NULL&&q!=NULL){if(p->exp==q->exp)/*兩結(jié)點(diǎn)的指數(shù)相等時(shí)，將兩節(jié)點(diǎn)的系數(shù)相加，然后存入結(jié)點(diǎn)S中*/{x=p->code+q->code;if(x!=0){S=(Structpnode*)malloc(Sizeof(Structpnode));S->code=x;S->exp=p->exp;r->next=S;r=S;}p=p->next;q=q->next;}else/*當(dāng)兩個(gè)結(jié)點(diǎn)的指數(shù)不相等時(shí)，將指數(shù)較小的結(jié)點(diǎn)復(fù)制成一個(gè)新的結(jié)點(diǎn)插入到C中*/if(p->exp>q->exp){s=(structpnode*)malloc(sizeof(structpnode));s->code=q->code;s->exp=q->exp;r->next=s;r=s;q=q->next;}else{s=(structpnode*)malloc(sizeof(structpnode));s->code=p->code;s->exp=p->exp;r->next=s;r=s;p=p->next;}}while(p!=NULL){s=(structpnode*)malloc(sizeof(structpnode));s->code=p->code;s->exp=p->exp;r->next=s;r=s;p=p->next;}while(q!=NULL){s=(structpnode*)malloc(sizeof(structpnode));s->code=q->code;s->exp=q->exp;r->next=s;r=s;q=q->next;}r->next=NULL;s=headc;headc=headc->next;free(s);return(headc);}structpnode*psubtract(heada,headb)/*兩個(gè)多項(xiàng)式相減的函數(shù)*/structpnode*heada,*headb;{structpnode*headd,*p,*q,*r,*s;intx;p=heada;q=headb;headd=(structpnode*)malloc(sizeof(structpnode));r=headd;while(p!=NULL&&q!=NULL){if(p->exp==q->exp)/*兩結(jié)點(diǎn)的指數(shù)相等時(shí)，將兩節(jié)點(diǎn)的系數(shù)相減，然后存入結(jié)點(diǎn)S中*/{x=p->code-q->code;if(x!=0){s=(structpnode*)malloc(sizeof(structpnode));s->code=x;s->exp=p->exp;r->next=s;r=s;}p=p->next;q=q->next;}else/*當(dāng)兩個(gè)結(jié)點(diǎn)的指數(shù)不相等時(shí)，將指數(shù)較小的結(jié)點(diǎn)復(fù)制成一個(gè)新的結(jié)點(diǎn)插入到C中*/if(p->exp>q->exp){s=(structpnode*)malloc(sizeof(structpnode));s->code=-(q->code);s->exp=q->exp;r->next=s;r=s;q=q->next;}else{s=(structpnode*)malloc(sizeof(structpnode));s->code=p->code;s->exp=p->exp;r->next=s;r=s;p=p->next;}}while(p!=NULL){s=(structpnode*)malloc(sizeof(structpnode));s->code=p->code;s->exp=p->exp;r->next=s;r=s;p=p->next;}while(q!=NULL){s=(structpnode*)malloc(sizeof(structpnode));s->code=-(q->code);s->exp=q->exp;r->next=s;r=s;q=q->next;}r->next=NULL;s=headd;headd=headd->next;free(s);return(headd);}voidlistprintf(structpnode*head){structpnode*p,*p1;p=head;while(p!=NULL){p1=p;p=p->next;if(p1->next!=NULL&&p->code>0)printf("%dx%d+",p1->code,p1->exp);elseprintf("%dx%d",p1->code,p1->exp);}printf("\n");}main(){structpnode*heada,*headb,*headc,*headd;heada=poly();headb=poly();headc=padd(heada,headb);headd=psubtract(heada,headb);listprintf(heada);listprintf(headb);listprintf(headc);listprintf(headd);}實(shí)習(xí)二：唯一的確定一棵二叉樹1、需求分析【問題描述】如果給出了遍歷二叉樹的前序序列和中序序列，則可以構(gòu)造出唯一的一棵二叉樹。試編寫實(shí)現(xiàn)上述功能的程序?！净疽蟆恳阎豢枚鏄涞那靶蚝椭行蛐蛄?，試設(shè)計(jì)完成下列任務(wù)的一個(gè)算法：（1） 構(gòu)造一棵二叉樹；（2） 證明構(gòu)造正確（即分別以前序和中序遍歷該樹，將得到的結(jié)果與給出的序列進(jìn)行比較）。（3） 對(duì)該二叉樹進(jìn)行后序遍歷，輸出后序遍歷序列。（4）用凹入法輸出該二叉樹。2、設(shè)計(jì)（1）設(shè)計(jì)思想存儲(chǔ)結(jié)構(gòu)：以兩個(gè)數(shù)組分別存儲(chǔ)給定的前序遍歷序列和中序遍歷序列。而所構(gòu)造的二叉樹則以二叉鏈存儲(chǔ)。算法主要思想：定義二叉鏈中結(jié)點(diǎn)的結(jié)構(gòu)體類型。設(shè)計(jì)根據(jù)前序遍歷序列、中序遍歷序列構(gòu)造二叉樹的函數(shù)。設(shè)計(jì)后序遍歷二叉樹的函數(shù)設(shè)計(jì)凹入法打印輸出二叉樹的函數(shù)在主函數(shù)中定義兩個(gè)數(shù)組，用來存放中序遍歷、前序遍歷序列的字符串主函數(shù)依次調(diào)用兩次字符串輸入函數(shù)，構(gòu)造二叉樹的函數(shù)，后序遍歷函數(shù)，凹入法打印輸出函數(shù)。（2）概要設(shè)計(jì)整個(gè)算法需要設(shè)計(jì)四個(gè)函數(shù)，分別是：根據(jù)前序遍歷序列、中序遍歷序列構(gòu)造二叉樹的函數(shù)、后序遍歷二叉樹的函數(shù)、凹入法打印輸出的函數(shù)以及主函數(shù)。在設(shè)計(jì)各個(gè)函數(shù)之前，要定義二叉鏈中結(jié)點(diǎn)的結(jié)構(gòu)體類型，存儲(chǔ)遍歷序列字符串的數(shù)組。根據(jù)前序遍歷序列和中序遍歷序列構(gòu)造二叉樹的函數(shù)：考慮算法的健壯性，要分情況討論，當(dāng)給出存放遍歷序列的數(shù)組中有一個(gè)為空或者都為空時(shí)，就不能成功構(gòu)造出二叉樹，只有當(dāng)二者都非空時(shí)才能進(jìn)一步運(yùn)行。后序遍歷二叉樹的函數(shù)：采用遞歸遍歷的方式。凹入法打印輸出的函數(shù)：這個(gè)函數(shù)課本上就有，在此我沒有單獨(dú)設(shè)計(jì)。主函數(shù)：將兩個(gè)遍歷序列字符串分別存入兩個(gè)數(shù)組中，調(diào)用根據(jù)前序遍歷序列、中序遍歷序列構(gòu)造二叉樹的函數(shù)，構(gòu)造完成二叉樹后，調(diào)用后序遍歷函數(shù)，將后序遍歷序列輸出，隨后調(diào)用凹入法打印輸出函數(shù)，將構(gòu)造的二叉樹打印輸出。拓展內(nèi)容：因?yàn)闃浜投鏄淠且徽鹿?jié)中，作業(yè)中涉及到求二叉樹的深度及葉子結(jié)點(diǎn)數(shù)目的算法，所以在這次實(shí)習(xí)唯一確定一棵二叉樹中，我在整體中加入了這兩部分，希望能更好的掌握與二叉樹相關(guān)的算法。（3）詳細(xì)設(shè)計(jì)略（因?yàn)樗惴蚣軋D太麻煩了，時(shí)間緊?。?、調(diào)試分析★問題的解決：在實(shí)習(xí)二中我遇到的主要問題是凹入法打印輸出函數(shù)的設(shè)計(jì)，別看書上已經(jīng)有了這個(gè)函數(shù)，事實(shí)上我在應(yīng)用上沒有那么得心應(yīng)手。將此函數(shù)的參數(shù)做相應(yīng)改變后，我就在主函數(shù)中進(jìn)行了調(diào)用，但是由于輸出格式的問題，在開始階段測(cè)試數(shù)據(jù)構(gòu)造的二叉樹的頭結(jié)點(diǎn)A總是不能顯示，最后經(jīng)過多次修改輸出格式，終于解決了這個(gè)問題?！锘仡櫽懻撆c分析：在最初的凹入法打印輸出函數(shù)中，輸出格式不對(duì)，調(diào)試過程中發(fā)現(xiàn)輸出結(jié)果如下圖：顯然這樣的輸出結(jié)果中，頭結(jié)點(diǎn)A并沒有正確輸出，不滿足算法的正確性。將輸出格式進(jìn)行調(diào)整，就得到了我們所需要的輸出格式如圖：★改進(jìn)設(shè)想：兩次上機(jī)實(shí)習(xí)，第二次實(shí)習(xí)任務(wù)并沒有按時(shí)完成，只是在課后完成的，由于后期備考時(shí)間比較緊，所以這個(gè)算法的設(shè)計(jì)比較粗糙，此外拓展內(nèi)容也沒有完成。只是額外加上了求葉子結(jié)點(diǎn)和二叉樹深度的算法?！锝?jīng)驗(yàn)與體會(huì)：除了有關(guān)算法的相關(guān)體會(huì)外，我還發(fā)現(xiàn)了一個(gè)問題，同學(xué)們?cè)诿鎸?duì)實(shí)習(xí)任務(wù)給出的算法要求時(shí)，大多感覺無從下手，或相互觀望，或干脆放棄，只有少數(shù)同學(xué)能夠堅(jiān)持摸索。可能我比較幸運(yùn)，只是按部就班的設(shè)計(jì)算法，后來能夠得到老師的指點(diǎn)，最終完成整個(gè)算法。我知道不可能一蹴而就，在設(shè)計(jì)和調(diào)試過程中也算是吃了不少苦頭，尤其在調(diào)整打印輸出格式時(shí)尤為明顯。這在一定程度上說明，我在格式控制這個(gè)知識(shí)點(diǎn)上掌握的不太理想。以后應(yīng)該對(duì)這個(gè)知識(shí)點(diǎn)鞏固加強(qiáng)。4、用戶手冊(cè)具體說明使用方法如下：1）在輸入前序遍歷序列、中序遍歷序列的字符串時(shí)，只需要將給定的字符連續(xù)輸入即可，輸入完成一個(gè)后，回車，接著輸入另一個(gè)。2）按要求輸入后整個(gè)程序就會(huì)運(yùn)行，顯示的結(jié)果依次為：后序遍歷序列，凹入法表示的二叉樹，葉結(jié)點(diǎn)個(gè)數(shù)以及二叉樹的深度。5、測(cè)試結(jié)果

測(cè)試數(shù)據(jù)實(shí)例一】前序序列為ABDEGCFHIJ，中序序列為DBGEAHFIJC。正確的后序遍歷序列應(yīng)該是：DGEBHJIFCA，構(gòu)造的正確二叉樹結(jié)構(gòu)應(yīng)該如下圖：設(shè)計(jì)算法的運(yùn)行結(jié)果如下圖：6、 源程序清單#include<stdio.h>#include<malloc.h>#include<string.h>voidexit(int);#defineMAX100typedefintDataType;typedefstructnode//定義結(jié)點(diǎn)的結(jié)構(gòu)體類型{chard;structnode*lchild,*rchild;}Tnode;voidMK(charin[],charis,charie,charpre[],charpres,charpree,Tnode**r)//根據(jù)前序、中序遍歷序列構(gòu)造二叉樹的函數(shù){inti;if(is>ie||pres>pree)//當(dāng)存放遍歷序列的數(shù)組有一個(gè)或兩個(gè)為空時(shí)，構(gòu)造失敗*r=NULL;else{*r=malloc(sizeof(Tnode));(*r)->d=pre[pres];for(i=is;i<=ie;i++){if(in[i]==pre[pres]){MK(in,is,i-1,pre,pres+1,pres+i-is,&(*r)->lchild);MK(in,i+1,ie,pre,pres+i-is+1,pree,&(*r)->rchild);break;}if(i>ie){printf("輸入錯(cuò)誤!\n");exit(1);}}}}voidpostorder(Tnode*r)//后續(xù)遍歷二叉樹{if(r){postorder(r->lchild);postorder(r->rchild);printf("%c",r->d);}}intleaf(Tnode*r)//函數(shù)功能：求所構(gòu)造的二叉樹葉結(jié)點(diǎn)數(shù)目{if(r==NULL)return0;elseif(r->lchild==NULL&&r->rchild==NULL)return1;elsereturnleaf(r->lchild)+leaf(r->rchild);}intheight(Tnode*r)//函數(shù)功能：求所構(gòu)造的二叉樹的高度{inth1,h2;if(r==NULL)return0;else{h1=height(r->lchild);h2=height(r->rchild);return1+(h1>h2?h1:h2);}}voidPrintBiTree(Tnode*r,intn)//逆時(shí)針旋轉(zhuǎn)90度打印二叉樹r,n為縮進(jìn)層數(shù)，初始值為0