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

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

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

3、：（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） 哈希表可选取其中任一种方法实现；（4） 二叉排序

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

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

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

8、，用来调用四个查找的子函数system(""E:shtuiDebugtui.exe"")：E盘中实现顺序查找的程序system(""E:shzhebanDebugzheban.exe"")：E盘中实现二分查找的程序system(""E:shertDebugert.exe"")：E盘中实现二叉排序树查找的程序system(""E:shgfDebuggf.exe"")：E盘中实现哈希查找的程序void Insert(BSTree *tree

9、, ElemType item)：二叉排序树查找void CreateHashList()：哈希表查找2.4. 数据结构：1. 顺序查找-顺序存储结构typedef int KeyType;typedef struct KeyType *elem;/数据元素存储空间基址，建表时按实际长度分配，0号单元留空 int length; /表长度SSTable; /顺序表的存储结构2 .折半查找-顺序存储结构typedef struct int key; RedType; /定义结构体RedTypetypedef RedType ElemType; /RedType型变量typedef struct

10、ElemType elem100; /表的空间大小 int length; / 表长度SSTable; 3.二叉树查找-链式存储结构 typedef int ElemType;typedef struct BSTNode/定义存储结构 ElemType data; struct BSTNode *lchild, *rchild; BSTNode, *BSTree;4 .哈希表-链式存储结构typedef struct NAME char *py; /名字的拼音 int k; /拼音所对应的整数 NAME; NAME NameListNAME_NO; typedef struct hterm /

11、哈希表 char *py; /名字的拼音 int k; /拼音所对应的整数 int si; /查找长度 HASH; 2.5. 源程序：#include<stdio.h> #include<stdlib.h> #include<windows.h> void main() char m=0;printf("请选择查找方式：a-顺序查找,b-二分查找,c-二叉排序树查找，d-哈希表查找：");scanf("%c",&m);switch(m) case 'a': printf("顺序查找：n

12、"); 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

13、': printf("哈希表查找：n"); system(""E:shgfDebuggf.exe""); break; /主函数/*typedef struct /顺序查找 KeyType *elem;/数据元素存储空间基址，建表时按实际长度分配，0号单元留空 int length; /表长度SSTable; /顺序表的存储结构int Search_Seq(SSTable ST, KeyType key) int i; ST.elem0 = key; /“哨兵”，如果顺序表中不存在要查找的数据的话，则查找指针必/定指向该哨兵

14、for(i = ST.length; ST.elemi != key; i-) return i; /找到的话，则i != 0,否则i = 0void 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("Pleas

15、e input the %dth entries n", i);/一个一个的输入元素 scanf("%d", &T.elemi); for (i=1; i<=T.length; i+) printf("%5d",T.elemi); /显示已经输入的所有数据 printf("nPlease input the data you want to searchn"); scanf("%d", &key);typedef struct /折半查找 int key; RedType; /定义一

16、个包含关键字的结构体typedef RedType ElemType; typedef struct ElemType elem100; /redtype结构体类型的数组 int length; /表的长度 SSTable; /定义一个int Search_Bin ( SSTable ST, int key ) / 在有序表ST中折半查找其关键字等于key的数据元素。 / 若找到，则函数值为该元素在表中的位置，否则为0。 int low, high, mid; low = 1; high = ST.length; / 置区间初值 while (low <= high) mid = (lo

17、w + high) / 2; if (key =ST.elemmid.key) return mid; / 找到待查元素 else if (key< ST.elemmid.key) high = mid - 1; /key小于mid所对应的k值时 / 继续在前半区间进行查找 else low = mid + 1; / 继续在后半区间进行查找 return 0; / 顺序表中不存在待查元素 / Search_Bin void main() SSTable T; int key,i=1; int postion; int n=1; /记录输入的关键字个数 printf("如果不想输

18、入,则输入0，当此数的位置为0时，查找不到该数。n"); printf("请输入第%d个数:n",n); scanf("%d",&key); while(key!=0) n+; T.elemi+.key=key; printf("请输入第%d个数,大于%dn",n,T.elemi-1.key); scanf("%d",&key); T.length=i; printf("请输入要查的数:n"); scanf("%d",&key); posti

19、on=Search_Bin(T, key); printf("此数的位置是 ：%dn",postion); void Insert(BSTree *tree, ElemType item) /二叉排序树查找 BSTree node = (BSTree)malloc(sizeof(BSTNode); node->data = item; node->lchild = node->rchild = NULL; if (!*tree) *tree = node; else BSTree cursor = *tree; while (1) if (item <

20、; cursor->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 =

21、 cursor->data)return cursor; else if ( item < cursor->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.k=NameListi.k; HashListadr.py=NameListi.py; HashListadr.si=1; else /冲突 do d=(d+(NameListi.k)%10+1)%M; /伪散列 sum=sum+1; /查找次数加1 while