当前位置：文档之家› 图的遍历_课程设计

图的遍历_课程设计

图的遍历课程设计

题目图的遍历

教学院计算机

专业

班级

姓名

指导教师

201X 年12 月31 日

课程设计任务书

2010 ～2011 学年第1 学期

学生姓名：专业班级：

指导教师：工作部门：

一、课程设计题目

图的遍历

二、课程设计内容（含技术指标）

1．显示图的邻接矩阵, 图的邻接表, 深度优先遍历, 广度优先遍历, 最小生成树PRIM算法, 最小生成树KRUSCAL算法,图的连通分量。

2．当用户选择的功能错误时，系统会输出相应的提示。

3．通过图操作的实现，把一些实际生活中的具体的事物抽象出来

三、进度安排

1．初步完成总体设计，搭好框架；

2．完成最低要求：两种必须都要实现，写出画图的思路；

3．进一步要求：画出图的结构，有兴趣的同学可以进一步改进图的效果。

四、基本要求

1．界面友好，函数功能要划分好

2．程序要加必要的注释

3．要提供程序测试方案

一概述 (1)

1.问题描述 (1)

2.系统分析 (1)

3.课程设计（论文）进程安排 (1)

二.总体设计方案 (2)

1．整体设计思路 (2)

2．算法的整体思路 (3)

3．工作内容 (3)

三详细设计 (4)

1.详细设计思路及算法 (4)

2.程序流程图 (11)

四程序的调试与运行结果说明 (12)

１.运行结果 (12)

五．课程设计总结 (15)

参考文献 (16)

附录 A 原程序清单 (16)

数据结构课程设计成绩评定表 (30)

一概述

1.问题描述

1)函数功能要划分好

2)总体设计应画流程图

3)程序要加必要的注释

4)要提供程序测试方案

2.系统分析

1)掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力

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

能

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

4)训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备

的科学的工作方法和作风

3.课程设计（论文）进程安排

二.总体设计方案

1．整体设计思路

图的邻接矩阵：

对于一个具有n个顶点的图，可以使用n*n的矩阵（二维数组）来表示它们间的邻接关系。

图的邻接表：

邻接表由表头结点和表结点两部分组成，其中图中每个顶点均对应一个存储在数组中的表头结点。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。

深度优先遍历的递归算法思想：

假定以图中某个顶点V i为出发点，首先访问出发点，然后选择一个V i的未访问过的邻接点V j，以V j为新的出发点继续进行深度优先搜索，直至图中所有顶点都被访问过。

1)访问结点V并标记结点V为已访问；

2)查找结点V的第一个邻接结点W；

3)若结点W的临界结点W存在，则继续执行，否则算法结束；

4)若结点W尚未被访问，则递归访问结点W；

5)查找结点V的W临界结点的下一个临界结点W ，转到步骤（3）。

广度优先遍历算法：

从图的某一顶点V i出发，访问此顶点后，依次访问V i的各个未曾访问过的邻接点，然后分别从这些邻接点出发，直至图中所有已有已被访问的顶点的邻接点都被访问到。

1)访问初始结点V并标记结点V为已访问；

2)结点V入队列；

3)当队列非空时则继续执行，否则算法结束；

4)出队列取得队头结点U；

5)查找结点U的第一个邻接结点W；

6)若结点U的邻接结点W不存在，则转到步骤（3），否则循环执行下列步骤：

a)（6.1）若结点W尚未被访问，则访问结点W并标记结点W

为已访问；

b)（6.2）结点W入队；

c)（6.3）查找结点U的W邻接结点的下一个邻接结点W，转到

步骤（6）。

普利姆算法思想：

令集合U的初值为U={u0}，集合T的初值为T={}。从所有结点u属于U和结点v属于V\U的带权边中选出具有最小权值的边（u，v），将结点v加入集合U中，将边（u，v）加入集合T中。如此不断反复，当U=V时，最小生成树便构造完毕。

克鲁斯卡尔算法思想：

设无向连通带权图G=(V,E)，其中V为结点的集合，E为边的集合。设带权图G 的最小生成树T由结点集合和边的集合构成，其初值为T=(v,{}),即初始时最小生成树T只由带权图G中的结点集合组成，各结点之间没有一条边。这样，最小生成树T中的各个结点各自构成一个连通分量。然后，按照边的权值递增的顺序考察带权图G中边集合E的各条边，若被考察的边的两个结点属于T的两个不同的连通分量，则将此边加入懂啊最小生成树T中，同时，把两个连通分量连接为一个连通分量；若被考察的边的两个结点属于T的同一个连通分量，则将此边舍去。如此下去，当T中的连通分量个数为1时，T中的该连通分量即为带权图G的一棵最小生成树。

连通分量：

非连通图的每一个连通部分。

2．算法的整体思路

本系统能分别用邻接矩阵存储结构和邻接表存储结构构造无向图，然后在此无向图中能实现深度优先遍历，广度优先遍历，最小生成树和连通分量的算法。

3．工作内容

1.显示图的邻接矩阵, 图的邻接表, 深度优先遍历, 广度优先遍历, 最小生成树PRIM算法, 最小生成树KRUSCAL算法,图的连通分量。

2.当用户选择的功能错误时，系统会输出相应的提示。

3.通过图操作的实现，把一些实际生活中的具体的事物抽象出来。

三详细设计1.详细设计思路及算法

图1-1 无向图1.程序中所用变量的定义:

#include

using namespace std;

#define int_max 10000

#define inf 9999

#define max 20

2.邻接矩阵的定义：

typedef struct ArcCell

{

int adj;

char *info;

}ArcCell,AdjMatrix[20][20];

typedef struct {

char vexs[20]; AdjMatrix arcs; int vexnum,arcnum; }MGraph_L;

A 0 50 60

0 0 0 0 B 50

0 0 65 40 0 0 C 60 0 0 52 0 0 45 D 0 65 52 0 50 30 0 E 0 40 0 50 0 70 0 F 0 0 0 30 70 0 80 G 0 0 45 0 0 80 0

图1-2 邻接矩阵

3.邻接表：

表1-1 邻接表

4.深度优先遍历：

void adjprint(algraph gra)

5.广度优先遍历：

void bfstra(algraph gra)

6.最小生成树PRIM算法：

7.最小生成树KRUSCAL算法：

2.程序流程图

四程序的调试与运行结果说明１.运行结果

图2-1 输入顶点数

图2-2 输入权值

无向图创建成功

图2-3 菜单

图2-4 邻接矩阵

图2-5 邻接表

图2-6 深广度优先遍历

图2-7 最小生成树

图2-8 连通分量

五．课程设计总结

课程设计是把我们所学的理论知识进行系统的总结并应用于实践的良好机会，有利于加强我们用知识理论来分析实际问题的能力，进而加强了我们对知识认识的实践度，巩固了我们的理论知识，深化了对知识的认识，并为走向社会打下一个良好的基础。

对于我们学生来讲，此次课程设计是为了让我们训练自己的实际设计能力，通过设计实践，去真正获得此项目管理和团队协作等方面的基本训练和工作经验。通过课程设计的一系列训练，我们能提高如何综合运用所学知识解决实际问题的能力，以及获得此项目管理和团队协作等等众多方面的具体经验，增强对相关课程具体内容的理解和掌握能力，培养对整体课程知识综合运用和融会贯通能力。

通过这近一个星期的数据结构课程设计实践，我学到了很多东西。本次课程设计对我来说正是一个提高自己能力的机会，我好好的抓住机会，努力做好每一步，完善每一步。自己的C语言知识和数据结构知识得到了巩固，编程能力也有了一定的提高。同时也学会了解决问题的方法。

此次课程设计也让我认识到必须培养严谨的态度。自己在编程时经常因为一些类似于“少了分号”的小错误而导致错误，不够认真细致，这给自己带来了许多麻烦。编程是一件十分严谨的事情，容不得马虎。所以在今后自己一定要培养严谨的态度。我想这不仅是对于程序设计，做任何事都应如此。

在实践过程中，我和组员分工合作，勇于提出问题，解决难题，在实践中，我遇到了许多困难，但都一一克服了。最终我圆满的完成此次课程设计，学到了很多东西。同时，程序还存在着一些缺陷，就是不能输出原图，存在一些局限性，不过我会继续努力思考，完善程序，做到最好。

此次试验，老师对我的指导是至关重要的，在此我非常感谢老师，从她那我学到了很多有关c语言的知识，为以后的学习打下了一定的基础。

总的来说，本次课程设计，不仅我的知识面有所提高，另外我的综合素质也有所提高，，比如说：团队精神、提问能力、思考能力等等。这次课程设计为我以后更好的学习和使用c语言打下了基础。

参考文献

[1]数据结构—使用C语言（第3版）朱战立编，西安交通大学出版社。

[2] Visual C++程序设计──基础与实例分析.北京：清华大学出版社，2004

附录A 原程序清单

#include

using namespace std;

#define int_max 10000

#define inf 9999

#define max 20

//…………………………………………邻接矩阵定义……………………

typedef struct ArcCell

{

int adj;

char *info;

}ArcCell,AdjMatrix[20][20];

typedef struct

{

char vexs[20];

AdjMatrix arcs;

int vexnum,arcnum;

}MGraph_L;

//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

int localvex(MGraph_L G,char v)//返回V的位置

{

int i=0;

while(G.vexs[i]!=v)

{

++i;

}

return i;

}

int creatMGraph_L(MGraph_L &G)//创建图用邻接矩阵表示

{

char v1,v2;

int i,j,w;

cout<<"…………创建无向图…………"<

cin>>G.vexnum>>G.arcnum;

for(i=0;i!=G.vexnum;++i)

{

cout<<"输入顶点"<

cin>>G.vexs[i];

}

for(i=0;i!=G.vexnum;++i)

for(j=0;j!=G.vexnum;++j)

{

G.arcs[i][j].adj=int_max;

G.arcs[i][j].info=NULL;

}

for(int k=0;k!=G.arcnum;++k)

{

cout<<"输入一条边依附的顶点和权:(a b 3)不包括()"<

cin>>v1>>v2>>w;//输入一条边依附的两点及权值

i=localvex(G,v1);//确定顶点V1和V2在图中的位置

j=localvex(G,v2);

G.arcs[i][j].adj=w;

G.arcs[j][i].adj=w;

}

cout<<"图G邻接矩阵创建成功！"<

return G.vexnum;

}

void ljjzprint(MGraph_L G)

{

int i,j;

for(i=0;i!=G.vexnum;++i)

{

for(j=0;j!=G.vexnum;++j)

cout<

}

int visited[max];//访问标记

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

课程设计任务书题目: 二叉排序树的建立及遍历的实现初始条件：理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法；实践：计算机技术系实验室提供计算机及软件开发环境。要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）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)

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

列车运行图说明书

铁路行车组织课程设计班级：学号：姓名：指导老师：设计时间：前言《城市轨道交通行车组织》课程是城市轨道交通运营专业的必修课程，通过对于该课程知识的学习，掌握行车闭塞法、正常/非正常情况的行车组织、列车运行图等。而本课程设计以列车运行图设计为主，学习列车运行图是学习行车组织的重要任务之一。通过对列车运行图的学习与理解，设计出与要求相关的列车运行图，掌握学习列车运行图的技巧，锻炼我们的思维能力，提高画图的能力。在设计的过程之中，我复习了之前的知识点，到图书馆收集一些关于列车运行图的参考资料，在老师和同学的指导帮助之下，顺利完成了本课程设计。由于本人的水平有限，说明书与设计图纸中出现的错误，或不足之处，还望见谅。也恳请老师指正。设计者：

2012年11月14日目录前言 (1) 目录 (2) 原始资料 (3) 甲~乙区段区间通过能力 (4) 编制甲~乙区段列车运行放行方案图 (5) 总结 (8) 附件 (9) 列车运行图课程设计一、原始资料 1、甲—乙区段线路示意图如下： 2、区段线路设备技术情况： 1)闭塞：单线半自动闭塞 2)各站均不具备相对方向同时接车和同方向同时发接列车条件 3、区段行车量：

1)特快旅客列车一对：T201次甲站开14：00 T202次乙站开15：40 2)快速旅客列车两队：K359次甲站开09：00 K360次乙站开08：20 K401次甲站开14：40 K402次乙站开16：00 3)区段货物列车8对，列车车次由30001/2编起 4、计算各种通过能力时，扣除系数ε客=1.3，r备=0.2，k=0.85 5、列车运行图时间段为6:00~18:00 二、计算甲~乙区段区间通过能力 1、选择限制区间的列车放行方案最大区间确定的计算：各列车在各个区间的运行时分总和：甲~A：8+8+11+10=37 A~B ：8+8+12+11=39 B~C：8+9+13+14=44 C~D：10+10+11+12=43 D~乙：8+9+11+12=40 所以选择最大区间为B~C区间，列车放行方案共四种，如下图所示：

课程设计二叉树

安徽理工大学数据结构课程设计说明书题目: 二叉树的遍历集成院系：计算机科学与工程学院专业班级：学号：学生姓名：指导教师： 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;sn;s++) { printf("请输入下标为%d的顶点的元素:\n",s); scanf("%c",&(G->adjlist[s].vertex)); scanf("%c",&y); //用y来接收回车符.当后面要输入的是和单个字符有关的数据时候要存贮回车符，以免回车符被误接收。 G->adjlist[s].firstedge=NULL; } printf("请分别输入该图的%d条弧\n",G->e); for(k=0;ke;k++) { printf("请输入第%d条弧的起点和终点（起点下标,终点下标）:\n",(k+1)); scanf("%d,%d",&i,&j); p=(EdgeNode*)malloc(sizeof(EdgeNode)); p->adjvex=j; p->next=G->adjlist[i].firstedge; G->adjlist[i].firstedge=p; } } 2.深度优先遍历 void DFS(ALGraph* G,int v) //深度优先遍历 { EdgeNode* p;

列车运行图课程设计报告

单线区段列车运行图分析实验报告姓名黎文皓学号 1104121013 专业班级运输1203 指导教师邓连波中南大学交通运输工程学院 2015年 6月

一、通过能力计算由表可得，T 周调整后最大为36min 。区间现有通过能力为： a)当不考虑固定作业时间和有效度系数时 n =144036 =40(对) n 货非=n ?ε客n 客?(ε摘挂?1)n 摘挂=40?1.2×5?(1.6?1)×2 =32.8≈33(对) b)当考虑固定时间而不考虑有效度系数时 n =1440?9036 =37.5≈38(对) n 货非=n ?ε客n 客?(ε摘挂?1)n 摘挂=38?1.2×5?(1.6?1)×2 =30.8≈31(对)

c)当同时考虑固定作业占用时间和有效度系数时 n =(1440?T 固)×d 有效 T 周 =(1440?90)×0.8936 =33.375≈33(对) n 货非=n ?ε客n 客?(ε摘挂?1)n 摘挂=33?1.2×5?(1.6?1)×2 =25.8≈26(对) 二、列车运行图技术指标统计及分析 1、数量指标（1）按列车性质分类的旅客列车及货物列车对数（2）旅客列车及货物列车走行公里 a) A-B 区段长度为：13+14+12+10+12+13+15+14=103km b) 旅客列车走行公里：103×10=1030km c) 货物列车走行公里：103×26=2678km （包括摘挂）（3）由各始发站发出的各种旅客列车数和货物列车对数 A 和B 发出的各种旅客列车数和货物列车数分别为5对、13对。（4）机车台数本设计中共用机车台数7台

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

课程设计任务书 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()

人工智能深度优先算法课程设计报告

人工智能课程报告题目：深度优先算法班级：XXXXXXXXXXX 学号：XXXXXXXXXXX 姓名：XXXXXXXXXXX

【摘要】结合生活中解决搜索问题所常用的思考方法与解题方法，从深度优先探讨了提高程序效率的适用技巧。【关键词】1搜索顺序；2搜索对象；3搜索优化；一、深度优先搜索的优化技巧我们在做事情的时候，经常遇到这类问题——给出约束条件，求一种满足约束条件的方案，这类问题我们叫它“约束满足”问题。对于约束满足问题，我们通常可以从搜索的顺序和搜索的对象入手，进而提高程序的效率。二、搜索的顺序及对象：在解决约束满足问题的时候，问题给出的约束条件越强，对于搜索就越有利。之所以深度优先搜索的效率在很大程度上优于穷举，就是因为它在搜索过程中很好的利用了题目中的约束条件进行优化，达到提高程序效率的目的。显然，在同样的一棵搜索树中，越在接近根接点的位置利用约束条件优化效果就越好。如何在搜索中最大化的利用题目的约束条件为我们提供剪枝的依据，是提高深度优先搜索效率的一个很重要的地方。而不同的搜索顺序和搜索对象就直接影响到我们对于题目约束条件的运用。三、搜索特点 1.由于深度搜索过程中有保留已扩展节点，则不致于重复构造不必要的子树系统。 2.深度优先搜索并不是以最快的方式搜索到解，因为若目标节点在第i层的某处，必须等到该节点左边所有子树系统搜索完毕之后，才会访问到该节点，因此，搜索效率还取决于目标节点在解答树中的位置。

3.由于要存储所有已被扩展节点，所以需要的内存空间往往比较大。 4.深度优先搜索所求得的是仅仅是目前第一条从起点至目标节点的树枝路径，而不是所有通向目标节点的树枝节点的路径中最短的路径。 5.适用范围：适用于求解一条从初始节点至目标节点的可能路径的试题。若要存储所有解答路径，可以再建立其它空间，用来存储每个已求得的解。若要求得最优解，必须记下达到目前目标的路径和相应的路程值，并与前面已记录的值进行比较，保留其中最优解，等全部搜索完成后，把保留的最优解输出。四、算法数据结构描述深度优先搜索时，最关键的是结点扩展（ＯＰＥＮ）表的生成，它是一个栈，用于存放目前搜索到待扩展的结点，当结点到达深度界限或结点不能再扩展时，栈顶结点出栈，放入CLOSE表（存放已扩展节点），继续生成新的结点入栈OPEN 表，直到搜索到目标结点或OPEN栈空为止。具体算法如下： ①把起始结点S放到非扩展结点OPEN表中(后进先出的堆栈)，如果此结点为一目标结点，则得到一个解。 ②如果OPEN为一空表，则搜索失败退出。 ③取OPEN表最前面(栈顶)的结点，并把它放入CLOSED的扩展结点表中，并冠以顺序编号ｎ。 ④如果结点ｎ的深度等于最大深度，则转向２。 ⑤否则，扩展结点ｎ，产生其全部子结点，把它们放入OPEN表的前头(入栈)，并配上指向ｎ的返回指针；如果没有后裔，则转向２。 ⑥如果后继结点中有任一个为目标结点，则求得一个解，成功退出；否则，转向２。

西南交通大学铁路行车组织课程列车运行图课程设计范文

列车运行图课程设计任务书一. 资料 1. M-N 区段示意图下行技术站中间站 2. 区段技术特征 3.区段距离及运行时分 4. 车站间隔时间及列车起停附加时分 4min τ不＝ 2min τ会＝ 4m i n τ连＝（第一种类型） 2τ连＝（第二种类型）

客：1=起t 1=停t 货：2=起t 1=停t 5. 区段站中间的信、联、闭设备色灯信号、集中电气连锁、半自动闭塞 6. 客货列车行车量及旅客列车到发时刻（1）行车量旅客列车：T63/T64特快旅客列车一对 1511/1512次直通旅客快车一对 1517/1518管内旅客列车一对货物列车：直达列车3对直通列车9对区段列车4对摘挂列车1对（2）旅客列车到发时刻及停站时间 T63在M 站21：22出发，T64在N 站23：11出发，这两列车在区段各中间站均不停车。 1511次由M 站9：31出发，1512次由N 站15：39出发，在d 站停车5min ，其它中间站均通过。 1517次由M 站17：05出发，1518次由N 站6：16出发，在d 站停留5min 钟，其它中间站各停留2min 。 7. 中间技术站作业时分 d 站为下行货物列车技术作业需要停车站，每次停留时间10min t 技＝。 8. 机车在机务段和折返段所在站停留时间标准机车交路为肩回制，M 为基本段，N 为折返段。机车在M 站停留时间标准为110分钟，在N 为70分钟。旅客列车、摘挂列车单独交路。

9. M-N区段各中间站卸车数 10.M-N区段各中间站装车数 11. 排空方向罐车向上行方向排空。除罐车外，其它车种卸车后利用装车。不足空车由M 站提供。

二叉树的建立及其遍历实验报告

数据结构实验报告 ———二叉树的建立及其遍历一、实验目的 1、了解二叉树的建立的方法及其遍历的顺序，熟悉二叉树的三种遍历 2、检验输入的数据是否可以构成一颗二叉树二、实验的描述和算法 1、实验描述二叉树的建立首先要建立一个二叉链表的结构体，包含根节点和左右子树。因为耳熟的每一个左右子树又是一颗二叉树，所以可以用递归的方法来建立其左右子树。二叉树的遍历是一种把二叉树的每一个节点访问完并输出的过程，遍历时根结点与左右孩子的输出顺序构成了不同的遍历方法，这个过程需要按照不同的遍历的方法，先输出根结点还是先输出左右孩子，可以用选择语句实现。 2、算法 #include #include #define OVERFLOW 0 #define OK 1 #define ERROR 0 typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; BiTree CreateBiTree(BiTree T)

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

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

目录一．选题背景 (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二叉树中序遍历示意图

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

##大学数据结构课程设计报告题目：图的遍历和生成树求解院（系）：计算机工程学院学生: 班级：学号: 起迄日期: 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