數(shù)據(jù)結(jié)構(gòu)樹的有關(guān)算法.doc

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書 學(xué)期：11-12-2 班級(jí)：網(wǎng)絡(luò)10一、設(shè)計(jì)目的數(shù)據(jù)結(jié)構(gòu)是一門實(shí)踐性較強(qiáng)的專業(yè)基礎(chǔ)課程，為了學(xué)好這門課程，必須在掌握理論知識(shí)的同時(shí)，加強(qiáng)上機(jī)實(shí)踐。本課程設(shè)計(jì)的目的就是要達(dá)到理論與實(shí)際應(yīng)用相結(jié)合，使同學(xué)們能夠根據(jù)數(shù)據(jù)對(duì)象的特性，學(xué)會(huì)數(shù)據(jù)組織的方法，能把現(xiàn)實(shí)世界中的實(shí)際問題在計(jì)算機(jī)內(nèi)部表示出來，并培養(yǎng)基本的、良好的程序設(shè)計(jì)技能。二、設(shè)計(jì)要求1、通過這次設(shè)計(jì)，要求在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇應(yīng)用、算法的設(shè)計(jì)及其實(shí)現(xiàn)等方面加深對(duì)課程基本內(nèi)容的理解。同時(shí)，在程序設(shè)計(jì)方法以及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。2、學(xué)生必須仔細(xì)研讀數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(實(shí)習(xí))要求，以學(xué)生自學(xué)為主、指導(dǎo)教師指導(dǎo)為輔，認(rèn)真、獨(dú)立地完成課程設(shè)計(jì)的任務(wù)，有問題及時(shí)主動(dòng)與指導(dǎo)教師溝通。3、本次課程設(shè)計(jì)按照教學(xué)要求需要在一周半時(shí)間內(nèi)獨(dú)立完成，學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課設(shè)的時(shí)間計(jì)劃，并在課設(shè)過程中不斷檢測(cè)自己的計(jì)劃完成情況，及時(shí)地向指導(dǎo)教師匯報(bào)。4、編程語言任選。三、設(shè)計(jì)選題題一：線索二叉樹（*）任務(wù)：1. 建立中序線索二叉樹，并且中序遍歷； 2. 求中序線索二叉樹上已知結(jié)點(diǎn)中序的前驅(qū)和后繼；需求分析和概要設(shè)計(jì)：建立中序線索二叉樹，并且中序遍歷。首先就是要建立樹，再將樹中序線索化。求中序線索二叉樹上已知結(jié)點(diǎn)中序的前驅(qū)和后繼時(shí)，即是將樹在遍歷一遍。也可以在遍歷的過程中，將樹的結(jié)點(diǎn)放在數(shù)組中，當(dāng)然必須講述先遍歷一遍，這是用空間來換時(shí)間。詳細(xì)設(shè)計(jì)：樹的結(jié)構(gòu)體的聲明：typedef char TElemtype;typedef enum PointerTagLink,Thread; /設(shè)置標(biāo)志：Link為指針，Thread為線索typedef struct BiThrNode /樹結(jié)點(diǎn)結(jié)構(gòu)體TElemtype data;struct BiThrNode *lchild,*rchild;PointerTag LTag,RTag;BiThrNode,*BiThrTree;相關(guān)函數(shù)的聲明：void InitBiTree(BiThrTree &T); /初始化樹 void CreatBiTree(BiThrTree &T); /建立二叉樹void InOrderThreading(BiThrTree &Thrt,BiThrTree &T); /中序線索二叉樹void InThreading(BiThrTree p); /線索化int InOrderTraverse_Thr(BiThrTree T); /中序遍歷void InOrderThread_BeAf(); /求已知結(jié)點(diǎn)中序的前驅(qū)和后繼初始化樹：void InitBiTree(BiThrTree &T)T = new BiThrNode;if(!T) exit(1);T = NULL;建立二叉樹：void CreatBiTree(BiThrTree &T)char ch;cinch;if(ch = ) T = NULL;else T = new BiThrNode;if(!T) exit(1);T-data = ch;CreatBiTree(T-lchild);CreatBiTree(T-rchild); 中序線索二叉樹：void InOrderThreading(BiThrTree &Thrt,BiThrTree &T)Thrt = new BiThrNode; /設(shè)置頭結(jié)點(diǎn)if(!Thrt) exit(1);Thrt-LTag = Link; /頭結(jié)點(diǎn)左邊標(biāo)志為指針 Thrt-RTag =Thread; /右邊的為線索Thrt-rchild = Thrt; /有孩子指向頭結(jié)點(diǎn)本身if(!T) Thrt-lchild = Thrt;/若樹根結(jié)點(diǎn)為空，則頭結(jié)點(diǎn)左孩子指向頭結(jié)點(diǎn)else /若根結(jié)點(diǎn)不為空，Thrt-lchild = T; /頭結(jié)點(diǎn)左孩子指向根結(jié)點(diǎn)pre = Thrt; /設(shè)置指針pre指向頭結(jié)點(diǎn)InThreading(T); /線索化樹Tpre-rchild = Thrt;pre-RTag = Thread;Thrt-rchild = pre;線索化樹:void InThreading(BiThrTree p)if(p)InThreading(p-lchild); /線索化左子樹if(!p-lchild) p-LTag = Thread;p-lchild = pre;if(!pre-rchild)pre-RTag = Thread;pre-rchild = p;pre = p;InThreading(p-rchild);中序遍歷：int InOrderTraverse_Thr(BiThrTree T)BiThrTree p;int i=1;p = T-lchild;while(p!=T)while(p-LTag!=Thread)p = p-lchild;coutdatadata;i+;length+;while(p-RTag=Thread&p-rchild!=T)p = p-rchild;coutdatadata; /將結(jié)點(diǎn)存于數(shù)組中i+;length+;p = p-rchild;return OK;測(cè)試結(jié)果和設(shè)計(jì)心得體會(huì)：通過對(duì)樹的中序線索化使我更加清楚樹的有關(guān)操作算法。題二：最小生成樹問題（*）【問題描述】若要在n個(gè)城市之間建設(shè)通信網(wǎng)絡(luò)，只需要假設(shè)n-1條線路即可。如何以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)，是一個(gè)網(wǎng)的最小生成樹問題。【系統(tǒng)要求】1 利用克魯斯卡爾算法求網(wǎng)的最小生成樹。2 利用普里姆算法求網(wǎng)的最小生成樹。3 要求輸出各條邊及它們的權(quán)值?！緶y(cè)試數(shù)據(jù)】由學(xué)生任意指定，但報(bào)告上要求寫出多批數(shù)據(jù)測(cè)試結(jié)果?！緦?shí)現(xiàn)提示】通信線路一旦建成，必然是雙向的。因此，構(gòu)造最小生成樹的網(wǎng)一定是無向網(wǎng)。設(shè)圖的頂點(diǎn)數(shù)不超過30個(gè)，并為簡(jiǎn)單起見，網(wǎng)中邊的權(quán)值設(shè)成小于100的整數(shù)，可利用C語言提供的隨機(jī)函數(shù)產(chǎn)生。圖的存儲(chǔ)結(jié)構(gòu)的選取應(yīng)和所作操作相適應(yīng)。為了便于選擇權(quán)值最小的邊，此題的存儲(chǔ)結(jié)構(gòu)既不選用鄰接矩陣的數(shù)組表示法，也不選用鄰接表，而是以存儲(chǔ)邊（帶權(quán)）的數(shù)組表示圖。【選作內(nèi)容】利用堆排序?qū)崿F(xiàn)選擇權(quán)值最小的邊。需求分析和概要設(shè)計(jì)：用克魯斯卡爾和普里姆算法生成圖的最小生成樹。首先要構(gòu)造出圖，然后將圖生成樹，故要使用鄰接矩陣儲(chǔ)存圖。詳細(xì)設(shè)計(jì)：有關(guān)結(jié)構(gòu)體的聲明：typedef char VertexType;typedef int VRType;typedef char InfoType;typedef struct ArcCellVRType adj; /VRType是頂點(diǎn)的關(guān)系類型。無權(quán)圖用1或0表示相連否。對(duì)帶權(quán)圖，則為權(quán)值類型。InfoType *info; /表示相關(guān)信息的指針ArcCell,AdjMatrixMAX_VEXTEX_NUMMAX_VEXTEX_NUM;typedef structVertexType vexsMAX_VEXTEX_NUM; /頂點(diǎn)向量AdjMatrix arcs; /鄰接矩陣int vexnum,arcnum; /圖的當(dāng)前頂點(diǎn)數(shù)和弧度數(shù)MGraph;typedef structVertexType adjvex;VRType lowcost;closedge;typedef structVertexType begin;VertexType end;VRType weight;EdgeType;相關(guān)函數(shù)的聲明：int CreateGraph(MGraph &G); /創(chuàng)造圖后要返回其值int LocateVex(MGraph G,VertexType u); /求點(diǎn)u在圖中的位置int minmum(closedge closedgeMAX_VEXTEX_NUM);/求最小值函數(shù)void MinSpanTree_PRIM(MGraph G,VertexType u); /PRIM最小生成樹void MinSpanTree_KRUSKAL(MGraph G); / KRUSKAL最小生成樹創(chuàng)造圖：int CreateGraph(MGraph &G) int i,j,k,w;VertexType v1,v2;cout請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)G.vexnumG.arcnum;high=G.arcnum;cout請(qǐng)輸入頂點(diǎn)信息endl;for(i=0;iG.vexsi;for(i=0;iG.vexnum;+i) /初始化鄰接矩陣for(j=0;jG.vexnum;+j)G.arcsij.adj =INFINITY; /最大值G.=NULL;cout請(qǐng)輸入每條邊對(duì)應(yīng)的兩個(gè)頂點(diǎn)(v1,v2)及其權(quán)值(w)endl;for(k=0;kv1v2w;i=LocateVex(G,v1);j=LocateVex(G,v2);edgesk+1.begin=v1;edgesk+1.end=v2;G.arcsij.adj=w;G.arcsji.adj=w;edgesk+1.weight=w;return OK;PRIM最小生成樹：void MinSpanTree_PRIM(MGraph G,VertexType u)int k,j,i;closedge closedgeMAX_VEXTEX_NUM;cinu;k=LocateVex(G,u);for(j=0;jG.vexnum;+j)closedgej.adjvex=u;closedgej.lowcost=G.arcskj.adj;closedgek.lowcost=0;for(i=1;iG.vexnum;+i)k=minmum(closedge);cout邊：(closedgek.adjvex,G.vexsk)權(quán)值：closedgek.lowcostendl;closedgek.lowcost=0;for(j=1;jG.vexnum;+j)if(G.arcskj.adjclosedgej.lowcost)closedgej.adjvex=G.vexsk;closedgej.lowcost=G.arcskj.adj; KRUSKAL最小生成樹：void MinSpanTree_KRUSKAL(MGraph G)HeapSort();for(int k=1;k=G.arcnum;k+)coutedgesk.weight ;coutendl;int fatherMAX_VEXTEX_NUM;int i,j,vf1,vf2;for(i=0;iG.vexnum;i+)fatheri=-1;i=0;j=0;while(iG.arcnum&jG.vexnum-1)vf1=Find(father,edgesi+1.begin);vf2=Find(father,edgesi+1.end);if(vf1!=vf2)fathervf2=vf1;j+;cout邊：(edgesi+1.begin,edgesi+1.end)權(quán)值：edgesi+1.weightch;38. if(ch = ) T = NULL;39. else 40. 41. T = new BiThrNode;42. if(!T) exit(1);43. T-data = ch;44. CreatBiTree(T-lchild);45. CreatBiTree(T-rchild);46. 47. 48. void InOrderThreading(BiThrTree &Thrt,BiThrTree &T)49. 50. Thrt = new BiThrNode;51. if(!Thrt) exit(1);52. Thrt-LTag = Link;53. Thrt-RTag =Thread;54. Thrt-rchild = Thrt;55. if(!T) Thrt-lchild = Thrt;56. else57. 58. Thrt-lchild = T;59. pre = Thrt;60. InThreading(T);61. pre-rchild = Thrt;62. pre-RTag = Thread;63. Thrt-rchild = pre;64. 65. 66. void InThreading(BiThrTree p)67. 68. 69. if(p)70. 71. InThreading(p-lchild);72. if(!p-lchild)73. 74. p-LTag = Thread;75. p-lchild = pre;76. 77. if(!pre-rchild)78. 79. pre-RTag = Thread;80. pre-rchild = p;81. 82. pre = p;83. InThreading(p-rchild);84. 85. 86. int InOrderTraverse_Thr(BiThrTree T)87. 88. BiThrTree p;89. int i=1;90. p = T-lchild;91. while(p!=T)92. 93. while(p-LTag!=Thread)94. p = p-lchild;95. coutdatadata;97. i+;98. length+;99. while(p-RTag=Thread&p-rchild!=T)100. 101. p = p-rchild;102. coutdatadata;104. i+;105. length+;106. 107. p = p-rchild;108. 109. return OK;110. 111. void InOrderThread_BeAf()112. 113. char YES;114. TElemtype data;115. bool flag=false;116. cout請(qǐng)輸入結(jié)點(diǎn)的信息data;118. for(int i=1;i=length;i+)119. 120. if(data=ai)121. 122. flag = true;123. if(i=1)124. coutdata的前驅(qū)為NILendl;125. else126. coutdata的前驅(qū)為ai-1endl;127. if(i=length)128. coutdata的后繼為NILendl;129. else130. coutdata的后繼為ai+1endl;131. 132. 133. if(!flag)134. cout沒有該節(jié)點(diǎn)endl;135. cout是否繼續(xù)查找(Y/N)YES;137. if(YES=Y|YES=y)138. InOrderThread_BeAf();139. 140. void main()141. 142. BiThrTree T;143. InitBiTree(T);144. cout建立二叉樹endl;145. cout二叉樹的根為(當(dāng)輸入時(shí)表示結(jié)點(diǎn)為空):endl;146. CreatBiTree(T);147. InOrderThreading(Thrt,T);148. cout中序遍歷為：endl;149. InOrderTraverse_Thr(Thrt);150. coutendl;151. InOrderThread_BeAf();152. 3. 最小生成樹代碼：1.#include iostream2.using namespace std;3.#define OK 14. #define ERROR 05. #define MAX_VEXTEX_NUM 30 /最多結(jié)點(diǎn)數(shù) 6. #define MAX_ARC_NUM 1000 7. #define INFINITY INT_MAX /最大值8. typedef char VertexType;9. typedef int VRType;10. typedef char InfoType;11. typedef struct ArcCell12. VRType adj; /VRType是頂點(diǎn)的關(guān)系類型。無權(quán)圖用1或0表示相連否。對(duì)帶權(quán)圖，則為權(quán)值類型。13. InfoType *info; /表示相關(guān)信息的指針14. ArcCell,AdjMatrixMAX_VEXTEX_NUMMAX_VEXTEX_NUM;15. typedef struct16. VertexType vexsMAX_VEXTEX_NUM; /頂點(diǎn)向量17. AdjMatrix arcs; /鄰接矩陣18. int vexnum,arcnum; /圖的當(dāng)前頂點(diǎn)數(shù)和弧度數(shù)19. MGraph;20. typedef struct21. VertexType adjvex;22. VRType lowcost;23. closedge;24. typedef struct25. VertexType begin;26. VertexType end;27. VRType weight;28. EdgeType;29. MGraph G;30. EdgeType edgesMAX_ARC_NUM;31. int high;32. int CreateGraph(MGraph &G); /創(chuàng)造圖后要返回其值33. int LocateVex(MGraph G,VertexType u);34. int minmum(closedge closedgeMAX_VEXTEX_NUM);35. void MinSpanTree_PRIM(MGraph G,VertexType u);36. void MinSpanTree_KRUSKAL(MGraph G);37.38. int CreateGraph(MGraph &G)39. 40. int i,j,k,w;41. VertexType v1,v2;42. cout請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)G.vexnumG.arcnum;44. high=G.arcnum;45. cout請(qǐng)輸入頂點(diǎn)信息endl;46. for(i=0;iG.vexsi;48. for(i=0;iG.vexnum;+i) /初始化鄰接矩陣49. 50. for(j=0;jG.vexnum;+j)51. 52. G.arcsij.adj =INFINITY;53. G.=NULL;54. 55. 56. cout請(qǐng)輸入每條邊對(duì)應(yīng)的兩個(gè)頂點(diǎn)(v1,v2)及其權(quán)值(w)endl;57. for(k=0;kv1v2w;60. i=LocateVex(G,v1);61. j=LocateVex(G,v2);62. edgesk+1.begin=v1;63. edgesk+1.end=v2;64. G.arcsij.adj=w;65. G.arcsji.adj=w;66. edgesk+1.weight=w;67. 68. return OK;69. 70. int LocateVex(MGraph G,VertexType u)71. 72. int i;73. for(i=0;iG.vexnum;i+)74. 75. if(u=G.vexsi)76. return i;77. 78. return OK;79. 80. int minmum(closedge closedgeMAX_VEXTEX_NUM)81. 82. int j,k;83. int mincost;84. mincost=INFINITY;85. for(j=0;jG.vexnum;+j)86. 87. if(closedgej.lowcost!=0&closedgej.lowcostu;100. k=LocateVex(G,u);101. for(j=0;jG.vexnum;+j)102. 103. closedgej.adjvex=u;104. closedgej.lowcost=G.arcskj.adj;105. 106. closedgek.lowcost=0;107. for(i=1;iG.vexnum;+i)108. 109. k=minmum(closedge);110. cout邊：(closedgek.adjvex,G.vexsk)權(quán)值：closedgek.lowcostendl;111. closedgek.lowcost=0;112. for(j=1;jG.vexnum;+j)113. if(G.arcskj.adjclosedgej.lowcost)114. 115. closedgej.adjvex=G.vexsk;116. closedgej.lowcost=G.arcskj.adj;117. 118. 119. 120. void HeapAdjust(int s,int high) /權(quán)值堆排序121. 122. edges0.weight=edgess.weight;123. edges0.begin=edgess.begin;124. edges0.end=edgess.end;125. for(int j=2*s;j=high;j*=2)126. 127. if(jhigh&edgesj.weight=edgesj.weight)130. break;131. edgess.weight=edgesj.weight;132. edgess.begin=edgesj.begin;133. edgess.end=edgesj.end;134. s=j;135. 136. edgess.weight=edges0.weight;137. edgess.begin=edges0.begin;138. edgess.end=edges0.end;139. 140. void HeapSort()141. 142. for(int i=high/2;i0;-i)143. HeapAdjust(i,high);144. for(i=high;i1;-i)145. 146. edges0.weight=edges1.weight;147. edges0.begin=edges1.begin;148. edges0.end=edges1.