精华内容
下载资源
问答
  • 顺序表的查找

    2021-04-08 17:17:41
    顺序表的查找 顺序表的按位查找 GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。 静态分配: typedef struct{ ElemType data[MaxSize];//用静态的“数组”存放数据元素 int length; //书序表的当前...

    顺序表的查找

    顺序表的按位查找

    GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。

    静态分配:

    typedef struct{
        ElemType data[MaxSize];//用静态的“数组”存放数据元素
        int length;         //书序表的当前长度
    }SqList;                //顺序表的类型定义(静态分配方式)
    
    ElemType GetElem(SqList L,int i){
        return L.data[i-1];
    }
    
    

    动态分配

    #define InitSize 10 //顺序表的初始长度
    typedef struct{
        ElemType *data;     //指示动态分配数组的指针
        int MaxSize;        //顺序表的最大容量
        int length;         //顺序表的当亲长度
    }SeqList;               //顺序表的类型定义(动态分配方式)
    
    ElemType GetElem(SqList L,int i){
        return L.data[i-1];
    }
    

    Tips:

    • ElemType *data是指针指向malloc分配的首地址

    • 定义另外一个指针int *p就是malloc申请的是int型的指针,即时ElemType为int型的

    顺序表的按值查找

    LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素。

    #define InitSize 10 //顺序表的初始长度
    typedef struct{
        ElemType *data;     //指示动态分配数组的指针
        int MaxSize;        //顺序表的最大容量
        int length;         //顺序表的当亲长度
    }SeqList;               //顺序表的类型定义(动态分配方式)
    
    int LocateElem(SeqList L,ElemType e){
        for(int i=0 ; i<L.length ; i++){
            if(L.data[i]==e)
                return i+1;         //数组下标为i的元素值等于e,返回其位序i+1
        return 0;                   //退出循环,说明查找失败
        }
    }
    

    基本数据类型:int、char、double、float等可以直接用运算符“==”比较

    结构类型:比较需要依次对比各个分量来判断是否相等

    时间复杂度:最好O(1)、最坏O(n)、平均O(n)

    总结

    在这里插入图片描述

    展开全文
  • 有序顺序表的查找

    2020-06-10 21:26:37
    有序顺序表的查找 一、 1.初始化一个顺序表 2.对顺序表进行顺序查找 3.建立一个有序顺序表 4.对有序顺序表进行折半查找 二、 1.首先建立一个结构体以便顺序表的使用,利用顺序查找算法的思想,我们把要查找的数存在...

    有序顺序表的查找

    一、
    1.初始化一个顺序表
    2.对顺序表进行顺序查找
    3.建立一个有序顺序表
    4.对有序顺序表进行折半查找

    二、
    1.首先建立一个结构体以便顺序表的使用,利用顺序查找算法的思想,我们把要查找的数存在List->data[0],从顺序表的后面依次向前便利直到我们找到与List->data[0]里面的元素一样的时候做好标记,返回1表示查找成功;若直到第0个元素仍未查找到,则返回0表示未查找到该元素。
    2.我们首先建立一个顺序表,我们可以利用随机函数rand()随机生成自己想要所在区间的数字,然后利用一个排序算法将它们做成一个有序顺序表(这样也就快速生成了一个有序顺序表),或是自己一个一个输入有序顺序表。再利用折半查找算法,对指定元素进行查找:首先将要查找的元素存进orderlist->data[0]里面,若该元素==orderlist->data[mid]则为找到,做好下标的标记返回一;
    若该元素大于orderlist->data[mid],则在右半部分进行查找;若该元素小于orderlist->data[mid],则在左半部分进行查找。反复进行直到当low大于high仍是未找到指定元素则返回0。

    三、具体代码如下:
    头文件如下:

    #include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    
    #define MAX 31
    
    typedef struct list{
    	int data[MAX];
    }ArrayList;
    
    ArrayList* Init_list(void);
    void SelectionSort_list(ArrayList* l);
    void SequentialSearch_list(ArrayList* l);
    void putNumber_list(ArrayList* l, int a);
    int JudgeOrder_list(ArrayList* l);
    void BinarySearch_list(ArrayList* l);
    

    主函数及自定义函数如下:

    #include"header.h"
    int main()
    {
    	ArrayList* arraylist = NULL;
    	arraylist = Init_list();
    	ArrayList* orderlist = NULL;
    	orderlist = Init_list();
    	srand(time(0));
    	for (int i = 1; i <= MAX-1; i++)
    		arraylist->data[i] = rand()%100+1;
    	for (int i = 1; i <= MAX-1; i++)
    		printf("%5d", arraylist->data[i]);
    	printf("\n请输入你要在顺序表中查找的元素: ");
    	int number;
    	scanf("%d", &number);
    	putNumber_list(arraylist, number);
    	SequentialSearch_list(arraylist);
    	printf("=====================================================\n");
    	printf("你是否想快速生成一个有序顺序表(Y or !Y): ");
    	char y;
    	setbuf(stdin, NULL);
    	scanf("%c", &y);
    	if (y == 'y' || y == 'Y')
    	{
    		printf("\n有序顺序表如下: ");
    		for (int i = 1; i <= MAX - 1; i++)
    			orderlist->data[i] = rand() % 100 + 1;
    		SelectionSort_list(orderlist);
    		for (int i = 1; i <= MAX - 1; i++)
    			printf("%5d", orderlist->data[i]);
    		putchar('\n');
    	}
    	else
    	{
    		printf("请输入你的有序顺序表(30个正序):\n");
    		setbuf(stdin, NULL);
    		for (int i = 1; i < MAX; i++)
    			scanf("%d", &orderlist->data[i]);
    		printf("您输入的有序顺序表为: ");
    		for (int i = 1; i < MAX; i++)
    			printf("%5d", orderlist->data[i]);
    		putchar('\n');
    		if (!JudgeOrder_list(orderlist))
    		{
    			printf("该有序顺序表并非有序!小编以为你转换为有序顺序表:\n");
    			SelectionSort_list(orderlist);
    			for (int i = 1; i < MAX; i++)
    				printf("%5d", orderlist->data[i]);
    			putchar('\n');
    		}
    
    	}
    	setbuf(stdin, NULL);
    	printf("请输入你要采用折半查找的元素: ");
    	scanf("%d", &number);
    	putNumber_list(orderlist, number);
    	BinarySearch_list(orderlist);
    
    	return 0;
    }
    ArrayList* Init_list(void)		//初始化一个顺序表
    {
    	ArrayList* list = (ArrayList*)malloc(sizeof(ArrayList));
    	return list;
    }
    void SelectionSort_list(ArrayList* l)		//选择排序
    {
    	for (int i = 1; i < MAX - 1; i++)
    	{
    		int min=i;
    		for (int j = i+1; j < MAX; j++)
    		{
    			if (l->data[j] < l->data[min])
    				min = j;
    		}
    		int temp = l->data[i];
    		l->data[i] = l->data[min];
    		l->data[min] = temp;
    	}
    }
    void SequentialSearch_list(ArrayList* l)		//顺序查找
    {
    	int i;
    	int k = 0;
    	printf("该顺序表");
    	for ( i = MAX - 1; i > 0; i--)
    	{
    		if (l->data[i] == l->data[0])
    		{
    			printf("第%d个\t", i);
    			k++;
    		}
    	}
    	if (k != 0)
    		printf("为查找到的元素!\n该顺序表一共含有%d个该元素\n", k);
    	else
    		printf("未找到该元素!!!\n");
    }
    void putNumber_list(ArrayList* l, int a)		//存入要查找的元素
    {
    	l->data[0] = a;
    }
    int JudgeOrder_list(ArrayList* l)		//判断是否有序
    {
    	int min = 1;
    	for (int i = 2; i < MAX; i++)
    	{
    		if (l->data[i] < l->data[min])
    			return 0;
    	}
    	return 1;
    }
    void BinarySearch_list(ArrayList* l)		//折半查找
    {
    	if (!JudgeOrder_list(l))
    	{
    		printf("您所要执行折半查找的元素并非有序!!!\n");
    		return;
    	}
    	int low,high;
    	low = 1;
    	high = MAX - 1;
    	printf("该顺序表");
    	while (high >= low)
    	{
    		int mid = (high + low) / 2;
    		if (l->data[mid] == l->data[0])
    		{
    			printf("第%d个元素为查找内容\n", mid);
    			return;
    		}
    		else if (l->data[0] < l->data[mid])
    			high--;
    		else
    			low++;
    	}
    	printf("未找到该元素!!!\n");
    }
    

    运行结果如下:
    运行结果希望对读者有所帮助!
    @all侵权删

    展开全文
  • 顺序表的查找可以用顺序查找实现 顺序查找的存储结构: typedef struct{ ElemType *elem; int length; }; 顺序查找:从表中最后一个记录进行查找 直到找到记录的关键词和给定值的记录 查找过程中的哨兵...

    顺序表的查找可以用顺序查找实现

    顺序查找的存储结构:

    typedef struct{

     ElemType *elem;

    int length;

    };

    顺序查找:从表中最后一个记录进行查找 直到找到记录的关键词和给定值的记录

    查找过程中的哨兵逻辑:

    在表头设置哨兵,从表尾进行查找,如果查找过程中遇到哨兵,则表查找结束

    查找操作的性能分析:

    主要从时间复杂度和空间复杂度进行评判:

    在时间复杂度的评判中,查找算法的基本操作为:将记录的关键字和给定值进行比较;

    则可以 “关键字与给定值进行比较的记录个数的平均值” 来评判查找操作的性能

    设Pi为与第i个记录进行比较的概率  Ci 为已与给定值进行过比较过的关键字个数;其中ΣPi=1;

    则查找成功时的平均查找长度为ASL=ΣPi*Ci;

    其中Ci取决于记录在表中的位置,如记录在第一个,采取从n到1的顺序进行查找,则需要比较查找表的长度n次 Ci=n-i+1;

    先关公式如下:

    n=length;

    ASL=nP1+(n-1)P2+....+2Pn-1+Pn;

    如果每个记录的查找概率相同,及 Pi=1/n;

    则ASL=PiΣ(Ci)=1/nΣ(n-i+1)=(1/n)(n(n+1)/2)=(n+1)/2

    当查找概率不同时,可对数据进行排序,可以提高查找效率

    方案:对数据元素增加一个数据项:访问频度;并按访问频度进行升序排列,频度越大,则数据元素在表中的位置越靠后,这样当我们从后往前查找时的效率最高,每次查找完需对该记录的频度加一;

     

    顺序查找和其他查找方法的优缺点:

    缺点:平均查找长度较大,当n很大时 插好效率很低

    优点:算法简单,比较常用

     

     

     

     

     

     

    展开全文
  • 顺序表的查找 顺序表的按位查找 注意返回值和数据元素的类型应当相同 当用动态分配进行查找时data变量为一个指针指向数据表中第一个数据元素也是用malloc函数申请顺序表的一整个存储空间虽然data变量是一个指针但也...

    顺序表的查找

    顺序表的按位查找

    在这里插入图片描述

    注意返回值和数据元素的类型应当相同

    当用动态分配进行查找时data变量为一个指针指向数据表中第一个数据元素也是用malloc函数申请顺序表的一整个存储空间虽然data变量是一个指针但也会像数组一样用下标的方式指向存储空间的元素

    如果说指针所对应的变量类型为int则data指向的地址为data[0]四个字节后为data[1],以此类推。和普通访问数据的方式一样。

    用这种方式访问数据系统的话系统在背后存取数据的时候每次取几个字节和指针指向的类型有关因此也能解释为什么用malloc函数申请一片内存空间,malloc函数返回的指针需要把其强制转换为和数据类型相对应的同类型指针因为虽然指针指向的是同一类地址但是由于指针指向的类型不同在访问数据元素的时候也会出现问题。

    按位查找的时间复杂度

    在这里插入图片描述

    安置查找

    找到线性表中有没有数据元素和传入的参数是相等的如果有则返回数据元素的存放位置

    在这里插入图片描述

    从第一个位置依次往后进行检索

    当要查找的元素类型也为结构类型时是否也可以按此类方法进行比较两个元素?

    不能

    在这里插入图片描述

    此代码不能进行编译

    按值查找的时间复杂度

    在这里插入图片描述

    总结

    在这里插入图片描述

    展开全文
  • C语言数据结构顺序表的查找算法

    千次阅读 2019-06-04 11:58:46
    *顺序表的查找算法(重点是哨兵的设置) *创建一个数据结构体 *创建一个顺序表的结构体 *顺序表结构体里面包含 数据数组 和 数组长度 *采用两种查找方法 哨兵设置 普通查找 *哨兵排序算法的设置的好处是可以降低时间...
  • 顺序表的查找 顺序查找 其实顺序查找可以理解为就是地毯式搜索,在找到正确答案之前我们都会一直地往下一个数去找。 1.准备工作 #include<iostream> #include<ctime> using namespace std; typedef ...
  • 查找-顺序表的查找

    2014-12-24 00:22:00
    查找-顺序表的查找 相关术语:  查找表:(Search Table)是由同一类型的数据元素(或记录)构成的集合。  关键字:(Key)是数据元素中某个数据项的值,又称为键值,它可以标识一个数据元素。 ...
  • (1)验证并设计顺序表的查找(顺序查找、折半查找)算法 (2)验证二叉排序树上的查找(创建、查找、插入)算法 (3)验证Hash表查找(Hash函数定义、建立,查找,插入)算法 //顺序表的顺序查找 折半查找 二叉...
  • 数据结构顺序表的查找。顺序查找!c语言编写!!!!!!!
  • 6-1 顺序表的查找操作 (10分)

    千次阅读 2020-06-09 22:03:47
    6-1 顺序表的查找操作 (10分) 本题要求实现一个函数,要求从顺序表中查找指定元素,并返回第一个查找成功的元素在表中的位置序号,若查找失败,则返回0; 函数接口定义: int LocateElem(SqList L,ElemType e); ...
  • 顺序表的查找可以分为两类,一个是顺序查找,一个是二分查找。 一般而言,我们讨论的都是给定关键字的查找。例如一个数组a[6]={1,2,3,4,5,6},我们给定一个关键字为3,就可以来查找它是否在我们的数组中了。查找成功...
  • . . . 计算机科学与技术系 实 验 报 告 专业名称 计算机科学与技术 课程名称 ...一实验目的 应用顺序表来实现对数据的查找 二实验要求 用顺序表实现对数据进行查找 三实验环境 VC++6.0. 二实验内容 #include<stdio.h
  • @【数据结构】(顺序表的查找) #include<iostream> #include<stdio.h> #include<stdlib.h> #define MAX 100 using namespace std; typedef struct { int data[MAX]; int last; }List; List *...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,844
精华内容 4,737
关键字:

顺序表的查找