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

1、文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持. 文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持. 文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.课程设计(论文)任务书软件学除学院专业班一、课程设计(论文)题目各种查找算法演示二、课程设计(论文)工作自2009年12月28日起至2010年1月2日止。三、课程设计(论文)地点：多媒体实验室(5-302,303)四、课程设计(论文)内容要求：.本课程设计的目的TOC o 1-5 h z(1)熟练掌握c语言的基本知识和技能；一(2)掌握各种查找(

2、顺序、二分法、二叉排序树、哈希)方法及适用场合，并能在解决实际问题时灵活应用。(3)巩固在散列查找时解决冲突的方法及特点；一(5)培养分析、解决问题的能力；提高学生的科技论文写作能力。一.课程设计的任务及要求1)基本要求:(1)设计一个的菜单将在实现的功能显示出来，并有选择提示；一(2)分别实现顺序、二分法、二叉排序树、哈希表的查找一(3)哈希表可选取其中任一种方法实现；一(4)二叉排序树必须实现构建、查找、插入、删除四个基本操作(5)输出各种排序的结果并进行比较。一2)创新要求：提高算法效率，降低时间复杂度和空间复杂度一3)课程设计论文编写要求(1)要按照课程设计模板的规格书写课程设计论文一

3、(2)论文包括目录、正文、心得体会、参考文献等一(3)课程设计论文用B5纸统一打印，装订按学校的统一要求完成一4)答辩与评分标准：一(1)完成原理分析：20分；(2)完成设计过程：40分；(3)完成调试：20分；(4)回答问题：20分。5)参考文献:(1)严蔚敏，吴伟民.数据结构.北京：清华大学出版社，2006.（2）严蔚敏、吴伟民、米宁.数据结构题集。北京：清华大学出版社，2006.（3）谭浩强.C程序设计（第二版）作者：清华大学出版社，2006.6）课程设计进度安排内容天数地点构思及收集资料2图书馆编程设计与调试5实验室撰写论文3图书馆、实验室学生签名：2009年12月28日课程设计（论文

4、）评审意见（1）完成原理分析（20分）：优（）、良（）、中（）、一般（）、差（）；（2）设计分析（20分）：优（）、良（）、中（）、一般（）、差（）；（3）完成调试（20分）：优（）、良（）、中（）、一般（）、差（）；（4）翻译能力（20分）：优（）、良（）、中（）、一般（）、差（）；（5）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性及考勤是否降等级：是（）、否（）评阅人：职称：一进顺2010年1月3日文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.目录问题描述.内容简介.基本要求：算法思想：模块划分：数据结构：源程序：测试情况：错误!未定义书签

5、。错误!未定义书签。错误!未定义书签。错误!未定义书签。错误!未定义书签。错误!未定义书签。错误!未定义书签。错误!未定义书签。三、小结错误!未定义书签。四、参考文献错误!未定义书签。问题描述（1）设计一个的菜单将在实现的功能显示出来，并有选择提示；（2）分别实现顺序、二分法、二叉排序树、哈希表的查找（3）哈希表可选取其中任一种方法实现；（4）二叉排序树必须实现构建、查找、插入、删除四个基本操作输出各种排序的结果并进行比较。内容简介基本要求：设计程序分别可以实现顺序查找、二分查找、二叉排序树查找和哈希表查找。其中，哈希表查找只需要选择其中的一种，二叉排序树必须实现构建、查找、插入和删除四个基本

6、操作。能输出各种排序的结果并进行比较。在运行结果中，可以选择各种查找方法，并且输入数据后能完成查找并输出结果。算法思想：利用主程序调用四个查找的子程序的绝对路径。主程序设计方法用abcd代表四种子程序的查找调用。例如假如用户输入a即代表用户希望通过顺序查找来找到结果。程序段为：casea：printf(顺序查找：n);system(E:shtuiDebugtui.exe);break;子程序设计方法顺序查找设置0号单元为哨兵从数组末尾逐次向前查找，返回数组下标。当下标为0时说明查找失败，反之查找成功。折半查找把low指针和high指针分别指向数组的上界和下界，Mid指针指向数组的中间位置。把m

7、id指针与所要查找的关键字比较，如果相等返回数组下标；当关键字大于mid指向的数据时，把mid+1赋值给low；小于时，把mid-1赋给high。如此循环，当low=high时，循环停止，返回mid值；当返回值为0时，查找失败，否则成功。(3)二叉树查找二叉树查找的数据键入方式有两种：手动查找，自动查找。根据要查找的数据与“根结点”大小的比较来查找。若数据小于根结点值则从左子树切入查找，若大于根结点则从右子树切入查找，假如等于根结点即表明查找到返回根结点的地址值。若查找完毕没有找到该数据即返回空值。哈希表用除留余数法创建哈希函数，当遇到冲突时用开放定址法的线性探测解决冲突问题。把字符定义在数组

8、中，再给定k值。根据造表时设定的哈希函数求得哈希地址，文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.若表中此位置上没有记录，则查找不成功；否则比较关键字，若和给定值相等则查找成功。模块划分：voidmain()：主函数，用来调用四个查找的子函数system(E:shtuiDebugtui.exe):E盘中实现顺序查找的程序system(E:shzhebanDebugzheban.exe):E盘中实现二分查找的程序system(E:shertDebugert.exe)：E盘中实现二叉排序树查找的程序system(E:shgfDebuggf.exe)：E盘中实现哈希查找的程序voi

9、dInsert(BSTree*tree,ElemTypeitem)：二叉排序树查找voidCreateHashList():哈希表查找数据结构：.顺序查找顺序存储结构typedefintKeyType;typedefstructKeyType*elem;/数据元素存储空间基址，建表时按实际长度分配，0号单元留空intlength;/表长度SSTable;/顺序表的存储结构.折半查找顺序存储结构typedefstructintkey;RedType;定义结构体RedTypetypedefRedTypeElemType;/RedType型变量typedefstructElemTypeelem100

10、;/表的空间大小intlength;/表长度SSTable;.二叉树查找链式存储结构typedefintElemType;typedefstructBSTNode/定义存储结构ElemTypedata;文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.structBSTNode*lchild,*rchild;BSTNode,*BSTree;.哈希表链式存储结构typedefstructNAMEchar*py;/名字的拼音intk;/拼音所对应的整数NAME;NAMENameListNAME_NO;typedefstruc

11、thterm/哈希表char*py;/名字的拼音intk;/拼音所对应的整数intsi;/查找长度HASH;源程序：#include#include#includevoidmain()charm=0;printf(请选择查找方式：a-顺序查找,b-二分查找。二叉排序树查找，d-哈希表查找：);scanf(%c,&m);switch(m)casea:printf(顺序查找：n);system(E:shtuiDebugtui.exe);break;caseb:printf(二分查找：n);system(E:shzhebanDebugzheban.exe);break;casec:printf(二叉

12、排序树查找：n);system(E:shertDebugert.exe);break;cased:printf(哈希表查找：n);system(E:shgfDebuggf.exe);break;6文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持. 文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持. 文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持./主函数/*typedefstruct/顺序查找KeyType*elem;/数据元素存储空

13、间基址，建表时按实际长度分配，0号单元留空intlength;/表长度SSTable;/顺序表的存储结构intSearch_Seq(SSTableST,KeyTypekey)inti;ST.elem0=key;/“哨兵”，如果顺序表中不存在要查找的数据的话，则查找指针必/定指向该哨兵for(i=ST.length;ST.elemi!=key;i-)returni；找到的话，则i!=0,否则i=0voidmain()inti,key;SSTableT;T.elem=(KeyType*)malloc(sizeof(KeyType);printf(HowManyEntriesDoYouWantinp

14、utn);/输入顺序表长度scanf(%d,&T.length);for(i=1;i=T.length;i+)printf(Pleaseinputthe%dthentriesn,i);/一个一个的输入元素scanf(%d,&T.elemi);for(i=1;i=T.length;i+)printf(%5d,T.elemi);/显示已经输入的所有数据printf(nPleaseinputthedatayouwanttosearchn);scanf(%d,&key);typedefstruct/折半查找intkey;RedType;/定义一个包含关键字的结构体typedefRedTypeElemT

15、ype;typedefstructElemTypeelem100;/redtype结构体类型的数组intlength;/表的长度SSTable;/定义一个intSearch_Bin(SSTableST,intkey)/在有序表ST中折半查找其关键字等于key的数据元素。/若找到，则函数值为该元素在表中的位置，否则为0。intlow,high,mid;low=1;high=ST.length;/置区间初值while(low=high)mid=(low+high)/2;if(key=ST.elemmid.key)returnmid;/找到待查元素elseif(keydata=item;node-l

16、child=node-rchild=NULL;if(!*tree)*tree=node;文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.elseBSTreecursor=*tree;while(1)if(itemdata)if(NULL=cursor-lchild)cursor-lchild=node;Break；cursor=cursor-lchild；elseif(NULL=cursor-rchild)cursor-rchild=node;break;cursor=cursor-rchild;return;BSTreeSearch(BSTreetree,ElemTypeite

17、m)BSTreecursor=tree;while(cursor)if(item=cursor-data)returncursor;elseif(itemdata)cursor=cursor-lchild;elsecursor=cursor-rchild;returnNULL;voidCreateHashList()/哈希表查找inti;for(i=0;i=50;i+)HashListi.py=;HashListi.k=0;HashListi.si=0;for(i=0;i=30;i+)intsum=0;intadr=(NameListi.k)%M;/哈希函数intd=adr;if(HashLi

18、stadr.si=0)/如果不冲突HashListadr.k=NameListi.k;HashListadr.py=NameListi.py;HashListadr.si=1;else/冲突dod=(d+(NameListi.k)%10+1)%M;/伪散列sum=sum+1;/查找次数加1while(HashListd.k!=0);HashListd.k=NameListi.k;HashListd.py=NameListi.py;HashListd.si=sum+1;*/测试情况：主界面顺序查找界面折半查找界面二叉树查找界面哈希表查找界面文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.三、小结本次课程设计遇到的主要困难是四个查找算法的编写与运行。有时程序虽写出来了，但运行时出现错误，经过改正后能运行了但结果不正确或没有运行结果。因此，借助网络，查了很多相关的资料及文献。它们给我的帮助和启发很大。如：不知道如何生成一个自动表，经过查资料，知道了可以在time.h函数中调用。另一个难题是设计菜单程序，由于菜单程序的运行需要Graphics.h库函数，但此函数在VC6.0中打不开。所以我就用了调用的方法即：先写一个主程序，在其中通过绝对路径调用其他子程序，这样就解决了问题。不足：这次的设计中还有一些不足之处