🚀线性表
【维基百科】 线性表（英语：Linear List）是由n（n≥0）个数据元素（结点）a[0]，a[1]，a[2]…，a[n-1]组成的有限序列。
其中：
- 数据元素的个数n定义为表的长度 = “list”.length() （“list”.length() = 0（表里没有一个元素）时称为空表）
- 将非空的线性表（n>=1）记作：（a[0]，a[1]，a[2]，…，a[n-1]）
- 数据元素a[i]（0≤i≤n-1）只是个抽象符号，其具体含义在不同情况下可以不同
一个数据元素可以由若干个数据项组成。数据元素称为记录，含有大量记录的线性表又称为文件。这种结构具有下列特点：存在一个唯一的没有前驱的（头）数据元素；存在一个唯一的没有后继的（尾）数据元素；此外，每一个数据元素均有一个直接前驱和一个直接后继数据元素。
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
🚀顺序表
🚨概念及结构
【维基百科】 顺序表是在
计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。
即：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
🎈. 静态顺序表：使用定长数组存储元素。
🎈. 动态顺序表：使用动态开辟的数组存储。
🚀接口实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。
所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。
这里的接口其实就是 接口函数 ，这些 接口函数 提供了顺序表的各种基本操作，允许我们对顺序表进行 增、删、查、改 等操作。
📌有哪些接口呢
// 基本 增删查改 接口 --- 命名风格是跟着STL走的，方便后续学习STL // 顺序表初始化 void SeqListInit(SL* psl); // 检查空间，如果满了，进行增容 --> 扩容 void SLCheckCapacity(SL* psl); // 顺序表尾插 void SeqListPushBack(SL* psl, SLDataType x); // 顺序表头插 void SeqListPushFront(SL* psl, SLDataType x); // 顺序表尾删 void SeqListPopBack(SL* psl); // 顺序表头删 void SeqListPopFront(SL* psl); // 顺序表查找 int SeqListFind(SL* psl, SLDataType x); //顺序表的修改 void SeqListModify(SL* psl,int pos, SLDataType x); // 顺序表在pos位置插入x（可以实现头插和尾插） void SeqListInsert(SL* psl, int pos, SLDataType x); // 顺序表删除pos位置的值（可以实现头删和尾删） void SeqListErase(SL* psl, int pos); // 顺序表打印 void SeqListPrint(SL* psl); // 顺序表销毁 void SeqListDestroy(SL* psl);
接下来我将带着大家一 一实现这些接口。
📌准备工作
在写顺序表前，我们需要创建工程，这里为了让大家养成模块化的好习惯，我们尽量将代码分成三个文件来写。这里我打开的编译器是 vs 2022，在资源管理器的 头文件 中创建 SeqList.h 文件，此文件作用主要是为了存储各种头文件和接口函数的声明以及顺序表结构体的创建；在源文件中创建 SeqList.c 文件用来实现接口函数，Test.c 文件用来测试顺序表的各个接口。具体如下图所示：
注意：
- 为了能够在顺序表中方便地存储各种类型的数据，我们可以使用
typedef将要存储的数据类型重命名为SLDataType，这样在定义顺序表的数据类型时只需要使用SLDataType就行了，修改数据类型时只需要修改typedef后面跟着的这个数据类型，这样就大大方便了对不同类型数据的存储。 - 类似的，为了方便结构体的定义和使用，我们也可以使用
typedef将结构体定义一个简单的别名为SL。
#pragma once #include<stdio.h> #include<stdlib.h> // NULL、size_t #include<assert.h> // 静态的顺序表:使用定长数组存储元素。 // 特点：如果满了就不让插入 // 缺点：N给小了不够用，给多了浪费，这个很难确定 //#define N 100 //typedef int SLDataType; // 给int取别名 //struct SeqList // 创建顺序表 //{ // SLDataType a[N]; // 定长数组 // int size; // 存储的有效数据的个数 //}; // 动态顺序表：使用动态开辟的数组存储。 //typedef double SLDatatype; typedef int SLDataType; //重定义类型名称，方便顺序表对不同类型的数据的存储和操作 typedef struct SeqList // 创建顺序表 { SLDataType* a; //指向动态开辟的数组 int size; // 存储的有效数据的个数 int capacity; // 容量空间大小 }SL; //将结构体类型取别名为 SL
📌初始化
这里我们实现动态顺序表，所以刚开始时我们可以假设给定顺序表的大小为 4（即能存放4个元素），不够就扩容，顺序表中刚开始是没有元素的。
//顺序表初始化 void SeqListInit(SL* psl) { //防止psl为空指针（即防止传错结构体地址） assert(psl); psl->a = (SLDataType*)malloc(sizeof(SLDataType) * 4); //判断能否成功开辟空间 if (psl->a == NULL) { perror("malloc fail");//将系统错误信息输出到屏幕 return; } psl->capacity = 4; psl->size = 0; }
📌扩容
在后续对顺序表进行操作过程中我们会插入数据，如果顺序表空间不够，我们就需要使用
realloc函数进行扩容。这里
newcapacity表示扩容后能存放的元素个数（即空间的容量），tmp表示的是扩容后的空间的地址，如果顺序表的空间为空，就给定能存放4个元素的空间；如果空间不够，就在原来空间的基础上，增加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) { printf("realloc fail\n"); exit(-1); //退出程序 } psl->a = tmp; psl->capacity = newcapacity; } }
📌顺序表打印
打印比较简单，这里我们只需要依次遍历每一个节点就行。
//打印 void SeqListPrint(SL* psl) { //防止psl为空指针（即防止传错结构体地址） assert(psl); //遍历 for (int i = 0; i < psl->size; i++) { printf("%d ", psl->a[i]); } printf("\n"); }
📌顺序表销毁
因为是动态开辟的，所以如果空间不用我们就需要销毁掉。如果不销毁会存在内存泄漏的风险，所以这里我们使用
free函数释放开辟的动态空间，并把有效数据个数和容量空间都置为0。
//销毁 void SeqListDestroy(SL* psl) { assert(psl); free(psl->a); psl->a = NULL; psl->size = 0; psl->capacity = 0; }
📌尾插
尾插就是在最后一个元素的后面插入一个元素（即在
size下标位置处插入数据），但要注意的是当capacity空间满了就需要扩容，因此我们要调用SLCheckCapacity函数。
//尾插 void SeqListPushBack(SL* psl, SLDataType x) { assert(psl); //psl->a[psl->size] = x; //psl->size++; SLCheckCapacity(psl); // 检查扩容 psl->a[psl->size++] = x; //复用指定pos下标位置插入数据的函数 //SeqListInsert(psl, psl->size, x); }
📌尾删
尾删其实就是将顺序表最后一个数据删去，要实现这一操作其实只需要将有效数据个数减一就可以了（即
size--），但是在尾删之前要先判断顺序表中是否有元素，如果没有元素就没有必要删了。
//尾删 void SeqListPopBack(SL* psl) { assert(psl); //温柔的处理方式 //if (psl->size > 0) //{ // psl->size--; //} //else //{ // printf("没有数据能够再删了！\n"); // exit(-1); //退出程序 //} //暴力的处理方式 assert(psl->size > 0);//确保顺序表中有数据 psl->size--; //复用pos下标位置删除数据的函数 //SeqListErase(psl, psl->size - 1); }
📌头插
头插操作其实就是在顺序表下表为
0的位置插入数据，然后size++，但是在此之前要判断顺序表容量空间是否已满，所以要先调用SLCheakCapacity函数。
//头插 void SeqListPushFront(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++; //复用指定pos下标位置插入数据的函数 //SeqListInsert(psl, 0, x); }
📌头删
头删的实现其实只需要将顺序表开头后面的数据依次往前挪动，然后将
size--就可以了，这里要从前往后挪，如果从后往前挪数据会被覆盖。注意：这里与尾删类似，在头删之前要先判断顺序表中是否有元素，如果没有元素就没有必要删了。
//头删 void SeqListPopFront(SL* psl) { assert(psl); assert(psl->size > 0);//有数据才能删，没数据就会报错 int begin = 1; while (begin < psl -> size) { psl->a[begin - 1] = psl->a[begin]; begin++; } psl->size--; //复用pos效标位置删除数据的函数 //SeqListErase(psl, 0); }
📌指定pos下标位置插入数据
我们只需要将顺序表中pos位置到最后的数据依次往后挪动（从后往前挪），然后将pos下标位置的数据改为要插入的数据，最后
size++即可。但是我们依然要判断是否满容,所以在插入数据前要调用SLCheakCapacity函数。同时我们也要判断pos位置是否合理，防止越界访问。
//指定pos下标位置插入数据 void SeqListInsert(SL* psl, int pos, SLDataType x) { assert(psl); //if (pos > psl->size || pos < 0) //{ // printf("pos的下标位置越界"); // return; //} //暴力的方式处理（pos下标不能越界） assert(pos >= 0 && pos <= psl->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++; }
📌删除pos位置的数据
与头删类似，我们只需要将pos位置后的数据依次往前挪动将pos位置处的数据覆盖，然后再
size--就可以了。但是要判断pos位置是否合理，防止越界访问。
//删除pos位置的数据（结合SeqListFind函数可以删除指定的数据） void SeqListErase(SL* psl, int pos) { assert(psl); assert(pos >= 0 && pos < psl->size);//pos位置需要有数据 //挪动数据 int begin = pos + 1; while (begin < psl->size) { psl->a[begin - 1] = psl->a[begin]; begin++; } psl->size--; }
📌查找
这个比较简单，我们只需要遍历一遍顺序表，查找相应数据，若找到，就返回下标，若没找到，就返回-1。
//查找，找到了返回下标，没找到返回-1 int SeqListFind(SL* psl, SLDataType x) { assert(psl); for (int i = 0; i < psl->size; i++) { if (psl->a[i] == x) { return i; } } return -1; }
📌修改pos位置的数据
通过pos下标直接修改
//修改pos位置的数据 void SeqListModify(SL* psl, int pos, SLDataType x) { assert(psl); assert(pos >= 0 && pos < psl->size); psl->a[pos] = x; }
🚀源码
🌴SeqList.h 文件
#pragma once #include<stdio.h> #include<stdlib.h>//NULL、size_t #include<assert.h> // 静态的顺序表:使用定长数组存储元素。 // 特点：如果满了就不让插入 // 缺点：N给小了不够用，给多了浪费，这个很难确定 //#define N 10000 //typedef int SLDatatype; // 给int取别名 //struct SeqList // 创建顺序表 //{ // SLDatatype a[N]; // 定长数组 // int size; // 存储的有效数据的个数 //}; //静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪 //费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实 //现动态顺序表。 // 动态顺序表：使用动态开辟的数组存储。 //typedef double SLDatatype; typedef int SLDataType; //重定义类型名称，方便顺序表对不同类型的数据的存储和操作 typedef struct SeqList { SLDataType* a; //指向动态开辟的数组 int size; // 存储的有效数据的个数 int capacity; // 容量空间大小 }SL; // 基本 增删查改 接口 --- 命名风格是跟着STL走的，方便后续学习STL // 顺序表初始化 void SeqListInit(SL* psl); // 检查空间，如果满了，进行增容 void SLCheckCapacity(SL* psl); // 顺序表尾插 void SeqListPushBack(SL* psl, SLDataType x); // 顺序表尾删 void SeqListPopBack(SL* psl); // 顺序表头插 void SeqListPushFront(SL* psl, SLDataType x); // 顺序表头删 void SeqListPopFront(SL* psl); // 顺序表查找 int SeqListFind(SL* psl, SLDataType x); // 顺序表在pos位置插入x（可以实现头插和尾插） void SeqListInsert(SL* psl, int pos, SLDataType x); // 顺序表删除pos位置的值（可以实现头删和尾删） void SeqListErase(SL* psl, int pos); // 顺序表打印 void SeqListPrint(SL* psl); // 顺序表销毁 void SeqListDestroy(SL* psl); //顺序表的修改 void SeqListModify(SL* psl, int pos, SLDataType x);
🌴SeqList.c 文件
#include"SeqList.h" //void SeqListInit(SL* psl) //{ // psl->a = NULL; // psl->size = 0; // psl->capacity = 0; //} //顺序表初始化 void SeqListInit(SL* psl) { //防止psl为空指针（即防止传错结构体地址） assert(psl); psl->a = (SLDataType*)malloc(sizeof(SLDataType) * 4); //判断能否成功开辟空间 if (psl->a == NULL) { perror("malloc fail");//将系统错误信息输出到屏幕 return; } psl->capacity = 4; psl->size = 0; } //销毁 void SeqListDestroy(SL* psl) { assert(psl); free(psl->a); psl->a = NULL; psl->size = 0; psl->capacity = 0; } //打印 void SeqListPrint(SL* psl) { assert(psl); for (int i = 0; i < psl->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) { printf("realloc fail\n"); exit(-1);//退出程序 } psl->a = tmp; psl->capacity = newcapacity; } } //尾插 void SeqListPushBack(SL* psl, SLDataType x) { assert(psl); //psl->a[psl->size] = x; //psl->size++; SLCheckCapacity(psl);//检查扩容 psl->a[psl->size++] = x; //复用指定pos下标位置插入数据的函数 //SeqListInsert(psl, psl->size, x); } //尾删 void SeqListPopBack(SL* psl) { assert(psl); //温柔的处理方式 //if (psl->size > 0) //{ // psl->size--; //} //else //{ // printf("没有数据能够再删了！\n"); // exit(-1); //} //暴力的处理方式 assert(psl->size > 0);//确保顺序表中有数据 psl->size--; //复用pos下标位置删除数据的函数 //SeqListErase(psl, psl->size - 1); } //头插 void SeqListPushFront(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++; //复用指定pos下标位置插入数据的函数 //SeqListInsert(psl, 0, x); } //头删 void SeqListPopFront(SL* psl) { assert(psl); assert(psl->size > 0);//有数据才能删，没数据就会报错 int begin = 1; while (begin < psl -> size) { psl->a[begin - 1] = psl->a[begin]; begin++; } psl->size--; //复用pos效标位置删除数据的函数 //SeqListErase(psl, 0); } //查找，找到了返回下标，没找到返回-1 int SeqListFind(SL* psl, SLDataType x) { assert(psl); for (int i = 0; i < psl->size; i++) { if (psl->a[i] == x) { return i; } } return -1; } //指定pos下标位置插入数据 void SeqListInsert(SL* psl, int pos, SLDataType x) { assert(psl); //if (pos > psl->size || pos < 0) //{ // printf("pos的下标位置越界"); // return; //} //暴力的方式处理（pos下标不能越界） assert(pos >= 0 && pos <= psl->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++; } //删除pos位置的数据（结合SeqListFind函数可以删除指定的数据） void SeqListErase(SL* psl, int pos) { assert(psl); assert(pos >= 0 && pos < psl->size);//pos位置需要有数据 //挪动数据 int begin = pos + 1; while (begin < psl->size) { psl->a[begin - 1] = psl->a[begin]; begin++; } psl->size--; } //修改pos位置的数据 void SeqListModify(SL* psl, int pos, SLDataType x) { assert(psl); assert(pos >= 0 && pos < psl->size); psl->a[pos] = x; }
🌴Test.c 文件
#define _CRT_SECURE_NO_WARNINGS 1 #include "SeqList.h" int main() { SL s; SeqListInit(&s); SeqListPushBack(&s, 1); SeqListPushBack(&s, 2); SeqListPushBack(&s, 3); SeqListPushBack(&s, 4); SeqListPushBack(&s, 5); SeqListPushBack(&s, 6);//尾插 SeqListPopBack(&s);//尾删 SeqListPushFront(&s, 0);//头插 SeqListPopFront(&s);//头删 SeqListInsert(&s, 2, 8);//指定pos下标为2的位置插入数据8 SeqListPrint(&s);//打印 SeqListDestroy(&s);//销毁 return 0; }
💨 今天的分享就到这里，如果觉得博主的文章还不错的话， 请👍三连支持一下博主哦🤞
