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

课程设计(论文)任务书 软件学院 　学　　院　　 　专　　业　 　班　 一、课程设计(论文)题目 各种查找算法演示　 　　 二、课程设计(论文)工作自2009 年 12 月 28 日起至 2010 年 1月 2 日止。 三、课程设计(论文) 地点: 多媒体实验室(5-302,303) 四、课程设计(论文)内容要求： 1．本课程设计的目的 （1）熟练掌握C语言的基本知识和技能；（）（2）（3）（） （1）严蔚敏，吴伟民.数据结构. 北京：清华大学出版社，2006. （2）严蔚敏、吴伟民、米宁.数据结构题集。北京：清华大学出版社，2006. (3) 谭浩强C程序设计（第二版）作者：清华大学出版社(论文)评审意见 （1）完成原理分析（20分）：优（　）、良（　）、中（　）、一般（　）、差（　）； （2）设计分析　　（20分）：优（　）、良（　）、中（　）、一般（　）、差（　）； （3）完成调试　　（20分）：优（　）、良（　）、中（　）、一般（　）、差（　）； （4）翻译能力　　（20分）：优（　）、良（　）、中（　）、一般（　）、差（　）； （5）回答问题　　（20分）：优（　）、良（　）、中（　）、一般（　）、差（　）； （6）格式规范性及考勤是否降等级：是（　）、否（　） 评阅人： 　　　 职称： 讲师 2010 年1 月3 日 目　录 一、 问题描述 4 二、 内容简介 5 2.1 基本要求： 5 2.2. 算法思想： 5 2.3. 模块划分： 6 2.4. 数据结构： 6 2.5. 源程序： 7 2.6. 测试情况： 11 三、小结 14 四、参考文献 15 问题描述 设计一个的菜单将在实现的功能显示出来，并有选择提示； 分别实现顺序、二分法、二叉排序树、哈希表的查找 哈希表可选取其中任一种方法实现； 二叉排序树必须实现构建、查找、插入、删除四个基本操作 输出各种排序的结果并进行比较。 内容简介 2.1 基本要求：输出各种排序的结果并进行比较。. 算法思想： system(\E:\\sh\\tui\\Debug\\tui.exe\); break; 2 子程序设计方法 (1) 顺序查找 设置0号单元为哨兵从数组末尾逐次向前查找，返回数组下标。当下标为0时说明查找失败，反之查找成功。 (2) 折半查找 把low指针和high指针分别指向数组的上界和下界，Mid指针指向数组的中间位置。把mid指针与所要查找的关键字比较，如果相等返回数组下标；当关键字大于mid指向的数据时，把mid+1赋值给low；小于时，把mid-1赋给high。如此循环，当low=high时，循环停止，返回mid值；当返回值为0时，查找失败，否则成功。 (3)二叉树查找 二叉树查找的数据键入方式有两种：手动查找，自动查找。 根据要查找的数据与“根结点”大小的比较来查找。若数据小于根结点值则从左子树切入查找，若大于根结点则从右子树切入查找，假如等于根结点即表明查找到返回根结点的地址值。若查找完毕没有找到该数据即返回空值。 (4) 哈希表 用除留余数法创建哈希函数，当遇到冲突时用开放定址法的线性探测解决冲突问题。把字符定义在数组中，再给定k值。根据造表时设定的哈希函数求得哈希地址，若表中此位置上没有记录，则查找不成功；否则比较关键字，若和给定值相等则查找成功。 2.3. 模块划分：void main（）：主函数，用来调用四个查找的子函数 system(\E:\\sh\\tui\\Debug\\tui.exe\)：E盘中实现顺序查找的程序 system(\E:\\sh\\zheban\\Debug\\zheban.exe\)：E盘中实现二分查找的程序 system(\E:\\sh\\ert\\Debug\\ert.exe\)：E盘中实现二叉排序树查找的程序 system(\E:\\sh\\gf\\Debug\\gf.exe\)：E盘中实现哈希查找的程序 void Insert(BSTree *tree, ElemType item)：二叉排序树查找 void CreateHashList()：哈希表查找 2.4. 数据结构：typedef int KeyType; typedef struct { KeyType *elem;//数据元素存储空间基址，建表时按实际长度分配，0号单元留空 int length; //表长度 }SSTable; //顺序表的存储结构 2 .折半查找---顺序存储结构 type