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

数据结构-顺序表【简单易懂】

news 2026/5/12 4:11:03

一、顺序表概述

顺序表是我们学完C语言后，接触的第一种数据结构，其逻辑上、物理上（底层）都是线性结构，其底层逻辑是数组（数组地址连续，所以是线性的），但对数组加工包装，更加高效的实现数据管理。其主要功能是：数据增加、数据删除、数据修改、数据查找（增删改查，以后的各种类型数据结构都主要围绕此四大方面展开）。总体功能如下：

//定义数据类型，方便类型替换 typedef int SLDatatype; //定义动态顺序表结构 typedef struct SeqList { SLDatatype* a; int capicity;//空间容量 int size;//有效数据个数 }SL; //初始化 void SLInit(SL* ps); //销毁 void SLDestroy(SL* ps); //打印数据 void SLPrint(SL* ps); //查找数据 void SLFind(SL* ps, SLDatatype x); //插入数据 void SLPushBack(SL* ps,SLDatatype x);//后插 void SLPushFront(SL* ps,SLDatatype x);//前插 void SLInsert(SL* ps, SLDatatype x, int pos);//指定位置插入元素 //删除数据 void SLPopBack(SL* ps);//后删 void SLPopFront(SL* ps);//前删 void SLErase(SL* ps, int pos);//指定位置删除元素 //修改数据 void SLModif(SL* ps, int pos, SLDatatype x);

二、定义顺序表结构

顺序表结构主要由三部分组成：数据类型的指针、空间容量、有效数据；

（1）数据类型的指针：

这里不直接定义数据的类型为int、char是为了以后数据类型的修改方便。所以我们利用typedef来定义数据类型，如：typedef int SLDataType,如果以后数据类型需要需改只需要将int改为其他数据类型，一了百了。注意：这里是SLDataType *a,而不是SL*a,a是各种数据类型的指针，用来存储数据，而不是结构体指针，SL *a就类似于链表了。

（2）空间容量

我们创建的顺序表是动态的（指针），指针指向的地址有一个空间容量，在这里我们写为：capicity,容量肯定为整数，所以是int类型。之后的插入操作需要考虑空间是否充足，如果容量不够的话，需要扩容操作，后面会讲。

（3）有效数据

这里的有效数据个数size是最后一个数据的位置（类似于int a[n]中的n，取不到），是为了之后查找数据、指定位置插入数据限定一个范围。

总代码如下：

//定义数据类型，方便类型替换 typedef int SLDatatype; //定义动态顺序表结构 typedef struct SeqList { SLDatatype* a; int capicity;//空间容量 int size;//有效数据个数 }SL;

三、顺序表初始化

刚才已经定义了顺序表结构，其结构体中包括数据类型指针、空间容量、有效数据，我们需要进行初始化操作，避免产生野指针，主要就就是将指针指向NULL，空间容量、有效数据赋0；代码如下：

//初始化 void SLInit(SL* ps) { ps->a = NULL; ps->capicity = 0; ps->size = 0; }

四、顺序表打印

这里主要要强调一下传过来的指针不能为空，要不然ps->a(此时ps=NULL)操纵是不合法的，所以需要添加assert函数（头文件 assert.h不要忘记引用），当指针为空时断言报错提醒。其代码如下：

//打印数据 void SLPrint(SL* ps) { assert(ps); for (int i = 0; i < ps->size; i++) printf("%d ", ps->a[i]); printf("\n"); }

五、 数据查找

数据查找主要依靠一个循环，将数据都遍历一遍，这里可以考虑引入一个变量j，记录所要查找的数据位置（所要查找的数据可能不止一个）。代码如下：

//查找数据 void SLFind(SL* ps, SLDatatype x) { int j = 1; int p = 1; for (int i = 0; i < ps->size; i++) { if (ps->a[i] == x) { printf("查找的数据第%d处位置为：第%d个数据", j, i + 1); printf("\n"); j++; p = 0; } } if (p == 1) printf("没有此数据！"); }

将printf中的i+1写为j也是一样的。

问：printf里面也有i+1，for循环里有i++，那i一次循环不是+2吗，有的数据是否没有考虑到？

答：其实printf里面的i+1只在printf中有效，当执行完i+1后便销毁了，i的值在printf执行完毕后值不会改变，自己可以测试一下。

六、插入数据

在插入数据之前，我们需要考虑原来的空间是否足够，如果原来空间满了，是插入不了的（类似int a[n] 已经存了n个数据了），这时候需要我们进行扩容操纵，我们将此操作封装SLCheckCapacit函数中，先看代码：

//插入操作前判断空间是否充足 void SLCheckCapacity(SL* ps) { if (ps->capicity == ps->size) { int NewCapicity = ps->capicity == 0 ? 4 : 2 * ps->capicity; SLDatatype* tmp = (SLDatatype*)realloc(ps->a, NewCapicity * sizeof(SLDatatype)); if (tmp == NULL) { perror("realloc fail!"); exit(1); } ps->a = tmp; ps->capicity = NewCapicity; }

利用ps->capicity==ps->size这个条件即可判断原来的空间是否满了，如果满了，需要重新开辟一块空间将此空间地址传给a指针。我们计算新空间的大小一般为原来空间的2倍，如果太大，会造成空间浪费，太小的话插入数据如果较多需要多次进行扩容操作，这会使计算机运行效率变低、性能变低等，所以一般取2倍。注意：原来空间没说不可以为0，所以一定要提前判断！代码中int NewCapicity = ps->capicity == 0 ? 4 : 2 * ps->capicity;就是此作用。开辟一块新地址我们这里用realloc。问：为什么不用malloc函数,而用realloc函数，二者有什么区别?

答：简单来讲：malloc 只负责分配指定字节数的内存块，不对其进行初始化；realloc 用于重新分配内存块的大小，并尝试保留原始内存块中的数据；我们这里开辟新的空间需要保留原有地址的数据，所以用realloc。

1、尾插操作

尾插需要考虑空间是否足够，所以我们需要调用一下SLCheckCapacity函数；既然是插入操作，那原指针的地址肯定不能为空，需要加入assert断言（后面的头插，指定位置插入都需要断言）。代码如下：

//尾插 void SLPushBack(SL* ps, SLDatatype x) { assert(ps); //判断空间是否足够 SLCheckCapacity(ps); ps->a[ps->size++] = x; }

别忘记size++,有效数据需要＋1。问：ps->a[ps->size++]=x中执行顺序？

答：由于size++是后置++，所以先执行语句后++，即ps->a[ps->size]=x执行完毕后，ps->size++。

2、头插操作

头插操作需要一个while循环，将前面之前所有的数据都往后挪一个，最后别忘记ps->size++。代码如下：

//头插 void SLPushFront(SL* ps, SLDatatype x) { assert(ps); //判断空间是否足够 SLCheckCapacity(ps); int i = ps->size; while (i> 0) { ps->a[i] = ps->a[i-1]; i--; } ps->a[0] = x; ps->size++; }

3、指定位置插入数据

首先需要考虑原来的顺序表不能为空，指定数据的位置不能为空，所以引用 assert(ps);
assert(pos >= 0 && pos <= ps->size);往指定位置插入数据需要将指定位置之后的数据全部往后挪一个，这里也需要一个循环，注意循环结束的条件为：i>pos（int i = ps->size;）。代码如下：

void SLInsert(SL* ps, SLDatatype x, int pos) { assert(ps); assert(pos >= 0 && pos <= ps->size); SLCheckCapacity(ps); int i = ps->size; while ( i>pos) { ps->a[i ] = ps->a[i-1]; i--; } ps->a[pos] = x; ps->size++; }

ps->size++别忘记！

七、删除数据

所有删除数据都要assert判断，删除数据，原来数不能为空。以及进行ps->size--,不能忘记。

1、数据尾删

尾删最简单，将ps->size--即可。代码如下：

/尾删 void SLPopBack(SL* ps) { assert(ps); assert(ps->size); ps->size--; }

2、数据头删

头删操作将所有数据从后往前覆盖即可，代码如下：

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

问：为什么这里需要考虑assert(ps->size)?

答：ps->size为0了，哪里有数据删。

3、指定位置删除数据

原理简单，需要一个循环，先找到指定位置，将指定位置之后的所有数据向前覆盖即可。代码如下：

//删除指定位置元素 void SLErase(SL* ps, int pos) { assert(ps); assert(pos >= 0 && pos <= ps->size); SLCheckCapacity(ps); for (int i = pos ; i < ps->size; i++) { ps->a[i] = ps->a[i + 1]; } ps->size--; }

八、修改数据

一种是修改指定位置的数据，一种是修改所有等于此值的数据，其代码如下：

//修改数据 void SLModif(SL* ps, int pos,SLDatatype x) { int y = 0; printf("1、将某一数据全部修改为新数据；\n"); printf("*****2、修改指定位置数据*******\n"); printf("请输入你的操作："); int input=scanf("%d", &y); int m = 0; if(input==1) { SLPrint(ps); printf("请输入你要修改的数字:"); scanf("%d", &m); for (int i = 0; i < ps->size; i++) { if (ps->a[i] == m) ps->a[i] = x; } } else if (input == 2) { if (pos >= 0 && pos < ps->size) ps->a[pos] = x; } else printf("输入无效，请重新输入："); }

九、销毁操作

顺序表的实现指针指向了新的地址，在完成操作后，需要将这些地址销毁，以免内存泄漏等问题，将指针指向NULL。代码如下：

//销毁 void SLDestroy(SL* ps) { if (ps->a) { free(ps->a); } ps->capicity = ps->size = 0; ps->a = NULL; }

十、总代码

将代码分装到三个文件，一个头文件SeqList.h，实现操纵的文件SeqList.c，测试文件test.c。

头文件SeqList.h主要定义顺序表结构和各种操作函数的声明。

实现操纵的文件SeqList.c主要敲各种代码，实现各种功能。

测试文件test.c对SeqList.c中各种函数进行测试。

1、SeqList.h

代码如下：

#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> //定义指针类型，方便类型替换 typedef int SLDatatype; //定义动态顺序表结构 typedef struct SeqList { SLDatatype* a; int capicity;//空间容量 int size;//有效数据个数 }SL; //初始化 void SLInit(SL* ps); //销毁 void SLDestroy(SL* ps); //打印数据 void SLPrint(SL* ps); //查找数据 void SLFind(SL* ps, SLDatatype x); //插入数据 void SLPushBack(SL* ps,SLDatatype x);//后插 void SLPushFront(SL* ps,SLDatatype x);//前插 void SLInsert(SL* ps, SLDatatype x, int pos);//指定位置插入元素 //删除数据 void SLPopBack(SL* ps);//后删 void SLPopFront(SL* ps);//前删 void SLErase(SL* ps, int pos);//指定位置删除元素 //修改数据 void SLModif(SL* ps, int pos, SLDatatype x);

2、SeqList.c

代码如下：

#define _CRT_SECURE_NO_WARNINGS 1 #include"SeqList.h" //初始化 void SLInit(SL* ps) { ps->a = NULL; ps->capicity = 0; ps->size = 0; } //销毁 void SLDestroy(SL* ps) { if (ps->a) { free(ps->a); } ps->capicity = ps->size = 0; ps->a = NULL; } //打印数据 void SLPrint(SL* ps) { assert(ps); for (int i = 0; i < ps->size; i++) printf("%d ", ps->a[i]); printf("\n"); } //查找数据 void SLFind(SL* ps, SLDatatype x) { int j = 1; int p = 1; for (int i = 0; i < ps->size; i++) { if (ps->a[i] == x) { printf("查找的数据第%d处位置为：第%d个数据", j, i + 1); printf("\n"); j++; p = 0; } } if (p == 1) printf("没有此数据！"); } //插入操作前判断空间是否充足 void SLCheckCapacity(SL* ps) { if (ps->capicity == ps->size) { int NewCapicity = ps->capicity == 0 ? 4 : 2 * ps->capicity; SLDatatype* tmp = (SLDatatype*)realloc(ps->a, NewCapicity * sizeof(SLDatatype)); if (tmp == NULL) { perror("realloc fail!"); exit(1); } ps->a = tmp; ps->capicity = NewCapicity; } } //插入数据 //尾插 void SLPushBack(SL* ps, SLDatatype x) { assert(ps); //判断空间是否足够 SLCheckCapacity(ps); ps->a[ps->size++] = x; } //头插 void SLPushFront(SL* ps, SLDatatype x) { assert(ps); //判断空间是否足够 SLCheckCapacity(ps); int i = ps->size; while (i> 0) { ps->a[i] = ps->a[i-1]; i--; } ps->a[0] = x; ps->size++; } //指定位置插入数据 void SLInsert(SL* ps, SLDatatype x, int pos) { assert(ps); assert(pos >= 0 && pos <= ps->size); SLCheckCapacity(ps); int i = ps->size; while ( i>pos) { ps->a[i ] = ps->a[i-1]; i--; } ps->a[pos] = 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; i++) { ps->a[i] = ps->a[i + 1]; } ps->size--; } //删除指定位置元素 void SLErase(SL* ps, int pos) { assert(ps); assert(pos >= 0 && pos <= ps->size); SLCheckCapacity(ps); for (int i = pos ; i < ps->size; i++) { ps->a[i] = ps->a[i + 1]; } ps->size--; } //修改数据 void SLModif(SL* ps, int pos,SLDatatype x) { int y = 0; printf("1、将某一数据全部修改为新数据；\n"); printf("*****2、修改指定位置数据*******\n"); printf("请输入你的操作："); int input=scanf("%d", &y); int m = 0; if(input==1) { SLPrint(ps); printf("请输入你要修改的数字:"); scanf("%d", &m); for (int i = 0; i < ps->size; i++) { if (ps->a[i] == m) ps->a[i] = x; } } else if (input == 2) { if (pos >= 0 && pos < ps->size) ps->a[pos] = x; } else printf("输入无效，请重新输入："); }

3、test.c

代码如下：

#define _CRT_SECURE_NO_WARNINGS 1 #include "SeqList.h" void SLtext1() { SL s; SLInit(&s); //尾插测试 SLPushBack(&s, 1); SLPushBack(&s, 2); SLPushBack(&s, 3); SLPushBack(&s, 4); SLPushBack(&s, 5); SLPushBack(&s, 5); SLPushBack(&s, 6);//1 2 3 4 5 6 // //SLPushBack(NULL, 6);//报错 SLPrint(&s); //头插测试 //SLPushFront(&s, 1); //SLPushFront(&s, 2); //SLPushFront(&s, 3); //SLPushFront(&s, 4); //SLPrint(&s); //4 3 2 1 //指定位置插入 //SLInsert(&s, 11, 0); //SLPrint(&s); //SLInsert(&s, 22, s.size); //SLPrint(&s); //SLInsert(&s, 33, 1); //SLPrint(&s); //查找数据 SLFind(&s, 5); //修改数据 SLModif(&s, 1, 5); SLPrint(&s); //尾删测试 SLPopBack(&s); SLPrint(&s); //头删测试 SLPopFront(&s); SLPrint(&s); //指定位置删除数据 SLErase(&s, 2); SLPrint(&s); SLDestroy(&s); } int main() { SLtext1(); return 0; }

有问题多多指教。

http://www.jsqmd.com/news/468426/

相关文章：

  • 蓝桥杯 回文字符串
  • 基于 libhv+Brigand 实现 HTTP 接口批量自动化注册
  • 1. 冒泡排序程序
  • Java（面向对象篇）
  • 唯品花购物额度提现与个人征信：合规使用、维护信用 - 容易提小溪
  • Elasticsearch 8.x 在 java 中的使用情况
  • 量化策略兼容性设计
  • 从安装到部署：SmartFormat在.NET项目中的完整集成指南
  • 蓝桥杯 跑步计划
  • 论文写作必备！2026年超实用AI工具排行榜，学生党赶紧私藏！ - 资讯焦点
  • 半同步复制
  • 蓝桥杯 残缺的数字
  • 苍穹外卖（数据统计-图形报表）
  • 苍穹外卖（数据统计–Excel报表）
  • 蓝桥杯 整数变换
  • OpenTelemetry Operator避坑指南：从TLS证书配置到Sidecar自动注入的全流程解析
  • 算法训练-模拟
  • Java（API与算法篇）
  • 量化交易策略的运行
  • 蓝桥杯 定时任务
  • 医疗影像分割实战：从原理到代码，全面解析surface-distance评估指标
  • 蓝桥杯 火车运输
  • ArcGIS实战：从XYZ坐标点到等高线的全流程解析
  • OpenVINO模型量化实战：用NNCF搞定PaddleOCR文本检测模型（附完整代码）
  • 为什么消息队列不像数据库那样可以配置读写分离？
  • Halcon 3D视觉实战：从点云预处理到精准定位的完整流程解析
  • 蓝桥杯 最大区间
  • 大端小端检测实战：5分钟用联合体写出CPU字节序测试工具（附结构体对比）
  • 量化交易系统技术方案设计
  • pr 3dmax ae au 达芬奇等各类安装包需要的自提，