《数据结构课程设计关于最短路径问题+二叉树排序问题.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计关于最短路径问题+二叉树排序问题.doc（34页珍藏版）》请在三一办公上搜索。
1、 课程设计综合成绩评定设计题目一： 二 叉 排 序 树 设计题目二： 最 短 路 径 问 题 设计题目三： 考核项目分值AC得分设计情况（共70分）设计工作量与难度20设计工作量大与设计有一定难度设计工作量与难度一般，基本达到了要求设计方案15设计方案正确、合理设计方案较正确、基本合理，但不是最优设计完成情况35完成了选题的设计内容，设计功能完整，相关算法设计正确，程序结果正确、直观性好基本完成了选题的设计内容及主要选题功能，相关算法设计基本正确，程序结果正确设计报告（共15分）报告组织结构及内容10内容组织及结构合理、内容充实、层次清晰、图表得当内容组织及结构较合理、内容较充实、层次较清晰、
2、图表应用基本得当报告排版格式5格式规范，完全符合要求格式基本规范，基本符合要求设计态度（共15分）15设计态度认真、积极设计态度比较认真综合得分课程设计综合成绩（折合为优、良、中、及格与不及格计）其它说明：目 录1.二叉排序树11.1 问题描述11.2 设计方案与概要设计21.3 详细设计41.4 程序运行说明与结果112.最短路径问题132.1 问题描述132.2 设计方案与概要设计162.3 详细设计172.4 程序运行说明与结果273.总结与分析321. 二叉排序树1.1 问题描述知二叉排序树的二叉链表存储结构的类型定义如下：typedef struct node int data; /
3、用整数表示一个结点的名 struct node *LChild,*RChild; /左右指针域BSTNode,*BSTree; （1）键盘输入一个元素序列创建一棵如图（1）的二叉排序树，并输出该二叉排序树的中序遍历序列；45556053402370371224 图（1） （2）在图（1）中所得的二叉排序树中插入一个值为58的结点，输出它的中序遍历序列； （3）在题（2）中所得的二叉排序树中删除值为45的结点，输出它的中序遍历序列；（4）我们知道教材中P220给出的二叉排序树的删除操作算法中，是用左子树中最右下结点来替代要被删除的结点（即为要被删除结点的中序前驱），也可以用右子树中最左下结点来替
4、代要被删除的结点（即为要被删除结点的中序后继），根据此思路修改P220算法在写一个删除操作，并利用修改后的删除算法删除图（1）中二叉排序树的值为45的结点，输出它的中序遍历序列；（5）利用题（2）中所得的二叉排序树的所有叶子结点构造一个带头结点的单链表L。要求不能破坏这棵二叉排序树。所得的单链表L元素递增，并输出单链表L。（6）设计算法将图（1）的二叉排序树的左右子树进行交换。最后输出所得到的二叉树的中序遍历序列。45556053402370371224所得二叉排序树如图所示： 图（2）（7）用计算法统计并输出图（1）中所得的二叉排序树中只有一个孩子结点的结点个数。（8）由图（1）的二叉排序树
5、，用计算法并编写程序输出结点40的所有祖先结点。1.2 设计方案与概要设计1. 二叉排序树应用的存储结构 typedef struct node / 二叉排序树的存储结构 int data; struct node *LChild,*RChild; BSTNode,*BSTree; typedef struct LNode /单链表的存储结构 int data; struct LNode *next; LNode,*LinkList;二叉排序树的设计用到了单链表L。单链表L主要用于题（5）的设计，用来存储图（1）的二叉排序树中所有叶子结点，并将其输出。2.方案设计本方案设计主要应用二叉树的性质
6、。创建空二叉排序树T，再输入图（1）中的元素后向T插入所有元素，在插入时比根结点小的放在树的左子树，比根结点大则放在树的右子树，同时树的左右子树也要遵循这个规律。在删除操作中当只有一个结点时可直接删除，否则用左子树中最右下结点来替代要被删除的结点进行删除操作，亦可用右子树中最左下结点来替代要被删除的结点进行删除操作，可视为同种删除方法。寻找叶子节点时主要采用递归方法，从根结点开始遍历当发现结点无左右孩子时则得到当前的结点元素并用尾插法将其放入单链表中直至遍历完毕，最后输出单链表L。在二叉排序树进行左右子树交换时新创建树R避免对树T的干扰，把树T复制给树R,调用树R采用递归法和交换法进行左右子树
7、的交换。寻找只有一个孩子结点的结点个数时也是采用递归法，从根结点开始遍历当发现结点只有左孩子或右孩子是则计数加1直至遍历完毕，输出最后的计数。在取某元素的祖先结点时，从根结点与该元素对比并寻找该元素，其所走路径即为该元素的祖先结点路径，因此用数组将该路径存储起来，并将其输出。3. 设计程序的整体功能结构（整体算法的描述）void create(BSTree &T):用来创建树，输入树的所有元素；int search(BSTree T,int K,BSTree &q)：对树进行查找，判断元素是否存在树中；void insert(BSTree &T,int e)：对树进行元素插入；void del
8、eteBST(BSTree &T,int k,int &e)：删除中序前驱，用左子树中最右下结点来替代要被删除的结点；void deleteBST1(BSTree &T,int k,int &e)：删除中序后驱，用右子树中最左下结点来替代要被删除的结点；void outTree(BSTree &T)：中序遍历函数，并输出T;int createList(LinkList &L): 创建单链表L并为空;int insertList(LinkList &L,int e)：用尾插法向单链表插入元素；void leaf(BSTree T,LinkList &L)：得到树T的叶子节点，并得到其结点； v
9、oid outList(LinkList L)：输出点链表； BSTree copy(BSTree T)：创建树R,把树T复制给R；void create1(BSTree &R)：把树R的左右子树进行交换； int jie(BSTree R)：计算只有一个孩子结点元素的个数; void bstree(BSTree R,int e)：得到某元素的祖先结点并将其输出； int main()：主函数; 1.3 详细设计 #include #include #define TRUE 1#define FALSE 0#define MAX 20 typedef struct node / 二叉排序树的存
10、储结构 int data; /用整数表示一个结点的名 struct node *LChild,*RChild; /左右指针域BSTNode,*BSTree; typedef struct LNode /单链表的存储结构 int data; struct LNode *next; LNode,*LinkList;创建树函数：void create(BSTree &T) int e; BSTree q; T=NULL; printf(请输入二叉树的根：); scanf(%d,&e); printf(依次输入个结点以-1结束：n); while(e!=-1) if(!search(T,e,q) in
11、sert(T,e); scanf(%d,&e); 树元素查找函数：int search(BSTree T,int K,BSTree &q) BSTree p,f; p=T; f=NULL; if(p=NULL) return FALSE; while(p) if(K=p-data) q=p; return TRUE; else if(Kdata) f=p; p=p-LChild; else f=p; p=p-RChild; q=f; return FALSE; 对树进行插入函数：void insert(BSTree &T,int e) BSTree p,q; if(T=NULL) p=(BST
12、ree)malloc(sizeof(BSTNode); p-data=e; p-LChild=p-RChild=NULL; T=p; else if(!search(T,e,q) p=(BSTree)malloc(sizeof(BSTNode); p-data=e; p-LChild=p-RChild=NULL; if(edata) q-LChild=p; else q-RChild=p; 删除函数（删除中序前驱）： void deleteBST(BSTree &T,int k,int &e) BSTree q,s,v,t; q=T; v=NULL; while(q) if(k=q-data)
13、 break; else if(kdata) v=q; q=q-LChild; else v=q; q=q-RChild; if(!q) printf(我要删除的数字不存在。n); return; e=q-data; if(q-LChild&q-RChild) s=q-LChild; v=q; while(s-RChild) v=s; s=s-RChild; q-data=s-data; q=s; if(q-LChild) t=q-LChild; else t=q-RChild; if(q=T) T=t; else if(q=v-LChild) v-LChild=t; else v-RChil
14、d=t; free(q); 删除函数（删除中序后继）： void deleteBST1(BSTree &T,int k,int &e) BSTree q,s,v,t; q=T; v=NULL; while(q) if(k=q-data) break; else if(kdata) v=q; q=q-LChild; else v=q; q=q-RChild; if(!q) printf(你要删除的数字不存在。n); return; e=q-data; if(q-LChild&q-RChild) s=q-RChild; v=q; while(s-LChild) v=s; s=s-LChild; q
15、-data=s-data; q=s; if(q-RChild) t=q-RChild; else t=q-LChild; if(q=T) T=t; else if(q=v-RChild) v-RChild=t; else v-LChild=t; free(q); 中序遍历函数： void outTree(BSTree &T) if(T) outTree(T-LChild); printf(%4d,T-data); outTree(T-RChild); 创建单链表： int createList(LinkList &L) /单链表初始化 L=(LinkList)malloc(sizeof(LNo
16、de); if(!L) return FALSE; L-next=NULL; return TRUE; 单链表插入函数： int insertList(LinkList &L,int e) /向单链表插入元素 LNode *p=L,*q; q=(LNode *)malloc(sizeof(LNode); if(!q) return FALSE; while(p-next!=NULL) p=p-next; q-data=e; q-next=p-next; p-next=q; 叶子结点函数: void leaf(BSTree T,LinkList &L) if(T) if(T-LChild=NUL
17、L&T-RChild=NULL) insertList(L,T-data); leaf(T-LChild,L); leaf(T-RChild,L); 单链表输出函数： void outList(LinkList L) /输出单链表 LNode *p; p=L-next; while(p) printf(%4d,p-data); p=p-next;创建树R函数： BSTree copy(BSTree T) /把树T复制到树R BSTree R; if(T=NULL) return NULL; R=(BSTree)malloc(sizeof(BSTNode); R-data=T-data; R-L
18、Child=copy(T-LChild); R-RChild=copy(T-RChild); return R; 树R左右子树交换函数： void create1(BSTree &R) BSTree q; if(R) create1(R-LChild); create1(R-RChild); q=R-RChild; R-RChild=R-LChild; R-LChild=q; 计算只有一个孩子结点的函数： int jie(BSTree R) int left,right,a; if(!R) return 0; if(R-LChild=NULL&R-RChild!=NULL) return 1;
19、 if(R-LChild!=NULL&R-RChild=NULL) return 1; left=jie(R-LChild); right=jie(R-RChild); a=left+right; return a; 祖先结点函数： void bstree(BSTree R,int e) int vMAX,i=0,j; BSTree q=R; while(q) if(e=q-data) break; else if(edata) vi=q-data; q=q-RChild; else vi=q-data; q=q-LChild; +i; if(!q) return; for(j=0;ji;j+
20、) printf(%4d,vj); 主函数： int main() int e,k,a=0; char c; BSTree T,R; LinkList L; create(T); printf(1、该二叉排序树的中序遍历序列：n); outTree(T); R=copy(T); create1(R); printf(n2、输入你插入的数字：); scanf(%d,&e); insert(T,e); outTree(T); printf(n3、请输入你要删除的数字：); scanf(%d,&k); deleteBST(T,k,e); outTree(T); printf(n4、请输入你要删除的数
21、字：); scanf(%d,&k); deleteBST1(T,k,e); outTree(T); createList(L); printf(n5、是否输出叶子结点构成的单链表 Y or N: ); scanf(%s,&c); if(c=Y) leaf(T,L); outList(L); printf(n6、是否输出二叉排序树的左右子树进行交换后的二叉树 Y or N: ); scanf(%s,&c); if(c=Y) outTree(R); printf(n7、是否输出二叉排序树中只有一个孩子结点的结点个数 Y or N: ); scanf(%s,&c); if(c=Y) printf(%
22、4d,jie(R); printf(n8、请输入要求祖先结点的元素: ); scanf(%d,&e); bstree(R,e); system(pause); return 0; 1.4 程序运行说明与结果1、创建二叉排序树，并以中序遍历输出图（1）：2、 向二叉排序树插入元素58：3、删除二叉排序树元素45（删除中序前驱）：4、删除二叉排序树元素45（删除中序后继）：由于在3中已删除45，故给出提示，输出原树。5、输出叶子结点：由于树T在2中输入58，故多了元素58。6、交换树T的左右子树，输出图（2）：中序遍历输出的图（2）是图（1）的倒序。7、 输出只有一个子树的结点个数：8、查找元素4
23、0的祖先结点，并输出：9、所有的运行结果视图：2. 最短路径问题2.1 问题描述假设网中的顶点用一个整数来表示，并从0开始编号，若网中有n个顶点，则这n个顶点为0，1，n-1。并假设网中不存在顶点到自身的弧。若网采用邻接矩阵存储结构，则直接用一个二维数组来表示。如下图所示的一个有向网：9 0124356136244457337211 图（1）（1）基于图的邻接表存储结构重新设计dijkstra算法及其输出算法，并以图（1）的有向网为测试实例编程实现。（2）dijkstra算法适合求解权值非负的单源最短路径问题，即求一个顶点到其余各个顶点的最短路径。现给定一个有向网G=(V,E)，各条边上的权值
24、均非负，给定G中一个顶点t，要求求出其余各个顶点到顶点t的最短路径长度并构造最短路径，这个问题称为单目标最短路径问题。基于邻接矩阵存储结构设计算法并以图（1）的有向网为测试实例编程实现。 （3）假设dijkstra算法采用邻接矩阵存储结构，利用dijkstra算法求有向网中任意两个顶点间的最短路径长度并构造最短路径。以图（1）的有向网为测试实例编程实现。（4）假设dijkstra算法采用邻接矩阵存储结构，求有向网中顶点i到顶点j的最短路径长度并输出最短路径，只求顶点i到顶点j的最短路径，不能有冗余的循环，i和j从键盘输入，并作为函数参数。（5）dijkstra算法不仅可以求解有向网中权值非负的
25、单源最短路径问题，对于无向网中权值非负的单源最短路径问题，同样适用。设G=(V,E)是一个连通无向网，采用邻接矩阵存储结构，每条边上的权值均非负，从G中任取一个顶点i，考虑顶点i到各个顶点的最短路径长度：d(i,0)，d(i,1)，d(i,n-1)其中d(i,k)（0kn-1）表示顶点i到顶点k的最短路径长度，规定d(i,i)=0。这n个值中最大的那个称为顶点i的最大距离，记为L(i)，在所有顶点中，使L(i)达到最小的顶点称为网G的中心。利用dijkstra算法编程求解给定无向网的中心。例如，下面这个无向网的中心为顶点521354632261.51.8031.52.5图（2） （6）假设将5
26、题中的网看成是一个矿区，它有7个矿，分别在顶点0,1，.,6处，这7个矿每天的矿产量分别是0：3000t，1：2000t，2：7000t，3：1000t，4：5000t，5：1000t，6：4000t，如下图所示。21354632261.51.8031.52.5(3000)(5000)(7000)(1000)(2000)(1000)(4000)图（3）现在要在顶点0,1，.,6中选一个来建选矿厂，如果选矿厂建在了顶点i，那么我们关心的是将各个矿生产的矿石都运到顶点i处的运输量是多少，然后再来确定在哪里建选矿厂最好。一般情况下，我们以运输的tkm数来度量运输量的大小，一吨货物运输一公里就叫1tk
27、m。例如，如果选矿厂建在顶点0处，则总的运输量表示为g(0)，它等于g(0)=30000+20003+70005+10006.3+50009.3+10004.5+40006=122300(tkm) 如果选矿厂建在顶点1处，则总的运输量表示为g(1)，它等于 g(1)=30003+20000+70002+10003.3+50006.3+10001.5+40003=68300(tkm) 显然，选矿厂建在顶点1要比建在顶点0处好，因为建在顶点1处时运输量较小。当然，顶点1是不是最好的还不能确定，应把g(0)，g(1)，g(6)都算出来再比较一下，才可以选出一个最好的建厂地点。 一般情况下，给定无向网
28、G=(V,E)，采用邻接矩阵存储结构，每条边上的权值均非负，G的每个顶点i还有一个“产量”A(i)，对于每个顶点i，令：g(i)=A(0)d(0,i)+ A(1)d(1,i)+A(n-1)d(n-1,i)其中d(k,i)（0kn-1）表示顶点k到顶点i的最短路径长度。g(i)代表了把各个点的物资运到顶点i处所花费的tkm，对于具有n个顶点的无向网G来说，使得g(i)达到最小的那个顶点i就称为该网的中央点，利用dijkstra算法编程求解给定无向网的中央点。 例如，上述图（3）的中央点为顶点2。2.2 设计方案与概要设计1. 最短路径问题应用的存储结构 typedef struct ArcNod
29、e int weight; int adjvex; struct ArcNode *nextarc; ArcNode; typedef struct VNode VertexType data; ArcNode *firstarc; VNode; typedef struct VNode verticesMAX; int vexnum,arcnum; int kind; ALGraph;应用到很多的数组，其g100100用于邻接矩阵存储，d100用于存储路径长度,path100用于存储上一个邻接点,final100用于区分集合S和V，final=1时在集合S,final=0时在集合V。2.方案
30、设计通过邻接表寻找有向图中源点到各点的最短路径，要先创建邻接表。把dijkstra算法设计为利用邻接表查找最短路径的算法，在输入源点后调用方法并进行输出操作。至于单目标问题创建一个与原邻接表相反的逆邻接表，如果创建成功则与源点问题相同。任意两点间的最短路径是把个元素分别作为源点，依次调用方法并进行输出，得到任意两点间的最短路径。固定两点的最短路径是通过邻接矩阵实现，利用dijkstra算法得到所有的最短路径，在输出时只输出固定两点的最短路径。无向网的最短路径方法亦可用dijkstra算法实现，得到以所有元素为源点的最短路径，并获得每个元素的最大距离，然后比较每个元素的最大距离得到最小距离即为网
31、G的中心。在获得每个元素到个顶点距离时同时乘以每个元素的运输量，得到总运输量，进行在比较得到运输量最小的元素即为该网的中央点。3. 设计程序的整体功能结构（整体算法的描述）int LocateVex(ALGraph &G, VertexType v)：查找元素是否存在有向图中；void CreateDG(ALGraph &G,ALGraph &L)：创建邻接表有向图G和其逆邻接表；void GraphOutput(ALGraph &G)：用邻接表输出有向图G;void dijkstra(int s,ALGraph &G) ：邻接表型的dijkstra算法；void out(int s,ALGr
32、aph &G)：邻接表dijkstra算法的输出；void out1(int s,ALGraph &L)：单目标的最短路径输出；void dijkstra(int n,int s,int v)：两定点间的dijkstra算法；void out(int n,int s,int v)：两定点间的路径输出；void dijkstra(int n, int s)：dijkstra算法；void out(int n, int s)：最短路径输出和获得最大距离；void out1(int n, int s)：输出总运输量；int main():主函数； 2.3 详细设计题（1）、（2）和（3）代码如下：#
33、include #include #include #define MAX 20 typedef char VertexTypeMAX; /顶点类型typedef struct ArcNode /有向图,省略的第二个成员 int weight; int adjvex; struct ArcNode *nextarc; ArcNode; typedef struct VNode VertexType data; ArcNode *firstarc; VNode; typedef struct VNode verticesMAX; int vexnum,arcnum; int kind; ALGr
34、aph;查找函数： int LocateVex(ALGraph &G, VertexType v) int i; for (i=0;iG.vexnum;i+) if(strcmp(G.verticesi.data,v)=0) return i; return -1;创建有向图： void CreateDG(ALGraph &G,ALGraph &L) int i,k,j,a,x,y; VertexType v1,v2; ArcNode *p,*s; G.kind=3; printf(请输入有向图的顶点数：n); scanf(%d,&(G.vexnum); printf(请输入有向图的边数:n)
35、; scanf(%d,&(G.arcnum); L.vexnum=G.vexnum; L.arcnum=G.arcnum; for(k=0;kG.vexnum;k+) getchar(); printf(输入第%d个顶点: ,k+1); scanf(%s,G.verticesk.data); strcpy(L.verticesk.data,G.verticesk.data); G.verticesk.firstarc=NULL; L.verticesk.firstarc=NULL; for(k=0;kG.arcnum;k+) getchar(); printf(输入第%d边 和 权值n,k+1); scanf(%s%s%d,v1,v2,&a); i= LocateVex (G,v1); j= LocateVex (G,v2); x= LocateVex (L,v1); y= LocateVex (L,v2); if(i0 |j0|x0|yadjvex=j; s-adjvex=x; p-weight=a; s-wei
