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

【数据结构】顺序表

ds 2025/5/5 12:59:13

本文是小编巩固自身而作，如有错误，欢迎指出！

1.线性表

线性表（linearlist）是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中⼴泛使⽤的 数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性 表在物理上存储时，通常以数组和链式结构的形式存储。

2.顺序表

顺序表是什么？

顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采⽤数组 存储。

 说通俗一点就是顺序表是对数组的封装，在数组的基础上，增加了增删数据，查找修改顺序的功能。

2.1顺序表的分类

2.11静态顺序表

静态顺序表即一个定长的数组，不能对其进行大小的改变

我们用下面代码声明一个简单的静态顺序表

typedef int sldatatype;//方面我们改变储存的数据类型
#define N 7
typedef struct seqlist
{
sldatatype a[N];//定长数组
int size;//有效数据个数
}

静态数据表的缺陷就是：空间给少了会不够用，给多了又会造成空间浪费

2.12动态顺序表

而动态顺序表即可以进行增删，扩容等等操作；

下面我们先声明一个动态顺序表

typedef int  sldtype;
struct seqlist
{sldtype* arr;int size;//有效数据个数int capacity;//空间容量
};
typedef struct seqlist SL;

下面我们看看如何实现一个完整的顺序表

2.121 顺序表的初始化
void slinit(SL*);//顺序表的声明
void slinit(SL* ps)
{ps->arr = NULL;ps->size = 0;ps->capacity = 0;
}

先将所有的数据置空。

2.122 顺序表的头插与尾插
void slpushback(SL* ps, sldtype x);//尾插
void slpushfrond(SL* ps, sldtype x);//头插

而当我们需要插入数据时，首先就要考虑一点，即空间是否足够，如果不够的话我们就需要进行扩容，所以我们先看怎么能够扩容。

void slcheckcapacity(SL* ps);//增容函数

 

void slcheckcapacity(SL* ps)//增容函数
{if (ps->capacity == ps->size){//增容int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;sldtype* tmp = (sldtype*)realloc(ps->arr, newcapacity * sizeof(sldtype));//不直接使用ps防止扩容失败将其质空导致数据丢失if (tmp == NULL){perror("realloc fail");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}
}

其主要思路就是当数据的储存量到达了极限时，我们进行增容，我的一开始设置的大小是4个储存类型的大小，当其大小不够时，进行整数倍扩容

了解怎么扩容后我们就看看怎么插入

首先是尾插，只用直接在最后的位置添加数据即可

void slpushback(SL* ps, sldtype x)
{//判断空间是否足够slcheckcapacity(ps);//当空间足够的时候ps->arr[ps->size++] = x;//插入数据}

而头插就需要将之前的数据整体向后挪动 

void slpushfrond(SL* ps, sldtype x)
{if (ps == NULL){return;}slcheckcapacity(ps);//将数组的所有数据向后挪动一位for (int i = ps->size;i > 0;i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;++ps->size;}
2.123头删和尾删

先看比较好实现的尾删

void slpopback(SL* ps)
{assert(ps&&ps->size);--ps->size;
}

直接将size所在的位置向前移动就行了，但要考虑size为0的情况，我们采用断言

然后是头删

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

思路就是将所有的数据向左移动

2.124在指定位置插入和删除数据

先看插入数据

void slinsert(SL* ps, int pos, sldtype x)
{slcheckcapacity(ps);assert(ps);assert(pos >= 0 && pos <= ps->size);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)
{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;
}

其思路就是将所有数据项删除的地方移动，将其覆盖

2.125 查找指定数据
int slfind(SL* ps, sldtype x)
{for (int i = 0;i < ps->size;i++){if (ps->arr[i] == x){return i;}}return -1;
}

简单的条件判断，不做解释

2.126顺序表的销毁
void sldestroy(SL* ps)
{assert(ps);if (ps->arr)free(ps->arr);ps->arr = NULL;ps->capacity =ps->size = 0;
}

即将所有数据置空，并释放动态内存 

3.完整代码展示

3.1头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
typedef int  sldtype;
struct seqlist
{sldtype* arr;int size;//有效数据个数int capacity;//空间容量};
typedef struct seqlist SL;
void slinit(SL*);//顺序表的初始化
void slpushback(SL* ps, sldtype x);//尾插
void slpushfrond(SL* ps, sldtype x);//头插
void slcheckcapacity(SL* ps);//增容函数
void slprint(SL* ps);//打印顺序表
void slpopback(SL* ps);//尾删void slpopfromt(SL* ps);//头删
void slinsert(SL* ps ,int pos, sldtype x);//在指定位置(下标)前插入数据
void slerase(SL* ps, int pos);//删除指定位置的数据
int slfind(SL* ps, sldtype x);//查找指定数据
void sldestroy(SL* ps);//销毁顺序表

3.2实现文件

#define _CRT_SECURE_NO_WARNINGS#include"seqlist.h"
#include<assert.h>
void slinit(SL* ps)
{ps->arr = NULL;ps->size = 0;ps->capacity = 0;
}
void slcheckcapacity(SL* ps)//增容函数
{if (ps->capacity == ps->size){//增容int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;sldtype* tmp = (sldtype*)realloc(ps->arr, newcapacity * sizeof(sldtype));//不直接使用ps防止扩容失败将其质空导致数据丢失if (tmp == NULL){perror("realloc fail");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}
}
void slpushback(SL* ps, sldtype x)
{//判断空间是否足够slcheckcapacity(ps);//当空间足够的时候ps->arr[ps->size++] = x;//插入数据}
void slpushfrond(SL* ps, sldtype x)
{if (ps == NULL){return;}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&&ps->size);--ps->size;
}
void slprint(SL* ps)
{for (int i = 0;i < ps->size;i++){printf("%d ", ps->arr[i]);}printf("\n");
}
void slpopfromt(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, sldtype x)
{slcheckcapacity(ps);assert(ps);assert(pos >= 0 && pos <= ps->size);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)
{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, sldtype x)
{for (int i = 0;i < ps->size;i++){if (ps->arr[i] == x){return i;}}return -1;
}
void sldestroy(SL* ps)
{assert(ps);if (ps->arr)free(ps->arr);ps->arr = NULL;ps->capacity =ps->size = 0;
}

 3.3测试文件

#define _CRT_SECURE_NO_WARNINGS
#include"seqlist.h"
void test1()
{SL sl;slinit(&sl);slpushback(&sl, 1);slpushback(&sl, 2);slpushback(&sl, 3);slpushback(&sl, 4);slpushback(&sl, 5);slpushfrond(&sl, 5);slpopback(&sl);slpopfromt(&sl);slinsert(&sl, 1, 5);slerase(&sl, 2);sldestroy(&sl);slprint(&sl);int find = slfind(&sl, 3);/*if (find>=0){printf("找到了\n");printf("下标是：%d\n", find);}else{printf("没找到\n");}*//*printf("%d", sl.size);*/}
int main()
{test1();return 0;
}

今天的内容就到这里了，后续会继续更新，感谢阅读！ 

http://www.xdnf.cn/news/2688.html

相关文章：

  • 伺服电机AB相输出，接入定时器通道，对定时器IO口的速率有何要求【详细分析】
  • 【Unity完整游戏开发案例】从0做一个太空大战游戏
  • MySQL主从同步原理与实践 - Java架构师面试解析
  • 【Python】Matplotlib：立体永生花绘制
  • 单值映射、多值映射
  • Linux：进程间通信-＞共享内存
  • 开源网络入侵检测与防御系统:Snort
  • 企业私有大模型DeepSeek落地部署该用什么? Ollama还是vLLM
  • PlatformIO 入门学习笔记（一）：背景了解
  • 【每天一个知识点】correntropy（相关熵）
  • 08-STM32外部中断
  • el-input限制输入只能是数字 限制input只能输入数字
  • 中国区域250米归一化植被指数数据集（2000-2023）
  • 迅雷精简绿色融合版【高速下载版】12.1.9.2870【11.2.2.1716】【20250426】
  • 树莓派学习专题＜10＞：使用V4L2驱动获取摄像头数据--申请和管理缓冲区
  • 【PVR】《Adaptive Palm Vein Recognition Method》
  • codeforcesB. Binary Colouring
  • 实人认证开发指南：用API+深度学习构建人证合一系统
  • 【CF】Day45——Codeforces Round 1021 (Div. 2) BC
  • UV工具的安装与使用
  • 2025系统架构师---数据抽象（Data Abstraction）‌与‌面向对象架构风格
  • Android原生开发基础
  • 龙芯远程方案
  • 如何判断对一件事的认知深度？
  • Python+jieba文本分析示例：实现统计《红楼梦》中的人物并生成词云图
  • 人工智能——XGBoost 算法
  • 【2025最新Java面试八股】如何在Spring启动过程中做缓存预热？
  • 【基础篇】prometheus页面UI功能详解
  • AI翻译LangChain实现的一点有趣思考
  • 深入浅出提示词工程（结合 DeepSeek）