数据结构——顺序表的实现

一、顺序表的基本概念

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

顺序表一般分为静态顺序表和动态顺序表，本文章主要说明动态顺序表的实现。

二、顺序表的的定义和初始化

1.顺序表的定义

typedef int SLDataType;typedef struct SeqList{    SLDataType* a;    int size;//有效数据    int capacity;//capacity表示空间的容量}SL;

注：typedef int SLDataType; 这个语句中，将int类型重命名为SLDataType。通过这个typedef声明，可以在代码中使用SLDataType来代替int类型。在后续的代码中，将直接使用SLDataType来声明变量，而不必再使用int类型。

这里命名了一个名为SeqList的顺序表，其中size表示此顺序表内的数据个数，capacity表示此顺序表所能容纳的数据个数。

2.顺序表的初始化

void SLInit(SL* psl){    psl->a = NULL;    psl->size = 0;    psl->capacity = 0;}

三、顺序表的接口实现 

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

顺序表的接口如下：

// 顺序表初始化void SeqListInit(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);// 顺序表查找int SeqListFind(SeqList* psl, SLDataType x);// 顺序表在pos位置插入xvoid SeqListInsert(SeqList* psl, size_t pos, SLDataType x);// 顺序表删除pos位置的值void SeqListErase(SeqList* psl, size_t pos);// 顺序表销毁void SeqListDestory(SeqList* psl);// 顺序表打印void SeqListPrint(SeqList* psl);

1.顺序表扩容

void SLCheckCapacity(SL* psl){    if (psl->size == psl->capacity)    {    int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;    SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * newCapacity);    if (tmp == NULL)    {    perror("realloc fail");    return;    }    psl->a = tmp;    psl->capacity = newCapacity;    }}

在顺序表当中，我们会插入元素，如果psl->size == psl->capacity（即顺序表中的元素个数与此顺序表所能容纳的数据个数相等），表示此顺序表已经满了，则需要使用realloc函数扩容。

2.顺序表尾插

void SLPushBack(SL* psl, SLDataType x){    SLCheckCapacity(psl); //检查顺序表空间容量    psl->a[psl->size] = x;    psl->size++;}

3.顺序表头插 

顺序表的要求是数据存储的时候必须是连续的，而且必须从头开始存储。所以顺序表在进行头插时，就需要从最后一个数据起，依次往后挪动。

问：如何确定顺序表中的最后一个元素？

创建一个end变量来指向要挪动的数据，由于end指向的是数据的下标，所以end=size-1。进入while循环，将顺序表中的所有元素依次向后移动一个位置，为新元素腾出插入位置。循环体结束后，就可以在下标为0的位置上插入新的元素。此时顺序表内元素加了一个，要记得size++。

void SLPushFront(SL* psl, SLDataType x){    SLCheckCapacity(psl);    // 挪动数据    int end = psl->size - 1;    while (end >= 0)    {    psl->a[end + 1] = psl->a[end];    --end;       }    psl->a[0] = x;    psl->size++;}

4.顺序表尾删

尾删即删除顺序表中的最后一个元素，只需要将元素的数量减去一个就可以了，即size--， 这样最后一个元素就是无效数据，无法访问了，那么就相当于删除了最后一个元素。

void SLPopBack(SL* psl){    assert(psl->size > 0);psl->size--;}

当顺序表中一个元素都没有时，size就会减到-1这个位置上，从而出现越界，但由于size是用来表示顺序表中的元素个数的，不可能小于0，所以这里需要断言。

越界通常指的是访问数组、链表等数据结构时，访问了超出其有效范围的位置。这种操作可能会导致程序运行出错或产生意料之外的结果。

在数组中，越界通常指的是访问数组索引小于0或大于等于数组长度的位置。例如，对于一个长度为n的数组，如果访问了数组索引为n或大于n的位置，就会发生越界。

越界访问可能会导致程序崩溃、内存错误、数据损坏等问题，所以在编程时应该格外注意边界条件的处理，避免越界访问的发生。

5.顺序表头删

头删只需要依次向前挪动数据即可。

void SLPopFront(SL* psl){assert(psl->size > 0);int begin = 1;while (begin size){psl->a[begin - 1] = psl->a[begin];++begin;}psl->size--;}

6.顺序表查找

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

7.任意位置插入

pos是元素的下标，所以要限定pos的范围pos >= 0 && pos size，以保证pos的值合法。

创建变量end指向顺序表中最后一个元素的下标，并通过ned指向需要挪动的数据。因为需要把pos下标之后的数据往后挪动（包括pos下标的元素),所以while循环中以end>=pos作为判断条件，数据挪动之后，便可以把插入数据x在pos这个位置上。最后size++。

// 注意pos是下标// size是数据个数，看做下标的话，他是最后一个数据的下一个位置void SLInsert(SL* psl, int pos, SLDataType x){assert(psl);assert(pos >= 0 && pos 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++;}

8.删除任意位置的元素

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

9.顺序表销毁

顺序表需要销毁的主要原因有以下几点：

1. 节约内存空间：当顺序表不再需要使用时，及时销毁顺序表可以释放占用的内存空间，避免内存泄漏问题，提高内存利用率。

2. 避免资源浪费：顺序表在不使用的情况下占用计算机资源，包括内存和其他系统资源，及时销毁可以避免资源的浪费。

3. 防止数据泄露：如果顺序表中存储了敏感或重要数据，在不再需要使用这些数据时，销毁顺序表可以有效防止数据泄露的风险。

4. 提高程序性能：当顺序表不再需要使用时，销毁顺序表可以减少系统资源的占用，提高程序的性能和响应速度。

所以呢，及时销毁顺序表是一种良好的编程习惯，能够有效管理内存和资源，保护数据安全，提高程序性能。

void SLDestroy(SL* psl){if (psl->a != NULL){free(psl->a);psl->a = NULL;psl->size = 0;psl->capacity = 0;}}

10.顺序表打印

实现函数后，我们想要打印出顺序表的元素，就需要一个打印函数，在实现其他功能时，我们需要进行简单测试，就可以调用此函数。

void SLPrint(SL* psl){for (int i = 0; i size; i++){printf("%d ", psl->a[i]);}printf("\n");}

四、代码总览

1.SeqList.h

#include#include#includetypedef int SLDataType;typedef struct SeqList{SLDataType* a;int size;//有效数据int capacity;//空间容量}SL;void SLInit(SL* ps1);//初始化顺序表void SLDestroy(SL* ps1);//销毁void SLPrint(SL* ps1);//打印void SLCheckCapacity(SL* ps1);//扩容// 头尾插入删除void SLPushBack(SL* ps1, SLDataType x);void SLPushFront(SL* ps1, SLDataType x);void SLPopBack(SL* ps1);void SLPopFront(SL* ps1);//在任意下标位置的插入删除void SLInsert(SL* psl, int pos, SLDataType x);void SLErase(SL* psl, int pos);//查找int SLFind(SL* psl, SLDataType x);

2.SeqList.c 

#include"SeqList.h"//初始化void SLInit(SL* psl){assert(psl);psl->a = NULL;psl->size = 0;psl->capacity = 0;}//销毁void SLDestroy(SL* psl){assert(psl);if (psl->a != NULL){free(psl->a);psl->a = NULL;psl->size = 0;psl->capacity = 0;}}//打印void SLPrint(SL* psl){assert(psl);for (int i = 0; i size; i++){printf("%d ", psl->a[i]);}printf("\n");}//扩容void SLCheckCapacity(SL* psl){assert(psl);if (psl->size == psl->capacity){int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * newCapacity);if (tmp == NULL){perror("realloc fail");return;}psl->a = tmp;psl->capacity = newCapacity;}}//尾插void SLPushBack(SL* psl, SLDataType x){assert(psl);SLCheckCapacity(psl);psl->a[psl->size] = x;psl->size++;}//头插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){assert(psl->size > 0);psl->size--;}//头删void SLPopFront(SL* psl){assert(psl->size > 0);int begin = 1;while (begin size){psl->a[begin - 1] = psl->a[begin];++begin;}psl->size--;}int SLFind(SL* psl, SLDataType x){assert(psl);for (int i = 0; i size; i++){if (psl->a[i] == x){return i;}return -1;}}// 注意pos是下标// size是数据个数，看做下标的话，他是最后一个数据的下一个位置void SLInsert(SL* psl, int pos, SLDataType x){assert(psl);assert(pos >= 0 && pos 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++;}void SLErase(SL* psl, int pos){assert(psl);assert(pos >= 0 && pos size);int begin = pos + 1;while (begin size){psl->a[begin - 1] = psl->a[begin];++begin;}psl->size--;}