1、 数 据 结 构 课 程 设 计 设计题目： 邻接表存储及遍历 学生姓名： 专业班级： 指导教师： 完成时间： 数据结构（c 语言版）课程设计报告 课题名称 邻接表存储及遍历 院 系 年级专业 学 号 姓 名 成 绩 课题设计 目的与 设计意义 1、课题设计目的：通过实习掌握数据结构中的知识。对于本 课题所要求掌握的数据结构知识主要有：图的邻接表储存结构、邻 接表的算法实现、图的广度优先搜索遍历、图的深度优先搜索遍历。 2、课题设计意义：培养学生运用数据结构的基本知识解决实际编 程中的数据结构设计和设计问题。 培养学生独立设计程序与解决问题的能力，培养学生团队协作集 成程序模块及调试能力。 指
2、导教师： 年 月 日 数据结构（c 语言版）课程设计报告 目目 录录 第一章 需求分析 .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 流程
3、图 .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 数据结构（c 语言版）课程设计报告 1 1 第一章第一章 需求分析需求分析 1.1 图 若图 1.1 中每一条边都是有方向的，则为有相图。 若图 1.1 中每一条边都是没有方向的，则为无向图。 v2 图 1.1 1.2 邻接表的概念 对于图 1.1 中的每个顶点 vi，该
4、方法把所有邻接于 vi 的顶点 vj 链成一个单链表，这个单链表就称为顶点 vi 的邻接表。 1.3 邻接表的表示法 邻接表中每个表结点均有 2 个域，其一是邻接点域（adjvex），用以存放与 vi 相邻接的顶点 vj 的序号；其二是链域（next），用来将邻接表的所有表结点链在一 起。 并且为每个顶点 vi 的邻接表设置一个具有 2 个域的表头结点：一个是顶点域 （vertex），用来存放顶点 vi 的信息；另一个是指针域（link），用于存入指向 vi 的邻接表中第一个表结点的头指针。 数据结构（c 语言版）课程设计报告 2 2 第二章第二章 概要分析概要分析 2.1 无向图 无向图邻接
5、表的建立， 无向图邻接表的输出， 无向图邻接表的深度优先搜索遍历， 无向图邻接表的广度优先搜索遍历。 2.2 有相图 有向图邻接表的建立， 有向图邻接表的输出， 有向图邻接表的深度优先搜索遍历， 有向图邻接表的广度优先搜索遍历。 2.3 无向图 函数名称 函数功能 creat_ljbiao 无向图邻接表的建立 print_ljb 无向图邻接表的输出 DFSL 无向图邻接表的深度遍历 BFSL 无向图邻接表的广度遍历 2.4 有向图 函数名称 函数功能 creat_yljb 有向图邻接表的建立 print_ljb 有向图邻接表的输出 DFSL 有向图邻接表的深度遍历 BFSL 有向图邻接表的广度
6、遍历 数据结构（c 语言版）课程设计报告 3 3 第三章第三章 详细分析详细分析 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;inext=gli.link; gli.link=p; p=(edgenode *)malloc(sizeof(edgenode); p-adjvex=
