精华内容
下载资源
问答
  • 数据结构顺序查找
    千次阅读
    2017-10-19 20:24:34

    Ⅰ )算法思想:

          在表的一端设置一个称为“监视哨”的附加单元,存放要查找元素的关键字,从表的另一端开始查找,如果在“监视哨”找到要查找元素的关键字,返回失败信息,否则,返回相应下标。

    Ⅱ)性能分析:

          假设列表长度为n,那么查找到第i 个元素时,需要进行n-i+1次比较。

          ASL =  1/n∑(n-i+1) = (n+1)/2

    Ⅲ)源代码:

    #include<stdio.h>
    #define MaxSize 20                  //线性表长度
    typedef struct
    {
        int key;
    }RecordType;
     
    typedef struct
    {
        int length;
        RecordType r[MaxSize + 1];       
    }RecordList;
     
    int SeqSearch(RecordList l, int key)
    {
        int i;
        l.r[0].key = key;                    //将要查找的值赋给监视哨
        i = l.length;
        while (l.r[i].key != key)              
        {
            i--;
        }
        return i;                             //当l.r[i].key == key时返回下标
    }
     
    int main()
    {
        RecordList L = { 6, 0, 12, 15, 20, 25, 45, 50 };
     
        printf("%d\n", SeqSearch(L, 20));            //输出元素20所在的下标
     
        return 0;
    }

    更多相关内容
  • 数据结构顺序查找

    2018-12-10 13:58:04
    数据结构查找 主要为顺序查找和折半查找的具采用c++语言实现
  • 数据结构顺序查找.cpp

    2020-12-24 13:03:28
    顺序查找
  • 顺序查找源代码 #include #include typedef struct{ char *elem; int length; }SSTable; char key;
  • 顺序查找 折半查找的平均查找长度分析 ASL:平均查找长度 其中n为查找表中元素个数,Pi为查找第i个元素的概率,通常假设每个元素查找概率相同,Pi=1/n,Ci是找到第i个元素的比较次数。 ASL=∑i=1npici ASL=\sum_{i=1...

    顺序查找 折半查找的平均查找长度分析

    ASL:平均查找长度

    其中n为查找表中元素个数,Pi为查找第i个元素的概率,通常假设每个元素查找概率相同,Pi=1/n,Ci是找到第i个元素的比较次数。
    A S L = ∑ i = 1 n p i c i ASL=\sum_{i=1}^{n} p_ic_i ASL=i=1npici

    一般顺序查找的平均查找长度:

    • 因为顺序查找就是顺序存储 一个一个比较,所以如果查找成功的话说明就和之前不相等的元素已经比较过了。
    • 所以第 n 个元素就是比较了 n 次
    • 每个元素都比较了其所在位序的次数
    • 每个元素被查找的概率都是1/n 所以

    A S L 成 功 = 1 n ( 1 + 2 + 3 + … + n ) = n + 1 2 ASL_{成功}=\frac{1}{n}(1+2+3+…+n)=\frac{n+1}{2} ASL=n1(1+2+3++n)=2n+1

    $ASL_{成功}=n+1 $

    有序顺序表的平均查找长度:

    • 查找成功的 ASL 不影响

    • 如果查找不成功的话,因为顺序表有序,所以可以提前结束,从而缩短查找失败的比较次数,需要画个简单【判定树】

    • 举个例子,在[10 20 30 40 50 60]中查找

    image-20210924175755222
    • 失败的一共有 n+1个结点,所以每个结点的概率就是 1 n + 1 \frac{1}{n+1} n+11
    • 比较次数是 每个失败结点上一层的层数

    A S L 失 败 = 1 n + 1 [ 1 + 2 + 3 + … + n + n ] = n 2 + n n + 1 ASL_{失败} = \frac{1}{n+1}[1+2+3+…+n+n]=\frac{n}{2}+\frac{n}{n+1} ASL=n+11[1+2+3++n+n]=2n+n+1n

    折半查找的平均查找长度:

    • 要涉及到判定树:n 个元素就有n 个【内部结点】 n+1个【外部结点】

    • 【判定树】一定是【满二叉树】

    • 根据折半算法画出初级判定树(只有内部结点),其他空位用【查找失败的方框代替】

    • 算 ASL 直接就是算 [每层结点的个数*层数]➗结点个数

    image-20210924180742717

    • 不成功要具体例子具体计算。
    展开全文
  • 顺序查找的实现 顺序查找的一般过程为:从表的一段开始,依次将记录的关键字和给定的值进行比较,若某个记录的关键字和给定值相等,则查找成功;反之,若扫描整个表后,仍未找到关键字和给定值相等的记录,则查找...

    顺序查找的实现

    顺序查找的一般过程为:从表的一段开始,依次将记录的关键字和给定的值进行比较,若某个记录的关键字和给定值相等,则查找成功;反之,若扫描整个表后,仍未找到关键字和给定值相等的记录,则查找失败。

    数据元素类型定义如下:

    typedef struct{
        keytype key;//关键字域
        InfoType otherinfo;//其他域
    }ElemType;

    顺序表的定义如下: 

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

     R可以理解成一个数组,用来存放数据的元素。开始时,元素从R[1]开始顺序向后存放,R[0]暂时闲置不用,之后设置监视哨,将它放置到R[0]。查找时从表的最后依次与监视哨开始比较(顺序表的一端添加用户用于搜索的关键字,称作“监视哨)放置好监视哨之后,顺序表遍历从没有监视哨的一端依次进行,如果查找表中有用户需要的数据,则程序输出该位置;反之,程序会运行至监视哨,此时匹配成功,程序停止运行,但是结果是查找失败.

     顺序查找的具体实现代码为:

    #include <stdio.h>
    #include <stdlib.h>
    #define keyType int
    typedef struct {
        keyType key;//查找表中每个数据元素的值
        //如果需要,还可以添加其他属性
    }ElemType;
    typedef struct{
        ElemType *elem;//存放查找表中数据元素的数组
        int length;//记录查找表中数据的总数量
    }SSTable;
    //创建查找表
    void Create(SSTable **st,int length){
        (*st)=(SSTable*)malloc(sizeof(SSTable));
        (*st)->length=length;
        (*st)->elem =(ElemType*)malloc((length+1)*sizeof(ElemType));
        printf("输入表中的数据元素:\n");
        //根据查找表中数据元素的总长度,在存储时,从数组下标为 1 的空间开始存储数据
        for (int i=1; i<=length; i++) {
            scanf("%d",&((*st)->elem[i].key));
        }
    }
    //查找表查找的功能函数,其中key为关键字
    int Search_seq(SSTable *st,keyType key){
        st->elem[0].key=key;//将关键字作为一个数据元素存放到查找表的第一个位置,起监视哨的作用
        int i=st->length;
        //从查找表的最后一个数据元素依次遍历,一直遍历到数组下标为0
        while (st->elem[i].key!=key) {
            i--;
        }
        //如果 i=0,说明查找失败;反之,返回的是含有关键字key的数据元素在查找表中的位置
        return i;
    }
    int main() {
        SSTable *st;
        Create(&st, 6);
        getchar();
        printf("请输入查找数据的关键字:\n");
        int key;
        scanf("%d",&key);
        int location=Search_seq(st, key);
        if (location==0) {
            printf("查找失败");
        }else{
            printf("数据在查找表中的位置为:%d",location);
        }
        return 0;
    }

    代码中设置了一个固定长度为6的顺序表,运行结果为:

     顺序查找的优缺点:优点:算法简单,对表结构无任何要求,既适用于顺序结构,也适用于链式结构,无论记录是否按关键字有序均可应用。缺点:平均查找长度较大,查找效率低,所以当n很大时,不宜用顺序查找。

    展开全文
  • 顺序查找 //顺序查找 #include<stdio.h> #define MAXSIZE 30 typedef struct { int key;//int为关键字key的数据类型 char data;//其他数据,可有可无 } SeqList;//顺序表元素类型 int SeqSearch(SeqList R...

    顺序查找

    //顺序查找
    #include<stdio.h>
    #define MAXSIZE 30
    typedef struct
    {
    	int key;//int为关键字key的数据类型
    	char data;//其他数据,可有可无 
     } SeqList;//顺序表元素类型
    
    int SeqSearch(SeqList R[],int n,int k)
    {
    	int i=n;
    	R[0].key=k;//R[0].key 为查找不成功的监视哨
    	while(R[i].key !=k)//由表尾向表头方向查找 
    	   i--;
    	return i;//查找成功返回找到的位置值,否者返回0 
     }
    int main()
    {
    	int i=0,j,x;
    	SeqList R[MAXSIZE];//建立存放顺序表的元素
    	//生成顺序表中的数据(-1结束)
    	scanf("%d",&x);
    	while(x!=-1)
    	{
    		R[i].key=x;
    		scanf("%d",&x);
    		i++;
    	 }
    	//输出顺序表中的数据
    	for(j=0;j<i;j++)
    	    printf("%2d",R[j].key);
    	//输入查找的数据(-1)结束
    	scanf("%d",&x);
    	i=SeqSearch(R,i,x);
    	if(i>0)
    		printf("Position of %d in SeqList is %d\n",x,i+1);//找到输出顺序表中的位置
    	else
    		printf("No Fund %d in SeqList!\n",x);//输出未找到的信息
     }
    /*测试数据:
    1
    2 3 4 5 6 -1
    2
    
    1
    2 3 4 5 6 -1
    8
    
    */ 
    
    展开全文
  • 数据结构顺序查找和折半查找

    千次阅读 多人点赞 2021-04-03 08:07:36
    摘要:在本篇文章中,主要讲述了在数据结构中所涉及的几大查找算法,包括:顺序查找、折半查找、分块查找和散列表查找。这些查找方式都是数据结构中最基本的查找方式,并且在数据结构中运用广泛。在查找算法中,最为...
  • C语言 数据结构 作业 顺序查找 折半查找
  • 数据结构29:顺序查找算法及分析

    千次阅读 2020-09-21 20:15:50
    通过下标,我们可以按照顺序来访问和查找数据项,这种技术称为“顺序查找”。 要确定列表中是否存在需要查找的数据项。 首先从列表的第一个数据项开始,按照下标增长的顺序,逐个对比数据项,如果.
  • 一、实验目的: 熟悉各种查找算法及其复杂性,能够根据实际情况选择合适的存储结构。 二、实验要求: 1、掌握查找的基本方法。 2、提交实验报告,报告...编程分别对有序顺序表的顺序查找,二分查找算法进行实现。
  • 数据结构-查找-顺序查找

    千次阅读 2021-07-02 13:19:13
    数据处理的过程中,是否能在时间内查找到所需要的数据是一个相当值得重视的问题。所谓查找(search),指的是在数据文件中找出满足某些条件的记录。用以查找的条件称作为“键值(Key)”,就如同排序所用的键值一样。 ...
  • 数据结构查找--顺序表的顺序查找

    千次阅读 2021-11-20 19:49:26
    顺序查找:从表的一端开始,依次将记录在...数据结构类型定义如下: typedef struct { KeyType key; //关键字域 InfoType otherinfo; //其他域 }ElemType; 定义单个结点后,再定义顺序表 typedef struct { ...
  • 洛阳理工学院实验报告 系别 计算机 班级 学号 姓名 课程名称 数据结构 实验日期 10/23 实验名称 顺序表的基本操作 成绩 实验目的 熟悉掌握线性表顺序存储结构掌握与应用顺序表的查找插入删除等基本操作算法训练和...
  • 合工大数据结构c++实验报告顺序查找Visio流程图
  • 折半查找算法 顺序表 折半查找算法C语言版
  • C语言数据结构,包括栈、队列的操作,二叉树,顺序查找,二分查找,哈夫曼树,图遍历等。
  • 数据结构顺序查找验证程序

    千次阅读 2016-12-03 09:24:42
    算法分析:顺序查找是在一个已知无(或有序)序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从最后一个开始逐个比较,直到找出与给定关键字相同的数为止,它的缺点是效率低下。    ...
  • 数据结构查找 顺序查找和折半查找 》 //顺序查找 //思路:从表中最后一个记录开始,逐个进行记录的关键字和 //给定值的比较,若某个记录的关键字和给定值比较相等,则 //返回返回记录所在的位置,或...
  • 数据结构顺序表的查找

    千次阅读 2017-12-06 14:17:58
    利用顺序查找数据。#include #include using namespace std; #define LIST_INIT_SIZE 100//顺序表存储空间的初始分配量 #define OK 1 #define ERROR 0 #define LT(a,b) ((a)(b)) typedef int KeyType; ...
  • 用c语言写的数据结构预算法的实验
  • PAGE 1 数据结构实验报告1 学院 专业 班级 姓名 学号 实验组 实验时间 2011-10-28 指导教师 成绩 实验项目名称 线性表的顺序存储结构 实验目的 1. 熟练掌握线性表的基本操作在顺序存储和链式存储上的实现 2. 以...
  • 顺序查找:速度慢例如:100万个数据,平均要找50万次没有排序的数据:只能顺序查找#include &lt;iostream&gt;using namespace std;int SequeSearch(int *a, const int n, const int x);int main(){ int m[]...
  • 查找排序算法的应用 班级 学号 姓名 一实验目的 1 掌握查找的不同方法并能用高级语言实现查找算法 2 熟练掌握顺序表和有序表的顺序查找和二分查找方法 3 掌握排序的不同方法并能用高级语言实现排序算法 4 熟练掌握...
  • 数据结构: 顺序查找

    千次阅读 2018-05-29 23:15:21
    有哨兵顺序查找意思就是将数组a[0]存下要查找的数,从数组的尾巴开始查找,若顺序查找函数返回的是非0值就代表查找成功,否则查找失败。#include&lt;stdio.h&gt; int Sequence_search(int *a,int n, int key...
  • 数据结构顺序查找(Sequential Search)

    千次阅读 2012-08-17 22:00:04
    查找: 就是在数据中寻找特定的值,这个值称为“关键码(key)”。 查找的目的: ...就是为了确定数据中是否...其中顺序查找法是使用未经排序的数据。 另外三种方法都需要将数据先排序好后,然后才能使用。 除
  • 数据结构-顺序表的查找插入与删除.pdf
  • #include<stdio.h> #include<stdlib.h> #define MAXSIZE 50 ...//顺序查找 int search(sqlist ST, int key) { int i; ST.elem[0] = key; for (i = ST.length; ST.elem[i] != key; --i); retur.

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 468,205
精华内容 187,282
关键字:

数据结构顺序查找

数据结构 订阅