数据结构课程设计图的建立与遍历

1、数据结构课程设计(论文)图的建立与遍历 院（系）名称电子与信息工程学院 专业班级物联网141 学号 学生姓名 指导教师 起 止 时 间： 2016.1.42016.1.15课程设计（论文）任务及评语院（系）：电子与信息工程学院 教研室：软件工程学 号学生姓名专业班级物联网141 课程设计（论文）题目图的建立与遍历课程设计（论文）任务任务要求：图的建立与遍历实现以下几个功能：（1）创建图的存储结构并保存；（2）对图进行广度优先搜索（3）对图进行深度优先搜索。（4）输出遍历结果。技术要求：1、数据的逻辑结构采用图状结构，物理结构采用链式存储结构（邻接表）。2、软件能正常运行，界面清晰，操作要简单。

2、3、系统要有主界面设计，调用各个功能项。4、采用viscal c+编写代码，可读性强。5、数据类型用typedef 定义。指导教师评语及成绩平时成绩： 答辩成绩： 论文成绩： 总成绩： 指导教师签字： 年 月 日注：平时成绩占20%，答辩成绩占40%，论文成绩占40%。摘 要随着信息时代的快速发展，大数据大流量对数据的存储有了更为苛刻的要求，数据之间的关系越来越复杂。图形结构的存储方式也就应运而生，因为图节点之间的关系可能是任意的，图中任意2个元素之间都可能相关。由此，图的应用更为广泛，特别是今年来的迅速发展，已渗透到诸如语言学、逻辑学、物理学化学、电讯工程、计算机科学以及数学的其他分支中。在

3、此课程设计中，程序设计语言采用visual c+window 7环境。在程序设计中主要解决的是给出一个图如何用多中方法完成图的遍历的问题，也包括如何创建一个图，深度优先遍历和广度优先遍历一个图。程序最终通过调试运行，初步实现了设计目标。关键词：数据结构；有向图；无向图；邻接表目 录第1章 绪论11.1系统的开发背景11.2开发工具及语言1第2章 概要设计22.1模块划分22.2 各模块的设计22.3 数据结构的选择3第3章 系统详细设计与编码53.1完整的源程序53.2程序的输入和输出113.3调试程序中遇到的问题及解决方案12第4章 思考题解析134.1 思考题的选择134.2类c算法134

4、.3程序分析14第5章 总结15参考文献16第1章 绪论1.1系统的开发背景图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前去和一个和直接后继；在树形结构中，数据元素之间没有明显的层次关系，并且每一层的数据元素可能和下一层中的多个元素相关，但是你只能和上一层的一个元素相关；而在图形结构中，节点之间的关系可能是任意的，图中任意2个元素之间都可能相关。由此，图的应用更为广泛，特别是今年来的迅速发展，已渗透到诸如语言学、逻辑学、物理学、化学、电讯工程、计算机科学以及数学的其他分支中。1.2开发工具及语言本系统使用viscal c+语言开发，主界

5、面清晰显示所有功能项，使用简单。各个功能项均定义一个函数来实现，在主函数中调用各个子函数实现不同的功能。第2章 概要设计2.1模块划分题目应实现的具体功能：按照自己的需要从有向向图不带权图、有向带权图、无向不带权图和有向带权图中选择建立一种图的结构，输入具体的顶点数目、顶点值、边的数目和权值，选择要开始遍历的顶点，并按照深度优先遍历和广度优先遍历输出该图。系统的功能模块图如图2.1所示。图2.1 系统功能模块图2.2 各模块的设计 题目应该实现的具体功能： a.有向不带权图的建立，从任意节点开始广度和深度遍历 b.有向不带权图的建立，从任意节点开始广度和深度遍历 c.有向不带权图的建立，从任意

6、节点开始广度和深度遍历 d.有向不带权图的建立，从任意节点开始广度和深度遍历 开始 出队访问访问标志数组初始化寻找第一个邻接点 第一个定点入队 是否访问过队列是否为空 否 是 否 定点入队 结束 寻找下一个邻接点 是图2.2 广度遍历模块程序流程图2.3 数据结构的选择系统数据的逻辑结构采用图状结构，物理结构采用邻接表的存储结构。存储结构定义如下：typedef struct arcnodeint adjvex; struct arcnode *nextarc; arctextype info; arcnode;typedef struct vnodevertextype data; arcn

7、ode *firstarc; vnode,adjlistmac_vertex_num;typedef structadjlist vertices;int vexnum,arcnum; int kind; graph;第3章 系统详细设计与编码3.1完整的源程序#include stdafx.h#include #include #define mac_vertex_num 10#define null 0#define true 1#define false 0#define overflow -2#define ok 1#define error 0#define arctextype i

8、nttypedef struct arcnodeint adjvex; struct arcnode *nextarc; arctextype info; arcnode;typedef char vertextype5;typedef struct vnodevertextype data; arcnode *firstarc; vnode,adjlistmac_vertex_num; typedef structadjlist vertices; int vexnum,arcnum; int kind; graph;int visitedmac_vertex_num; int greatv

9、ex(graph *g); int print(graph g); int adjfound(graph g,vertextype c); int dfs(graph g,int v); int bfstraverse(graph g,vertextype vex); int dfstraverse(graph g,vertextype vex); int firstadjvex(graph g,int v); int nextadjvex(graph g,int v,int w); int greatvex(graph *g) int i=0;printf(请输入顶点数：);scanf(%d

10、,&g-vexnum);while(g-vexnummac_vertex_num)printf(定点数最大为10！n);printf(请重新输入：);scanf(%d,&g-vexnum);printf(请输入边数：);scanf(%d,&g-arcnum);printf(输入各顶点的值：);for(i=0;ivexnum;i+) scanf(%s,g-verticesi.data);g-verticesi.firstarc=null;return ok;int greatudg(graph *g) int i=0,start,end;vertextype b,e;arcnode *d1,*d

11、2;for(i=0;iarcnum;i+)printf(请输入第%d个相连的两个顶点，格式：顶点1 顶点2（中间用空格隔开）：,i+1);scanf(%s%s,b,e);start=adjfound(*g,b); end=adjfound(*g,e); d1=(arcnode *)malloc(sizeof(arcnode); d1-adjvex=end;d1-nextarc=g-verticesstart.firstarc;g-verticesstart.firstarc=d1;d2=(arcnode *)malloc(sizeof(arcnode); d2-adjvex=start;d2-

12、nextarc=g-verticesend.firstarc;g-verticesend.firstarc=d2;return ok;int greatdg(graph *g) int i=0,start,end;vertextype b,e;arcnode *d1;for(i=0;iarcnum;i+)printf(请输入第%d个相连的两个顶点，格式：顶点1顶点2：（中间用逗号隔开）,i+1);scanf(%s%s,b,e);start=adjfound(*g,b);end=adjfound(*g,e);d1=(arcnode *)malloc(sizeof(arcnode);d1-adjv

13、ex=end;d1-nextarc=g-verticesstart.firstarc;g-verticesstart.firstarc=d1;return ok;int greatudn(graph *g) int i=0,start,end;vertextype b,e;arcnode *d1,*d2;for(i=0;iarcnum;i+)d1=(arcnode *)malloc(sizeof(arcnode); printf(请输入第%d个相连的两个顶点，格式：顶点1 权值 顶点2（中间用空格隔开）：,i+1);scanf(%s%d%s,b,&(d1-info),e);start=adjf

14、ound(*g,b);end=adjfound(*g,e);d1-adjvex=end;d1-nextarc=g-verticesstart.firstarc;g-verticesstart.firstarc=d1;d2=(arcnode *)malloc(sizeof(arcnode);d2-adjvex=start;d2-nextarc=g-verticesend.firstarc;g-verticesend.firstarc=d2;return ok;int greatdn(graph *g) int i=0,start,end;vertextype b,e;arcnode *d1;fo

15、r(i=0;iarcnum;i+)d1=(arcnode *)malloc(sizeof(arcnode); printf(请输入第%d个相连的两个顶点，格式：顶点1 权值 顶点2（中间用逗号隔开）：,i+1);scanf(%s%d%s,b,&(d1-info),e);start=adjfound(*g,b);end=adjfound(*g,e);d1-adjvex=end;d1-nextarc=g-verticesstart.firstarc;g-verticesstart.firstarc=d1;return ok;int print(graph g) int i=0;while(g.ve

16、rticesi.data!=null&ig.vexnum)printf(%s,g.verticesi.data);i+;return ok;int adjfound(graph g,vertextype c) int i=0;while(strcmp(g.verticesi.data,c)!=0&ig.vexnum)i+;if(i,g.verticesv.data);visitedv=true; if(g.verticesv.firstarc) for(w=firstadjvex(g,v);w=0;w=nextadjvex(g,v,w)if(!visitedw)dfs(g,w);return

17、ok;int dfstraverse(graph g,vertextype vex) /深度遍历int v,i;i=adjfound(g,vex); for(v=0;vadjvex;return -1;int nextadjvex(graph g,int v,int w) /广度遍历调用的查找下一条边arcnode *p; p=(arcnode *)malloc(sizeof(arcnode);p=g.verticesv.firstarc;while(p-adjvex!=w)p=p-nextarc;if(p-nextarc)return (p-nextarc)-adjvex;elseretur

18、n -1;int bfstraverse(graph g,vertextype vex) 广度遍历int a=0,b=0; int *queue;int v,i,w;i=adjfound(g,vex); queue=(int *)malloc(g.vexnum*2)*sizeof(int);queueb=i,b+; for(v=0;v,g.verticesqueuea.data);visitedqueuea=true; for(w=firstadjvex(g,queuea);w=0;w=nextadjvex(g,queuea,w)if(w!=-1&!visitedw) queueb=w,b+;

19、a+; return ok;void main()graph *g=null;vertextype n;int again=1;g=(graph *)malloc(sizeof(graph);while(1)printf( 图的建立与遍历 n n); printf( 1:有向不带权图n 2:有向带权图n 3:无向不带权图n 4:无向带权图n 请选择要建立的图的类型:); scanf(%d,&(g-kind);switch(g-kind) case 1:greatvex(g);greatdg(g);break;case 2:greatvex(g);greatdn(g);break; case 3

20、:greatvex(g);greatudg(g);break; case 4:greatvex(g);greatudn(g);break; default:printf(输入错误，请重新输入: n); printf(该图的所有顶点：);print(*g);printf(n请输入从哪个顶点开始遍历：);while(again!=0)scanf(%s,n);printf(深度优先遍历为：);dfstraverse(*g,n);printf(n广度优先遍历为：);bfstraverse(*g,n);printf(n从其他顶点开始遍历请输入顶点值，退出请输入0：);scanf(%d,&again);f

21、ree(g); 3.2程序的输入和输出程序运行主界面：图3.1 主界面图3.2 图的建立 图3.3广度遍历和深度遍历3.3调试程序中遇到的问题及解决方案 问题：图的邻接表广度遍历是只能显示第一个邻接点。 解决方案：后来经过大量排查发现在节点入队是吧v写成v0了，虽然都是很小的错误，但是充分暴露了自己的粗心大意，在以后的试验中一低昂要改正。第4章 思考题解析4.1 思考题的选择所选择的思考题：数组a中有n个值，根据其编写一个算法，构造一棵哈夫曼树，并求出其带权路径长度。4.2类c算法struct btreenode *createhuffman(elemtype a,int n)int i,j;

22、struct btreenode *b,*q;b=malloc(n*sizeof(struct btreenode);for(i=0;idata=ai;bi-left=bi-right=null;for(i=1;in;i+) int k1=-1;k2; /k1for(j=0;jn;j+) if(bj!=null&k1=-1)k1=j;continue;if(bj!=null)k2=j;break;for(j=k2;jdatadata)k2=k1;k1=j;else if(bj-datadata)k2=j;q=malloc(sizeof(struct btreenode); q-left=bk1

23、;q-right=bk2;free(q);elemtype weightpathlength(struct btreenode *fbt,int len) if(fbt=null) return 0;elseif(fbt-left=null&fbt=null) return fbt-data*len;else return weightpathlength(fbt-left,len+1)+weighpathlength(fbt-right,len+1);4.3程序分析elemtype weightpathlength函数是求哈夫曼树的带权路径长度的，fbt是对哈夫曼树逐个访问的指针，len是当前结点到根结点的路径长度，每次调用elemtype weightpathlength函数，len加1。由于递归调用，当fbt为空树时，返回，从而求出带权路径长度。第5章 总结转眼，为期两周的数据结构课程设