当前位置： 首页 > news >正文

【数据结构】顺序表(附源码)

news 2025/5/19 10:07:34

数据结构之顺序表

  • 1、线性表
  • 2、顺序表
    • 2.1 概念与结构
    • 2.2 顺序表的分类
  • 3、动态顺序表
    • 3.1 结构
    • 3.2 初始化
    • 3.3 容量检查
    • 3.4 尾部插入数据
    • 3.5 删除尾部数据
    • 3.6 头部插入数据
    • 3.7 头部删除数据
    • 3.8 任意位置pos插入数据
    • 3.9 任意位置pos删除数据
    • 3.10 查找
  • 4、动态顺序表实现的源码

1、线性表

首先，在讲解顺序表之前呢，我们首先了解一下线性表，我们本期博客要讲解的顺序表就属于线性表。
定义：线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就是连续的⼀条直线。但是在物理结构上并不⼀定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。

2、顺序表

2.1 概念与结构

概念：顺序表是用一段物理地址连续的储存单元依次存储数据元素的线性结构，一般情况下采用数组存储。
结构：
在这里插入图片描述

2.2 顺序表的分类

既然顺序表一般是用数组来实现的，那我们知道数组分为在初始化时长度固定的数组，和用动态内存开辟出的长度可变的数组两种类型，顺序表也自然而然存在两种。
顺序表又分为静态顺序表和动态顺序表。

静态顺序表就是使用定长数组储存元素的顺序表，它有很明显的缺陷，就是空间给少了不够用，空间给多了造成空间浪费。

所以我们本篇博客着重讲解动态顺序表！

3、动态顺序表

动态顺序表的开辟首先要定义结构体。
上面提到动态顺序表是用动态开辟的数组来储存数据的，那为什么我们不直接动态开辟一个数组来储存数据，而要先定义一个结构体呢？我们实现顺序表不只是拿顺序表动态开辟一个空间，我们还要用顺序表进行一系列操作，例如插入数据、删除数据、查找数据、修改数据等等，我们需要知道储存的元素个数size，还要知道顺序表目前的空间大小capacity，才能进行这些操作。它们之间的联系如下图：
在这里插入图片描述

3.1 结构

//定义动态顺序表的结构
typedef int SLDataType;//取别名
typedef struct SeqList
{SLDataType* arr;int size;      //有效数据个数int capacity;  //空间容量
}SL;

上面的代码部分就是我封装的顺序表，我们可以看到在结构体中定义了一个未初始化的数组、未初始化的两个变量。
在代码中我还把 int 命名成了 SLDataType ，为什么要这样命名呢？
这是因为数组类型有很多种类，int 、char 等等，当我们有这样一个取别名的过程，到时候要修改时就可以将int改成你想要的类型，实现一键修改，省去了很多不必要的麻烦。

3.2 初始化

void SLInit(SL* ps)//初始化
{assert(ps);//判断是不是NULLps->arr = (SLDataType*)malloc(4 * sizeof(SLDataType));if (ps->arr == NULL){perror("malloc");//报出错误信息return 1;}ps->size = 0;ps->capacity = 4;
}

注意：定义完成这个函数后，形参用指针接收，所以在传参时要传结构体类型的地址，不能传递实参。

3.3 容量检查

我们在向数组增添数据或者插入数据的时候，总需要检查空间容量capacity是否足够，如果不够的话，需要进行扩容，顺序表也是一样。

void SLCheckCapacity(SL* ps)//检查容量
{assert(ps);//判断是不是NULLif (ps->size == ps->capacity){SLDataType newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));if (tmp == NULL){perror("realloc fail");return 1;}ps->arr = tmp;ps->capacity *= 2;}
}

之后的代码在检查容量的时候，我们就直接可以使用函数SLCheckCapacity。
realloc函数是扩容函数，有关它的用法如果忘了的兄弟可以看看我之前发布的博客：【C语言】动态内存管理

3.4 尾部插入数据

void SLPushBack(SL* ps, SLDataType x)//尾插
{assert(ps);SLCheckCapacity(ps);//进行容量检查ps->arr[ps->size] = x;ps->size++;
}

我们这里就直接使用到了SLCheckCapacity函数，检查容量是不是满了，size是数据个数，同时也表示顺序表最后一个元素后一个位置的下标，成功插入后，有效数据个数size要加1。
示例：

#include "SeqList.h"void test1()
{SL pa;SLInit(&pa);//初始化SLPushBack(&pa, 1);//尾部插入数据SLPushBack(&pa, 2);SLPushBack(&pa, 3);SLPushBack(&pa, 4);SLPushBack(&pa, 5);SLPrint(&pa);
}int main()
{test1();return 0;
}

我刚才写的函数都在SeqList.c中，在博客最后我会公布源码。其中SLPrint是设计的打印函数，这里就不再展示，源码在博客末尾。
运行结果：
在这里插入图片描述

3.5 删除尾部数据

void SLPopBack(SL* ps)//尾删
{assert(ps->size);//判断数据个数是否为0ps->size--;
}

在删除尾部数据的时候，我们只需要将存储的元素个数size减1即可，当再次在尾部增添数据时，新数据会把原来的数据覆盖掉，不影响顺序表的操作。
示例：

#include "SeqList.h"void test1()
{SL pa;SLInit(&pa);//初始化SLPushBack(&pa, 1);//尾部插入数据SLPushBack(&pa, 2);SLPushBack(&pa, 3);SLPushBack(&pa, 4);SLPushBack(&pa, 5);SLPrint(&pa);SLPopBack(&pa);SLPopBack(&pa);SLPopBack(&pa);SLPrint(&pa);
}int main()
{test1();return 0;
}

运行结果：
在这里插入图片描述

3.6 头部插入数据

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++;
}

头插先检查容量，然后，将原顺序表中的元素依次向后挪动一位，最后进行插入，再将储存的数据容量size加1即可。
示例：

#include "SeqList.h"void test1()
{SL pa;SLInit(&pa);//初始化SLPushBack(&pa, 1);//尾部插入数据SLPushBack(&pa, 2);SLPushBack(&pa, 3);SLPrint(&pa);SLPushFront(&pa, -1);SLPushFront(&pa, -2);SLPrint(&pa);
}int main()
{test1();return 0;
}

运行结果：
在这里插入图片描述

3.7 头部删除数据

void SLPopFrant(SL* ps)//头删
{assert(ps && ps->size);for (int i = 0;i < ps->size - 1;i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}

头删只需要判断一下储存的数据个数size大于0，之后从第二个元素开始把后面的元素都往前移，储存的数据个数size减一即可。
示例：

#include "SeqList.h"void test1()
{SL pa;SLInit(&pa);//初始化SLPushBack(&pa, 1);//尾部插入数据SLPushBack(&pa, 2);SLPushBack(&pa, 3);SLPrint(&pa);SLPopFrant(&pa);SLPopFrant(&pa);SLPrint(&pa);
}int main()
{test1();return 0;
}

运行结果：
在这里插入图片描述

3.8 任意位置pos插入数据

void SLInsert(SL* ps, int pos, SLDataType x)//在pos位置插入
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);for (int i = ps->size;i > pos;i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}

只需要判断一下，无误后将pos位置即之后的元素整体后移一位，最后size加1即可。
示例：

#include "SeqList.h"void test1()
{SL pa;SLInit(&pa);//初始化SLPushBack(&pa, 1);//尾部插入数据SLPushBack(&pa, 2);SLPushBack(&pa, 3);SLPrint(&pa);SLInsert(&pa, 2, 15);SLInsert(&pa, 2, 35);SLPrint(&pa);
}int main()
{test1();return 0;
}

运行结果：
在这里插入图片描述

3.9 任意位置pos删除数据

void SLErase(SL* ps, int pos)//删除pos位置数据
{assert(ps);assert(pos >= 0 && pos <= ps->size);for (int i = pos;i < ps->size - 1;i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}

判断无误后，将pos+1位置即之后元素前移，最后size减一即可。
示例：

#include "SeqList.h"void test1()
{SL pa;SLInit(&pa);//初始化SLPushBack(&pa, 1);//尾部插入数据SLPushBack(&pa, 2);SLPushBack(&pa, 3);SLPrint(&pa);SLInsert(&pa, 2, 15);SLInsert(&pa, 2, 35);SLPrint(&pa);SLErase(&pa, 1);SLErase(&pa, 2);SLPrint(&pa);
}int main()
{test1();return 0;
}

运行结果：
在这里插入图片描述

3.10 查找

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

示例：

#include "SeqList.h"void test1()
{SL pa;SLInit(&pa);//初始化SLPushBack(&pa, 1);//尾部插入数据SLPushBack(&pa, 2);SLPushBack(&pa, 3);SLPrint(&pa);SLInsert(&pa, 2, 15);SLInsert(&pa, 2, 35);SLPrint(&pa);SLErase(&pa, 1);SLErase(&pa, 2);SLPrint(&pa);int h = SLFind(&pa, 15);if (h != -1){printf("找到了\n");}else printf("没找到\n");
}int main()
{test1();return 0;
}

运行结果：
在这里插入图片描述

4、动态顺序表实现的源码

SeqList.h：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//定义动态顺序表的结构
typedef int SLDataType;//取别名
typedef struct SeqList
{SLDataType* arr;int size;      //有效数据个数int capacity;  //空间容量
}SL;//初始化
void SLInit(SL* ps);//检查空间容量
void SLCheckCapacity(SL* ps);//打印
void SLPrint(SL* ps);//尾插
void SLPushBack(SL* ps, SLDataType x);//尾删
void SLPopBack(SL* ps);//头插
void SLPushFront(SL* ps, SLDataType x);//头删
void SLPopFrant(SL* ps);//在pos位置插入
void SLInsert(SL* ps, int pos, SLDataType x);//删除pos位置的数据
void SLErase(SL* ps, int pos);//查找
int SLFind(SL* ps, SLDataType x);

SeqList.c：

#include "SeqList.h"void SLInit(SL* ps)//初始化
{ps->arr = NULL;ps->size = 0;ps->capacity = 0;
}void SLPrint(SL* ps)
{assert(ps);int i = 0;for (i = 0;i < ps->size;i++){printf("%d ", ps->arr[i]);}printf("\n");
}void SLCheckCapacity(SL* ps)//检查容量
{assert(ps);//判断是不是NULLif (ps->size == ps->capacity){SLDataType newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));if (tmp == NULL){perror("realloc fail");return 1;}ps->arr = tmp;ps->capacity *= 2;}
}void SLPushBack(SL* ps, SLDataType x)//尾插
{assert(ps);SLCheckCapacity(ps);//进行容量检查ps->arr[ps->size] = x;ps->size++;
}void SLPopBack(SL* ps)//尾删
{assert(ps->size);//判断数据个数是否为0ps->size--;
}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 SLPopFrant(SL* ps)//头删
{assert(ps && ps->size);for (int i = 0;i < ps->size - 1;i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}void SLInsert(SL* ps, int pos, SLDataType x)//在pos位置插入
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);for (int i = ps->size;i > pos;i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}void SLErase(SL* ps, int pos)//删除pos位置数据
{assert(ps);assert(pos >= 0 && pos <= ps->size);for (int i = pos;i < ps->size - 1;i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}int SLFind(SL* ps, SLDataType x)//查找
{assert(ps);for (int i = 0;i < ps->size;i++){if (ps->arr[i] == x){return i;}}return -1;
}

test.c:

#include "SeqList.h"void test1()
{SL pa;SLInit(&pa);//初始化SLPushBack(&pa, 1);//尾部插入数据SLPushBack(&pa, 2);SLPushBack(&pa, 3);SLPrint(&pa);SLInsert(&pa, 2, 15);SLInsert(&pa, 2, 35);SLPrint(&pa);SLErase(&pa, 1);SLErase(&pa, 2);SLPrint(&pa);int h = SLFind(&pa, 15);if (h != -1){printf("找到了\n");}else printf("没找到\n");
}int main()
{test1();return 0;
}

总结：
以上就是本期博客分享的全部内容啦！技术的探索永无止境。
道阻且长，行则将至！后续我会给大家带来更多优质博客内容，欢迎关注我的CSDN账号，我们一同成长！
(～￣▽￣)～


http://www.mrgr.cn/news/94984.html

相关文章：

  • 《大语言模型》学习笔记（三）
  • 生成PDF文件：从html2canvas和jsPdf渲染到Puppeteer矢量图
  • SSL/TLS 和 SSH 区别
  • 2025最新！人工智能领域大模型学习路径、大模型使用、AI工作流学习路径
  • SpringCloud 学习笔记3（OpenFeign）
  • 【Netty】消息分发处理方式
  • 【数据库】掌握MySQL事务与锁机制-数据一致性的关键
  • MySQL ：参数修改
  • 鸿蒙NEXT开发问题大全（不断更新中.....）
  • C++继承 ---- 继承是面向对象三大特性之一【好处：可以减少重复的代码】
  • Python教学:lambda表达式的应用-由DeepSeek产生
  • Direct2D 极速教程(3) —— 画动态淳平
  • LeetCode[42] 接雨水
  • Opencv之计算机视觉一
  • 《深度学习》—— 模型部署
  • 导出的使用
  • PHP转GO Go语言环境搭建（Day1） 常见问题及解决方案指南
  • 8. Merge Sorted Array
  • 【数据结构】LinkedList与链表(1) + 经典面试OJ题解析 —— 有码有图有真相
  • Mysql:关于命名