《软件综合算法设计报告》由会员分享，可在线阅读，更多相关《软件综合算法设计报告（22页珍藏版）》请在金锄头文库上搜索。
1、软件综合算法设计说明书项目名称：用顺序和二叉链表作存储结构实现二叉排序树学院名称：信息与电气工程学院学生姓名：XXX学生学号：XXX专业班级：计算机科学与技术XXX班同组人员：XXX指导教师：XXX摘要数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及 它们之间的关系和操作等的学科。本课程设中的二叉排序树，可以用顺序存储和 链式存储两种算法计算。本课程设中的二叉排序树，一共要实现四项基本的功能。 它们分别是二叉搜索树的创建、中序遍历、查找结点和删除结点。关键词：二叉排序树；中序遍历；搜索结点；删除结点；cc+目录一、第一章 课题介绍31. 课题背景32. 课题目的33. 课程设计
2、的要求3二、第二章 课程设计的需求分析31. 问题分析和任务定义32. 设计任务流程33. 课程设计思想54. 逻辑设计54.1. 主要函数54.2. 各函数之间的流程图55. 物理设计95.1.二叉排序树95.2. 中序遍历105.3. 查找115.4. 删除115.5. 插入13三、第三章 程序设计141. 源代码142. 各功能截图203. 结果分析21四、体会总结22五、参考文献22第一章 课题介绍1课题背景随着经济的迅猛发展，各行各业纷纷应用计算机数据管理。在计算机迅猛发展的 今天，将计算机这一信息处理器应用于实际数据问题已是势必所然。采用计算机 对数据信息的处理是信息现代化和科学化
3、的重要标志。2 课题目的本课题运用c语言编写一些简易的程序来实现对一些问题的解决，检验本学期数 据结构课程的掌握度。让学生了解并掌握软件算法设计的方法与步骤，具备初步 的独立分析问题、解决问题的能力。积累项目设计及程序调试、测验的经验，提 高综合运用的能力，培养软件工作者所具备的科学工作方法和作风。3课程设计的要求简要描述题目要求，选定数据结构，写出算法，上机调试出正确的代码，总结和 整理实验报告。第二章 课程设计的需求分析1 问题分析和任务定义用顺序和二叉链表作存储结构实现二叉排序树：（1）以回车（n）为输入结束标志，输入数列L,生成一棵二叉排序树T；（2）对二叉排序树 T 作中序遍历，输出
4、结果；（3）输入元素x,查找二叉排序树T,若存在含x的结点，则删除该结点，并作 中序遍历（执行操作2）；否则输出信息“无x”。2 设计任务流程图 1 任务流程图3 课程设计思想建立二叉排序树采用边查找边插入的方式。查找函数采用递归的方式进行查 找。如果查找到相等的则插入其左子树。然后利用插入函数将该元素插入原树。对二叉树进行中序遍历采用递归函数的方式。在根结点不为空的情况下，先 访问左子树，再访问根结点，最后访问右子树。删除结点函数，采用边查找边删除的方式。如果没有查找到，进行提示；如 果查找到结点则将其左子树最右边的节点的数据传给它，然后删除其左子树最右 边的节点。4逻辑设计4.1 主要函数
5、SearchBT()InsertBT()InorderTraverse()Delete()Main()4.2 各函数之间的流程图插入子函数InsertBT()的流程图:YNNY开始p=p-lchildp=p-rchild图2子函数InsertBT()的流程图主函数流程图：; 开始 丿输入二叉排序树中的元素*调用子函数InsertBT()1 r调用子函数InorderTraverse()调用子函数SearchBT()1 r调用子函数 InorderTraverse()Delete。图3 主函数流程图子函数SearchBT()的流程图开始flag=0YN结束调用查找函数并返回找不到值为d的节点已找
6、到该节点输入需要查找的值图4子函数SearchBT()的流程图子函数InorderTraverse()流程图图 5 子函数中序遍历的流程图5 物理设计5.1 二叉排序树二叉排序树的定义：二叉排序树或者是一棵空树， 或者是一棵具有如下性 质的二叉树：(1) 每个结点都有一个作为搜索依据的关键码(key),所有结点的关键码 互不相同；(2) 若它的左子树非空，则左子树上所有结点的值均小于根结点的值；(3) 若它的右子树非空，则右子树上所有结点的值均大于根结点的值；( 4) 左、右子树本身又各是一棵二叉排序树顺序存储结构： typedef struct Tnode int data;struct T
7、node *lchild,*rchild;*node,BSTnode;链式存储结构：typedef struct node/记录类型KeyType key;/关键字项InfoType data;/其他数据域struct node *lchild,*rchild; /左右孩子指针 BTNode;5.2 二叉排序树的中序遍历(以顺序为例)中序遍历二叉树算法的框架是：若二叉树为空，则空操作；否则中序遍历左子树(L)；访问根结点(V)；中序遍历右子树(R)。中序遍历二叉树也采用递归函数的方式，先访问左子树,然后访问根结点,最后访问右子树.直至所有的结点都被访问完毕。核心代码：status Inorde
8、rTraverse(node *t) /*中序遍历函数*/if(*t)if(InorderTraverse(&(*t)-lchild)/*中序遍历根的左子树*/printf(%d ,(*t)-data); /*输出根结点*/ if(InorderTraverse(&(*t)-rchild); /*中序遍历根的右子树*/return OK ;5.3 二叉排序树中元素的查找(以顺序为例)在二叉排序树上进行查找，是一个从根结点开始，沿某一个分支逐层向下进 行比较判等的过程。若二叉排序树为空，则查找失败。否则，将根结点的关键字与待查关键字进行比较，若相等，则查找成功；若 根节点关键字大于待查值，则进入
9、左子树重复次步骤，否则，进入右子树进行此 步骤；若在查找过程中遇到二叉排序树的叶子节点时，还没有找到待查节点，则 查找不成功。核心代码：status SearchBT(node t,int key,node f,node *p) /*查找函数*/if(!t)*p=f;return ERROR;/*查找不成功*/elseif(key=t-data)*p=t;return OK; /*查找成功*/elseif(keydata) SearchBT(t-lchild,key,t,p); /*在左子树中继续查找*/elseSearchBT(t-rchild,key,t,p); /*在右子树中继续查找*/
10、5.4 二叉排序树中元素的删除(以顺序为例)对于二叉排序树，删去树上的一个结点相当于删去有序序列中的一个记录， 只要在删除某个结点之后依旧保持二叉排序树的特性即可。在二叉排序树中删除 节点，首先要进行查找操作，以确定被删除的节点是否在二叉排序树中。若不在，则不做任何操作；否则，假设要删除的节点为*P,节点*P的父节 点为*f,并假设*P是*f的左孩子。根据被删除节点*P有无孩子，删除部分可做 以下 3 中情况讨论：(1) 若*P为叶子节点，则可令其父节点*f的左孩子指针域为空，直接将其 删除。(2) 若*p节点只有右子树或左子树，则可以将p的左子树或右子树直接改 为其双亲节点 f 的左子树。(
11、3) 若*p既有左子树又有右子树；将节点*s为*p的中序前驱。首先找到 *p的中序前驱节点*S,然后用节点*S的值代替节点*p的值，再将节点*S删除，节点*s的原左子树改为*s的双亲节点*q的右子树;核心代码：node Delete(node t,int key)/*删除函数*/node p=t,q=NULL,s,f; while(p!=NULL)/*查找要删除的点*/if(p-data=key)break;q=p; if(p-datakey) p=p-lchild; elsep=p-rchild; if(p=NULL)return t;/*查找失败*/if(p-lchild=NULL)/*p
12、 指向当前要删除的结点*/if(q=NULL) t=p-rchild; /*q 指向要删结点的父母*/ elseif(q-lchild=p) q-lchild=p-rchild; /*p 为 q 的左孩子*/ elseq-rchild=p-rchild;/*p 为 q 的右孩子*/ free(p);else/*p 的左孩子不为空*/f=p;s=p-lchild; while(s-rchild)/*左拐后向右走到底*/f=s; s=s-rchild;if(f=p) f-lchild=s-lchild; /*重接 f 的左子树*/ else f-rchild=s-lchild;/*重接 f 的右子树*/p-data=s-data;free (s); return t;5.5 二叉排序树的插入(以顺序为例)在二叉排序树中插入一个新节点，首先要查找该节点在二叉排序树中是否已 经存在。若二叉排序树中不存在关键字等于 x 的节点，则插入。将一个关键字值为 x 的节点 s 插入到二叉
