數(shù)據(jù)結(jié)構(gòu)與算法與實踐數(shù)據(jù)結(jié)構(gòu)實踐實驗指導(dǎo)書參考

1、 printf(后序遍歷二叉樹:)；PostOrderTraverse(T,PrintElement);后序遞歸遍歷二叉樹printf(n)；elseprintfC二叉樹為空!n);break;case4:DisplayBiTreeInConcave(T);break;case5:printf();DisplayBiTreeInBracket(T);printf()n);break;case6:DestroyBiTree(T);CreateBiTree(T);break;default:flag=0;printf(程序運行結(jié)束，按任意鍵退出!n);getch();DestroyBiTree(T

2、);實驗五圖的算法的實現(xiàn)一、實驗?zāi)康恼莆請D的基本存儲方法；掌握有關(guān)圖的操作算法并用高級語言實現(xiàn)；熟練掌握圖的兩種搜索路徑的遍歷方法。二、實驗內(nèi)容假設(shè)以一個帶權(quán)有向圖表示某一區(qū)域的公交線路網(wǎng)，圖中頂點代表一些區(qū)域中的重要場所，弧代表已有的公交線路，弧上的權(quán)表示該線路上的票價（或搭乘所需時間），試設(shè)計一個交通指南系統(tǒng)，指導(dǎo)前來咨詢者以最低的票價或最少的時間從區(qū)域中的某一場所到達(dá)另一場所。三、實驗步驟定義結(jié)點結(jié)構(gòu)，定義圖結(jié)構(gòu)。存儲圖信息；定義求任意兩點最短路徑函數(shù)；寫出主函數(shù)。四、實現(xiàn)提示typedefstructnodeintno;floatwgt;structnode*next;edgenode

3、;typedefstructcharvtx;edgenode*link;vexnode;typedefvexnodeGraphn;voidFloyd(GraphG,floatAnn,intpnn)inti,j,k;for(i=0;in;i+)for(j=0;jn;j+)Aij=Gij;Pij=-1;for(k=0;kn;k+)for(i=0;in;i+)for(j=0;jn;j+)if(Aik+AkjAij)Pij=k;Aij=Aik+Akj;五、思考與提高判斷兩點是否可達(dá)。如何對程序進(jìn)行修改，找一條人最少的公交線路？練習(xí)圖的拓?fù)渑判蛄?、完整參考程?.圖的建立與遍歷#include#incl

4、ude#include#include#defineMAX_VERTEX_NUM20/圖的最大頂點數(shù)#defineMAXQSIZE30/隊列的最大容量enumBOOLFalse,True;typedefstructArcNodeintadjvex;/該弧所指向的頂點的位置structArcNode*nextarc;/指向下一條弧的指針ArcNode;/弧結(jié)點typedefstructArcNode*AdjListMAX_VERTEX_NUM;/指向第一條依附該頂點的弧的指針intvexnum,arcnum;/intvexnum,arcnum;/圖的當(dāng)前頂點和弧數(shù)intGraphKind;/圖的

5、種類，0無向圖，1有向圖Graph;typedefstruct/隊列結(jié)構(gòu)intelemMAXQSIZE;/數(shù)據(jù)域intfront;/隊頭指針intrear;/隊尾指針SqQueue;BOOLvisitedMAX_VERTEX_NUM;/全局變量訪問標(biāo)志數(shù)組voidCreateGraph(Graph&);/生成圖的鄰接表voidDFSTraverse(Graph);/深度優(yōu)先搜索遍歷圖voidDFS(Graph,int);voidBFSTraverse(Graph);/廣度優(yōu)先搜索遍歷圖voidInitial(SqQueue&);/初始化一個隊列BOOLQueueEmpty(SqQueue);/

6、判斷隊列是否空BOOLEnQueue(SqQueue&,int);/將一個元素入隊列BOOLDeQueue(SqQueue&,int&);/將一個元素出隊列intFirstAdjVex(Graph,int);/求圖中某一頂點的第一個鄰接頂點intNextAdjVex(Graph,int,int);/求某一頂點的下一個鄰接頂點voidmain()GraphG;/采用鄰接表結(jié)構(gòu)的圖charj=y;printf(”本程序?qū)⒀菔旧梢粓D，并對它進(jìn)行遍歷.n);printf(“首先輸入要生成的圖的種類.n);printf(0無向圖，1-有向圖n);printf(之后輸入圖的頂點數(shù)和弧數(shù)。n格式：頂點數(shù)，

7、弧數(shù)；例如:4,3n);printf(接著輸入各邊(弧尾，弧頭).n例如:n1,2n1,3n2,4n);printf(程序會生成一個圖，并對它進(jìn)行深度和廣度遍歷An);printf(深度遍歷:1-2-4-3n廣度遍歷:1-2-3-4n);while(j!=N&j!=n)printf(“請輸入要生成的圖的種類(0/1):)；scanf(%d,&G.GraphKind);/輸入圖的種類printf(請輸入頂點數(shù)和弧數(shù)：)；scanf(%d,%d,&G.vexnum,&G.arcnum);/輸入圖的頂點數(shù)和弧數(shù)CreateGraph(G);/生成鄰接表結(jié)構(gòu)的圖DFSTraverse(G);/深度優(yōu)先

8、搜索遍歷圖BFSTraverse(G);/廣度優(yōu)先搜索遍歷圖printf(圖遍歷完畢，繼續(xù)進(jìn)行嗎?(Y/N);scanf(%c,&j);voidCreateGraph(Graph&G)/構(gòu)造鄰接表結(jié)構(gòu)的圖Ginti;intstart,end;ArcNode*s;for(i=1;i=G.vexnum;i+)G.AdjListi=NULL;/初始化指針數(shù)組for(i=1;inextarc=G.AdjListstart;/插入到鄰接表中s-adjvex=end;G.AdjListstart=s;if(G.GraphKind=0)/若是無向圖，再插入到終點的弧鏈中s=(ArcNode*)malloc(

9、sizeof(ArcNode);s-nextarc=G.AdjListend;s-adjvex=start;G.AdjListend=s;voidDFSTraverse(GraphG)/深度優(yōu)先遍歷圖Ginti;printf(DFSTraverse:);for(i=1;i=G.vexnum;i+)visitedi=False;/訪問標(biāo)志數(shù)組初始化for(i=1;i,i);for(w=FirstAdjVex(G,i);w;w=NextAdjVex(G,i,w)if(!visitedw)DFS(G,w);/對尚未訪問的鄰接頂點w調(diào)用DFSvoidBFSTraverse(GraphG)/按廣度優(yōu)先非

10、遞歸的遍歷圖G，使用輔助隊列Q和訪問標(biāo)志數(shù)組visitedinti,u,w;SqQueueQ;printf(BFSTreverse:);for(i=1;i=G.vexnum;i+)visitedi=False;/訪問標(biāo)志數(shù)組初始化Initial(Q);/初始化隊列for(i=1;i,i);EnQueue(Q,i);/將序號i入隊列while(!QueueEmpty(Q)/若隊列不空，繼續(xù)DeQueue(Q,u);/將隊頭元素出隊列并置為ufor(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w)if(!visitedw)/對u的尚未訪問的鄰接頂點w進(jìn)行訪問并入隊列

11、visitedw=True;printf(%d-,w);EnQueue(Q,w);printf(bbn);intFirstAdjVex(GraphG,intv)/在圖G中尋找第v個頂點的第一個鄰接頂點if(!G.AdjListv)return0;elsereturn(G.AdjListv-adjvex);intNextAdjVex(GraphG,intv,intu)/在圖G中尋找第v個頂點的相對于u的下一個鄰接頂點ArcNode*p;p=G.AdjListv;while(p-adjvex!=u)p=p-nextarc;/在頂點v的弧鏈中找到頂點uif(p-nextarc=NULL)return

12、0;/若已是最后一個頂點，返回0elsereturn(p-nextarc-adjvex);/返回下一個鄰接頂點的序號voidInitial(SqQueue&Q)/隊列初始化Q.front=Q.rear=0;BOOLQueueEmpty(SqQueueQ)/判斷隊列是否已空，若空返回True，否則返回Falseif(Q.front=Q.rear)returnTrue;elsereturnFalse;BOOLEnQueue(SqQueue&Q，intch)/入隊列，成功返回True，失敗返回Falseif(Q.rear+1)%MAXQSIZE=Q.front)returnFalse;Q.elemQ

13、.rear=ch;Q.rear=(Q.rear+1)%MAXQSIZE;returnTrue;BOOLDeQueue(SqQueue&Q,int&ch)/出隊列，成功返回True，并用ch返回該元素值，失敗返回Falseif(Q.front=Q.rear)returnFalse;ch=Q.elemQ.front;Q.front=(Q.front+1)%MAXQSIZE;returnTrue;/成功出隊列，返回True2.最短路徑-迪杰斯特拉算法#include#include#include#include#defineINFINITY30000/定義一個權(quán)值的最大值#defineMAX_VE

14、RTEX_NUM20/圖的最大頂點數(shù)enumBOOLFalse，True;typedefstructintarcsMAX_VERTEX_NUMMAX_VERTEX_NUM;/鄰接矩陣intvexnum，arcnum;/圖的當(dāng)前頂點和邊數(shù)Graph;voidCreateGraph(Graph&);/生成圖的鄰接矩陣voidShortestPath_DiJ(Graph，int，intMAX_VERTEX_NUM，int);/用迪杰斯特拉算法求從某一源點到其余頂點的最短路徑voidPrint_ShortestPath（Graph,int,intMAX_VERTEX_NUM,int）;/顯示最短路徑v

15、oidmain（）GraphG;/采用鄰接矩陣結(jié)構(gòu)的圖charj=y;intu;intPMAX_VERTEX_NUMMAX_VERTEX_NUM;/存放從源點到各頂點的最短路徑intDMAX_VERTEX_NUM;/存放從源點到各頂點的最短路徑的距離printf（“本程序?qū)⒀菔纠玫辖芩固乩惴ㄇ髇從圖的一點到其余頂點的最短路徑An）;printf（首先輸入圖的頂點數(shù)和弧數(shù).n格式：頂點數(shù)，弧數(shù)；例如:5,7n）;printf（然后輸入各弧和權(quán)值.n格式：弧尾，弧頭，權(quán)值；例如:nl,2,10nl,3,18n2,4,5n3,2,5n4,3,2n4,5,2n5,3,2n）;printf（再輸入從

16、哪個頂點出發(fā)，例如:1n）;printf（程序?qū)页鰪?到其余頂點的最短路徑.n）;printf（101-2n171-2-4-3n151-2-4n171-2-4-5n）;while（j!=N&j!=n）CreateGraph（G）;/生成鄰接矩陣結(jié)構(gòu)的圖printf（從哪個頂點出發(fā):）;scanf(%d,&u);/輸入迪杰斯特拉算法中的起始頂點ShortestPath_DiJ(G,u,P,D);/利用迪杰斯特拉算法求最短路徑Print_ShortestPath(G,u,P,D);/顯示最短路徑printf(“最短路徑演示完畢，繼續(xù)進(jìn)行嗎?(Y/N);scanf(%c,&j);voidCrea

17、teGraph(Graph&G)/構(gòu)造鄰接矩陣結(jié)構(gòu)的圖Ginti,j;intstart,end,weight;printf(請輸入圖的頂點數(shù)和弧數(shù)(頂點數(shù)，弧數(shù)):)；scanf(%d,%d,&G.vexnum,&G.arcnum);/輸入圖的頂點數(shù)和邊數(shù)for(i=1;i=G.vexnum;i+)for(j=1;j=G.vexnum;j+)G.arcsij=INFINITY;/初始化鄰接矩陣printf(輸入各弧和權(quán)值，格式：弧尾，弧頭，權(quán)值n);for(i=1;i=G.arcnum;i+)scanf(%d,%d,%d,&start,&end,&weight);/輸入邊的起點和終點及權(quán)值G.

18、arcsstartend=weight;voidShortestPath_DiJ(GraphG,intv0,intPMAX_VERTEX_NUM,intD)/用迪杰斯特拉算法求有向網(wǎng)G的v0頂點到其余頂點v的最短路徑Pv及其帶權(quán)路徑長度Dv若PvOO,表明從源點出發(fā)存在一條到頂點v的最短路徑，該路徑存放在Pv中finalv為True則表明已經(jīng)找到從v0到v的最短路徑inti,j,w,v;intmin;BOOLfinalMAX_VERTEX_NUM;for(v=1;v=G.vexnum;v+)/初始化finalv=False;Dv=G.arcsv0v;for(i=0;i=G.vexnum;i+)

19、Pvi=0;/設(shè)空路徑if(DvvINFINITY)Pv0=v0;/若從v0到v有直達(dá)路徑Dv0=0;finalvO=True;/初始時，vO屬于S集開始主循環(huán)，每次求得v0到某個頂點v的最短路徑，并加v到S集for(i=1;i=G.vexnum;i+)/尋找其余G.vexnum-1個頂點v=O;min=INFINITY;for(w=1;w=G.vexnum;w+)/尋找當(dāng)前離v0最近的頂點vif(!finalw)&(Dwmin)v=w;min=Dw;if(!v)break;/若v=0表明所有與v0有通路的頂點均已找到了最短路徑，退出主循環(huán)finalv=True;/將v加入S集for(j=0;

20、Pvj!=0;j+);Pvj=V；將路徑Pv延伸到頂點Vfor(w=1;w=G.vexnum;w+)/更新當(dāng)前最短路徑及距離if(!finalw&(min+G.arcsvwDw)Dw=min+G.arcsvw；for(j=0；Pvj!=0；j+)Pwj=Pvj；voidPrint_ShortestPath(GraphG,intv0,intPMAX_VERTEX_NUM,intD)/顯示從頂點u到其余頂點的最短路徑及距離intv,j；printf(TheshortestpathfromVertex%dtotheotherVertex:n)；for(v=1；v,v0);for(j=0;Pvj!=0

21、;j+)printf(%d-,Pvj);printf(bbn);3.最短路徑-弗洛依德算法#include#include#include#include#defineINFINITY10000/定義權(quán)值的最大值#defineMAX_NUM20/圖的最大頂點數(shù)enumBOOLFalse,True;typedefstructintarcsMAX_NUMMAX_NUM;/鄰接矩陣intvexnum,arcnum;/圖的當(dāng)前頂點和邊數(shù)Graph;voidCreateGraph(Graph&);/生成圖的鄰接矩陣voidShortestPath_Floyd(Graph,BOOLMAX_NUMMAX_N

22、UM,intMAX_NUM);/用弗洛依德算法求每對頂點之間的最短路徑voidPrint_ShortestPath(Graph,BOOLMAX_NUMMAX_NUM,intMAX_NUM);/顯示用弗洛依德算法所求得的最短路徑voidPrint_OnePath(int,int,int,BOOLMAX_NUMMAX_NUM);/顯示一對頂點之間的最短路徑voidmain()GraphG;/采用鄰接矩陣結(jié)構(gòu)的圖charj=y;intu;BOOLPMAX_NUMMAX_NUMMAX_NUM;/存放每對頂點的最短路徑intDMAX_NUMMAX_NUM;/存放每對頂點的最短路徑的距離printf(本程

23、序演示弗洛依德算法求圖的每一對頂點之間的最短路徑n);printf(“首先輸入圖的頂點和弧的數(shù)目。n例如：3,5n);printf(接著輸入弧(i,j)和其權(quán)值。n例如：n1,2,4n2,1,6n1,3,11n3,1,3n2,3,2n);printf(程序?qū)@示出每對頂點之間的最短路徑值和所經(jīng)過的路徑：n);printf(41-2n61-2-3n52-3-1n22-3n33-1n73-1-2n);while(j!=N&j!=n)CreateGraph(G);/生成鄰接矩陣結(jié)構(gòu)的圖ShortestPath_Floyd(G,P,D);/利用弗洛依德算法求最短路徑Print_ShortestPat

24、h(G,P,D);/顯示每對頂點之間的最短路徑printf(“繼續(xù)執(zhí)行嗎?(Y/N);scanf(%c,&j);printf(程序運行結(jié)束，按任意鍵退出窗口門；getch();voidCreateGraph(Graph&G)/構(gòu)造鄰接矩陣結(jié)構(gòu)的圖Ginti,j;intstart,end,weight;printf(請輸入頂點和弧的數(shù)目，格式：頂點數(shù)，弧數(shù)n);scanf(%d,%d,&G.vexnum,&G.arcnum);/輸入圖的頂點數(shù)和邊數(shù)for(i=1;i=G.vexnum;i+)for(j=1;j=G.vexnum;j+)G.arcsij=INFINITY;/初始化鄰接矩陣print

25、f(請輸入各條弧和其權(quán)值，格式：弧尾，弧頭，權(quán)值：n);for(i=1;i=G.arcnum;i+)scanf(%d,%d,%d,&start,&end,&weight);/輸入邊的起點和終點及權(quán)值G.arcsstartend=weight;voidShortestPath_Floyd(GraphG,BOOLPMAX_NUMMAX_NUM,intDMAX_NUM)用弗洛依德算法求有向網(wǎng)G的每對頂點v和w之間的最短路徑Pvw/及其帶權(quán)路徑長度Dvw,/若Pvwu為True,表明u是從v到w當(dāng)前求得最短路徑上的頂點intu,v,w,i;for(v=1;v=G.vexnum;v+)/各對頂點之間的初

26、始已知路徑及距離for(w=1;w=G.vexnum;w+)Dvw=G.arcsvw;for(u=1;u=G.vexnum;u+)Pvwu=False;if(DvwvINFINITY)從v到w有直接路徑Pvwv=True;Pvww=True;for(u=1;u=G.vexnum;u+)for(v=1;v=G.vexnum;v+)for(w=1;w=G.vexnum;w+)if(Dvu+DuwvDvw&v!=w)/從v經(jīng)u到w的一條路徑更短Dvw=Dvu+Duw;for(i=1;i=G.vexnum;i+)if(Pvui|Puwi)Pvwi=True;voidPrint_ShortestPath

27、(GraphG,BOOLPMAX_NUMMAX_NUM,intDMAX_NUM)/顯示每對頂點之間的最短路徑及距離intv,w,j;printf(”最短路徑：n);for(v=1;v=G.vexnum;v+)for(w=1;w=G.vexnum;w+)if(DvwvINFINITY)頂點v和w之間有通路printf(%-5d,Dvw);從v到w的最短距離Print_OnePath(v,w,G.vexnum,P);/顯示從v到w的最短路徑printf(n);voidPrint_OnePath(intv,intw,intnum,BOOLPMAX_NUMMAX_NUM)/顯示從v到w的最短路徑int

28、i;for(i=1;inum)printf(%d-%d,v,w);/說明從v到w不需經(jīng)過其它的頂點elsePrint_OnePath(v,i,num,P);/否則從v到w需經(jīng)過頂點i，先顯示從v到i的最短路徑if(ielseprintf(bb);Print_OnePath(i,w,num,P);/顯示從i到w的最短路徑實驗六查找算法的實現(xiàn)一、實驗?zāi)康恼莆詹檎业牟煌椒?，并能用高級語言實現(xiàn)查找算法；熟練掌握二叉排序樹的構(gòu)造和查找方法。熟練掌握靜態(tài)查找表及哈希表查找方法。二、實驗內(nèi)容設(shè)計一個讀入一串整數(shù)，然后構(gòu)造二叉排序樹，進(jìn)行查找。三、實驗步驟從空的二叉樹開始，每輸入一個結(jié)點數(shù)據(jù)，就建立一個新結(jié)

29、點插入到當(dāng)前已生成的二叉排序樹中。在二叉排序樹中查找某一結(jié)點。用其它查找算法進(jìn)行排序（課后自己做）。四、實現(xiàn)提示1.定義結(jié)構(gòu)typedefstructnodeintkey;intother;structnode*lchild,*rchild;bstnode;voidinorder(t)if(t!=Null)inorder(t-lchild);printf(“4d篤keyt；inorder(trchild);bstnode*insertbst(t,s)bstnode*s,*t;bstnode*f,*p;p=t;while(p!=Null)f=p;if(skey=pkey)returnt;if(s

30、keyvpkey)p=plchild;elsep=prchild;if(t=Null)returns;if(skeyvfkey)flchild=s;elsefrchild=s;returnt;bstnode*creatord()bstnode*t,*s;intkey;t=Null;scanf(“%d”,&key);while(key!=0)s=malloc(sizeof(bitree);skey=key;slchild=Null;srchild=Null;scanf(“%d”,&data);sother=data;t=insertbst(t,s);scanf(“%d”,&key);return

31、t;五、思考與提高1.用其它的查找方法完成該算法。2.比較各種算法的時間及空間復(fù)雜度。六、完整參考程序1.折半查找#include#include#defineMAX30/定義有序查找表的最大長度typedefstructcharelemMAX;/有序查找表intlength;/length指示當(dāng)前有序查找表的長度SSTable;voidinitial(SSTable&);/初始化有序查找表intsearch(SSTable,int);/在有序查找表中查找元素voidprint(SSTable);/顯示有序查找表中所有元素voidmain()SSTableST;/ST為一有序查找表intch,

32、loc,flag=1;charj;initial(ST);/初始化有序查找表while(flag)printf(“請選擇：n);printf(l.顯示所有元素n);printf(2.查找一個元素n);printf(3.退出n);scanf(%c,&j);switch(j)case1:print(ST);break;/顯示所有元素case2:printf(請輸入要查找的元素：)；scanf(%d,&ch);/輸入要查找的元素的關(guān)鍵字loc=search(ST,ch)；/查找if(loc!=0)printf(該元素所在位置是：dn,loc);顯示該元素位置elseprintf(%d不存在!n,ch

33、);當(dāng)前元素不存在break;default:flag=0;printf(程序運行結(jié)束!按任意鍵退出!n);voidinitial(SSTable&v)/初始化有序查找表inti;printf(請輸入靜態(tài)表的元素個數(shù)：);輸入有序查找表初始化時的長度scanf(%d,&v.length);printf(請從小到大輸N%d個元素(整形數(shù))：n,v.length);getchar();for(i=1;i=v.length;i+)scanf(%d,&v.elemi);/從下到大輸入有序查找表的各元素intsearch(SSTablev,intch)/在有序查找表中查找ch的位置，成功返回其位置，失敗

34、返回0intlow,high,mid;low=1;high=v.length;/置區(qū)間初值while(lowch)high=mid-1;/繼續(xù)在前半?yún)^(qū)間進(jìn)行查找elselow=mid+1;/繼續(xù)在后半?yún)^(qū)間進(jìn)行查找return0;找不到時，i為0voidprint(SSTablev)/顯示當(dāng)前有序查找表所有元素inti;for(i=1;i=v.length;i+)printf(%d,v.elemi);printf(n);2.二叉排序樹的建立與查找#include#include#include#includeenumBOOLFalse,True;typedefstructBiTNode/定義二叉

35、樹節(jié)點結(jié)構(gòu)chardata;/為了方便，數(shù)據(jù)域只有關(guān)鍵字一項structBiTNode*lchild,*rchild;/左右孩子指針域BiTNode,*BiTree;BOOLSearchBST(BiTree,char,BiTree,BiTree&);/在二叉排序樹中查找元素/在二叉排序樹中插入元素/在二叉排序樹中插入元素/在二叉排序樹中刪除元素/刪除二叉排序樹的根結(jié)點/中序遍歷二叉排序樹，即從小到大顯示BOOLDeleteBST(BiTree&,char);voidDelete(BiTree&);voidInorderBST(BiTree);各元素voidmain()BiTreeT,p;cha

36、rch,keyword,j=y;BOOLtemp;T=NULL;while(j!=n)printf(1.displayn);printf(2.searchn);printf(3.insertn);printf(4.deleten);printf(5.exitn);scanf(%c,&ch);/輸入操作選項switch(ch)case1:if(!T)printf(TheBSThasnoelem.n);elseInorderBST(T);printf(n);break;case2:printf(Inputthekeywordofelemtobesearched(achar):);scanf(%c,

37、&keyword);/輸入要查找元素的關(guān)鍵字temp=SearchBST(T,keyword,NULL,p);if(!temp)printf(%cisntexisted!n,keyword);/沒有找到elseprintf(%chasbeenfound!n,keyword);/成功找到break;case3:printf(Inputthekeywordofelemtobeinserted(achar):);scanf(%c,&keyword);/輸入要插入元素的關(guān)鍵字temp=InsertBST(T,keyword);if(!temp)printf(%chasbeenexisted!n,key

38、word);/該元素已經(jīng)存在elseprintf(Sucesstoinert%c!n,keyword);/成功插入break;case4:printf(Inputthekeywordofelemtobedeleted(achar):);scanf(%c,&keyword);/輸入要刪除元素的關(guān)鍵字temp=DeleteBST(T,keyword);if(!temp)printf(%cisntexisted!n,keyword);/該元素不存在elseprintf(Sucesstodelete%cn,keyword);/成功刪除break;default:j=n;printf(Theprogra

39、misover!nPressanykeytoshutoffthewindow!n);getchar();getchar();voidInorderBST(BiTreeT)/以中序方式遍歷二叉排序樹T,即從小到大顯示二叉排序樹的所有元素if(T-lchild)InorderBST(T-lchild);printf(%2c,T-data);if(T-rchild)InorderBST(T-rchild);BOOLSearchBST(BiTreeT,charkey,BiTreef,BiTree&p)/在根指針T所指二叉排序樹中遞歸的查找其關(guān)鍵字等于key的元素，若查找成功則指針p指向該數(shù)據(jù)元素，并返

40、回True，否則指針指向查找路徑上訪問的最后一個結(jié)點并返回False,指針f指向T的雙親，其初始調(diào)用值為NULLBOOLtmp1，tmp2;tmp1=tmp2=False;if(!T)p=f;returnFalse;/查找不成功elseif(key=T-data)p=T;returnTrue;/查找成功elseif(keydata)tmp1=SearchBST(T-lchild,key,T,p);/在左子樹中繼續(xù)查找elsetmp2=SearchBST(T-rchild,key,T,p);/在右子樹中繼續(xù)查找if(tmp1|tmp2)returnTrue;/若在子樹中查找成功，向上級返回Tru

41、eelsereturnFalse;/否則返回FalseBOOLInsertBST(BiTree&T,chare)/當(dāng)二叉排序樹T中不存在元素e時，插入e并返回True,否則返回FalseBiTreep,s;if(!SearchBST(T,e,NULL,p)/查找不成功s=(BiTree)malloc(sizeof(BiTNode);s-data=e;s-lchild=s-rchild=NULL;if(!p)T=s;被插結(jié)點*s為新的根結(jié)點elseif(evp-data)p-lchild=s;被插結(jié)點*s為左孩子elsep-rchild=s;被插結(jié)點*s為右孩子returnTrue;/成功插入e

42、lsereturnFalse;/樹中已存在關(guān)鍵字為e的數(shù)據(jù)元素BOOLDeleteBST(BiTree&T,charkey)/若二叉排序樹T中存在關(guān)鍵字等于key的數(shù)據(jù)元素時，則刪除該數(shù)據(jù)元素結(jié)點并返回True,否則返回FalseBOOLtmpl,tmp2;tmp1=tmp2=False;if(!T)returnFalse;不存在關(guān)鍵字等于key的數(shù)據(jù)元素elseif(key=T-data)Delete(T);returnTrue;找到關(guān)鍵字等于key的數(shù)據(jù)元素并刪除它elseif(keydata)tmpl=DeleteBST(T-lchild,key);/繼續(xù)在左子樹中刪除elsetmp2=

43、DeleteBST(T-rchild,key);/繼續(xù)在右子樹中刪除if(tmpl|tmp2)returnTrue;/在子樹中刪除成功，返回TrueelsereturnFalse;/不存在該元素voidDelete(BiTree&p)/在二叉排序樹中刪除結(jié)點P,并重接它的左或右子樹BiTrees,q;if(!P-rchild)/右子樹空，只需重接它的左子樹q=P;P=P-lchild;free(q);elseif(!P-lchild)/左子樹空，只需重接它的右子樹q=P;P=P-rchild;free(q);else/左右子樹均不空q=P;s=P-lchild;while(s-rchild)q

44、=s;s=s-rchild;/轉(zhuǎn)左，然后向右走到盡頭P-data=s-data;/s指向被刪結(jié)點的“前驅(qū)”if(q!=p)q-rchild=s-rchild;重接*q的右子樹elseq-lchild=s-lchild;重接*q的左子樹free(s);實驗七排序算法的實現(xiàn)一、實驗?zāi)康恼莆粘Ｓ玫呐判蚍椒?，并掌握用高級語言實現(xiàn)排序算法的方法；深刻理解排序的定義和各種排序方法的特點，并能加以靈活應(yīng)用；了解各種方法的排序過程及其時間復(fù)雜度的分析方法。二、實驗內(nèi)容統(tǒng)計成績給出n個學(xué)生的考試成績表，每條信息由姓名和分?jǐn)?shù)組成，試設(shè)計一個算法：（1）按分?jǐn)?shù)高低次序，打印出每個學(xué)生在考試中獲得的名次，分?jǐn)?shù)相同的為

45、同一名次；（2）按名次列出每個學(xué)生的姓名與分?jǐn)?shù)。三、實驗步驟定義結(jié)構(gòu)體。定義結(jié)構(gòu)體數(shù)組。定出主程序，對數(shù)據(jù)進(jìn)行排序。四、實現(xiàn)提示#definen30typedefstructstudentcharname8;intscore;studentRn;main()intnum,i,j,max,temp;printf(“n請輸入學(xué)生成績:n”);for(i=0;in;i+)printf(“姓名:”);scanf(“%s”,&);scanf(“%4d”,&stui.score);num=1;for(i=0;in;i+)max=i;for(j=i+1;jRmax.score)max=j;

46、if(max!=i)temp=Rmax;Rmax=Ri;Ri=temp;if(i0)&(Ri.scoreRi-1.score)num=num+1;printf(“%4d%s%4d”,num,R,Ri.score);五、思考與提高快速排序算法解決本問題。較各種排序算法的優(yōu)缺點及。使用其它排序算法實現(xiàn)該問題(直接插入排序、希爾排序、簡單選擇排序、堆排序等)。六、完整參考程序1.直接插入排序#include#include#include#include#defineMAXSIZE20/排序表的最大容量typedefstruct/定義排序表的結(jié)構(gòu)intelemwordMAXSIZE;/數(shù)

47、據(jù)元素關(guān)鍵字intcount;/表中當(dāng)前元素的個數(shù)SqList;voidInitialSqList(SqList&);/初始化排序表voidInsertSort(SqList&);/直接插入排序voidPrintSqList(SqList);/顯示表中的所有元素voidmain()SqListL;/聲明表Lcharj=y;printf(本程序?qū)⒀菔局苯硬迦肱判虻牟僮鳌);while(j!=n&j!=N)InitialSqList(L);InsertSort(L);PrintSqList(L);printf(”繼續(xù)進(jìn)行下一次排序嗎?(Y/N);scanf(%c,&j);printf(”程序運行

48、結(jié)束!n按任意鍵關(guān)閉窗口!n);getchar();getchar();voidInitialSqList(SqList&L)/表初始化inti;printf(”請輸入待排序的記錄的個數(shù):”)；scanf(%d,&L.count);printf(”請輸入待排序的記錄的關(guān)鍵字(整型數(shù)):n);for(i=1;i=L.count;i+)scanf(%d,&L.elemwordi);voidInsertSort(SqList&L)inti,j;for(i=2;i=L.count;i+)if(L.elemwordivL.elemwordi-l)/,需將L.elemwordi插入有序子表L.elemwo

49、rd0=L.elemwordi;復(fù)制為哨兵for(j=i-l;L.elemword0L.elemwordj;-j)L.elemwordj+l=L.elemwordj;/記錄后移L.elemwordj+l=L.elemword0;/插入到正確的位置voidPrintSqList(SqListL)/顯示表所有元素inti;printf(已排好序的序列如下：n);for(i=l;i=L.count;i+)printf(%4d,L.elemwordi);printf(n);2.希爾排序#include#include#include#include#defineMAXSIZE20/排序表的最大容量ty

50、pedefstruct/typedefstruct/定義排序表的結(jié)構(gòu)intelemwordMAXSIZE;/數(shù)據(jù)元素關(guān)鍵字intcount;/表中當(dāng)前元素的個數(shù)SqList;voidInitialSqList(SqList&);/初始化排序表voidShellSort(SqList&,int,int);希爾排序voidShellInsert(SqList&,int);/一趟希爾排序voidPrintSqList(SqList);/顯示表中的所有元素voidmain()SqListL;聲明表Lcharj=y;intdlta3=5,3,1;/希爾排序增量序列，本程序采用5，3，1序列intt=3;

51、/希爾排序增量序列中增量的個數(shù)printf(本程序?qū)⒀菔鞠柵判虻牟僮?。n增量序列為5,3,1on);while(j!=n&j!=N)InitialSqList(L);/待排序列初始化ShellSort(L,dlta,t);/希爾排序PrintSqList(L);/顯示希爾排序結(jié)果printf(”繼續(xù)進(jìn)行下一次排序嗎?(Y/N);scanf(%c,&j);printf(”程序運行結(jié)束!n按任意鍵關(guān)閉窗口!n);getchar();getchar();voidInitialSqList(SqList&L)/表初始化inti;printf(”請輸入待排序的記錄的個數(shù):”)；scanf(%d,&L.

52、count);printf(請輸入待排序的記錄的關(guān)鍵字(整型數(shù)):n);for(i=1;i=L.count;i+)scanf(%d,&L.elemwordi);voidShellSort(SqList&L,intdlta,intt)/按增量序列dltaO.t-l對順序表L作希爾排序for(intk=0;kt;+k)SheHInsert(L,dltak);一趟增量為dltak的插入排序voidShellInsert(SqList&L,intdk)/對順序表L做一趟希爾插入排序。本算法是和一趟直接插入排序相比作了以下修改：/1.前后記錄的增量是dk，而不是1/2.0號單元只是暫存單元，不是哨兵。當(dāng)j=0時，插入位置已找到inti,j;for(i=dk+1;i=L.