投稿
  1. 首页
  2. 随笔

实验八 查找算法的实现

郝琳 • 2022-12-17 • 随笔 • 阅读 46

实验八 查找算法的实现,第1张

实验八 查找算法的实现

  1. 实验目的

熟练掌握顺序表和有序表的查找方法，掌握其时间复杂度的分析方法

  1. 实验内容

（1）验证并设计顺序表的查找（顺序查找、折半查找）算法

（2）验证二叉排序树上的查找（创建、查找、插入）算法

（3）验证Hash表查找（Hash函数定义、建立，查找，插入）算法

  1. 问题描述

    （说明你选做的题目及要求）

验证并设计顺序表的查找，通过顺序查找和折半查找算法。验证二叉排序树上的查找，并实现二叉树的创建查找插入等基本 *** 作。验证Hash表查找，实现Hash函数定义，建立，查找，插入等基本 *** 作算法。

  1. 数据结构定义

    （说明你算法中用到的数据结构、数据类型的定义）

以顺序表或线性表表示静态查找表。

Typedef struct{

ElemType  *elem;

Int        length;

}SSTable;
  1. 算法思想及算法设计

    （先文字说明算法的思想，然后给出类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]

③若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 <= high)

{

mid = (low + high) / 2;

if (arr[mid] == key)

return mid;//查找成功

else if (arr[mid] > 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;

}

  1. 实验代码

    （即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元素下标为：%dn", 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元素下标为：%dn", 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<8;i++){

        InsertBST(T,arr[i]);

    }

    //createBTS(T,arr,8);

    LDR(T);

    return 0;

}

（3）

//哈希表的定义 创建 查找 插入 以数值型元素为例

#include

#include



#define EQ(a,b) a==b

#define LT(a,b) a 

 

  1. 算法测试结果


    （说明测试数据，粘贴实验结果图）
 

 

 

数据为 {5，9，35，7，21，6，4}
 

 

 
 

 
 

 

 

  1.  分析与总结 


    （1）算法复杂度分析及优、缺点分析
 

        （说明你编写算法的复杂度，算法的优点和缺点有哪些）
 

1、
 

顺序查找：平均查找长度在等概率（P=1/n）情形下，算法1（不用哨兵）
 查找成功的平均查找长度为：ASL=(n-1)/2；
 查找失败的平均查找长度为：n+1。
 

缺点是查找效率低，特别是当n较大时，查找效率较低，不宜采用。
 

优点是算法简单、适应面广，对表的结构或关键字是否无序无任何要求。
 

折半查找：若设n=2h-1。则描述折半查找的扩充二叉树是高度为h的满二叉树，h=log 2 (n+1)上取整。
 第一层结点有一个，查找第一层结点要比较一次；
 第二层结点有两个，查找第二层结点要比较两次。
 第i（1<=i<=h）层结点有2i-1个，查找第i层结点要比较 i 次。
 

缺点是由于折半查找的表仍是线性表，若经常要进行插入、删除 *** 作，则元素排列费时太多，因此折半查找比较适合于一经建立就很少改动而又需要经常查找的线性表。较少查找而又经常需要改动的线性表可以采用链接存储，使用顺序查找。
 

2、
 

二叉排序树
 

 
 
创建：O(log2n)
 查找：O(log2n)
 插入：O(log2n)以上都是其最好的时间复杂度，最坏的情况是O(n)
 

 

3、
 

假设哈希函数产生的哈希值均匀分布在哈希表上，哈希表的长度可以动态增长，那么在哈希表上的插入、删除、查找 *** 作的摊还时间复杂度是O(1)，每次 *** 作的实际消耗时间与哈希表的装载因子线性相关。 查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。
 

    （2）实验总结
 

        （说明你怎么解决实验中遇到的问题，有什么收获）
 

之前一直搞不懂O(log2n)和O(logn)的区别，但是感觉其实底数应该不是太重要，去查了一下发现其实可以不用管底数，可以把他们当作是一类时间复杂度进行处理。算法时间复杂度为log（n）时，不同底数对应的时间复杂度的倍数关系为常数，不会随着底数的不同而不同，因此可以将不同底数的对数函数所代表的时间复杂度，当作是同一类复杂度处理，即抽象成一类问题。通过这次实验熟悉了各个查找方式的 *** 作，以及二叉排序树Hash表的应用。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5690546.html
赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
郝琳 郝琳 一级用户组
0 0
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表（0条）

保存