《数据结构》课程设计.docx

数据结构课程设计数据结构课程设计总结学号： 099910 姓名： 耿康康 学校： 同济大学电信学院专业： 计算机科学技术 2011 年 7 月24目录第一部分 算法实现（1）31.1 题目31.2 软件功能31.3 设计思想31.4 逻辑结构与物理结构51.5 开发平台51.6 系统的运行结果分析说明51.7 系统的安装与运行71.8 操作说明8第二部分 算法实现（2）92.1 题目92.2 软件功能92.3设计思想102.4 逻辑结构与物理结构102.5 开发平台112.6 系统的运行结果分析说明112.7 系统的安装与运行152.8操作说明16第三部分 综合应用163.1 题目163.2软件功能173.3 设计思想173.4逻辑结构与物理结构183.5开发平台183.6 系统的运行结果分析说明183.7系统的安装与运行213.8操作说明22第四部分 课程设计总结224.1所作工作224.2总结与收获23 第一部分 算法实现（1）1.1 题目本程序题目为哈希表的建立、查找、插入和删除1.2 软件功能 本程序的作用功能是实现哈希表的建立、查找、插入和删除等操作。1.3 设计思想 哈希表的构造首先要考虑两个因素，一个是用什么样的哈希函数，一个是怎么去处理冲突。常用的构造哈希函数的方法有多种，比如直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法等，而本程序选取的是除留余数法 。这是一种最简单也是最常用的构造哈希函数的方法，它的思想就是取关键字被某个不大于哈希表长的数m除后所得的余数为哈希地址，即 H（key）=key MOD m , m为小于等于表长的整数对m的选取一般可以选m为质数或不包含小于20的质因素的合数，本程序选取m为7.冲突就是指由关键字得到的哈希地址为j的位置上已经 存在记录，则处理冲突就是为该关键字的记录找到另一个“空”的哈希地址。通常用的处理冲突的方法有开放定址法、再哈希法、链地址法、建立一个公共溢出区等，本程序采用的是开放定址法。开放地址法的函数如下： i=1,2,k(km-1)其中H（key）为哈希函数；m为哈希表长；为增量序列，可有3种取法：（1）=1,2,3，m-1，称为线性探测再散列；（2）=，（km/2）称为二次探测再散列；（3）=伪随机数序列，称伪随机探测再散列。本程序采用的是第一种方法线性探测再散列。 在处理哈希表数据进行查找的过程和构造哈希表的过程基本一致，给定K值，根据造表时设定的哈希函数求得哈希地址，比较关键字，若和给定值相等，则查找成功；若和给定值不相等，则根据造表时设定的处理冲突的方法找“下一地址”，直到哈希表中某个位置为“空”或者表中所填记录的关键字等于给定值为止；若表中此位置上没有记录，则查找不成功。插入操作同样要用时要用到查找和处理冲突的方法，这两样工作完成后也就完成了插入的操作，删除操作相对来说简单一些，直接查找元素，找到后把哈希表重新建立一下，要删除的元素除外。1.4 逻辑结构与物理结构本程序采用的逻辑结构是顺序表，物理结构为线性存储1.5 开发平台本程序的开发平台为笔记本电脑，CPU为Ath.60 M320，内存为2G，硬盘为320G，操作系统为windows7，而本程序的开发运行是基于WIN7的Windows Xp Mode(WIN7的xp模式)下的Microsoft Visual C+6.0 。1.6 系统的运行结果分析说明本程序为可视化界面，主页面如下图再输入区输入相应的关键字，单击创建按钮就可以创建哈希表（表中的初始值为0），如下图 查找元素只需要在查找框里输入要查找的数据，单击查找按钮即可同样的插入和删除操作也都是再相应的编辑框里输入数据，然后单击相应按钮即可，如下图1.7 系统的安装与运行若是想简单的运行一下结果，可以直接进入哈希表文件夹下的debug文件夹，双击 HASH即可运行程序。如下图若要是对整个工程就行安装运行，则首先打开Microsoft Visual C+6.0 ，在file菜单下选择Open Workspace选项，找到工程文件路径，打开HASH.dsw即可，如下图1.8 操作说明首先要打开Microsoft Visual C+6.O,打开HASH.dsw文件即可打开整个工程文件，在工程界面的左下角有三个按钮，分别是类视图（ClassView）、资源视图（ResourceView）、文件视图（FileView）,如下图类视图包含整个工程的函数文件以及响应函数和变量等，大部分的代码操作在这里完成，资源视图就是对整个界面的设计的地方，文件视图则包含所有需要的文件。在确保整个工程文件完成的情况下，可以去build菜单下选择build HASH.exe进行调试建立，最后CTRL+F5运行程序。整个界面程序的操作步骤在“系统的运行结果分析说明”已经详细介绍，这里不再赘述。第二部分 算法实现（2）2.1 题目本程序题目为二叉排序树的建立和删除，输入一组关键值，建立相应的二叉排序树，完成结点的查找和删除操作。2.2 软件功能 本程序是MFC界面程序，可以实现二叉排序树的建立，查找、插入和删除等操作，可以实现删除根结点、叶子结点以及其它任意节点的功能。2.3设计思想非空二叉排序树的特点是：若它的左子树不空，则左子树上所有的结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于根结点的值；它的左右子树也分别为二叉排序树。 它的查找过程如下：当二叉排序树不空时，首先将给定的值和根结点的关键字比较，若相等，则查找成功，否则将依据给定值和根结点的关键字之间的大小关系，分别在左子树或右子树上继续进行查找。在查找的过程中，当树中不存在关键字等于给定值的结点是进行插入。进行删除操作时要考虑三种情况：（1）若删除结点为叶子结点，则只需要修改其双亲结点的指针即可。（2）若删除的结点只有左子树或者只有右子树，此时只要让结点的左子树或右子树直接成为其双亲结点的左子树即可。（3）若删除结点的左、右子树均不空，则在删除结点之前，中序遍历该二叉排序树，为保证删除结点之后其它元素的相对位置不变，可以有两种做法：其一是令*p的左子树为*f的左子树，而*p的右子树为s的右子树；其二是令此结点的直接前驱（或直接后继）代替此结点，然后在从二叉排序树中删去它的直接前驱（或直接后继）即可。然后在程序设计界面添加响应的按钮响应函数以及编辑框即可。2.4 逻辑结构与物理结构本程序的逻辑结构为二叉链表，物理结构为链式存储2.5 开发平台本程序的开发平台为笔记本电脑，CPU为Ath.60 M320，内存为2G，硬盘为320G，操作系统为windows7，而本程序的开发运行是基于WIN7的Windows Xp Mode(WIN7的xp模式)下的Microsoft Visual C+6.0 ，利用VC6.0的MFC对话框应用程序设计而成。2.6 系统的运行结果分析说明本程序运行时为可视化界面，如下图然后在创建按钮后面的编辑框输入关键字，用空格隔开，单击创建即可，如下图在查找栏输入要查找的元素进行查找，如输入5，如下图在插入栏可以选择要插入的元素，如插入11，如下图在删除栏可以选择你想删除的元素，如下图删除根结点9删除叶子节点2，如下图删除任何一个节点，比如结点12，如下图2.7 系统的安装与运行若要简单的安装运行，可以直接找到资源文件夹Debug下面双击BST即可若要是对整个工程就行安装运行，则首先打开Microsoft Visual C+6.0 ，在file菜单下选择Open Workspace选项，找到工程文件路径，打开BST.dsw即可，如下图2.8操作说明首先要打开Microsoft Visual C+6.O,打开BST.dsw文件即可打开整个工程文件，在工程界面的左下角有三个按钮，分别是类视图（ClassView）、资源视图（ResourceView）、文件视图（FileView）,如下图类视图包含整个工程的函数文件以及响应函数和变量等，大部分的代码操作在这里完成，资源视图就是对整个界面的设计的地方，文件视图则包含所有需要的文件。在确保整个工程文件完成的情况下，可以去build菜单下选择build BST.exe进行调试建立，最后CTRL+F5运行程序。整个界面程序的操作步骤在“系统的运行结果分析说明”已经详细介绍，这里不再赘述。第三部分 综合应用3.1 题目有一单位，为了实现办公自动化，想在本单位建立一个局域网，把10个办公地点的事务所连接起来，试问应该怎样布线，使得建立起来的局域网成本最低。3.2软件功能本程序的功能是在一个带权值的无向图中，找出一个权值最小的生成树，即为最小代价生成树。以此来表示建立局域网的最低成本。3.3 设计思想本程序用无向图的十个顶点来表示此单位的十个办公地点，每一条边表示两个办公地点之间的连线，边上的权值表示布线的成本。这实际上也就转化成了求无向图的最小生成树问题，构造最小生成树可以有很多种算法，其中多种算法都利用了最小生成树的下列一种简称为MST的性质：假设N=(V,E)是一个连通网，U是顶点集V的一个非空子集。若（u , v）是一条具有最小权值（代价）的边，其中u U , vV-U,则必存在一棵包含边（u , v）的最小生成树。普利姆（Prim）算法和克鲁卡尔（Kruskal）算法是两个比较常用的求最小生成树的算法，本程序是根据普利姆算法构造的，普利姆算法的思想如下：假设N=(V,E)是连通网，TE是N上最小生成树的集合。算法从U=()，TE=开始，重复执行下列操作：在所有uU , vV-U的边（u，v） E中找一条代价最小的边（）并入集合TE，同时并入U，直到U=V为止。此时TE中必有n-1条边，则T=(V,TE)为N的最小生成树。然后在给操作界面的按钮添加相应的响应函数完成程序的整体布局。3.4逻辑结构与物理结构本程序的逻辑结构为链表，物理结构为链式存储3.5开发平台本程序的开发平台为笔记本电脑，CPU为Ath.60 M320，内存为2G，硬盘为320G，操作系统为windows7，程序的实现运行平台为Microsoft Visual Studio 2010.3.6 系统的运行结果分析说明本程序是基于VS2010的MFC可视化程序，运行后的界面如下图所示默认单选按钮为“请输入结点”，在空白区域单击输入结点即可，如下图然后用鼠标连接两个顶点的边并输入其权值，如下图本例选择0到9十个顶点以及相应的权值，如下图单击生成按钮，即可生成最小生成树，如下图3.7系统的安装与运行若是简单运行操作可直接找到工程文件目录下的Debug下面的，SHU.EXE，双击打开即可，如下图若是要运行整个工程文件，则需要先打开Microsoft Visual Studio 2010,然后选择文件-打开-项目/解决方案，打开对话框，选择路径打开SHU.sln即可，如下图3.8操作说明运行Microsoft Visual Studio 2010,打开项目解决方案SHU.sln即可打开整个工程文件，在打开的工程界面左下角有五个选项，分别是解决方案资源管理器、类视图、属性管理器、资源视图、团队资源管理器，如下图类视图里包含了大部分代码，资源视图可以对对话框界面进行修改。想要运行程序首先要先生成代码，调试，然后才能运行形成界面。至于本程序进入界面后的操作信息在本程序的“系统运行结果分析说明”中详细介绍过，这里不再赘述。第四部分 课程设计总结4.1所作工作在做课程设计之前首先翻阅了关于数据结构上机实验的书籍，然后有翻阅了关于MFC可视化设计的教程，另外还在网上查阅了大量的资料，看了许多相关的知识要点。主要的参考书籍以及网址如下：1甘玲、邱劲.面向对象技术与Visual C+清华大学出版社20042王宏等.数据结构实验指导中国电力出版社.20103智东杰.数据结构实验程序中国水利水电出版社.20084郑阿奇.Visual C+实训清华大学出版社.20055http:/www.