【数据结构】_顺序表

【本节目标】

1. 线性表
2. 顺序表

1.线性表

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

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

2.顺序表

2.1概念及结构

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

顺序表一般可以分为：

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

顺序表的静态存储

//顺序表，有效数据在数组中必须是连续的
//静态顺序表设计（大小固定）
typedef int SLDataType;//重命名，为int类型定义了一个别名SLDataType
#define N 10
struct SeqList
{SLDataType a[N];//定长数组int size;//数组中存放的有效数据个数
};

顺序表的动态存储

//动态顺序表设计（大小可变）
typedef int SLDataType;//重命名，为int类型定义了一个别名SLDataTypestruct SeqList
{SLDataType* a;//给的是数组的指针int size;//有效数据的个数int capacity;//容量
};

2.2 接口实现

1.顺序表初始化

void SeqListInit(SL* ps)
{ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);//单个数据的大小*4个然后强转if (ps->a == NULL){printf("申请内存失败\n");exit(-1);//强行直接终止程序}ps->size = 0;//个数ps->capacity = 4;//容量为4，不是四个字节
}

SeqListInit 函数的主要作用是为顺序表分配初始的内存空间，并将顺序表的有效数据个数初始化为 0，容量初始化为 4。如果内存分配失败，程序会输出错误信息并终止执行。 这个函数是顺序表操作的基础，通常在创建顺序表对象后首先调用该函数进行初始化。

🖋️🖋️🖋️补充一个知识：

exit 是C标准库<stdlib.h>中定义的一个函数，其原型为 void exit(int status); 。该函数用于终止当前正在运行的程序，并将参数status的值返回给操作系统，以此表示程序的退出状态。一般而言：

• 状态码为 0 表示程序正常退出。
• 非零状态码通常表示程序出现异常或错误后退出。

exit(-1); 表示程序以异常状态退出，这里的-1就是传递给操作系统的退出状态码。不同的操作系统和应用场景可能会对退出状态码有不同的解读，不过通常非零状态码都意味着程序执行过程中出现了问题。

2.扩容检查与操作

if (ps->size >= ps->capacity)
{ps->capacity *= 2;ps->a = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity);if (ps->a == NULL){printf("扩容失败");exit(-1);}
}

• if (ps->size >= ps->capacity)：检查顺序表的当前元素数量ps->size是否达到或超过了其容量 ps->capacity。如果是，则需要进行扩容。
• ps->capacity *= 2;：将顺序表的容量扩大为原来的两倍。
• ps->a = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity);：使用 realloc 函数重新分配内存。realloc 会尝试在原内存块的基础上进行扩展，如果空间不足则会开辟新的内存块，并将原数据复制过去，最后返回新内存块的地址。
• if (ps->a == NULL)：检查realloc是否成功。如果 ps->a 为 NULL，表示内存分配失败，程序输出错误信息并终止。

3.尾插

void SeqListPushBack(SL* ps, SLDataType x)
{assert(ps);ps->a[ps->size] = x;ps->size++;
}

• ps->a[ps->size] = x;：将新元素x插入到顺序表的尾部，即ps->a[ps->size]位置。
• ps->size++;：将顺序表的元素数量加 1。

画图解析如下：

顺序表初始容量为 4，已存储 3 个元素，结构如下：

+---+---+---+---+
| 1 | 2 | 3 |   |
+---+---+---+---+↑ps->a
size = 3
capacity = 4

当调用SeqListPushBack(ps, 4)时，由于 size（3）小于 capacity（4），不需要扩容，直接插入新元素：

+---+---+---+---+
| 1 | 2 | 3 | 4 |
+---+---+---+---+↑ps->a
size = 4
capacity = 4

当调用 SeqListPushBack(ps, 5) 时，size（4）等于capacity（4），需要扩容：

+---+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 |   |   |   |
+---+---+---+---+---+---+---+---+↑ps->a
size = 5
capacity = 8

4.尾删

void SeqListPopBack(SL* ps)
{assert(ps);//ps->a[ps->size - 1] = 0;//此代码不重要ps->size--;
}

• ps->a[ps->size - 1] = 0;：这行代码被注释掉了，实际上它的作用是将顺序表尾部元素置为 0，但在顺序表的删除操作中，这一步并非必要，因为后续再访问这个位置时，由于 size 的限制，它已经不在有效元素范围内了。
  (在顺序表的删除操作中，我们的核心目的是让顺序表逻辑上不再包含最后一个元素。而在SeqListPopBack 函数里，ps->size–; 这行代码已经实现了这个目的。当 size 的值减 1 后，顺序表的有效元素范围就变成了从 0 到 size - 1（此时是原来的 size - 2），原来的最后一个元素（下标为 size - 1）就不在有效元素范围内了。)
• ps->size--;：核心操作，将顺序表的有效元素数量 size 减 1。通过减小 size，使得原来的最后一个元素不再被视为顺序表的有效元素，相当于从顺序表中删除了该元素。在内存层面，该元素的值并没有被真正清除，只是后续不会再通过顺序表的正常操作访问到它。

5.头插

void SeqListPushFront(SL* ps, SLDataType x)
{int end = ps->size - 1;//定义一个下标，指向这个有效个数的最后一个位置while (end >= 0){ps->a[end + 1] = ps->a[end];--end;//注意这里写成end--;没有任何影响，因为都会增加，只不过--end运算起来更快}ps->a[0] = x;ps->size++;//插入新元素后，顺序表的有效元素个数增加 1，所以将 ps->size 的值加 1。
}

使用 while 循环将顺序表中的所有元素依次向后移动一个位置。具体操作如下：

• 循环条件end >= 0确保从最后一个元素开始，一直移动到第一个元素。
• ps->a[end + 1] = ps->a[end]; 将当前 end 位置的元素复制到 end + 1 位置，实现元素的后移。
• --end; 将 end 减 1，指向前一个元素，继续进行后移操作

ps->a[0] = x;指的是：
经过元素移动后，顺序表的第一个位置（下标为 0）空了出来，将新元素x插入到这个位置

画图解析

总结： 经过以上四次循环，顺序表中的所有元素都依次向后移动了一个位置，此时顺序表的第一个位置（下标为 0）空了出来，可以将新元素插入到该位置。插入新元素后再将 size 加 1，就完成了在顺序表头部插入元素的操作。

6.头删

void SeqListPopFront(SL* ps)
{// 1. 断言指针ps不为空assert(ps);// 2. 初始化一个变量start，用于标记当前要移动元素的位置，从0开始int start = 0;// 3. 循环将后续元素依次向前移动一个位置while (start < ps->size - 1){// 将后一个元素赋值给当前位置ps->a[start] = ps->a[start + 1];// 移动到下一个位置++start;//注意这里写成start++;没有任何影响，因为都会增加，只不过++start运算起来更快}// 4. 顺序表的大小减1ps->size--;
}

核心逻辑

• 元素前移：从索引0开始，将每个元素的后一个值覆盖当前值（a[start] = a[start + 1]）。

• 循环条件：start < ps->size - 1，确保遍历到倒数第二个元素。

• 更新大小：ps->size--，标记顺序表有效元素减少一个。

注意：为什么这里的循环条件是start<size-1呢？

原因：当进行元素前移操作时，最后一次覆盖操作是把倒数第二个元素用最后一个元素的值覆盖。如果已经处理到倒数第二个元素（即 start 等于 ps->size - 2），把 ps->a[ps->size - 1] 的值赋给 ps->a[ps->size - 2] 之后，就完成了所有元素的前移工作。此时如果再往后处理，就会导致数组越界访问。

图示辅助理解

举个例子：

7.任意位置的插入

//任意位置的插入
void SeqListInsert(SL* ps, int pos, SLDataType x)//结构体指针；要插入的位置；要插入的数据
{assert(ps);assert(pos<=ps->size && pos>=0);//要插入的位置必须要有效小于size是因为下标//pos=0表示的就是头插//pos<=ps->size顺序表的末尾进行插入操作SeqListCheckCapacity(ps);//检查容量是否够了int end = ps->size - 1;//定义的end为下标while (end >= pos){ps->a[end + 1] = ps->a[end];--end;//注意这里写成end--;没有任何影响，因为都会增加，只不过--end运算起来更快}ps->a[pos] = x;ps->size++;
}

画图解释：

8.任意位置的删除

//任意位置的删除
void SeqListErase(SL* ps, int pos)//只用给一个要删除的位置int pos就行
{assert(ps);assert(pos < ps->size && pos >= 0);int start = pos;while (start < ps->size - 1){ps->a[start] = ps->a[start+1];++start;//注意这里写成start++;没有任何影响，因为都会增加，只不过++start运算起来更快}ps->size--;
}

画图解释：

9.顺序表查找

// 顺序表查找
int SeqListFind(SL* ps, SLDataType x)
{assert(ps);int i = 0;while (i < ps->size){if (ps->a[i] == x){return i;//找到了}i++;}return -1;//没找到返回一个无效下标，因为下标不可能为-1
}

🎈🎈🎈例如在test文件中要查找5的位置，并且把它删除，写法如下：

	int pos = SeqListFind(&s, 5);if (pos != -1){SeqListErase(&s, pos);//找到了，删除}SeqListPrint(&s);//打印
}

10.销毁程序

顺序表最后要进行销毁操作，主要有以下三个关键理由：

• 🎉避免内存泄漏：顺序表通常会动态分配内存来存储数据，当不再使用时，若不释放这部分内存，它就无法被系统回收再利用，随着程序运行，会造成可用内存不断减少，最终可能导致系统内存耗尽。销毁操作能释放动态分配的内存，将其归还给操作系统。
• 🎉防止野指针问题：释放内存后，指向该内存的指针会变成野指针，若后续代码不小心使用它进行访问，会引发未定义行为，如程序崩溃、数据损坏等。将指针置为NULL，能避免此类问题。
• 🎉保证程序健壮性和数据完整性：销毁操作会重置顺序表的状态，像将元素数量和容量置为 0，可避免后续代码错误使用已销毁的顺序表，保证程序逻辑正确，提升程序的健壮性。

代码实现：

void SeqListDestory(SL* ps)
{free(ps->a);//释放的是指针指向的空间，而不是指针ps->a = NULL;//要置空，因为指针没释放，要去访问的话就是野指针的越界问题了ps->size = ps->capacity = 0;
}

🎈到这里我们顺序表就结束啦~

🎈祝贺~🎉🎉🎉🎉

🎈我们下一章见噜( ﾟдﾟ)つBye~