二叉樹實(shí)驗(yàn)要求

實(shí)驗(yàn)四二叉樹的基本操作一、實(shí)驗(yàn)?zāi)康耐ㄟ^實(shí)驗(yàn),掌握二叉樹的建立與存儲通過實(shí)驗(yàn),掌握二叉樹的遍歷方法二、實(shí)驗(yàn)內(nèi)容練習(xí)二叉樹的建立與存儲練習(xí)二叉樹的遍歷三、實(shí)驗(yàn)步g三、實(shí)驗(yàn)步g建立自己的頭文件BT.H,內(nèi)容包括二叉鏈表的結(jié)構(gòu)描述、二叉樹存儲結(jié)構(gòu)（二叉鏈表）的建立、二叉樹的先序、中序與后序遍歷算法。建立二叉樹，并通過調(diào)用函數(shù)，建立二叉樹的存儲結(jié)構(gòu)（二叉鏈表\輸出先序遍歷、中序遍歷與后序遍歷的結(jié)果。實(shí)現(xiàn)提示建立二叉樹存儲結(jié)構(gòu)時(shí)采用的二叉樹的定義方法（即課上講的第一種方法,參看課件）:以字符串形式"根左子樹右子樹"定義一顆二叉樹。五、測試數(shù)據(jù)1、AB#C##D##2、ABC##DE#G##F##H##

實(shí)驗(yàn)六圖一、 實(shí)驗(yàn)?zāi)康恼莆請D的基本存儲方法；掌握有關(guān)圖的操作算法并用高級語言實(shí)現(xiàn)；熟練掌握圖的兩種搜索路徑的遍歷方法。二、 實(shí)驗(yàn)內(nèi)容假設(shè)以一個帶權(quán)有向圖表示某一區(qū)域的公交線路網(wǎng)，圖中頂點(diǎn)代表一些區(qū)域中的重要場所，弧代表已有的公交線路，弧上的權(quán)表示該線路上的票價(jià)（或搭乘所需時(shí)間），試設(shè)計(jì)一個交通指南系統(tǒng)，指導(dǎo)前來咨詢者以最低的票價(jià)或最少的時(shí)間從區(qū)域中的某一場所到達(dá)另一場所。三、實(shí)驗(yàn)步g三、實(shí)驗(yàn)步g定義結(jié)點(diǎn)結(jié)構(gòu)，定義圖結(jié)構(gòu)。2?存儲圖信息；定義求任意兩點(diǎn)最短路徑函數(shù)；寫出主函數(shù)。實(shí)現(xiàn)提示tvpedefstmctnode{mtno;floatwgt;stmctnode*next;}edgenode;tvpedefstmct{charvtx;edgenode*luik;}vexnode;tvpedefvexnodeGraph[n];voidFloyd(GraphGfloatA[n][n],intp[n][n]){int1,j,k;for(1=0;i<n;i++)for(j=0;j<n;j++){A[i]U]=G[i]D]；}for(k=0;k<n;k卄)for(1=0;i<n;i卄)forO=0;j<n;j++)if(A[i][k]+A[k][j]<A[i]U]){P[i]UJ=k;A[i]U]=A[i][k]+A[k]U]；}}五、思考與提高判斷兩點(diǎn)是否可達(dá)。如何對程序進(jìn)行修改，找一條人最少的公交線路?練習(xí)圖的拓?fù)渑判驅(qū)嶒?yàn)七查找實(shí)驗(yàn)七查找一、實(shí)驗(yàn)?zāi)康恼莆詹檎业牟煌椒?并能用高級語言實(shí)現(xiàn)查找算法;熟練掌握二叉排序樹的構(gòu)造和查找方法。了解靜態(tài)查找表及哈希表查找方法。二、實(shí)驗(yàn)內(nèi)容設(shè)計(jì)一個算法讀入一串整數(shù)，然后構(gòu)造二叉排序樹，進(jìn)行查找。三、實(shí)驗(yàn)步g三、實(shí)驗(yàn)步g從空的二叉樹開始，每輸入一個結(jié)點(diǎn)數(shù)據(jù)，就建立一個新結(jié)點(diǎn)插入到當(dāng)前已生成的二叉排序樹中。在二叉排序樹中查找某一結(jié)點(diǎn)。3?用其它查找算法進(jìn)行排序（課后自己做\實(shí)現(xiàn)提示定義結(jié)構(gòu)tvpedefstmctnode{intkey;intother;stmctnode*lcluld,*ichild;}bstnode;voidlnoider(t){if(t!=Null){inorder(t—?lchild);pTintf(“％4d”，t~>kev);iiiorder(t—?rchild);}}bstnode*inseilbst(t,s)bstnode*s,*t;{bstnode*f,*p;p=t;while(p!=Null){f=P；if(sTkey==p—^key)returnt;if(s~>key<p—?key)p=p~^lchild;elsep=p~^ichild;}if(t==Null)retunis;if(s—keyvLkey)Llchild=s;elsef^ichild=s;returnt;}bstnode*cieatoid(){bstnode*t,*s;intkey;t=Null;scanf(“％d”,&key);wlule(key!=0){s=malloc(sizeof(bitree));s~>key=key;s->lchild=Null;s->ichild=Null;scanf(“％d‘：&data);s—>otlier=data;t=iiisertbst(t,s);scanf(“％d”,&key);}returnt;}五、思考與提高用其它的查找方法完成該算法。比較各種算法的時(shí)間及空間復(fù)雜度。實(shí)驗(yàn)八排序一、實(shí)驗(yàn)?zāi)康恼莆粘Ｓ玫呐判蚍椒?，并掌握用高級語言實(shí)現(xiàn)排序算法的方法；深刻理解排序的定義和各種排序方法的特點(diǎn)，并能加以靈活應(yīng)用；了解各種方法的排序過程及其時(shí)間復(fù)雜度的分析方法。二、實(shí)驗(yàn)內(nèi)容統(tǒng)計(jì)成績給出n個學(xué)生的考試成績表，每條信息由姓名和分?jǐn)?shù)組成，試設(shè)計(jì)一個算法:(1)按分?jǐn)?shù)高低次序，打印出每個學(xué)生在考試中獲得的名次，分?jǐn)?shù)相同的為同一名次；(2)按名次列出每個學(xué)生的姓名與分?jǐn)?shù)。三、實(shí)驗(yàn)步g三、實(shí)驗(yàn)步gi.定義結(jié)構(gòu)體。定義結(jié)構(gòu)體數(shù)組。定出主程序，對數(shù)據(jù)進(jìn)行排序。實(shí)現(xiàn)提示#defuien30typedefstmctstudent{charnaine[8];intscore;studentR[n];main(){intnum,i,j,max、temp;

priiitf(u\n請輸入學(xué)生成績:E);for(i=0;i<n;i++){pnntf(“姓名:”);scanf("%s篤&stu[i].name);scanf("%4d篤&stii[i].score);}num=l;for(i=0;i<n;i++){max=i;fbr(j=i+l;j<n;j++)if(R[j].score>R[max].score)max=j;if(max!=i){temp=R[niax];R[max]=R[i];R[i]=temp;}if((i>0)&&(R[i].score<R[i-1].score))num=num+l;pnntfC<%4d%s%4d,\num,R[i].name,R[i].score);}}五、思考與提高快速排序算法解決本問題。較各種排序算法的優(yōu)缺點(diǎn)及。使用其它排序算法實(shí)現(xiàn)該問題（直接插入排序、希爾排序、簡單選擇排序、利用VC++6.0進(jìn)行數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)的標(biāo)準(zhǔn)步驟演示新建一個Win32ConsoleApplication工程，并給該工程設(shè)置一個名稱（比如Expl）。ILM 1?U4Xatlc匕"SUsl>占/ □闔曹刑JMd Fl 創(chuàng)IF棄繪7CzViseal*o? r-^.r*.C5maoo二點(diǎn)擊OK迸入下一步f選擇AnEmptyPr