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

数据结构之顺序表（C语言版本）

news 2025/6/28 11:21:03

欢迎拜访：雾里看山-CSDN博客
本篇主题：数据结构之顺序表（C语言版本）
发布时间：2025.6.27
隶属专栏：数据结构

在这里插入图片描述

目录

  • 顺序表的概念
  • 核心特点：
  • 顺序表的优缺点分析
    • 优点：
    • 缺点：
  • 顺序表的使用场景
  • 具体实现（以动态为例）
    • 创建结构体
      • 静态顺序表
      • 动态顺序表
    • 基本功能 接口实现
      • 初始化
      • 销毁
      • 打印
    • 扩容检查 接口实现
    • 增删查改 接口实现
      • 增
        • 头插
        • 尾插
        • 指定位置插入
      • 删
        • 头删
        • 尾删
        • 指定位置删除
      • 查
      • 改
  • 整体代码展示

顺序表的概念

顺序表（Sequence List）是线性表的顺序存储结构，它用一段连续的存储单元依次存储线性表中的数据元素。在C语言中，顺序表通常通过数组来实现。

核心特点：

  • 连续存储：数据元素在内存中连续存放
  • 随机访问：可以通过下标直接访问任意元素
  • 固定容量：需要预先分配存储空间
  • 长度可变：通过记录当前元素数量实现动态使用

顺序表的优缺点分析

优点：

  • 随机访问：通过下标直接访问元素，时间复杂度O(1)
  • 存储密度高：只存储数据元素，无额外空间开销
  • 尾插高效：在表尾插入元素的时间复杂度O(1)
  • 缓存友好：连续存储有利于CPU缓存命中

缺点：

  • 插入/删除慢：平均需要移动n/2个元素，时间复杂度O(n)
  • 容量固定：静态分配需要预先确定大小，可能浪费空间或不足
  • 扩容代价高：动态分配扩容需要复制所有元素，时间复杂度O(n)
  • 内存要求：需要连续的大块内存空间

顺序表的使用场景

  • 元素数量相对固定的应用
  • 查询操作远多于插入删除的场景
  • 需要快速随机访问元素的情况
  • 对内存占用敏感的嵌入式系统
  • 元素规模较小的数据集合

具体实现（以动态为例）

创建结构体

顺序表一般可分为：

  1. 静态顺序表：使用定长数组存储元素。
  2. 动态顺序表：使用动态开辟的数组存储。

静态顺序表

// 静态顺序表
#define N 1000 // 顺序表的最大容量typedef int SLDataType; //顺序表存储的数据类型struct SeqList
{SLDataType a[N]; //存储元素的数组int size;		 //当前元素个数
};

动态顺序表

typedef int SLDataType;//顺序表存储的数据类型typedef struct SeqList
{SLDataType* a;   // 动态分配数组的指针int size;        // 存储有效数据的个数int capacity;    // 数组的空间大小
}SL;

基本功能 接口实现

初始化

初始化阶段先开辟少量的空间，便于后续操作

void SLInit(SL* ps)
{assert(ps); //断言避免传参是空指针ps->a = (SLDataType *)malloc(sizeof(SLDataType) * 4);// 预先开辟出来一定的空间if (ps->a == NULL){perror("malloc fail");exit(-1);}ps->size = 0;ps->capacity = 4;
}

销毁

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

打印

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

扩容检查 接口实现

当size和capacity相同时，就要准备进行扩容操作了。此处的实现是将空间二倍扩容。

void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){SLDataType * tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(SLDataType));if (tmp == NULL){perror("realloc fail");exit(-2);}ps->a = tmp;ps->capacity = ps->capacity * 2;}
}

增删查改 接口实现

增

头插

头插要考虑好是否需要扩容，而且要将所有数据进行移动。

void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);for (int i = ps->size; i > 0; i--){ps->a[i] = ps->a[i - 1];}ps->a[0] = x;ps->size++;}
尾插

尾插不需要移动数据，只需要考虑是否扩容即可

void SLPushBack(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);ps->a[ps->size] = x;ps->size++;
}
指定位置插入

这里要考虑数据插入的位置是否合理，数组是否需要扩容和数组中的元素移动的问题

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

删

头删

头删要考虑数组中是否存在数据和后面数据的移动问题。

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

只需要判断是否存在数据即可。

void SLPopBack(SL* ps)
{assert(ps);if (ps->size == 0)return;ps->a[ps->size-1] = 0;ps->size--;
}
指定位置删除

要考虑删除的位置是否合理，后续数据的移动问题

// 删除pos位置的值
void SLErase(SL* ps, int pos)
{assert(ps);if (ps->size <= pos || pos < 0)return ;for (int i = pos; i < ps->size-1; i++){ps->a[i] = ps->a[i + 1];}ps->size--;
}

查

遍历数组，返回元素下标，如果元素不存在，返回-1

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

改

需要判断元素位置是否合理

void SLModify(SL* ps, int pos, SLDataType x)
{assert(ps);if (ps->size <= pos || pos < 0)return;ps->a[pos] = x;
}

整体代码展示

整体的代码包括三个文件：SeqList.h、 SeqList.c和 main.c

SeqList.h

#pragma once#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>// 静态顺序表
//#define N 1000 // 顺序表的最大容量
//
//typedef int SLDataType; //顺序表存储的数据类型
//
//struct SeqList
//{
//	SLDataType a[N]; //存储元素的数组
//	int size;		 //当前元素个数
//};// 动态顺序表
typedef int SLDataType;typedef struct SeqList
{SLDataType* a;int size;      // 存储有效数据的个数int capacity;  // 顺序表空间大小
}SL;// 管理数据 -- 增删查改
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);// 扩容检查机制
void SLCheckCapacity(SL* ps);// 头插头删 尾插尾删
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);// 返回下标，没有找打返回-1
int SLFind(SL* ps, SLDataType x);// 在pos位置插入x
void SLInsert(SL* ps, int pos, SLDataType x);// 删除pos位置的值
void SLErase(SL* ps, int pos);//修改pos位置的值
void SLModify(SL* ps, int pos, SLDataType x);

SeqList.c

#include "SeqList.h"// 管理数据 -- 增删查改
void SLInit(SL* ps)
{assert(ps);ps->a = (SLDataType *)malloc(sizeof(SLDataType) * 4);if (ps->a == NULL){perror("malloc fail");exit(-1);}ps->size = 0;ps->capacity = 4;
}
void SLDestroy(SL* ps)
{assert(ps);free(ps->a);ps->a = NULL;	ps->size = 0;ps->capacity = 0;
}
void SLPrint(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);printf("\n");}
}
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){SLDataType * tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(SLDataType));if (tmp == NULL){perror("realloc fail");exit(-2);}ps->a = tmp;ps->capacity = ps->capacity * 2;}
}// 头插头删 尾插尾删
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);ps->a[ps->size] = x;ps->size++;
}
void SLPopBack(SL* ps)
{assert(ps);if (ps->size == 0)return;ps->a[ps->size-1] = 0;ps->size--;
}
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);for (int i = ps->size; i > 0; i--){ps->a[i] = ps->a[i - 1];}ps->a[0] = x;ps->size++;}
void SLPopFront(SL* ps)
{assert(ps);if (ps->size <= 0)return ;for (int i = 0; i < ps->size-1; i++){ps->a[i] = ps->a[i + 1];}ps->size--;
}// 返回下标，没有找打返回-1
int SLFind(SL* ps, SLDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->a[i] == x)return i;}return -1;
}// 在pos位置插入x
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);if (ps->size <= pos || pos < 0)return;	SLCheckCapacity(ps);for (int i = ps->size; i > pos; i--){ps->a[i] = ps->a[i - 1];}ps->a[pos] = x;ps->size++;
}
// 删除pos位置的值
void SLErase(SL* ps, int pos)
{assert(ps);if (ps->size <= pos || pos < 0)return ;for (int i = pos; i < ps->size-1; i++){ps->a[i] = ps->a[i + 1];}ps->size--;
}void SLModify(SL* ps, int pos, SLDataType x)
{assert(ps);if (ps->size <= pos || pos < 0)return;ps->a[pos] = x;
}

main.c

#include<stdio.h>
#include"SeqList.h"void TestSeqList1()
{SL sl;SLInit(&sl);SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPushBack(&sl, 5);SLPushBack(&sl, 6);SLPushBack(&sl, 6);SLPushBack(&sl, 0);SLPushBack(&sl, 0);SLPrint(&sl);SLPopBack(&sl);SLPopBack(&sl);SLPrint(&sl);SLPopBack(&sl);SLPopBack(&sl);SLPopBack(&sl);SLPopBack(&sl);SLPopBack(&sl);SLPopBack(&sl);SLPopBack(&sl);//SLPopBack(&sl);//SLPopBack(&sl);/*SLPopBack(&sl);SLPopBack(&sl);SLPopBack(&sl);SLPopBack(&sl);*/SLPrint(&sl);SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPrint(&sl);SLDestroy(&sl);
}void TestSeqList2()
{SL sl;SLInit(&sl);SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPushBack(&sl, 5);SLPrint(&sl);SLPushFront(&sl, 10);SLPushFront(&sl, 20);SLPushFront(&sl, 30);SLPushFront(&sl, 40);SLPrint(&sl);SLDestroy(&sl);
}void TestSeqList3()
{SL sl;SLInit(&sl);SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPushBack(&sl, 5);SLPrint(&sl);SLPopFront(&sl);SLPopFront(&sl);SLPrint(&sl);SLPopFront(&sl);SLPopFront(&sl);SLPopFront(&sl);//SLPopFront(&sl);SLPrint(&sl);SLPushBack(&sl, 4);SLPushBack(&sl, 5);SLPrint(&sl);SLDestroy(&sl);
}void TestSeqList4()
{SL sl;SLInit(&sl);SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPushBack(&sl, 5);SLPushFront(&sl, -1);SLPushFront(&sl, -2);SLPrint(&sl);SLInsert(&sl, 3, 40);SLPrint(&sl);int x;scanf("%d", &x);int pos = SLFind(&sl, x);if (pos != -1){SLInsert(&sl, pos, x * 10);}SLPrint(&sl);SLDestroy(&sl);}void TestSeqList5()
{SL sl;SLInit(&sl);SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPushBack(&sl, 5);SLPrint(&sl);SLErase(&sl, 2);SLPrint(&sl);int x;scanf("%d", &x);int pos = SLFind(&sl, x);if (pos != -1){SLErase(&sl, pos);}SLPrint(&sl);SLDestroy(&sl);}void TestSeqList6()
{SL sl;SLInit(&sl);SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPushBack(&sl, 5);SLPrint(&sl);SLModify(&sl, 2, 20);sl.a[2] = 20;SLPrint(&sl);/*int x;scanf("%d", &x);int pos = SLFind(&sl, x);if (pos != -1){SLModify(&sl, pos, x*10);}SLPrint(&sl);*/int pos, x;scanf("%d%d", &pos, &x);//sl.a[pos] = x;SLModify(&sl, pos, x);SLPrint(&sl);SLDestroy(&sl);
}void TestSeqList7()
{/*SL* sl = NULL;SLInit(sl);SLPushBack(sl, 1);SLPushBack(sl, 2);SLPushBack(sl, 3);SLPushBack(sl, 4);SLPushBack(sl, 5);SLPrint(sl);*/SL sl;SLInit(&sl);SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPushBack(&sl, 5);SLPrint(&sl);SLPopFront(&sl);SLDestroy(&sl);
}//int main()
//{
//	TestSeqList6();
//
//	return 0;
//}void menu()
{printf("****************************************\n");printf("1、尾插  2、头插\n");printf("3、头删  4、尾删\n");// ...printf("7、打印 -1、退出\n");printf("****************************************\n");
}int main()
{SL sl;SLInit(&sl);int option = 0;do{menu();scanf("%d", &option);if (option == 1){//printf("请依次输入输入你要插入的数据，以-1结束\n");printf("请依次输入你要插入数据个数和数据\n");int n = 0;scanf("%d", &n);int x = 0;for (int i = 0; i < n; i++){scanf("%d", &x);SLPushBack(&sl, x);}}else if (option == 2){printf("请依次输入你要插入数据个数和数据\n");int n = 0;scanf("%d", &n);int x = 0;for (int i = 0; i < n; i++){scanf("%d", &x);SLPushFront(&sl, x);}}else if (option == 3){SLPopFront(&sl);}else if (option == 4){SLPopBack(&sl);}else if (option == 7){SLPrint(&sl);}} while (option != -1);SLDestroy(&sl);return 0;
}

⚠️ 写在最后：以上内容是我在学习以后得一些总结和概括，如有错误或者需要补充的地方欢迎各位大佬评论或者私信我交流！！！

http://www.lqws.cn/news/545725.html

相关文章：

  • 【高并发服务器项目测试报告】
  • 大事件项目记录4-用户接口开发-更新用户基本信息
  • 【论文阅读 | CVPR 2025 |MambaVision：一种混合 Mamba-Transformer 视觉骨干网络】
  • Node.js到底是什么
  • Dockerfile——AI教你学Docker
  • 【Python】实现对LGBT+ rights worldwide (2025)数据集的可视化展示
  • 还在手动部署？用Jenkins+Docker+Git实现自动化CI/CD
  • 使用ant-design-vue 写个适用于web端的条件搜索栏组件，可折叠展开
  • 2025Mybatis最新教程（七）
  • 机器学习中为什么要用混合精度训练
  • 2025.6.27总结
  • HTTP协议中Connection: Keep-Alive和Keep-Alive: timeout=60, max=100的作用
  • SpringMVC系列（四）（请求处理的十个实验（下））
  • 多模态融合相机L3CAM
  • 高斯过程动态规划（GPDP）
  • 免费无广告PDFCreator：虚拟打印软件一键转 PDF/PNG/JPG
  • printf和scanf
  • 问卷调查[bell ring]
  • 全志A733、瑞芯微RK3576与联发科MTK8371场景化应用解析在物联网与智能设备快速迭代的今天，芯片作为硬件核心直接决定了设备的性能边界与应用场景。
  • moduo之tcp客户端TcpClient
  • Webpack 自定义插件开发指南：构建流程详解与实战开发全攻略
  • Html5播放器禁止拖动播放器进度条（教学场景）
  • 神经网络的概念和案例
  • FrozenBatchNorm2d 详解
  • 聚铭网络入选嘶吼《中国网络安全细分领域产品名录》“云平台安全管理”与“态势感知”双领域TOP10
  • Linux tcp_info：监控TCP连接的秘密武器
  • CatBoost：征服类别型特征的梯度提升王者
  • 蓝牙工作频段与跳频扩频技术（FHSS）详解：面试高频考点与真题解析
  • System.Threading.Tasks 库简介
  • ubuntu ollama 遇到的若干问题