【数据结构】顺序表 超详细！

大家好，欢迎来到IT知识分享网。

目录

一.顺序表定义

1 、顺序表的概念及结构

1.1线性表

2、顺序表分类

2.1 静态顺序表

2.2 动态顺序表

二、动态顺序表的实现 ( 重要！)

1.准备工作及其注意事项

1.1 先创建三个文件

1.2 注意事项：帮助高效记忆和理解

2.顺序表的基本功能接口

2.0 创建一个 顺序表

2.1 顺序表的初始化

2.2 顺序表的销毁

2.3 顺序表的打印

3.顺序表的扩容检查接口

4.顺序表的增加功能接口

4.1 尾插接口

4.2 头插接口

4.3 指定位置插入接口

5.顺序表的删除功能接口

5.1 尾删接口

5.2头删接口

5.3指定位置删除接口

6.顺序表的查找实现接口

三.总代码

SeqList.h

SepList.c

test.c

一.顺序表定义

1 、顺序表的概念及结构

1.1线性表

线性表（linearlist）是n个具有相同特性的数据元素的有限序列。

线性表是一种在实际中广泛使  用的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串…  

线性表在逻辑上是线性结构，也就说是连续的一条直线。

但是在物理结构上并不一定是连续的，  线性表在物理上存储时，通常以数组和链式结构的形式存储。  简单来说顺序表是线性表的一种,而且逻辑和物理都是线性结构

2、顺序表分类

顺序表和数组的区别

◦ 顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口

2.1 静态顺序表

概念：使用定长数组存储元素

静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费

 静态顺序表(这里拿里面存储的整形举例)  typedef int SLDataType;  #define N 100  typedef struct SeqList  {      SLDatatype arr[N];      int size;//size是有效数据的个数  }SL;    解释一下为什么要把存储的类型变为SLDataType  这么做是为了方便以后修改 使用 不同 的类型  还有把数组存储的数据容量N 便于修改

2.2 动态顺序表

前言：

动态顺序表的结构更加灵活, 可以对结构进行 增删查改，所以我们下面的接口都是通过动态顺序表实现的

二、动态顺序表的实现(重要！)

1.准备工作及其注意事项

1.1 先创建三个文件

 解释这三个文件的作用  1、头文件SeqList.h  是来声明接口函数，定义顺序表，将几个公共用到的库函数集合起来  2、源文件SeqList.c  是用来具体实现接口  3、源文件test.c  用于接口的测试工作 ，即具体的使用场景

1.2 注意事项：帮助高效记忆和理解

 1.不管写任意一种接口函数，我们在处理之前都要进行断言，避免穿过来的是NULL指针  assert(ps->arr) ;  2.在进行扩容操作 的时候别忘记了 realloc要将新空间的地址和容量 更新给 自己的数组 和 容量变量(在下文)  3.进行插入操作之后  要把size++;  在进行删除操作的时候要进行size--;(很重要的一点)  4、插入操作 和 删除操作 用到循环 数据整体后移 或 前移 一定要注意 边界！！！

2.顺序表的基本功能接口

2.0 创建一个 顺序表

//动态顺序表 typedef int SLDataType;// 定义一个 类型名字，方便快速修改 类型 typedef struct SeqList { SLDataType* arr; int capacity; // 记录动态顺序表 申请空间的大小 int size;// 记录 顺序表 当前有效的数据个数 }SL; // 给 结构体命名，翻遍方便使用：直接写在下面也可以 // typedef struct SeqList SL;

2.1 顺序表的初始化

void SLInit(SL* ps) { assert(ps); ps->arr = NULL; ps->capacity = ps->size = 0; }

2.2 顺序表的销毁

void SLDestroy(SL* ps) { assert(ps); free(ps->arr); ps->arr = NULL; ps->capacity = ps->size = 0; }

2.3 顺序表的打印

// 打印顺序表：这里可以 传值 也可 传址 ， // 因为不需要对数据进行修改(可以传值)，但是 为了保持接口一致性(其他接口都是传址)，这里直接使用 传址 void SLPrint(SL* ps) { for (int i = 0; i < ps->size; ++i) printf("%d ", ps->arr[i]); printf("\n"); }

3.顺序表的扩容检查接口

// 公共的扩容判断 void SLCheckCapacity(SL* ps) { //当容量capacity 大小 == 标记点size 时，说明 已经满了：需要 扩容 if (ps->size == ps->capacity) { // 开辟空间时注意，当capacity初始化为 0 时，直接相乘的结果还是 0 ！！ // 所以要先判断一下, 并且需要做 申请空间是否成功的判断， // 还不能直接将申请的空间赋值给 目标数组，先给一个 临时变量 int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; // 每次 两倍空间扩容(tip：这里推荐2倍的倍数扩容，可以自行查找为什么倍数扩容 较好！) SLDataType* ptmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType)); if (ptmp == NULL) { perror("realloc fail!"); exit(1); } // 扩容成功 ps->arr = ptmp; ps->capacity = newCapacity; } }

4.顺序表的增加功能接口

4.1 尾插接口

// （1）尾插法：有三种情况：1) 头部非空，尾部还有空间；2)全部为空；3)全部满了 void SLPushBack(SL* ps, SLDataType x) { // 先判断指针是否非空 assert(ps); // 空间不够，扩容 : 3） SLCheckCapacity(ps); // 空间足够，直接插入：1 ) ; 2 ) // 在 size 这个位置插入数据: size 是标记第一个空位置 ps->arr[ps->size++] = x; // ps->size++; // 标记点size 需要即使更新：size++ 也可以合并在上面 }

4.2 头插接口

// 头插法 void SLPushFront(SL* ps, SLDataType x) { assert(ps); // 空间不够，扩容 : 3） SLCheckCapacity(ps); // 将数据向后挪动：注意边界问题！！！ for (int i = ps->size; i > 0; --i) ps->arr[i] = ps->arr[i - 1]; ps->arr[0] = x; // 将插入数据 放在头部 ps->size++; // 别忘 了 更新 size } 

4.3 指定位置插入接口

// 指定位置之前插入数据 void SLInsert(SL* ps, int pos, SLDataType x) { assert(ps); // 注意 ： 可以指定位置插入 说明 指定的位置pos 可能不合理，可能越界, 必须要断言判断一下 assert(0 <= pos && pos < ps->size); // 注意 不能等于 size！！！！ // 判断是否有足够的空间 SLCheckCapacity(ps); // 在 pos 位置中 插入 数据 x ：就要将 pos 位置 起的 后面数据向后挪动 for (int i = ps->size; i >= pos + 1; --i) // 让 pos 这个位置 空出来 { ps->arr[i] = ps->arr[i - 1]; } ps->arr[pos] = x; ps->size++; }

5.顺序表的删除功能接口

5.1 尾删接口

void SLPopBack(SL* ps) { // 删除前 检查：顺序表非空才能执行删除，同时 size 不能为 0 assert(ps); assert(ps->size);// 顺序表不为空 ps->size--; // 直接 size-- 将 size 位置的数值 丢出 我们的有效数据空间，那个位置不属于有效空间了，则类似达到删除的效果 }

5.2头删接口

void SLPopFront(SL* ps) { // 删除前 检查：顺序表非空才能执行删除，同时 size 不能为 0 assert(ps); assert(ps->size); // 将 后面的 数据 向前移动： 注意边界！！ for (int i = 1; i < ps->size; ++i) ps->arr[i - 1] = ps->arr[i]; ps->size--; }

5.3指定位置删除接口

void SLErase(SL* ps, int pos) { assert(ps); // 注意 ： 可以指定位置插入 说明 指定的位置可能不合理，可能越界, 必须要断言判断一下 assert(0 <= pos && pos < ps->size); // 注意 不能等于 size for (int i = pos + 1; i < ps->size; ++i) { ps->arr[i - 1] = ps->arr[i]; } ps->size--; }

6.顺序表的查找实现接口

int SLFind(SL* ps, int x) { for (int i = 0;i < ps->size;++i) { if (ps->arr[i] == x) { return i; } } return -1; }

三.总代码

SeqList.h

#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int SLDataType; typedef struct SeqList { SLDataType* arr; int Capacity; int size; }SL; // 一、初始化 void SLInit(SL* ps); // 二、 尾插法 void SLPushBack(SL* ps, SLDataType x); // 二、 头插法 void SLPushFront(SL* ps, SLDataType x); // 三、尾删法 void SLPopBack(SL* ps); // 四、头删法 void SLPopFront(SL* ps); // 五、指定位置删除 void SLErase(SL* ps, int pos); // 六、指定位置插入 void SLInsert(SL* ps, int pos, SLDataType x); //顺序表的扩容检查(扩容的原则,以及扩容的方法) void SLCheckCapacity(SL* ps); // 打印函数 void SLPrint(SL* ps);

SepList.c

#include"SeqList.h" void SLInit(SL* ps) { ps->arr = NULL; ps->Capacity = ps->size = 0; } // 开辟空间函数 void SLCheckCapacity(SL* ps) { if (ps->size == ps->Capacity) { int NewCapacity = ps->Capacity == 0 ? 4 : 2 * (ps->Capacity); SLDataType* ptmp = realloc(ps->arr, NewCapacity * sizeof(SLDataType)); if (ptmp == NULL) { perror("realloc fail !"); exit(1); } ps->arr = ptmp; ps->Capacity = NewCapacity; } } // 二、 尾插法 void SLPushBack(SL* ps, SLDataType x) { // 先判断指针是否非空 assert(ps); // 别忘了 // 分两大类情况：空间足够 和 空间不够 // (1) 空间不够：空间扩展 SLCheckCapacity(ps); // 开始尾插 ps->arr[ps->size++] = x; } // 二、 头插法 void SLPushFront(SL* ps, SLDataType x) { assert(ps); // 别忘了 SLCheckCapacity(ps); for (int i = ps->size; i > 0; --i) { ps->arr[i] = ps->arr[i - 1]; } ps->arr[0] = x; ps->size++; // 别忘记了 } // 三、尾删法 void SLPopBack(SL* ps) { assert(ps); assert(ps->size); ps->size--; } // 四、头删法 void SLPopFront(SL* ps) { assert(ps); assert(ps->size); for (int i = 0; i < ps->size - 1; ++i) { ps->arr[i] = ps->arr[i + 1]; } ps->size--; } // 五、指定位置删除 void SLErase(SL* ps, int pos) { assert(ps); assert(0 <= pos && pos < ps->size); for (int i = pos; i < ps->size - 1; ++i) { ps->arr[i] = ps->arr[i + 1]; } ps->size--; } // 六、指定位置插入 void SLInsert(SL* ps, int pos, SLDataType x) { assert(ps); // 别忘了 assert(0 <= pos && pos < ps->size); SLCheckCapacity(ps); for (int i = ps->size; i >= pos + 1; --i) { ps->arr[i] = ps->arr[i - 1]; } ps->arr[pos] = x; ps->size++; // 别忘记了 } // 打印函数 void SLPrint(SL* ps) { for (int i = 0; i < ps->size; ++i) { printf("%d ", ps->arr[i]); } printf("\n"); }

test.c

#include"SeqList.h" void slTest01() { SL sl; // 创建一个结构体变量 sl SLInit(&sl); // 这里需要 传地址：才能真正被初始化 //测试尾插 SLPushBack(&sl, 1); SLPushBack(&sl, 2); SLPushBack(&sl, 3); SLPushBack(&sl, 4); // ctrl + d == ctrl + c + v printf("测试尾插: "); SLPrint(&sl); // 测试头插 SLPushFront(&sl, 10); printf("测试头插: "); SLPrint(&sl); // 测试 尾删 SLPopBack(&sl); printf("测试尾删: "); SLPrint(&sl); // 测试 头删 SLPopFront(&sl); printf("测试头删: "); SLPrint(&sl); // 测试 指定位置插入 SLInsert(&sl, 1, 15); printf("指定插入: "); SLPrint(&sl); SLErase(&sl, 1); printf("指定删除: "); SLPrint(&sl); } int main() { slTest01(); // 第一个测试函数 return 0; }

四、顺序表的问题及思考

问题：

1. 中间/头部的插⼊删除，时间复杂度为O(N)

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不⼩的消耗。

3. 增容⼀般是呈2倍的增⻓，势必会有⼀定的空间浪费。例如当前容量为100，满了以后增容到 200，我们再继续插⼊了5个数据，后⾯没有数据插⼊了，那么就浪费了95个数据空间。

思考：如何解决以上问题呢？

有没有 这样一个 数据结构

1、中间 和 头尾的 数据插入 不用 挪动 其他数据，而是一步到位

2、不需要直接扩充连续的空间（用不完容易浪费，像上面第 3 点所说）

3、不会造成空间浪费

这样的强大的数据结构 即为  【 链表 】

可以 点击跳转 讲解 单链表 的实现文章  —->：【数据结构】单链表的实现

完。

若上述文章有什么错误，欢迎各位大佬及时指出，我们共同进步！