目录
一、课题的主要功能 (2)
1.1 设计内容 (2)
1.2 对课程设计功能的需求分析 (2)
二、课题的功能模块的划分. (2)
2.1 模块划分 (2)
2.2 系统的概要设计 (3)
三、主要功能的实现 (4)
3.1 算法思想 (4)
1. 图的邻接矩阵的建立 (4)
2. 图的遍历的实现 (4)
3.2 数据结构 (4)
3.3 主函数流程图 (5)
3.4 深度优先遍历流程图 (6)
3.5 深度优先遍历递归 (7)
3.6 深度优先遍历流程图 (8)
3.7 广度优先遍历递归流程图 (9)
四、程序调试 (11)
4.1 程序的调试分析 (11)
4.2 程序的测试结果 (11)
五、总结 (15)
六、附件 (16)
6.1 源程序 (16)
、课题的主要功能
1.1 设计内容
演示图的深度优先, 广度优先遍历过程，并输出原图结构及遍历结果。要求图的结点数不能少于 6 个。可以由系统随机生成图，也可以由用户手动输入图。报告中要写出画图的思路；画出图的结构，有兴趣的同学可以进一步改进图的效果。
1.2 对课程设计功能的需求分析
图的遍历并不需要是一个过于复杂的工作环境，一般来说：最合适的才是最好的。软件设计必须符合我们使用实际情况的需要。根据要求，图的遍历主要功能如下：
1. 用户可以随时建立一个有向图或无向图；
2. 用户可以根据自己的需要，对图进行深度遍历或广度遍历；
3. 用户可以根据自己的需要对图进行修改；
4. 在整个程序中,用户可以不断的按照不同的方式对图进行遍历,若不继续,用户也可以随时跳出程序,同时, 如果用户输入的序号错误, 程序会提示用户重新输入序号；
二、课题的功能模块的划分
2.1 模块划分
1. 队列的初始化、进队、出队、队列空、队列满的函数
void InitQueue(CirQueue *Q) // 初始化队列
int QueueEmpty(CirQueue *Q)// 队列是否为空
int QueueFull(CirQueue *Q)// 队列满
Void EnQueue(CirQueue *Q,int x)// 将队员进队
int DeQueue(CirQueue *Q)// 将队员出队
2. 创建图的函数
void CreateMGraph(MGraph *G)// 根据用户需要创建一个图
3. 图的深度优先遍历递归
void DFSM(MGraph *G,int i)/* 含有输出已访问的顶点的语句*/ 4. 图的广度优先遍历递归
void BFSM(MGraph *G,int k) /* 含有输出已访问的顶点的语句*/
5. 深度优先遍历
void DFSTraverseM(MGraph *G)/* 调用DFSM函数*/
6. 广度优先遍历
void BFSTraverseM(MGraph *G) /* 调用BFSM函数*/
7. 主函数
main() /* 包含一些调用和控制语句*/
2.2 系统的概要设计
开始
信息录入
深
度优先
三、主要功能的实现
3.1 算法思想
本课题所采用的是邻接
矩阵的方式存储图，实现图
的深度、广度两种遍历，并
将每种遍历结果输出来。
1.图的邻接矩阵的建立
对任意给定的图（顶点数和边数自定），根据邻接矩阵的存储结构建立图的邻接距
阵。
2.图的遍历的实现
图的遍历包括图的广度优先遍历与深度优先遍历。对于广度优先遍历应利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）来实现。首先建立一空队列，从初始点出发进行访问，当被访问时入队，访问完出队。并以队列是否为空作为循环控制条件。对于深度优先遍历则采用递归或非递归算法来实现，这里我所采用的是递归算法。
3.2 数据结构
#define Max 10
#define FALSE 0
#define TRUE 1
#define Error printf
#define QueueSize 30
typedef struct
{
char vexs[Max]; int edges[Max][Max]; int n,e;
}MGraph;
int visited[Max];
typedef struct
{
int front;
int rear;
int count;
int data[QueueSize];
}CirQueue;
3.3 主函数流程图
3.4 深度优先遍历流程图
3.5 深度优先遍历递
归
DFSM(MGraph *G,int i)
3.6 深度优先遍历流程图
i=0
i
visited[i]=FALSE
i++
i=0
i
visited[i]
非零零
BFS(G,i)
i++
结束程序3.7 广度优先遍历递归流程图
InitQueue(&Q)
四、程序调试
4.1 程序的调试分析
在调试过程中，程序中出现了许多的错误，有错误的调用, 一些变量没有定义等等。不断的对程序进行调试以得到最好的结果，程序中特别要注意的是类的对象作为作为参数时要注意如何去调用它，使程序有一个令人满意的结果，具体的调试是在上机过程中进行的，在编写程序的过程中主要有如下错误：
1. 在编写程序的过程出现了一些函数名、变量的大小写不统一的错误，导致程序在运行的过程中出现函数名、变量没有被定义等问题；
2. 在编写程序的过程中数组的大小写没有被确定；
3. 在编写程序的过程中一些变量没有被定义，导致程序出错；
4. 数组visited[Max] 应定义为全局变量，若不是则会出错；
5. 函数的返回类型要确定，是void 还是其他类型要十分注意；
6. 在编程的过程中，函数里一些控制语句的嵌套使用，括号要引起注意，
4.2 程序的测试结果
初始进入程序时，程序提示按格式输入图的顶点个数和边数。
输入顶点数和边数后，程序提示输入顶点的序号，为各顶点依次进行编号。
将各顶点进行编号后，程序提示按格式输入边的顶点序号。
按格式依次输入边的顶点序号后，按 enter 键程序会出现“选择菜单” ，用户根据需要 进行选择。
用户选择 2 进入深度优先搜索，并输出深度优先遍历后的序列，再次输出菜单栏，进行 选择。
用户再次选择 3 进入广度优先搜索，并输出广度优先遍历后的序列，再次输出菜单栏， 进行选择。
用户选择 1
后进入更改数据，重新创建一个图
用户选择 0，则退出程序
五、总结
通过这次数据结构课程设计实践，我学到了很多东西。本次课程设计对我来说正是 一个提高自己能力的机会，我好好的抓住机会，努力做好每一步，完善每一步。自己的 C 语言知识和数据结构知识得到了巩固，编程能力也有了一定的提高。同时也学会了解 决问题的方法。总结起来，自己主要有以下几点体会：
1. 必须牢固掌握基础知识。由于 C 语言是大一所学知识，有所遗忘，且未掌握好上 学期所学的《数据结构》这门课，所以在实践之初感到棘手。不知如何下手，但在后来 的实习过程中自己通过看书和课外资料， 并请教其他同学， 慢慢地对 C 语言和数据结构 知识有所熟悉，这时才逐渐有了思路。所以今后一定要牢固掌握好专业基础知识。
2. 必须培养严谨的态度。自己在编程时经常因为一些小错误而导致出现问题，不够 认真细致，这给自己带来了许多麻烦。编程是一件十分严谨的事情，容不得马虎。所以 在今后自己一定要培养严谨的态度。我想这不仅是对于程序设计，做任何事都应如此。
3. 这次课程设计也让我充分认识到《数据结构》这门课的重要性。它给我们一个思
想和大纲，让我们在编程时容易找到思路，不至于无章可循。同时它也有广泛的实际应用。
在实践过程中，我遇到了许多困难，但都一一克服了。最终我圆满的完成此次课程设计，学到了很多东西。同时，程序还存在着一些缺陷，我会继续努力思考，完善程序，做到最好。
总的来说，本次课程设计，不仅我的知识面有所提高，另外我的综合素质也有所提高，这次课程设计为我以后更好的学习和使用 c 语言打下了基础。
六、附件
6.1 源程序
#include
#define Error printf #define QueueSize 30 typedef struct
{
char vexs[Max];
int edges[Max][Max];
int n,e;
}MGraph;/* 以邻接矩阵作为图的存储结构*/
int visited[Max]; /* 将visited[Max] 定义为全局变量并分配最大空间*/ typedef struct
{
int front;
int rear;
int count;
int data[QueueSize];
}CirQueue; /* 定义队列的数据结构*/
// 初始化队列
void InitQueue(CirQueue *Q)
{
Q->front=Q->rear=0;
Q->count=0;
}
// 队列空
int QueueEmpty(CirQueue *Q)
{
return Q->count=QueueSize; /* 返回队列的最大长度*/ }
// 队列满
int QueueFull(CirQueue *Q)
{
return Q->count==QueueSize; /* 返回队列的最大长度*/ }
// 进队
void EnQueue(CirQueue *Q,int x)
{
if(QueueFull(Q)) /* 队列满则出错*/
{
Error("Queue overflow");
}
else
Q->count++; /* 否则count++ ，将x 进队*/
Q->data[Q->rear]=x;
Q->rear=(Q->rear+1)%QueueSize;
}
}
// 出队
int DeQueue(CirQueue *Q)
{
int temp; /* 定义整型的变量*/
if(QueueEmpty(Q)) /* 若为真则出错*/
{ Error("Queue underflow");
}
else /* 为假则count-- ，将队员出队*/
{ temp=Q->data[Q->front]; /* 用temp 返回其值*/
Q->count--;
Q->front=(Q->front+1)%QueueSize; return temp; /* 返回出队元素值*/ }
}
// 建立一个图
void CreateMGraph(MGraph *G)
{
int i,j,k; /* 定义整型变量*/
char ch1,ch2; /* 定义字符型变量*/ printf("\n 请输入顶点数，边数(格式：3，4) :");
scanf("%d,%d",&(G->n),&(G->e)); /* 输入图的顶点数和边数*/
for(i=0;i
getchar();
printf("\n 请输入第%d个顶点序号",i+1);
scanf("%c",&(G->vexs[i])); /* 输入顶点的序号*/
}
for(i=0;i
{
for(j=0;j
{
G->edges[i][j]=0; /* 初始化矩阵*/
}
}
for(k=0;k
{
getchar();
printf("\n 请输入第%d条边的顶点序号(格式：i ，j ):",k+1);
scanf("%c,%c",&ch1,&ch2); /* 输入边的顶点序号*/
for(i=0;ch1!=G->vexs[i];i++);
for(j=0;ch2!=G->vexs[j];j++);
G->edges[i][j]=1; /* 有边则赋值为1*/
}
}
// 深度优先遍历递归
void DFSM(MGraph *G,int i)
{
int j;
printf("%c ",G->vexs[i]);
visited[i]=TRUE; /* 标记visited[i]*/
/* 依次优先搜索访问visited[i] 的每个邻接点*/
for(j=0;j
/* 若visited[i] 的一个有效邻接点visited[j] 未被访问过，则从visited[j]
出发进行递归调用*/ if(G->edges[i][j]==1&&!visited[j])
DFSM(G,j);
}
// 广度优先遍历递归
课程设计任务书 题目: 二叉排序树的建立及遍历的实现 初始条件： 理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法； 实践：计算机技术系实验室提供计算机及软件开发环境。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）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)
摘要 《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的： ?了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； ?初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； ?提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。 因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。 关键词：计算机；图；算法。
安徽理工大学 数据结构 课程设计说明书题目: 二叉树的遍历集成 院系：计算机科学与工程学院 专业班级： 学号： 学生姓名： 指导教师： 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,若二叉树为空,则头结
合肥学院 计算机科学与技术系 课程设计报告 2013～2014学年第二学期 课程数据结构与算法 课程设计名称图的深度优先遍历算法的实现 学生姓名陈琳 学号1204091022 专业班级软件工程 指导教师何立新 2014 年9 月 一：问题分析和任务定义 涉及到数据结构遍会涉及到对应存储方法的遍历问题。本次程序采用邻接表的存储方法，并且以深度优先实现遍历的过程得到其遍历序列。
深度优先遍历图的方法是，从图中某顶点v 出发： （1）访问顶点v ； （2）依次从v 的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v 有路径相通的顶点都被访问； （3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。 二：数据结构的选择和概要设计 设计流程如图： 图1 设计流程 利用一维数组创建邻接表，同时还需要一个一维数组来存储顶点信息。之后利用创建的邻接表来创建图，最后用深度优先的方法来实现遍历。 图 2 原始图 1.从0开始，首先找到0的关联顶点3 2.由3出发，找到1；由1出发，没有关联的顶点。 3.回到3，从3出发，找到2；由2出发，没有关联的顶点。 4.回到4，出4出发，找到1，因为1已经被访问过了，所以不访问。
所以最后顺序是0,3,1,2,4 三：详细设计和编码 1.创建邻接表和图 void CreateALGraph (ALGraph* G) //建立邻接表函数. { int i,j,k,s; char y; EdgeNode* p; //工作指针. printf("请输入图的顶点数n与边数e(以逗号做分隔符)：\n"); scanf("%d,%d",&(G->n),&(G->e)); scanf("%c",&y); //用y来接收回车符. for(s=0;s
课程设计任务书 2011 —2012 学年第一学期 电子与信息工程系计算机专业09计算机一班班级 课程设计名称：数据结构课程设计 设计题目：排序二叉树的遍历 完成期限：自2012 年 1 月 2 日至2012 年 1 月 6 日共 1 周 设计依据、要求及主要内容（可另加附页）： 一、设计目的 熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。 二、设计要求 （1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务； （2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩； （3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表； （4）认真编写课程设计报告。 三、设计内容 排序二叉树的遍历（用递归或非递归的方法都可以） 1)问题描述 输入树的各个结点，建立排序二叉树，对建立的排序二叉树进行层次、先序、中序和后序遍历并统计该二叉树中叶子结点的数目。 2)基本要求 (1)用菜单实现 (2)能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列和叶子结点的数目。 四、参考文献
1．王红梅．数据结构．清华大学出版社 2．王红梅．数据结构学习辅导与实验指导．清华大学出版社3．严蔚敏，吴伟民．数据结构（C语言版）．清华大学出版社 #include
数据结构实验报告 ———二叉树的建立及其遍历 一、实验目的 1、了解二叉树的建立的方法及其遍历的顺序，熟悉二叉树的三种遍历 2、检验输入的数据是否可以构成一颗二叉树 二、实验的描述和算法 1、实验描述 二叉树的建立首先要建立一个二叉链表的结构体，包含根节点和左右子树。因为耳熟的每一个左右子树又是一颗二叉树，所以可以用递归的方法来建立其左右子树。二叉树的遍历是一种把二叉树的每一个节点访问完并输出的过程，遍历时根结点与左右孩子的输出顺序构成了不同的遍历方法，这个过程需要按照不同的遍历的方法，先输出根结点还是先输出左右孩子，可以用选择语句实现。 2、算法 #include
{ scanf("%c",&e); if(e==' ') T=NULL; else { if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T->data=e; T->lchild=CreateBiTree(T->lchild); T->rchild=CreateBiTree(T->rchild); } return T; } /************************前序遍历***********************/ char PreOrderTraverse(BiTree T,char (* Visit)(char e)) { if(T) { if(Visit(T->data)) if(PreOrderTraverse(T->lchild,Visit)) if(PreOrderTraverse(T->rchild,Visit)) return OK; return ERROR; } else return OK; } char Visit(char e) { printf("%5c",e); return OK; } main() {
人工智能课程报告 题目： 深 度 优 先 算 法 班级：XXXXXXXXXXX 学号：XXXXXXXXXXX 姓名：XXXXXXXXXXX
【摘要】结合生活中解决搜索问题所常用的思考方法与解题方法，从深度优先探讨了提高程序效率的适用技巧。 【关键词】1搜索顺序；2搜索对象；3搜索优化； 一、深度优先搜索的优化技巧 我们在做事情的时候，经常遇到这类问题——给出约束条件，求一种满足约束条件的方案，这类问题我们叫它“约束满足”问题。对于约束满足问题，我们通常可以从搜索的顺序和搜索的对象入手，进而提高程序的效率。 二、搜索的顺序及对象： 在解决约束满足问题的时候，问题给出的约束条件越强，对于搜索就越有利。之所以深度优先搜索的效率在很大程度上优于穷举，就是因为它在搜索过程中很好的利用了题目中的约束条件进行优化，达到提高程序效率的目的。 显然，在同样的一棵搜索树中，越在接近根接点的位置利用约束条件优化效果就越好。如何在搜索中最大化的利用题目的约束条件为我们提供剪枝的依据，是提高深度优先搜索效率的一个很重要的地方。而不同的搜索顺序和搜索对象就直接影响到我们对于题目约束条件的运用。 三、搜索特点 1.由于深度搜索过程中有保留已扩展节点，则不致于重复构造不必要的子树系统。 2.深度优先搜索并不是以最快的方式搜索到解，因为若目标节点在第i层的某处，必须等到该节点左边所有子树系统搜索完毕之后，才会访问到该节点，因此，搜索效率还取决于目标节点在解答树中的位置。
3.由于要存储所有已被扩展节点，所以需要的内存空间往往比较大。 4.深度优先搜索所求得的是仅仅是目前第一条从起点至目标节点的树枝路径，而不是所有通向目标节点的树枝节点的路径中最短的路径。 5.适用范围：适用于求解一条从初始节点至目标节点的可能路径的试题。若要存储所有解答路径，可以再建立其它空间，用来存储每个已求得的解。若要求得最优解，必须记下达到目前目标的路径和相应的路程值，并与前面已记录的值进行比较，保留其中最优解，等全部搜索完成后，把保留的最优解输出。 四、算法数据结构描述 深度优先搜索时，最关键的是结点扩展（ＯＰＥＮ）表的生成，它是一个栈，用于存放目前搜索到待扩展的结点，当结点到达深度界限或结点不能再扩展时，栈顶结点出栈，放入CLOSE表（存放已扩展节点），继续生成新的结点入栈OPEN 表，直到搜索到目标结点或OPEN栈空为止。 具体算法如下： ①把起始结点S放到非扩展结点OPEN表中(后进先出的堆栈)，如果此结点为一目标结点，则得到一个解。 ②如果OPEN为一空表，则搜索失败退出。 ③取OPEN表最前面(栈顶)的结点，并把它放入CLOSED的扩展结点表中，并冠以顺序编号ｎ。 ④如果结点ｎ的深度等于最大深度，则转向２。 ⑤否则，扩展结点ｎ，产生其全部子结点，把它们放入OPEN表的前头(入栈)，并配上指向ｎ的返回指针；如果没有后裔，则转向２。 ⑥如果后继结点中有任一个为目标结点，则求得一个解，成功退出；否则，转向２。
目录 一．选题背景 (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二叉树中序遍历示意图
#include "stdio.h" #include "stdlib.h" #define STACK_INIT_SIZE 100 //栈存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配增量 //------二叉树的存储结构表示------// typedef struct BiTNode{ int data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //-----顺序栈的存储结构表示------// typedef struct{ BiTree *top; BiTree *base; int stacksize; }SqStack; //*************************************************** //构造一个空栈s SqStack *InitStack(); //创建一颗二叉树 BiTree CreatBiTree(); //判断栈空 int StackEmpty(SqStack *S); //插入元素e为新的栈顶元素 void Push(SqStack *S,BiTree p); //若栈不为空，则删除s栈顶的元素e，将e插入到链表L中void Pop(SqStack *S,BiTree *q); //非递归先序遍历二叉树 void PreOrderTraverse(BiTree L); //非递归中序遍历二叉树 void InOrderTraverse(BiTree L); //非递归后序遍历二叉树 void PostOrderTraverse(BiTree L); //递归后序遍历二叉树 void PostOrder(BiTree bt); //递归中序遍历二叉树 void InOrder(BiTree bt); //递归先序遍历二叉树 void PreOrder(BiTree bt); //***************************************************
##大学 数据结构课程设计报告题目：图的遍历和生成树求解 院（系）：计算机工程学院 学生: 班级：学号: 起迄日期: 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
数据结构程序设计报告 学院： 班级： 学号： 姓名：
实验名称：二叉树的建立与遍历 一、实验目的： 1.掌握二叉树的二叉链表存储结构； 2.掌握二叉树创建方法； 3.掌握二叉树的先序、中序、后序的递归实现方法。 二、实验内容和要求： 创建二叉树，分别对该二叉树进行先序、中序、后序遍历，并输出遍历结果。 三、叉树的建立与遍历代码如下： #include
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;
二叉树的建立和遍历的实验报告 篇一：二叉树的建立及遍历实验报告 实验三：二叉树的建立及遍历 【实验目的】 （1）掌握利用先序序列建立二叉树的二叉链表的过程。 （2）掌握二叉树的先序、中序和后序遍历算法。 【实验内容】 1. 编写程序，实现二叉树的建立，并实现先序、中序和后序遍历。 如：输入先序序列abc###de###，则建立如下图所示的二叉树。 并显示其先序序列为：abcde 中序序列为：cbaed 后序序列为：cbeda 【实验步骤】 1.打开VC++。 2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。 3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。
4．写好代码 5．编译－＞链接－＞调试 #include #include #define OK 1 #define OVERFLOW -2 typedef int Status; typedef char TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; }BiTNode,*BiTree; Status CreateBiTree(BiTree &T) { TElemType ch; scanf("%c",&ch); if (ch=='#') T= NULL; else { if (!(T = (BiTNode *)malloc(sizeof(BiTNode))))
中南大学 课程设计报告 题目数据结构课程设计学生姓名 指导教师漆华妹 学院信息科学与工程学院专业班级 学号 完成时间 2011年07月
目录 第一章、需求分析 (2) 第二章、概要设计 (2) 2.1设定图的抽象数据类型 (2) 2.2设定队列的抽象数据类型 (3) 2.3本程序包含的功能模块 (3) 第三章、详细设计 (3) 3.1顶点、边和图的类型 (6) 3.2队列类型 (8) 3.3主程序和其他伪码算法 (9) 第四章、调试分析 (9) 第五章、用户手册 (9) 第六章、测试结果 (10) 第七章、心得体会 (10) 附：源程序代码 (11)
图遍历的演示 题目:试设计一个程序,演示在连通的无向图上访问全部结点的操作 第一章、需求分析 1、以邻接多重表为存储结构； 2、实现连通和非连通的无向图的深度优先和广度优先遍历； 3、要求利用栈实现无向图的深度优先遍历； 4、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和生成树的边集； 5、用凹入表打印生成树； 6、求出从一个结点到另外一个结点，但不经过另外一个指定结点的所有简单路径；6、本程序用C语言编写，在C-Free3.5环境下通过。 第二章、概要设计 1、设定图的抽象数据类型: ADT Graph{ 数据对象V:V是具有相同特性的数据元素的集合,称为点集. 数据关系R: R={VR} VR={(v,w)|v,w属于V,(v,w)表示v和w之间存在的路径} 基本操作P: CreatGraph(&G,V,VR) 初始条件:V是图的顶点集,VR是图中弧的集合. 操作结果:按V和VR是定义构造图G. DestroyGraph(&G) 初始条件:图G存在 操作结果:销毁图G LocateVex(G,u) 初始条件: 图G存在,u和G中顶点有相同的特征 操作结果:若图G中存在顶点u,则返回该顶点在图中的位置;否则返回其他信息GetVex(G,v) 初始条件: 图G存在,v是G中顶点 操作结果:返回v的值 FirstAjvex(G,v) 初始条件: 图G存在,v是G中顶点 操作结果:返回v的第一个邻接顶点,若顶在图中没有邻接顶点,则返回为空 NextAjvex(G,v,w) 初始条件: 图G存在,v是G中顶点,w是v的邻接顶点 操作结果:返回v的下一个邻接顶点,若w是v的最后一个邻接顶点,则返回空DeleteVexx(&G,v) 初始条件: 图G存在,v是G中顶点 操作结果:删除顶点v已经其相关的弧 DFSTraverse(G,visit()) 初始条件: 图G存在,visit的顶点的应用函数
学号 数据结构课程设计 设计说明书 排序二叉树的遍历 起止日期：2011 年12月12日至2011 年12月16日 学生姓名 班级 成绩 指导教师(签字) 电子与信息工程系 2011年12月16日
天津城市建设学院 课程设计任务书 2011 —2012 学年第二学期 电子与信息工程系软件工程专业班级 课程设计名称：数据结构课程设计 设计题目：排序二叉树的遍历 完成期限：自2011 年12月12 日至2011 年12月16 日共 1 周 设计依据、要求及主要内容（可另加附页）： 一、设计目的 熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。 二、设计要求 （1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务； （2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩； （3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表； （4）认真编写课程设计报告。 三、设计内容 排序二叉树的遍历（用递归或非递归的方法都可以） 1)问题描述 输入树的各个结点，建立排序二叉树，对建立的排序二叉树进行层次、先序、中序和后序遍历并统计该二叉树中叶子结点的数目。 2)基本要求 (1)用菜单实现
(2)能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列和叶子结点的数目。 四、参考文献 1．王红梅．数据结构．清华大学出版社 2．王红梅．数据结构学习辅导与实验指导．清华大学出版社 3．严蔚敏，吴伟民．数据结构（C语言版）．清华大学出版社 指导教师（签字）： 教研室主任（签字）： 批准日期： 2011 年 12 月 17 日 主要内容： 一、需求分析： 输入树的各个结点，建立排序二叉树，对建立的排序二叉树进行层次、先序、中序和后序遍历并统计该二叉树中叶子结点的数目。 我自己的思想：首先设想把源程序分成头文件，调用和主函数三部分。在头文件中申明类和定义结构体，把先序，中序，后序，层次和叶子节点数的函数定义在类中。然后在调用文件中，把几个函数的实现定义写在里面。最后在主函数中把输出结果以菜单的样式输出来的方式写完主函数程序。实现的过程是先想好自己要输入的是什么，然后通过输入节点制，判断其是否是满足前序遍历，满足则可以实现下后面的功能。 二、问题求解： 现实中的问题：给同学排队问题。 层次是从头开始每一层一层的排，然后分别记号码。 前序是先从最上面的那一个开始往左手边开始排，排之前先计算好人数，然后开始排，排玩左边排右边。 中序是先从最左边开始，然后左斜上角，然后右下角，再左斜上角，直到最上层为止，然后安这个顺序继续排右边的。 后序是先从最左边开始的，左边的一次排过来，然后直接排右边的，也是安依次的顺序，最后才是最上层的。
图的操作 一、问题描述 图是一种较线性表和树更为复杂的数据结构。在图形结构中，节点间的关系可以是任意的，图中任意两个数据元素之间都可以相关。由此，图的应用极为广泛。现在邻接矩阵和邻接表的存储结构下，完成图的深度、广度遍历。 二、基本要求 1、选择合适的存储结构完成图的建立； 2、建立图的邻接矩阵，能按矩阵方式输出图，并在此基础上，完成图的深度和广度遍历，输出遍历序列； 3、建立图的邻接表，并在此基础上，完成图的深度和广度遍历，输出遍历序列； 三、测试数据 四、算法思想 1、邻接矩阵 顶点向量的存储。用两个数组分别存储数据（定点）的信息和数据元素之间的关系（边或弧）的信息。 2、邻接表 邻接表是图的一种链式存储结构。在邻接表中，对图中每个定点建立一个单链表，第i 个单链表中的节点表示依附于定点vi的边。每个节点由3个域组成，其中邻接点域（adjvex）指示与定点vi邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的节点；数据域（info）存储和边或弧相关的信息，如权值等。每个链表上附设一个头节点。在表头节点中，
除了设有链域（firstarc）指向链表中第一个节点之外，还设有存储定点vi的名或其他有关信息的数据域（data）。 3、图的深度遍历 深度优先搜索遍历类似于树的先根遍历，是树的先跟遍历的推广。假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，甚至图中所有和v相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 4、图的广度遍历 广度优先遍历类似于树的按层次遍历过程。假设从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先与“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个 曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 五、模块划分 一、基于邻接矩阵的深广度遍历 1．Status InitQueue(LinkQueue *Q) 根据已知Q初始化队列 2．Status QueueEmpty (LinkQueue Q) 判断队列是否为空 3．Status EnQueue(LinkQueue *Q, QElemType e) 将e压入队尾 4．Status DeQueue(LinkQueue *Q, QElemType *e) 取队头元素e 5．int LocateVex(MGraph G,VertexType v) 定位定点v 6．void CreateGraph(MGraph *G) 建立无向图的邻接矩阵 7．void PrintGraph(MGraph G) 输出邻接矩阵的无向图 8．int FirstAdjVex(MGraph G,int v) 第一个邻接点的定位 9．int NextAdjVex(MGraph G,int v,int w) 查找下一个邻接点
用C语言编写二叉树的建立与遍历 #include "stdio.h" #include "string.h" #define NULL 0 typedef struct BiTNode{ char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; BiTree Create(BiTree T){ char ch; ch=getchar(); if(ch=='#') T=NULL; else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) printf("Error!"); T->data=ch; T->lchild=Create(T->lchild); T->rchild=Create(T->rchild); } return T;
} void Preorder(BiTree T){ if(T){ printf("%c",T->data); Preorder(T->lchild); Preorder(T->rchild); } } int Sumleaf(BiTree T){ int sum=0,m,n; if(T){ if((!T->lchild)&&(!T->rchild)) sum++; m=Sumleaf(T->lchild); sum+=m; n=Sumleaf(T->rchild); sum+=n; } return sum; } void zhongxu(BiTree T){ if(T){
zhongxu(T->lchild); printf("%c",T->data); zhongxu(T->rchild); } } void houxu(BiTree T){ if(T){ houxu(T->lchild); houxu(T->rchild); printf("%c",T->data); } } int Depth(BiTree T){ int dep=0,depl,depr; if(!T) dep=0; else{ depl=Depth(T->lchild); depr=Depth(T->rchild); dep=1+(depl>depr?depl:depr); } return dep; }
《数据结构》课程设计题目 课程设计题一：学生成绩管理系统 设计目的： 1 掌握线性链表的建立。 2 掌握线性链表的基本操作。 3 掌握查找的基本算法。 设计内容： 利用线性链表实现学生成绩管理系统，具体功能：输入、输出、插入、删除、查找、追加、读入、显示、保存、拷贝、排序、索引、分类合计、退出，并能在屏幕上输出操作前后的结果。 设计要求： 1 写出系统需求分析,并建模。 2 编程实现,界面友好。 3 输出操作前后的结果。 课程设计题二：停车场管理系统 设计目的： 1 掌握栈和队列的建立。 2 掌握栈和队列的基本操作。 3 深入了解栈和队列的特性,以便在解决实际问题中灵活运用它们。 4 加深对栈和队列的理解和认识。 设计内容： 设有一个可以停放n辆汽车的狭长停车场,它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放(最先到达的第一辆车放在停车场的最里面)。如果停车场已放满n辆车,则后来的车辆只能在停车场大门外的便道上等待,一旦停车场内有车开走,则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走,在他之后进入停车场的车都必须先退出停车场为它让路,待其开出停车场后,这些车辆在依原来的次序进场。每辆车在离开停车场时,都应依据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去,允许其离去,不收停车费,并且仍然保持在便道上等待的车辆的次序。编制一程序模拟该停车场的管理。 设计要求： 1 以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入的输入数据序列进行模拟管理。 2 每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。 3 对每一组输入数据进行操作后的输出信息为：若是车辆到达,则输出汽车在停车场或便道上的停车位置；若是车辆离去,则输出汽车在停车场内停留的时间和应交纳的费用(在便道上停留的时间不收费，功能可自己添加)。 课程设计题三：约瑟夫(Joseph)环 设计目的：
二叉树遍历--教学设计 所属学科：数据库 专业：计算机(相关学科) 课程：数据结构 适用对象：大二上学期 本课所讲解的内容为二叉树遍历的三种基本方法和一种新颖的方法，所属学科为数据结构与算法。数据结构与算法是计算机专业的重要基础课，也是非计算机专业学生在大学生计算机等级考试中的课程之一，是一门集技术性、理论性和实践性于一体的课程。故本微课结合该课程特点，合理分配知识结构及节奏，并融充分合多媒体技术，算法描述清晰，展现内容丰富，适合课堂教学，也便于自学，可作为高等院校计算机专业和其他相关专业的参考资料，也可供参加全国普通高校非计算机专业大学生计算机等级考试（CCT）的学生及计算机爱好者学习和参考。 教学思想： 本课内容没有太过繁琐的语言，而是采用与多媒体充分融合的方式，并采用部分flash动画讲解遍历方法，生动、简洁、丰富地展现教学内容，教学思路清晰。提高了教学效率和教学质量，使学生在单位时间内能够学到更多的知识，更大幅度地提高学生各方面的能力，从而使学生获得良好的发展。 课程设计思路： 遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。由于访问结点所做的操作依赖于具体的应用问题，所以我们对所讲解的问题分别举了一个容易和较难的例子，并配上一个难度适中的启发式的习题思考，在讲解过程中让学生充分理解，并学会运用不同的遍历方式解决问题，最后加上顺口溜式的总结，使学生对知识点更加融会贯通。 教学特色： 1、教学思路清晰。对于遍历的讲解是按照遍历概念、实例、动画演示、算法和 总结的步骤进行的，效果较好。 2、在视频讲解中，语言生动而富于亲和力，表达多样，激发学生兴趣。通过改 变教学内容的展现形式，更具独到趣味，激发学生内外动力来实现。 3、在课件中，我们的幻灯片布局简洁，动画紧随讲解节奏的推进而随时跟进， 生动形象，而又清晰明了地将所讲的知识点呈现出来，充分运用了现代多媒体教学方式的优点。 4、在PPT中我们插入了Flash动画，让遍历方法更加清晰明了，让学习者更容