当前位置：文档之家› 图的遍历实现课程设计数据结构程序图

图的遍历实现课程设计数据结构程序图

数据结构课程设计

设计说明书

图的遍历的实现

数学与计算机科学学院 2014年1 月 4日

学生姓名英茜学号

1118064033 班级

网络1101班成绩指导教师

申静

课程设计任务书

2013—2014学年第一学期

课程设计名称：数据结构课程设计

课程设计题目：图的遍历实现

完成期限：自2013年12 月23日至2014年 1 月4 日共 2 周

设计内容：

1. 任务说明

(1) 采用邻接表存储结构创建一个图；

(2) 编程实现图的深度优先搜索（或广度优先搜索）遍历算法；

(3) 输出遍历结果；

(4) 给定具体数据调试程序。

2. 要求

1）问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？

2）逻辑设计：写出抽象数据类型的定义，各个主要模块的算法，并画出模块之间的调用关系图；

3）详细设计：定义相应的存储结构并写出各函数的伪码算法。

4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。

5）程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。

6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析；

7）编写课程设计报告。

3. 参考资料

指导教师：申静教研室负责人：余冬梅

课程设计评阅

摘要

针对图问题中如何更好地实现图的遍历问题，以无向图为例，分别采用广度优先遍历和深度优先遍历的算法实现对各节点的遍历，以VC++为开发环境进行系统的设计和实现，其运行结果表明，系统能很好地完成遍历后节点的输出，实现了遍历的目的，系统界面友好，可操作性强。

关键词：数据结构；存储结构；邻接矩阵

一课题描述 (1)

二设计目的与任务 (2)

2.1课程设计的目的 (2)

2.2课程设计的任务 (2)

三设计方案和实施 (3)

3.1总体设计 (3)

3.2基本操作 (3)

3.3详细设计 (4)

四运行调试结果 (6)

五结论与致谢 (9)

六附录 (11)

一课题描述

数据结构是一门专业基础课，它对学习者的要求很明确：学会分析、研究计算机加工的数据结构的特性，以便为应用设计所需的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。其次，该课程的学习过程也是复杂程序设计的训练过程，要求学习者编写的程序结构或设计的程序结构体清楚、正确、易读，符合软件工程的规范。

图是一种较为复杂且重要的数据结构，其特殊性在于图形结构中结点之间的关系可以是任意的，图中任意两个数据元素之间都有可能相关。就本课程设计而言应用图论的知识讨论如何在计算机上实现图的遍历的操作，主要解决图的遍历的几种方法的实现。

本设计采用目前最通用的程序设计语言之一—C语言作为数据结构和算法的描述语言。

二设计目的与任务

2.1课程设计的目的

进一步的了解图的遍历的问题，图的DFS,BFS的递归和非递归算法的实现，用无向图来实现图的遍历。

初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。

训练学生灵活应用所学数据结构的基本知识，熟练的完成问题分析、算法设计、编写程序，求解出指定的问题。

训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养严谨的科学态度和良好的工作作风。

提高综合运用所学的理论知识和方法独立分析和解决问题的能力。

2.2课程设计的任务

1）任务说明

用C/C++编写一个程序实现图的遍历的算法。

从键盘上输入一个图的基本信息（图用邻矩阵表示）。图的DFS,BFS的递归和非递归算法的实现;用有向图实现图的遍历；用无向图实现图的遍历；用邻接矩阵存储图；用邻接表存储图。

2）要求

1>首先输入图的结点数；

2>依次输入图的各条边（数据之间用空格隔开）；

3>输出的形式：按用户选择的遍历方法给出遍历顺序，各字符间用->分隔；

4>程序所能达到的功能：能够按要求输出所要的结果。

三设计方案和实施

3.1总体设计

采用邻接矩阵作为图的存储结构。程序中主要用到以下抽象数据类型：抽象数据类型的定义

typedef struct{

char *vexs; //顶点向量

int arcs[MAX_VEX][MAX_VEX];//邻接矩阵

int vexnum,arcnum; //图的当前顶点数和弧数

}Graph;

3.2基本操作

CreateUDN(Graph &G)

操作结果：用邻接矩阵创建带权无向网图。

DFS(Graph G,int k)

操作结果：对已存在的图进行深度优先遍历。

BFS(Graph G)

操作结果：对已存在的图进行广度优先遍历。

choose(Graph G)

操作结果：对将要实现的操作步骤进行选择。

程序包含两个模块

主程序模块，其中主函数为

int main{

输入信息；

根据输入要求进行选择操作和输出；

输出结果；

}

选择操作模块—实现具体选择的对应操作及输出操作。

两模块之间关系如下图3.1所示

图3.1 模块关系图

3.3详细设计

程序流程图如图3.2所示

图3.2 程序流程图

函数设计程序设计中主要包括下列函数用邻接矩阵创建一个图：

void CreateUDN(Graph &G){

用邻接矩阵创建一个带权无向网图;

输入顶点数和弧数;

输入各个顶点及各条弧;

}

递归方法实现图的遍历：

void DFS(Graph G, int k)

{

用递归的方法访问图中的结点;

对图进行深度优先遍历;

}

非递归方法实现图的遍历：

void BFS(Graph G)

{

用队列辅助访问图中的结点;

对图进行广度优先遍历;

}

选择输出需要的遍历方法：

void choose(Graph G)

{

给出程序运行的选项;

对相应的输入选项调用相应的函数以执行操作；

}

四运行调试结果

)

例：遍历如下无向图（图4.1）(a,b,c,d,e分别表示V1 V2 V3 V4 V5五个顶点

步骤一：

运行程序，按提示首先输入顶点数和弧数。

图4.2输入顶点数和弧数

步骤二：

输入顶点和弧

（1）输入顶点

图4.3 输入各顶点

（2）输入弧

图4.3 输入各条弧

步骤三：

选择便利方式以及选择后结果

选择1操作显示广度优先编历结果

图4.4 广度优先结果

选2操作显示深度优先遍历

图4.4深度优先遍历结果

五结论与致谢

在程序设计中我主要是解决的是给出一个图如何用多种方法完成图的遍历的问题，也包括

如何创建一个图，深度优先遍历和广度优先遍历一个图，递归和非递归的方法实现图的遍历。

程序最终通过调试运行，初步实现了设计目标。

图是一种较为复杂且重要的数据结构，其特殊性在于图形结构中结点之间的关系可以是任意的，图中任意两个数据元素之间都有可能相关。用邻接矩阵作为图的数据存储结构很好地解决了图的结构难点，借助于邻接矩阵容易判定任意两个顶点之间是否有边(或弧)相连，并容易求得各个顶点的度。该程序通俗易懂且实用性强，并且该程序清单详细具体、全面、具有很强的可读性；系统整体上比较完美，可以从键盘获取输入元素，并且可以根据用户输入进行选择性地输出；整体输出画面效果整洁、大方。

这次课程设计也让我充分认识到《数据结构》这门课的重要性。它给我们一个思想和大纲，让我们在编程时容易找到思路，不至于无章可循。同时它也有广泛的实际应用。

最后，我还要特别感谢我们的辅导老师申静老师，在她的精心辅导和帮助下，我的设计才得以顺利完成。对她为我们的设计所提出的宝贵意见表示忠心的感谢！

参考文献

[1]谭浩强. C程序设计[第三版]. 北京:清华大学出版社.

[2]罗宇等. 数据结构[M ].北京邮电大学出版社.

[3]严藯敏. 数据结构[C语言版]. 北京:清华大学出版社.

[4]杨路明. C语言程序设计教程. 北京邮电大学出版社.

[5]徐孝凯. 数据结构课程实验. 清华大学出版社.

六附录

源程序代码

// 程序功能：采用递归和非递归算法，有向图和无向图，邻接矩阵和邻接表等多种结构存储实现图的遍历。

// 程序作者：英茜

// 最后修改日期：2014-1-3

#include"stdio.h"

#include"stdlib.h"

#define INFINITY 32767

#define MAX_VEX 20 //最大顶点个数

#define QUEUE_SIZE (MAX_VEX+1) //队列长度

bool *visited; //访问标志数组

int z=1; //图的邻接矩阵存储结构

typedef struct{

char *vexs; //顶点向量

int arcs[MAX_VEX][MAX_VEX]; //邻接矩阵

int vexnum,arcnum; //图的当前顶点数和弧数

}Graph;

class Queue{ //队列类

public:

void InitQueue(){

base=(int *)malloc(QUEUE_SIZE*sizeof(int));

front=rear=0;

}

void EnQueue(int e){

base[rear]=e;

rear=(rear+1)%QUEUE_SIZE;

}

void DeQueue(int &e){

e=base[front];

front=(front+1)%QUEUE_SIZE;

}

int *base;

int front;

int rear;

};

int Locate(Graph G,char c){ //图G中查找元素c的位置for(int i=0;i

if(G.vexs[i]==c) return i;

return -1;

}

void CreateUDN(Graph &G){ //创建无向网

int i,j,w,s1,s2;

char a,b,c,temp;

printf("输入顶点数和弧数(顶点数和弧数之间以空格隔开) : ");

scanf("%d%d",&G.vexnum,&G.arcnum);

temp=getchar(); //接收回车

G.vexs=(char *)malloc(G.vexnum*sizeof(char)); //分配顶点数目

printf("输入%d个顶点.\n",G.vexnum);

for(i=0;i

scanf("%c",&G.vexs[i]);

temp=getchar(); //接收回车

}

for(i=0;i

for(j=0;j

G.arcs[i][j]=INFINITY;

printf("输入%d条弧.\n",G.arcnum);

for(i=0;i

printf("输入弧%d: ",i);

scanf("%c %c %d%c",&a,&b,&w,&c); //输入一条边依附的顶点和权值s1=Locate(G,a);

s2=Locate(G,b);

G.arcs[s1][s2]=G.arcs[s2][s1]=w;

}

int FirstVex(Graph G,int k){ //图G中顶点k的第一个邻接顶点

if(k>=0 && k

for(int i=0;i

if(G.arcs[k][i]!=INFINITY) return i;

}

return -1;

}

//图G中顶点i的第j个邻接顶点的下一个邻接顶点

int NextVex(Graph G,int i,int j){

if(i>=0 && i=0 && j

for(int k=j+1;k

if(G.arcs[i][k]!=INFINITY) return k;

}

return -1;

}

//深度优先遍历

void DFS(Graph G,int k){

int i;

if(k==-1){ //第一次执行DFS时,k为-1

for(i=0;i

if(!visited[i]) DFS(G,i); //对尚未访问的顶点调用DFS

}

else{

visited[k]=true;

if(z==1)

printf("%c",G.vexs[k]);

else printf(" -> %c",G.vexs[k]); ++z; //访问第k个顶点

if((z-1)%G.vexnum==0) z=1;

for(i=FirstVex(G,k);i>=0;i=NextV ex(G,k,i))

if(!visited[i]) DFS(G,i); //对k的尚未访问的邻接顶点i递归调用DFS

}

//广度优先遍历

void BFS(Graph G){

int k;

Queue Q; //辅助队列Q

Q.InitQueue();

for(int i=0;i

if(!visited[i]){ //i尚未访问

visited[i]=true;

printf("%c ",G.vexs[i]);

Q.EnQueue(i); //i入列

while(Q.front!=Q.rear){

Q.DeQueue(k); //队头元素出列并置为k

for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w))

if(!visited[w]){ //w为k的尚未访问的邻接顶点

visited[w]=true;

printf("-> %c ",G.vexs[w]);

Q.EnQueue(w);

}

} printf("\n 请继续选择:\n");

}

void choose(Graph G){ //对输入选项调用相应的函数执行操作int i,m;

visited=(bool *)malloc(G.vexnum*sizeof(bool));

scanf("%d",&m);

switch(m){

case 1:

printf("广度优先遍历: ");

for(i=0;i

visited[i]=false;

BFS(G); choose(G); printf("\n");break;

case 2:

printf("深度优先遍历: ");

for(i=0;i

visited[i]=false;

DFS(G,-1);

printf("\n 请继续选择:\n");choose(G);break;

case 3:printf("程序结束."); break;

default : printf(" 输入错误!\n请在1-3中选择:\n"); choose(G);

}

//主函数

void main(){

int i,m;

Graph G;

CreateUDN(G);

printf("有如下选项供选择：\n");

printf("\n");

printf("|*| 1:广度优先遍历2:深度优先遍历3:退出本程序！|*|\n"); printf("\n");

printf("请选择(1--3):\n");

choose(G);

}

二叉排序树的建立及遍历的实现

课程设计任务书题目: 二叉排序树的建立及遍历的实现初始条件：理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法；实践：计算机技术系实验室提供计算机及软件开发环境。要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、系统应具备的功能：（1）建立二叉排序树；（2）中序遍历二叉排序树并输出排序结果； 2、数据结构设计； 3、主要算法设计； 4、编程及上机实现； 5、撰写课程设计报告，包括：（1）设计题目；（2）摘要和关键字；（3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、设计体会等；（4）结束语；（5）参考文献。时间安排：2007年7月2日－7日（第18周） 7月2日查阅资料 7月3日系统设计，数据结构设计，算法设计 7月4日-5日编程并上机调试7月6日撰写报告 7月7日验收程序，提交设计报告书。指导教师签名： 2007年7月2日系主任（或责任教师）签名： 2007年7月2日排序二叉树的建立及其遍历的实现

摘要：我所设计的课题为排序二叉树的建立及其遍历的实现，它的主要功能是将输入的数据组合成排序二叉树，并进行，先序，中序和后序遍历。设计该课题采用了C语言程序设计，简洁而方便，它主要运用了建立函数，调用函数，建立递归函数等等方面来进行设计。关键字：排序二叉树，先序遍历，中序遍历，后序遍历 0．引言我所设计的题目为排序二叉树的建立及其遍历的实现。排序二叉树或是一棵空树；或是具有以下性质的二叉树：（1）若它的左子树不空，则作子树上所有的结点的值均小于它的根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；(3）它的左，右子树也分别为二叉排序树。对排序二叉树的建立需知道其定义及其通过插入结点来建立排序二叉树，遍历及其输出结果。该设计根据输入的数据进行建立排序二叉树。对排序二叉树的遍历，其关键是运用递归调用，这将极大的方便算法设计。 1．需求分析建立排序二叉树，主要是需要建立节点用来存储输入的数据，需要建立函数用来创造排序二叉树，在函数内，需要进行数据比较决定数据放在左子树还是右子树。在遍历二叉树中，需要建立递归函数进行遍历。该题目包含两方面的内容，一为排序二叉树的建立；二为排序二叉树的遍历，包括先序遍历，中序遍历和后序遍历。排序二叉树的建立主要运用了循环语句和递归语句进行，对遍历算法运用了递归语句来进行。 2．数据结构设计本题目主要会用到建立结点，构造指针变量，插入结点函数和建立排序二叉树函数，求深度函数，以及先序遍历函数，中序遍历函数和后序遍历函数，还有一些常用的输入输出语句。对建立的函明确其作用，先理清函数内部的程序以及算法在将其应用到整个程序中，在建立排序二叉树时，主要用到建立节点函数，建立树函数，深度函数，在遍历树是，用到先序遍历函数，中序遍历函数和后序遍历函数。

数据结构课程设计图的遍历和生成树求解

数学与计算机学院课程设计说明书课程名称: 数据结构与算法课程设计课程代码: 6014389 题目: 图的遍历和生成树求解实现年级/专业/班: 学生姓名: 学号: 开始时间: 2012 年 12 月 09 日完成时间: 2012 年 12 月 26 日课程设计成绩：指导教师签名：年月日

目录摘要 (3) 引言 (4) 1 需求分析 (5) 1.1任务与分析 (5) 1.2测试数据 (5) 2 概要设计 (5) 2.1 ADT描述 (5) 2.2程序模块结构 (7) 软件结构设计： (7) 2.3各功能模块 (7) 3 详细设计 (8) 3.1结构体定义 (19) 3.2 初始化 (22) 3.3 插入操作（四号黑体） (22) 4 调试分析 (22) 5 用户使用说明 (23) 6 测试结果 (24) 结论 (26)

摘要《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的： ?了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； ?初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； ?提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。关键词：计算机；图；算法。

图的遍历实现课程设计-数据结构-程序-图

数据结构课程设计设计说明书图的遍历的实现学生姓名英茜学号1１18064０33 班级网络1101班成绩指导教师申静数学与计算机科学学院 2０14年1 月4日

课程设计任务书 2013—２０14学年第一学期课程设计名称:数据结构课程设计课程设计题目:图的遍历实现完成期限：自2013年1２月23日至2014年１月4日共 2 周设计内容： 1. 任务说明 (1）采用邻接表存储结构创建一个图； (２）编程实现图的深度优先搜索(或广度优先搜索)遍历算法; (3) 输出遍历结果； (4) 给定具体数据调试程序。２．要求１）问题分析和任务定义：根据设计题目的要求,充分地分析和理解问题，明确问题要求做什么? 2)逻辑设计：写出抽象数据类型的定义，各个主要模块的算法,并画出模块之间的调用关系图； 3）详细设计：定义相应的存储结构并写出各函数的伪码算法。 4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。 5）程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。 6)结果分析:程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析; 7)编写课程设计报告。 3. 参考资料指导教师:申静教研室负责人：余冬梅课程设计评阅

摘要针对图问题中如何更好地实现图的遍历问题，以无向图为例,分别采用广度优先遍历和深度优先遍历的算法实现对各节点的遍历，以ＶＣ++为开发环境进行系统的设计和实现,其运行结果表明，系统能很好地完成遍历后节点的输出,实现了遍历的目的，系统界面友好,可操作性强。关键词：数据结构;存储结构；邻接矩阵

课程设计二叉树

安徽理工大学数据结构课程设计说明书题目: 二叉树的遍历集成院系：计算机科学与工程学院专业班级：学号：学生姓名：指导教师： 2015年 01 月 9 日

安徽理工大学课程设计（论文）任务书计算机科学与工程学院信息安全教研室 2014年 12 月 18 日

目录 1.需求分析 (1) 2、总体设计 (1) 2.1 程序目录 (1) 2.2 算法流程 (3) 3、详细设计 (3) 3.1 界面设计 (3) 3.2 详细代码设计 (5) 3.3 调试分析 (10) 4、总结 (15) 参考文献 (16) 代码详述 (16)

1.需求分析 “数据结构”是计算机程序设计的重要理论技术基础,它不仅是计算机学科的核心,而且也成为其他理工类学科必修课程,所谓”数据结构”是相互之间存在一种或多种特定关系的数据元素的集合.数据元素之间的相互关系成为结构,结构一般有线性结构,树形结构,图状结构,本程序所做的就是树形结构的二叉树的遍历算法和线索化查找. 本程序使用VC6.0++编写,具体实现功能有二叉树的遍历,包括先序遍历,中序遍历,后序遍历的递归算法以及非递归算法.另外本程序还有可线索化二叉树的功能,由此可以得到二叉树某个节点的前驱和后继. 题目要求为: 1.实现二叉树的各种遍历。包括先序遍历、中序遍历、后序遍历的递归和非递归算法、以及层次遍历。 2.要求能查找任一结点在某种遍历序列中的前驱和后继。 3.界面友好，易于操作。可采用菜单或其它人机对话方式进行选择。由小组一起制作,本人做小组汇总工作,并在基础上加了查找某个节点是否存在二叉树,以及求二叉树总节点数等一些简单功能 2、总体设计 2.1 程序目录 (1)typedef struct node 二叉树的定义,包含数据域data,左孩子lchild,右孩子rchild,若二叉树为空,则头结

数据结构实验报告-图的遍历

数据结构实验报告实验：图的遍历一、实验目的： 1、理解并掌握图的逻辑结构和物理结构——邻接矩阵、邻接表 2、掌握图的构造方法 3、掌握图的邻接矩阵、邻接表存储方式下基本操作的实现算法 4、掌握图的深度优先遍历和广度优先原理二、实验内容： 1、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接矩阵存储改图。 2、输入顶点数、边数、每个顶点的值以及每一条边的信息，构造一个无向图G，并用邻接表存储该图 3、深度优先遍历第一步中构造的图G，输出得到的节点序列 4、广度优先遍历第一部中构造的图G，输出得到的节点序列三、实验要求： 1、无向图中的相关信息要从终端以正确的方式输入； 2、具体的输入和输出格式不限； 3、算法要具有较好的健壮性，对错误操作要做适当处理； 4、程序算法作简短的文字注释。四、程序实现及结果： 1、邻接矩阵： #include #include #define VERTEX_MAX 30 #define MAXSIZE 20 typedef struct { int arcs[VERTEX_MAX][VERTEX_MAX] ; int vexnum,arcnum; } MGraph; void creat_MGraph1(MGraph *g) { int i,j,k; int n,m; printf("请输入顶点数和边数:"); scanf("%d%d",&n,&m); g->vexnum=n; g->arcnum=m; for (i=0;iarcs[i][j]=0;

数据结构课程设计二叉树遍历查找

课程设计任务书 2011 —2012 学年第一学期电子与信息工程系计算机专业09计算机一班班级课程设计名称：数据结构课程设计设计题目：排序二叉树的遍历完成期限：自2012 年 1 月 2 日至2012 年 1 月 6 日共 1 周设计依据、要求及主要内容（可另加附页）：一、设计目的熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。二、设计要求（1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；（2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩；（3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表；（4）认真编写课程设计报告。三、设计内容排序二叉树的遍历（用递归或非递归的方法都可以） 1)问题描述输入树的各个结点，建立排序二叉树，对建立的排序二叉树进行层次、先序、中序和后序遍历并统计该二叉树中叶子结点的数目。 2)基本要求 (1)用菜单实现 (2)能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列和叶子结点的数目。四、参考文献

1．王红梅．数据结构．清华大学出版社 2．王红梅．数据结构学习辅导与实验指导．清华大学出版社3．严蔚敏，吴伟民．数据结构（C语言版）．清华大学出版社 #include using namespace std; int num; //-----------排序二叉树节点--------------// struct tree //定义二叉树节点结构 { int data; //节点数据域 tree *right,*left; //右，左子树指针 }; //-----------排序二叉树类----------------// class Btree { tree *root;//根节点 public: Btree()

数据结构实验---图的储存与遍历

学号：姓名：实验日期： 2016.1.7 实验名称：图的存贮与遍历一、实验目的掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。二、实验内容与实验步骤题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。测试数据：如图所示题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。测试数据：如图所示 V0 V1 V2 V3 V4 三、附录：在此贴上调试好的程序。 #include #include #include V0 V1 V4 V3 V2 ??? ? ??? ? ????????=010000000101010 1000100010A 1 0 1 0 3 3 4

#define M 100 typedef struct node { char vex[M][2]; int edge[M ][ M ]; int n,e; }Graph; int visited[M]; Graph *Create_Graph() { Graph *GA; int i,j,k,w; GA=(Graph*)malloc(sizeof(Graph)); printf ("请输入矩阵的顶点数和边数(用逗号隔开)：\n"); scanf("%d,%d",&GA->n,&GA->e); printf ("请输入矩阵顶点信息：\n"); for(i = 0;in;i++) scanf("%s",&(GA->vex[i][0]),&(GA->vex[i][1])); for (i = 0;in;i++) for (j = 0;jn;j++) GA->edge[i][j] = 0; for (k = 0;ke;k++) { printf ("请输入第%d条边的顶点位置(i,j)和权值(用逗号隔开)：",k+1); scanf ("%d,%d,%d",&i,&j,&w); GA->edge[i][j] = w; } return(GA); } void dfs(Graph *GA, int v) { int i; printf("%c%c\n",GA->vex[v][0],GA->vex[v][1]); visited[v]=1;

数据结构图的遍历

#include"stdlib.h" #include"stdio.h" #include"malloc.h" #define INFINITY 32767 #define MAX_VERTEX_NUM 20 typedef enum{FALSE,TRUE}visited_hc; typedef enum{DG,DN,UDG,UDN}graphkind_hc; typedef struct arccell_hc {int adj; int*info; }arccell_hc,adjmatrix_hc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct {char vexs[MAX_VERTEX_NUM]; adjmatrix_hc arcs; int vexnum,arcnum; graphkind_hc kind; }mgraph_hc; typedef struct arcnode_hc {int adjvex; struct arcnode_hc *nextarc; int*info; }arcnode_hc; typedef struct vnode_hc {char data; arcnode_hc *firstarc; }vnode_hc,adjlist_hc[MAX_VERTEX_NUM]; typedef struct {adjlist_hc vertices; int vexnum,arcnum; graphkind_hc kind; }algraph_hc; int locatevex_hc(mgraph_hc*g,char v) {int i,k=0; for(i=0;ivexnum;i++) if(g->vexs[i]==v){k=i;i=g->vexnum;} return(k);}

二叉树遍历课程设计心得【模版】

目录一．选题背景 (1) 二．问题描述 (1) 三．概要设计 (2) 3.1.创建二叉树 (2) 3.2.二叉树的非递归前序遍历示意图 (2) 3.3.二叉树的非递归中序遍历示意图 (2) 3.4.二叉树的后序非递归遍历示意图 (3) 四．详细设计 (3) 4.1创建二叉树 (3) 4.2二叉树的非递归前序遍历算法 (3) 4.3二叉树的非递归中序遍历算法 (4) 4.4二叉树的非递归后序遍历算法 (5) 五．测试数据与分析 (6) 六．源代码 (6) 总结 (10) 参考文献: (11)

一．选题背景二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉链存储结构的每个结点包含三个域，分别是数据域，左孩子指针域，右孩子指针域。因此每个结点为由二叉树的定义知可把其遍历设计成递归算法。共有前序遍历、中序遍历、后序遍历。可先用这三种遍历输出二叉树的结点。然而所有递归算法都可以借助堆栈转换成为非递归算法。以前序遍历为例，它要求首先要访问根节点，然后前序遍历左子树和前序遍历右子树。特点在于所有未被访问的节点中，最后访问结点的左子树的根结点将最先被访问，这与堆栈的特点相吻合。因此可借助堆栈实现二叉树的非递归遍历。将输出结果与递归结果比较来检验正确性。。二．问题描述对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。画出搜索顺序示意图。

三．概要设计 3.1.创建二叉树 3.2.二叉树的非递归前序遍历示意图图3.2二叉树前序遍历示意图3.3.二叉树的非递归中序遍历示意图图3.3二叉树中序遍历示意图

数据结构课程设计-图的遍历和构建

图（Graph）是一种复杂的非线性结构。图可以分为无向图、有向图。若将图的每条边都赋上一个权，则称这种带权图网络。在人工智能、工程、数学、物理、化学、计算机科学等领域中，图结构有着广泛的应用。在图结构中，对结点（图中常称为顶点）的前趋和后继个数都是不加以限制的，即结点之间的关系是任意的。图中任意两个结点之间都可能相关。图有两种常用的存储表示方法：邻接矩阵表示法和邻接表表示法。在一个图中，邻接矩阵表示是唯一的，但邻接表表示不唯一。在表示的过程中还可以实现图的遍历（深度优先遍历和广度优先遍历）及求图中顶点的度。当然对于图的广度优先遍历还利用了队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）来实现。这不仅让我们巩固了之前学的队列的基本操作，还懂得了将算法相互融合和运用。

第一章课程设计目的 (3) 第二章课程设计内容和要求 (3) 2.1课程设计内容 (3) 2.1.1图的邻接矩阵的建立与输出 (3) 2.1.2图的邻接表的建立与输出 (3) 2.1.3图的遍历的实现 (4) 2.1.4 图的顶点的度 (4) 2.2 运行环境 (4) 第三章课程设计分析 (4) 3.1图的存储 (4) 3.1.1 图的邻接矩阵存储表示 (4) 3.1.2 图的邻接表存储表示 (5) 3.2 图的遍历 (5) 3.2.1 图的深度优先遍历 (5) 3.2.2 图的广度优先遍历 (6) 3.3图的顶点的度 (7) 第四章算法（数据结构）描述 (7) 4.1 图的存储结构的建立。 (7) 4.1.1 定义邻接矩阵的定义类型 (7) 4.1.2定义邻接表的边结点类型以及邻接表类型 (7) 4.1.3初始化图的邻接矩阵 (8) 4.1.4 初始化图的邻接表 (8) 4.2 图的遍历 (8) 4.2.1 深度优先遍历图 (8) 4.2.2 广度优先遍历图 (9) 4.3 main函数 (9) 4.4 图的大致流程表 (10) 第五章源代码 (10) 第六章测试结果 (20) 第七章思想总结 (21) 第八章参考文献 (22)

二叉树遍历课程设计】汇编

数据结构程序设计报告学院：班级：学号：姓名：

实验名称：二叉树的建立与遍历一、实验目的： 1.掌握二叉树的二叉链表存储结构； 2.掌握二叉树创建方法； 3.掌握二叉树的先序、中序、后序的递归实现方法。二、实验内容和要求：创建二叉树，分别对该二叉树进行先序、中序、后序遍历，并输出遍历结果。三、叉树的建立与遍历代码如下： #include #include struct tnode//结点结构体 { char data; struct tnode *lchild,*rchild; }; typedef struct tnode TNODE; TNODE *creat(void) { TNODE *root,*p; TNODE *queue[50];

int front=0,rear=-1,counter=0;//初始队列中需要的变量front、rear和计数器counter char ch; printf("建立二叉树，请输入结点:（#表示虚节点,!表示结束)\n"); ch=getchar(); while(ch!='!') { if(ch!='#') { p=(TNODE *)malloc(sizeof(TNODE)); p->data=ch; p->lchild=NULL; p->rchild=NULL; rear++; queue[rear]=p;//把非#的元素入队 if(rear==0)//如果是第一个元素，则作为根节点 { root=p; counter++; } else { if(counter%2==1)//奇数时与其双亲的左子树连接 { queue[front]->lchild=p; } if(counter%2==0)//偶数时与其双亲的右子树连接 { queue[front]->rchild=p;

数据结构课程设计之图的遍历和生成树求解

##大学数据结构课程设计报告题目：图的遍历和生成树求解院（系）：计算机工程学院学生: 班级：学号: 起迄日期: 2011.6.20 指导教师:

2010—2011年度第 2 学期一、需求分析 1.问题描述：图的遍历和生成树求解实现图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（及其孩子结点）相关但只能和上一层中一个元素（即双亲结点）相关；而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。生成树求解主要利用普利姆和克雷斯特算法求解最小生成树，只有强连通图才有生成树。 2.基本功能 1) 先任意创建一个图； 2) 图的DFS,BFS的递归和非递归算法的实现 3) 最小生成树（两个算法）的实现，求连通分量的实现 4) 要求用邻接矩阵、邻接表等多种结构存储实现 3.输入输出

输入数据类型为整型和字符型，输出为整型和字符二、概要设计 1.设计思路： a.图的邻接矩阵存储：根据所建无向图的结点数n,建立n*n的矩阵，其中元素全是无穷大（int_max），再将边的信息存到数组中。其中无权图的边用1表示，无边用0表示；有全图的边为权值表示，无边用∞表示。 b.图的邻接表存储：将信息通过邻接矩阵转换到邻接表中，即将邻接矩阵的每一行都转成链表的形式将有边的结点进行存储。 c.图的广度优先遍历：假设从图中的某个顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后再访问此邻接点的未被访问的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中还有未被访问的，则另选未被访问的重复以上步骤，是一个非递归过程。 d.图的深度优先遍历：假设从图中某顶点v出发，依依次访问v的邻接顶点，然后再继续访问这个邻接点的系一个邻接点，如此重复，直至所有的点都被访问，这是个递归的过程。 e.图的连通分量：这是对一个非强连通图的遍历，从多个结点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其连通分量的顶点集。本程序利用的图的深度优先遍历算法。 2.数据结构设计： ADT Queue{ 数据对象：D={a i | a i ∈ElemSet,i=1,2,3……，n,n≥0} 数据关系：R1={| a i-1 ,a i ∈D,i=1,2,3,……，n} 基本操作： InitQueue(&Q) 操作结果：构造一个空队列Q。 QueueEmpty(Q) 初始条件：Q为非空队列。操作结果：若Q为空队列，则返回真，否则为假。 EnQueue(&Q,e) 初始条件：Q为非空队列。操作结果：插入元素e为Q的新的队尾元素。 DeQueue(&Q,e) 初始条件：Q为非空队列。操作结果：删除Q的队头元素，并用e返回其值。}ADT Queue