数据结构设计说明书书

来源：智榕旅游

摘要

数据结构是研究与数据之间的关系，我们称这一关系为数据的逻辑结构，简称数据结构。当数据的逻辑结构确定以后，数据在物理空间中的存储方式，称为

数据的存储结构。相同的逻辑结构可以具有不同的存储结构，因而有不同的算法。

本次课程设计，程序中的数据采用“树形结构”作为其数据结构。具体采用的是“二叉排序树”，并且使用“一维数组”来作为其存储结构。一维数组顺序表存储结构是用一组地址连续的存储单元依次自上而下、自左而右存储完全二叉树上的结点元素；本课程设计实现了二叉排序树的创建、中序遍历、计算二叉排序树的平均查找长度和删除二叉排序树中某个结点。

本课程主要介绍了本课题的开发背景，所要完成的功能和开发的过程。重点说明了系统的设计思路、总体设计、各个功能模块的设计与实现方法。

关键词：二叉排序树的实现；C语言；数据结构；线性表；顺序表；中序遍历。

摘要.............................................................. I 1 课题背景的介绍.................................................... 1

1.1 课题背景 ..................................................... 1 1.2 目的......................................................... 1 2 需求分析.......................................................... 1

2.1课程设计题目、任务及要求 ....................................... 1 2.2课程设计思想 .................................................. 2 3 系统总体设计...................................................... 3

3.1 系统模块划分.................................................. 3 3.2 二叉排序树的生成过程 .......................................... 3 3.3 主要功能模块设计 .............................................. 3 4 系统详细设计...................................................... 5

4.1 主函数菜单模块 ................................................ 5 4.2 查找模块 ..................................................... 6 4.3 插入模块 ..................................................... 7 4.4 中序遍历模块.................................................. 8 4.5删除模块...................................................... 9 5 系统连编与运行.................................................. 11 6 总结.......................................................... 12 参考文献........................................................... 13

附录.....................................................................14

A）课题背景的介绍

1.1 课题背景

随着经济的迅速发展，各行各业纷纷应用计算机数据信息管理。当然数据信息是一个很笼统的概念，随着现代信息的大量增加，其处理难度也越来越大，如何对各个数据信息进行更好的树立，这就是我们研究这个课题的目的。

在计算机迅速发展的今天，将计算机这一信息处理器应用于实际数据问题问题的信息计算已是势必所然，而且这也将数据信息处理带来前所未有的改变。采用计算机对数据的信息处理是信息科学化和现代化的重要标志，它也给各行各业带来了明显的经济效益。主要体现在：极大地提高了工作人员的工作效率，大大地减少了以往的手工操作的各种弊端，同时也加强和规范掌握对于数据信息的计算。 1.2 目的

本课题运用C语言进行开发，C语言能够简单的进行编译一些程序，来实现对一些问题的解决。它虽然比较简单的处理一些问题，但却有更高的效率。它能够被大多数用户所接受，因为它能够呈现出清晰的界面，是人们能够很好的理解。能在一些方面给人们更好的服务，成为人们的好帮手。

经过这一个学期对《数据结构》的学习，我们都学到了不少东西，可能有些学的还不够理想，但无论如何这些知识都为我们的下一步学习打下了坚实的基础。做这么一个课程设计，一方面是为了检查我们一个学期以来的学习成果，另一方面也是为了让我们进一步的掌握和运用它，同时也让我们认清自己的不足之处和薄弱环节，加以弥补和加强。

B）需求分析

2.1课程设计题目、任务及要求

二叉排序树。用顺序表(一维数组)作存储结构

(1)以回车('\\n')为输入结束标志,输入数列L，生成一棵二叉排序树T； (2)对二叉排序树T作中序遍历,输出结果；

(3)计算二叉排序树T查找成功的平均查找长度,输出结果；

(4)输入元素x,查找二叉排序树T:若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”； 2.2课程设计思想

建立二叉排序树采用边查找边插入的方式。查找函数采用递归的方式进行查找。如果查找成功则不应再插入原树，否则返回当前结点的上一个结点。然后利用插入函数将该元素插入原树。

对二叉树进行中序遍历采用递归函数的方式。在根结点不为空的情况下，先访问左子树，再访问根结点，最后访问右子树。

计算二插排序树的平均查找长度时，仍采用类似中序遍历的递归方式，用s记录总查找长度，j记录每个结点的查找长度，s置初值为0，采用累加的方式最终得到总查找长度s。平均查找长度就等于s/i(i为树中结点的总个数)。

删除结点函数，采用边查找边删除的方式。如果没有查找到，则不对树做任何的修改；如果查找到结点，则分四种情况分别进行讨论：

1、该结点左右子树均为空； 2、该结点仅左子树为空； 3、该结点仅右子树为空； 4、该结点左右子树均不为空。

C）系统总体设计

3.1 系统模块划分

二叉排序树是一种动态树表。

二叉排序树的定义：二叉排序树或者是一棵空树，或者是一棵具有如下性质的二叉树：

⑴ 若它的左子树非空，则左子树上所有结点的值均小于根结点的值； ⑵ 若它的右子树非空，则右子树上所有结点的值均大于根结点的值； ⑶ 左、右子树本身又各是一棵二叉排序树。 3.2 二叉排序树的生成过程

二叉排序树的生成，采用递归方式的边查找边插入的方式。如图初始化数组插入结点是空树插入否在左子树中查找否在右子树中查找插入

是插入 3.3 主要功能模块设计

程序主要设计了五个功能：首先是创建二叉排序树，完成后出现任务菜单，菜单中设计了四个模块：退出，中序遍历，计算平均查找长度和删除结点。

主函数流程如下： Switch(0) 否 Switch(1) 否 Switch(2) 否 Switch(3) 否 default 否图3.1.1主函数流程图

是是提示出错是是删除结点是计算平均查找长度是是中序遍历是 Exit(0)退出是创建二叉排序树

4 系统详细设计

4.1 主函数菜单模块

该模块功能主要是给用户提供清晰的可操作界面，易于人机操作，并能很好的调用其他各模块，使程序更加优化，思路更加清晰，结构更加明了，提高了程序的实用性。其算法如下：

Void main() { node T=NULL; Int num; Int ch=0; Node p=NULL;

Printf(\"please input a list o numbers end with zero:\"); Do{ scanf(\"%d,&num\");

If(!num) printf(\"you have finished your input!\\n\"); Else insertBST(&T,num); } while(num);

Printf(\"\\n\\n--the menu of the opperation---\\n\");/*主程序菜单*/ Printf(\"\\n 0: exit\");

Printf(\"\\n 1: inorder travel the tree\"); Printf(\"\\n 2: delete\"); While(ch==ch)

{ printf(\"\\n choose the opperation to continue:\");

Scanf(\"%d，&ch\"); Switch(ch){

Case 0: exit(0); /*0--退出*/

Case 1: printf(\" The result of inorder traverse is:\\n \"); Inorder Traverse(&T); /*1--中序遍历*/ Break;

Case 2: printf(\" Please input the number you want to delete:\"); Scanf(\"%d,&num\"); /*3--删除某个结点*/

If(searchBST(T,num,NULL,&p)) {

T=delete(T,num);

Printf(\" You have delete the number successfully!\\n \");

InorderTravers(&T); }

Else printf(\" No node %d you want to delete!\Break;

Default: printf(\"You input is wrong!Please input again!\\n\"); Break;

Default: printf(\"Your input is wrong!Please input again!\\n\"); Break; /*输入无效字符*/ } } }

4.2 查找模块

该模块是给用户提供查找功能。其查找过程是：若二叉排序树为空，则查找失败，结束查找，返回信息 NULL；否则，将要查找的值与二叉排序树根结点的值进行比较，若相等，则查找成功，结束查找，返回被查找到结点的地址，若不等，则根据要查找的值与根结值的大小关系决定时到根结点的左子

树还是右子树中继续查找（查找过程同上），直到查找成功或者查找失败为止。其算法如下:

scarchBST(node,int key,node f,node *p) /*查找函数*/ {

If(!t) {*p=f;return(1);} /*查找不成功*/ Else if(key==t->data) searchBST(t->lchild,key,t,p); /*在左子树中继续查找*/

Else searchBST(t->rchild,key,t,p); /*在右子树中继续查找*/

}

4.3 插入模块

在二叉排序树种插入新结点，要保证插入后的二叉树仍符合二叉排序树的定义。插入过程；若二叉排序树为空，则待插入结点*p作为根结点插入到空树中；当非空时，将待插结点关键字p->item和树根关键字t->item进行比较，若p->item=t->item，则无须插入，若p->itemitem，则插入到根的左子树中，若p->item>t->item，则插入到根的右子树中。而子树种的插入过程和在树中的插入过程相同，如此进行下去，直到把结点*p作为一个新的树叶插入到二叉排序树中，或者直到发现数已有相同关键字的结点为止。其算法如下：

insertBST（node *t,int key） /*插入函数*/

{

Node p=NULL,s=NULL;

If(!searchBST(*t,key,NULL,&p)) /*查找不成功*/ {

S=(node)malloc(size(BSTnode)); S->data=key;

S->lchild=s->rchild=NULL;

If(!p) *t=s; /*被插结点*s为新的根结点*/

Else if(keydata) p->lchild=s; /*被查结点*s为左孩子*/

Else p->rchild=s;/*被插结点*s为右孩子*/ Return（1）； }

Else return(0); /*树中已有关键字相同的结点，不再插入*/ }

4.4 中序遍历模块

遍历（Traversal）是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。二叉树共有三个部分组成，即根结点，根结点的左子树，根结点的右子树。限定以从左至右方式共有三种遍历方式，即前序遍历，中序遍历，后序遍历。中序遍历的原则：若被遍历的二叉树为非空，则依次执行如下操作：

A）以中序遍历方式遍历左子树； B）访问根结点；

C）以中序遍历方式遍历右子树。其算法如下： inorderTraverse(node *t) /*中序遍历函数*/ {

If(*t){

If(inorderTraverse(&(*t)->lchild)) /*中序遍历根的左子树*/ Printf（\"%d \中序遍历根的右子树*/ }

Return(1); }

4.5删除模块

删除模块：删除结点函数，采用边查找边删除的方式。如果没有查找到，则不对树做任何的修改；如果查找到结点，则分四种情况分别进行讨论： D）该结点左右子树均为空，可以直接进行删除；

E）该结点仅左子树为空，右子树不为空，用右子树的根结点取代被删除结点的位置；

F）该结点仅右子树为空，左子树不为空；

G）该结点左右子树均不为空，找到被删除结点右子树中最小的结点，并用该结点取代被删除节点的位置。其算法如下：

Node Delete(node,int key) /*删除函数*/ {

Node p=t,q=NULL,s,f; While(p!=NULL) /*查找要删除的点*/ {

If(p->data==key) break; Q=p;

If(p->data>key) p=p->lchild; Else p=p->rchild; }

If(p==NULL) return t; /*查找失败*/

If(p->lchild==NULL) /*p指向当前要删除的结点*/ {

If(q==NULL) t=p->rchild; /*q指向要删除的父母*/

Else if(q->lchild==p) q->lchild=p->rchild; /*p为q的左孩子*/

Else q->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; /*重接f的左子树*/ Esle f->rchild=s->lchild /*重接f的右子树*/ P->data=s->data; Free(s); }

Return t; }

5 系统连编与运行

一个应用系统设计和创建完成后，还必须进行连编，以便生成一个可执行文件供最终用户使用。连编完成后还要运行，以检查整个系统的完整性和准确性，同时还可增加程序代码的保密性。

（1）先进行编译，编译过之后再选择计算机运行。如图9所示：

6 总结

通过这次课程设计我也着实又感受了一次编程的乐趣，从中也学到了不少知识。我在学习运用数据结构编程之前，并没能深刻体会到这一点，直到这次课程设计，我才有所领悟。

这次实验中我也出现过一些比较严重的错误。在用一维数组顺序表结构编写程序时我错误的运用静态链表来实现函数功能。这是我对基本概念理解的模糊不清造成的。我原以为只要采用一维数组作为存储结构它就一定也是顺序表结构，而实质上这根本是两个不相干的概念。后来在同学的指点下我意识到自己的错误。不过收获也很不少。至少我又练习了运用静态链表来实现同样的功能，同时我也发现两者在很多函数上是互通的，只需稍作修改即可移植。

另外程序的不足之处是不能实现对0这个数字的存储，可以通过改变数字的存储结构方式来实现，如使用二叉链表来作为数据的存储结构，即可实现该功能。

总之，我会继续我的兴趣编写程序的，相信在越来越多的尝试之后，自

己会不断进步不断提高的。

参考文献

[1] 谭浩强.C程序设计[M].北京：清华大学出版社. 2005.

[2] 严蔚敏. 数据结构（C语言版） [M]. 北京：清华大学出版社. 2008. [3] 陈雁.数据结构 [M].北京：高等教育出版社，2004. [4] 张磊.C程序设计教程.北京：中国铁道出版社.2007.

[5] 冯舜玺.数据结构与算法分析—C语言描述（原书第2版）.北京：机械工业出版社，2004.1

[6]张海藩.《软件工程》，清华大学出版社，2008

[7]杨明军、董亚卓、汪黎.《C++实用教程（第一版）》.人民邮电出版社.2002 [8]张荣梅、梁晓林.《Visual C++实用教程（第一版）》.冶金工业出版社.2004

附录

二叉链表存储结构: 1.源程序:

#include #include using namespace std; bool rut=false; class jie{ public: int data; jie *left; jie *right; };

void insert1(jie **root,jie *s)//插入 {

if(*root==NULL){ *root=s;} else

if((*root)->data>s->data)insert1(&(*root)->left,s);

else insert1(&(*root)->right,s); }

void create(jie **root,int n,int a[])//以

数组A构造二叉树（root为根）

{

jie *s;

for(int i=1;i<=10;i++) {

s=new jie; s->data=a[i];

s->left=NULL;s->right=NULL; insert1(&(*root),s); //*root=s; }

//cout<<\"check successfully\\n\"; }

void check(jie *root,int key)//检查某节点

是否存在在以root为根的树里

{

if(root->data==key)rut=true; else if(root==NULL) rut=false; else

if(root->data>key&&root->left!=NULL)check(root->left,key);

else

if(root->dataright!=NULL)check(root->right,key);

}

void ergotic(jie *root)//中序遍历 {

jie *p=root; if (p!=NULL) {

ergotic(p->left); cout<data<<\"\\"; ergotic(p->right); } }

jie *fin(jie *root)//找以root为根的最左

的不为空的节点的父节点

{

jie *q=root; jie *p=q;

while(q->left!=NULL){p=q;q=q->left;} return p; }

void del(jie *root,int key)//删除节点 {

jie *q=root;jie *f=q;

while(q->data!=key&& q!=NULL) {

if(q->data>key){f=q;q=q->left;} else{f=q; q=q->right;} }

if(q!=NULL&&f->left==q)//q是其父节点

f的左孩子时

{

jie *find,*p=NULL;

if(q->left==NULL&&q->right==NULL)f->left=NULL;

else

if(q->left!=NULL&&q->right==NULL){f->left=q->left;}

else if(q->right->left!=NULL)

{find=fin(q->right);p=find->left;find->left=NULL;p->left=q->left;p->right=q->right;f->left=p;}

else

if(q->right->left==NULL){q->right->left=q->left;f->left=q->right;}

}

else if(q!=NULL&&f->right==q)//q是其

父节点f的右孩子时

{

jie *find,*p=NULL;

if(q->left==NULL&&q->right==NULL)f->right=NULL;

else

if(q->left!=NULL&&q->right==NULL){f->right=q->left;}

else if(q->right->left!=NULL)

{find=fin(q->right);p=find->left;find->left=NULL;p->left=q->left;p->right=q->right;f->right=p;}

else

if(q->right->left==NULL){q->right->left=q->left;f->right=q->right;}

} }

int main() {

\\n\";

create(&root,10,a);//为根构造二叉排序树

\\n\";

int a[11];//a[0]忽略不用 printf(\"请输入11个整数:\\n\"); int i=1;

for(i=1;i<=10;i++) {

scanf(\"%d\}

system( \"cls \") ;

cout<<\"在插入二叉排序树之前的序列顺序：

for(i=1;i<=10;i++) cout<jie *root=NULL;//定义二叉树的根

以数组a，以root

cout<<\"二叉排序树构造成功！\\n\"; if(root==NULL)cout<<\"空树\\n\";//p=root; cout<<\"中序遍历此二叉排序树，结果为：

ergotic(root);cout<<\"\\n\";//中序遍历

cout<<\"请输入要删除的关键字：\\n\"; int sun;cin>>sun; check(root,sun);

if(rut==false)cout<<\"你输入的关键字不

在树里\\n\";

else {del(root,sun);cout<<\"删除以后中

序遍历得到的结果为：\\n\";ergotic(root);}

cout<<\"\\n\"; return 0; }

运行效果:

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文