线性表的查找

简介:

查找基本概念

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

线性表的查找

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

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

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

数据元素类型定义

    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
}

性能分析

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

适用条件

采用顺序存储结构的有序表,不易于链式结构
目录
相关文章
|
网络协议 安全 Android开发
软件丨李跳跳们现在该如何跳呢?
前段时间,李跳跳等软件被某大厂发了律师函,之后,好些个跳广告软件都相继发布公众号说明,停止维护软件,并且下架了相关软件,那我们还能跳吗?该怎么跳呢?
1020 0
软件丨李跳跳们现在该如何跳呢?
|
3月前
|
存储 Windows
内存卡坏了还能修吗?4种常见修复方法
内存卡出现“无法保存”或“存储异常”等问题时,不一定是硬件损坏,可能是系统错误或文件系统异常导致。本文介绍几种亲测有效的修复方法:1) 更换读卡设备排除接触问题;2) 格式化修复文件系统(需先备份数据);3) 使用DiskGenius检测坏道;4) 借助厂商工具深度修复。同时提供日常保养建议,如避免高温环境、养成数据备份习惯,延长内存卡使用寿命。通过这些方法,多数问题可轻松解决,无需更换硬件。
|
8天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1192 4
|
7天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
950 12
|
6天前
|
机器学习/深度学习 物联网
Wan2.2再次开源数字人:Animate-14B!一键实现电影角色替换和动作驱动
今天,通义万相的视频生成模型又又又开源了!Wan2.2系列模型家族新增数字人成员Wan2.2-Animate-14B。
536 11
|
17天前
|
人工智能 运维 安全
|
8天前
|
弹性计算 Kubernetes jenkins
如何在 ECS/EKS 集群中有效使用 Jenkins
本文探讨了如何将 Jenkins 与 AWS ECS 和 EKS 集群集成,以构建高效、灵活且具备自动扩缩容能力的 CI/CD 流水线,提升软件交付效率并优化资源成本。
339 0
|
8天前
|
消息中间件 Java Apache
SpringBoot集成RocketMq
RocketMQ 是一款开源的分布式消息中间件,采用纯 Java 编写,支持事务消息、顺序消息、批量消息、定时消息及消息回溯等功能。其优势包括去除对 ZooKeeper 的依赖、支持异步和同步刷盘、高吞吐量及消息过滤等特性。RocketMQ 具备高可用性和高可靠性,适用于大规模分布式系统,能有效保障消息传输的一致性和顺序性。
463 2