数据结构的遍历课程设计与实现 本文关键词：遍历，数据结构，课程设计
数据结构的遍历课程设计与实现 本文简介：摘要:在数据结构课程学习中，实践很重要。实践分为验证性、设计性和和综合性实验。课程设计为综合性实验。验证性和设计性实验在整个实验教学中占比例较大，是针对课堂某章节教学内容的小型实验，由学生独立进行程序设计与上机实现；而综合性的课程设计更强调知识的整合，要求学生具备问题分析与求解能力，由小组合作完成，
数据结构的遍历课程设计与实现 本文内容：
摘要:在数据结构课程学习中，实践很重要。实践分为验证性、设计性和和综合性实验。课程设计为综合性实验。验证性和设计性实验在整个实验教学中占比例较大，是针对课堂某章节教学内容的小型实验，由学生独立进行程序设计与上机实现；而综合性的课程设计更强调知识的整合，要求学生具备问题分析与求解能力，由小组合作完成，可培养学生的团队合作能力。本文给出了树型结构的一个课程设计，对问题进行分析及实现，最后进行了测试，可为学生完成综合性数据结构实践提供参考。
关键词:数据结构；树；课程设计
1树形结构
1.1树的定义
[1]一棵有根树T，简称为树，可定义为n(n≥0)个结点的有限集合。当n=0时，T称为空树；否则，T是非空树，记作：其中，r是T的一个特殊结点，称为根(root);T1,T2,...,Tm是除r之外其他结点构成的互不相交的m(m≥0)个子集合。每个子集合也是一棵树，称为根的子树(subtree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。m称为r的分支数。树的定义是一个递归的定义。
1.2树的存储结构
树的主要存储结构有以下三种[2]：○1双亲表示法：用一组连续的空间来存储树中的结点，在保存每个结点的同时附设一个指示器来指示其双亲结点在表中的位置。○2孩子表示法把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表。n个结点共有n个孩子链表（叶子结点的孩子链表为空表），而n个结点的数据和n个孩子链表的头指针又组成一个顺序表。○3孩子兄弟表示法这种表示法又称为树的二叉表示法，或者二叉链表表示法，即以二叉链表作为树的存储结构。链表中每个结点设有两个链域，分别指向该结点的第一个孩子结点和下一个兄弟（右兄弟）结点。
2课程设计
2.1问题描述
给出某操作系统的目录和文件信息，编程将其以树状结构显示。输入的信息有两种，第一种为目录信息。目录下面可以存放文件或子目录，即目录结点可能存在孩子结点，若存在，其孩子结点信息要求在该目录信息的下一行给出，孩子结点信息要求用圆括号“（）”括起。目录的输入格式为：[目录名称]大小。第二种是文件信息。输入格式为：文件名称大小。目录名或文件名为长度小于等于10的字符串，且目录名或文件名不能包含‘（’，‘）’和‘*’。目录的“大小”都表示为1，文件的“大小”输入值为文件的实际大小。编程实现如下输出，要求是有层次结构的树，每层结点（目录结点或文件结点）都要比上一层结点多缩进多个空格。同层目录或文件结点在同一列显示。计算所有目录的大小(为其子目录大小+子文件大小+1)，并在目录名和文件后面显示各自大小。
2.2算法思想
本文对目录树采用孩子兄弟链表法结合双亲法的存储结构，根据输入的目录和文件信息，先创建树，再把孩子兄弟存储结构的树以显式的树状结构输出，每个结点要按其所在层次作相应的缩进。其中，创建树采用层序遍历算法实现，输出树采用先序遍历算法实现。若某结点的第一个孩子结点有右孩子结点（兄弟结点），则需要按其所在层次进行缩进后输出连接符|和多个空格；否则只输出多个空格；计算某目录的大小时，为该目录结点的左子树（以其第一个孩子为根的树）所有结点的“大小”的和再加该目录的“大小”。
3实现
3.1树的存储结构
在输出树结构时，由于先输出的是同一层结点的第一个结点及其对应的子树，再输出同一层结点的第二个结点及其对应的子树，所以，使用孩子兄弟链表存储结构时，用先序遍历算法遍历该结构，刚好可以实现上面的输出顺序的要求；其次，由于每一个目录结点（双亲结点）下面可能存在子目录或文件结点（孩子结点），在缩进处理上，输出子目录或文件结点信息时，要比其双亲的目录结点信息缩进更多，为了便于处理缩进，在孩子兄弟存储结构中增加了parent域，得到了改进后的孩子兄弟存储结构[3。
3.2关键算法的设计
（1）创建树的改进孩子兄弟存储结构：首先读入根目录名称和大小，创建根结点，将根结点的三个指针域置空。读入下一行目录或文件信息并创建结点。创建新结点，该结点是根结点的第一孩子结点，建立其和根结点的链接。然后循环做如下的操作：若本行后面还有文件或目录信息，建立新结点，建立其和双亲结点的链接，建立其和前一兄弟结点的链接。将该结点的“大小”值加到根结点的“大小”中去。重复该过程，直到本行信息读取结束。重复上面的过程，直到整体输入结束。(2)输出树：设当前指针（位置）为根目录，先输出根结点；将当前指针改为根结点的第一孩子结点循环做如下操作：输出当前指针对应的结点及其子树；将当前指针移向当前指针的下一兄弟结点；直至当前指针为空。
作者：田晓辉 单位：渭南师范学院网络安全与信息化学院
《数据结构的遍历课程设计与实现》
由：免费论文网互联网用户整理提供,链接地址：
http://m.csmayi.cn/show/212426.html
转载请保留,谢谢!
- 上一篇：小学数学电子作业设计理念
- 下一篇：绿色设计理念在食品包装的运用