线性表的查找

简介:

查找基本概念

查找,也可称检索,是在大量的数据元素中找到某个特定的数据元素而进行的工作。

线性表的查找

在查找表中,线性表查找是最简单的一种,主要的操作为顺序查找和折半查找。

顺序查找:从表的一端开始,依次将查找的关键字与给定数据库进行批对,若关键字在给定数据库中存在,则查找成功,否则当数据库从头到尾没有批对到,则查找失败。

作用范围:即使用线性表的顺序存储又适合于线性表的链式存储结构。

数据元素类型定义

    typedef struct{
     KeyType key;               //关键字域
     InfoType other info;    //其他域
        }ElemType;

顺序表的定义:

     typedef struct
 {
       ElemType *R;    //存储空间基地址
       int length;        //当前长度
 }SSTable;

顺序查找

我们假设ST.R[1]开始存储数据,把ST.R[0]放置不用,这样返回的i值就是当前数据的位置。

伪代码:
  int Search_Seq(SSTable ST,KeyType key)
  {
  //在顺序表ST中顺序查找其关键字等于key的数据元素。若找到,则函数值为
  //该元素在表中的位置,否则为0
   for(i=ST.length;i>=1;--i)
   if(ST.R[i].key==key) return i;//从后往前找
   return 0;
}

将伪代码简单实现下

     int MAX=100;
        for (int i=0; i<MAX; i++) {
    printf("我被打印一次");
    if (i==50) {
        printf("YES");
        return i;
    }
    }

可以看到“我被打印一次”这句话被打印了50次,说明每次都要循环变量是否满足条件i>=1进行检测。算法是世界在于根据具体的情况进行不断的优化。我们完全可以改进算法,免去这个检测过程。改进的办法是查找之前先对ST.R[0]的关键字赋值key,这时候ST.R[0]起到了监视哨的作用。

改进后的伪代码

    int Search_Seq(SSTable ST,KeyType key)
    {
    //在顺序表ST中顺序查找其他关键字等于key的元素。若找到,则函数值为该元素在表中的位置,否则为0
    ST.R[0].key=key;         
    for(i=ST.length;ST.R[i].key!=key;--i);
    return i;
  }

将改良后伪代码简单实现下

        int MAX=100;

    for (int i=0; i != MAX; i++) 
    {
    printf("s");
    return i;
     }

可以清晰的看到改良前的代码打印了50次,改良后的代码只打印了1次,这其中的差距就是选择算法的重要性

顺序查找算法优缺点

  • 算法简单,对表结构无任何要求(顺序和链式),无论记录是否按关键字有序均可应用。

  • n很大时查找效率较低,不易采取顺序查找。

折半查找

说起了折半查找,让我想起了我的高中数学老师,曾经老师在课堂讲折半查找的时候说等到大学有接触计算机的童鞋就会在数据结构中会重新学到折半查找,没想到那个人就是我。~~(>_<)~~

                        采用二分法找21

二分法

总的来说可以描述为:

若k==R[mid].key,查找成功
若k<R[mid].key,则high=mid-1
若k>R[mid].key,则low=mid+1 
当low>high时,查找失败
伪代码
 int Search_Bin(SSTable ST,keyType key,int low,int hight)
 {
    while(low<=high)
    {
     mid=(low+high)/2;
     if(key==ST.R[mid].key)return mid;
     else if(key<ST.R[mid].key)
     high=mid-1;
     else
     low=mid+1;
    }  
    return 0;//查找不到返回0
}

性能分析

 每次查找将区间缩小一半,比顺序查找的效率高

适用条件

采用顺序存储结构的有序表,不易于链式结构
目录
相关文章
|
6月前
双链表的插入,删除以及遍历
双链表的插入,删除以及遍历
49 6
|
6月前
|
算法 C语言
【408数据结构与算法】—顺序表的插入、删除和查找(四)
【408数据结构与算法】—顺序表的插入、删除和查找(四)
|
存储 机器学习/深度学习 缓存
链表和有序二叉树插入元素时真的比数组快吗?
公司有位C++标准委员会的顾问大佬,一年会有几次视频讲座,分享一些编程要点或者经验。很多时候都是C++很基础的方面,但是他的讲解视频真的很深入浅出,有时候会“打破”一些理所应当的观点,这篇文章就是让我觉得很有趣,并且意想不到的地方,在这里分享一下。
链表和有序二叉树插入元素时真的比数组快吗?
链表oj题讲解(1)——移除链表元素
在初步给大家介绍链表之后,为了让大家更好的理解和巩固链表,小编这里会从易到难以此给大家带来一系列关于链表的oj题。那么接下来就让我们看看今天的例题。
69 1
|
存储 C语言
数据结构实验二 线性表顺序结构的删除、插入操作
数据结构实验二 线性表顺序结构的删除、插入操作
243 0
单链表的按位查找和按值查找
单链表的按位查找和按值查找的代码实现讲解
405 0
|
存储 C语言 C++
顺序表的插入、删除和查找(四)
详细介绍了数据结构中的顺序表
255 0
|
机器学习/深度学习 算法
删除重复元素(顺序表、单链表)
用顺序表和单链表分别实现删除操作
403 0
删除重复元素(顺序表、单链表)