2015年数据结构课程设计报告.pdf

《2015年数据结构课程设计报告.pdf》由会员分享，可在线阅读，更多相关《2015年数据结构课程设计报告.pdf（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课程设计报告撰写要求（-）纸张与页面要求1.采用国际标准A4型打印纸或复印纸，纵向打印。2.封页和页面按照下面模板书写（正文为：小四宋体1.5倍行距）。3.图表及图表标题按照模板中的表示书写。（二）课设报告书的内容应包括以下各个部分：（按照以下顺序装订）1.封页（见课设模版）2.任务书（学生教师均要签字，信息填写完整）3.目录4.正文一般应包括以下内容：（1）题目介绍和功能要求（或描述）课程设计任务的详细描述（注意不能直接抄任务书），将内容做更详细的具体的分析与描述;（2）系统功能模块结构图绘制系统功能结构框图及主要模块的功能说明；（3）使用的数据结构的描述：数据结构设计及用法说明；（

2、4）涉及到的函数的描述；（5）主要算法描述（程序流程图）（6）给出程序测试/运行的结果设计多组数据加以描述（包括输入数据和输出结果）（7）课程设计的总结及体会（8）参考文献格式要求：1作者，等.书名.出版地：出版社，出版年5.附录：程 序 清 单（应带有必要的注释）沈阳航空航天大学课 程 设 计 报 告课程设计名称：数据结构课程设计课程设计题目：二叉排序树的插入、删除算法院（系）：计算机学院专 业：计算机科学与技术班 级：24010101学 号：2012040101036姓 名：周勇指导教师：许清沈阳航空航天大学课程设计报告沈阳航空航天大学课程设计报告目 录1题目介绍和功能要求.11.1 课程

3、设计的任务.11.2 程序实现的功能.12概要设计.22.1 系统功能模块结构图.23数据结构的描述.23.1 数据结构设计.24详细设计.34.1 算法描述.34.2 函数的描述（程序流程图）.错误！未定义书签。5调试分析.95.1 程序运行的结果.9参考文献.13附录（关键部分程序清单）.14课程设计总结.19沈阳航空航天大学课程设计报告1题目介绍和功能要求1.1 课程设计的任务1.给定一组关键字，生成一棵二叉排序树；2.删除该二叉排序树中的指定节点，删除后二叉排序树的性质不发生改变;3.用直观、易于理解的形式来演示二叉树的插入、删除过程；4.对二叉排序树T作中序遍历，输出结果。5.设计一

4、个小型的集成环境，开辟儿个操作窗口，功能操作在该集成环境中完成。1.2 程序实现的功能1.给定一组关键字，运用程序生成一棵二叉排序树。2.根据提示，进行将要进行的操作。3.输入一数据，程序将这一数据插入进已经排好序的二叉排序数中，且插入后的二叉排序树的性质不发生改变。4.将插入数据后的二叉排序树按中序遍历输出5.将数据进行删除操作，输入将要删除的数据值，程序进行查找，如果二叉树中含有将要删除的数据，则进行删除操作，并且二叉排序树的性质不会发生变化；如果二叉树中没有找到要删除的数据，则不进行删除操作。I沈阳航空航天大学课程设计报告2概要设计2.1 系统功能模块结构为了完成所需的功能，需要的函数及

5、其功能如下：main()：主函数模块InsertBST()：插入一个新节点CreateBST()：创建一棵二叉排序树Inorder()：对二叉排序树进行中序遍历menu()：主函数显示菜单模块DeleteBST()：删除节点3数据结构的描述3.1 数据结构设计选择链式结构存储。用链表的方式构造节点，存储二叉排序树中的节点,节点类型和指针类型如下：typedef struct node(int key;int other;struct node*lchild,*rchild;Bstnode;2沈阳航空航天大学课程设计报告4详细设计4.1算法描述1、二叉排序树的节点插入算法在二叉排序树中插入一个新

6、节点，首先要查找该节点在二叉排序树中是否已经存在。若二叉排序树中不存在关键字等于X的节点，则插入。将一个关键字值为X的节点S插入到二叉排序树中，可以用下面的方法：(1)若二叉排序树为空，则关键字为X的节点S成为二叉排序树的根，(2)若二又排序树非空，则将x与二叉排序树根进行比较，如果x的值等于根节点关键值，则停止插入；如果x的根节点值小于根节点关键值，则将x插入左子树；如果X的值大于根节点关键字的值，则将X插入右子树。在左右两个子树的插入方法与整个二叉排序树相同。算法如下：Bstnode*InsertBST(Bstnode*t,int x)插入Bstnode*s,*p,*f;p=t;while

7、(p!=NULL)f=p；if(x=p-key)return t;序插入查找过程中，f指向*p的父节点二叉排序树中已有关键字为x的元素，无if(xkey)p=p-lchild;else p=p-rchild;s=(Bstnode*)malloc(sizeof(Bstnode);s-key=x;s-lchild=NULL;s-rchild=NULL;if(t=NULL)return s;if(xkey)f-lchild=s;else f-rchild=s;return t;原树为空，新节点成为二叉排序树的根新节点作为*f的左孩子新节点作为*f的右孩子3沈阳航空航天大学课程设计报告2、二叉排序树的

8、节点删除算法在二叉排序树中删除节点，首先要进行查找操作，以确定被删除的节点是否在二叉排序树中若不在，则不做任何操作；否则，假设要删除的节点为*p,节点*p的父节点为*f,并假设*p是*f的左孩子。根据被删除节点*p有无孩子，删除部分可做以下3中情况讨论：(1)若*p为叶子节点，则可令其父节点*f的左孩子指针域为空，直接将其删除。(2)若*p节点只有右子树或左子树，则可以将p的左子树或右子树直接改为其双亲节点f的左子树。(3)若*p既有左子树又有右子树.；将节点*s为*p的中序前驱。首先找到*p的中序前驱节点*s,然后用节点*s的值代替节点*p的值，再将节点*s删除，节点*s的原左子树改为*s的

9、双亲节点*q的右子树；算法如下：Bstnode*DeleteBST(Bstnode*t,int k)删除Bstnode*p,*f,*s,*q;p=t;f=NULL;while(p)if(p-key=k)break;f=p;查找关键字为k的待删节点*p找到，则退出循环节点*f为节点*p的父节点if(p-keyk)p=p-lchild;else p=p-rchild;if(p=NULL)return t;若找不到，则返回原二叉排序树的根指针if(p-lchild=NULL)ll(p-rchild=NULL)若*p 无左孩子或右孩子if(f=NULL)若*p是原二叉排序树的根if(p-lchild=

10、NULL)t=p-rchild;else t=p-lchild;else if(p-lchild=NULL)若*p无左孩子4沈阳航空航天大学课程设计报告if(f-lchild=p)f-lchild=p-rchild;/p 是*f 的左孩子else f-rchild=p-rchild;else if(f-lchild=p)f-lchild=p-lchild;else f-lchild=p-lchild;free(p);)else q=p;s=p-lchild;while(s-rchild)q=s;s=s-rchild;)if(q=p)q-lchild=s-lchild;p-key=s-key;f

11、ree(s);)return t;)4.2算法描述(程序流程图)主函数流程图：/若*P 无右孩子/p是*f 的左孩子/p是*f 的右孩子若p 有左右子树在*P 的左子树中查找最右下节点将*S的值赋给*P5沈阳航空航天大学课程设计报告6沈阳航空航天大学课程设计报告子函数流程图：插入子函数InsertBST()的流程图:图(b)子函数InsertBST()的流程图7沈阳航空航天大学课程设计报告子函数Bsearch(p)的流程图图(c)子函数Bsearch(p)的流程图8沈阳航空航天大学课程设计报告5调试分析程序运行的结果1、输入节点信息:I C:USERSHPDESKTOP新建文件夹Debug二叉

12、排序的课程设计.exe=回J，束0结2,3粪输2序13请56中节?8历23并7为，6列43息59序信3得42点所08，9义304?85976891-插入节点-2-删除节点-3-退出-请选择操作:图（1）输入节点信息图9沈阳航空航天大学课程设计报告2、显示菜单后，根据提示选择操作，选择插入一个新节点 CUSERSHPDESKTOP新建文件夹Debug二叉排序钝课程设计.exe.1 =1回点i所入3遍输2序13请56中HT78历23并7为，6列43息59序信3得42以437808959束0结267981-插入节点-2-删除节点-3-退出-878列59日沅60彳5:?所点历43节遍:1的序42:作操

13、个，23操莘-后举迦入入13避住de67图（2）插入新节点图10沈阳航空航天大学课程设计报告3、继续选择操作，删除一个已有的节点j 回 J aJ 70 78 987 请输入节点信息，并 以 结 束：56 23 78 13 59 67 43 98 42 0中序遍历所得序列为：13 23 42 43 56 59 67 78 98 C:USERSHPDESKTOP新建文件夹Debug二如密树课程设计.exe，67?0?81-插入节点-2-删除节点-3-退出-况59况67序序。得56得59:?所2所点历43:4历56节遍据遍:1的序42:2瞽43:-备中作操个,23襄,23操择-后择删后择选人入13选

14、人除13选主主月3刖主QE图（3）查找一个已有节点图|沈阳航空航天大学课程设计报告4.若 操 作 已 完 成，则 退 出 程 序。C:USERSHPDESKTOPSfttDebug-EJ?15riSei+.exe3%2序1356中，6列4330箔4 208(9以43:井7为7859?6981-插入节点-2-删除节点-3-退出-67707898耳59日于60彳5:7所点历43节遍707898du7歹6得592月:4历56t:1的序42:2瞽43:3裔中作y操个，23，23操an莘-后择删后择S因人入13四IA除13因es主主BEA刖主AEI-fw-kMpyt O图（4）退出图12沈阳航空航天大学

15、课程设计报告参考文献1 严蔚敏，吴伟民.数据结构（C语言版）M.北京：清华大学出版社,20062 吕国英.算法设计与分析M.北京：清华大学出版社,20063 徐宝文，李志.C程序设计语言M.北京：机械工业出版社,20044 谭浩强.C程序设计（第三版）.北京：清华大学出版社，200913沈阳航空航天大学课程设计报告附 录(关键部分程序清单)#include#include#include 符号常量#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define MAXSIZE 30#define OVERFLOW-2自定义类型lyp

16、edef int Status;typedef int TElemType;typedef struct BiTNodeTElemType data;struct BiTNode*lchird,*rchild;)BiTNode,*BiTree;/SearchBST查找关键字key的结点Status SearchBST(BiTree T,TElemType key,BiTree f,BiTree*p)(if(!T)(*p=f;return FALSE;)else if(T-data=key)(*p=T;return TRUE;)else if(keydata)return SearchBST(T

17、-lchird,key,T,p);左子树中继续查找，找后继结点elsereturn SearchBST(T-rchild,key,T,p);右子树中继续查找14沈阳航空航天大学课程设计报告/SearchBST/InsertBST插入二叉排序树Status InsertBST(BiTree*T,TElemType key)(BiTree p,s;if(!SearchBST(*T,key,NULL,&p)(s=(B iTree)malloc(sizeof(B iTNode);s-data=key;s-lchird=s-rchild=NULL;if(!p)二叉树若为空*T=s;else if(key

18、data)p-lchird=s;被插入的结点为左孩子elsep-rchild=s;被插入的结点为右孩子return TRUE;)elsereturn FALSE;/InsertBSTStatus Delete(BiTree*p)(BiTree q,s;if(*p)-rchild=NULL)(q=*p；*p=(*p)-lchird;free(q);)else if(*p)-lchird=NULL)(q=*p；*p=(*p)-rchild;free(q);)else(q=*p；s=(*p)-lchird;15沈阳航空航天大学课程设计报告while(s-rchild)(q=s;s-rchild;)(

19、*p)-data=s-data;if(q!=*p)q-rchild=s-lchird;elseq-lchird=s-lchird;free(s);)return TRUE;)Status DeleteBST(BiTree*T,int key)(if(!*T)return FALSE;else(if(key=(*T)-data)return Delete(T);else if(keydata)return DeleteBST(&(*T)-lchird,key);elsereturn DeleteBST(&(*T)-rchild,key);void Inorder(BiTreeT)中序遍历函数，中

20、序遍历二叉排序树可以得到个关键字的有序序列if(T)(Inorder(T-lchird);printf(%4d,T-data);Inorder(T-rc hild);若二叉树不空中序遍历左子树/访问根节点中序遍历右子树void main()int i,Num;16沈阳航空航天大学课程设计报告int aMAXSIZEJ=0;BiTree T=NULL,p=NULL;/printf(”请输入生成排序树的数据元素个数:)scanf(d，&Num);printf(”请输入生成排序树的数据:n)；for(i=0;iNum;i+)(读入一个数并插入到二叉生成树中scanf(M%dM,&ai);Insert

21、BST(&T,ai)；插入的过程相当于构建排序二叉树)printf(中序遍历如下Inorder(T);printf(nnn);getchar();getchar();while(l)system(uclsn);printf(n -1 n);printf(|1-查找节点-I n);printf(|-1 n);printf(|2-插入节点-I n);printf(|-1 n);printfC|3-删除节点-I n);printf(|-1 n);printfC I 4-退出-|n);printf(1-1 n);int w;printf(nn 请输入你要的操作:n);scanf(%d,&w);if(4

22、=w)break;17沈阳航空航天大学课程设计报告elseswitch(w)(case 1:printf(请输入你要查找的数:n)int key,h;scanf(n%dn,&key);h=SearchBST(T,key,NULL,&p);/if(TRUE=h)printf(此数存在!n“);elseprintf(此数不存在!n“)；getchar();getchar();break;)case 2:printf(请输入你要插入的数:n)；int s,k;scanf(H%dn,&s);k=SearchBST(T,s,NULL,&p);/if(TRUE=k)printf(此数已经存在排序树中！nu

23、);else(InsertBST(&T,s);printf(Hn 插入成功!nH);printf(中序遍历如下:n);Inorder(T);printf(nn);getchar();getchar();)break;case 3:(printff请输入你要删除的数:n)；int u,l;18沈阳航空航天大学课程设计报告scanf(n%d&u);l=SearchBST(T,u,NULL,&p);/if(FALSE=l)printf(删除操作失败！原排序树中不存在此数!n);else(DeleteBST(&T,u);printf(”n 删除成功!nH);printf(中序遍历如下:n)；Inord

24、er(T);printf(“n)；getchar();getchar();)void menu()菜单函数(printf(n -1 n);printf(|1-插入节点-|n);printf(|-1 n);printf(|2-删除节点-I n);printf(|-1 n);printf(|3-退出-|n);printf(1-1 n);void main()主函数(Bstnode*tree,*p;int seai,deli,x;19沈阳航空航天大学课程设计报告int k,flag=1;printf(请输入节点信息，并 以 0 结束:n)；tree=CreateBST();创建一个新的二叉树prin

25、tf(中序遍历所得序列为:nn);Inorder(tree);引用中序遍历函数printf(nn);menu();引用菜单函数while(flag)(printf(请选择操作scanf(n%dn,&k);switch(k)case 1:printf(插入一个新的节点scanf(d”,&x);InsertBST(tree,x);引用插入函数printf(插入后，中序遍历所得序列:n“);Inorder(tree);引用中序遍历函数printf(nn);break;case 2:printf(输入删除的数据scanf(%d,&deli);tree=DeleteBST(tree,deli);引用删除函数printf(删除后，中序遍历所得序列:n)Inorder(tree);引用中序遍历函数printf(n);break;)case 3:退出flag=0;break;)20沈阳航空航天大学课程设计报告21沈阳航空航天大学课程设计报告课程设计总结：指导教师评语：指导教师（签字）：_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 年_ 月 _日课程设计成绩22