数据结构课设-二叉排序树合编.doc

课程设计(论文)任务书 　学院　　 　专业　 　班 一、课程设计(论文)题目　 二、课程设计(论文)工作自 年 月 日起至 年 月 日止。 三、课程设计(论文) 地点: 四、课程设计(论文)内容要求： 1．本课程设计的目的 （1）使学生熟练掌握抽象数据类型的组织和定义； （2）使学生熟练掌握数据类型的定义和实现； （3）培养学生组织和分析数据的能力； （4）培养学生分析和应用基于不同数据结构的算法的能力； （5）提高学生的科技论文写作能力。 2．基本要求： 每位同学在以下题目中任选一题（在方框中打勾），独立完成课程设计： □ 二叉排序树：将输入的n个关键字构建成为一棵二叉排序树，并按照层次输出。 □ 文档检索系统：实现一个信息检索系统，包含至少10条记录。 （1）每条记录至少包含4个数据项 （2）能够按照不同数据项的关键字进行查询。 □ 校园导游咨询：参见《数据结构题集》P151。 3．课程设计论文编写要求 （1）要按照书稿的规格打印誊写课设报告； （2）报告分为封面、任务书（本文档）、正文、课程设计体会和参考文献四部分。 学生签名： 2014年 12月 22日 课程设计(论文)评审意见 （1）题目分析 （20分）：优（　）、良（　）、中（　）、一般（　）、差（　）； （2）流程分析　 （30分）：优（　）、良（　）、中（　）、一般（　）、差（　）； （3）数据定义　 （30分）：优（　）、良（　）、中（　）、一般（　）、差（　）； （4）代码编写　 （10分）：优（　）、良（　）、中（　）、一般（　）、差（　）； （5）创新能力　 （10分）：优（　）、良（　）、中（　）、一般（　）、差（　）； （6）格式规范性、设计态度及考勤是否降等级：是（　）、否（　） 评阅人： 　　　 职称： 讲 师 2014年12 月 31日 正 文 数据结构定义 抽象数据类型 本设计中用到的数据结构ADT定义如下： ADT?BinaryTree{? 数据对象D：D是具有相同特性的数据元素的集合。 数据关系 R：若D为空集，则称为二叉树； ????若D仅含有一个数据元素，则R为空集，否则R={H}，H是如下二元关系：? (1)?在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；? (2)? 若D-{root}≠NULL，则存在D-{root}的一个划分D1,D2,D3,??,Dm(m0)，对于任意j≠k(1≤j,k≤m)有Dj∩Dk=NULL,且对任意的i(1≤i≤m)，唯一存在数据元素xi∈Di有root,xi∈H;? (3)?对应于D-{root}的划分，H-{root,xi,?,root,xm}有唯一的一个划分H1，H2,?,Hm(m0)，对任意j≠k(1≤j,k≤m)有Hj∩Hk=NULL，且对任意i(1≤i≤m),Hi是Di上的二元关系，(Di,{Hi})是一棵符合本定义的树，称为根root的子树。 基本操作P：? CreateTree(T,definition);? 初始条件：definition给出二叉树T的定义。? 操作结果：按definition构造二叉树T。? ?InsertChild(T,p,I,c);? 初始条件：树Ｔ存在，ｐ指向Ｔ中某个结点，1≤i≤p指结点的度＋１，非空树ｃ与Ｔ不相交。? 操作结果：插入c为Ｔ中ｐ指结点的第ｉ棵子树。 DeleteChild(T,p,i);? 初始条件：树T存在，p指向T中某个结点，1≤i≤p指结点的度。? 操作结果：删除Ｔ中ｐ所指结点的第ｉ棵子树。? LevelOrderTraverse(T,visit());? 初始条件：树T存在，visit是对结点操作的应用函数。? 操作结果：层序遍历T，对每个结点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败。? }ADT?BinaryTree 存储结构定义 数据存储结构的C语言定义如下： #define maxx 1000 typedef struct node { int key; struct node *lchild; struct node *rchild; }BSTNode; 基本操作 数据结构的基本操作实现如下： /** 菜单界面 **/ void showmenu() { system(cls); printf(\n\n\n\n); printf(\t\t 请选择你要