@[TOC]

顺序表前言

顺序表作为数据结构的入门知识，整体知识较为简单，主要对动态内存开辟 结构体 指针有要求，其余难度较低

顺序表要实现的功能

顺序表主要需要实现的有顺序表的增删查改和定向搜索销毁等，具体实现函数如下

// 对数据的管理:增删查改 
void SeqListInit(SeqList* ps);
void SeqListDestroy(SeqList* ps);

void SeqListPrint(SeqList* ps);
void SeqListPushBack(SeqList* ps, SLDateType x);
void SeqListPushFront(SeqList* ps, SLDateType x);
void SeqListPopFront(SeqList* ps);
void SeqListPopBack(SeqList* ps);

// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos);

定义顺序表

要实现顺序表，就需要对顺序表进行定义，在c语言中通常使用结构体进行写入，包括顺序表的容量，顺序表中存在元素的个数，顺序表的主体

在对顺序表的定义中存在两种，如果不使用动态内存开辟，可以直接定义一个数组实现顺序表，但由于数组容量是固定的，会把整个顺序表固定大小，于是在这里采用动态内存开辟的方法实现顺序表

首先对顺序表进行定义

typedef int SLDateType;
typedef struct SeqList
{
   
    SLDateType* a;
    int size;
    int capacity;
}SeqList;

接下来我们就对顺序表的各项功能进行依次实现

顺序表初始化

把顺序表的结构体定义完成后就可以创建一个顺序表了，创建好初始值后就要对顺序表进行一定的初始化内容

代码实现如下

void SeqListInit(SeqList* ps)
{
   
    assert(ps);
    ps->a = (SLDateType*)malloc(sizeof(SLDateType) * 4);
    if (ps->a == NULL)
    {
   
        perror("malloc fail");
        return;
    }
    ps->size = 0;
    ps->capacity = 4;
}

==关于assert函数==

assert的作用是断言，主要是用来进行条件判断，例如这里检测ps，意思就是检测ps是否为空指针，如果ps是空指针后续的操作就不必而行了，这样有利于检查错误信息，当运行到该语句结论为假时，会直接终止代码，算是暴力检查的一种方法

顺序表的销毁

创建完顺序表后就要对顺序表进行销毁，销毁的就是把它对应的空间释放，置空指针，返回初始值

代码实现如下

void SeqListDestroy(SeqList* ps)
{
   
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->size = 0;
    ps->capacity = 0;
}

==关于置空指针==

一般来说，把相关空间释放后为了避免出现野指针的情况要把指针置空，但不进行指针的置空在一些情况下也是可以的，一般释放空间后都会紧跟置空指针

打印顺序表

将顺序表里的信息打印到屏幕上，进行可视化观察有无错误信息

代码实现如下

void SeqListPrint(SeqList* ps)
{
   
    assert(ps);
    for (int i = 0; i < ps->size; i++)
    {
   
        printf("%d ", ps->a[i]);
    }
    printf("\n");
}

顺序表的尾插

将一个数据插入到顺序表中就涉及到了顺序表的尾插

思路也很简单，首先看原来顺序表的容量是否满足要求，如果不满足就进行一定的扩容，再把要插入的数据放到顺序表的尾部即可

==如何实现检查容量？==

如果顺序表的size和capacity是一致的，说明已经满了，到达上限了

因此函数实现如下

void SLCheckCapacity(SeqList* ps)
{
   
    assert(ps);
    SLDateType* tmp = NULL;
    if (ps->capacity == ps->size)
    {
   
        tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * ps->capacity * 2);
        if (tmp == NULL)
        {
   
            perror("realloc fail");
            return;
        }
        ps->a = tmp;
        ps->capacity *= 2;
        printf("扩容成功 当前容量%d\n", ps->capacity);
    }
}

但是由于后续还有再规定位置插入元素的情况，我们可以直接先写在x位置插入元素的情况

==因此函数实现就变成了实现在x位置插入元素==

函数实现如下

void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{
   
    assert(ps);
    assert(pos >= 0 && pos <= ps->size);
    SLCheckCapacity(ps);
    int end = ps->size - 1;
    while (pos <= end)
    {
   
        ps->a[end + 1] = ps->a[end];
        end--;
    }
    ps->a[pos] = x;
    ps->size ++ ;
}

有了在x位置插入元素函数的实现，对于在尾部插入函数只需要将x换成size即可

void SeqListPushBack(SeqList* ps, SLDateType x)
{
   
    assert(ps);
    SeqListInsert(ps,ps->size,x);
}

顺序表的头插

和顺序表的尾插相似，当我们有了在x位置插入元素的函数时，这些需求就很好写了

void SeqListPushFront(SeqList* ps, SLDateType x)
{
   
    assert(ps);
    SeqListInsert(ps, 0, x);
}

顺序表的头删

有了前面的想法，我们也把在x位置的元素进行删除封装成一个函数

==函数实现如下==

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

那么头删就是把标号为0的元素删除

==具体函数实现如下==

void SeqListPopFront(SeqList* ps)
{
   
    assert(ps);
    SeqListErase(ps, 0);
}

顺序表的尾删

有了头删的想法，尾删和头删基本一致

void SeqListPopBack(SeqList* ps)
{
   
    assert(ps);
    int end = ps->size - 1;
    SeqListErase(ps, end);
}

顺序表定向位置查找

最简单的功能，只需要遍历顺序表即可

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

整体来说顺序表是数据结构入门的部分，难度偏低