数据结构设计说明书数据结构计说明书设计说明书.doc

摘 要 数据结构是研究与数据之间的关系，我们称这一关系为数据的逻辑结构，简称数据结构。当数据的逻辑结构确定以后，数据在物理空间中的存储方式，称为数据的存储结构。相同的逻辑结构可以具有不同的存储结构，因而有不同的算法。 本次课程设计，程序中的数据采用“树形结构”作为其数据结构。具体采用的是“二叉排序树”，并且使用“一维数组”来作为其存储结构。一维数组顺序表存储结构是用一组地址连续的存储单元依次自上而下、自左而右存储完全二叉树上的结点元素；本课程设计实现了二叉排序树的创建、中序遍历、计算二叉排序树的平均查找长度和删除二叉排序树中某个结点。 本课程主要介绍了本课题的开发背景，所要完成的功能和开发的过程。重点说明了系统的设计思路、总体设计、各个功能模块的设计与实现方法。 关键词：二叉排序树的实现；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  课题背景的介绍 1.1 课题背景 随着经济的迅速发展，各行各业纷纷应用计算机数据信息管理。当然数据信息是一个很笼统的概念，随着现代信息的大量增加，其处理难度也越来越大，如何对各个数据信息进行更好的树立，这就是我们研究这个课题的目的。 在计算机迅速发展的今天，将计算机这一信息处理器应用于实际数据问题问题的信息计算已是势必所然，而且这也将数据信息处理带来前所未有的改变。采用计算机对数据的信息处理是信息科学化和现代化的重要标志，它也给各行各业带来了明显的经济效益。主要体现在：极大地提高了工作人员的工作效率，大大地减少了以往的手工操作的各种弊端，同时也加强和规范掌握对于数据信息的计算。 1.2 目的 本课题运用C语言进行开发，C语言能够简单的进行编译一些程序，来实现对一些问题的解决。它虽然比较简单的处理一些问题，但却有更高的效率。它能够被大多数用户所接受，因为它能够呈现出清晰的界面，是人们能够很好的理解。能在一些方面给人们更好的服务，成为人们的好帮手。 经过这一个学期对《数据结构》的学习，我们都学到了不少东西，可能有些学的还不够理想，但无论如何这些知识都为我们的下一步学习打下了坚实的基础。做这么一个课程设计，一方面是为了检查我们一个学期以来的学习成果，另一方面也是为了让我们进一步的掌握和运用它，同时也让我们认清自己的不足之处和薄弱环节，加以弥补和加强。 需求分析 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、该结点左右子树均不为空。 系统总体设计 3.1 系统模块划分 二叉排序树是一种动态树表。 二叉排序树的定义：二叉排序树或者是一棵空树，?或者是一棵具有如下性质的二叉树： ⑴ 若它的左子树非空，则左子树上所有结点的值均小于根结点的值； ⑵ 若它的右子树非空，则右子树上所