[简单易懂]数据结构顺序表——C语言

前言💖：

​ 顺序表是线性表的一种，而线性表是n个具有相同特性的数据元素（换种说法，顺序表其实就是数组）的有限序列。线性表是在实际中广泛使用的数据结构，常见的线性表：顺序表，链表，栈，队列，字符串…
​ 线性表在逻辑上是线性结构，也就是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上储存时，通常以数组和链式结构的形式存储。

为什么要学习顺序表？

1.连续的物理空间，方便下标随机访问（查找访问）
2.支持排序，二分查找

车站🚗：

注释👀：

制作顺序表需要的功能有：增删查改

我们创建两个.c文件，一个.h文件分别实现菜单(test.c)，具体代码(SeqList.c)，函数声明和头文件(SeqList.h)

实现功能的代码注释：

voidSeqListPrint(SeqList* psl);//打印voidSeqListInit(SeqList* psl);//初始化voidSeqListDestroy(SeqList* psl);//清空voidSeqListCheckCapacity(SeqList* psl);//扩容voidSeqListPushBack(SeqList* psl, SLDataType x);//尾加voidSeqListPopBack(SeqList* psl);//尾删voidSeqListPushFront(SeqList* psl, SLDataType x);//头插voidSeqListPopFront(SeqList* psl);//头删voidSeqListInsert(SeqList* psl, size_t pos, SLDataType x);//在pos位置插入voidSeqListErase(SeqList* psl, size_t pos);//删除pos位置的数据intSeqListFind(SeqList* psl, SLDataType x);//查找voidSeqListModify(SeqList* psl, size_t pos, SLDataType x);//修改

过程🙌：

1.顺序表结构体的定义：

//重定义int和链表名字，增加可读性和维护性typedefint SLDataType;typedefstruct SeqList {
    SLDataType* a;int size;//存储数据的个数int capacity;//存数据的大小(扩容大小)}SeqList;

2.定义完成后，在菜单文件进行结构体命名，再实现初始化和打印函数

//test.c
SeqList s;SeqListInit(&s);//传入结构体s的地址//SeqList.hvoidSeqListInit(SeqList* psl);//用*psl接收svoidSeqListPrint(SeqList* psl);//SeqList.cvoidSeqListInit(SeqList* psl){assert(psl);//断言psl不为空
    psl->a =NULL;
    psl->size =0;
    psl->capacity =0;}voidSeqListPrint(SeqList* psl){assert(psl);for(int i =0; i < psl->size;++i){printf("%d ", psl->a[i]);}printf("\n");}

3.在初始化完成后，我们需要思考一个问题，就是在进行增删查改时，a数组的空间该如何分配，如果用宏定义a的空间，那并不好控制空间的动态大小，所以我们实现一个动态内存分配的函数，当我们需要扩容时只需要调用函数即可

//SeqList.hvoidSeqListCheckCapacity(SeqList* psl);//扩容//SeqList.cvoidSeqListCheckCapacity(SeqList* psl){assert(psl);if(psl->size == psl->capacity)//当已有大小等于扩容大小时{
        size_t newCapacity = psl->capacity ==0?4: psl->capacity *2;//从4开始扩容，之后每扩一次都是两倍扩
        SLDataType* tmp =realloc(psl->a,sizeof(SLDataType)* newCapacity);//用*tmp接收扩容后的值if(tmp ==NULL)//当已经无法扩容时退出程序{printf("realloc fail\n");exit(-1);}else{
            psl->a = tmp;
            psl->capacity = newCapacity;}}}

4.完成了扩容函数，现在就可以开始实现插入删除了，我们先完成尾插尾删的函数

//test.cSeqListPopBack(&s);//尾删SeqListPushBack(&s, x);//尾插x//SeqList.hvoidSeqListPopBack(SeqList* psl);voidSeqListPushBack(SeqList* psl, SLDataType x);//SeqList.cvoidSeqListPopBack(SeqList* psl){assert(psl);if(psl->size >0){
        psl->size--;}}voidSeqListPushBack(SeqList* psl, SLDataType x){assert(psl->a);SeqListCheckCapacity(psl);//防止内存不够先进行扩容
    psl->a[psl->size]= x;//原本最后一位下标为size-1，插入一个元素为size
    psl->size++;//size个数+1}

5.之后是头插头删函数

//test.cSeqListPopFront(&s, x);//在头部插入xSeqListPushFront(&s);//SeqList.hvoidSeqListPushFront(SeqList*psl，SLDataType x);voidSeqListPopFront(SeqList*psl);//SeqList.cvoidSeqListPushFront(SeqList* psl, SLDataType x){assert(psl);SeqListCheckCapacity(psl);//老样子，先扩容int end = psl->size -1;while(end >=0){
        psl->a[end +1]= psl->a[end];//让元素依次往后移--end;}
    psl->a[0]= x;//在覆盖完成后，x的值就可以赋给第一个元素了
    psl->size++;}voidSeqListPopFront(SeqList*psl){assert(psl);if(psl->size >0)//防止size为负{int begin =1;//定义下标begin，从第二个元素开始while(begin < psl->size)//当begin没有超过size时便会一直覆盖{
            psl->a[begin -1]= psl->a[begin];//让元素依次往前移
            begin++;}--psl->size;//size个数-1}}

6.查找位置删除和查找位置之后插入

//test.cSeqListInsert(&s, pos, x);//在pos位置之前插入xSeqListInsert(&s, pos);//在pos位置删除//SeqList.hvoidSeqListInsert(SeqList* psl, size_t pos, SLDataType x);voidSeqListErase(SeqList* psl, size_t pos);//SeqList.cvoidSeqListInsert(SeqList* psl, size_t pos, SLDataType x){assert(psl);assert(pos < psl->size);//防止查找的pos越界SeqListCheckCapacity(psl);//扩容
    size_t end = psl->size;//end为最后一个元素的下标while(end > pos){
        psl->a[end]= psl->a[end -1];//从后往前移动元素，直到遇到pos位置时停下，相当于将pos位置之前的位置进行前移--end;}
    psl->a[pos]= x;
    psl->size++;}voidSeqListErase(SeqList* psl, size_t pos){assert(psl);assert(pos < psl->size);
    size_t begin = pos +1;while(begin < psl->size){
        psl->a[begin -1]= psl->a[begin];//从后往前移动
        begin++;}   
    psl->size--;}

7.目前为止，我们的增和删就已经完成了，接下来的查和改就很简单了

//test.cSeqListFind(&s, x);SeqListModify(&s, pos, x);//将pos位置改为x//SeqList.hintSeqListFind(SeqList* psl, SLDataType x);voidSeqListModify(SeqList* psl, size_t pos, SLDataType x);//SeqList.cintSeqListFind(SeqList* psl, SLDataType x){assert(psl);for(int i =0; i < psl->size;++i){if(psl->a[i]== x){return i;}}return-1;}voidSeqListModify(SeqList* psl, size_t pos, SLDataType x){assert(psl);assert(pos < psl->size);
    psl->a[pos]= x;}

8.最后，实现一个清空顺序表的函数

//test.cSeqListDestroy(&s);//SeqList.hvoidSeqListDestroy(SeqList* psl);//SeqList.cvoidSeqListDestroy(SeqList* psl){assert(psl);free(psl->a);//注意：释放后的指针为野指针，我们还需要将其置空
    psl->a =NULL;
    psl->capacity = psl->size =0;}

最终代码

test.c部分

#include "SeqList.h"
int main()
{
    SeqList s;
    SeqListInit(&s); //传入结构体s的地址
    SeqListPushFront(&s, 13);//头插
    SeqListPushFront(&s, 12);
    SeqListPushFront(&s, 11);
    SeqListPushFront(&s, 10);

    SeqListPushBack(&s, 19);//尾插
    SeqListPushBack(&s, 20);
    SeqListPushBack(&s, 21);
    SeqListPushBack(&s, 22);

    SeqListInsert(&s, 3, 100);//在第三个元素后插入100
    SeqListPrint(&s);
    SeqListErase(&s, 3);//删除第三个元素
    SeqListPopFront(&s); //头删
    SeqListPopBack(&s); //尾删
    SeqListPrint(&s);
    int num = SeqListFind(&s, 11); //查找值为11的下标
    printf("下标为:%d\n", num); //打印值为11的下标
    SeqListModify(&s, 3, 200); //修改pos之后的值
    SeqListPrint(&s);
    SeqListDestroy(&s);
}

SeqList.h部分

#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefint SLDataType;typedefstruct SeqList {
    SLDataType* a;int size;//存储数据的个数int capacity;//存数据的大小(扩容大小)}SeqList;voidSeqListPrint(SeqList* psl);//打印voidSeqListInit(SeqList* psl);//初始化voidSeqListDestroy(SeqList* psl);//清空voidSeqListCheckCapacity(SeqList* psl);//扩容voidSeqListPushBack(SeqList* psl, SLDataType x);//尾加voidSeqListPopBack(SeqList* psl);//尾删voidSeqListPushFront(SeqList* psl, SLDataType x);//头插voidSeqListPopFront(SeqList* psl);//头删voidSeqListInsert(SeqList* psl, size_t pos, SLDataType x);//在pos位置插入voidSeqListErase(SeqList* psl, size_t pos);//删除pos位置的数据intSeqListFind(SeqList* psl, SLDataType x);//查找voidSeqListModify(SeqList* psl, size_t pos, SLDataType x);//修改

SeqList.c部分

#include"SeqList.h"voidSeqListInit(SeqList* psl){assert(psl);//断言psl不为空
    psl->a =NULL;
    psl->size =0;
    psl->capacity =0;}voidSeqListPrint(SeqList* psl){assert(psl);for(int i =0; i < psl->size;++i){printf("%d ", psl->a[i]);}printf("\n");}voidSeqListCheckCapacity(SeqList* psl){assert(psl);if(psl->size == psl->capacity)//当已有大小等于扩容大小时{
        size_t newCapacity = psl->capacity ==0?4: psl->capacity *2;//从4开始扩容，之后每扩一次都是两倍扩
        SLDataType* tmp =realloc(psl->a,sizeof(SLDataType)* newCapacity);//用*tmp接收扩容后的值if(tmp ==NULL)//当已经无法扩容时退出程序{printf("realloc fail\n");exit(-1);}else{
            psl->a = tmp;
            psl->capacity = newCapacity;}}}voidSeqListPopBack(SeqList* psl){assert(psl);if(psl->size >0){
        psl->size--;}}voidSeqListPushBack(SeqList* psl, SLDataType x){assert(psl->a);SeqListCheckCapacity(psl);//防止内存不够先进行扩容
    psl->a[psl->size]= x;//原本最后一位下标为size-1，插入一个元素为size
    psl->size++;//size个数+1}voidSeqListPushFront(SeqList* psl, SLDataType x){assert(psl);SeqListCheckCapacity(psl);//老样子，先扩容int end = psl->size -1;while(end >=0){
        psl->a[end +1]= psl->a[end];//让元素依次往后移--end;}
    psl->a[0]= x;//在覆盖完成后，x的值就可以赋给第一个元素了
    psl->size++;}voidSeqListPopFront(SeqList* psl){assert(psl);if(psl->size >0)//防止size为负{int begin =1;//定义下标begin，从第二个元素开始while(begin < psl->size)//当begin没有超过size时便会一直覆盖{
            psl->a[begin -1]= psl->a[begin];//让元素依次往前移
            begin++;}--psl->size;//size个数-1}}voidSeqListInsert(SeqList* psl, size_t pos, SLDataType x){assert(psl);assert(pos < psl->size);//防止查找的pos越界SeqListCheckCapacity(psl);//扩容
    size_t end = psl->size;//end为最后一个元素的下标while(end > pos){
        psl->a[end]= psl->a[end -1];//从后往前移动元素，直到遇到pos位置时停下，相当于将pos位置之前的位置进行前移--end;}
    psl->a[pos]= x;
    psl->size++;}voidSeqListErase(SeqList* psl, size_t pos){assert(psl);assert(pos < psl->size);
    size_t begin = pos +1;while(begin < psl->size){
        psl->a[begin -1]= psl->a[begin];//从后往前移动
        begin++;}
    psl->size--;}intSeqListFind(SeqList* psl, SLDataType x){assert(psl);for(int i =0; i < psl->size;++i){if(psl->a[i]== x){return i;}}return-1;}voidSeqListModify(SeqList* psl, size_t pos, SLDataType x){assert(psl);assert(pos < psl->size);
    psl->a[pos]= x;}voidSeqListDestroy(SeqList* psl){assert(psl);free(psl->a);//注意：释放后的指针为野指针，我们还需要将其置空
    psl->a =NULL;
    psl->capacity = psl->size =0;printf("释放完成！\n");}