图的邻接矩阵存储结构建立.doc

课程名称: 《数据结构》课程设计
课程设计题目:图的邻接矩阵存储 结构建立
姓名:XXX
院系:计算机学院
专业:计算机科学技术
年级:11级
学号:XXXXXXXX
指导教师:XXX
2013年9月28日

目录

1 课程设计的目的………………………………………………………3

2需求分析………………………………………………………………3

3 课程设计报告内容 …………………………………………………3
3.1 概要设计………………………………………………………3
3.2 详细设计………………………………………………………4
3.3 调试分析………………………………………………………5
3.4 用户手册………………………………………………………5
3.5 程序清单………………………………………………………5
3.6 测试结果………………………………………………………10

4 小结…………………………………………………………………12

5 参考文献……………………………………………………………12

1.课程设计的目的
(1) 熟练使用 C 语言编写程序，解决实际问题;
(2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;
(3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;
(4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力;
2.需求分析
 问题描述:建立图的邻接矩阵存储结构(图的类型可以是有向图或有向网、无向图或无向网，学生可以任选一种类型)，能够输入图的顶点和边的信息，并存储到相应存储结构中，而后给出图的 DFS,BFS次序。
要求：
①先任意创建一个图；
②图的DFS,BFS的递归和非递归算法的实现。
3.课程设计报告内容
3.1概要设计
1.函数
①主函数：main( )
②创建无向图：CreateGraph( )
③深度优先遍历图：DFS( )
④广度优先遍历图：BFS( )
3.2详细设计
1.使用邻接矩阵作为图的存储结构，程序中主要用到的抽象数据类型：
typedef struct
{
char vexs[MAX]; //顶点向量
int arcs[MAX][MAX]; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和弧数
}Graph;
2.程序流程图：

主函数main( )
创建无向图
数据输入
功能选择
深度优先遍历
退出程序
广度优先遍历
数据输出
程序结束
数据输出

3.3调试分析
程序的设计严格遵循结构化的程序设计思想，由简单到复杂，注意规范。在此次程序运行中，出现了很多的错误，开始的时候，不能很好的创建一个图，后来改进了算法，使得程序能够正确的运行。
3.4用户手册
①进入程序后，您会看到以下提示：
“无向图的创建及DFS和BFS的递归和非递归实现!”
1.“创建无向图!”；
2.“图的深度优先遍历!”；
3.“图的广度优先遍历!”；
4.“退出!”；
请选择相应的数字键实现相应的功能。
②在执行图的遍历前必须先创建图，创建图时，按照系统的提示进行操作即可。
3.5程序清单
#include<stdio.h>
#include<malloc.h>
#define MAX 20
int visited[MAX]; //访问标志数组

typedef struct
{
char vexs[MAX]; //顶点向量
int arcs[MAX][MAX]; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和边数
}Graph;

typedef struct Qnode
{
int data;
struct Qnode *next;
}Qnode,*Queueptr;
typedef struct
{
Queueptr front;
Queueptr rear;
}Linkqueue;
void InitQueue(Linkqueue &Q)
{
Q.front=Q.rear=(Queueptr)malloc(sizeof(Qnode));
if(Q.front)
Q.front->next=NULL;
}
void EnQueue(Linkqueue &Q,int e)
{
Queueptr p;
p=(Queueptr)malloc(sizeof(Qnode));
if(p)
{
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
}
}
int DeQueue(Linkqueue &Q)
{
int e;
Queueptr p;
if(Q.rear!=Q.front)
{
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
}
if(Q.front==p)
Q.rear=Q.front;
return e;
}

int Locatevex(Graph G,char v) //返回元素v的位置
{
int i;
for(i=0;i<G.vexnum;i++)
if(G.vexs[i]==v)
return i;
return -1;
}
void CreateGraph(Graph &G) //创建无向图的邻接矩阵
{
int i,j,w,m,n;
char a,b,c;
printf("请输入图G的顶点数和弧数:");
scanf("%d%d",&G.vexnum,&G.arcnum);
getchar();
for(i=0;i<G.vexnum;i++)
visited[i]=0;
for(i=0;i<G.vexnum;i++)
{ printf("请输入第%d个顶点信息:",i+1);
scanf("%c",&G.vexs[i]);
getchar();
}
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=0;
for(i=0;i<G.arcnum;i++)
{
printf("请输入第%d条弧依附的两个顶点及权值: ",i+1);
scanf("%c %c %d%c",&a,&b,&w,&c);
m=Locatevex(G,a);
n=Locatevex(G,b);
G.arcs[m][n]=w;
G.arcs[n][m]=w;
}
}
void PrintMatrix(Graph G) //输出邻接矩阵
{
int i,j;
printf("\n由图G生成的邻接矩阵如下:\n");
for(i=0;i<G.vexnum;++i)
{
for(j=0;j<G.vexnum;++j)
printf("%-2d",G.arcs[i][j]);
printf("\n");
}
}

int FirstAdiVex(Graph G,int v) //图G中顶点v的第一个邻接顶点
{
int i;
if(v>=0&&v<G.vexnum)
{
for(i=0;i<G.vexnum;i++)
if(G.arcs[v][i]!=0)
return i;
}
return -1;
}
int NextAdVex(Graph G,int i,int j) //图G中顶点i的第j个邻接顶点的下一个邻接顶点
{
int k;
if(i>=0&&i<G.vexnum&&j>=0&&j<G.vexnum)
{
for(k=j+1;k<G.vexnum;k++)
if(G.arcs[i][k]!=0)
return k;
}
return -1;
}
void DFS(Graph G,int v) //从第v个顶点出发深度递归遍历图
{
int u;
printf("%2c",G.vexs[v]);
visited[v]=1;
u=FirstAdiVex(G,v);
while(u>=0)
{
if(!visited[u])
DFS(G,u);
u=NextAdVex(G,v,u);
}
}

void BFS(Graph G)//广度非递归遍历
{
int i,w,k;
Linkqueue Q;
InitQueue(Q);
for(i=0;i<MAX;i++)
visited[i]=0;
for(i=0;i<G.vexnum;i++)
if(!visited[i])
{
visited[i]=1;
printf("%2c",G.vexs[i]);
EnQueue(Q,i);
while(Q.front!=Q.rear)
{
k=DeQueue(Q);
for(w=FirstAdiVex(G,k);w>=0;w=NextAdVex(G,k,w))
if(!visited[w])
{
visited[w]=1;
printf("%2c",G.vexs[w]);
EnQueue(Q,w);
}
}
}
}

int main()
{
int m;
Graph G;
printf("无向图的创建及DFS和BFS的递归和非递归实现!\n\n");
while(1)
{
printf("1.创建无向图!\n");
printf("2.图的深度优先遍历!\n");
printf("3.图的广度优先遍历!\n");
printf("4.退出!\n");
printf("请选择功能:");
scanf("%d",&m);
if(m==1)
{
CreateGraph(G);
PrintMatrix(G);
}
else if(m==2)
{
printf("图G的深度递归优先遍历序列为:\n");
DFS(G,0);
printf("\n");
}
else if(m==3)
{
printf("图G的广度非递归优先遍历序列为:\n");
BFS(G);
printf("\n");
}
else if(m==4)
{
printf("成功退出!\n");
break;
}
else
printf("重新输入!\n");
}
return 0;
}

3.6测试结果
测试数据如下：
A
B
C
E
D
深度优先遍历序列：A->B->D->C->E
广度优先遍历序列：A->B->C->E->D
（1）程序开始的界面。

（2）创建无向图。

(3)图的深度优先遍历。

(4)图的广度优先遍历。

4.小结
在数据结构课程设计的过程中，我不仅认识到了学好解理论知识的必要性，更认识到了上机操作的重要性。上机操作能过培养我们解决实际问题的能力，通过对上机操作遇到的各种问题的解决，自己感到一丝成功的同时，更下决心努力学好专业课，为以后的学习及实践打下好的基础。

5.参考文献
①严蔚敏,吴伟民 编著.数据结构(C语言版)--北京:清华大学出版社
12