5分钟带你了解什么是顺序表，并用它写一个简单的增删查改(画图讲

顺序表的概念及结构

顺序表在数据结构中一种很重要的逻辑结构 ,它是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。也就是说，顺序表本质是一个数组，它的存储的数据从左向右必须是连续的。
顺序表的结构：

下面这种结构不是顺序表，因为数据不是连续的,5和6中间空了一块空间。

顺序表可以分为：

1. 静态顺序表：使用定长数组存储。
2. 动态顺序表：使用动态开辟的数组存储。

顺序表的静态的存储：

#define N 100
typedef int SLDataType;
typedef struct SeqList
{
 SLDataType array[N]; // 定长数组，数组的大小是固定的，所以是静态储存
  size_t size; // 有效数据的个数 
}SeqList;

动态顺序表的存储：

，

顺序表的缺点

1.在头部或中间插入数据需要挪动数据

2.动态增容有增容时有性能的消耗
3增容时一般是以2倍或1.5倍增长的,势必会有一定的空间的浪费,例如,当前最大容量为100,满了以后,增容到200,我在插入5个数据,后面就有95个空间浪费掉了.

增删查改(动态)

增删查改的意义

在写代码之前,我们先来聊一下写这个增删查改的意义.增删查改的结构随处可见,无论是我们的微信的通讯录里,还是在学校的教务系统里,都需要有一个增删查改去去添加联系人(学生)的信息,查找联系人(学生)的信息,所以学习增删查改的基本结构的对我们的意义很大,当我们学会了增删查改的基本逻辑以后,我们才能去延伸去写通讯录,去写教务系统.或者看懂代码.

动态顺序表

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

初始化数据

先定义一个结构体

typedef struct SeqList
{
	int* s;
	int capacity;//该数组的最大容量
	int sz;//该数组当前存储数据的个数
}SeqList;

void SeqListInit(SeqList* pc)
{
	pc->s = NULL;
	pc->capacity = 0;
	pc->sz = 0;
}

尾部增加一个数据

如果想在4后面插入一个5,此时的sz为4,只要再pc->s[pc->sz]插入一个5即可,因为5的位置为数组下标为4
的位置.

当然,我们在插入数据之前,得检查是否需要增容.
所以我们在定义一个增容的函数

void CheckCapacity(SeqList* pc)
{
	assert(pc);
	if (pc->capacity == pc->sz)//若sz等于最大容量,则需要增容
	{
		pc->capacity = pc->capacity == 0 ? 5 : pc->capacity * 2;
		pc->s = (int *)realloc(pc->s, sizeof(int) * pc->capacity);
		if (pc->s == NULL)
		{
			return;
		}
		printf("增容成功\n");
	}

 }

void SeqListPushBack(SeqList* pc,int x)
{
	assert(pc);//防止pc为NULL
	CheckCapacity(pc);//检查是否需要增容
	pc->s[pc->sz] = x;
	pc->sz++;
}

头部插入一个数据

我们如何把一个数据插入在顺序表的首位置呢?
这就需要我们把数据全部往后移,然后空出首位置的,在把值插入到首位置

代码如下:

void SeqListPushFront(SeqList* pc, int x)
{
	assert(pc);//防止pc为NULL
	CheckCapacity(pc);//检查是否需要增容
	int i = pc->sz;
	while (i--)
	{
		pc->s[i + 1] = pc->s[i];
	}
	pc->s[0] = x;
	pc->sz++;

}

尾部删除一个数据

尾删其实很简单,只需要把有效数据减少一个就行,也就是把sz就可以,

参考如下代码;

void SeqListPopFront(SeqList* pc)
{
	assert(pc);
	pc->s[pc->sz - 1] = 0;
	pc->sz--;

}

头部删除一个元素

void SeqListPopFront(SeqList* pc)
{
	assert(pc);
	if (pc->sz == 0)//当sz=0,也就是说没有有效数据,后面不用删除数据
	{
		return;
	}
	for (int i = 0; i < pc->sz - 1; i++)
	{
		pc->s[i] = pc->s[i + 1];
	}
	pc->sz--;
}

查找函数

查找函数是查找想要的数在顺序表中第一个位置,该代码如下

int SeqListFind(SeqList* pc, int x)
{
	assert(pc);
	for (int i = 0; i < pc->sz; i++)//先阅历一遍数组
	{
		if (pc->s[i] == x)
		{
			return i ;//找到了该数,则返回该数在线性表的下标
		}
	}
	return 0;//如果找不到,则返回0
}

在指定的位置中插入一个数据

代码如下

void SeqListInster(SeqList* pc, int pos, int x)
{
	assert(pc);
	assert(pos >= 0 && pos < pc->sz);//检查该位置是否为合理
	CheckCapacity(pc);//检查容量是否满了
	int i = pc->sz-1;
	while (i>=pos)
	{
		pc->s[i + 1] = pc->s[i];
		i--;
	}
	pc->s[pos] = x;
	pc->sz++;
}

删除指定位置的数据

void SeqListErase(SeqList* pc, int pos)
{
	assert(pc);
	assert(pos >= 0 && pos < pc->sz);//检查pos是否为有效位置
	if (pc->sz == 0)
	{
		return 0;
	}
	int i = pos;
	for (i = pos; i < pc->sz - 1; i++)
	{
		pc->s[i] = pc->s[i + 1];
	}
	pc->sz--;//有效数据减1
}

好了,文章就写到这里了,如果有什么不懂的地方,可以私信我一下,我尽量帮助你去搞懂,若文章有什么错误,可以在评论区里帮我指正,如果文章对你有帮助的话,希望你能够帮我点个赞鼓励一下笔者,谢谢!