数据结构课程设计-查找.

1、数据结构课程设计报告设计题目：查找专业：计算机科技 院系：计算机学院 姓名： XX XX 学号： XXXXXXXXX时间：2013年10月7日目录一实践目的与要求-2 -1.1实践目的-2-1.2实践要求-2-二 顺序查找的分析、程序、及运行结果 -2 -2.1系统简介-2-2.2设计思路-.2-2.3顺序查找算法描述-.3-三 折半查找的分析、程序、及运行结果 -4 -3.1系统简介-4-3.2设计思路-4-3.3折半查找算法描述-.5-四 二叉排序树查找的分析、程序、及运行结果 -5 -4.1系统简介-5 -4.2设计思路-5 -4.3二叉排序树算法描述 -.6 -五 哈希查找的分析、程序

2、、及运行结果 -8 -5.1系统简介-8 -5.2设计思路-9 -5.3哈希查找算法描述-.9-六 用户手册 错误!未定义书签。七 附件错误!未定义书签。八参考文献-16 -一实践目的与要求1.1实践目的1) 掌握各种查找算法的思想及其使用条件；2) 掌握上机实现各种查找算法的基本思想；3) 熟练掌握二叉排序树的构造和查找方法；4) 掌握散列表存储结构的思想，能选择合适的散列表函数，实现不同冲突处理方法的散列表的查找与建立；1.2实践要求1) 掌握实践是算法。2) 上机运行程序，保存和打印运行结果，并结合程序进行分析。3) 注意理解折半查找的适用条件。4) 建立二叉排序树、散列表是相同元素的处

3、理。5) 比较各种查找算法的各自特点，能够结合实际情况选择合适的查找方式。二 顺序查找的分析、程序、及运行结果2.1系统简介一次输入顺序表中的各个元素，然后进行关键字查找。如果存在则返回待查元素的位置。2.2设计思路1)顺序查找的思想对于给定的关键字K,从表中的一端开始，逐个进行数据元素的关键字和给 定值的比较，若当前扫描到的关键字与 K相等则查找成功；若扫描结束后，仍 未找到关键字等于K的节点，则查找失败。建立一个顺序表，数据元素从下标为1的单元开始放入，下标为0的元素起 哨兵作用，将待查的关键字存入下标为0的单元，顺序表从后向前查找，若直到 下标为0时才找到关键字则说明查找失败，若不到下标

4、为0时就找到关键字，则 查找成功。2.3顺序查找算法描述/*顺序表结构体定义*/typedef structkeytype keymaxsize;int len;stable;/*建立线性表*/stable create_s(stable r) _int i,j=0,k=1;printf("请输入顺序表元素，要为整形，用空格分开，-99为结束标志：n");sca nf("%d",&i);while(i!=-99)j+；r.keyk=i;k+;scan f("%d",&i);r.le n=j;return r;/*顺序表

5、查找*/int search_s(keytype k,stable *r)int j;j=r->le n;r->keyO=k;while(r->keyj!=k)j_；return j;三 折半查找的分析、程序、及运行结果3.1系统简介一次输入顺序表中的各个元素，然后进行关键字查找。如果存在则返回待 查元素的位置，否则显示不存在。3.2设计思路1)折半查找的基本思想设查找表中的元素存放在数组 r中，数据元素的下标范围为low,high,查找 的关键字值为key，中间元素的下标为 mid=(low+high)/2,(向下取整)，令key与 rmid的关键字比较：若key=rmid

6、.key,查找成功，下标为 m的记录即为所求，返回 mid。若key<rmid.key,所要找的记录只能在左半部分记录中，在对左半部分记录 中，再对左半部分使用折半查找法继续进行查找，搜索区间缩小一半。若key>rmid.key,所要找的记录只能在右半部分记录中，在对右半部分记 录中，再对右半部分使用折半查找法继续进行查找，搜索区间缩小一半。重复上述过程，直到找到查找表中某个数据元素的关键字的值等于给定的值 key说明查找成功，若出现low的值大于high的情况，说明查找不成功。建立一个有序表，数据元素从下标为1的单元开始放入。实现查找算法时， 首先将low赋值为1，high等于最

7、后一个数据元素的下标，然后将给定的关键字与查找区间low,high中间的数据元素的关键字比较，实现查找过程3.3折半查找算法描述/*顺序表结构体定义*/typedef structkeytype keymaxsize;int len;stable;/*折半查找*/int search_bi n(keytype k,stable *r)int low,high,mid;low=1;high=r->le n;while(low<=high)mid=(low+high)/2;if(k=r->keymid)return mid;else if(k<r->keymid)hi

8、gh=mid-1;else low=mid+1;return 0;四 二叉排序树查找的分析、程序、及运行结果4.1系统简介依次输入关键字并建立二叉排序树，实现二叉排序树的插入和查找功能4.2设计思路1)二叉排序树的基本思想二叉排序树就是将原来的数据根据大小构成一棵二叉树， 二叉树中的所有节 点数据满足一定的大小关系，所有的左自述中的节点均比根节点小， 所有的右子 树的节点均比根结点大。二叉排序树查找是指按照二叉排序树中结点的关系进行查找，查找的关键字首先同根结点比较，如果相等则查找成功；如果比根结点小，则在左子树中查找； 如果比根结点大，则在右子树中查找。这种查找方法可以快速缩小查找范围，大大

9、减小查找关键字的比较次数，从而提高查找效率。2)算法分析算法的关键过程实际上就是二叉排序树的创建和查找两个步骤。首先创建一个根结点，第二步就是将其他结点不断插入到二叉树中的合适位置。二叉排序树 进行结点插入时，首先要为结点寻找合适的位置插入。这个过程实际上就是关键 字不断比较的过程。如果比根结点小，贝恠左子树中插入；如果比根结点大，贝U 在右子树中插入。然后在二叉排序树中查找关键字的结点存在 。4.3二叉排序树算法描述/*二叉排序树结构体定义*/typedef struct bsnodekeytype data;struct bsnode *lchild;struct bsnode *rchi

10、ld;bno de;bnode * bsp;bnode bst;/*为关键字key建立一个二叉排序树结点*/bnode * createbst(keytype key)bnode *s;s=(b node *)malloc(sizeof(bst);s->data=key;s->lchild=s->rchild=NULL;return (s);/*将s指向的结点插入到t指向的二叉树中*/ bnode * bst in sert(b node * t,b node * s)bnode * q,*p;if(t=NULL)return(s);elsep=t;q=NULL;while(

11、p)q=p;if(s->data=p->data)printf("这个数(%d 已存在",s->data); return (t);if(s->data<p->data)p=p->lchild;else p=p->rchild;if(s->data<q->data) q->lchild=s;else q->rchild=s;return (t);/*输出二叉排序树*/ void bstpri nt(b node * t)if(t)bstpri nt(t->lchild);prin tf(&q

12、uot;%d->",t->data);bstpri nt(t->rchild);/*在二叉排序树中查找关键字*/void search(b node * t,keytype x)bnode * p;if(t=NULL)prin tf("error n");return;elsep=t;while(p)if(p->data=x)prin tf("search success!' n"); return;else if(x<p->data) p=p->lchild;else p=p->rchi

13、ld;if(!p)prin tf("%d not exist !n",x);五 哈希查找的分析、程序、及运行结果5.1系统简介依次输入关键字并建立哈希表，进行关键字查找。如果存在则返回待查元素 的位置，否则显示不存在。5.2设计思路1) 哈希表查找基本思想它是通过记录中的关键字值key为自变量，通过，某一个特定的函数h计算 出函数值h(key)作为存储地址，而查找时也用这个函数h进行计算，获得所要查 找关键字所在记录的存储位置。除留余数法是用关键字key除以某个正整数M，所得余数作为哈希地址的方 法。哈希函数h(key)=key%M，般M的取值为不大于表长的质数。用开放地址

14、法解决冲突，形成下一个地址的形式时Hi=(h(key)+di)%Mi=1,2,.k k(k<=m-1)H(key)为哈希函数；M为正整数；di为增量序列；m为表长。线性探测再散列是将开放地址法中的增量序列di设定为从1开始一直到表长减1的整数序列：1, 2，3，m-12) 算法分析算法的关键过程实际上就是Hash表的创建和查找两个步骤。其中查找时利用除留余数法构造哈希函数 h，计算出函数值获得所要查找的 关键字的存储位置。若存储位置对应的数据元素的值和查找关键字相等，则查找 成功，否则，采用线性探测法从关键字的哈希地址开始向后扫描，直到找到与关键字相等的数据元素，查找成功；若查找到最后还

15、没找到关键字，则查找失败， 不存在与关键字相等的数据元素。5.3哈希查找算法描述/*哈希表结构体定义*/typedef structkeytype key; int cn;hashtable;/*哈希函数*/int h(keytype key)return(key%m);/*哈希表查找函数*/int hashsearch(hashtable ht,keytype key)int d,i;i=0;d=h(key);=O;while(htd.key!=key)&&( htd.key!=0)&&(i<hm) i+;+;d=(d+i)%m;

16、if(i>=hm)printf("哈希表已满");retur n (un sucess);return (d);/*插入函数 查找不成功就将key插入哈希表*/int hashi nsert(hashtable ht,keytype key)int d;d=hashsearch(ht,key);if(htd.key=0)htd.key=key;return(sucess);else prin tf(" un success!n");retur n(un sucess);/*建立哈希表函数*/void hashcreate(hashtable ht)

17、int i,n;keytype keyl;printf(”请输入元素个数要小于表长d:n",hm);sea nf("%d",&n);printf("请输入元素关键字：n");for(i=0;i <n ;i+)sea nf("%d",&key1);hashi nsert(ht,key1);六用户手册1.主界面学号，_学进人查找算法性能比较系统11忡討严5 退岀»»>»iiiSS功能二2顺序查找>»»»请选桧功能:1算评弭料界料评耳科:

18、M |p 序查找科弭期XX评X科贰料请输入顺序表元素，要为整形，用空格分开，为结朿标志:0 1 2 3 4 5 fc 7 S 9 12 23 34 45 56 67 78 89 -99耗时：52849.600000# 秒!舲薯議羌翳存在3. 折半查找»»»>请丧核功能臨am入jft序表元素，要为整形，用空格分开，-即为结束标志.0 1 2 3 4 5 6 7 8 9 12 23 34 45 56 67 78 89 -99號时；50097.0000004®IM.W 81曰霧置毫89位00:素00字元盹键查9.关待购查中S：待叢:入序时4. 在二叉排序

19、树中查找»>»»请鏈择功能旧_二叉甫*序树 中查找 mxxxx请输入二叉排序树中元素以杠结束1 2 3 4 5 6 7 8 9 12 23 34 45 56 67 78 89 0建立二叉排序树是1->2->3->4->5->S->7->8->9->12->23->34->45->56->6?->?S->89-> 请输入待查元素：4seal*匚h success?5. HASH查找>»»» 请选扌峯功能：4科満 Wiffii

20、科清牺|(flS H査枚黑轉甘科清愜酬旺建立喰橙裏：请輸犬兀臺个数要M、于克长2 a:1B请输入元素关键字；1 33 4 56 7 89 12 34 £5 £：234盘时：陌42 .00因000毫秒!；3-115c s jtesnui:67£ 击 sh d卫心豪哈藉美中不存6. 退出_欢彗查找彗性能比蟹学4.HAGH查技乩退岀»»»> 请链捧功能=5i*rtss 就ey hey to cont inuc七附件#include<stdio.h>#include<malloc.h>#define keytyp

21、e int#define maxsize 100#define hm 20#define m 19#define free 0#define sucess 1#define unsucess 0void main()system("cls");system("color 1f");printf(”i1n"printf("I®必做题：查找®| n"printf("1姓名：xxxxI n"printf("I学号：xxxxxxxxxI n"printf("11n

22、"stable a;bnode *t,*s; hashtable hthm; int i=0,k,n;double cl=clock(); keytype key;int flag=1; t=NULL; while(flag)printf("|一-1n");printf("|欢迎进入查找算法性能比较系统| n");printf("| n");printf("|1.顺序查找2.折半查找| n");printf("|3.在二叉排序树中查找| n");printf("|4.HASH

23、查找5.退出| n");printf("1一-1n");prin tf(">>>> >>>n “)； printf(”请选择功能：");scanf("%d",&n);switch(n)case 1:printf(" *printf("a=create_s(a); while(i!=-1)顺序查找*n");n");printf("n输入待查关键字：");scanf("%d",&i);k=se

24、arch_s(i, &a);if(i=-1) break;if(k=0)printf("顺序表中待查元素不存在n");elseprintf("顺序表中待查元素位置是：%d",k);printf("n 耗时：%f 毫秒！ n", (clock()-cl); printf("n");break;case 2:printf("printf("*折半查找*n");n");a=create_s(a);while(i!=-1)printf("n输入待查关键字："

25、;);scanf("%d",&i);k=search_bin(i, &a);if(i=-1) break;if(k=0)printf(”顺序表中待查元素不存在 n");elseprintf("顺序表中待查元素位置是：%d",k);printf("n 耗时：%f 毫秒！ n", (clock()-cl); printf("n");break;case 3:printf("*在二叉排序树中查找* n");printf("n");printf("请输入二叉排序树中元素以0结束n");scanf("%d",&key