精华内容
下载资源
问答
  • 静态查找表(Static Search Table):只作查找操作的查找表;  动态查找表(Dynamic Search Table):在查找... 顺序查找也称为线形查找,属于无序查找算法。从数据结构线形表的一端开始,顺序扫描,依次将扫描到...

    静态查找表(Static Search Table):只作查找操作的查找表; 

    动态查找表(Dynamic Search Table):在查找过程中同时插入不存在的元素,或者是删除已经存在的元素。

    顺序查找

           顺序查找适合于存储结构为顺序存储或链接存储的线性表。

    原理:

           顺序查找也称为线形查找,属于无序查找算法。从数据结构线形表的一端开始,顺序扫描,依次将扫描到的结点关键字与给定值k相比较,若相等则表示查找成功;若扫描结束仍没有找到关键字等于k的结点,表示查找失败。

    代码实现:

    def sequenceSearch(arr,target):
        for i ,value in enumerate(arr):
            if value==target:
                return True
        return False
        

    时间复杂度:

    平均查找长度(Average Search Length,ASL):需和指定key进行比较的关键字的个数的期望值,称为查找算法在查找成功时的平均查找长度。

    对于含有n个数据元素的查找表,查找成功的平均查找长度为:ASL = Pi*Ci的和。
    Pi:查找表中第i个数据元素的概率
    Ci:找到第i个数据元素时已经比较过的次数

           顺序查找成功时的平均查找长度为:(假设每个数据元素的概率相等)ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;当查找不成功时,需要n+1次比较,时间复杂度为O(n);所以,顺序查找的时间复杂度为O(n)

    展开全文
  •  静态查找表:只做查找操作的查找表 动态查找表:在查找过程中还做插入和删除数据元素的操作 查找时可改变数据元素之间的关系以获得较高的查找性能,将查找集合组织成表、树结构。也即是从数据的存储方式作出改进。...
  • 静态查找和动态查找,在上述内容的基础上,将所有查找算法整合在一个程序中。学生可参考教材中的伪代码。鼓励学生自创新思路,新算法。
  • 无序表查找算法

    2018-10-17 00:43:00
    def sequential_search(lis, key): length = len(lis) for i in range(length): ...如果查找到123就会打印出123 的位置索引,否则显示false 转载于:https://www.cnblogs.com/sea-stream/p/9801641.html

     

    def sequential_search(lis, key):
        length = len(lis)
        for i in range(length):
            if lis[i] == key:
                return i
        return False
    
    LIST = [1, 5, 8, 123, 22, 54, 7, 99, 300, 222]
    result = sequential_search(LIST, 123)
    print(result)
    

    如果查找到123就会打印出123 的位置索引,否则显示false

    转载于:https://www.cnblogs.com/sea-stream/p/9801641.html

    展开全文
  • 顺序查找(基于无序链表)

    千次阅读 2018-09-01 10:36:42
    基于无序链表的顺序查找 1、基本思想 采用链表数据结构,每个节点存储一个键值对 get():顺序遍历链表,用equals()方法比较键,如果匹配成功就返回相应的值,否则返回null put():顺序遍历链表,用equals()方法...

    1、基本思想

    采用链表数据结构,每个节点存储一个键值对
    get():顺序遍历链表,用equals()方法比较键,如果匹配成功就返回相应的值,否则返回null
    put():顺序遍历链表,用equals()方法比较键,如果匹配成功就用第二个参数更新该键相关联的值,否则就创建一个新的节点并将该键值对插入到链表的开头。
    这里写图片描述
    这里写图片描述

    2、算法实现

    /** 算法3.1 顺序查找(基于无序链表)
     * 符号表的实现使用了一个私有内部Node类来在链表中保存键和值。
    */
    public class SequentialSearchST<Key,Value>
    {
        private Node first;           //链表首节点
        //private int N;              //结点数量
        private class Node            //私有类来保存键和值
        {
            Key key;
            Value val;
            Node next;
            public Node(Key key, Value val, Node next)
            { this.key=key; this.val=val; this.next=next; }
        }
    
        // get()的实现会顺序地搜索链表查找给定的键(找到则返回相关联的值)
        public Value get(Key key)
        {              
            for(Node x=first; x!=null; x=x.next)
                if(key.equals(x.key))
                    return x.val;                /*命中*/
            return null;                         /*未命中*/
        }
    
        //put()的实现也会顺序地搜索链表查找给定的键,如果找到则更新相关联的值,否则它会用给定的键值对创建一个新的结点并将其插到链表的开头。
        public void put(Key key, Value val)
        {                
            for(Node x=first; x!=null; x=x.next)
                if(key.equals(x.key))
                {
                    x.val=val;
                    return;                      /*命中,更新*/
                }
            first=new Node(key,val,first);       /*未命中,新建结点*/
        }
    
        //表中的键值对数量
        public int size()                         
        {
            int N=0;
            for(Node x=first; x!=null; x=x.next)
                N++;
            return N;
        }
    
        //从表中删去键key及其对应的值
        public void delete (Key key)              
        {
            for(Node x=first; x!=null; x=x.next)
            {
                if(key.equals(x.next.key))
                    x.next = x.next.next;
            }
        }
    
        //键key在表中是否有对应的值
        public boolean contains(Key key)            
        {
            for(Node x=first; x!=null; x=x.next)          
                if(key.equals(x.key))               
                    return true;
            return false;
        }
    
        //表中所有键的集合
        public Iterable<Key> Keys()           
        {
            Queue<Key> q=new Queue<Key>();
            for(Node x=first; x!=null; x=x.next)
                q.enqueue(x.key);
            return q;
        }
    }

    附:可参考例子-记频器

    3、性能分析

    在含有 N N 对键值的基于(无序)链表的符号表中,
    未命中的查找和插入操作都需要 N 次比较; 命中的查找在最坏情况下需要 N N 次比较
    特别地,向一个空表中插入 N 个不同的键需要 ~ N2/2 N 2 / 2 次比较。∑Ni = ∑(i) = 1+2+…+N = N(N+1)/2 ~ N2/2 N 2 / 2

    这些分析完全证明了基于链表的实现以及顺序查找是非常低效的,无法满足处理庞大输入问题的需求。


    附:数据结构中含节点数量N参考


    展开全文
  • 静态表查找--顺序查找无序

    千次阅读 2015-12-09 15:47:50
    静态查找表在查找的过程中不改变表的状态---不插入也不删除,适合不变动或者不经常变动的查找,顺序表可以使有序的也可以是无序的,如果是有序的可以使用折半查找,每查找一次,就把范围缩小一半。如果是无序的就...

    静态查找表在查找的过程中不改变表的状态---不插入也不删除,适合不变动或者不经常变动的查找,顺序表可以使有序的也可以是无序的,如果是有序的可以使用折半查找,每查找一次,就把范围缩小一半。如果是无序的就只能从表的一端开始逐一查找了。

    本文先构建一个无序的顺序表,然后从表的一端进行查找指定的元素。

    #include<stdio.h>
    #include<malloc.h>
    #include<process.h>
    #define ERROR 0
    #define key number //设置number为查找的关键字
    //数据元素的类型
    struct ElemType
    {
    	long number;//key
    	char name[9];
    	int Chinese;
    	int math;
    	int English;
    };
    //静态查找表的顺序存储结构
    struct SSTable
    {
    	ElemType *elem;//数据元素的存储空间的基地址,(0号单元不用)
    	int length;//表的长度
    };
    //对于两个数值型变量的比较约定为如下的宏定义
    #define EQ(a,b) ((a) == (b))
    #define LT(a,b) ((a) < (b))
    #define LQ(a,b) ((a) <= (b))
    
    //由n个数据元素的数组r,构造静态查找表ST
    void Create_Seq(SSTable &ST,ElemType r[],int n)
    {
    	int i;
    	//ST.elem=(ElemType*)calloc(n+1,sizeof(ElemType));//动态生成n+1个数据元素空间,0号单元不用
    	ST.elem=(ElemType*)malloc((n+1)*sizeof(ElemType));
    	if(!ST.elem)
    		exit(ERROR);
    	for(i=1;i<=n;i++)
    		ST.elem[i]=r[i-1];//将数组的元素依次赋值给ST
    	ST.length = n;
    }
    //在顺序表ST中查找关键字等于key的数据元素,并返回在表中的位置(查找无序的顺序表)
    int Search_Seq(SSTable &ST,long key)
    {
    	int i;
    	ST.elem[0].key = key;//设置哨兵
    	//for(i=ST.length;!EQ(ST.elem[i].key,key);--i);
    		//return i;//找不到时i为0
    	i=ST.length;
    	while(ST.elem[i].key != ST.elem[0].key)
    	{
    		--i;
    	}
    	return i;
    }
    //打印ST中的元素
    void Traverse(SSTable ST) //注意这里不要使用ST的引用,因为如果你++ST.elem之后,就永久的改变了ST.elem的指向了
    {                         //当你再次使用Seach_seq的时候就会把改变后的ST.elem传入其中
    	ElemType *p;
    	int i;
    	p=++ST.elem;//p指向第一个元素
    	printf("准考证号  姓名  语文  数学  英语  \n");
    	for(i=1;i<=ST.length;i++,p++)
    		printf("%-8ld%-8s%4d%5d%5d\n",p->number,p->name,p->Chinese,p->math,p->English);
    }
    void main()
    {
    	int i;
    	long s;
    	ElemType r[3]={{120118,"zhu",80,86,88},{120117,"zhi",88,90,96},{120114,"hao",88,99,75}};
    	SSTable st;
    	Create_Seq(st,r,3);//由数组r产生顺序查找表st
    	Traverse(st);
    	printf("请输入待查找人的考号:");
    	scanf("%ld",&s);
    	i=Search_Seq(st,s);
    	printf("%d\n",i);
    	if(i)
    		printf("%-8ld%-8s%4d%5d%5d\n",st.elem[i].number,st.elem[i].name,st.elem[i].Chinese,st.elem[i].math,st.elem[i].English);
    	else
    		printf("没找到!");
    }
    

    (1)静态查找表的顺序存储结构:

    struct SSTable
    {
    ElemType *elem;//数据元素的存储空间的基地址,(0号单元不用)
    int length;//表的长度
    };


    (2)

    由n个数据元素的数组r,构造静态查找表ST,调用函数void Create_Seq(SSTable &ST,ElemType r[],int n):


    (3)程序的运行结果:


    展开全文
  • 设计一个查找算法,该算法将在一个给定的无序数组中查找指定的元素,若找到该元素返回true,反之返回false。请分析你所设计算法的时间复杂度。 要求 编写并测试所设计的查找算法 实验报告中还需要包含对所设计算法的...
  • 在学习之前我们先来了解一下... 无序查找就是顺序查找这组数据(无序数组)中的每个元素,判断要查找的数据元素是否存在。如果查找成功,则返回该yua元素在数据组中的位置,若查找失败,则返回-1,其实我们了解了这...
  • excel无序查询 使用LOOKUP函数实现无序查询,在这个电脑办公的时代,要是不掌握点office办公软件相关的知识那你简直就没有晋升的机会了,excel无序查询这个问题,不知道是否也困扰着你,关于excel无序查询 使用...
  • 链表中的每个结点存储一个键值对,get()的实现即为遍历链表,equals()方法比较需要被查找的键和每个结点中的键,如果匹配成功就返回相应的值,否则返回null。put()的实现也是遍历链表,用equals()方法比较需要被查找...
  • 排序是计算机程序设计中的一种重要运算,它的功能是将一个数据元素的无序序列调整为一个有序序列。经排序的数据若按从大到小的顺序排列,则称为下降序。反之,若经排序的数据若按从小到大的顺序排列,则称为上升序。...
  • 首先需要设计高效的数据结构来表示这些数据,要存储的数据一般分为两个部分,键和值,如何根据键值去安排这些数据尤为重要,首先我们想到线性存储,即利用的形式线性存储,线性查找,即符号这种数据结构. 符号 ...
  • 顺序表查找的实现

    2015-12-31 09:19:29
    顺序查找。通过递归实现对顺序中指定元素的查找
  • 在一个无序表A中,采用顺序查找算法查找值为x的元素, 返回其所在位置 CODE: /* 在一个无序表A中,采用顺序查找算法查找值为x的元素, 返回其所在位置 */ #include <stdio.h> //顺序查找 void ...
  • 无序链表和有序链表

    2020-01-07 20:30:33
    链表–无序链表 无序链表的相关接口 寻秩访问–rank2data(head,rank),时间复杂度为O(rank),复杂度与rank成正比,以均匀分布为例,期望的时间复杂度为O(n),其中n为链表的长度 <pre> public class LinkedList ...
  • 设计一个读入一串整数,然后构造二叉排序树,进行查找。 二叉排序树又称二叉查找树,它可以是一棵空树,若非空时具有下述性质: 1.若根结点的左子树非空,则左子树上所有结点的关键字值均小于等于根结点的关键字值...
  • 该算法针对无序数据,其基本的思想是:从数组的首元素开始,将数组的每个元素逐一与要查找的数据进行比较,直到找到相等的为止,如果查找结束都没有相等的元素,则查找不成功 2. 算法实现 时间复杂度:O(n) #include...
  • 有序查找

    千次阅读 2015-11-14 10:28:02
    对大小均为n的有序无序表分别进行顺序查找,在等概率查找的情况下,对于查找成功,它们的平均查找长度是相同的,而对于查找失败,它们的平均查找长度是不同的() 查找失败的情况下,无序表查找需要更长, ...
  • 无序序列折半查找

    2021-10-29 09:16:32
    无序序列的折半查找,最终输出原数组中要寻找的数的下标 - 要使用折半查找那提供的数组一定要是有序的,可是当提供的是无序序列时,很多时候我们都是先将无序序列排序,然后输出想要找的数的下标,这显然不太对,...
  • 在有序中,取中间记录作为比较对象, 若给定值与中间记录的关键码相等,则查找成功。 若给定值小于中间记录的关键码,则在中间记录的左半区继续查找; 若给定值大于中间记录的关键码,则在中间记录的右半区继续...
  • 《数据结构 思想与实现第二版》第八章代码摘录 集合元素的类型 template <class KEY,class OTHER> struct SET{ ...无序表的顺序查找 template<class KEY,class OTHER> int seqSearc...
  • 无序表删除重复元素

    2021-03-22 15:27:28
    无序表删除重复元素,升序或保持原顺序排列,要求:时间复杂度为O(n) 代码: #include<iostream> #include<string.h> using namespace std; int n, elem[30], elem_n[50], hashlist[50]; void ...
  • 有序查找,无序查找,二分查找总结 基本排序方法:有序查找,无序查找,二分查找总结无序查找有序查找二分查找 无序查找 其实大部分的查找方法,都是通过先定义初始的 found=False,然后一旦查找到之后,found变为...
  • 无序查找

    2018-04-25 10:36:53
    从最简单的有序集合列表list中查找数据,并返回数据在列表中的位置:"""定义一个查找函数 参数:list(列表) key(键值) 返回值:i key值在列表中的位置 """ def sequential_search...
  • 用Python链表实现有序无序表

    千次阅读 2020-11-28 18:32:34
    用Python链表实现有序无序表《数据结构与算法》MOOC(北大地空)课堂笔记2020.4by dlnb526啥是链表链表,顾名思义,顾名思义,链表像锁链一样,由一节节节点连在一起,组成一条数据链。为什么要使用链表?在之前...
  • 逆天!对无序数组使用二分查找

    千次阅读 多人点赞 2018-07-17 22:58:46
     所谓的无序数组并不是乱序,我们会遇见很多情况是旋转数组,比如一个递增数组最开始的几个元素挪到数组的最后位置。也可以理解成是两个有序数组的组合。 面试题:打印出旋转数组的最小数字  题目:把一个数组...
  • 四大查找ASL的总结

    千次阅读 2019-11-26 20:54:44
    一、一般线性表的顺序查找 ASL成功 = (n+1)/2 ASL失败 = (n+1) 二、有序线性表的顺序查找 ASL成功 = (n+1)/2 ASL失败 = (n+1)/2 + n/2 三、二分查找 二分查找的ASL成功和ASL失败通过画出对应查找序列的判定树,进而...
  • 顺序表查找:顺序查找,哨兵查找 有序表查找:折半查找,插值查找,斐波那契查找
  • 符号是一种存储键值对的数据结构,支持两种操作:插入(put),即将一组新的键值对存入中;查找(get),即根据给定的键得到相应的值。... 算法3.1 顺序查找(基于无序链表)API public class Se

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 118,348
精华内容 47,339
关键字:

无序表查找

友情链接: Promod.rar