当前位置：文档之家 › 数据结构课程设计报告

数据结构课程设计报告

  • 格式：doc
  • 大小：540.50 KB
  • 文档页数：27

课程设计任务书2014 — 2015 学年第1 学期计算机与通信学院（系、部）专业班级课程名称：数据结构设计题目：二叉树操作系统完成期限：自年月日至年月日共周指导教师（签字）：年月日系（教研室）主任（签字）：年月日数据结构课程设计设计说明书二叉树操作系统起止日期：年月日至年月日学生姓名班级学号成绩指导教师(签字)计算机与通信学院（部）年月日目录1 课程设计简介 (4)1.1 课程设计的目的 (4)1.2 课程设计内容 (4)2 数据结构的设计 (5)2.1 结构体设计 (5)2.1 编译预处理 (5)3 数据结构的分析 (6)3.1 菜单界面 (6)3.2辅助函数和语句 (6)3.3创建和遍历 (7)3.4查找和删除 (8)3.5常用编辑 (8)3.6打印输出 (8)3.7队列和栈 (8)3.8功能菜单 (9)3.9文件操作 (9)4 程序运行结果 (9)4.1二叉树的基本操作 (9)4.2二叉树的主要应用 (10)4.3各部分效果演示 (10)4.4 程序运行解释 (11)5 心得体会 (12)参考文献 (13)附部分源代码 (14)1 课程设计简介1.1 课程设计的目的通过对“二叉树操作系统”的深究，使我对问题进行分析和设计的能力获得加强；使我对二叉树的基本操作、以及主要应用得到了深层次的理解，同时复习了自己的C语言知识，加强了自己对代码的可操作性，为以后编写应用程序打下基础。

熟悉各类编译器的使用，加深自己对数据结构课本的研读，了解更多的算法思维，结合到生活中的实际应用等。

1.2 课程设计内容二叉树操作系统应具备如下的功能：①二叉树基本操作：a)创建二叉树：采用仿先序遍历方式创建一棵二叉树，引入了外部节点b)插入左孩子：默认是根节点，其他则查找后执行同样的操作c)插入右孩子：默认是根节点，其他则查找后执行同样的操作d)查找某节点：对已存入二叉树的中节点信息进行按元素查找e)求叶子数目：遍历加判断确定出叶子节点的数目f)求深度操作：递归求构建的二叉树的深度g)先中后递归打印：先序、中序、后序遍历二叉树的同时打印节点信息h)先中后非递归打印：采用栈、队列、数组实现二叉树的非递归遍历打印i)层次遍历：采用队列实现层次遍历j)各类节点数：计算构建的二叉树内各类度数节点的数目k)树左右互换：默认是根节点，其他节点按元素查找并执行同样的操作l)删除左子树：默认也是根节点，其他节点也是同上方法即可实现m)删除右子树：默认也是根节点，其他节点也是同上方法即可实现n)查找指定节点双亲：查找构建的二叉树内任意节点(根节点除外)的双亲o)查找指定节点孩子：查找构建的二叉树内任意节点(叶子除外)左右孩子p)查找指定节点子孙：查找任意节点的所有子孙节点信息q)查找指定节点祖先：查找任意节点的所有祖先节点信息②二叉树的主要应用：a)二叉排序树：创建二叉、搜索节点、插入节点、删除节点b)最优二叉树：初始操作、编码操作、译码操作、打印操作③其他辅助的维护调整美化工作。

2 数据结构的设计2.1 结构体设计因为涉及到二叉树，我采用的是链式存储方式，以左右孩子指针域存储下整个二叉树的结构，再设置了每个节点应有的数据域存放每个节点的信息。

因为涉及到二叉树非递归遍历涉及到队列和栈，所以我又设计了顺序栈和顺序循环队列的结构类型声明定义；因为二叉树的主要应用有二叉排序树和最优二叉树，但是二叉排序树的数据类型我默认是整型，所以二叉排序树结构类型不做重复声明定义，然而我的最优二叉树节点类型是字符型的，所以我另外设置了新的数据类型。

具体如下：二叉链表结构类型声明定义：typedef struct BTNode //左右孩子表示法---二叉链表{ //为后面的二叉排序树和最优二叉树做准备DataType data; //存放字符型数据ElemType ans; //存放整型数据struct BTNode *lchild; //二叉树的链式存储结构struct BTNode *rchild;}BTNode,*BTree;顺序栈结构类型声明定义：#define MaxStackSize 10000 //主要处理先中后非递归遍历typedef struct{BTree data[MaxStackSize];int top;}SqStack;顺序循环队列结构类型声明定义：#define MAX 10000typedef struct //既然顺序队列的话，那么一个这种结构类型的节点就好了{BTree data[MAX]; //主要处理先中后非递归遍历以及层次遍历int front;int rear;int tag;}SqQueue,*Squeue;2.1 编译预处理考虑到可能需要用到的文件名包括以及宏定义、条件编译等原因，做了足够的编译预处理,但是考虑到报告的填写，这里只列出主要用到的，具体如下：#include<queue>#include<stack>#include<math.h>#include<stdio.h>#include<iostream>#include<string.h>#include<stdlib.h>#include<malloc.h>using namespace std;typedef int ElemType;typedef char DataType;#include"SqStack.h"#include"SqQueue.h"#include"二叉树基本操作.h"#include"二叉排序树.h"#include"哈夫曼树.h"3 功能模块（或算法）描述在实现程序的时候并没有完全按照书上给出的函数来进行设计，在实际的过程中用到了将近50个函数，大部分函数是实现核心功能的，还有一部分函数是用来美化控制台的输出操作以及功能菜单(加强用户对程序的可操作性)，期间还涉及到了C++ STL库函数应用操作。

3 数据结构的分析3.1 菜单界面main() 主函数Basic_operation(root); 显示“二叉树的基本操作”功能界面Fuction_BTree(root); 显示“二叉排序树”功能界面Fuction_HuffumanTree(root); 显示“哈夫曼树”功能界面3.2辅助函数和语句system(“cls”); //控制台清屏函数system(“pause”); //输出暂停函数system("color 0b"); //设置控制台颜色函数Sleep(100); //延时函数fclose() //文件关闭函数fopen() //文件打开函数rewind() //文件指针重定位函数fgetc() //以字符方式进行文件读写函数fputc() //以字符方式进行文件读写函数fprintf() //以格式化方式进行文件读写函数fscanf() //以格式化方式进行文件读写函数system("mode con:cols=400 lines=30000"); //调节控制台大小函数goto语句的使用 //循环设置switch语句 //多路分支语句3.3创建和遍历void CreateBiTree(BTNode **root) //仿先序遍历创建二叉树BTree CreateHuf(ElemType a[],int n) //建立哈夫曼树void Create_BTree(BTree *root) //建立二叉排序树void Pre_order_Rec(BTree root) //先序遍历递归版void In_order_Rec(BTree root) //中序遍历递归版void Post_order_Rec(BTree root) //后序遍历递归版void LevelOrder_First(BTree Tree) //层次遍历C++ STL实现void LevelOrder_Second(BTree Tree) //层次遍历指针数组模拟队列void LevelOrder_Third(BTree root) //C语言自写队列void PreOrder_NonRec_First(BTree root) //先序非递归其一void PreOrder_NonRec_Second(BTree Tree) //先序非递归其二void PreOrder_NonRec_Third(BTree Tree) //先序非递归其三void PreOrder_NonRec_Fouth(BTree Tree) //先序非递归其四void InOrder_NonRec_First(BTree root) //中序非递归其一void InOrder_NonRec_Second(BTree T) //中序非递归其二void InOrder_NonRec_Third(BTree T) //中序非递归其三void PostOrder_NonRec_Second(BTree T) //后序非递归其一void PostOrder_NonRec_Third(BTree T) //后序非递归其二3.4查找和删除void Find_Child_Bnode(BTNode *p,BTNode **p_lchild,BTNode **p_rchild)int Find_Parent_Bnode(BTree root,BTNode *p,BTNode **p_parent)void FindDescendants_Blist(BTNode *p) //查找指定节点子孙void FindAncersors_Blist(BTree root,BTNode *p) //查找祖先节点int Insearch_BTree(BTree root,DataType x,BTree &p) //根据元素指定查找3.5常用编辑BTree Insert_LeftNode(BTree father,DataType x) //给某节点插入左孩子BTree Insert_RightNode(BTree father,DataType x) //给某节点插入右孩子BTree Delete_LeftTree(BTree Node) //删除左子树BTree Delete_RightTree(BTree Node) //删除右子树void Destroy_BTree(BTree *root) //通过释放节点达到销毁的目的void Exchange_BTree(BTree root) //交换所有节点的左右子树void NodeCount_Rec(BTree root) //基于后序遍历的二叉树各类结点统计递归算法3.6打印输出void In_order_Rec_BST(BTree root) //中序遍历输出二叉排序结果void Print_BTree(BTree root) //以广义表形式显示哈夫曼树的结构3.7队列和栈void Init_Squeue(Squeue &head) //队列初始化void En_Squeue(Squeue head,BTree e) //入队void De_Squeue(Squeue head,BTree *e) //出队int Empty_Squeue(SqQueue head) //队空判断int Full_Squeue(SqQueue head) //队满判断void StackInitiate(SqStack *S) //栈初初始化int StackPush(SqStack *S,BTree x) //入栈int StackPop(SqStack *S,BTree *d) //出栈int StackNotEmpty(SqStack S) //栈空判断3.8功能菜单void Basic_operation(BTree root) //二叉树基本操作功能菜单Fuction_BTree(root); //二叉排序树功能菜单Fuction_HuffumanTree(root); //哈夫曼树功能菜单3.9文件操作void Hufcoding(BTree root,int len,FILE *fp,FILE *fp2)//哈夫曼编码写入文件void Decoding_HuffumanTree(BTree root,FILE *fp1)//哈夫曼译码写入文件4 程序运行结果4.1二叉树的基本操作4.2二叉树的主要应用4.2.1 二叉排序树界面4.2.2 最优二叉树界面4.3各部分效果演示4.4 程序运行解释1、输入abc####，构建一颗如下所示的二叉树：2、二叉排序树构建，输入5个节点信息分别为5,3,1,7,8构建一棵如下的树：3、哈夫曼树的应用，输入6个叶子节点的权值(3,9,5,12,6,15)，构建一棵如下树：代码根据仿先序遍历的思维(引入了外部节点#，实则为NULL)，创建了一棵左斜树。

合集下载

数据结构课程设计实践报告

数据结构课程设计实践报告

数据结构课程设计实践报告数据结构课程设计实践报告1. 实验目的本次数据结构课程设计实践的目的是帮助学生掌握数据结构的基本概念，了解常见数据结构的实现原理，提高代码实现能力和问题解决能力。

2. 实验背景数据结构是计算机科学的基础课程，它是计算机科学的重要组成部分。

在计算机科学中，数据结构是针对计算机中的数据存储、管理和操作的方法论。

数据结构中的“数据”是指计算机中存储的各种信息，而“结构”则是指这些信息之间的相互关系。

常见的数据结构包括数组、链表、栈、队列、树和图等。

3. 实验内容本次数据结构课程设计实践包括以下内容：3.1 栈和队列实现一个基于栈和队列的计算器程序，能够进行加减乘除等基本运算和括号运算。

3.2 链表与树实现一个简单的文件系统，包括文件的创建、删除、移动、复制等操作，利用链表实现文件存储，利用树来实现文件目录结构。

3.3 图实现最短路径算法，并利用Graphviz工具将结果可视化展示出来。

4. 实验过程我们小组首先进行了团队分工，每个成员负责一个模块的代码实现，同时进行代码审查。

我们使用C++语言进行编码实现，采用面向对象设计思想，将每个数据结构封装成一个类，方便日后的调用和扩展。

在实现栈和队列的计算器程序时，我们使用了双栈法来进行括号运算的处理，使用队列来实现多项式的存储和输出。

在实现文件系统时，我们构建了一颗树形结构来表示文件的目录结构，同时在每个节点处保存了一个链表，来存储该目录下的文件信息，方便进行操作。

在实现最短路径算法时，我们采用了Dijkstra算法，并使用Graphviz 工具将结果可视化展示出来。

5. 实验结果我们小组经过不断尝试和调试，最终实现了所有要求的功能，并达到了预期的效果。

我们在实验过程中遇到的问题，如链表的指针操作、树的遍历方法以及Dijkstra算法的实现等，我们通过文献资料的查阅和团队讨论得以解决。

6. 实验总结通过本次数据结构课程设计实践，我们加深了对数据结构的理解和掌握，同时也提高了我们的编程能力和问题解决能力。

数据结构课程设计实验报告完整版

数据结构课程设计实验报告完整版

数据结构课程设计实验报告完整版【正文】一、实验目的本实验主要目的是通过实践，掌握数据结构的基本概念、常见数据结构的实现方式以及在实际应用中的应用场景和效果。

二、实验背景数据结构是计算机科学与技术领域中的一个重要概念，是研究数据的组织方式、存储方式、访问方式以及操作等方面的方法论。

在计算机科学领域，数据结构是实现算法和解决问题的基础，因此对数据结构的理解和应用具有重要意义。

三、实验内容本次数据结构课程设计实验主要分为以下几个部分：1. 实验环境的准备：包括选择合适的开发平台、安装必要的软件和工具。

2. 实验数据的收集和处理：通过合适的方式收集实验所需的数据，并对数据进行处理和整理。

3. 数据结构的选择和实现：根据实验需求，选择合适的数据结构，并进行相应的数据结构实现。

4. 数据结构的测试和优化：对所实现的数据结构进行测试，包括性能测试和功能测试，并根据测试结果对数据结构进行优化和改进。

5. 实验报告的撰写：根据实验过程和结果，撰写完整的实验报告，包括实验目的、实验背景、实验内容、实验结果和结论等。

四、实验过程1. 实验环境的准备本实验选择了Visual Studio作为开发平台，安装了相应版本的Visual Studio，并根据官方指引进行了相应的配置和设置。

2. 实验数据的收集和处理本实验选取了一份包含学生信息的数据集，包括学生姓名、学号、性别、年龄等信息。

通过编写Python脚本，成功提取了所需信息，并对数据进行了清洗和整理。

3. 数据结构的选择和实现根据实验需求，我们选择了链表作为数据结构的实现方式。

链表是一种常见的动态数据结构，能够高效地插入和删除元素，适用于频繁插入和删除的场景。

在实现链表时，我们定义了一个节点结构，包含数据域和指针域。

通过指针的方式将节点连接起来，形成一个链式结构。

同时，我们还实现了相关的操作函数，包括插入、删除、查找等操作。

4. 数据结构的测试和优化在完成链表的实现后，我们对其进行了性能测试和功能测试。

数据结构课程设计实验报告

数据结构课程设计实验报告

数据结构课程设计实验报告引言数据结构课程设计实验是为了加深对数据结构基本概念和算法的理解和掌握，通过实际操作来加深对数据结构的认识和应用能力。

本实验报告将介绍在数据结构课程设计实验中所完成的内容，包括实验目的、实验环境、实验过程、实验结果以及实验总结。

实验目的通过本次实验，旨在掌握以下内容： - 理解并掌握线性表、栈、队列、链表、二叉树等基本数据结构的概念和实现； - 熟悉数据结构的插入、删除、查找等基本操作； - 学习并掌握基本排序算法和查找算法的实现； - 通过实验加深对数据结构和算法的理解，并能够灵活运用于实际问题的解决。

实验环境本次实验在以下环境下进行： - 操作系统：Windows 10 - 编程语言：C语言 - 集成开发环境：Visual Studio Code实验过程1. 线性表的操作设计1.1 定义结构体首先，定义表示线性表的结构体，包括数据域和指向下一个结点的指针。

typedef struct Node {int data; // 数据域struct Node* next; // 指向下一个结点的指针} Node;1.2 初始化线性表编写函数以初始化一个空的线性表。

void InitList(Node** head) {*head = (Node*)malloc(sizeof(Node));(*head)->next = NULL;}1.3 插入元素编写函数以在线性表的指定位置插入元素。

```C void Insert(Node* head, int pos, int data) { if (pos < 1) { printf(。

数据结构课程设计实验报告 完整版

数据结构课程设计实验报告 完整版

第一章链表的应用线性表是数据结构中最简单、最常用的一种线性结构，也是学习数据结构全部内容的基础，其掌握的好坏直接影响着后继课程的学习。

线性表的顺序存储结构，即顺序表的概念相对比较简单，因此，本章的主要任务是使用有关单链表的操作来实现通讯录信息系统的管理。

1.1设计要求本章的设计实验要求使用有关链表的操作来实现通讯录信息系统的管理。

为了验证算法，通讯录管理包括单通讯录链表的建立、通讯者的插入、通讯者的删除、通讯者的查询及通讯录表的输出等。

主控菜单的设计要求使用数字0—5来选择菜单项，其他输入则不起作用。

程序运行后，给出6个菜单项的内容和输入提示：1．通讯录链表的建立2. 通讯者结点的插入3. 通讯者结点的查询4. 通讯者结点的删除5. 通讯录链表的输出0. 退出管理系统请选择0—5：1.2设计分析1.2.1主控菜单函数设计分析1.实现循环和功能选择首先编写一个主控菜单驱动程序，输入0—5以进入相应选择项。

假设输入选择用变量sn存储，它作为menu_select函数的返回值给switch语句。

使用for循环实现重复选择，并在主函数main()中实现。

实际使用时，只有选择大于5或小于0的值，程序才能结束运行，这就要使用循环控制。

这里使用for循环语句实现菜单的循环选择，为了结束程序的运行，使用了“return”语句，也可以使用“exit(0);”语句。

2.得到sn的合理值如前所述，应该设计一个函数用来输出提示信息和处理输入，这个函数应该返回一个数值sn，以便供给switch语句使用。

假设函数名为menu_select,对于sn的输入值，在switch 中case语句对应数字1—5，对于不符合要求的输入，提示输入错误并要求重新输入。

将该函数与主函数合在一起，编译运行程序，即可检查并验证菜单选择是否正确。

1.2.2功能函数设计分析1.建立通讯录链表的设计这里实际上是要求建立一个带头结点的单链表。

建立单链表有两种方法，一种称之为头插法，另一种称为尾插法。