数据结构课程设计图的建立与输出 (luoshifu)

《数据结构课程设计图的建立与输出 (luoshifu)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、《数据结构》课程设计题目：图的建立与输出院系：电子与信息工程学院学生姓名：罗世福学号：4专业：电子信息工程班级：09级（1）班指导教师：余先伦职称教授完成时间：2011-6-23-7-目录一课程设计目的……………………………………………3二课程设计内容……………………………………………3三算法和思想………………………………………………3四源代码……………………………………………………4五课程设计心得……………………………………………6六参考文献…………………………………………………7-7-图的建立与输出摘要：运用数组类型来表示元素之间的

2、关系，还采用多重链表示图，运用邻接矩阵来输出图。 关键字：邻接矩阵，多重链表，时间复杂度，数据域，指针域，邻接表。一、程序设计目的巩固和加深课堂教学内容，提高学生实际工作能力，使学生熟练掌握数据结构课程中所学的理论知识，通过综合运用数据结构的基本知识来解决实际问题加强学生分析和解决问题的能力。建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。二、课程设计内容建立图的存储结构，并能输出图的顶点和边的信息，并存储到相应的存储结构中

3、，同时并能输出图的邻接矩阵，（图可以是有向图，无向图，有向网，无向网，）图的建立比较复杂，任意两个顶点之间都有可能存在联系，因此无法以数据元素在存储区中的物理位置来表示元素之间的关系，因此图没有顺序影像的存储结构，但可以借助数组的数据类型来表示元素之间的关系。三、算法和思想首先是图的存储结构，用多重链表表示图是自然的事，它是一种最简单的链式影像结构，以一个由一个数据域和多个指针域组成的结点表示图的一个顶点，其中数据域存储该结点的信息，指针域存储指向其临界点的指针。数组表示法，用两个数组分别别存储顶点的信息和数据元素之间的关系的信息。邻接

4、表，在邻接表中对图中的每一个顶点建立一个单链表，第I个单链表中的结点表示依附于顶点VI的边。每个结点由三个域组成，其中邻接点域指示与顶点VI邻接的点在图中的位置，链域指示下一条边或弧的结点，数据域存储和边或弧相关的信息。每个链表上依附一个表结点。在表头结点中除了设有链域指针链表中第一个结点之外，还设有存储顶点VI的名或其他信息的数据域。-7-图的遍历，图中任一都有可能和其余顶点相邻接，所以在访问了某个定点之后，可能沿着某条路径搜索之后，又回到该顶点上。深度优先搜索，假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可以从图中某个顶点V

5、出发，访问此顶点，然后依次从V的未被访问的邻接点出发深度优先遍历图，直到图中所有和V有路径相通的顶点都被访问到，若此时图中还有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。广度优先搜索，从图中某个顶点V出发在访问了V之后依次访问V的各个未曾访问过的邻接点，然后分别从这些邻接点出发一次访问他们的邻接点，并使先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此图中还有未被访问到的结点，则另选图中一个未被访问的顶点作为起始点，重复上述过

6、程，直至图中所有顶点都被访问倒为止。四、源代码#include"stdio.h"#include"stdlib.h"#defineMAX999//定义无穷#defineMaxVertexNum100//定义最大顶点数typedefstruct{charvexs[MaxVertexNum];//顶点表intedges[MaxVertexNum][MaxVertexNum];//邻接矩阵，可看作边表intn,e;//图中的顶点数n和边数e}MGraph;//用邻接矩阵表示的图的类型//=========建立邻接矩阵=======typede

7、fenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];voidCreatMGraph(MGraph*G){inti,j,k,w;chara;printf("InputVertexNum(n)andEdgesNum(e):");scanf("%d,%d",&G->n,&G->e);//输入顶点数和边数scanf("%c",&a);printf("InputVertexstring:");for(i=0;in;i++){scanf("%c",&a);G->vexs[i]=a;//

8、读入顶点信息，建立顶点表-7-}for(i=0;in;i++)for(j=0;jn;j++)G->edges[i][j]=MAX;//初始化邻接矩阵printf("Inputedges,Cr