精华内容
下载资源
问答
  • 顺序查找的缺点是n较大时,平均查找长度较大,效率低 优点对数据元素存储没有要求,顺序存储或链式存储均可;对表中记录的有序性也没有要求 */ #include <stdlib.h> #include<stdio.h> #define LIST_...
    /*基于线性表的查找法——顺序查找法      
    顺序查找的缺点是n较大时,平均查找长度较大,效率低
    优点对数据元素存储没有要求,顺序存储或链式存储均可;对表中记录的有序性也没有要求
    */
    #include <stdlib.h>
    #include<stdio.h>
    #define LIST_SIZE 20
    
    //链表结点类型
    typedef struct {
        int key;
        int data;
    }RecordType;
    
    //链表数组结构
    typedef struct {
        RecordType r[LIST_SIZE+1];      
        int length;
    }RecordList;
    
    //初始化链表数组
    int Init_Seq(RecordList *RecordList){
        if (!RecordList->r) 
            return -1;
        else {
            RecordList->length = 0;
            return 1;
        }
    }
    
    //设置监视哨的顺序查找法 耿国华版本
    int SeqSearch(RecordList l,int k){
        l.r[0].key = k;
        int i = l.length;
        while (l.r[i].key!=k)
            i--;
        return i;
    }
    
    /*不设置监视哨的顺序查找法 耿国华版本 
      虽然没有设置监视哨 但是还是空出来了第一个位置
      如果要实现从实际地址的第一个元素开始排序 那么i的条件则改为i>=0且如果查找失败的话 返回值要设置为-1 最后在输出下标的时候就需要index+1来调整
    */
    int SeqSearch(RecordList l, int k) {
        int i = l.length;
        while (i>=1&&l.r[i].key != k)
            i--;
        if (i >= 1)
            return i;
        else
            return 0;
    }
    
    void main() {
        RecordList *S1 = (RecordList*)malloc(sizeof(RecordList));
        int a=Init_Seq(S1);
        //给链表数组赋值 如果在带有监视哨 要将数组的第一个位置空余出来不对其赋值
        for (int j = 0; j < 10; j++)
        {
            S1->r[j].key = j*2;
            S1->length++;
        }
        //数组成功赋值后的值
        printf("数组为:");
        for (int j = 0; j < 10; j++)
        {
            printf("%d ", S1->r[j].key);
        }
        //进行顺序查找 k代表关键字的值
        int k = 8;
        int index = SeqSearch(*S1, k);
        printf("\n关键字%d在%d个位置\n", k,index);
    
        system("pause");
    }

    展开全文
  • 线性表顺序查找和折半查找顺序查找设置监视哨的顺序查找非递归折半查找递归折半查找代码整合测试 顺序查找 //顺序查找 int Search_Seq01(SSTable ST,KeyType key) { for(int i=ST.length;i>=1;i--) if(ST.R...

    顺序查找

    //顺序查找
    int Search_Seq01(SSTable ST,KeyType key)
    {
    	for(int i=ST.length;i>=1;i--)
    		if(ST.R[i].key==key) return i;
    	return 0;
    }
    

    设置监视哨的顺序查找

    //设置监视哨的顺序查找
    int Search_Seq02(SSTable ST,KeyType key)
    {
    	int i;
    	ST.R[0].key = key;
    	for(i=ST.length;ST.R[i].key!=key;i--);
    	return i;
    }
    

    非递归折半查找

    //非递归折半查找
    int Search_Bin01(SSTable ST,KeyType key)
    {
    	int low=1,high=ST.length,mid;    //low和high分别为表的上下界 
    	while(low<=high)
    	{
    		mid=(low+high)/2;     //取中间位置 
    		if(ST.R[mid].key==key) return mid;    //找到给定值 
    		else if(ST.R[mid].key>key) high = mid-1;   //前往前一个子表 
    		else low = mid + 1;    //前往后一个子表 
    	}
    	return 0;
    }
    

    递归折半查找

    //递归折半查找
    int Search_Bin02(SSTable ST,KeyType key,int low,int high) 
    {
    	int mid = (low+high)/2;
    	if(ST.R[mid].key==key) return mid;   //找到给定值 
    	else if(ST.R[mid].key>key) Search_Bin02(ST,key,low,mid-1);   //前一个子表递归查找 
    	else Search_Bin02(ST,key,mid+1,high);        //后一个子表递归查找 
    }
    

    代码整合测试

    #include <stdio.h>
    #include <stdlib.h>
    
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    #define MAXSIZE 20
    
    typedef int Status;
    typedef int KeyType;
    typedef int InfoType;
    typedef struct
    {
    	KeyType key;   //关键字域 
    	InfoType otherInfo;   //其他域 
    }ElemType;
    typedef struct
    {
    	ElemType *R;   //储存空间基地址 
    	int length;    //当前长度 
    }SSTable;
    
    //初始化一个自定义类型线性表
    Status InitTable(SSTable *ST)
    {
    	ST->R = (ElemType *)malloc(MAXSIZE*sizeof(ElemType));    //开辟空间,别漏了sizeof(ElemType) 
    	if(ST->R == NULL) return ERROR;
    	ST->length =0;
    	return OK;
    }
    
    //顺序查找
    int Search_Seq01(SSTable ST,KeyType key)
    {
    	for(int i=ST.length;i>=1;i--)
    		if(ST.R[i].key==key) return i;
    	return 0;
    }
    
    //设置监视哨的顺序查找
    int Search_Seq02(SSTable ST,KeyType key)
    {
    	int i;
    	ST.R[0].key = key;
    	for(i=ST.length;ST.R[i].key!=key;i--);
    	return i;
    }
    
    //非递归折半查找
    int Search_Bin01(SSTable ST,KeyType key)
    {
    	int low=1,high=ST.length,mid;    //low和high分别为表的上下界 
    	while(low<=high)
    	{
    		mid=(low+high)/2;     //取中间位置 
    		if(ST.R[mid].key==key) return mid;    //找到给定值 
    		else if(ST.R[mid].key>key) high = mid-1;   //前往前一个子表 
    		else low = mid + 1;    //前往后一个子表 
    	}
    	return 0;
    }
    
    //递归折半查找
    int Search_Bin02(SSTable ST,KeyType key,int low,int high) 
    {
    	int mid = (low+high)/2;
    	if(ST.R[mid].key==key) return mid;   //找到给定值 
    	else if(ST.R[mid].key>key) Search_Bin02(ST,key,low,mid-1);   //前一个子表递归查找 
    	else Search_Bin02(ST,key,mid+1,high);        //后一个子表递归查找 
    }
    
    int main()
    {
    	SSTable ST;
    	InitTable(&ST);    //初始化顺序表 
    	for(int i=1;i<=20;i++)   //循环赋值 
    	{
    		ST.R[i].key = i;
    		ST.length+=1;
    	}
    	printf("%d\n",ST.R[Search_Seq02(ST,2)].key);    //由上往下对应查找 
    	printf("%d\n",Search_Seq01(ST,3));
    	printf("%d\n",Search_Bin01(ST,9));
    	printf("%d",Search_Bin02(ST,14,1,20));
    	return 0;
    }
    
    展开全文
  • 查找: 给定一个值k,在含有n个元素的表中找出关键字等于k的元素,若找到,则查找成功,否则,查找失败 查找前首先确定(1)存放数据的数据结构是什么(2)...线性表查找是一种最简单的查找表,分为顺序查..

    查找:

    给定一个值k,在含有n个元素的表中找出关键字等于k的元素,若找到,则查找成功,否则,查找失败

    查找前首先确定(1)存放数据的数据结构是什么(2)元素是否有序

    动态查找表:查找的同时做修改操作(插入,删除)

    静态查找表:查找中不涉及表的修改操作

    内查找:整个查找过程都在内存中进行

    外查找:查找过程需要访问外存

    平均查找长度(ASL):平均需要比较的次数

     ASL分为查找成功和查找失败两种情况

    ASL越小,其时间性能越好

    线性表的查找是一种最简单的查找表,分为顺序查找折半查找(二分法) 

    顺序查找:

    思路:从表的一端向另一端逐个将关键字和定值k比较,若相等,则查找成功;否则查找失败

    while(i<size&&key!=a[i])
    {
    i++;
    }
    if(i>=size)
    {
    //查找失败
    }
    else
    {
    //查找成功
    
    }
    

    性能分析:

    查找成功的ASL:

     

     综上,线性表顺序查找的时间复杂度为O(n)

    折半(二分)查找:

    折半查找又叫二分查找,要求元素有序(递增或者递减),下面讨论递增的情况

    思路:

    nums[low,..,high]是当前查找区间,首先确定中点mid=(low+high)/2,然后将待查找的值k和

    nums[mid]比较:

    (1)nums[mid]=k,查找成功

    (2)nums[mid]<k,说明k在右子表nums[mid+1,high]中

    (3)nums[mid]>k.说明k在左子表nums[low,mid-1]中

    重复这一过程

    代码:
     

    binsearch(int nums[],int k,int n)
    {
    int low=0;
    int high=n-1;
    while(low<=high)
    {
    mid=(low+high)/2;
      if(k==nums[mid])
     {
    return mid;
    }
    else if(k<nums[mid])
    {
    high=mid-1;
    }
    else 
    low=mid+1;
    }
    return -1;
    }

    二分查找的判定树(比较树):

     内部节点:判定树中查找成功对应的节点

     外部节点:判定树中查找失败对应的节点

    外部节点的构造方法:

    对于内部节点的单分支点,添加一个孩子节点成为双分支节点;

    对于内部节点的叶子节点,添加两个孩子节点成为双分支节点

     利用判定树求二分查找的ASL:

    查找成功时,每个元素对应的概率为1/n,比较次数为根节点到该元素对应的节点的节点树(不是分支树)

    查找失败是,每个外部节点的概率如果近似看出相等,每个外部节点的概率为1/N(N为外部节点的个数),比较次数为根节点到外部节点的边的个数

     

     

     

     

     

     

     

    展开全文
  • int data[N]; int index;//初始值-1,代表里面没有元素,使用时代表下标。 }*List; 第一种方法:顺序双指针法 指针i控制向后遍历,指针j记录需要交换的位置。、 1、进入循环,当遇到item元素时,不做任何...

    为了方便描述过程,假定一个线性表结构体ArrayList

    typedef struct ArrayList{
    	int data[N];  
    	int index;//初始值为-1,代表里面没有元素,使用时代表下标。
    }*List;
    
    • 第一种方法:顺序双指针法

    指针i控制向后遍历,指针j记录需要交换的位置。、

    1、进入循环,当遇到item元素时,不做任何处理,否则将指针i指向的值赋予指针j的位置,且指针j右移

    2、循环终止,最终将线性表的index等于j-1的位置。(最后一步的index位置,看index的含义,代表下标就j-1,逻辑位置就直接等于j即可)

    在这里插入图片描述

    代码实现:

    void deletes(List list,int item){
    	int j=0;
    	for(int i=0;i<=list->index;++i){
    		if(list->data[i]!=item){
    			list->data[j]=list->data[i];
    			++j;
    		}
    	}
    	list->index=j-1;
    } 
    
    • 第二种方法:前后双指针法

    因为题目没有要求说非item元素是按照原来的顺序,所以可以采用该方法。

    1、设置前后两个指针,i=0,j=index

    2、i从前遍历,直到找到item元素的位置,j从后遍历,直到找到不是item元素的位置,将指针j指向的值放到指针i的位置,循环往复,直到i>j,结束循环。

    3、设置index的位置。

    在这里插入图片描述

    代码实现:

    void deletes(List list,int item){
    	int i=0,j=list->index;
    	while(i<=j){
    		while(i<=j && list->data[i]!=item) i++;
    		if(i<=j) while(i<=j && list->data[j]==item) j--;
    		if(i<=j) list->data[i++]=list->data[j--];
    	}
    	list->index = j;
    }
    

    注意点:每次循环前都要先判断i,j的位置,防止出现越界,或不满足的情况。

    展开全文
  • 存储结构查找表为线性表,其存储结构一维结构数组,也即是顺序表,数组的每一个元素对应查找表的一个记录...顺序查找顺序查找(Sequential Search)是一种最简单的查找方法。现假设查找表中有n个记录,顺序存放在某...
  • 已知长度为n线性表A采用顺序储存结构,请写出一个时间复杂度O(n),空间复杂度O(1)的算法,该算法可删除线性表中的所有值item的数据元素。 源代码: #include <stdio.h> #include <stdlib.h> #...
  • 【单选题】在长度为 n 的顺序表中进行顺序查找,查找失败时需与键值比较次数是 ( ) 。【单选题】一个具有n个顶点e条边的图中,所有顶点的度数之和等于 ( )。(5.0分)【填空题】假设在有序线性表a[20]上进行折半查找,则...
  • 数据结构学习——线性表顺序表示及实现线性表顺序表示及实现基本概念存储表示顺序表的操作1.查找(按值查找)2.插入算法插入算法整合代码完整cpp 线性表顺序表示及实现 基本概念 顺序存储:把逻辑上相邻的数据...
  • 顺序线性表查找操作 线性表查找操作:线性表l查找第一个与元素e满足compare()元素的位置。若在,返回其在l中的次序。若不存在则输出不存在 。 int locateelem_sq(sqlist *l,elemtype e,status (*compare)...
  • /* Description:线性表查找_折半查找(C语言源代码) /* Date:2021/9/1 /* Author:汝南城 /****************************************************/ #include <stdio.h> #include<stdlib.h> #define ...
  • 1.1线性表·顺序

    2021-06-01 14:35:47
    线性表是最常用且最简单的一种数据结构。一个线性表n个数据元素的有限序列。在稍复杂的线性表中,一个数据元素可以由若干个数据项组成。在这种情况下,常把数据元素称为记录,含有大量记录的线性表you ...
  • 线性表顺序存储

    2021-03-17 22:16:47
    线性表顺序存储 你好! 这是我第一次使用博客记录我学习的生活,废话不多说,在你基本了解C语言和或者对数组,指针,结构体有比较好的一个掌握的话,那么你学习第一章后,理解一下顺序表概念,就从阿牛理解的角度...
  • 一、顺序存储的线性表抽象数据类型定义: #include&amp;amp;amp;amp;amp;lt;stdio.h&amp;amp;amp;amp;amp;gt; #include&amp;amp;amp;amp;amp;lt;stdlib.h&amp;amp;amp;amp;amp;gt; #define ...
  • 顺序查找、折半查找,都是在一个线性表中,查找指定的关键字。它们的区别是,折半查找需要该线性表本身是有序的,而顺序查找则没有这个限制。
  • 顺序表作为线性表最基本的一种结构。本文介绍了顺序表的定义和特点,然后给出了顺序表的常见各种操作和代码,包括了初始化、查找、插入、删除和归并(合并),并分析了程序的复杂度。
  • 2.2 线性表顺序映象

    2021-05-12 14:51:52
    // 线性表的动态分配 顺序存储结构 # include <stdio.h> # include <malloc.h> //包含了malloc函数 # include <stdlib.h> //包含了exit函数 #define LIST_INIT_SIZE 100 // 线性表存储空间的初始...
  • 线性表的数据对象集合{a1,a2,.....,an},每个元素的类型均DataType。其中,除第一个元素a1外,每一个元素有且只有一个直接前驱元素;除了最后一个元素an外,每一个元素有且只有一个直接后继元素。数据元素
  • 数据结构线性表的查找-顺序查找-二分查找-分块查找 顺序查找是最基本的查找算法,从表的开头或结尾依次对表中的元素进行对比,直到成功找到关键字或是将表中的所有元素对比一遍。
  • 顺序表(线性表顺序存储结构)及C语言实现

    万次阅读 多人点赞 2018-02-06 09:48:55
    逻辑结构上呈线性分布的数据元素在实际的物理存储结构中也同样相互之间紧挨着,这种存储结构称为线性表顺序存储结构。 也就是说,逻辑上具有线性关系的数据按照前后的次序全部存储在一整块连续的内存空间中,...
  • 一、线性表顺序存储 1、线性表顺序存储原理 线性表顺序存储(Sequential Mapping,简称顺序表),是指用一组地址连续的存储单元按线性表元素之间的逻辑顺序,依次存储线性表的数据元素。数据元素的逻辑顺序和...
  • 线性表长度线性表元素的个数n 线性表的抽象数据类型: ADT线性表(list) Data 线性表的数据对象集合{a1,a2,……,an},每个元素的类型均Datatype。其中,除第一个元素a1外,每一个元素有且只有一个直接...
  • 线性表顺序存储结构及基本操作

    千次阅读 2018-10-03 22:16:36
    学习书籍《大话数据结构》,自学完后,总结一下,以后也好复习 ,欢迎互相...ListEmpty(L): 若线性表为空,返回true,否则返回false ClearList(*L): 将线性表清空 GetElem(L,i,*e) : 将线性表L中的第i个位置元...
  • 线性表查找

    千次阅读 2018-03-14 12:25:48
    在这种条件下,查找的定义是:给定一个值k,在含有n个记录的表中找出关键字等于k的记录。若找到,则查找成功,返回该记录的信息或该记录在表中的位置;否则查找失败,返回相关的指示信息。 若在查找的同时对表做修改...
  • 文章目录1.线性表:1.1线性表的定义及逻辑表示2.线性表顺序存储结构——顺序表2.1顺序表定义2.2建立顺序表2.3...线性表顺序存储结构是把线性表中的所有元素按照顺序存储方法进行存储,如下图所示 2.2建立顺序
  • 顺序查找

    千次阅读 2018-10-13 23:48:24
    顺序查找的缺点是当n很大时,平均查找长度较大,效率低;优点是对数据元素的存储没有要求,顺序存储和链式存储皆可。 一般线性表顺序查找 基本思想:从线性表的一段开始,逐个检查关键字是否满足给定的条件。若...
  • 查找线性表查找

    2021-03-14 00:46:48
    查找的基本概念什么是查找?...此外,如果查找的全过程都在内存中进行,称之查找;反之,如果查找过程中需要访问外存,称之查找查找算法性能比较的标准——平均查找长度ASL(Average Search Len...
  • 代码:(详解请看注释) #include<stdio.h> #include<stdlib.h>//动态分配需要的头文件 #define LIST_INIT_SIZE 100 #define LISTNCREAMENT 10 ...//线性表动态分配内存的顺序存储结构 typedef struct
  • 数据结构之线性表线性表顺序存储结构-----------顺序表基本运算 线性表顺序存储结构-----------顺序表 值传递:实参到形参,不改变内部参数。 指针传递(占空间):形参指向实参的地址,影响函数内部参数。 ...
  • 当我们要在线性表顺序存储结构上的第i个位置上插入一个元素时,必须先将线性表的第i个元素之后的所有元素依次后移一个位置,以便腾空一个位置,再把新元素插入到该位置。若要删除第i个元素时,也必须把第i个元素...
  • 有序线性表查找平均长度 ...长度为10的表,采用顺序查找法,平均查找长度ASL是? 如果一定可以找到的: 则10个数,每个被找到的概率是1/10; 每个元素被找到的长度分别是:1,2,3,。。,10; ASL=(1+2+3+。。+10...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 22,746
精华内容 9,098
关键字:

对于长度为n的线性表进行顺序查找