【数据结构】顺序表(SeqList)（增、删、查、改）详解

一、顺序表的概念和结构

1、顺序表的概念：

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

---

 2、顺序表的结构：

（1）静态顺序表：使用定长数组存储元素

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

// 顺序表的静态存储
#define N 10
typedef int SLDataType;

typedef struct SeqList
{
	SLDataType array[N];// 定长数组
	size_t size;// 有效数据个数
}SeqList;

---

 （2）动态顺序表：使用动态开辟的数组存储元素

优点：动态顺序表可以根据需要动态的分配空间大小。

// 顺序表的动态存储
typedef int SLDataType; //类型重命名，后续要存储其它类型时方便更改

typedef struct SeqList
{
	SLDataType* a;// 指向动态开辟的数组
	size_t size;// 有效数据个数（当前顺序表中已存放的数据个数）
	size_t capacity;// 容量大小（顺序表总共能够存放的数据个数）
}SeqList;

注：size_t 数据类型表示 C 中任何对象所能达到的最大长度，它是无符号整数。 

---

 二、动态顺序表的接口实现

1、创建文件

1. test.c（主函数、测试顺序表各个接口功能）
2. SeqList.c（动态顺序表接口函数的实现）
3. SeqList.h（动态顺序表的类型定义、接口函数声明、引用的头文件）

  

---

 2、SeqList.h 头文件代码

// SeqList.h
#pragma once // 防止头文件被二次引用

#include<stdio.h>
#include<assert.h> // assert
#include<stdlib.h> // realloc

typedef int SLDataType; // 后续要存储其它类型时方便直接更改

// 顺序表的动态存储
typedef struct SeqList
{
    SLDataType* a; // 指向动态开辟的数组
    size_t size ; // 有效数据个数
    size_t capicity ; // 容量空间的大小
}SeqList;

// 基本增删查改接口
// 顺序表初始化
void SeqListInit(SeqList* psl);
// 顺序表销毁
void SeqListDestory(SeqList* psl);
// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl);
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SeqList* psl);
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
// 顺序表头删
void SeqListPopFront(SeqList* psl);
// 顺序表打印
void SeqListPrint(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);
// 查看顺序表中的有效数据个数 
size_t SeqListSize(const SeqList* psl);
// 修改指定下标位置的数据
void SeqListAt(SeqList* psl, size_t pos, SLDataType x);

---

 三、在 SeqList.c 中实现各个接口函数

1、初始化顺序表

// 初始化顺序表
void SeqListInit(SeqList* psl)
{
	assert(psl); // 断言 -- 防止传进来的指针为空

	psl->a = NULL; // 初始化顺序表为空
    psl->size = 0; // 初始数据个数为0
	psl->capacity = 0; // 初始空间容量为0
}

---

2、顺序表销毁

// 销毁顺序表
void SeqListDestroy(SeqList* psl)
{
	assert(psl); // 断言 -- 防止传进来的指针为空

	free(psl->a); // 释放动态开辟的空间
    psl->a = NULL; // 置空
	psl->size = 0; // 数据个数置为0
	psl->capacity = 0; // 空间容量大小置为0
}

---

3、检查空间，如果满了，进行增容 

// 检查顺序表容量是否满了，好进行增容
void CheckCapity(SeqList* psl)
{
	if (psl->size == psl->capacity) // 检查容量，满了则增容
	{
        // 原来容量为0，扩容为4；不为0，扩容为原来的2倍
		size_t newcapacity = psl->capacity == 0 ? 4 : 2 * (psl->capacity);
		psl->a = (SeqList*)realloc(psl->a, sizeof(SLDateType) * newcapacity); // 扩容
		psl->capacity = newcapacity; // 更新容量
	}
}

为什么不采取插一个数据，增容一个空间的方式呢？

因为这样做很麻烦，代价也很大。一般情况下，为了避免频繁的增容，当空间满了之后，我们不会选择一个一个的去增，而是一次增容 2 倍，当然也不会一次增容太大，比如 3 倍 4 倍，这样空间可能会造成浪费，所以 2 倍是一个折中的选择。

---

 注：realloc 在开辟动态内存空间时，如果传给它的是一个空指针，那么他就会开辟一个新的内存空间，用法类似malloc。

---

4、顺序表尾插

// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDateType x) // O(1)
{
	// 不需要断言 空指针也符合条件

    // 第一种写法：
    /* CheckCapacity(psl); // 检查顺序表容量是否已满
	psl->a[psl->size] = x; // 尾插数据
	psl->size++; // 有效数据个数+1 */

    // 第二种写法：
	SeqListInsert(psl, psl->size, x);
}

---

5、顺序表尾删

// 顺序表尾删
void SeqListPopBack(SeqList* psl) // O(1)
{
	assert(psl); // 断言

    // 第一种写法：
    /* assert(psl->size > 0); // 尾删 -- 顺序表不能为空
	//psl->a[psl->size - 1] = 0; // 不知道SLDataType是什么类型的数据，不能冒然的直接赋值为0
	psl->size--; // 有效数据个数-1 */

    // 第二种写法：
	SeqListErase(psl, psl->size - 1);
}

关于在程序中检查错误的方式：

（1）温柔检查法： 如果出现错误，程序就不再继续执行。因为一般情况下，程序运行成功就返回0，则运行失败就返回-1。
（2）暴力检查法（推荐）：如果发生错误，程序会报警告，可以直接知道出错位置。

// 温柔处理方式
    if (psl->size > 0)
    {
        psl->a[ps->size - 1] = 0;
        psl->size--;
    }

// 暴力处理方式
    assert(psl->size > 0);
    psl->size--;

---

注：不知道 SLDataType 是什么类型的数据，不能冒然的将顺序表最后一个数据赋值为 0，我们只需将有效数据个数 size 减 1 即可达到尾删的目的。 

---

6、顺序表头插

// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDateType x) // O(n)
{
    // 头插不需要断言 空指针也符合条件

    /* CheckCapacity(psl); // 检查顺序表容量是否已满
	for (int i = psl->size - 1; i >= 0; i--) // 顺序表中[0,size-1]的元素依次向后挪动一位
	{
		psl->a[i + 1] = psl->a[i];
	}
	psl->a[0] = x; // 头插数据
	psl->size++; // 有效数据个数+1 */

	SeqListInsert(psl, 0, x);
}

---

7、顺序表头删

// 顺序表头删
void SeqListPopFront(SeqList* psl) // O(n)
{
	assert(psl); // 断言

    // 方法一：
    /* assert(psl->size > 0);  //顺序表不能为空
	for (int i = 1; i < psl->size; i++) // 顺序表中[1,size-1]的元素依次向前挪动一位
	{
		psl->a[i - 1] = psl->a[i];
	}
	psl->size--; // 有效数据个数-1 */

    // 方法二：
	SeqListErase(psl, 0);
}

---

8、顺序表打印

// 打印顺序表
void SeqListPrint(SeqList* ps)
{
	assert(ps); // 断言

    if (psl->size == 0) // 顺序表为空
	{
		printf("顺序表为空\n");
		return;
	}

    // 顺序表不为空
	for (size_t i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

---

 9、顺序表查找指定值

// 顺序表查找
int SeqListFind(SeqList* psl, SLDateType x)
{
	assert(psl); // 断言
	for (int i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
		{
			return i; //查找到，返回该值在数组中的下标
		}
	}
	return -1; // 没查找到
}

---

 10、顺序表在pos位置插入x

// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDateType x)
{
	assert(psl); // 断言
	assert(pos >= 0 && pos <= (psl->size)); // 检查pos下标的合法性
	CheckCapity(psl);

    // 第一种写法：
	/* size_t end = psl->size;
	while (end > pos)
	{
		psl->a[end] = psl->a[end - 1];
		end--;
	} */

    //第二种写法：
    size_t i = 0;
	for (i = psl->size; i > pos; i--)  // 将pos位置后面的数据依次向后挪动一位
	{
		psl->a[i] = psl->a[i - 1];
	}

	psl->a[pos] = x; // 插入数据
	psl->size++; // 有效数据个数+1
}

---

注：原先下面这种写法，当顺序表为空 size = 0 时，会导致 i = -1，执行 i >= pos 时，i 被算术转换成无符号数，而无符号数的 -1 是一个值很大的正数，远远大于 pos，满足条件进入循环，会造成越界访问。 

int i = 0;
for (i = psl->size - 1; i >= pos; i--)
	psl->a[i + 1] = psl->a[i];

注：转换并不会改变 i 本身的值，而是在执行 i >= pos 时，生成一个临时值与 pos 进行比较。如果在顺序表头部（pos = 0）插入数据，i 最终也会减成 -1，被算术转换后变成一个很大的数。

---

总结：避免负数给到无符号数，或者避免有符号数变成负数后，被算术转换或整型提升后，变成一个很大的数。按照第二种写法就可以避免 i 变成负数（-1）了。

---

 实现了此接口，顺序表头插和尾插相当于在下标为 0 和 psl -> size-1 位置处插入数据。

---

---

11、顺序表删除pos位置的值

// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl); // 断言
    assert(psl->size > 0); // 顺序表不能为空
	assert(pos >= 0 && pos < psl->size); // 检查pos下标的合法性

    // 第一种写法：
	/* size_t start = pos;
	while (start < psl->size-1)
	{
		psl->a[start] = psl->a[start + 1];
		start++;
	} */

    //第二种写法：
    size_t i = 0;
	for (i = pos + 1; i < psl->size; i++)  // 将pos位置后面的数据依次向前挪动一位
	{
		psl->a[i - 1] = psl->a[i];
	}

	psl->size--; // 有效数据个数-1
}

实现了此接口，顺序表头删和尾删相当于删除下标为 0 和 psl -> size-1 位置处的数据。

---

---

12、查看顺序表中的有效数据个数 

// 查看顺序表中的有效数据个数
size_t SeqListSize(const SeqList* psl)
{
	assert(psl); // 断言
	return psl->size;
}

为什么不选择在主函数里面直接通过定义的结构体变量直接访问，还要弄一个相关函数呢？

在数据结构中，如果要访问或者修改数据结构中的数据，不要直接访问，而是应该去调用它的函数来访问和修改，这样会更加规范和安全，也更方便检查出是否出现了越界等错误情况。

---

数组越界是不一定报错的，系统对越界的检查是设岗检查。

• 越界读（读了不属于自己的数据），一般是检查不出来的，往往并不会造成内存奔溃。

• 越界写（缓冲区溢出）如果是修改到标志位才会被检查出来，会造成数据破坏，严重会造成内存奔溃。

（系统在数组末尾后设的有标志位，越界写时，恰好修改到标志位了，就会被检查出来）

---

13、修改指定下标位置的数据

// 修改指定下标位置的数据
void SeqListAt(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl); // 断言
    assert(psl->size > 0); // 顺序表不能为空
	assert(pos >= 0 && pos < psl->size); // 检查pos下标的合法性
	psl->a[pos] = x; // 修改pos下标处对应的数据
}

---

 四、代码整合

// SeqList.c
#include "SeqList.h"

// 初始化顺序表
void SeqListInit(SeqList* psl)
{
	assert(psl); // 断言 -- 防止传进来的指针为空

	psl->a = NULL; // 初始化顺序表为空
    psl->size = 0; // 初始数据个数为0
	psl->capacity = 0; // 初始空间容量为0
}

// 销毁顺序表
void SeqListDestroy(SeqList* psl)
{
	assert(psl); // 断言 -- 防止传进来的指针为空

	free(psl->a); // 释放动态开辟的空间
    psl->a = NULL; // 置空
	psl->size = 0; // 数据个数置为0
	psl->capacity = 0; // 空间容量大小置为0
}

// 检查顺序表容量是否满了，好进行增容
void CheckCapity(SeqList* psl)
{
	if (psl->size == psl->capacity) // 检查容量，满了则增容
	{
        // 原来容量为0，扩容为4；不为0，扩容为原来的2倍
		size_t newcapacity = psl->capacity == 0 ? 4 : 2 * (psl->capacity);
		psl->a = (SeqList*)realloc(psl->a, sizeof(SLDateType) * newcapacity); // 扩容
		psl->capacity = newcapacity; // 更新容量
	}
}

// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDateType x) // O(1)
{
	SeqListInsert(psl, psl->size, x);
}

// 顺序表尾删
void SeqListPopBack(SeqList* psl) // O(1)
{
	assert(psl); // 断言
	SeqListErase(psl, psl->size - 1);
}

// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDateType x) // O(n)
{
	SeqListInsert(psl, 0, x);
}

// 顺序表头删
void SeqListPopFront(SeqList* psl) // O(n)
{
	assert(psl); // 断言
	SeqListErase(psl, 0);
}

// 打印顺序表
void SeqListPrint(SeqList* ps)
{
	assert(ps); // 断言

    if (psl->size == 0) // 顺序表为空
	{
		printf("顺序表为空\n");
		return;
	}

    // 顺序表不为空
	for (size_t i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

// 顺序表查找
int SeqListFind(SeqList* psl, SLDateType x)
{
	assert(psl); // 断言
	for (int i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
		{
			return i; //查找到，返回该值在数组中的下标
		}
	}
	return -1; // 没查找到
}

// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDateType x)
{
	assert(psl); // 断言
	assert(pos >= 0 && pos <= (psl->size)); // 检查pos下标的合法性
	CheckCapity(psl);

    size_t i = 0;
	for (i = psl->size; i > pos; i--)  // 将pos位置后面的数据依次向后挪动一位
	{
		psl->a[i] = psl->a[i - 1];
	}
	psl->a[pos] = x; // 插入数据
	psl->size++; // 有效数据个数+1
}

// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl); // 断言
    assert(psl->size > 0); // 顺序表不能为空
	assert(pos >= 0 && pos < psl->size); // 检查pos下标的合法性

    size_t i = 0;
	for (i = pos + 1; i < psl->size; i++)  // 将pos位置后面的数据依次向前挪动一位
	{
		psl->a[i - 1] = psl->a[i];
	}
	psl->size--; // 有效数据个数-1
}

// 查看顺序表中的有效数据个数
size_t SeqListSize(const SeqList* psl)
{
	assert(psl); // 断言
	return psl->size;
}

// 修改指定下标位置的数据
void SeqListAt(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl); // 断言
    assert(psl->size > 0); // 顺序表不能为空
	assert(pos >= 0 && pos < psl->size); // 检查pos下标的合法性
	psl->a[pos] = x; // 修改pos下标处对应的数据
}