邻接矩阵的表示及其应用--.doc

摘 要
这个设计里面我选择图为主要研究对象，对其一些基本运算和相关功能的实现作简单的描述。在这里，我围绕图为中心，主要涉及以下内容：第一部分，用其中一种存储方法——邻接矩阵法创建图(或网)，具体分为（1）：用邻接矩阵创建一个无向网；（2）：用邻接矩阵创建一个有向图；（由于时间原因，这里仅涉及邻接矩阵法，并且只建立一个无向网和一个有向图）第二部分是通过两种方法对图和网遍历以验证图和网建立的正确性，主要有：（3）：对建立的连通无向网进行深度遍历；（4）：对建立的连通无向网进行广度遍历；（5）：对建立的非连通有向图进行深度遍历；（6）：对建立的非连通有向图进行广度遍历。以上各功能的实现过程中用到了递归思想、图的数据结构和逻辑结构、表单的实现、程序的模块化思想、函数间的调用。
关键字：图、邻接矩阵、无向网、有向图、深度遍历、广度遍历。
Abstract
The photo shows the design which I have chosen the main object of study, some of its basic operations and related functions to make a simple description of the implementation. Here, I focus on photo center, mainly related to the following: the first part, using one of the storage method - create a map adjacency matrix (or network), specifically divided into (1): The adjacency matrix of an undirected network to create ; (2): with the adjacency matrix to create a directed graph; (For reasons of timing here relates only to the adjacency matrix method, and only the establishment of a network and an undirected graph) The second part is on the charts and through the two methods network traversal to verify the correctness of diagrams and networks have been established, mainly: (3): the establishment of an undirected network connectivity for in-depth traversal; (4): the establishment of the connectivity of an undirected network to traverse the breadth; (5): right the establishment of a non-connected directed graph traversal depth; (6): the establishment of a non-connected directed graph traversal breadth. The realization of the above functions used in the process of recursive thinking, graph data structure and logical structure, forms of implementation, the program's modular idea, the function calls between the.
Keywords: graph, adjacency matrix of undirected network, a directed graph, depth traversal, breadth traversal.
目 录
第一章 课题介绍 3
1.1题目描述 3
1.2题目要求 3
1.3输入功能 3
1.4输出功能 3
1.5扩展功能 4
第二章设计分析 4
2.1课题设计 4
2.2算法描述 4
2.2.1用邻接矩阵建立无向网 4
2.2.2用邻接矩阵创建一个有向图 6
2.2.3对建立的连通无向网进行深度遍历 7
2.2.4对建立的连通有向图进行广度遍历 7
2.2.5对建立的非连通无向网进行深度遍历 8
2.2.6对建立的非连通有向图进行广度遍历 9
2．3结果显示 10
2.3.1 建立一个无向网 10
2.3.2 建立无向网 11
2.3.3 无向网深度遍历 11
2.3.4 无向网的广度遍历 12
2.3.5 建立一个有向图 12
2.3.5 对非连通有向图深度遍历 13
2.3.6 对非连通有向图广度遍历 13
2.3.7 建立非连通无向网 14
2.3.8 对非连通无向网深度遍历 14
2.3.9 对非连通无向网广度遍历 15
第三章 程序设计的总结 15
3.1 模块化程序设计思想 15
3.2 注释的关键性 16
3.3设计思想 16
附录 17

第一章 课题介绍
1.1题目描述
设计程序使有功能：
（1）：用邻接矩阵创建一个无向网；
（2）：用邻接矩阵创建一个有向图；
（3）：对建立的连通无向网进行深度遍历；
（4）：对建立的连通有向图进行广度遍历；
（5）：对建立的非连通无向网进行深度遍历；
（6）：对建立的非连通有向图进行广度
（7）：能很好的实现函数与函数间的调用
1.2题目要求
1、按照分析、设计、编码、调试和测试的软件开发过程完成这个程序。
2、为各项操作功能设计一个菜单程序后，先显示这个菜单，然后用户可以通过菜单选择想要进行的操作项目。
3、自我设计及参看相关算法对图的相关功能进行实现。
1.3输入功能
程序测试成功后，在运行时会在屏幕上显示一个菜单提示，用户可以从键面输入相应信息进行操作。
1.4输出功能
1、程序运行后在屏幕上显示一个菜单
2、要求用户输入数据时给定清晰明确的提示信息，包括输入数据内容、格式等。
1.5扩展功能
图的功能远不止此设计中所涉及的，还有许多其他的功能如拓扑排序，最小生成树，最短路径，关键路径等问题。而且图的一些功能的实现也有多种途径，如可以用到栈和队列，邻接表等方法。此相关知识在今后的程序中会进行相应的补充和描述。
第二章设计分析
2.1课题设计
对象是图的设计菜单，分为以下几个板块：
（）setnull………………队列置空
（）enqueue………………元素入队
（）dequeue………………元素出队
（）creatgraph………………创建无向网
（）creatgraph………………创建有向图
（）traver……………………对非连通图深度遍历
（）traver1……………………对非连通图广度遍历
（）DFS…………………………深度遍历
（）BFS……………………………广度遍历

2.2算法描述
上述每个模板均用子函数实现，出主函数外，其余函数原型如下：
2.2.1用邻接矩阵建立无向网
算法思想：根据邻接矩阵是表示顶点之间相邻的矩阵。这里借助矩阵（二维数组）表示两顶点间相邻关系外，还要建立一个顺序表用来存储顶点信息。由结构体中知，顶点信息室由0到n-1的编号并对两个顶点是相邻关系的赋权值，由于建立的是无向网，所以可以用压缩存储的方法存储信息。
下面给出用邻接矩阵建立无向网的算法如下：

creatgraph(graph *ga)
{
int i,j,k;
float w;
printf("请输入顶点的个数:");
scanf("%d",&ga->n);
printf("请输入边的个数:");
scanf("%d",&ga->e);
printf("请输入各顶点:");
getchar();
for(i=0;i<ga->n;i++)
ga->vexs[i]=getchar();
for(i=0;i<ga->n;i++)
for(j=0;j<ga->n;j++)
ga->arcs[i][j]=0;
printf("请输入边和权值:\n");
for(k=0;k<ga->e;k++)
{
scanf("%d%d%f",&i,&j,&w);
ga->arcs[i][j]=w;
ga->arcs[j][i]=w;
}
for(i=0;i<ga->n;i++)
{
printf("\nv%c ",ga->vexs[i]);
for(j=0;j<ga->n;j++)
printf(" %.1f",ga->arcs[i][j]);
}
}
2.2.2用邻接矩阵创建一个有向图
算法思想：对于有向图的建立的算法，首先也要用邻接矩阵表示顶点间的相邻关系，这里用数字1表示两顶点间有边，同时也要用一个顺序表存储顶点信息。只是在顶点信息由0到n-1编号，对于有联系的两顶点赋值为1.
下面给出建立一个有向图的算法如下：
creatgraph1(graph *ga)
{
int i,j,k;
printf("请输入顶点的个数:");
scanf("%d",&ga->n);
printf("请输入边的个数:");
scanf("%d",&ga->e);
printf("请输入各顶点:");
getchar();
for(i=0;i<ga->n;i++)
ga->vexs[i]=getchar();
for(i=0;i<ga->n;i++)
for(j=0;j<ga->n;j++)
{
ga->arcs[i][j]=0;
}
for(k=0;k<ga->e;k++)
{
scanf("%d%d",&i,&j);
ga->arcs[i][j]=1;
}
for(i=0;i<ga->n;i++)
{
printf("\nv%c ",ga->vexs[i]);
for(j=0;j<ga->n;j++)
printf(" %.1f",ga->arcs[i][j]);
}
}
2.2.3对建立的连通无向网进行深度遍历
算法思想：根据深度遍历的特点是尽可能先对纵深方向进行搜索，所以可以选定某一点（对此点用visited做标记，表示已访问过），然后寻找一个与它相邻而且未被访问过的顶点。之后再以这点进行访问，运用递归的思想将所有的顶点访问完，此时程序结束。
下面给出对建立的连通无向网进行深度遍历算法如下：
int visited[200]={0};
void DFS(graph *ga,int i)
{

int j;
printf("v%c,",ga->vexs[i]);
visited[i]=1;
for(j=0;j<ga->n;j++)
if((ga->arcs[i][j]!=0)&&(!visited[j]))
DFS(ga,j);
}
2.2.4对建立的连通有向图进行广度遍历
算法思想：根据广度遍历的特点是尽可能先对横向进行搜索，所以其中思想为选定为选定某顶点并做标记，然后一次访问与此顶点相邻又未被访问过的顶点，再根据访问的次序依次对未被访问的顶点运用递归思想进行广度遍历，知道所有顶点被访问完为止。
下面给出对建立的连通无向网进行广度遍历的算法如下：
int visited1[200]={0};
void BFS(graph *ga,int k)
{

int i,j;sequeue Q;
setnull(&Q);
printf("%c\n",ga->vexs[k]);
visited1[k]=1;
enqueue(&Q,k);
while(!empty(&Q))
{
i=dequeue(&Q);
for(j=0;j<ga->n;j++)
if((ga->arcs[i][j]!=0)&&(!visited1[j]))
{
printf("%c\n",ga->vexs[j]);
visited1[j]=1;
}
}
}
2.2.5对建立的非连通无向网进行深度遍历
算法思想：对于一个连通图就不能用DFS进行遍历，这里需要用traver算法，它是对每个连通分量中都选定一个顶点作为出发点进行搜索，其中多次调用DFS（）算法，直到每个连通分量中的顶点都被访问完。
下面给出对建立的非连通有向图进行深度遍历的算法如下：
traver(graph *ga)
{
int i;
int count=1;
for(i=0;i<ga->n;i++)
visited[i]=0;
for(i=0;i<ga->n;i++)
{

if(!visited[i])
{
printf("第%d个连通分量为:",count);
if(!visited[i])
DFS(ga,i);
count++;
printf("comp end\n");
}
}
}
2.2.6对建立的非连通有向图进行广度遍历
算法思想：对于非连通图的广度遍历，思想也是选定每个连通分量中的一个顶点，然后多次调用BFS（）算法，直到所有连通分量中的所有顶点斗都被访问到了，可算法结束。
下面给出对建立的非连通有向图进行广度遍历的算法如下：
traver1(graph *ga)
{
int i;
int count=1;
for(i=0;i<ga->n;i++)
visited1[i]=0;
for(i=0;i<ga->n;i++)
{
if(!visited1[i])
{
printf("第%d个连通分量为:",count);
if(!visited1[i])
BFS(ga,i);
count++;
printf("comp end\n");
}
}
}
2．3结果显示
2.3.1 菜单界面

2.3.2 建立无向网

2.3.3 无向网深度遍历

2.3.4 无向网的广度遍历

2.3.5 建立一个有向图

2.3.5 对非连通有向图深度遍历

2.3.6 对非连通有向图广度遍历

2.3.7 建立非连通无向网

2.3.8 对非连通无向网深度遍历

2.3.9 对非连通无向网广度遍历

第三章 程序设计的总结
3.1 模块化程序设计思想
一．采用模块化程序设计思想的原因：
在平时上机课中的题目往往只有一个，或是两三个功能，只要几十行代码甚至只要几行就能完成了，我们不需要考虑太多就可以让程序实现出来了。但是此程序设计要完成这么多的功能，所以想用平时的设计在一个主程序里完成，是很困难的，即使完成了程序也会混乱，出现错误时也不容易修改，所以采用模块化程序设计思想。
二．采用模块化程序设计需要：
采用模块化程序设计需要把程序分成几个模块，每个模块完成什么样的功能我们必须事先想好并画出模块功能表，有自己的想法。这样不至于在之后的编程时混乱。所以采用模块化的子程序能帮助我理清编程思路。
最后，将各子程序整合在一起就可以了。
3.2 注释的关键性
一．便于读程序：
我们都知道，对于代码偏长的程序，即使是自己编的，但在过了一段时间后，再回来看程序时，也是需要花一些时间去弄懂的。、倘若这样的程序中没有注释，等到我们看时，可想而知，会浪费时间的。而且一个大型程序不可能一次性完成，我们还需要对它进行完善，所以程序中必须配上一定量的文字注释。
二．便于合作编程
在大型程序编程中，一个程序不可能由一个人来完成，都是要几个人，甚至几十个分工合作的，所以每个人完成的模块，其他人需要读懂，这就要求我们在编程时要让程序可读性强，所以也要求我们对程序进行注释。
综上所述，可以知道注释在程序中所起的作用了。
3.3设计思想
对于此次课程设计，做的东西虽然不多，涉及的知识也不广，但是都是自己做出来的。说实话，自己完成的比较仓促，原本想精心选择一个比较好的题目进行设计，最好是实用性较强的东西，可是应该是时间的原因吧！不过更多的还应该是自己不愿意去挖掘吧，所以这次的课程设计自己还是很不满意的。但是感想还是蛮多的。具体如下：
(1) 设计的自我评价.通过这个自己认为比较大的程序的实现，我明白了对于一个程序应该从局部和整体去看它，并且协调好局部与整体的关系。因为在局部里面体现了你的仔细和认真的态度，好比在一个子程序里面，即便是少了一个分号或是一个大括号没有配对，都是不能使程序正常运行的。当你把局部的细节问题处理好后，还要从大局出发，看是否能在一个main（）函数里面将各个子函数的功能都实现出来，好比对于一个全局变量的考虑以及某变量在子函数里面是否有定义冲突等等问题。所以一个程序坐下来之后，最大的感受就是调试程序时要从小处着手，大处着眼。
(2) 课题的选择。为了这次的课程设计，我翻看了不少数据结构书，尤其是关于课程设计的内容，当然，也上网搜集了一些，为的是选择一个很好的课题，可是最后结合自己的实际，综合考虑了一番，最终选定研究对象为图。愿因是图虽然看上去能做的内容不是很多，但你真做起来，也是很复杂的，好比对于网就有有向网和无向网，图也有有向图和无向图等等做这些程序可以锻炼自己从大局上把握程序的能力。
(3) 内容的选定。此次课程设计研究对象很明确，很有针对性。特别地紧密结合了老师上课的内容，并且在自行查找搜集资料的过程中，做了比较细致的安排，就图的相关操作都一一进行了实现。虽然方法比较单一，思想比较简单，但还是能够很好的将各功能衔接在一起。尤其是设计中菜单的子程序的设置，相关语句的提示以及界面设置，自己觉得还好。
（4）设计的调试与完善。程序的最终完成，还是要花一定时间的。在编程过程中，我遇到的最大问题就是各子程序间的衔接问题，尤其是在处理创建完一个图后，再次对其进行其他操作时，起初是根本进行不了，后来思考后，知道是返回值的问题，所以进行再次甚至多次调试与修改后，程序基本成功。但后来，仔细一想，如果是一个不懂的人使用了该程序，可能操作不好，我于是就详尽地修改了注释，还特别地设置了提示信息。所以再次调试后，最终完成。

总之，通过这次课程设计，真正地让自己锻炼实际调试程序的能力，在不断地失败中学到了许多的东西，当然，以后还要好好学，提高自己的编程能力。
附录
一、参考文献：[1] 唐策善 李龙彭 黄刘生 编著 《数据结构》——（用C语言描述） 高等教育出版社 1995年4月第一版
[2] 朱站立 张选平 编著 《数据结构》——（学习指导 典型题解 新版）西安交通大学出版社
二、源程序代码如下：
#include <stdio.h>
#define maxsize 1024
typedef int datatype;
typedef char vextype; /*顶点的数据类型*/
typedef float adjtype; /*权值类型*/
typedef struct
{
vextype vexs[200];
adjtype arcs[200][200];
int n,e; /*n是顶点数e为边数*/
}graph;
typedef struct
{
datatype data[maxsize];
int front,rear;
}sequeue; /*顺序队列的类型*/
setnull(sequeue *sq) /*置队列sq为空队*/
{
sq->front=sq->rear=maxsize-1;
}
enqueue(sequeue *sq,datatype x) /*将新元素x插入队列*sq的队尾*/
{
if((sq->rear+1)%maxsize==sq->front) /*队满上溢*/
{
printf("This queue is full");
return 0;
}
else
{
sq->rear=(sq->rear+1)%maxsize;
sq->data[sq->rear]=x;
}
}
int empty(sequeue *sq) /*判断*sq是否为空*/
{
if(sq->front==sq->rear)
return 1;
else
return 0;
}
datatype dequeue(sequeue *sq) /*删除队列*sq的头元素，并返回该元素*/
{
if(empty(sq))
{
printf("queue is empty"); /*队空下溢*/
return 0;
}
else
sq->front=(sq->front+1)%maxsize;
return sq->data[sq->front];
}
main()
{
graph b;
int a,i,k;

while(1)
{
printf("\n\n\t\t\t欢迎进入我的程序设计:\n ");
printf("\t\t\**************************************\n\n\n ");
printf("\t\t1:用邻接矩阵创建一个无向网:\n ");
printf("\t\t2:用邻接矩阵创建一个y向网:\n ");
printf("\t\t3:采用深度优先搜素对图进行遍历:\n");
printf("\t\t4:采用广度优先搜素对图进行遍历\n");
printf("\t\t5:采用深度优先搜素对非连通图进行遍历:\n");
printf("\t\t6:采用广度优先搜素对非连通图进行遍历\n");
printf("请输入a的值:");
scanf("%d",&a);
switch(a)
{
case 1:creatgraph(&b);break;
case 2:creatgraph1(&b);break;
case 3:printf("请输入i的值:");
scanf("%d",&i);
printf("\n深度优先遍历序列:");
DFS(&b,i);
if(c!=b.n)
printf("请选择非连通图遍历");break;
case 4:
printf("请输入k的值:");
scanf("%d",&k);
printf("\n广度优先遍历序列:");
BFS(&b,k);
if(c1!=b.n)
printf("请选择非连通图遍历");break;
case 5:traver(&b);break;
case 6:traver1(&b); break;
default:exit(0);
}
}
}

21