二叉樹實驗要求

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

實驗六圖一、 實驗目的掌握圖的基本存儲方法；掌握有關圖的操作算法并用高級語言實現；熟練掌握圖的兩種搜索路徑的遍歷方法。二、 實驗內容假設以一個帶權有向圖表示某一區(qū)域的公交線路網，圖中頂點代表一些區(qū)域中的重要場所，弧代表已有的公交線路，弧上的權表示該線路上的票價（或搭乘所需時間），試設計一個交通指南系統(tǒng)，指導前來咨詢者以最低的票價或最少的時間從區(qū)域中的某一場所到達另一場所。三、實驗步g三、實驗步g定義結點結構，定義圖結構。2?存儲圖信息；定義求任意兩點最短路徑函數；寫出主函數。實現提示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]；}}五、思考與提高判斷兩點是否可達。如何對程序進行修改，找一條人最少的公交線路?練習圖的拓撲排序實驗七查找實驗七查找一、實驗目的掌握查找的不同方法,并能用高級語言實現查找算法;熟練掌握二叉排序樹的構造和查找方法。了解靜態(tài)查找表及哈希表查找方法。二、實驗內容設計一個算法讀入一串整數，然后構造二叉排序樹，進行查找。三、實驗步g三、實驗步g從空的二叉樹開始，每輸入一個結點數據，就建立一個新結點插入到當前已生成的二叉排序樹中。在二叉排序樹中查找某一結點。3?用其它查找算法進行排序（課后自己做\實現提示定義結構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;}五、思考與提高用其它的查找方法完成該算法。比較各種算法的時間及空間復雜度。實驗八排序一、實驗目的掌握常用的排序方法，并掌握用高級語言實現排序算法的方法；深刻理解排序的定義和各種排序方法的特點，并能加以靈活應用；了解各種方法的排序過程及其時間復雜度的分析方法。二、實驗內容統(tǒng)計成績給出n個學生的考試成績表，每條信息由姓名和分數組成，試設計一個算法:(1)按分數高低次序，打印出每個學生在考試中獲得的名次，分數相同的為同一名次；(2)按名次列出每個學生的姓名與分數。三、實驗步g三、實驗步gi.定義結構體。定義結構體數組。定出主程序，對數據進行排序。實現提示#defuien30typedefstmctstudent{charnaine[8];intscore;studentR[n];main(){intnum,i,j,max、temp;

priiitf(u\n請輸入學生成績: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)缺點及。使用其它排序算法實現該問題（直接插入排序、希爾排序、簡單選擇排序、利用VC++6.0進行數據結構實驗的標準步驟演示新建一個Win32ConsoleApplication工程，并給該工程設置一個名稱（比如Expl）。ILM 1?U4Xatlc匕"SUsl>占/ □闔曹刑JMd Fl 創(chuàng)IF棄繪7CzViseal*o? r-^.r*.C5maoo二點擊OK迸入下一步f選擇AnEmptyPr