中北大学软件学院数据结构课程设计.docx

1、1 设计目的： 数据结构课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的：n 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；n 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；n 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。2设计内容和要求设计内容：(1) 采用合适的存储结构来创建图，并实现图的遍

2、历；（2）计算图的最小生成树，求联通分量设计要求：（1）先任意创建一个图；（2)图的DFS,BFS的递归和非递归算法的实现（3)最小生成树（两个算法）的实现，求连通分量的实现（4)要求用邻接矩阵、邻接表、十字链表多种结构存储实现3本设计所采用的数据结构：本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。对图的遍历分别采用了广度优先遍历和深度优先遍历。4.1 详细设计思想这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直

3、接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。开始创建图G表存储图If y=yNY显示图的邻接矩阵KRUSCAL算法显示图的邻接表深度优先遍历广度优先遍历最小生成树PRIM输入字母If y=y结束NY图的连通分量输入一个数20134564.3 核心代码#include#include #include using namespace std; #define

4、int_max 10000#define inf 9999 #define max 20/邻接矩阵定义typedef struct ArcCell22 int adj; char *info;ArcCell,AdjMatrix2020;typedef struct char vexs20; AdjMatrix arcs; int vexnum,arcnum; /有向图的当前顶点数和弧数MGraph_L;/int localvex(MGraph_L G,char v)/返回V的位置int i=0; while(G.vexsi!=v) +i; return i;int creatMGraph_L(

5、MGraph_L &G)/创建图用邻接矩阵表示char v1,v2; int i,j,w; cout创建无向图endl请输入图G顶点和弧的个数:(4 6)不包括G.vexnumG.arcnum; for(i=0;i!=G.vexnum;+i) cout输入顶点iG.vexsi; for(i=0;i!=G.vexnum;+i) for(j=0;j!=G.vexnum;+j) G.arcsij.adj=int_max; G.arcsij.info=NULL; for(int k=0;k!=G.arcnum;+k) cout输入一条边依附的顶点和权:(a b 3)不包括v1v2w;/输入一条边依附的

6、两点及权值 i=localvex(G,v1);/确定顶点V1和V2在图中的位置 j=localvex(G,v2); G.arcsij.adj=w; G.arcsji.adj=w; cout图G邻接矩阵创建成功！endl; return G.vexnum;void ljjzprint(MGraph_L G) int i,j; for(i=0;i!=G.vexnum;+i) for(j=0;j!=G.vexnum;+j) coutG.arcsij.adj ; coutadjvex=j; gra.verticesi.firstarc=arc; arc-nextarc=NULL; p=arc; +j;

7、 while(G.arcsij.adj!=int_max&j!=G.vexnum) tem=(arcnode *)malloc(sizeof(arcnode); tem-adjvex=j; gra.verticesi.firstarc=tem; tem-nextarc=arc; arc=tem; +j; -j; else if(G.arcsij.adj!=int_max&j!=G.vexnum) arc=(arcnode *)malloc(sizeof(arcnode); arc-adjvex=j; p-nextarc=arc; arc-nextarc=NULL; p=arc; gra.vex

8、num=G.vexnum; gra.arcnum=G.arcnum; /*for(i=0;i!=gra.vexnum;+i) arcnode *p; couti ; p=gra.verticesi.firstarc; while(p!=NULL) coutadjvex; p=p-nextarc; coutendl; */ cout图G邻接表创建成功！endl; return 1;void adjprint(algraph gra) int i; for(i=0;i!=gra.vexnum;+i) arcnode *p; couti ; p=gra.verticesi.firstarc; whi

9、le(p!=NULL) coutadjvex; p=p-nextarc; coutadjvex;int nextadjvex(algraph gra,vnode v,int w)/返回依附顶点V的相对于W的下一个顶点 arcnode *p; p=v.firstarc; while(p!=NULL&p-adjvex!=w) p=p-nextarc; if(p-adjvex=w&p-nextarc!=NULL) p=p-nextarc; return p-adjvex; if(p-adjvex=w&p-nextarc=NULL) return -10; int initqueue(linkqueu

10、e &q)/初始化队列 q.rear=(queueptr)malloc(sizeof(qnode); q.front=q.rear; if(!q.front) return 0; q.front-next=NULL; return 1;int enqueue(linkqueue &q,int e)/入队 queueptr p; p=(queueptr)malloc(sizeof(qnode); if(!p) return 0; p-data=e; p-next=NULL; q.rear-next=p; q.rear=p; return 1;int dequeue(linkqueue &q,in

11、t &e)/出队 queueptr p; if(q.front=q.rear) return 0; p=q.front-next; e=p-data; q.front-next=p-next; if(q.rear=p) q.rear=q.front; free(p); return 1;int queueempty(linkqueue q)/判断队为空 if(q.front=q.rear) return 1; return 0;void bfstra(algraph gra)/广度优先遍历 int i,e; linkqueue q; for(i=0;i!=gra.vexnum;+i) visi

12、tedi=0; initqueue(q); for(i=0;i!=gra.vexnum;+i) if(!visitedi) visitedi=1; coutgra.verticesi.data; enqueue(q,i); while(!queueempty(q) dequeue(q,e); / cout e=0;we=nextadjvex(gra,gra.verticese,we) if(!visitedwe) visitedwe=1; coutgra.verticeswe.data; enqueue(q,we); int dfs(algraph gra,int i);/声明DFSint d

13、fstra(algraph gra) int i,j; for(i=0;i!=gra.vexnum;+i) visitedi=0; for(j=0;j!=gra.vexnum;+j) if(visitedj=0) dfs(gra,j); return 0;int dfs(algraph gra,int i) visitedi=1; int we1;/ coutivisitediendl; coutgra.verticesi.data;/ cout=0;we=nextadjvex(gra,gra.verticesi,we) / coutwevisitedweendl; we1=we; / cou

14、tnextadjvex(gra,gra.verticesi,we)endl; if(visitedwe=0) / cout dfs(gra,we);/endl; / coutiwe1endl; we=we1; / coutnextadjvex(gra,gra.verticesi,we)endl; return 12;int bfstra_fen(algraph gra)/求连通分量 int i,j; for(i=0;i!=gra.vexnum;+i) visitedi=0; for(j=0;j!=gra.vexnum;+j) if(visitedj=0) dfs(gra,j); coutend

15、l; return 0;typedef struct int adjvex; int lowcost; closedge;/*int minimum(closedge *p);int minispantree(MGraph_L G,char u) int k,j,i; closedge closedge_a20; k=localvex(G,u);/ coutkendl; for(j=0;j!=G.vexnum;+j) if(j!=k) closedge_aj.adjvex=u; closedge_aj.lowcost=G.arcskj.adj; for(i=1;i!=G.vexnum;+i)

16、k=minimum(closedge_a); coutk; coutclosedge_ak.adjvex G.vexskendl; closedge_ak.lowcost=0; for(j=0;j!=G.vexnum;+j) if(G.arcskj.adjp-lowcost) s=p-lowcost; return s;*/int prim(int gmax,int n) /最小生成树PRIM算法 int lowcostmax,prevexmax; /LOWCOST存储当前集合U分别到剩余结点的最短路径 /prevex存储最短路径在U中的结点 int i,j,k,min; for(i=2;i=

17、n;i+) /n个顶点，n-1条边 lowcosti=g1i; /初始化 prevexi=1; /顶点未加入到最小生成树中 lowcost1=0; /标志顶点1加入U集合 for(i=2;i=n;i+) /形成n-1条边的生成树 min=inf; k=0; for(j=2;j=n;j+) /寻找满足边的一个顶点在U,另一个顶点在V的最小边 if(lowcostjmin)&(lowcostj!=0) min=lowcostj; k=j; printf(%d,%d)%dt,prevexk-1,k-1,min); lowcostk=0; /顶点k加入U for(j=2;j=n;j+) /修改由顶点k

18、到其他顶点边的权值 if(gkj0) f=acrvisitedf; return f;void kruscal_arc(MGraph_L G,algraph gra) edg edgs20; int i,j,k=0; for(i=0;i!=G.vexnum;+i) for(j=i;j!=G.vexnum;+j) if(G.arcsij.adj!=10000) edgsk.pre=i; edgsk.bak=j; edgsk.weight=G.arcsij.adj; +k; int x,y,m,n; int buf,edf; for(i=0;i!=gra.arcnum;+i) acrvisited

19、i=0; for(j=0;j!=G.arcnum;+j) m=10000; for(i=0;i!=G.arcnum;+i) if(edgsi.weightm) m=edgsi.weight; x=edgsi.pre; y=edgsi.bak; n=i; / coutxym;/ coutendl; buf=find(acrvisited,x); edf=find(acrvisited,y); / coutbuf edfendl; edgsn.weight=10000; if(buf!=edf) acrvisitedbuf=edf; cout(x,y)m; coutendl; void main(

20、) algraph gra; MGraph_L G; int i,d,g2020; char a=a; d=creatMGraph_L(G); creatadj(gra,G); vnode v; coutendl#注意：若该图为非强连通图(含有多个连通分量)时endl 最小生成树不存在,则显示为非法值。endlendl; cout菜单endlendl; cout0、显示该图的邻接矩阵endl; cout1、显示该图的邻接表endl; cout2、深度优先遍历endl; cout3、广度优先遍历endl; cout4、最小生成树PRIM算法endl; cout5、最小生成树KRUSCAL算法en

21、dl; cout6、该图的连通分量endlendl; int s; char y=y; while(y=y) cout请选择菜单：s; switch(s) case 0: cout邻接矩阵显示如下：endl; ljjzprint(G); break; case 1: cout邻接表显示如下：endl; adjprint(gra); break; case 2: cout广度优先遍历：; bfstra(gra); coutendl; break; case 3: for(i=0;i!=gra.vexnum;+i) visitedi=0; cout深度优先遍历：; dfstra(gra); cou

22、tendl; break; case 4: for(i=0;i!=G.vexnum;+i) for(int j=0;j!=G.vexnum;+j) gi+1j+1=G.arcsij.adj; coutprim:endl; prim(g,d); break; case 5: coutkruscal:endl; kruscal_arc(G,gra); break; case 6: cout连通分量:; bfstra_fen(gra); break; coutendly; if(y=n) break; 5编译运行6.课程设计心得及存在问题课程设计的过程是艰辛的，但是收获却是很大的。这次课程设计我主要

23、是应用以前学习的数据结构与面向对象程序设计知识，综合起来才完成了这个程序，虽然程序很小，但是付出却是艰辛的。首先，综合课程设计让我把以前学习到的知识得到巩固和进一步的提高认识，对已有知识有了更进一步的理解和认识，再次，我在课程设计中碰到了很多的问题，我通过查阅相关书籍，资料，通过自己钻研，以及周围同学的帮助使问题得以逐一解决，在此过程中让我认识到了自己对以前所学知识的不足方面。图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（即其孩子节点）相关，但只能和上一层中一个元素（即其双亲节点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，图的应用极为广泛，特别是近年来的迅速发展，已深入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其他分支中。本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。对图的遍历分别采用了广度优先遍历和深度优先遍历。当然，通过这次课程设计，我也发现了自身的很多不足之处，在以后的学习中，我会不断的完善自我，不断进取，能使自己在编程这方面有一个大的发展。