数据结构与算法

Lesson02 - 顺序表C语言实现（没有伪代码）

文章目录

• 数据结构与算法
• 前言
• 1 什么是顺序表
• • 1.1 基本概念
  • 1.2 顺序表的类型
• 二、顺序表上的基本操作实现（c语言版）
• • 2.1 初始化
  • 2.2 销毁
  • 2.3 打印
  • 2.4 增容
  • 2.5 尾插
  • 2.6 尾删
  • 2.7 在 pos 位置插入元素
  • 2.8 删除 pos 位置的元素
  • 2.9 头插
  • 2.10 头删
  • 2.11 查找（按位查找）
  • 2.12 查找（按值查找）
  • 2.13 修改 pos 位置的值
• 3 顺序表的特点
• • 先来谈优点：
  • 再来谈优点：
• //后记

前言

💘 Lesson02 主要讲解数据结构中的 - 顺序表，以及顺序表的C语言实现。

💘 本篇文章没有伪代码，帮助大家在理解顺序表的前提下，自己动手用C语言实现动态增长的顺序表

1 什么是顺序表

1.1 基本概念

🏃 线性表的顺序存储又称为顺序表
🏃 通俗而言，就是用一组地址连续的存储单元，依次来存储线性表中的数据元素
🏃 再简单来说，极其类似我们C语言中定义的数组

但是，区别于数组的是：

🏃 在数组中，我们的数据可以有间隔
🏃 比如在 int arr [10] 这个数组中，我们可以通过访问下标将1和2存在数组中的任意位置
🏃 但是在顺序表中，我们必须将元素依次存放，也就是在逻辑上相邻的元素，在物理位置上（存储单元内）也相邻，不可随意存放

1.2 顺序表的类型

🏃 由于我们可以用一维数组模拟实现顺序表
🏃 而一维数组的空间分配可以直接静态分配定长的数组（比如直接 inta[100]，就是静态分配100个int型的空间）；
🏃 也可以动态分配空间（比如 int* a = (int*)malloc(sizeof(int)*100 ,就是动态分配100个空间）；
因此顺序表也可以分为两类：

💘第一类：静态数据表

#define MAX_SIZE 100 //定义静态数组的最大容量typedef int SLDataType; //定义顺序表中数据的类型//定义一个静态顺序表typedef struct SeqList{SLDataType a[MAX_SIZE]; //固定大小的数组int size; //顺序表中有效数据的个数,方便我们寻找最后一个元素的位置}SeqList;

🏃 数组的大小和空间固定，一旦空间占满，新的数据就是溢出，程序就会崩溃
🏃 而且如果静态开辟的数组很大，但是需要存储的数据很少的话，会造成空间的浪费
🏃 因此，静态顺序表有其局限性

💘 第二类：动态顺序表

typedef int SLDataType; //定义顺序表中数据的类型//定义一个动态顺序表typedef struct SeqList{SLDataType* a; //定义一个指向动态数组的指针int size; //顺序表中有效元素的个数int capacity; //顺序表此时的容量，方便扩容}SeqList;

🏃 存储的空间是在程序执行过程中动态分配的
🏃 一旦分配的空间用满，我们可以另外开辟一块更大的空间（比如用 realloc 函数），用来替换之前的空间
🏃 这样带来的好处就是我们需要存储的数据就不会出现溢出，空间利用率较高

二、顺序表上的基本操作实现（c语言版）

💘 ps：由于静态顺序表局限性很大，我们这里用C语言实现一个动态顺序表~

2.1 初始化

🏃 在初始化接口中，会给顺序表动态分配一个数组，并且将 size 和 capacity 的值初始化

#include //顺序表初始化//定义默认容量#define DEFAULT_CAPACITY 10void SeqListInit(SeqList* ps)//这里切记要传创建的顺序表的地址{assert(ps); //断言一下，如果是空指针，无法解引用操作ps->capacity = DEFAULT_CAPACITY; //容量初始化为默认容量ps->size = 0; //有效数据为 0//动态申请一个大小为capacity的数组ps->a = (int*)malloc(sizeof(SLDataType) * ps->capacity);if (ps->a == NULL) //使用 malloc 函数一定要注意检查申请失败的情况{perror("SeqList::malloc");}}

2.2 销毁

🏃 将顺序表清空
🏃 malloc 申请的空间还给系统，capacity 与 size 的值清 0

//顺序表的销毁void SeqListDestroy(SeqList* ps){assert(ps);free(ps->a); //释放申请的空间ps->a = NULL; ps->capacity = 0;ps->size = 0;}

2.3 打印

🏃 类似于数组元素的打印，也就是遍历整个顺序表，依次将元素打印出来

#include //顺序表的打印void SeqListPrint(SeqList* ps){assert(ps);int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");}

2.4 增容

🏃 在插入操作中要重复判断顺序表是否已满，所以这里单独定义一个接口函数

//检查是否已满void CheckSeqListFull(SeqList* ps){//顺序表已满的条件if (ps->capacity == ps->size){ //每次扩容选择扩大为原来的二倍SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2);if (tmp == NULL){perror("CheckFull::realloc");}ps->a = tmp;ps->capacity *= 2;//切记一定要修改扩容后的容量}}

2.5 尾插

🏃 尾插 - 在顺序表的最后面插入一个元素
🏃 插入前一定要注意顺序表是否已满，不然会造成越界访问
🏃 并且在插入后，记得修改顺序表的 size

//顺序表的尾插void SeqListPushBack(SeqList* ps, SLDataType x){assert(ps);CheckSeqListFull(ps); //一定要检查是否已满ps->a[ps->size++] = x; //插入数据后记得size++}

2.6 尾删

🏃 尾删 - 删除顺序表的最后一个元素
🏃 在这里我们不在物理上删除这个元素，而是在逻辑上将其删除即可
🏃 也就是只需修改顺序表中有效元素的个数即可

//顺序表的尾删void SeqListPopBack(SeqList* ps){assert(ps);//如果没有元素，不必删除if (ps->size == 0)return;//逻辑上删除，物理上这个元素还是存在的,但是我们已经访问不到它了ps->size--;}

2.7 在 pos 位置插入元素

🏃 思路：将 pos 位置之后的元素从后往前以此向后移动一位
🏃 再将待插入元素放入 pos 位置上即可

//在 pos 位置上插入元素xvoid SeqListInsert(SeqList* ps, int pos ,SLDataType x){assert(ps);assert(pos >= 0); //检查插入位置的合法性CheckSeqListFull(ps); //检查顺序表是否已满int i = 0;//从后往前，依次后移一位for (i = ps->size - 1; i >= pos; i--){ps->a[i + 1] = ps->a[i];}//插入xps->a[pos] = x;ps->size++;}

2.8 删除 pos 位置的元素

🏃 思路：将 pos 位置之后的元素从前往后依次向前移动一位，覆盖之前的元素

//删除顺序表 pos 位置的元素void SeqListErase(SeqList* ps, int pos){assert(ps);assert(pos >= 0);int i = 0;// 将pos ~ size-1位置的元素依次前移一位for (i = pos; i < ps->size - 1; i++)//这里注意i的最大值不能超过size-1，否则i+1就会越界{ps->a[i] = ps->a[i + 1];}//删除元素记得size--ps->size--;}

2.9 头插

🏃 这里可以复用 2.7 在顺序表的 pos 位置插入元素 的代码
🏃 即在 0 位置插入元素

//顺序表的头插void SeqListPushFront(SeqList* ps, SLDataType x){//复用代码-在0位置插入元素xSeqListInsert(ps, 0, x);}

2.10 头删

🏃 这里依旧可以复用 2.8 删除顺序表 pos 位置的元素 的代码
🏃 即删除 0 位置的元素

//顺序表头删void SeqListPopFront(SeqList* ps){//复用代码-删除0位置的元素SeqListErase(ps, 0);}

2.11 查找（按位查找）

🏃 按位查找很简单，直接访问下标即可

//顺序表的查找（按位查找）SLDataType SeqListFindByPos(SeqList* ps, int pos){assert(ps);//检查位置的合法性assert(pos >= 0 && pos < ps->size);return ps->a[pos];}

2.12 查找（按值查找）

🏃 只需遍历整个顺序表，找到此值返回下标
🏃 找不到就返回 -1

//顺序表的查找（按值查找）int SeqListFindByVal(SeqList* ps, SLDataType x){assert(ps);int i = 0;for (i = 0; i < ps->size; i++){if (ps->a[i] == x)return i;}return -1;}

2.13 修改 pos 位置的值

🏃 判断位置合法性，然后修改即可

//修改 pos 位置的值void SeqListModify(SeqList* ps, int pos, SLDataType x){assert(ps);assert(pos >= 0 && pos < ps->size);ps->a[pos] = x;}

3 顺序表的特点

先来谈优点：

🏃 支持随机访问，即通过下标直接访问 pos 位置的元素，时间复杂度为o（1）
🏃 存储密度高，每个结点只存储数据

再来谈优点：

🏃 在数据中间插入或删除元素时，需要移动大量数据
🏃 数据量过大时，增容操作也会消耗一定的性能

💘 综上就是关于顺序表最核心的知识，对您有帮助的老铁，还望关注、点赞、收藏一键三连哦~~~

//后记

🏃 以后每周会更新一到两篇学习数据结构的笔记，用来记录自己的学习历程，复习巩固所学的知识。
🏃 文中概念或者代码有任何错误的地方，希望大佬们在评论区指出，本人会虚心接受并且改正。

松山湖人才网