实验8查找与排序算法的实现和应用

1、班级学号姓名实验组别实验日期室温报告日期成绩报告内容：（目的和要求、原理、步骤、数据、计算、小结等） 实验名称：查找与排序算法的实现和应用 实验目的：1. 掌握顺序表中查找的实现及监视哨的作用。2. 掌握折半查找所需的条件、折半查找的过程和实现方法。3. 掌握二叉排序树的创建过程，掌握二叉排序树查找过程的实现。4. 掌握哈希表的基本概念，熟悉哈希函数的选择方法，掌握使用线性探测法和链地址法进行冲突解决的方法。5. 掌握直接插入排序、希尔排序、快速排序算法的实现。实验环境（硬/软件要求）：Windows 2000,Visual C+实验内容：通过具体算法程序，进一步加深对各种查找算法的掌握，以及

2、对实际应用中问题解决方 法的掌握。各查找算法的输入序列为：26 5 37 1 61 11 59 15 48 19输出要求：查找关键字37,给出查找结果。对于给定的某无序序列，分别用直接插入排序、希尔排序、 快速排序等方法进行排序，并输出每种排序下的各趟排序结果。各排序算法输入的无序序列为：26 5 37 1 61 11 59 15 48 19。实验要求：一、查找法1. 顺序查找首先从键盘输入一个数据序列生成一个顺序表，然后从键盘上任意输入一个值，在顺序表中进行查找。2. 折半查找任意输入一组数据作为个数据元素的键值，首先将此序列进行排序，然后再改有序表上使用折半查找算法进一对给定值key的查找

3、。3. 二叉树查找任意输入一组数据作为二叉排序树中节点的键值，首先创建一颗二叉排序树，然后再次二叉排序树上实现对一定k的查找过程。4. 哈希表查找任意输入一组数值作为个元素的键值，哈希函数为Hash（ key）=key%11,用线性探测再散列法解决冲突问题。二、排序算法编程实现直接插入排序、希尔排序、快速排序各算法函数；并编写主函数对各排序函数进行 测试。实验原理：1. 顺序查找：在一个已知无（或有序）序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从最后一个开始逐个比较，直到找出与给定关键字相同的数为止，它的缺点是效率低下。二分查找又称折半查找，优点是比较次数少， 查找

4、速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列 表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置 记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录， 使查找成功，或直到子表不存在为止， 此时查找不成功。2哈希查找：哈希查找的操作步骤：用给定的哈希函数构造哈希表；根据选择的冲突处理方法解决地址冲突；在哈希表的基础上执行哈希查找。哈希查找的本质是先将数据映射

5、成它的哈希值。哈希查找的核心是构造一个哈希函数， 它将原来直观、整洁的数据映射为看上去似乎是随机的一些整数。哈希查找的产生有这样一种背景一一有些数据本身是无法排序的（如图像），有些数据是很难比较的（如图像）。如果数据本身是无法排序的， 就不能对它们进行比较查找。 如果数据是很难比较的， 即使采用折半 查找，要比较的次数也是非常多的。因此，哈希查找并不查找数据本身，而是先将数据映射为一个整数（它的哈希值），并将哈希值相同的数据存放在同一个位置一即以哈希值为索引构 造一个数组。在哈希查找的过程中，只需先将要查找的数据映射为它的哈希值，然后查找具有这个哈希值的数据，这就大大减少了查找次数。如果构造哈

6、希函数的参数经过精心设计，内存空间也足以存放哈希表，查找一个数据元素所需的比较次数基本上就接近于一次。3排序算法：排序（Sorting）是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记 录）的任意序列，重新排列成一个关键字有序的序列。流程图:实验代码：一、查找法1顺序查找#in elude #defi ne MAX 100 typedef int keytype;typedef struct keytype key;elemtype;typedef struct elemtype elemMAX+1;int length;SStable;void create_seq(SSta

7、ble*list);int seq_search(SStable*list,keytype k);void main() SStable *list,table;keytype key;int i;list=&table;printf( 请输入顺序表的长度： );scanf(%d,&list-length);create_seq(list);printf( 创建的顺序表内容： n);for(i=0;ilength;i+)printf(%d.key=%dn,i+1,list-elemi.key); printf( 输入查找关键字： ); scanf(%d,&key); seq_search(li

8、st,key);void create_seq(SStable *list) int i;printf( 请输入顺序表的内容： n); for(i=0;ilength;i+) printf(%d.key=,i+1);scanf(%d,&list-elemi.key);int seq_search(SStable*list,keytype k) int i=0,flag=0;while(ilength) if(list-elemi.key=k) printf( 查找成功 .n);flag=1;printf(%d.key=%dn,i+1,k);i+;if(flag=0)printf( 没有找到数据

9、 %d!n,k); return(flag);2、折半查找#include#define MAX 100typedef struct int elemMAX+1;int length;Stable;void creat_seq(Stable*list);int sort_seq(Stable*list);int bin_search(Stable*list,int k,int low,int higt); void main() Stable *list,table;int i,key;list=&table;printf( 请输入线性表的长度： ); scanf(%d,&list-lengt

10、h);creat_seq(list);sort_seq(list);printf( 排列后的数据 n); for(i=1;ilength;i+) printf(%d.key=%dn,i,list-elemi); printf(n 请输入查找的值 :); scanf(%d,&key); bin_search(list,key,1,list-length);void creat_seq(Stable*list) int i;printf( 请输入顺序表的内容 :n); for(i=1;ilength;i+) printf(%d.key=,i); scanf(%d,&list-elemi);int

11、sort_seq(Stable*list) int i,j,flag;for(i=1;ilength;i+)flag=0;for(j=1;jlength-i+1;j+)if (list-elemjlist-elemj+1) list-elem0=list-elemj+1;list-elemj+1=list-elemj;list-elemj=list-elem0;flag=1;if(flag=0)return 1;int bin_search(Stable*list,int k,int low,int high) int mid;if(lowhigh) printf( 没有找到要查找的值 n);

12、return(0);mid=(low+high)/2;if(list-elemmid=k) printf( 查找成功 n);printf(list%d=%dn,mid,k);return(mid);elseif(list-elemmidk) return(bin_search(list,k,mid+1,high); else return(bin_search(list,k,low,mid-1);3、二叉树查找#include #include typedef struct bitnodeint key;struct bitnode *lchild;struct bitnode *rchild

13、;bnode;void ins_bitree(bnode *p,int k)bnode *q;if(p-key k&p-lchild)ins_bitree(p-lchild,k);elseif(p-keyrchild) ins_bitree(p-rchild,k);else q=(bnode *)malloc(sizeof(bnode); q-key=k;q-lchild=NULL;q-rchild=NULL;if(p-keyk) p-lchild=q;elsep-rchild=q;void bit_search(bnode *p,int k)if(p-keyk&p-lchild) bit_s

14、earch(p-lchild,k);elseif(p-keyrchild)bit_search(p-rchild,k);elseif(p-key =k)printf( 查找成功 !n);elseprintf(%d 不存在 !n);void inorder(bnode *p)if(p)inorder(p-lchild);printf(%4d,p-key);inorder(p-rchild);void main () int k;bnode *p;p=NULL;printf( 请输入二叉树结点的值，输入 0 结束 :n); scanf(%d,&k);p=(bnode *)malloc(sizeof

15、(bnode);p-key=k;p-lchild=NULL;p-rchild=NULL;scanf(%d,&k);while (k0)ins_bitree(p,k); scanf(%d,&k);printf(n);printf( 二叉树排序的结果 :);inorder(p);printf(n 请输入查找的值 :n);scanf(%d,&k);bit_search(p,k);4、哈希表查找#include #define MAX 11void ins_hash(int hash,int key)int k,k1,k2; k=key%MAX; if(hashk=0)hashk=key;return

16、 ;elsek1=k+1;while(k1MAX&hashk1!=0)k1+;if(k1MAX) hashk1=key; return ;k2=0;while(k2k&hashk2!=0)k2+;if(k2k)hashk2=key;return ;void out_hash(int hash)int i;for(i=0;iMAX;i+)if(hashi)printf(hash%d=%dn,i,hashi);void hash_search(int hash,int key)int k,k1,k2,flag=0;k=key%MAX;if(hashk=key) printf(hash%d=%d,k

17、,key); flag=1;elsek1=k+1;while(k1MAX&hashk1!=key)k1+;if(k1MAX)printf(hash%d=%d,k1,key);flag=1;k2=0;if(!flag)while(k2k&hashk2!=key)k2+;if(k2k)printf(hash%d=%d,k2,key);flag=1;if(flag)printf( 查找成功！ n);return;elseprintf( 查找失败！ n);return;void main()int i,key,k,sum=0;int hashMAX;for(i=0;iMAX;i+)hashi=0;pr

18、intf( 请输入数据，以 0 结束： n);scanf(%d,&key);sum+;while(key&sumMAX)ins_hash(hash,key);scanf(%d,&key);sum+;printf(n);out_hash(hash);printf(n);printf( 请输入查找的值： );scanf(%d,&k);hash_search(hash,k);printf(n);二、排序算法#include#include#define size 11typedef char datatype;typedef structint key;datatype others;rectype

19、;void INSERTSORT(rectype R) int i,j;for (i=2;i=size;i+) R0=Ri;j=i-1;while (R0.key0)for(j=h;j=0)&=&(ij)j-;if(ij)Ri+=Rj;while (Ri.key=&(ij)i+;if(ij) Rj-=Ri;while(i!=j);Ri=temp;return i;void QUICKSORT(rectype R,int s1,int t1) int i;if(s1t1) i=PARTITION(R,s1,t1);QUICKSORT(R,s1,i-1);QUICKSORT(R,i+1,t1);v

20、oid main() rectype Rsize;int i;printf( 请输入使用插入算法排序的 10 个数据 n); for(i=1;isize;i+)scanf(%d,&Ri.key);printf(n 插入排序之前 n);for(i=1;isize;i+)printf(%dt,Ri.key);INSERTSORT(R);printf(n 插入排序之后 n); for(i=1;isize;i+) printf(%dt,Ri.key); printf(n 请输入使用希尔顿算法排序的 10 个数据 n); for(i=0;isize-1;i+) scanf(%d,&Ri.key);printf(n希尔排序之前n);for(i=0;isize-1;i+)prin tf(%dt,Ri.key);SHELLSORT(R,10);printf(n希尔排序之后n);for(i=0;isize-1;i+)prin tf(%dt,Ri.key);printf(请输入使用快速算法排序的10个数据n);for(i=1;isize;i+)scan f(%d,&Ri.