2022年数据结构课程方案二叉排序树实现.docx

《2022年数据结构课程方案二叉排序树实现.docx》由会员分享，可在线阅读，更多相关《2022年数据结构课程方案二叉排序树实现.docx（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用数据结构课程设计一、 引言数据结构是一门理论性强、思维抽象、难度较大的课程,是基础课和专业课之间的桥梁；该课程的先行课程是运算机基础、程序设计语言、离散数学等,后续课程有操作系统、编译原理、数据库原理、软件工程等；通过本门课程的学习,我们应当能透彻地懂得各种数据对象的特点,学会数据的组织方法和实现方法,并进 一步培育良好的程序设计才能和解决实际问题的才能；数据结构是运算机科学与技术专业的一门核心专业基础课程,在该专业的课程 体系中起着承上启下的作用,学好数据结构对于提高理论认知水平和实践才能有着 极为重要的作用；学习数

2、据结构的最终目的是为了获得求解问题的才能；对于现实 世界中的问题,应当能从中抽象出一个适当的数学模型,该数学模型在运算机内部 用相应的数据结构来表示,然后设计一个解此数学模型的算法,再进行编程调试,最终获得问题的解答；实习课程是为了加强编程才能的培育,勉励同学使用新兴的编程语言；信任通 过数据结构课程实践,无论是理论学问,仍是实践动手才能,我们都会有不同程度 上的提高；二、 课程设计目的 本课程是数据结构课程的实践环节；主要目的在于加强同学在课程中学习的相关算法和这些方法的具体应用,使同学进一步把握在C+或其他语言中应用这些算法的才能；通过课程设计题目的练习,强化同学对所学学问的把握及对问题分

3、析和 任务定义的懂得；名师归纳总结 - - - - - - -第 1 页,共 12 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用三、内容设计要求二叉排序树的实现：用次序和二叉链表作储备结构1）以回车 对二叉排序树 T作中序遍历,输出结果；L, 生成一棵二叉排序树 T；3）输入元素 x,查找二叉排序树 T,如存在含 x的结点,就删除该结点,并作中序遍 历执行操作 2）；否就输出信息 “无x” ；一）问题分析和任务定义 对问题的描述应躲开具体的算法和涉及的数据结构,它是对要完成的任务作出 明确的回答,强调的是做什么,而不是怎么做；二）具体的设计和编码 算法的具体描

4、述和代码的书写；三）上机调试 源程序的输入和代码的调试；要求：设计中要求综合运用所学学问,上机解决一些与实际应用结合紧密的、规模较大的问题,通过分析、设计、编码、调试等各环节的训练,深刻懂得、坚固 的把握数据结构和算法设计技术,把握分析、解决实际问题的才能；四、源代码 1、用二叉链表储备结构实现 #include using namespace std；typedef int KeyType；名师归纳总结 - - - - - - -第 2 页,共 12 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用typedef struct Node KeyType key

5、；struct Node *lchild,*rchild ；BSTNode, *BSTree；void InsertBSTBSTree *bst, KeyType key BSTree s；if *bst = NULL/* 递归终止条件 */ s=new BSTNode；s- key=key；s-lchild=NULL ；s-rchild=NULL ；*bst=s； else if key -key InsertBST&*bst-lchild, key ；/* 将 s插入左子树 */ else if key *bst-key InsertBST&*bst-rchild, key ； /* 将

6、s 插入右子树 */ void CreateBSTBSTree *bst 名师归纳总结 - - - - - - -第 3 页,共 12 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用KeyType key；*bst=NULL ；scanf%d, &key ；while key.=0 InsertBSTbst, key；scanf%d, &key ； void InOrderBSTree root if root.=NULL InOrderroot-lchild ；printf%d ,root-key ；InOrderroot-rchild ； BSTNode *

7、 DelBSTBSTree T, KeyType x BSTNode *p, *f,*s ,*q ；p=T；f=NULL ；名师归纳总结 - - - - - - -第 4 页,共 12 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用whilep /* 查找关键字为 x 的待删结点 p*/ ifp-key=x break ；f=p； /*f 指向 p 结点的双亲结点 */ ifp-keyx p=p-lchild ；else p=p-rchild； */ ifp=NULLreturn T ； /* 如找不到,返回原先的二叉排序树 ifp-lchild=NULL /*

8、p 无左子树 */ iff=NULL T=p-rchild ；else iff-lchild=p f-lchild=p-rchild ；else f-rchild=p-rchild ；delete p； else /*p 有左子树 */ 名师归纳总结 - - - - - - -第 5 页,共 12 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用q=p；s=p-lchild ；whiles-rchild /* 在 p 的左子树中查找最右下结点 */ q=s；s=s-rchild； ifq=p q-lchild=s-lchild ； /* 将 s的左子树链到 q 上

9、*/ else q-rchild=s-lchild ；p-key=s-key；delete s； return T； void main BSTree T；int x；BSTree result；printf 建立二叉排序树,请输入序列 L:n ； CreateBST&T；名师归纳总结 - - - - - - -第 6 页,共 12 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用printf 中序遍历输出序列为 :；InOrderT；cinx；result = DelBSTT,x；if result .= NULL InOrderresult； else pri

10、ntf 无 xn ； 2、用次序储备结构实现 #include using namespace std；typedef int KeyType；typedef struct Node KeyType key； struct Node *next；BSTNode,*BSTree ；int A40=-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1；int j,i=0 ；名师归纳总结 - - - - - - -第

11、 7 页,共 12 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用void InsertBSTint A,KeyType key int j=0； whileAj.=-1 ifkey j=2*j+1 ； else j=2*j+2 ； Aj=key ； void CreateBSTint A int key；scanf%d, &key ；while key.=-1 InsertBSTA,key；scanf%d, &key ； void Traverseint A,int i ifAi.=-1 名师归纳总结 - - - - - - -第 8 页,共 12 页精选学习

12、资料 - - - - - - - - - 个人资料整理 仅限学习使用 TraverseA,2*i+1； coutAi； void DelBSTint A,KeyType x fori=0 ；i ifAi=x Ai=-1 ； void main int x； /int key； printf 建立二叉排序树,请输入序列 L:n ； CreateBSTA； printf 中序遍历输出序列为 :； TraverseA,0； cinx； ifAi.=-1 DelBSTA,x ；名师归纳总结 printf 删除 x 后中序遍历输出序列为:；第 9 页,共 12 页- - - - - - -精选学习资料

13、- - - - - - - - - 个人资料整理 仅限学习使用 TraverseA,0； else printf 无 Xn ； 五、测试分析 程序运行：1、用二叉链表储备结构实现：名师归纳总结 - - - - - - -第 10 页,共 12 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用2、用次序储备结构实现：六、总结与体会通过一周的课程设计,对运算机的应用,数据结构的作用以及 C+的使用都有了更深的明白；在理论学习和上机实践的各个环节中,通过自主学习和请教老师,我收成了不少；当然也遇到不少的问题,也正是由于这些问题引发的摸索给我带了名师归纳总结 - - -

14、- - - -第 11 页,共 12 页精选学习资料 - - - - - - - - - 个人资料整理 仅限学习使用收成；从起初不喜爱上机写程序到现在能主动写程序,从起初拿着程序不知如何下手到现在知道如何分析问题,如何用专业学问解决实际问题的转变,我发觉无论是专业学问仍是动手才能,自己都有很大程度的提高；通过课程设计题目的练习,强化同学对所学学问的把握及对问题分析和任务定义的懂得；在这段时间里,我遇到过的问题主要就是C 语言和 C+语言有些混淆,一些用法记不太清晰；在老师的指导帮忙下,同学们课余时间的争论中,这些问题都一一 得到明白决；在程序的调试才能上,无形中得到了很多的提高；例如：头文件的使 用,变量和数组的范畴问题,定义变量时显现的问题等等；在实际的上机操作过程中,不仅是让我们明白数据结构的理论学问,更重要的 是培育解决实际问题的才能,所以信任通过此次实习可以提高我们分析设计才能和 编程才能,为后续课程的学习及实践打下良好的基础；名师归纳总结 - - - - - - -第 12 页,共 12 页