《2022年数据结构课程方案小组报告模板》由会员分享，可在线阅读，更多相关《2022年数据结构课程方案小组报告模板（13页珍藏版）》请在金锄头文库上搜索。
1、个人资料整理仅限学习使用数据结构课程设计-小组设计报告专业：计算机科学与技术班级：计算机科学与技术06* 组号：201 组长姓名 副组长姓名 组员姓名 指导教师：冯向阳、陈志良日期： 08 年 1 月 10 日至 08 年 1 月 20 日目录精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 13 页个人资料整理仅限学习使用1组内成员贡献表姓名 学号）学号贡献度张三060* 李四钱五总计）2 课程设计目的1、 学习获取知识的方法；2、 提高发现问题、分析问题和解决实际问题的能力；3、 加强创新意识和创新精神；4、 加强团队的分工与合作；5
2、、 掌握面向实际背景思考问题的方法。3 课程设计内容和要求内容：第一章前言第二章航班信息的查询与检索第三章树结构的应用第四章图结构的应用第五章大数四则运算第六章综合应用 图书管理信息系统的设计和实现要求：完成第 2章、第 3章中每章 2个设计任务中的至少一个任务。在完成个人任务1的基础上，完成第4章2个设计任务中的至少一个任务。每人必须在完成个人任务的基础上提交个人任务的设计报告，内容包括：任务名称、目的、具体内容、需求分析、概要设计、主要代码分析、测试结果、收获与体会。无论是个人任务还是小组任务希望各小组团队合作，小组成员之间应互相讨论，互相启发。表1-1 组内成员贡献表精选学习资料 - -
3、 - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 13 页个人资料整理仅限学习使用4 任务完成情况任务完成情况介绍，如表3-1.仅供参考，请根据实际完成情况填写）完成任务名称交通咨询系统设计关键路径问题大数四则运算5 设计名称5.1 设计目的根据内容填写5.2 设计内容及要求本程序用VC编写，完成以下功能：根据内容填写5.3 需求分析下列仅供参考 请根据内容填写）本程序用 VC编写，完成二叉树的生成二叉链表、递归中序遍历、非递归中序遍历、层次遍历、计算二叉树的深度及叶子个数、建立线索二叉树并实现中序遍历等功能，并且需要一个菜单让用户自主选择执行的功能。 输入
4、的形式和输入值的范围：元素输入时，元素的值都是char型，以 “ #” 为空结点。输出的形式：在每次选择菜单后，都输出相应的结果，并且询问下次操作的工程。程序所能达到的功能：完成单链表的二叉树的生成二叉链表、递归中序遍历、非递归中序遍历、层次遍历、计算二叉树的深度及叶子个数、建立线索二叉树并实现中序遍历。每次操作结束后，都会有菜单方便用户进行下一步的操作。测试数据：A菜单显示为：-菜单 -A-二叉树建立B-递归中序遍历C-非递归中序遍历D-层次遍历E-求二叉树的深度F-求二叉树的子叶个数表3-1 任务完成情况表精选学习资料 - - - - - - - - - 名师归纳总结 - - - - -
5、- -第 3 页，共 13 页个人资料整理仅限学习使用G-线索二叉树的建立及遍历H-退出请输入您要测试的工程：B二叉树建立? 选择A或 a ? 显示 “请按先序建立二叉树的结点序列以 “ #”为空结点）：”? 输入 ABC#DE#F#G# ? 输出完成创建二叉树! C递归中序遍历? 选择B或b ? 显示 “该二叉树的递归中序遍历序列为：”? 输出 C B E D F A G D非递归中序遍历? 选择C或 c ? 显示 “该二叉树的非递归中序遍历序列为：”? 输出 C B E D F A G E层次遍历? 选择D或 d ? 显示 “该二叉树层次遍历序列为：”? 输出 C B E D F A G
6、F求二叉树的深度? 选择E或e ? 显示 “该二叉树的深度为：”? 输出 4 G求二叉树的子叶个数? 选择F或f ? 显示 “该二叉树的子叶个数为：”? 输出 4 H线索二叉树的建立及遍历? 选择G或 g ? 显示 “请按先序线索二叉树输入元素：”? 输入 ABC#DE#F#G# ? 输出完成创建线索二叉树! ? 显示 “二叉树的线索化：”? 输出线索化成功 ! ? 显示 “线索二叉树的中序遍历：”? 输出 C B E D F A G I退出程序? 选择 7 ? 退出当前程序5.4 概要设计1)为了实现上述程序功能，需要定义单链表的抽象数据类型：下列仅供参考 请根据内容填写）CreateBin
7、Tree&T ）操作结果：构造一个先序存储的二叉树T，以 “#”为空结点InorderT ）初始条件：二叉树T已存在操作结果：将二叉树T按中序遍历InorderNT ）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 13 页个人资料整理仅限学习使用初始条件：二叉树T已存在操作结果：将二叉树T按中序遍历print_cengciT ）初始条件：二叉树T已存在操作结果：将二叉树T按层次遍历PostTreeDepthT）初始条件：二叉树T已存在操作结果：将二叉树T的深度输出leafT）初始条件：二叉树T已存在操作结果：将二叉树T的叶子个数输出C
8、reateBiThrTreeTr ）操作结果：构造一个先序存储的线索二叉树Tr，以 “#”为空结点InOrderThreadingTr ）初始条件：线索二叉树Tr已存在操作结果：将二叉树Tr线索化InOrderTraverse_ThrTr ）初始条件：线索二叉树Tr已存在操作结果：将线索二叉树Tr输出2)本程序包含 9个函数：下列仅供参考 初始化二叉树函数CreateBinTree ( 递归中序遍历二叉树函数Inorder ( 非递归中序遍历二叉树函数Inorder N( 层次遍历二叉树函数print_cengci ( 计算二叉树深度函数PostTreeDepth ( 计算二叉树叶子个数函数l
9、eaf l ( 初始化线索二叉树函数CreateBiThrTree ( 二叉树线索化函数InOrderThreading ( 线索二叉树输出函数 InOrderTraverse_Thr( 3)各函数间关系如下：下列仅供参考 Inorder ( Inorder N( print_cengci ( main(PostTreeDepth ( leaf l ( CreateBiThrTree ( InOrderThreading ( InOrderTraverse_Thr(5.5 详细代码见附录一。5.6 使用说明下列仅供参考 请根据内容填写）程序名为二叉树.exe，所有程序在VC+ 6.0 环境下调
10、试通过。程序执行如图4-1。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 13 页个人资料整理仅限学习使用输入字母选择执行不同的功能。要求首先创建二叉树或线索二叉树，才可以进行其他的操作。每执行一次功能，就会显示执行的结果以及再次输出菜单，以便继续选择功能。选择 A或 a：显示 “ 请按先序建立二叉树的结点序列以“#”为空结点）：” ，要求输入二叉树的结点，以“ #”为空结点，显示 “ 完成创建二叉树! ” 。选择 B或b：显示 “ 该二叉树的递归中序遍历序列为：” 。选择 C或c：显示 “ 该二叉树的非递归中序遍历序列为：” 。选择
11、 D或d： “ 该二叉树的层次遍历序列为：” 。选择 E或e：显示 “ 该二叉树的深度为：” 。选择 F或f： 显示 “ 该二叉树的子叶个数为：” 。选择 G或g： 显示 “ 请按先序线索二叉树输入元素：” ，要求输入线索二叉树的结点，以“ #”为空结点，显示 “ 完成创建线索二叉树! ” ，显示 “ 二叉树的线索化：” ，显示 “ 线索化成功 ! ” ，显示 “ 线索二叉树的中序遍历：” 。选择 H或h：退出程序5.7 测试结果与分析下列仅供参考 请根据内容填写）1)建立二叉树：实验结果 文字说明并配图），如图4-2。图 4-1 二叉树的程序执行图精选学习资料 - - - - - - - -
12、 - 名师归纳总结 - - - - - - -第 6 页，共 13 页个人资料整理仅限学习使用相应分析。2)递归中序遍历二叉树：下列仅供参考请根据内容填写）运行结果 文字说明并配图），如图4-3。相应分析。3)非递归中序遍历二叉树：实验结果 文字说明并配图），如图4-4。图4-2 建立二叉树的程序执行图图4-3 二叉树的递归中序遍历的程序执行图精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 13 页个人资料整理仅限学习使用相应分析。4)层次遍历：实验结果 文字说明并配图），如图4-5。相应分析。5)计算二叉树的深度：实验结果 文字说明并
13、配图），如图4-6。相应分析。6） 计算二叉树的叶子个数：实验结果 文字说明并配图），如图4-7。图4-4 二叉树的非递归中序遍历的程序执行图图4-5 二叉树的层次遍历的程序执行图图4-6 计算二叉树的深度的程序执行图精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 13 页个人资料整理仅限学习使用相应分析。7） 初始化线索二叉树及其遍历：实验结果 文字说明并配图），如图4-8。相应分析。8） 退出程序：实验结果 文字说明并配图），如图4-9。相应分析。5.8 体会与感想下列仅供参考 请根据内容填写）经过。，对我的编程能力有了一定的提高。
14、所以这的实验相对来说完成的稍微快一些。对于书上图4-7 计算二叉树的叶子个数的程序执行图图4-8 初始化线索二叉树及其遍历的程序执行图图4-8 退出程序的程序执行图精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 13 页个人资料整理仅限学习使用算法的实现，也有了一定的效率的提高。由于线索二叉树的复杂，在其的初始化以及线索化上，都花费了一些时间。最后还是参考了书以及其他人的程序，才得以实现。今后，要提高编程的速度，同时在完成基本任务的情况下，也可以尝试着做一下老师布置的较高要求。6 参考文献附录：设计名称的代码#include #incl
15、ude #include #define MAX 1000 #define OVERFLOW 0 #define OK 1 int num_leaf=0 。typedef char ElemType。typedef ElemType TElemType 。typedef struct node TElemType data。struct node *lchild,*rchild。BinTNode 。typedef enum PointerTagLink,Thread。typedef struct BiThrNode TElemType data。struct BiThrNode *lchild
16、,*rchild。 PointerTag LTag,RTag。BiThrNode 。typedef BinTNode *BinTree 。typedef BiThrNode *BiThrTree。BiThrTree pre 。void CreateBinTree(BinTree &T /二叉树的建立 char ch。cinch 。if(ch=# T=NULL 。else T=(BinTNode *malloc(sizeof(BinTNode。T-data=ch。CreateBinTree(T-lchild 。CreateBinTree(T-rchild 。 精选学习资料 - - - - - -
17、 - - - 名师归纳总结 - - - - - - -第 10 页，共 13 页个人资料整理仅限学习使用 void Inorder(BinTree T /二叉树的中序递归便历if(T Inorder(T-lchild 。printf(%3c,T-data 。Inorder(T-rchild 。 void InorderN(BinTree T /二叉树的中序非递归便历BinTree stackMAX,p 。 int top=0 。p=T。do while(p!=NULL stacktop=p 。top+。p=p-lchild 。 if(top0 top-。p=stacktop 。printf(%
18、3c,p-data 。p=p-rchild 。 while(p!=NULL|top!=0。 void print_cengci(BinTree T/ 层次遍历二叉树 BinTree stackMAX,p 。int top=0,base=0。if(T p=T。stackbase=p。base+。while(top!=base printf(%3c,stacktop-data。if(stacktop-lchild stackbase=stacktop-lchild 。base+。 if(stacktop-rchild stackbase=stacktop-rchild 。base+。 top+。
19、int PostTreeDepth(BinTree T / 求二叉树的高度 int hl,hr,max 。 if(T 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 13 页个人资料整理仅限学习使用 hl=PostTreeDepth(T-lchild 。 /求左子树的深度 hr=PostTreeDepth(T-rchild 。 /求右子树的深度 max=hlhr?hl:hr 。 /得到左、右子树深度较大者 return(max+1 。 / 返回树的深度 else return(0 。 /如果是空树，则返回 void leaf(BinT
20、ree T / 二叉树的叶子个数 if(T if(T-lchild=NULL&T-rchild=NULL num_leaf+。 /若T所指结点为叶子, 则累加leaf(T-lchild 。leaf(T-rchild 。 void CreateBiThrTree(BiThrTree &Tr /线索化建立二叉树 char ch。cinch 。if(ch=# Tr=NULL 。else Tr=(BiThrNode *malloc(sizeof(BiThrNode。Tr-data=ch。Tr-LTag=Tr-RTag=Link 。CreateBiThrTree(Tr-lchild 。CreateBiT
21、hrTree(Tr-rchild 。 void InThread(BiThrTree Tr / 线索化二叉树 if(Tr InThread(Tr-lchild 。 /线索化左子树if(!Tr-lchild / 置前驱线索Tr-LTag=Thread。Tr-lchild=pre 。 if(!pre-rchild / 置后继线索pre-RTag=Thread。pre-rchild=Tr 。 pre=Tr。 /保持 pre指向 Tr的前驱InThread(Tr-rchild 。 /线索化右子树 struct BiThrNode *InOrderThreading(BiThrTree Tr /中序遍历
22、二叉树T /将其中序线索化，Thrt指向头结点 BiThrTree Thrt 。if(!(Thrt=(BiThrTreemalloc(sizeof(BiThrTree exit(OVERFLOW 。Thrt-LTag=Link 。 Thrt-RTag=Thread 。 /建立头结点Thrt-rchild=Thrt 。 /右指针回指精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 13 页个人资料整理仅限学习使用if(!Tr / 若二叉树为空，则左指针回指Thrt-lchild=Thrt 。else Thrt-lchild=Tr 。pre
23、=Thrt。InThread(Tr 。 /中序遍历进行中序线索化 pre-rchild=Thrt 。pre-RTag=Thread。 /最后一个结点线索化Thrt-rchild=pre 。 printf( 线索化成功 !n 。return(Thrt 。 void InOrderTraverse_Thr(BiThrTree T /输出线索二叉树 /T 指向头结点，头结点的左链lchild 指向根结点/中序遍历二叉线索树T的非递归算发 BiThrTree p。p=T-lchild 。 /p 指向根结点while(p!=T / 空树或遍历结束时，p=T while(p-LTag=Link p=p-lchild 。printf(%3c,p-data 。 /访问其左子树为空的结点while(p-RTag=Thread&p-rchild!=T p=p-rchild 。printf(%3c,p-data 。 /访问后继结点 p=p-rchild 。 void main( BinTree T 。BiThrTree Tr 。char ch1,ch2。printf(n 欢迎进入二叉树基本操作测试程序，请选择：n。ch1=y。while(ch1=y|ch1=Y printf(-菜单 -。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 13 页
