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

欢迎拜访：雾里看山-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;
}

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