数据结构各种查找的课程设计报告.docx

1、数据结构各种查找的课程设计报告课程设计(论文)任务书 软件学院 学院 专业 班 一、课程设计(论文)题目 各种查找算法演示 二、课程设计(论文)工作自2009 年 12 月 28 日起至 2010 年 1月 2 日止。三、课程设计(论文) 地点: 多媒体实验室(5-302,303) 四、课程设计(论文)内容要求：1本课程设计的目的（1）熟练掌握C语言的基本知识和技能； （2）掌握各种查找（顺序、二分法、二叉排序树、哈希）方法及适用场合，并能在解决实际问题时灵活应用。（3）巩固在散列查找时解决冲突的方法及特点；（5）培养分析、解决问题的能力；提高学生的科技论文写作能力。 2课程设计的任务及要求1

2、）基本要求：（1）设计一个的菜单将在实现的功能显示出来，并有选择提示； （2）分别实现顺序、二分法、二叉排序树、哈希表的查找（3）哈希表可选取其中任一种方法实现；（4）二叉排序树必须实现构建、查找、插入、删除四个基本操作（5）输出各种排序的结果并进行比较。2）创新要求： 提高算法效率，降低时间复杂度和空间复杂度3）课程设计论文编写要求（1）要按照课程设计模板的规格书写课程设计论文（2）论文包括目录、正文、心得体会、参考文献等（3）课程设计论文用B5纸统一打印，装订按学校的统一要求完成4）答辩与评分标准： （1）完成原理分析：20分； （2）完成设计过程：40分； （3）完成调试：20分；（4）

3、回答问题：20分。5）参考文献：（1）严蔚敏，吴伟民.数据结构. 北京：清华大学出版社，2006. （2）严蔚敏、吴伟民、米宁.数据结构题集。北京：清华大学出版社，2006.(3) 谭浩强. C程序设计（第二版）作者：清华大学出版社，2006.6）课程设计进度安排内容 天数地点构思及收集资料 2图书馆编程设计与调试 5实验室撰写论文 3图书馆、实验室学生签名： 2009 年12月28日课程设计(论文)评审意见（1）完成原理分析（20分）：优（）、良（）、中（）、一般（）、差（）； （2）设计分析（20分）：优（）、良（）、中（）、一般（）、差（）； （3）完成调试（20分）：优（）、良（）、中

4、（）、一般（）、差（）；（4）翻译能力（20分）：优（）、良（）、中（）、一般（）、差（）；（5）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性及考勤是否降等级：是（）、否（）评阅人： 职称： 讲师 2010 年1 月3 日目录一、 问题描述 4二、 内容简介 52.1 基本要求： 52.2. 算法思想： 52.3. 模块划分： 62.4. 数据结构： 62.5. 源程序： 72.6. 测试情况： 11三、小结 14四、参考文献 15一、 问题描述（1）设计一个的菜单将在实现的功能显示出来，并有选择提示；（2）分别实现顺序、二分法、二叉排序树、哈希表的查找（3）

5、哈希表可选取其中任一种方法实现；（4）二叉排序树必须实现构建、查找、插入、删除四个基本操作输出各种排序的结果并进行比较。二、 内容简介2.1 基本要求： 设计程序分别可以实现顺序查找、二分查找、二叉排序树查找和哈希表查找。其中，哈希表查找只需要选择其中的一种，二叉排序树必须实现构建、查找、插入和删除四个基本操作。能输出各种排序的结果并进行比较。在运行结果中，可以选择各种查找方法，并且输入数据后能完成查找并输出结果。2.2. 算法思想：利用主程序调用四个查找的子程序的绝对路径。1 主程序设计方法用a b c d代表四种子程序的查找调用。例如假如用户输入a即代表用户希望通过顺序查找来找到结果。程序

6、段为：case a: printf(顺序查找：n); system(E:shtuiDebugtui.exe); break; 2 子程序设计方法(1) 顺序查找 设置0号单元为哨兵从数组末尾逐次向前查找，返回数组下标。当下标为0时说明查找失败，反之查找成功。(2) 折半查找把low指针和high指针分别指向数组的上界和下界，Mid指针指向数组的中间位置。把mid指针与所要查找的关键字比较，如果相等返回数组下标；当关键字大于mid指向的数据时，把mid+1赋值给low；小于时，把mid-1赋给high。如此循环，当low=high时，循环停止，返回mid值；当返回值为0时，查找失败，否则成功。(

7、3)二叉树查找二叉树查找的数据键入方式有两种：手动查找，自动查找。根据要查找的数据与“根结点”大小的比较来查找。若数据小于根结点值则从左子树切入查找，若大于根结点则从右子树切入查找，假如等于根结点即表明查找到返回根结点的地址值。若查找完毕没有找到该数据即返回空值。 (4) 哈希表用除留余数法创建哈希函数，当遇到冲突时用开放定址法的线性探测解决冲突问题。把字符定义在数组中，再给定k值。根据造表时设定的哈希函数求得哈希地址，若表中此位置上没有记录，则查找不成功；否则比较关键字，若和给定值相等则查找成功。2.3. 模块划分：void main（）：主函数，用来调用四个查找的子函数system(E:s

8、htuiDebugtui.exe)：E盘中实现顺序查找的程序system(E:shzhebanDebugzheban.exe)：E盘中实现二分查找的程序system(E:shertDebugert.exe)：E盘中实现二叉排序树查找的程序system(E:shgfDebuggf.exe)：E盘中实现哈希查找的程序void Insert(BSTree *tree, ElemType item)：二叉排序树查找void CreateHashList()：哈希表查找2.4. 数据结构：1. 顺序查找-顺序存储结构typedef int KeyType;typedef struct KeyType *

9、elem;/数据元素存储空间基址，建表时按实际长度分配，0号单元留空 int length; /表长度SSTable; /顺序表的存储结构2 .折半查找-顺序存储结构typedef struct int key; RedType; /定义结构体RedTypetypedef RedType ElemType; /RedType型变量typedef struct ElemType elem100; /表的空间大小 int length; / 表长度SSTable; 3.二叉树查找-链式存储结构 typedef int ElemType;typedef struct BSTNode/定义存储结构 E

10、lemType data; struct BSTNode *lchild, *rchild; BSTNode, *BSTree;4 .哈希表-链式存储结构typedef struct NAME char *py; /名字的拼音 int k; /拼音所对应的整数 NAME; NAME NameListNAME_NO; typedef struct hterm /哈希表 char *py; /名字的拼音 int k; /拼音所对应的整数 int si; /查找长度 HASH; 2.5. 源程序：#include #include #include void main() char m=0;prin

11、tf(请选择查找方式：a-顺序查找,b-二分查找,c-二叉排序树查找，d-哈希表查找：); scanf(%c,&m); switch(m) case a: printf(顺序查找：n); system(E:shtuiDebugtui.exe); break; case b: printf(二分查找：n); system(E:shzhebanDebugzheban.exe); break; case c: printf(二叉排序树查找：n); system(E:shertDebugert.exe); break; case d: printf(哈希表查找：n); system(E:shgfDeb

12、uggf.exe); break; /主函数/*typedef struct /顺序查找 KeyType *elem;/数据元素存储空间基址，建表时按实际长度分配，0号单元留空 int length; /表长度SSTable; /顺序表的存储结构int Search_Seq(SSTable ST, KeyType key) int i; ST.elem0 = key; /“哨兵”，如果顺序表中不存在要查找的数据的话，则查找指针必/定指向该哨兵 for(i = ST.length; ST.elemi != key; i-) return i; /找到的话，则i != 0,否则i = 0void

13、main() int i, key; SSTable T; T.elem = (KeyType *)malloc(sizeof(KeyType); printf(How Many Entries Do You Want inputn);/输入顺序表长度 scanf(%d, &T.length); for(i=1; i=T.length; i+) printf(Please input the %dth entries n, i);/一个一个的输入元素 scanf(%d, &T.elemi); for (i=1; i=T.length; i+) printf(%5d,T.elemi); /显示已

14、经输入的所有数据 printf(nPlease input the data you want to searchn); scanf(%d, &key);typedef struct /折半查找 int key; RedType; /定义一个包含关键字的结构体typedef RedType ElemType; typedef struct ElemType elem100; /redtype结构体类型的数组 int length; /表的长度 SSTable; /定义一个int Search_Bin ( SSTable ST, int key ) / 在有序表ST中折半查找其关键字等于key的

15、数据元素。 / 若找到，则函数值为该元素在表中的位置，否则为0。 int low, high, mid; low = 1; high = ST.length; / 置区间初值 while (low = high) mid = (low + high) / 2; if (key =ST.elemmid.key) return mid; / 找到待查元素 else if (keydata = item; node-lchild = node-rchild = NULL; if (!*tree) *tree = node; else BSTree cursor = *tree; while (1)

16、if (item data) if (NULL = cursor-lchild) cursor-lchild = node; Break； cursor = cursor-lchild； else if (NULL = cursor-rchild) cursor-rchild = node;break; cursor = cursor-rchild; return; BSTree Search(BSTree tree, ElemType item)BSTree cursor = tree;while (cursor) if (item = cursor-data)return cursor;

17、else if ( item data) cursor = cursor-lchild; else cursor = cursor-rchild; return NULL; void CreateHashList() /哈希表查找 int i; for (i=0; i=50;i+) HashListi.py=; HashListi.k=0; HashListi.si=0; for (i=0;i=30;i+) int sum=0; int adr=(NameListi.k) % M; /哈希函数 int d=adr; if(HashListadr.si=0) /如果不冲突 HashListadr

18、.k=NameListi.k; HashListadr.py=NameListi.py; HashListadr.si=1; else /冲突 do d=(d+(NameListi.k)%10+1)%M; /伪散列 sum=sum+1; /查找次数加1 while (HashListd.k!=0); HashListd.k=NameListi.k; HashListd.py=NameListi.py; HashListd.si=sum+1; */2.6. 测试情况： 主界面 顺序查找界面 折半查找界面 二叉树查找界面 哈希表查找界面三、小结本次课程设计遇到的主要困难是四个查找算法的编写与运行。

19、有时程序虽写出来了，但运行时出现错误，经过改正后能运行了但结果不正确或没有运行结果。因此，借助网络，查了很多相关的资料及文献。它们给我的帮助和启发很大。如：不知道如何生成一个自动表，经过查资料，知道了可以在time.h函数中调用。另一个难题是设计菜单程序，由于菜单程序的运行需要Graphics.h库函数，但此函数在VC6.0中打不开。所以我就用了调用的方法即：先写一个主程序，在其中通过绝对路径调用其他子程序，这样就解决了问题。不足：这次的设计中还有一些不足之处。例如,主程序不能实现循环。虽然采纳了同学的建议采用while语句，但这个语句基本上不起作用。另外，在哈希表中只有固定的表，没有自动生成的表。虽然尝试着写了，但老是出错，所以也就没有用。体会：1.首先对程序设计的步骤有了更深刻的了解。 2.对顺序查找，折半查找，二叉排序树及哈希表中的查找方法了解的更清楚了。 3.最大的收获是知道如何在C中实现子程序的调用。 4.体会到了集中精力去完成一份任务时所收获的成就感。四、参考文献1 严蔚敏，吴伟民.数据结构. 北京：清华大学出版社，2006.2 严蔚敏、吴伟民、米宁.数据结构题集。北京：清华大学出版社，20063 谭浩强. C程序设计（第二版）作者：清华大学出版社，2006