感谢各位大佬对我的支持,如果我的文章对你有用,欢迎点击以下链接
🐒🐒🐒 个人主页
🥸🥸🥸 C语言
🐿️🐿️🐿️ C语言例题
🐣🐣🐣 python
🐓🐓🐓 数据结构C语言

下面是这篇文章会涉及到的知识,如果在阅读的过程中有疑惑的可以看一下
C语言函数介绍（详解）
C语言数组介绍（详解）
C语言深入理解指针（非常详细）（一）
动态内存管理(上)
动态内存管理(下)
自定义类型结构体(上)
自定义类型结构体(中)
自定义类型结构体(下)

线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列
常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线
但是在物理结构上并不一定是连续的
线性表在物理上存储时，通常以数组和链式结构的形式存储

顺序表

概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存
储
在数组上完成数据的增删查改
顺序表和数组的区别：
1：顺序表的存储必须是连续的，而数组是可以间隔的存储
2：顺序表在数组中存储时必须是从头开始依次存储，而数组可以在任意位置存储

顺序表一般可以分为：
静态顺序表：使用定长数组存储元素
缺点：N不知道给多少，可能会造成N太大或者太小

#define N 7
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType array[N];
	size_t size;
} SeqList;

动态顺序表：使用动态开辟的数组存储

typedef struct SeqList
{
	SLDataType* arry;
	size_t size;
	size_t capacity;
}SeqList;

接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用

所以现实中基本都是使用动态顺序表，根据需要动态的分配空间
大小，所以下面我们实现动态顺序表

首先我们先创建3个文件
1:SeqList.c是放一些功能函数具体实现的文件
2:SeqList.h是放一些功能函数函数名的文件
3:test.c是测试我们实现出的顺序表功能是否成功
之后就是实现函数了

初始化函数void SLInit(SL *psl);

SeqList.c文件
void SlInit(SL psl)
{
	psl.a = NULL;
	/*psl.size=....;
	psl.capacity=....;*/
}

这里有一个常见的错误，就是我们在test.c中用初始化函数时往往会这样传

test.c文件
void TestSL1()
{
	SL psl;
	SLInit(psl);
}

因为我们的目的是为了初始化，所以在传参的时候我们要将地址传入函数
如果不传的话就相当于我们将顺序表的成员都拷贝了一遍，然后对拷贝到成员进行初始化，当出了这个初始化函数的时候拷贝到成员就会销毁

简单的来说就是没传入地址就是形参，而形参是实参的拷贝，出了作用域就会自动销毁，只有传入地址才可以更改实参
(如果形参和实参不是很清楚的可以看一下我上面链接中的 C语言函数介绍（详解）)

所以正确的传入方式为

SeqList.c文件
void SlInit(SL *psl)
{
    assert(psl);//防止有人传空指针
	psl ->a = NULL;//结构体用箭头解引用
	psl->size=0;
	psl->capacity=0;
}

test.c文件
void TestSL1()
{
	SL s1;
	SLInit(&s1);
}

销毁函数 void SLDestroy(SL *psl);

SeqList.c文件
void SLDestroy(SL* psl)
{
    assert(psl);//防止有人传空指针
	if (psl->a!=NULL)
	{
		free(psl->a);//因为a是指针,所以要free a指向的空间
		psl->a = NULL;//然后让a=NULL，不能让a指向被销毁的空间
		psl->size = 0;
		psl->capacity = 0;
	}
}

尾插函数void SLPushBack(SL* psl ,SLDataType x);

尾插函数我们需要分情况讨论
1：尾插时有剩余的空间
2：尾插时没有剩余的空间

SeqList.c文件
void SLPushBack(SL* psl, SLDataType x)
{
    assert(psl);//防止有人传空指针
	if ((psl->size) >= (psl->capacity))
	{
		int newCapacity = psl->capacity * 2;
		SLDataType* a = realloc(psl->a, sizeof(SLDataType) * newCapacity);
		if (a == NULL)
		{
			perror("realloc fail");
			return;
		}
		psl->capacity = newCapacity;
	}
	psl->a[psl->size] = x;
	psl->size++;
}

这段代码的逻辑为判断有效长度是否大于总的长度，如果大于就意味着需要扩容

于是用newCapacity 等于2倍的capacity来扩大总长度（注意这里的2倍扩容并不一定非要2倍）

然后用realloc对空间扩容，因为realloc的函数特性（如果realloc不是很清楚可以看这篇文章最上面的链接内存函数部分），所以将realloc返回到地址给a

之后让capacity=newCapacity

然后对数组末尾进行插入，再将有效长度size加1

但是这段代码其实有几处的问题
1:在之前初始化函数中我们对于capacity的初始化为0,而这里的newCapacity是直接等于capacity*2，也就是newcapacity也为0

解决措施是在之前的初始化部分将capacity赋值为大于0的数
或者我们通过三目运算进行判断赋值

2：我们这段代码是将realloc返回的地址用a来接受，但是如果返回失败的话，a也就找不到之前的地址了

解决措施是我们用一个新的指针tmp来接受realloc返回到地址，然后判断是否扩容成功，成功的话就a=tmp

可能会有人认为a在之前初始化函数中a是空指针，而realloc(psl->a, sizeof(SLDataType) * newCapacity)中我们是对a进行扩容，但是a既然是空指针，我们就没有办法扩容，其实realloc是可以扩容的，因为当a是空指针的时候，realloc的功能就和malloc的功能一样了

封装函数void SLCheckCapacity(SL* psl)

因为对于后面的函数和尾插函数SLPushBack有一些代码是重合的，所以为了少写一些代码，我们将这些重合的写入这个封装函数SLCheckCapacity中
封装函数代码如下：

SeqList.c文件
void SLCheckCapacity(SL* psl)
{ 
    assert(psl);//防止有人传空指针
	if ((psl->size) >= (psl->capacity))
	{
		int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		SLDataType* tmp = realloc(psl->a, sizeof(SLDataType) * newCapacity);//sizeof(SLDataType)一定要乘,否则会出现越界
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		psl->a = tmp;
		psl->capacity = newCapacity;
}

头插函数void SLPushFront(SL* psl, SLDataType x);

对于头插函数我们并不能向前扩容,所以我们只能将数据向后移动

于是我们需要借助一个end指向顺序表最后的一块有效数据,end=size-1

然后通过a[end+1]=a[end],end–,使所有数据向后移动

最后再对a[0]进行头插

但是需要注意的是这里头插一次的时间复杂度为O[N],因此不能经常使用头插

SeqList.c文件
void SLPushFront(SL * psl, SLDataType x)
{    
    assert(psl);//防止有人传空指针
	SLCheckCapacity(psl);
	int end = psl->size - 1;
	while (end >= 0)
	{
		psl->a[end + 1] = psl->a[end];
		--end;
	}
	psl->a[0] = x;
	psl->size++;
}

尾删函数void SLPopBack(SL* psl);

SeqList.c文件
void SLPopBack(SL* psl)
{
    assert(psl);//防止有人传空指针
	psl->size--;
}

尾插函数只需要将记录有效数据的size减减就行了(也就是图中的红线),因为之后用顺序表时可能会用头插或者尾插,使图中的4被其他数字覆盖

但是这个函数也是有一点问题的,假如我们一直删除数据,当数据删除完了我们仍然不停止,就会出问题

当数据删除完后我们仍然继续删除,那么size就会为负数,而当我们再进行插入数据的时候,就会出现数据的丢失,原因就是size为负数,我们插入的数据不在我们想要的空间里

为了防止这种情况的出现,我们需要加一个断言

void SLPopBack(SL* psl)
{
    assert(psl);//防止有人传空指针 
    assert(psl->size>0);
	psl->size--;
}

但是我觉得这种尾删方法是有一点问题的,因为4的空间没有办法消除,所以a[size+1]仍然可以访问到4,这是不好的,但是也不知道该怎么去解决

头删函数void SLPopFront(SL* psl);

头删函数和之前的头插函数思路是一样的,把后面的数据往前移,将原来的数据覆盖掉就可以了

但是这里也有一个细节,如果是从后往前挪动数据的话,是无法实现头删的

比如上图中,我们将4往前挪动覆盖3,然后end–,但是下一次覆盖的话3就找不到了,只能用4把前面的2也给覆盖掉,这不是我们想要的结果

所有我们选择从前开始覆盖

通过a[end[=a[end+1]的方式挪动数据,然后end++,由于挪动后,end指向的新数据并没有被覆盖,所以就可以继续按照这种方式继续挪动

只不过我们还需要注意挪动结束的条件判断,如果end<size-1后我们就该停止挪动了,然后size–

为什么是end<size-1呢?

因为end是这个数组的下标,size-1就代表数组的最后一个有效数据的下标,如果是end<size的话就会访问到没有有效数据的空间

	void SLPopFront(SL* psl)
	{      
	        assert(psl);//防止有人传空指针
		    assert(psl->size > 0);
			int end = 0;
			while (end < psl->size-1)
			{
				psl->a[end] = psl->a[end + 1];
				end++;
			}
			psl->size--;
	}

任意下标插入函数void SLInsert(SL* psl, int pos, SLDataType x)

	void SLInsert(SL* psl, int pos, SLDataType x)
	{
		assert(psl&&(pos>=0)&&(pos<=psl->size));
		SLCheckCapacity(&psl);
		int end = psl->size - 1;
		while (end >= pos)
		{
			psl->a[end + 1] = psl->a[end];
			--end;
		}
		psl->a[pos] = x;
		psl->size++;
	}

注意这里的pos为下标,而assert断言是判断传入的是否为空指针

并且pos下标必须要大于0,而pos小于等于size中pos是可以等于size的,这样就相当于尾插函数

而为什么pos不能大于size呢?

其实是因为顺序表必须是连续的,如果大于size就不会连续了

任意下标删除函数void SLErase(SL* psl, int pos)

void SLErase(SL* psl, int pos)
{
	assert(psl && (pos >= 0) && (pos < psl->size));
		int end = pos;
		while (end < psl->size-1)
		{
			psl->a[end] = psl->a[end+1];
			end++;
		}
		psl->size--;
}

查找数据函数int SLFind(SL* psl, int pos, SLDataType x)

这个函数的功能是从pos位置的下标开始找数据,如果找到想要的数据就返回对应的下标

int SLFind(SL* psl, int pos, SLDataType x)
{
	assert(psl);
	for (int i = pos; i < psl->size; i++)
	{
		if (psl->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

这个函数可以和删除函数void SLErase(SL psl, int pos)一起使用*

有时候我们并不知道我们想要删除的数据在哪个位置

我们就可以用int SLFind(SL psl, int pos, SLDataType x)去查找,找到想要删除的数据,我们就通过删除函数去删除*

int pos = SLFind(&sl, 0, 1);
	if (pos != -1)
	{
		SLErase(&sl, pos);
	}

数组越界的情况分析

对于一个数组,我们可能会常常发生数组越界访问的错误,但是越界不一定会报错

在我们越界读取数据的时候并没有报错

而当我们越界写的时候就会报错