🍔一、前言
停更了一个月限时返场啦😍从本篇文章开始就进入了我们数据结构的学习喽！本篇文章也是《数据结构与算法》 专栏的第一篇文章，本篇的内容是顺序表的学习，也是数据结构的开胃小菜，希望烙铁们可以理解消化哦🥰！！！
在我们学习顺序表之前呢，我们大家肯定会有疑问，什么是数据结构，为什么要去学习数据结构，顺序表在数据结构里面代表什么呢？，这里我来给大家一次解惑，让大家真正的搞懂数据结构，学习起来才更加有动力🥰！
🍟1. 什么是数据结构
🚩简单地说，数据结构是以某种特定的布局方式存储数据的容器。这种“布局方式”决定了数据结构对于某些操作是高效的，而对于其他操作则是低效的。首先我们需要理解各种数据结构，才能在处理实际问题时选取最合适的数据结构。
🚩数据的逻辑结构是指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后间关系，而与他们在计算机中的存储位置无关。逻辑结构分为以下几种：
🔴集合结构：数据元素同属一个集合，单个数据元素之间没有任何关系。
🔴线性结构：数据结构中的元素存在一对一的相互关系。
🔴树形结构：数据结构中的元素存在一对多的相互关系。
🔴图形结构：数据结构中的元素存在多对多的相互关系。
🚩数据的物理结构是指数据的逻辑结构在计算机存储空间的存放形式，它包括数据元素的机内表示和关系的机内表示。物理结构又叫存储结构，分为以下几种：
🔴顺序存储结构：一段连续的内存空间。优点：随机访问；缺点：插入删除效率低，大小固定。
🔴链式存储结构：不连续的内存空间。优点：大小动态扩展，插入删除效率高；缺点：不能随机访问。
🔴索引存储结构：为了方便查找，整体无序，但索引块之间有序，需要额外空间，存储索引表。优点：对顺序查找的一种改进，查找效率高；缺点：需额外空间存储索引。
🔴散列存储结构：选取某个函数，数据元素根据函数计算存储位置可能存在多个数据元素存储在同一位置，引起地址冲。优点：查找基于数据本身即可找到，查找效率高，存取效率高；缺点：存取随机，不便于顺序查找。
🍔二、顺序表的概念----线性表
🍟1. 什么是线性表
本次我们要来介绍，第一种数据结构，也是数据结构中最简单的一部分：线性表
此时此刻，肯定会有烙铁会有疑问，为什么难道他会像一条线一样一次连接吗？
没错，当数据首尾依次相连接，这种数据结构就被叫做线性表。
注意 ：相连接是逻辑上的连接，不是空间上的连接。
此时，可能还会有烙铁站出来说：你说的这不就是数组嘛，小意思，我会！
其实 数组只是一种线性表，可是线性表还有很多种形式哦！
线性表的形式： 数组、链表、顺序表、队列等 （其中数组我们在C语言已经学过，不再提及） 。
🚨官方解释：线性表（linear list）是 n 个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就是说是连续的一条直线。但是在物理结构上不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
🍟2. 顺序表与数组的区别
🚩顺序表：顺序表是用 一段物理地址连续存储单元 ，依次存储数据元素的线性结构
顺序表就是将数据连着存放，存放的数据空间也是连着的🚩数组：数据不用按顺序的存放，可以随意的存放
🚩区别：数组不按空间顺序随意地存放数据，但是顺序表的数据是要按照空间的的顺序存放
说的这里估计有些烙铁已经开始有点 晕晕的状态了，我来给大家画图解释一下：
🍔三、顺序表详解
💧 静态顺序表
🚩静态顺序表：使用定长数组存储
🚩优点：操作简单，代码实现容易
🚩缺点：定长数组很受限制，数组开小了不够用，开大了又浪费
//静态顺序表 #define N 10; typedef int SLDatatype; typedef struct SeqList { SLDatatype a[N]; int size; }SL;
💧 动态顺序表
🚩动态顺序表：使用动态开辟的数组进行数据的存储
🚩优点：数组大小可以根据自己的需求进行调节
🚩缺点：代码比较复杂
//动态顺序表 typedef int SLDatatype; typedef struct SeqList { SLDatatype* a; //指向动态开辟的数组 int size; //存储的有效数据的个数 int capacity; //当前容量 }SL;
🍎创建动态顺序表
🥰这里先创建三个文件：
1️⃣：SeqList.h文件，用于函数的声明
2️⃣：SeqList.c文件，用于函数的定义
3️⃣：Test.c文件，用于测试函数
建立三个文件的目的： 将顺序表作为一个项目来进行书写，方便我们的学习与观察。
⭕接口1：定义结构体SL
🥰请看代码与注释👇
typedef int SLDatatype; //数据类型 typedef struct SeqList { SLDatatype* a; //指向动态开辟的数组 int size; //存储的有效数据的个数 int capacity; //当前容量 }SL;
⭕接口2：初始化结构体（SLInit）
🥰请看代码与注释👇
void SLInit(SL* psl) { assert(psl); psl->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4); if (psl->a == NULL) { perror("malloc fail"); return; } psl->capacity = 4; psl->size = 0; }
⭕接口3：检查结构体中的数组是否需要扩容(SLCheckCapacity)
🥰请看代码与注释👇
void SLCheckCapacity(SL* psl) { assert(psl); if (psl->size == psl->capacity) { SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * psl->capacity * 2); if (tmp == NULL); { perror("realloc fail"); return; } psl->a = tmp; psl->capacity *= 2; } }
⭕接口4：结构体销毁（SLDestroy）
销毁顺序表所开辟的空间，防止内存泄漏
🥰请看代码与注释👇
void SLDestroy(SL* psl) { assert(psl); free(psl->a); psl->a = NULL; psl->size = 0; psl->capacity = 0; }
⭕接口5：打印（SLPrint）
🥰请看代码与注释👇
void SLPrint(SL* psl) { assert(psl); for (int i = 0; i < psl->size; i++) { printf("%d ", psl->a[i]); } printf("\n"); }
⭕接口6：尾插（SLPushBack）
🥰请看代码与注释👇
void SLPushBack(SL* psl, SLDatatype x) { assert(psl); SLCheckCapacity(psl);//检查是否需要扩容 psl->a[psl->size] = x; psl->size++; }
⭕接口7：头插（SLPushFront）
（1）从第一个数据开始向后挪动：会发生覆盖----不可取❌
（2）从最后一个数据开始向后挪动：理想状态✅
🥰请看代码与注释👇
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++; }
⭕接口8：尾删（SLPopBack）
🥰请看代码与注释👇
void SLPopBack(SL* psl) { //暴力检查 assert(psl->size > 0); //温柔的检查 //if (psl->size == 0) // return; psl->size--; }
⭕接口9：头删（SLPopFront）
（1）从最后一个数据开始向前挪动：会发生覆盖----不可取❌
（1）先从下标为 1 的数据开始向前挪动：理想状态✅
🥰请看代码与注释👇
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++; }
⭕接口10：在指定位置（pos）插入（SLInsert）
🚨要实现这一功能，我们依然需要一个end下标，数据从后往前依次后挪，直到pos下标移动完毕。另外，别忘了检查容量。
🥰请看代码与注释👇
void SLInsert(SL* psl, int pos, SLDatatype x) { assert(0 <= pos && 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++; }
🥰拓展：了解了以上在指定位置插入的代码之后，我们就可以在头插和尾插中复用该功能
👇请看代码👇
//尾插 void SLPushBack(SL* psl, SLDatatype x) { SLInsert(psl, psl->size, x); } //头插 void SLPushFront(SL* psl, SLDatatype x) { SLInsert(psl, 0, x); }
🥰这样写是不是非常滴香！
⭕接口11：在指定位置（pos）删除（SLErase）
🚨要实现这一功能，我们依然需要一个start下标，数据从前往后依次前挪，直到移动完毕。
🥰请看代码与注释👇
void SLErase(SL* psl, int pos) { assert(0 <= pos && pos < psl->size); int start = pos + 1; while (start < psl->size) { psl->a[start - 1] = psl->a[start]; start++; } psl->size--; }
🥰拓展：同样的了解了以上在指定位置删除的代码之后，我们就可以在头删和尾删中复用该功能
👇请看代码👇
//尾删 void SLPopBack(SL* psl) { SLErase(psl, psl->size - 1); } //头删 void SLPopFront(SL* psl) { SLErase(psl, 0); }
⭕接口12：查找某一个数据的位置（SLFind）
找到返回下标，没找到返回-1
🥰请看代码与注释👇
int SLFind(SL* psl, SLDatatype x) { assert(psl); for (int i = 0; i < psl->size; i++) { if (psl->a[i] == x) { return i; } } return -1; }
⭕接口13：查找某一个数据的位置（SLFind）
🥰请看代码与注释👇
void SLModify(SL* psl, int pos, SLDatatype x) { assert(0 <= pos && pos < psl->size); psl->a[pos] = x; }
⭕菜单
🚨数据结构阶段不建议写菜单，不便于调试，本篇文章菜单写在下面的完整代码中的 Test.c文件和 main主函数中了，需要的烙铁自行学习查看🥰
🍔四、完整代码
🍪SeqList.h
#include<stdio.h> #include<stdlib.h> #include<errno.h> #include<string.h> #include<assert.h> //动态顺序表 typedef int SLDatatype; //数据类型 typedef struct SeqList { SLDatatype* a; //指向动态开辟的数组 int size; //存储的有效数据的个数 int capacity; //当前容量 }SL; //初始化 void SLInit(SL* psl); //销毁 void SLDestroy(SL* psl); //检查是否需要扩容 void SLCheckCapacity(SL* psl); //打印 void SLPrint(SL* psl); //尾插 void SLPushBack(SL* psl, SLDatatype x); //头插 void SLPushFront(SL* psl, SLDatatype x); //尾删 void SLPopBack(SL* psl); //头删 void SLPopFront(SL* psl); //在pos位置插入 void SLInsert(SL* psl, int pos, SLDatatype x); //在pos位置删除 void SLErase(SL* psl, int pos); //查找（找到返回下标，没找到返回-1） int SLFind(SL* psl, SLDatatype x); //修改 void SLModify(SL* psl, int pos, SLDatatype x);
🍪SeqList.c
#include"SeqList.h" //初始化 void SLInit(SL* 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 SLDestroy(SL* psl) { assert(psl); free(psl->a); psl->a = NULL; psl->size = 0; psl->capacity = 0; } //检查是否需要扩容 void SLCheckCapacity(SL* psl) { assert(psl); if (psl->size == psl->capacity) { SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * psl->capacity * 2); if (tmp == NULL); { perror("realloc fail"); return; } psl->a = tmp; psl->capacity *= 2; } } //打印 void SLPrint(SL* psl) { assert(psl); for (int i = 0; i < psl->size; i++) { printf("%d ", psl->a[i]); } printf("\n"); } //尾插 void SLPushBack(SL* psl, SLDatatype x) { //SLCheckCapacity(psl); //psl->a[psl->size] = x; //psl->size++; SLInsert(psl, psl->size, x); } //头插 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++; SLInsert(psl, 0, x); } //尾删 void SLPopBack(SL* psl) { //暴力检查 //assert(psl->size > 0); //温柔的检查 //if (psl->size == 0) // return; //psl->size--; SLErase(psl, psl->size - 1); } //头删 void SLPopFront(SL* psl) { //暴力检查 //assert(psl->size > 0); //int start = 1; //while (start < psl->size) //{ // psl->a[start - 1] = psl->a[start]; // start++; //} //psl->size--; SLErase(psl, 0); } //在pos位置插入 void SLInsert(SL* psl, int pos, SLDatatype x) { assert(0 <= pos && 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位置删除 void SLErase(SL* psl, int pos) { assert(0 <= pos && pos < psl->size); int start = pos + 1; while (start < psl->size) { psl->a[start - 1] = psl->a[start]; start++; } psl->size--; } //查找（找到返回下标，没找到返回-1） int SLFind(SL* psl, SLDatatype x) { assert(psl); for (int i = 0; i < psl->size; i++) { if (psl->a[i] == x) { return i; } } return -1; } //修改 void SLModify(SL* psl, int pos, SLDatatype x) { assert(0 <= pos && pos < psl->size); psl->a[pos - 1] = x; }
🥝Test.c
#include"SeqList.h" //尾插测试 void TestSeqList1() { SL s; SLInit(&s); SLPushBack(&s, 1); SLPushBack(&s, 2); SLPushBack(&s, 3); SLPushBack(&s, 4); SLPushBack(&s, 5); SLPushBack(&s, 6); SLPushBack(&s, 7); SLPushBack(&s, 8); SLPrint(&s); SLDestroy(&s); } //头插测试 void TestSeqList2() { SL s; SLInit(&s); SLPushBack(&s, 1); SLPushBack(&s, 2); SLPushBack(&s, 3); SLPushBack(&s, 4); SLPushBack(&s, 5); SLPushFront(&s, 6); SLPushFront(&s, 7); SLPushFront(&s, 8); SLPrint(&s); SLDestroy(&s); } //尾删测试 void TestSeqList3() { SL s; SLInit(&s); SLPushBack(&s, 1); SLPushBack(&s, 2); SLPushBack(&s, 3); SLPushBack(&s, 4); SLPushBack(&s, 5); SLPushFront(&s, 6); SLPushFront(&s, 7); SLPushFront(&s, 8); SLPrint(&s); SLPopBack(&s); SLPopBack(&s); SLPrint(&s); SLDestroy(&s); } //头删测试 void TestSeqList4() { SL s; SLInit(&s); SLPushBack(&s, 1); SLPushBack(&s, 2); SLPushBack(&s, 3); SLPushBack(&s, 4); SLPushBack(&s, 5); SLPushFront(&s, 6); SLPushFront(&s, 7); SLPushFront(&s, 8); SLPrint(&s); SLPopBack(&s); SLPopBack(&s); SLPrint(&s); SLPopFront(&s); SLPopFront(&s); SLPrint(&s); SLDestroy(&s); } //指定位置插入测试 void TestSeqList5() { SL s; SLInit(&s); SLPushBack(&s, 1); SLPushBack(&s, 2); SLPushBack(&s, 3); SLPushBack(&s, 4); SLPushBack(&s, 5); SLPushFront(&s, 6); SLPushFront(&s, 7); SLPrint(&s); SLInsert(&s, 2, 30); SLPrint(&s); SLDestroy(&s); } //指定位置删除测试 void TestSeqList6() { SL s; SLInit(&s); SLPushBack(&s, 1); SLPushBack(&s, 2); SLPushBack(&s, 3); SLPushBack(&s, 4); SLPushBack(&s, 5); SLPushBack(&s, 6); SLPrint(&s); SLInsert(&s, 2, 30); SLPrint(&s); SLErase(&s, 2); SLPrint(&s); SLDestroy(&s); } //菜单 void menu() { printf("***********************************************************\n"); printf("1、尾插数据 2、尾删数据\n"); printf("\n"); printf("3、头插数据 4、头删数据\n"); printf("\n"); printf("5、在任意位置插入数据（位置3插入20）\n"); printf("\n"); printf("6、在任意位置删除数据 \n"); printf("\n"); printf("7、查找某个数据的位置 \n"); printf("\n"); printf("8、修改数据 \n"); printf("\n"); printf("9、打印数据 \n"); printf("\n"); printf("-1、退出 \n"); printf("\n"); printf("***********************************************************\n"); } int main() { printf("************* 欢迎大家来到动态顺序表的测试 **************\n"); int option = 0; SL s; SLInit(&s); do { menu(); printf("请输入你的操作：>"); scanf("%d", &option); int sum = 0; int x = 0; int y = 0; int z = 0; int pos = 0; int w = 0; int o = 0; int p = 0; switch (option) { case 1: printf("请依次输入你要尾插的数据：，以-1结束\n"); scanf("%d", &sum); while (sum != -1) { SLPushBack(&s, sum); // 1.尾插 scanf("%d", &sum); } break; case 2: SLPopBack(&s); // 2.尾删 break; case 3: scanf("%d", &x); SLPushFront(&s, x); // 3.头插 break; case 4: SLPopFront(&s); // 4.头删 break; case 5: SLInsert(&s, 3, 20); // 5.在任意位置插入数据 break; case 6: SLErase(&s, 3); // 6.在任意位置删除数据 break; case 7: printf("请输入要删除序列的中的某个数据>\n"); scanf("%d", &z); y = SLFind(&s, z); // 7.查找某个数字的位置 printf("%d的位置在%d处： \n", z, y); break; case 9: SLPrint(&s); break; case 8: printf("请输入要修改序列的中的某个数据的下标：>\n"); scanf("%d", &o); printf("请输入要修改成什么：>\n"); scanf("%d", &p); SLModify(&s, o, p); break; default: if (option == -1) { exit(0); // 退出程序 } else { printf("输入错误，请重新输入\n"); } break; } } while (option != -1); // 退出程序 SLDestroy(&s); return 0; }
✅运行界面
