数据结构---顺序表

线性表

什么是线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的（地址不一定是连续的，但是可以通过之间存在的逻辑关系找到下一个数据）线性表在物理上存储时，通常以数组和链式结构的形式存储。

顺序表

什么是顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存 储。在数组上完成数据的增删查改。

静态顺序表

静态顺序表指的是使用定长数组存储元素的顺序表，由于在使用之前，顺序表的个数就已经确定，对于需要大量增删查改的项目来说很鸡肋，所以静态顺序表只作为顺序表一个小的知识点一带而过。

静态顺序表的初始化

//静态顺序表
typedef int SLDataType;
#define N 10
typedef struct Seqlist
{
	SLDataType array[N];//定长数组
	size_t size;//有效数据的个数
}SeqList;

动态顺序表

动态顺序表指的是使用动态开辟的数组存储，顺序表的有效数据个数根据所需要进行修改。

动态顺序表的初始化

//动态顺序表
typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* array;  //指向动态开辟的数组
	size_t size;  //数据中存储的数据
	size_t capacity;   //数组的容量
}SeqList；

1. 由于动态顺序表不像静态顺序表那样直接给出存储有效数据的个数，所以没有办法直接写出数组，这是就需要指针进行操作，因为指针就是数据的地址，所以要通过定义指针去找到动态开辟的空间，通过指针的加减去对应相应的数据的增删查改。
2. 动态开辟要有初始条件，只有满足才能扩容，所以加入数组的容量(capacity)，当有效数据个数与数组容量相等时，说明顺序表已满，需要扩容。

接口实现

使用数据结构的目的就是为了对数据进行增删查改，那么对于动态顺序表的增删查改，我们使用接口的方式去详细的描述这一过程。

顺序表的初始化

对于顺序表的初始化，主要就是针对顺序表的初始地址，有效数据个数以及最大容量进行设定，只有初始化成功才能开始正常的工作。

//顺序表初始化
void SeqListInit(SeqList* psl) //psl  p指针，sl顺序表
{
	assert(psl);
	psl->array = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
	if (psl->array == NULL)
	{
		perror("fail in malloc");
		return;
	}
	psl->size = 0;
	psl->capacity = INIT_CAPACITY;
}

1. 起始地址可以置为NULL；但是以上代码是使用malloc函数开辟一块空间，目的是为了使得顺序表的最大容量不为0；当然，如果起始地址是NULL；最大容量就要设置为0；这两种方法都可以。
2. INIT_CAPACITY是在头文件中定义的大小为4的数据；
3. 如果对malloc函数和realloc函数不是很清楚，可参考动态内存管理https://blog.csdn.net/Senyu_nuanshu/article/details/131934727

顺序表的扩容

动态顺序表要时刻检查最大容量是否和有效数据个数相等，如果相等就说明要进行扩容操作

//检查空间，如果满了，进行增容
void SeqListCheckCapacity(SeqList* psl)
{
	assert(psl);
	if (psl->size == psl->capacity)
	{
		SLDataType* newnode = (SLDataType*)realloc(psl->array, sizeof(SLDataType)* 2 * psl->capacity);
		if (newnode == NULL)
		{
			perror("fail in realloc");
			return;
		}
		psl->array = newnode;
		psl->capacity *= 2;
	}
}

1. realloc函数分为原地扩容或者异地扩容，这两种扩容方式是根据电脑不同时刻内存的情况选择的，处理扩容问题最正确的办法就是先设定一个新的地址去保存扩容出来的内存，再将新的地址赋值给原来的地址。
2. 我们要扩容到最大容量的2倍，很多同学会写成   sizeof(SLDataType)* 2   ，这个是4*2，8个字节的大小，但是最大容量是4*4字节，也就是16字节，2倍就是32个字节；所以这么写完就会报错，报错的原因就是扩容扩少了，导致新的元素没有地方存放，所以正确的写法是 sizeof(SLDataType)* 2 * psl->capacity
3. 扩容成功之后，除了地址要改变以外，顺序表的最大容量也要*2，这样才是正确的扩容。

顺序表的打印

打印是一个很好检查自己代码错误以及输出的方法，一定要先写打印，然后用其测试头插头删，尾插尾删。

//打印顺序表
void PrintSL(SeqList* psl)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->array[i]);
	}
	printf("\n ");
}

1. assert断言函数是为了防止顺序表为空而加入的，各位同学在写的时候一定要注意，仔细思考一下顺序表为空能不能打印，能不能进行增删查改，答案肯定是不能，顺序表都已经空了，你打印什么，增删查改谁？
2. 还有就是size-1才是array数组的最后一个下标

顺序表的尾插

从图中就可以明白，尾插其实就是赋值给array[size]，前提是要检查一下存储空间够不够用

同时尾插之后要注意，数组存储的有效数据个数已经增加了

//顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);
	SeqListCheckCapacity(psl);
	psl->array[psl->size] = x;//size是顺序表的最后一个位置
	psl->size++;
}

顺序表的尾删

对于顺序表的删除，一定要注意，要保证有效数据个数，也就是size>0；如果没有数据你删什么。

从图中可以看出来，顺序表的尾删是什么，就是把尾巴的数据直接扔掉就行了。

//顺序表尾删
void SeqListPopBack(SeqList* psl)
{
	assert(psl);
	assert(psl->size > 0);
	psl->size--;
}

 很多小伙伴会质疑，realloc函数开辟出来的空间，不用的时候应该使用free函数将空间的使用权还给操作系统啊，但是请注意，动态内存函数开辟出来的空间，只能一起还给操作系统，不能一个一个free，我们可以在最后使用free函数将所有开辟出来的空间全部还给操作系统。

顺序表的头插

//顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);
	SeqListCheckCapacity(psl);
	for (int i = psl->size; i > 0; i--)
	{
		psl->array[i] = psl->array[i - 1];
	}
	psl->array[0] = x;
	psl->size++;
}

顺序表的头删

//顺序表头删
void SeqListPopFront(SeqList* psl)
{
	assert(psl);
	assert(psl->size > 0);
	for (int i = 0; i < psl->size-1; i++)
	{
		psl->array[i] = psl->array[i + 1];
	}
	psl->size--;
}

 顺序表的查找

int SeqListFind(SeqList* psl, SLDataType x)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		if (psl->array[i] == x)
		{
			return i;
		}
	}
	return -1;
}

顺序表在pos位置插入x

pos指的是数组的下标，在寻找的时候注意头和尾，pos=size 相当于尾插，

//顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(pos>=0 && pos <= psl->size);
	SeqListCheckCapacity(psl);
	for (int i = psl->size; i > pos; i--)
	{
		psl->array[i] = psl->array[i - 1];
	}
	psl->array[pos] = x;
	psl->size++;
}

上述代码可以规避pos=0的情况，如果pos=0；i可以在0的位置停下来。相当于是头插； 如果是这样的代码会出现什么情况呢

 
void SeqListInsert(SeqList* psl, size_t pos, SLDateType x)
{
	assert(psl);
	assert(pos<=psl->size);
	for (int i = psl->size-1; i >= pos; i--)
	{
		psl->array[i + 1] = psl->array[i];
	}
  
}

当在下标为0的位置上插入一个数据时，i从psl->size-1到0，i进行i--操作，此时i=-1，再执行i>=pos操作，此时会停止循环吗？答案是不会，大家可以去调试，确实不会让循环停下。

那为什么呢？因为pos为 size_t 的类型，size_t 为无符号整形-，当int（有符号整形）和size_t（无符号整形）比较大小时，int型的数据会发生算数转换，转换成unsigned int型，此时为负数的 i 就变成了很大的数字，自然而然比0大，因此会进入死循环。

顺序表删除pos位置的值

删除pos位置的值其实就是另一种的头删，采用覆盖pos位置的值的方法

void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl);
	assert(pos >= 0 && pos < psl->size);
	for (int i = pos; i < psl->size - 1; i++)
	{
		psl->array[i] = psl->array[i + 1];
	}
	psl->size--;
}

顺序表的销毁

void SeqListDestory(SeqList* psl)
{
	assert(psl);
	free(psl->array);
	psl->array = NULL;
	psl->capacity = psl->size = 0;
}

总代码

头文件--seqlist.h

#pragma once
#include
#include
#include
#define INIT_CAPACITY 4
typedef int SLDataType;
typedef struct Seqlist
{
	SLDataType* array;
	size_t size;
	size_t capacity;
}SeqList;
 
//顺序表初始化
void SeqListInit(SeqList* psl);  //psl  p指针，sl顺序表
//检查空间，如果满了，进行增容
void SeqListCheckCapacity(SeqList* psl);
//顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
//顺序表尾删
void SeqListPopBack(SeqList* psl);
//顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
//顺序表头删
void SeqListPopFront(SeqList* psl);
//顺序表查找
int SeqListFind(SeqList* psl, SLDataType x);
//顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
//顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
//顺序表销毁
void SeqListDestory(SeqList* psl);
//打印顺序表
void PrintSL(SeqList* psl);

函数文件--seqlist.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"seqlist.h"
 
//打印顺序表
void PrintSL(SeqList* psl)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->array[i]);
	}
	printf("\n ");
}
 
//顺序表初始化
void SeqListInit(SeqList* psl) //psl  p指针，sl顺序表
{
	assert(psl);
	psl->array = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
	if (psl->array == NULL)
	{
		perror("fail in malloc");
		return;
	}
	psl->size = 0;
	psl->capacity = INIT_CAPACITY;
}
 
//检查空间，如果满了，进行增容
void SeqListCheckCapacity(SeqList* psl)
{
	assert(psl);
	if (psl->size == psl->capacity)
	{
		SLDataType* newnode = (SLDataType*)realloc(psl->array, sizeof(SLDataType)* 2 * psl->capacity);
		if (newnode == NULL)
		{
			perror("fail in realloc");
			return;
		}
		psl->array = newnode;
		psl->capacity *= 2;
	}
}
 
//顺序表销毁
void SeqListDestory(SeqList* psl)
{
	assert(psl);
	free(psl->array);
	psl->array = NULL;
	psl->capacity = psl->size = 0;
}
 
//顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);
	SeqListCheckCapacity(psl);
	psl->array[psl->size] = x;//size是顺序表的最后一个位置
	psl->size++;
}
 
//顺序表尾删
void SeqListPopBack(SeqList* psl)
{
	assert(psl);
	assert(psl->size > 0);
	psl->size--;
	//不能单独free，申请的空间要不然就一起释放掉，不能单独释放某一段空间
}
 
//顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);
	SeqListCheckCapacity(psl);
	for (int i = psl->size; i > 0; i--)
	{
		psl->array[i] = psl->array[i - 1];
	}
	psl->array[0] = x;
	psl->size++;
}
//顺序表头删
void SeqListPopFront(SeqList* psl)
{
	assert(psl);
	assert(psl->size > 0);
	for (int i = 0; i < psl->size-1; i++)
	{
		psl->array[i] = psl->array[i + 1];
	}
	psl->size--;
}
//顺序表查找
int SeqListFind(SeqList* psl, SLDataType x)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		if (psl->array[i] == x)
		{
			return i;
		}
	}
	return -1;
}
//顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(pos>=0 && pos <= psl->size);
	SeqListCheckCapacity(psl);
	for (int i = psl->size; i > pos; i--)
	{
		psl->array[i] = psl->array[i - 1];
	}
	psl->array[pos] = x;
	psl->size++;
}
//顺序表删除pos位置的值
 
void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl);
	assert(pos >= 0 && pos < psl->size);
	for (int i = pos; i < psl->size - 1; i++)
	{
		psl->array[i] = psl->array[i + 1];
	}
	psl->size--;
}

测试文件--test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"seqlist.h"
 
 
void Test()
{
	SeqList seq;
	SeqListInit(&seq);
	SeqListPushBack(&seq, 1);
	SeqListPushBack(&seq, 1);
	SeqListPushBack(&seq, 1);
	SeqListPushBack(&seq, 1);
	SeqListPushBack(&seq, 1);
	SeqListPushBack(&seq, 1);
	SeqListPushBack(&seq, 1);
	SeqListPushFront(&seq, 4);
	SeqListPopFront(&seq);
	SeqListInsert(&seq, 3, 6);
	SeqListInsert(&seq, 3, 6);
	SeqListInsert(&seq, 3, 6);
	SeqListInsert(&seq, 3, 6);
	SeqListInsert(&seq, 3, 6);
	SeqListInsert(&seq, 3, 6);
	SeqListErase(&seq, 3);
	PrintSL(&seq);
	SeqListDestory(&seq);
}
 
int main()
{
	Test();
	return 0;
}