实验八 查找算法的实现 |
您所在的位置：网站首页 › infotype数据结构 › 实验八 查找算法的实现 |
|
实验目的
熟练掌握顺序表和有序表的查找方法，掌握其时间复杂度的分析方法 实验内容（1）验证并设计顺序表的查找（顺序查找、折半查找）算法 （2）验证二叉排序树上的查找（创建、查找、插入）算法 （3）验证Hash表查找（Hash函数定义、建立，查找，插入）算法 问题描述（说明你选做的题目及要求） 验证并设计顺序表的查找，通过顺序查找和折半查找算法。验证二叉排序树上的查找，并实现二叉树的创建查找插入等基本操作。验证Hash表查找，实现Hash函数定义，建立，查找，插入等基本操作算法。 数据结构定义（说明你算法中用到的数据结构、数据类型的定义） 以顺序表或线性表表示静态查找表。 Typedef struct{ ElemType *elem; Int length; }SSTable; 算法思想及算法设计（先文字说明算法的思想，然后给出类C语言算法） 设有n个数据元素的顺序表，从表的一端（前端或后端）开始，用给定的值依次和表中各数据元素的关键字进行比较，若在表中找到某个数据元素的关键字和给定值相等，则查找成功，给出该数据元素在表中的位置；若查遍整个表，不存在关键字等于给定值的数据元素，则查找失败，给出失败信息。 #define N 11 //顺序查找（适用于线性表） int Seq_Search(int *arr, int key) { int i; arr[0] = key;//0号下标作为哨兵 for (i = N-1; arr[i] != key; i--); return i;}折半查找：如果查找区间长度小于1（low>high）则表示查找失败，返回-1；否则继续以下步骤。2）求出查找区间中间位置的数据元素下标mid（mid=（low+high）/2）。3）用区间中间位置的数据元素的关键字elem[mid]与给定值key进行比较，比较的结果有以下三种可能。 ①若elem[mid]=key，则查找成功，报告成功信息并返回其下标mid。 ②若elem[mid]key，则说明如果数据表中存在要找的数据元素，该数据元素一定在mid的左侧。可把查找区间缩小到数据表的前半部分**（high=mid-1）**，再维续进行折半查找（转步骤1）。 //折半查找（二分查找），适用于有序的顺序表 int Binary_Search(int *arr, int key) { int low = 1;//元素起始下标 int high = N-1;//最后元素下标 int mid;//中间元素下标 while (low key) high = mid - 1;//查找前半部分 else low = mid + 1;//查找后半部分 } return -1;//查找失败 }（2）二叉排序树的查找与折半查找类似，根结点相当于查找区间的中点，左子树相当于前半子区间，右子树相当于后半子区间。查找过程为：若根结点的关键字值等于查找的关键字，成功。否则，若小于根结点的关键字值，查找左子树。若大于根结点的关键字值，查找右子树。若子树为空，查找不成功。 int SearchBTS(BTNode *T,int key,BTNode *f,BTNode *&p){//二叉排序树的查找 BTNode *r,*s; if(!T){ p=f;//p指向他父亲 return 0; }else{ if(key==T->data){ p=T; return 1; }else if(keydata){ return SearchBTS(T->lchild,key,T,p); }else{ return SearchBTS(T->rchild,key,T,p); }}}二叉排序树的插入操作主要包括以下几个过程： 1.首先判断插入结点，和树中结点是否存在重复，这时候用到的是结点的搜索操作，若没有重复的节点，就进行后面的插入操作。 2.创建一个新结点，存储插入结点的值。 3.如果是空树，插入结点直接插入进去。 4.如果树不为空，插入结点的值小于最后一个结点的值，插入结点连接最后一个结点的左子树；插入结点的值大于最后一个结点的值，插入结点连接最后一个结点的右子树。 int InsertBST(BTNode *&T,int key){//二叉树的插入 BTNode *p,*s; if(!SearchBTS(T,key,NULL,p)){ s=(BTNode *)malloc(sizeof(BTNode)); s->data=key; s->lchild=s->rchild=NULL; if(!p){ T=s; }else if(keydata){ p->lchild=s; }else{ p->rchild=s; } return 1; } return 0; } 实验代码（即C语言程序） （1） int main() { //数组的0号下标不存放实际意义key（可以声明时存放数组长度） int arr1[N] = { N,1,4,2,7,5,6,9,8,3,0 }; if (Seq_Search(arr1, 4) != 0) printf("4元素下标为：%d\n", Seq_Search(arr1, 4)); else printf("该元素不存在！\n"); int arr2[N] = { N,0,1,2,3,4,5,6,7,8,9 }; if (Binary_Search(arr2, 4) != -1) printf("4元素下标为：%d\n", Binary_Search(arr2, 4)); else printf("该元素不存在！\n"); return 0; }（2） #include #include typedef struct BTNode{ int data; BTNode *lchild; BTNode *rchild; }BTNode; int SearchBTS(BTNode *T,int key,BTNode *f,BTNode *&p){//二叉排序树的查找 BTNode *r,*s; if(!T){ p=f;//p指向他爹 return 0; }else{ if(key==T->data){ p=T; return 1; }else if(keydata){ return SearchBTS(T->lchild,key,T,p); }else{ return SearchBTS(T->rchild,key,T,p); } } } int InsertBST(BTNode *&T,int key){//二叉树的插入 BTNode *p,*s; if(!SearchBTS(T,key,NULL,p)){ s=(BTNode *)malloc(sizeof(BTNode)); s->data=key; s->lchild=s->rchild=NULL; if(!p){ T=s; }else if(keydata){ p->lchild=s; }else{ p->rchild=s; } return 1; } return 0; } void createBTS(BTNode *&T,int arr[],int n){ for(int i=0;ilchild); printf("%d ",T->data); LDR(T->rchild); } } int main(int argc, char** argv) { BTNode *T; int arr[]={5,9,35,8,7,21,6,4}; for(int i=0;i |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |