数据结构后序遍历

数据结构实验五实验报告

实验名称：图的遍历

姓名：黄州龙 班级：08软件工程A班 学号：0825121022

一、 需求分析

1、 本实验要求要利用图论的一些基本概念和算法来

实现对无向图和有向图的2种遍历，分别是深度优先遍历(DFS)和广度优先遍历(BFS)，通过本实验对图遍历算法的实现来帮助了解图这一特殊(多对多)的数据结构，以便在以后的实际应用中可以以此为基础来进行更好的软件程序开发；

2、 该程序开始时是通过用户输入的图的数据文件

(.txt)所在的路径来读取对应文件中的图的数据，以此来构建，进而调用遍历算法函数来对图进行遍历，如果文件不存在或路径不正确，程序将会报告错误并终止；

3、 本程序读取的文件的格式是.txt文件，其中存储的

数据组成如下:

第一行:M N， M是图中结点的个数，N是图中

弧的条数

第二行:D ，D是1或0, 1表示该图是一个有向图，

0表示该图是一个无向图

第三行:M个互不相同的字符，代表每个结点的字

符数据

接下来的N行，每行有2个字母P1、P2，对于有

向图，表示存在一条从P1到P2的有向边；

对于无向图，表示在P1和P2之间存在一条边；

4、 程序中采用的图

数据结构实验五实验报告

实验名称：图的遍历

姓名：黄州龙 班级：08软件工程A班 学号：0825121022

一、 需求分析

1、 本实验要求要利用图论的一些基本概念和算法来

实现对无向图和有向图的2种遍历，分别是深度优先遍历(DFS)和广度优先遍历(BFS)，通过本实验对图遍历算法的实现来帮助了解图这一特殊(多对多)的数据结构，以便在以后的实际应用中可以以此为基础来进行更好的软件程序开发；

2、 该程序开始时是通过用户输入的图的数据文件

(.txt)所在的路径来读取对应文件中的图的数据，以此来构建，进而调用遍历算法函数来对图进行遍历，如果文件不存在或路径不正确，程序将会报告错误并终止；

3、 本程序读取的文件的格式是.txt文件，其中存储的

数据组成如下:

第一行:M N， M是图中结点的个数，N是图中

弧的条数

第二行:D ，D是1或0, 1表示该图是一个有向图，

0表示该图是一个无向图

第三行:M个互不相同的字符，代表每个结点的字

符数据

接下来的N行，每行有2个字母P1、P2，对于有

向图，表示存在一条从P1到P2的有向边；

对于无向图，表示在P1和P2之间存在一条边；

4、 程序中采用的图

数据结构

课程设计报告

班级：

姓名：

学号：

目录

一， 设计任务----------------------------------------3

二、 设计时间----------------------------------------3

三、 设计内容----------------------------------------3

1、需要分析----------------------------------------3

2、概要设计----------------------------------------3

3、详细设计----------------------------------------4

4、测试与分析--------------------------------------9

四、设计总结-----------------------------------------10

源程序清单--------------------------------------11

一．设计任务：

我选课程设计是自选题目《图的遍历》。

要求：设计一个程序，实现图的广度，深度优先遍历。

二、设计时间

2009年12月28日

三、设计内容

1、需求分析

本题目需要

数据结构》实验报告

◎实验题目: 创建并遍历二叉树◎实验目的：熟悉二叉树存储结构，熟悉二叉树的三种遍历方法，并能用非递归的方法建立并且遍历二叉树。

◎实验内容：用先序和中序建立二叉树，用后序遍历并输出二叉树，要求算法非递归。

一、需求分析

该程序用非递归的方法，利用先序和中序建立二叉树，然后用后序遍历的方法输出二叉树的

1、输入的形式和输入值的范围；程序运行时输入二叉树的先序和中序序列，为字符型元素。

2、输出的形式；运行结果为输出二叉树的后序序列，亦为字符型元素。

3、程序所能达到的功能；本程序可以建立一个二叉树存储结构，并且访问其结点元素。

4、测试数据：输入：先序：abcde

中序：edcba 输出：后序：edcba

二概要设计

1. 本程序中首先需定义二叉树的节点类型，节点为一个含有数据与和指针域的结构体。

2. 其次，本程序中需要用两个栈，一个用来存放指针，一个用来存放数组元素的下标。

3. 主程序中，分别输入两个字符串，作为二叉树的先序和中序序列；两个子函数分别实现创建二叉树和后序遍历输出二叉树的功能。而在子函数中还调用了例如出栈入栈等子函数。

三详细设计

1. 定义二叉树节点类型

struct node

{

char data;

struct node *lchil

合肥学院

计算机科学与技术系

课程设计报告

XX 学年第 二 学期

课学学专指

业导

班教生

姓

程 数据结构与算法

图遍历的演示

名 号 级 师

课程设计名称

XXXX 年 6 月

图遍历的演示

一、问题分析和任务定义

很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。将每个结点看做一个地名，如合肥。然后任选国内的城市，起点未合肥，忽略城市间的里程。

设图的结点20-30个，每个结点用一个编号表示(如果一个图有n个结点，则它们的编号分别为1，2，…，n)。通过输入图的全部边(存于数据文件中，从文件读写)输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。

二、数据结构的选择和概要设计

城市与城市之间的关系使没有方向的，无向图采用邻近多重表来实现，主要要表示无向图中的各个结点和边，在多重表中边是采用两个结点来表示的。

在邻接表中Edgenode表示邻接表中的结点类型，其中含有访问标记mark，一条边所依附的两个结点的序号ivex和jvex，以及分别指向依附于ivex和jvex的顶点边的链域ilink和jlink。

合肥学院

计算机科学与技术系

课程设计报告

XX 学年第 二 学期

课学学专指

业导

班教生

姓

程 数据结构与算法

图遍历的演示

名 号 级 师

课程设计名称

XXXX 年 6 月

图遍历的演示

一、问题分析和任务定义

很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。将每个结点看做一个地名，如合肥。然后任选国内的城市，起点未合肥，忽略城市间的里程。

设图的结点20-30个，每个结点用一个编号表示(如果一个图有n个结点，则它们的编号分别为1，2，…，n)。通过输入图的全部边(存于数据文件中，从文件读写)输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。

二、数据结构的选择和概要设计

城市与城市之间的关系使没有方向的，无向图采用邻近多重表来实现，主要要表示无向图中的各个结点和边，在多重表中边是采用两个结点来表示的。

在邻接表中Edgenode表示邻接表中的结点类型，其中含有访问标记mark，一条边所依附的两个结点的序号ivex和jvex，以及分别指向依附于ivex和jvex的顶点边的链域ilink和jlink。

摘要

针对现实世界中许多关系复杂的数据，如人类社会的家谱，各种社会组织机构,博弈交通等复杂事物或过程以及客观世界中广泛存在的具有分支关系或层次特性的对象．如操作系统的文件构成、人工智能和算法分析的模型表示以及数据库系统的信息组织形式等，用线性结构难以把其中的逻辑关系表达出来，必须借助于数和图这样的非线性结构，因此在以模拟客观世界问题，解决客观世界问题为主要任务的计算机领域中树型结构是信息的一种重要组织形式，树有着广泛应用。在树型结构的应用中又以二叉树最为常用。

二叉树是一种非常重要的非线性结构，所描述的数据有明显的层次关系，其中的每个元素只有一个前驱，二叉树是最为常用的数据结构，它的实际应用非常广泛，二叉树的遍历方式有三种，前序遍历，中序遍历，后序遍历，先序遍历的顺序为：NLR先根结点，然后左子树，右子树；中序遍历顺序为；LNR先左子树，然后根结点，右子树；后序遍历顺序为：LRN先左子树，然后右子树，根结点。由前序和中序遍历，有中序和后序遍历序列可以唯一确定一棵二叉树。对于给几个数据的排序或在已知的几个数据中进行查找，二叉树均能提供一种十分有效的方法，比如在查找问题上，任何借助于比较法查找长度为Ⅳ的一个序表的算法，都可以表示成一株二叉树。反之

数 据 结 构 课 程 设 计

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

邻接表存储及遍历

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

课题名称 院 学 系 号

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

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

指导教师： 年 月 日

目 录

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

1.1 图 .......................................................................

#include \#include \#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status;

typedef char ElemType; typedef struct BiTNode {

ElemType data;

struct BiTNode *lchild,*rchild;//左右孩子指针 } BiTNode,*BiTree;

Status CreateBiTree();

Status CreateBiTree(BiTree &T) // 算法6.4 {

// 按先序次序输入二叉树中结点的值（一个字符），’#’字符表示空树， // 构造二叉链表表示的二叉树T。 char ch;

scanf(\ if (ch=='#') T = NULL; else {

if (!(T = (BiTNode *)malloc(sizeof(BiTNode))))

数据结构

1

1.为解决计算机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。（全国统考2009） A．栈 B．队列 C．树 D．图

2.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后入队Q，若出队序列为e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是（ ）。（全国统考2009）

A．1 B．2 C．3 D．4

3.若元素abcdef依次进栈，允许进栈、出栈交替进行，不允许连续三次进行出栈操作，则不可能得到的出栈序列是（ ）。（全国统考2010）

A．dcebfa B．cbdaef C．dbcaef D．afedcb 4.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是（ ）。（全国统考2010） A．bacde B．dbace C．dbcae D．ecbad

5.元素abcde依次进入初