数据结构树的有关算法.doc

数据结构课程设计任务书 学期：11-12-2 班级：网络10一、设计目的数据结构是一门实践性较强的专业基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。二、设计要求1、通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。2、学生必须仔细研读数据结构课程设计(实习)要求，以学生自学为主、指导教师指导为辅，认真、独立地完成课程设计的任务，有问题及时主动与指导教师沟通。3、本次课程设计按照教学要求需要在一周半时间内独立完成，学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时地向指导教师汇报。4、编程语言任选。三、设计选题题一：线索二叉树（*）任务：1. 建立中序线索二叉树，并且中序遍历； 2. 求中序线索二叉树上已知结点中序的前驱和后继；需求分析和概要设计：建立中序线索二叉树，并且中序遍历。首先就是要建立树，再将树中序线索化。求中序线索二叉树上已知结点中序的前驱和后继时，即是将树在遍历一遍。也可以在遍历的过程中，将树的结点放在数组中，当然必须讲述先遍历一遍，这是用空间来换时间。详细设计：树的结构体的声明：typedef char TElemtype;typedef enum PointerTagLink,Thread; /设置标志：Link为指针，Thread为线索typedef struct BiThrNode /树结点结构体TElemtype data;struct BiThrNode *lchild,*rchild;PointerTag LTag,RTag;BiThrNode,*BiThrTree;相关函数的声明：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(); /求已知结点中序的前驱和后继初始化树：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; /设置头结点if(!Thrt) exit(1);Thrt-LTag = Link; /头结点左边标志为指针 Thrt-RTag =Thread; /右边的为线索Thrt-rchild = Thrt; /有孩子指向头结点本身if(!T) Thrt-lchild = Thrt;/若树根结点为空，则头结点左孩子指向头结点else /若根结点不为空，Thrt-lchild = T; /头结点左孩子指向根结点pre = Thrt; /设置指针pre指向头结点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; /将结点存于数组中i+;length+;p = p-rchild;return OK;测试结果和设计心得体会：通过对树的中序线索化使我更加清楚树的有关操作算法。题二：最小生成树问题（*）【问题描述】若要在n个城市之间建设通信网络，只需要假设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。【系统要求】1 利用克鲁斯卡尔算法求网的最小生成树。2 利用普里姆算法求网的最小生成树。3 要求输出各条边及它们的权值。【测试数据】由学生任意指定，但报告上要求写出多批数据测试结果。【实现提示】通信线路一旦建成，必然是双向的。因此，构造最小生成树的网一定是无向网。设图的顶点数不超过30个，并为简单起见，网中边的权值设成小于100的整数，可利用C语言提供的随机函数产生。图的存储结构的选取应和所作操作相适应。为了便于选择权值最小的边，此题的存储结构既不选用邻接矩阵的数组表示法，也不选用邻接表，而是以存储边（带权）的数组表示图。【选作内容】利用堆排序实现选择权值最小的边。需求分析和概要设计：用克鲁斯卡尔和普里姆算法生成图的最小生成树。首先要构造出图，然后将图生成树，故要使用邻接矩阵储存图。详细设计：有关结构体的声明：typedef char VertexType;typedef int VRType;typedef char InfoType;typedef struct ArcCellVRType adj; /VRType是顶点的关系类型。无权图用1或0表示相连否。对带权图，则为权值类型。InfoType *info; /表示相关信息的指针ArcCell,AdjMatrixMAX_VEXTEX_NUMMAX_VEXTEX_NUM;typedef structVertexType vexsMAX_VEXTEX_NUM; /顶点向量AdjMatrix arcs; /邻接矩阵int vexnum,arcnum; /图的当前顶点数和弧度数MGraph;typedef structVertexType adjvex;VRType lowcost;closedge;typedef structVertexType begin;VertexType end;VRType weight;EdgeType;相关函数的声明：int CreateGraph(MGraph &G); /创造图后要返回其值int LocateVex(MGraph G,VertexType u); /求点u在图中的位置int minmum(closedge closedgeMAX_VEXTEX_NUM);/求最小值函数void MinSpanTree_PRIM(MGraph G,VertexType u); /PRIM最小生成树void MinSpanTree_KRUSKAL(MGraph G); / KRUSKAL最小生成树创造图：int CreateGraph(MGraph &G) int i,j,k,w;VertexType v1,v2;cout请输入顶点数和边数G.vexnumG.arcnum;high=G.arcnum;cout请输入顶点信息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请输入每条边对应的两个顶点(v1,v2)及其权值(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)权值：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)权值：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请输入结点的信息data;118. for(int i=1;i=length;i+)119. 120. if(data=ai)121. 122. flag = true;123. if(i=1)124. coutdata的前驱为NILendl;125. else126. coutdata的前驱为ai-1endl;127. if(i=length)128. coutdata的后继为NILendl;129. else130. coutdata的后继为ai+1endl;131. 132. 133. if(!flag)134. cout没有该节点endl;135. cout是否继续查找(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二叉树的根为(当输入时表示结点为空):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 /最多结点数 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是顶点的关系类型。无权图用1或0表示相连否。对带权图，则为权值类型。13. InfoType *info; /表示相关信息的指针14. ArcCell,AdjMatrixMAX_VEXTEX_NUMMAX_VEXTEX_NUM;15. typedef struct16. VertexType vexsMAX_VEXTEX_NUM; /顶点向量17. AdjMatrix arcs; /邻接矩阵18. int vexnum,arcnum; /图的当前顶点数和弧度数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); /创造图后要返回其值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请输入顶点数和边数G.vexnumG.arcnum;44. high=G.arcnum;45. cout请输入顶点信息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请输入每条边对应的两个顶点(v1,v2)及其权值(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)权值：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) /权值堆排序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.