多种查找算法实现及其比较

1、广西工学院计算机学院数据结构课程实验报告书实验八多种查找算法实现及其比较学生姓名：学 号：班级：计指导老师专 业：计算机学院软件学院提交日期：2013年6月28日1 .实验目的1)掌握常见的静态查找表和动态查找表的表示和操作方法。2)能根据具体的查找方法设计合理的查找表的数据结构。2 .实验内容1)用静态查找结构实现静态查找算法，包括顺序查找 一用顺序表、链表(流程图)折半查找 一用有序顺序表(流程图)基本操作：Create(&ST,n); / 构造含有n个元素的静态查找表 STDestroy(&ST); / 销毁表Search(ST,key); /查找关键字为key的数据元素

2、Traverse(ST,visit(); / 遍历查找表数据结构定义：typedef struct int key; Eletype;typedef struct Elemtype *elem;int length; SSTable;# define BLOCK_NUM 32)用动态查找结构实现动态查找算法，包括二叉排序树一无重复关键字AVL树一平衡二叉排序树动态查找：表结构本身是在查找过程中动态生成的。基本操作：InitDSTable(&DT); /构造一个空的动态查找表 DTDestroyDSTable(&DT); / 销毁表SearchDSTable(DT,key); /

3、查找关键字为key的数据元素InsertDSTable(&DT,e);DeleteDSTable(&DT,key);TraverseDSTable(DT,visit(); / 遍历查找表二叉排序树的数据类型描述：typedef struct int key; ElemType;typedef struct BiTNodeElemType data;struct BiTNode *lchild,*rchild; BiTNode, * BiTree;3).用以上方法中的一种，编程实现在 n个数据(n>=10)中查找某个数3.实验要求(1)上机前交实验源程序(纸质版)，由学习委

4、员统一收好交老师(附上不交同学名 单)。(2)用一切你能想到的办法解决遇到的问题，培养解决问题的能力。(3)实验课上进行答辩。(4)实验报告当场交。报告内容包括 ：实验目的、实验内容、实验代码、实验运行 结果以及实验体会供五部分。3.主要算法3.1 顺序存储结构(1)结构定义：#include<stdio.h> #include<stdlib.h>#include <conio.h>#include<malloc.h>/各头文件#define N 10#define OK 1 #define ERROR 0 #define OVERFLOW -2

5、typedef int keyType;/设关键字域为长整型typedef int TElemType;/定义宏参/定义静态表存储结构typedef struct(TElemType *elem;/定义数据类型int length;/ 记录当前长度 SSTable;/定义动态表存储结构typedef struct(int key; / 关键字 ElemType;/定义动态表指针typedef struct BiTNode(ElemType data;/定义数据类型struct BiTNode *lchild;/左孩子指针struct BiTNode *rchild;/右孩子指针BiTNode,

6、*BiTree;void Insert_BST(BiTree &T, BiTree S ); int Delete(BiTree &p);/建立静态表void Creat_seq(SSTable &ST,TElemType r,int n)int i;ST.elem=(TElemType*)calloc(n+1,sizeof(TElemType);分配存储空间if(!ST.elem)/分配存储空间失败exit(0);for(i=1;i<=n;i+)/ 把r中的数据元素复制给STST.elemi=ri;ST.length=n;/ 记录当前长度/静态表清空void C

7、lear(SSTable &ST)/初始条件：静态表已存在/操作结果：清空静态表int i=ST.length;for(i=1;i<=ST.length;i+)/把 ST 当前长度赋值为 0ST.elemi=0;return;/静态顺序查找int search_seq(SSTable ST,keyType key)/初始条件：静态表已存在/操作结果：在顺序表中顺序查找其关键字等于key的数据元素，/若存在，则返回该元素，否则返回0int i=ST.length;ST.elem0=key;while(ST.elemi!=key)return i;/静态折半查找int search_

8、bin(SSTable ST,keyType key)/初始条件：静态表已存在/操作结果：在顺序表中折半查找其关键字等于key的数据元素,/若存在，则返回该元素，否则返回0int low,mid,high;low=1;high=ST.length;while(low<=high)mid=(low+high)/2;if (key=(ST.elemmid)return mid;elseif (key<ST.elemmid)high=mid -1;elselow=mid+1;)/静态表输出void Traverse(SSTable ST)/初始条件：静态表已存在int i;for(i=1

9、;i<=ST.length;i+)/依次输出ST中所有数据元素printf("%d ",ST.elemi);return;/建立动态表void CreatBST( BiTree &T )/操作结果：建立一个空二叉树int x,i,n;BiTree S;T=NULL;printf("请输入您要存储的数据长度：");scanf("%d",&n);for(i=1;i<=n;i+)printf(" 请输入第%d个数据：",i);scanf("%d",&x);S=(Bi

10、TNode*) malloc(sizeof(BiTNode);建立结点S->data.key=x;S->lchild=NULL;S->rchild=NULL;Insert_BST(T,S);/ 调用函数return;/建立二叉树调用函数void Insert_BST(BiTree &T, BiTree S) /初始条件：二叉树T已存在BiTree p,q;if(iT)T=S;elseP=T;while(p)q=p;if(S->data.key<p->data.key)p = p->lchild;elsep = p->rchild;if(S

11、->data.key<q->data.key)q->lchild=S;elseq->rchild=S;return;/历遍二叉树void traverse(BiTree T)/初始条件：二叉树T已存在if(T)traverse(T->lchild );printf("%d ",T->data);traverse(T->rchild);return;/销毁二叉树void DestroyBST(BiTree &T)/初始条件：二叉树T已存在/操作结果：销毁二叉树Tif(T)T->data.key=NULL;Destr

12、oyBST(T->lchild);DestroyBST(T->rchild);return;/二叉树查找int SearchBST(BiTree T,keyType key,BiTree f,BiTree &p)/初始条件：二叉树T已存在/操作结果：在二叉树中查找其关键字等于key的数据元素,/若存在，则返回该元素，否则返回0/f 指向t的双亲，初值为 NULLif (!T)p=f;return 0;)elseif(key=T->data.key)(P=T;return OK;)elseif (key<T->data.key)return SearchBS

13、T(T->lchild,key,T,p);elsereturn SearchBST(T->rchild,key,T,p);)/二叉排序树插入算法int InsertBST(BiTree &T,ElemType e)/初始条件：二叉树T已存在/操作结果：二叉树若存在，则插入tK元素，否则返回 0BiTree s,p;/p指向查找中最后一次访问的节点if(!SearchBST(T,e.key,NULL,p)s=(BiTree)malloc(sizeof(BiTNode);s->data=e;s->lchild=s->rchild=NULL;if(!p)T=s;

14、elseif(e.key<p->data.key)p->lchild=s;elsep->rchild=s;return OK;elsereturn 0;/二叉树删除int DeleteBST(BiTree &T,keyType key)/初始条件：二叉树T已存在/操作结果：在二叉树中查找其关键字等于key的数据元素,/若存在，则删除该元素，否则返回 0if (!T)return 0;elseif(key=T->data.key)return Delete(T);elseif(key<T->data.key) return DeleteBST(T

15、->lchild,key);elsereturn DeleteBST(T->rchild,key);)/删除调用函数int Delete(BiTree &p)/初始条件：二叉树T已存在BiTree q,s;if (!p->rchild)q=p;p=p->lchild;free(q);)elseif(!p->lchild)q=p;p=q->rchild;free(q);)elseq=p;s=p->lchild;/ 向左走一步while (s->rchild)/转右走到头q=s;s=s->rchild;p->data=s->

16、data;if(q!=p)q->rchild = s->lchild;elseq->lchild = s->lchild;/ 说明还没转右 delete s;)/删除节点sreturn OK;) void main()TElemType rN;ElemType e;BiTree T,f=NULL,p;SSTable st;int i,j,k,n,key,mid;long s ,c;while(1)system("cls");/ 清屏printf("nt*”);printf（"nt*多种查找算法实现及其比较*"）;prin

17、tf("nt*n");printf（"t *1.建立静态表2.静态顺序查*n"）;printf("t3.静态折半查4.清空静态表* n");5.建立动态表6.动态查找printf("t7.动态表插入8.动态表删除printf("t *9.销毁动态表0.退出* n");* n");*n");printf("t*n");printf("请选择选项 <1-9>:");scanf(" %d",&k);if(k<

18、;0|k>9)printf（"输入有误，请重新输入!"）;printf("n");printf("nttt按任意键进行重新操作!"）;getch();continue;switch(k)case 1:printf（"建立静态表！n"）;printf（"请输入您要存储的数据长度："）;scanf("%d",&n);for(i=1;i<=n;i+)printf（"请输入第%d个数据：",i）;scanf("%d",&am

19、p;ri);Creat_seq(st,r,n);printf（" 你输入数据："）;Traverse(st);printf("n");getch();break;case 2:printf("静态顺序查找法！n");printf("请输入要查找的关键字：");scanf("%d",&s);i=search_seq(st,s);if(i)printf("要查找的关键字的序号为：%dn",i);elseprintf("没有找到 n");printf(&

20、quot;n");printf("nttt按任意键进行重新操作!");getch();break;case 3:printf("静态折半查找法！n");printf("请输入要查找的关键字：");scanf("%d",&c);mid=search_bin(st,c);if(mid)printf("要查找的关键字的序号为：dn",mid);elseprintf("没有找到 n");printf("n");printf("nttt按

21、任意键进行重新操作!");getch();break;case 4:printf（" 你真确定要清空静态表！ 1.YES 2.NOn"）;printf("请选择项 <1-2>:");scanf("%d",&j);if(j=1)Clear(st);printf("清空静态表成功呦！n");if(j=2)printf("n");printf("nttt按任意键进行重新操作!");getch();break;case 5:printf(" 建

22、立动态表!n");CreatBST(T);printf("你输入数据：");traverse(T);printf("n");printf("nttt按任意键进行重新操作!");getch();break;case 6:printf(" 动态查找法！ n");printf("请输入你要查找的关键字：");scanf("%d",&key);i=SearchBST(T,key,f,p);if(i=1)printf("查找成功!");elsepr

23、intf("没有找到 n");printf("n");getch();break;case 7:printf("动态表插入!n");printf("请输入你要插入的数：");scanf("%d",&e);i=InsertBST(T,e);if(i=1)printf(" 插入成功呦!n");printf(" 新数据：");traverse(T);elseprintf("插入失败!n");printf("n");

24、printf("nttt按任意键进行重新操作!");getch();break;case 8:printf("动态表删除!n");printf("请输入要删除的关键字：");scanf("%d",&key);DeleteBST(T,key);printf("删除成功呦!n");printf("新数据：");traverse(T);printf("n");printf("nttt按任意键进行重新操作!");getch();brea

25、k;case 9:printf(" 你真确定要销毁动态表！ 1.YES 2.NOn");printf("请选择项 <1-2>:");scanf("%d",&j);if(j=1)DestroyBST(T);printf("销毁成功呦!n");traverse(T);elseprintf("n");printf("nttt按任意键进行重新操作!");getch();break;case 0:printf("你真确定要退出！ 1.YES 2.NOn");printf("请选择项 <1-2>:");scanf("%d",&j);if(j=1)printf("nttt 再见，欢迎再次使用!");exit(OVERFLOW);elseprintf("n");printf("nttt按任意键进行重新操作!&