顺序表的查找

顺序表首先你要知道的一点就是它是用一组地址连续的储存单元依次存储线性表中的每个元素，采用的存储结构是顺序存储结构，可以通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，这句话是不是有点难懂，没事看下面这张图你就知道了哦

这是顺序表的储存结构图

 

可以看到这张图的loc(a1),loc(a1)+k……loc(a1)+(n-1)*k就是数据元素的存储地址，也就是数据元素的物理存储的相邻关系，而在表的右边是逻辑地址数1，2，3……，k为每个数据元素的存储单元的多少，如果已经知道了第一个数据元素的存储地址那么第2个元素（也就是逻辑地址数为2）的存储地址就是loc(a1)+k，第3个数据元素的存储地址就是loc(a1)+2k，以此类推第n个数据元素的存储地址就是loc(a1)+(n-1)*k，而顺序表就反映出了这样的关系，这就是对于我放这张图之前说的话的解释，其实就是帮你初步了解一下顺序表，说到这里，你如果是有一些编程基础的话，肯定会想到我们曾经学过的数组与之类似，其实，数组就是顺序表，我们再定义创建顺序表的时候其实就是用的数组

关于顺序表有哪些功能

1. 查找顺序表里的某个元素
2. 往顺序表里面插入元素
3. 删除顺序表的某个元素
4. 将两个顺序表合并

如何写代码呢

首先我们创建一个结构体，把它命名为seqlist

​
#include <stdio.h>
struct seqlist
{
	int elem[MAXSIZE];//这里我们拿整型数组来作示范
	int last;//last用来记录表中最后一个元素的下标值，注意是下标值，所以我们last从-1开始取 
}n;//我一开始写的时候这里的n直接写成了*l本来想着直接用这个l指针的但是这么写l就是空的没有指向，所以才会出错
 
​

别忘了对MAXSIZE进行宏定义赋值#define MAXSIZE 10

看一下我们写的主函数

int main()
{
    seqlist *l;
    l=&n;
	int i=0;//计数器
	int a;//你要查找的数字 
	int data;
	for(int j=0;j<3;j++)
	{
		printf("输入第%d个初始数据:",j+1);
		scanf("%d",&data);
		l->elem[j]=data;
	}
	printf("输入你要查找的数字\n");
	scanf("%d",&a);
	int number=search(l,a,i);
	if(number==-1)
	{
		printf("找不到与之对应的元素\n");
	}
	if(number!=-1)
	{
		printf("找到了该元素该元素为第%d个元素\n",number+1);
		printf("该元素的值为%d\n",l->elem[number]);
	}
}

这里可以看到大体思路先输入三个数据然后进行查找如果找到了就输出对应的下标以及元素值如果没找到就提示没找到

在主函数里写seqlist *l;定义一个该结构体类型的指针然后我们进行查找顺序表里的元素

编写查找函数

int search(seqlist *l,int a,int i)
{
	//a是你要查找的数字 
	//i是计数器,我在主函数里已经定义了用来记录查找到了哪个元素的位置了,记录的是下标值,所以i从0开始取 
	while(i<MAXSIZE)
	{
		if(l->elem[i]!=a)
		{
			i++;
		}
		if(l->elem[i]==a) 
		{
			return i;//如果与表中的元素相等我们返回下标值，在主函数里用于输出
		}
	} 
	//如果找不到与之对应的元素会不满足while的循环条件出while循环
	printf("找不到与之对应的元素\n");
	return -1; 
}
总体代码为
#include <stdio.h>
#define MAXSIZE 10
struct seqlist 
{
	int elem[MAXSIZE];//这里我们拿整型数组来作示范
	int last;//last用来记录表中最后一个元素的下标值，注意是下标值，所以我们初始化的时候last从-1开始取 
}n;
int search(seqlist *l,int a,int i)
{
	//a是你要查找的数字 
	//i是计数器,我在主函数里已经定义了用来记录查找到了哪个元素的位置了,记录的是下标值,所以i从0开始取 
	while(i<MAXSIZE)
	{
		if(l->elem[i]!=a)
		{
			i++;
		}
		if(l->elem[i]==a) 
		{
			return i;//如果与表中的元素相等我们返回下标值，在主函数里用于输出
		}
	} 
	//如果找不到与之对应的元素会不满足while的循环条件出while循环
	printf("找不到与之对应的元素\n");
	return -1; 
}
int main()
{
    seqlist *l;
    l=&n;
	int i=0;//计数器
	int a;//你要查找的数字 
	int data;
	for(int j=0;j<3;j++)
	{
		printf("输入第%d个初始数据:",j+1);
		scanf("%d",&data);
		l->elem[j]=data;
	}
	printf("输入你要查找的数字\n");
	scanf("%d",&a);
	int number=search(l,a,i);
	if(number==-1)
	{
		printf("找不到与之对应的元素\n");
	}
	if(number!=-1)
	{
		printf("找到了该元素该元素为第%d个元素\n",number+1);
		printf("该元素的值为%d\n",l->elem[number]);
	}
}

测试一下我们先输入1，2，3

 然后查找2这个元素值，发现运行正确

很简单的一个知识点， 最后给出顺序表的一些特点

存储结构：顺序存储结构

逻辑结构：线性结构

优点：在查找数据的时候，时间复杂度都是低的，所以可以快速地存取某一数据

缺点：插入和删除操作需要移动大量元素（这个可以说一说，如果有n个元素我要在第i个位置插入元素，注意这里说的不是下标，而是第几个位置，那么我要移动的次数为n-i+1次，如果删除第i个位置元素则要移动元素次数为n-i次