数据结构先序遍历

数据结构》实验报告

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

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

一、需求分析

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

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

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

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

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

中序：edcba 输出：后序：edcba

二概要设计

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

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

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

三详细设计

1. 定义二叉树节点类型

struct node

{

char data;

struct node *lchil

数据结构实验五实验报告

实验名称：图的遍历

姓名：黄州龙 班级：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、 程序中采用的图

2011-2012年数据结构 课程设计实验报告

学院：计算机学院

班级： 姓名: 学号： 邮箱： 年月日

《课程设计》实验报告

◎实验题目: 字典序

◎实验目的：设计合适的数据结构，建立字典树，解决文件中单词的搜索统计问题。

◎实验内容：现在有一个英文字典（每个单词都是由小写的'a'-'z'组成），单词量很大，达到100多万的单词，而且还有很多重复的单词。

此外，我们现在还有一些 Document，每个Document 包含一些英语单词。 针对这个问题，请你选择合适的数据结构，组织这些数据，使时间复杂度和空间复杂度尽可能低，并且解决下面的问题和分析自己算法的时间复杂度。 1）基本型问题

（1）选择合适的数据结构，将所有的英文单词生成一个字典Dictionary。 （2）给定一个单词，判断这个单词是否在字典 Dictionary中。如果在单词库中，输出这个单词总共出现的次数。否则输出NO。 2）扩展型问题

（3）给定一个单词，按字典序输出字典 Dictionary 中所有以这个单词为前缀的单词。例如，如果字典 T={a,aa, aaa, b, ba}, 如果你输入 a,那么输出应该为{a, aa, aaa}。

（4）给定一个单词，输出

数据结构

课程设计报告

班级：

姓名：

学号：

目录

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

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

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

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

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

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

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

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

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

一．设计任务：

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

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

二、设计时间

2009年12月28日

三、设计内容

1、需求分析

本题目需要

合肥学院

计算机科学与技术系

课程设计报告

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))))