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

班级 学号 姓名 实验组别 实验日期 室温 报告日期 成绩 报告内容：（目的和要求、原理、步骤、数据、计算、小结等）实验名称：查找与排序算法的实现和应用实验目的：1. 掌握顺序表中查找的实现及监视哨的作用。2. 掌握折半查找所需的条件、折半查找的过程和实现方法。3. 掌握二叉排序树的创建过程，掌握二叉排序树查找过程的实现。4. 掌握哈希表的基本概念，熟悉哈希函数的选择方法，掌握使用线性探测法和链地址法进行冲突解决的方法。5. 掌握直接插入排序、希尔排序、快速排序算法的实现。实验环境（硬/软件要求）：Windows 2000,Visual C+ 6.0实验内容： 通过具体算法程序，进一步加深对各种查找算法的掌握，以及对实际应用中问题解决方法的掌握。各查找算法的输入序列为：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. 二叉树查找任意输入一组数据作为二叉排序树中节点的键值，首先创建一颗二叉排序树，然后再次二叉排序树上实现对一定k的查找过程。 4.哈希表查找 任意输入一组数值作为个元素的键值，哈希函数为Hash（key）=key%11,用线性探测再散列法解决冲突问题。二、排序算法编程实现直接插入排序、希尔排序、快速排序各算法函数；并编写主函数对各排序函数进行测试。实验原理：1.顺序查找：在一个已知无(或有序）序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从最后一个开始逐个比较，直到找出与给定关键字相同的数为止，它的缺点是效率低下。二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。2.哈希查找：哈希查找的操作步骤：用给定的哈希函数构造哈希表；根据选择的冲突处理方法解决地址冲突；在哈希表的基础上执行哈希查找。 哈希查找的本质是先将数据映射成它的哈希值。哈希查找的核心是构造一个哈希函数，它将原来直观、整洁的数据映射为看上去似乎是随机的一些整数。哈希查找的产生有这样一种背景有些数据本身是无法排序的(如图像)，有些数据是很难比较的(如图像)。如果数据本身是无法排序的，就不能对它们进行比较查找。如果数据是很难比较的，即使采用折半查找，要比较的次数也是非常多的。因此，哈希查找并不查找数据本身，而是先将数据映射为一个整数(它的哈希值)，并将哈希值相同的数据存放在同一个位置一即以哈希值为索引构造一个数组。在哈希查找的过程中，只需先将要查找的数据映射为它的哈希值，然后查找具有这个哈希值的数据，这就大大减少了查找次数。如果构造哈希函数的参数经过精心设计，内存空间也足以存放哈希表，查找一个数据元素所需的比较次数基本上就接近于一次。 3.排序算法: 排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。开始流程图：输入查找条件用户输入输出结果排序创建二叉树 是是否继续中序遍历 否结束实验代码：一、查找法1、顺序查找#include #define MAX 100typedef int keytype; typedef struct keytype key;elemtype;typedef struct elemtype elemMAX+1; int length;SStable;void create_seq(SStable*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(list.elem%d.key=%dn,i+1,list-elemi.key);printf(输入查找关键字：);scanf(%d,&key);seq_search(list,key);void create_seq(SStable *list) int i; printf(请输入顺序表的内容：n);for(i=0;ilength;i+) printf(list.elem%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(list.elem%d.key=%dn,i+1,k);i+;if(flag=0)printf(没有找到数据%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-length);creat_seq(list);sort_seq(list);printf(排列后的数据n);for(i=1;ilength;i+)printf(list.elem%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(list.elem%d.key=,i);scanf(%d,&list-elemi);int 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);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);elsereturn(bin_search(list,k,low,mid-1);3、 二叉树查找#include #include typedef struct bitnodeint key;struct bitnode *lchild; struct bitnode *rchild;bnode;void ins_bitree(bnode *p,int k)bnode *q;if(p-key k&p-lchild)ins_bitree(p-lchild,k);else if(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;else p-rchild=q;void bit_search(bnode *p,int k)if(p-keyk&p-lchild)bit_search(p-lchild,k);else if(p-keyrchild)bit_search(p-rchild,k);else if(p-key =k)printf(查找成功!n);else printf(%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(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 ;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,key);flag=1;else k1=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;printf(请输入数据，以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 struct int key;datatype others;rectype;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)&temp.key=temp.key)&(ij)j-;if(ij)Ri+=Rj;while (Ri.key=temp.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); void 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+) printf(%dt,Ri.key);SHELLSORT(R,10); printf(n希尔排序之后n);for(i=0;isize-1;i+) printf(%dt,Ri.key); printf(请输入使用快速算法排序的10个数据n); for(i=1;isize;i+) scan