内容发布更新时间 : 2024/9/26 5:23:11星期一 下面是文章的全部内容请认真阅读。

上海应用技术学院

《数据结构与算法》课程设计报告

院 系： *学院 专 业： ******

班 级： 091****11 姓 名： 公孙胜天 学 号： 091**** 指导老师： 何****

一、 课程设计目的

培养学生用学到的书本知识解决实际问题的能力；培养实际工作所需要的动手能力；培养学生以科学理论和工程上能力的技术，规范地开发大型、复杂、高

质量的应用软件和系统软件具有关键性作用；通过课程设计的实践，学生可以在程序设计方法、上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

二、 课程设计要求

1)学生必须仔细阅读《数据结构与算法》课程设计方案，认真主动完成课程设计的要求。有问题及时主动通过各种方式与教师联系沟通。

2)学生要发挥自主学习能力，充分利用时间，安排好课程设计的时间计划，并在课程设计过程中不断检测自己的计划完成情况，及时向教师汇报。

3)课程设计按照教学计划需要两周时间完成，两周中每天至少要上六小时的上机来调试C或C++语言设计的程序，总共至少要上机调试程序30小时。属教师安排上机时间学生不得缺席。

三、 课程设计内容

1、 建立二叉树，层序、先序、中序、后序遍历（ 用递归或非递归的方法都可以）**

任务：

要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数；

2、 各种排序

任务：用程序实现插入法排序、选择法排序、起泡法改进算法排序； 利用插入排序、选择法排序和冒泡法的改进算法,将用户随机输入的一列数按递增的顺序排好。

输入的数据形式为任何一个正整数，大小不限。 输出的形式：数字大小逐个递增的数列。

四、 课程设计细节

（一）第一题设计：

a)需求分析：

本程序是用链式存储结构来存储二叉树并进行一系列的算法，且结点内容的数据类型为字符型。

本程序用C-Free 5编写，可以实现各种二叉树的遍历。包括层序遍历、先序遍历、中序遍历、后序遍历的非递归算法。

根据题目知，程序主要是根据给定二叉树的四种遍历结果：

(1)先创建二叉树：按括号表示法输入二叉树字符串，然后构造二叉链表表示的二叉树。

(2)设计算法：层序遍历、先序遍历、中序遍历、后序遍历. 在做到层序遍历时，应注意算法如下：根结点入队，队头元素出队，左孩子不为空入队右孩子不为空入队的顺序进行。

(3)设计main()函数调用以上步骤实现相关功能。 根据题目要求，我们主要设计了以下几个函数： （1）typedef struct node

定义一个用链式存储结构存储的二叉树，其中包括左孩子和右孩子以及数据元素的内容。和单链表类似，一个二叉链表由头指针唯一确定，若二叉树为空，则头指针指向空。并且结点内容的数据类型为字符型。 （2）BTNode *CreateBTNode(BTNode *&b)

此函数的功能是构建二叉树。从键盘上按括号表示法输入二叉树字符串构造二叉链表表示的二叉树T。

（3）void LevelOrder(BTNode *b)

此函数的功能是用非递归的方法实现二叉树的层序遍历算法。调用此函数可以获得二叉树的非递归的中序遍历的结果。 （4）void PreOrder(BTNode *b)

此函数的功能是用非递归的方法实现二叉树的先序遍历算法。调用此函数可以获得二叉树的非递归的先序遍历的结果。 （5）void InOrder(BTNode *b)

此函数的功能是用非递归的方法实现二叉树的中序遍历算法。调用此函数可以获得二叉树的非递归的中序遍历的结果。 （6）void PostOrder(BTNode *b)

此函数的功能是用非递归的方法实现二叉树的后序遍历算法。调用此函数可以获得二叉树的非递归的后序遍历的结果。 （7）void DispBTNode(BTNode *b)

此函数的功能是先序输出二叉树字符串。

b)概要设计：

我们的算法设计如下：

一、非递归遍历算法

用指针数组stack[]代替栈，添加一个top来表示进栈出栈的操作，同时还可以判断stack是否为空。 1、 先序遍历

每次将节点压入栈，然后弹出，压右子树，再压入左子树，在遍历过

程中，遍历序列的右节点依次被存入栈，左节点逐次被访问。 2、 中序遍历

先寻找最左边的树叶输出（寻找过程中每个根节点都要入栈），然后依次出栈，判断根节点的右孩子是否有左孩子（即每次都要寻找每个根的最左孩子）知道top=-1,即栈空。 3、 后序遍历

设置一标志，以判断节点是否访问过。先寻找最左边的树叶，但不输出