数据结构-邻接表存储及遍历-课程设计-实验报告。

数 据 结 构 课 程 设 计

设计题目：学生姓名：专业班级：指导教师：完成时间：

邻接表存储及遍历

数据结构(c 语言版)课程设计报告

课题名称 院 学 系 号

邻接表存储及遍历 年级专业 姓 名 成 绩

1、课题设计目的：①通过实习掌握《数据结构》中的知识。对于本 课题所要求掌握的数据结构知识主要有：图的邻接表储存结构、邻 接表的算法实现、图的广度优先搜索遍历、图的深度优先搜索遍历。 2、课题设计意义：①培养学生运用数据结构的基本知识解决实际编 程中的数据结构设计和设计问题。 课题设计 ②培养学生独立设计程序与解决问题的能力，培养学生团队协作集 目的与 成程序模块及调试能力。 设计意义

指导教师： 年 月 日

目 录

第一章 需求分析 ....................................................................................................................................... 1

1.1 图 ................................................................................................................................................ 1 1.2 邻接表的概念 ........................................................................................................................... 1 1.3邻接表的表示法 .......................................................................................................................... 1 第二章 概要分析 ..................................................................................................................................... 2

2.1 无向图 ....................................................................................................................................... 2 2.2 有相图......................................................................................................................................... 2 2.3 无向图 ....................................................................................................................................... 2 2.4有向图.......................................................................................................................................... 2 第三章 详细分析 ....................................................................................................................................... 3

3.1 邻接表的建立 ............................................................................................................................. 3 3.2 邻接表的建立过程如下： ....................................................................................................... 3

3.2.1无向图邻接表的建立 ...................................................................................................... 3 3.2.2 有向图邻接表的建立 ..................................................................................................... 4 3.3 邻接表的输出过程如下： ....................................................................................................... 4 3.4 邻接表的遍历 ........................................................................................................................... 5

3.4.1 连通图的深度优先搜索遍历 ....................................................................................... 5 3.4.2 有向图的广度优先搜索遍历 ....................................................................................... 6 3.5 流程图 ....................................................................................................................................... 7

3.5.1 主流程图 ..................................................................................................................... 7 3.5.2 无向图邻接表的流程图 ............................................................................................... 7 3.5.3 有向图邻接表的流程图 ............................................................................................... 9

第四章 测试分析 ..................................................................................................................................... 11

4.1 无向图....................................................................................................................................... 11

4.1.1 主程序main()编写如下： ...................................................................................... 11 4.1.2 运行步骤 ..................................................................................................................... 13 4.2 有向图....................................................................................................................................... 15 第五章 心得体会 ..................................................................................................................................... 17 第六章、参考文献 ................................................................................................................................... 17

第一章 需求分析

1.1 图

①若图1.1 ②若图1.1

v2

图1.1 1.2 邻接表的概念

对于图1.1中的每个顶点vi，该方法把所有邻接于vi

的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表。

1.3邻接表的表示法

邻接表中每个表结点均有2个域，其一是邻接点域（adjvex），用以存放与vi相邻接的顶点vj的序号；其二是链域（next），用来将邻接表的所有表结点链在一起。

并且为每个顶点vi的邻接表设置一个具有2个域的表头结点：一个是顶点域（vertex），用来存放顶点vi的信息；另一个是指针域（link），用于存入指向vi的邻接表中第一个表结点的头指针。

第二章 概要分析

2.1 无向图

无向图邻接表的建立，无向图邻接表的输出，无向图邻接表的深度优先搜索遍历，无向图邻接表的广度优先搜索遍历。

2.2 有相图

有向图邻接表的建立，有向图邻接表的输出，有向图邻接表的深度优先搜索遍历，有向图邻接表的广度优先搜索遍历。

2.3 无向图

2.4有向图

第三章 详细分析

3.1 邻接表的建立

邻接表是把所有邻接于vi的顶点vj链成一个单链表。其次还需要一个顺序表来储存顶点信息。其具体C语言代码如下： typedef struct node {

int adjvex;/*邻接点域*/ struct node *next;/*链域*/ }edgenode;/*边表结点*/

3.2 邻接表的建立过程如下：

3.2.1无向图邻接表的建立

void creat_ljb(topnode gl[],int n,int e) /*无向图邻接表的建立*/ {

int i,j,k; edgenode *p; getchar();

printf("请输入%d个顶点的元素:",n); for(i=0;i<n;i++)/*读入顶点信息*/ {

scanf("%c",&gl[i].topvex)；

gl[i].link=NULL; /*边表头指针初始化*/ }

printf("请输入要邻接的俩个顶点的下标:\n"); for(k=0;k<e;k++) /*建立边表*/ {

scanf("%d%d",&i,&j);

p=(edgenode *)malloc(sizeof(edgenode)); p->adjvex=j;

p->next=gl[i].link; gl[i].link=p;

p=(edgenode *)malloc(sizeof(edgenode)); p->adjvex=i; p->next=gl[j].link; gl[j].link=p; } }

3.2.2 有向图邻接表的建立

void creat_yljb(topnode gl[],int n,int e)/*有向图邻接表的建立*/ {

int i,j,k; edgenode *p; getchar();

printf("请输入%d个顶点的元素:",n); for(i=0;i<n;i++) {

scanf("%c",&gl[i].topvex); gl[i].link=NULL; }

printf("请输入要邻接的俩个顶点的下标:\n"); for(k=0;k<e;k++) {

scanf("%d%d",&i,&j);

p=(edgenode *)malloc(sizeof(edgenode)); p->adjvex=j; p->next=gl[i].link; gl[i].link=p; } }

3.3 邻接表的输出过程如下：

void print_ljb(topnode gl[],int n)/*邻接表的输出*/

{

int i; edgenode *p;

printf("建立后的邻接表为:\n"); for(i=0;i<n;i++) {

printf("%c\t",gl[i].topvex); p=gl[i].link; while(p) {

printf("%d\t",p->adjvex); p=p->next; }

printf("\n"); } }

3.4 邻接表的遍历

对于图的遍历，和树的遍历类似，也是从某个顶点出发，沿着搜索路径对图中所有顶点做一次访问。若给定的图是连通图，则从图中人一顶点出发顺着边可以访问到该图的所有顶点。又因为图中任一顶点都可能和其余顶点相邻接，故在访问了某个顶点之后，可能顺着某条路又反回到了该顶点。为避免重复访问同顶点，必须记住每个顶点是否被访问过。为此，我们已经在前面设置了向量int visited[vexnum]={0}来标示，他的初始值为0。 3.4.1 连通图的深度优先搜索遍历 int visited_lj[20]={0};

void DFSL(topnode gl[],int i)/*邻接表的深度遍历*/ {

edgenode *p;

printf("%c",gl[i].topvex); visited_lj[i]=1; p=gl[i].link; while(p!=NULL)

{

if(visited_lj[p->adjvex]==0) DFSL(gl,p->adjvex); p=p->next; } }

int visited[20]={0};

3.4.2 有向图的广度优先搜索遍历 int visited_ljb[20]={0};

void BFSL(topnode gl[],int k)/*邻接表的广度遍历*/ {

int i; edgenode *p; linkqueue Q; setnull(&Q);

printf("%c",gl[k].topvex); visited_ljb[k]=1; enqueue(&Q,k); while(!empty(&Q)) {

i=dequeue(&Q); p=gl[i].link; while(p!=NULL) {

if(!visited_ljb[p->adjvex]) {

printf("%c",gl[p->adjvex].topvex); visited_ljb[p->adjvex]=1; enqueue(&Q,p->adjvex); }

p=p->next; } } }

int visited_jz[20]={0}; 3.5 流程图

3.5.1

3.5.2 无向图邻接表的流程图

数据结构(c 语言版)课程设计报告

输出建立后邻接表

输入深度遍历起 始位置

P!=NULL

否

是 Visited-lj[p->adjvex==0] 否

是

输出遍历结果

输出建立后邻接表

输入广度遍历起 始位置

!empty(&Q)

否

是 P!=NULL 否

是 !visited-ljb[p->adjvex]

8

8

3.5.3 有向图邻接表的流程图

数据结构(c 语言版)课程设计报告

否

Visited-lj[p->adjvex==0] 是

否

是

输出遍历结果

输出建立后邻接表

输入广度遍历起 始位置

否 !empty(&Q)

是 否 P!=NULL

是

!visited-ljb[p->adjvex]

否

是

输出遍历结果

结束

10

10

第四章 测试分析

运行环境：Microsoft Visual C++ 程序语言：C语言

下面，我们来检验一下程序能否正确运行。 4.1 无向图

顶点信息

序号 元素

0 a 1 b 2

c

3

4.1.1 主程序main()编写如下：

void main()

{

int i=1,j,n,e; int k=1,m=1,l=1,t=1; graph ga; topnode *gl;

printf("\t\t\t邻接表表示图及深广度优先遍历\n"); while(i) {

printf("\n1:无向图\n2:有向图\n"); scanf("%d",&i); switch(i) {

case 1://无向图的基本运算 while(k)

{

printf("\n1:无向图邻接表的建立\n2:无向图邻接表的

输出\n3:无向图邻接表的深度遍历\n4:无向图邻接表的广度遍历\n"); scanf("%d",&k);

switch(k) {

case 1:printf("请输入顶点数和边数:"); scanf("%d%d",&n,&e); creat_ljb(&gl,n,e); break;

case 2:print_ljb(&gl,n); break;

scanf("%d",&k); } break;

case 2://有向图的基本运算 while(l) {

printf("\n1:有向图邻接表的建立\n2:有向图邻接表

的输出\n3:有向图邻接表的深度遍历\n4:有向图邻接表的广度遍历\n"); scanf("%d",&l);

case 3:printf("请输入要遍历的起始位置:"); scanf("%d",&j);

printf("邻接表深度遍历后的结果为:") break;

case 4:printf("请输入要遍历的起始位置:"); scanf("%d",&j);

printf("邻接表广度遍历后的结果为:"); BFSL(&gl,j); break;

printf("\n0:结束\n1:继续\n");

DFSL(&gl,j);

}

switch(l)

case 1:printf("请输入顶点数和边数:");

{

为:");

scanf("%d%d",&n,&e);

creat_yljb(&gl,n,e);

case 2:print_ljb(&gl,n);

break;

break;

case 3:printf("请输入要遍历的起始位置:"); scanf("%d",&l);

printf("邻接表深度遍历后的结果为:"); DFSL(&gl,l);

break;

case 4:printf("请输入要遍历的起始位置:"); scanf("%d",&l);

printf("邻接表广度遍历后的结果

BFSL(&gl,l);

break;

}

printf("\n0:结束\n1:继续\n"); scanf("%d",&l);

} break;

}

printf("\n0:结束无向图的运算1:继续无向图的运算\n"); scanf("%d",&i); } }

4.1.2 运行步骤

1 无向图邻接表建立与输出

2 广度与深度遍历

4.2 有向图

2

3

顶点信息

序号 元素 0 1 2 3

a b c d

其主函数于无向图相图 运行步骤

1 有向图的建立与输出

2有向图邻接表的深度与广度遍历

第五章 心得体会

数据结构交给我们了许多关于电脑的知识，开阔了我们的视野，让我们更加喜爱计算机，同时教给我们许多不足，让我们充分了解了计算机的乐趣及其重要性，本章的学习，让我们了解了许多，也懂得了许多……

第六章、参考文献

1. 徐德民.最新C语言程序设计.电子工业出版社，1992 2. 张国锋.C++语言及其程序设计教程.电子工业出版社，1992 3. 百度文库

本文来源：https://www.bwwdw.com/article/nwae.html