您现在的位置是：首页 >技术交流 >顺序表的实现 （C语言）从0到1，还有视频帮助理解，事半功倍！！网站首页技术交流
顺序表的实现 （C语言）从0到1，还有视频帮助理解，事半功倍！！
简介顺序表的实现 （C语言）从0到1，还有视频帮助理解，事半功倍！！
爱，是一件非专业的事情，不是本事，不是能力，是花木那样的生长，有一份对光阴和季节的钟情和执着。一定要，爱着点什么，它让我们变得坚韧，宽容，充盈。业余的，爱着。
——《生活是很好玩的》
大家好，今天我们来实现一个在数据结构中较为容易理解的一种数据结构——顺序表。
一 . 线性表
在我们完成顺序表之前，我们先来了解一下什么是线性表。
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物 理上存储时，通常以数组和链式结构的形式存储。
例图：
二 . 顺序表
（1）概念及结构：
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为：
1. 静态顺序表：使用定长数组存储。
优点：操作简单，代码实现容易 。
缺点：内存给多少的合适呢？这个很难确定。给小了不够用，给大了就浪费内存了。
2. 动态顺序表：使用动态开辟的数组存储。
优点：数组可以根据自己的需求进行调解
缺点：中间/头部的插入删除，时间复杂度为O(N) 并且 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
（2）目录实现：
void menu()
{
printf("***********************************************************
");
printf("1 尾插数据------2 尾删数据
");
printf("
");
printf("3 头插数据------4 头删数据
");
printf("
");
printf("5 在任意位置插入数据
");
printf("
");
printf("6 在任意位置删除数据
");
printf("
");
printf("7 查找某个数据的位置，并删除它
");
printf("
");
printf("8 打印数据
");
printf("
");
printf("-1 退出
");
printf("
");
printf("***********************************************************
");
}
int main()
{
int option = 0;
SL s;
SeqListInit(&s);
do
{
menu();
printf("请输入你的操作：>>>>>> ");
scanf("%d", &option);
int sum = 0;
int x = 0;
int y = 0;
int z = 0;
int pos = 0;
int w = 0;
switch (option)
{
case 1:
printf("请依输入尾插的数据：(-1结束)
");
scanf("%d", &sum);
while (sum != -1)
{
SeqListPushBack(&s, sum); // 1.尾插
scanf("%d", &sum);
}
break;
case 2:
SeqListPopBack(&s); // 2.尾删
break;
case 3:
scanf("%d", &x);
SeqListPushFront(&s, x); // 3.头插
break;
case 4:
SeqListPopFront(&s); // 4.头删
break;
case 5:
SeqListInsert(&s, 3, 20); // 5.在任意位置插入数据
break;
case 6:
SeqListErase(&s, 3); // 6.在任意位置删除数据
break;
case 7:
printf("请输入要删除序列的中的某个数字
");
scanf("%d", &z);
y = SeqListFind(&s, z); // 7.查找某个数字的位置，并且删除它
printf("%d的位置在%d处：
", z, y);
if (y != -1)
{
SeqListErase(&s, y);
}
break;
case 8:
SeqListPrint(&s);
break;
default:
if (option == -1)
{
exit(0); // 退出程序
}
else
{
printf("输入错误，请重新输入
");
}
break;
}
} while (option != -1); // 退出程序
SeqListDestory(&s);
return 0;
}
（3）接口实现：
由于静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。
在这里我们先建立三个文件：
SeqList.h 文件，用于函数声明
SeqList.c 文件，用于函数的定义
Test.c 文件，用于测试函数
这样可以便利我们检查代码，理清思路。
2.1 定义结构体 SL 【SeqList.h】
动态顺序表的结构体是由三个成员变量组成的：
a ：用来指向动态开辟空间的指针
size ：用来记录当前有效数据个数——表示当前数组中存储了多少个数据
capacity ：用来记录当前容量——数组当前实际能存数据的空间容量是多大
#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;
// 动态顺序表
typedef struct SeqList
{
SLDataType* a;
int size; // 表示数组中存储了多少个数据
int capacity; // 数组实际能存数据的空间容量是多大
}SL;
2.2 初始化结构体 (SeqListInit)
我们知道，要正确的进行的初始化结构体，我们就需要传递SL 的地址，通过指针来对结构体的内容进行修改。这是因为实参在传参的时候，会形成一个份临时拷贝，叫做形参。当我们在函数中对形参的内容进行修改时，形参的改变是不会影响到实参的。
//顺序表初始化
void SeqListInit(SL* ps)
{
assert(ps);
ps->a = NULL;
ps->size = 0；
ps->capacity = 0;
}2.3 检查结构体中的数组是否需要扩容 (SeqListCheckCapacity)
当顺序表需要插入数据时，可能会遇到三种情况：
整个顺序表没有空间
空间不够，需要扩容
空间足够，直接插入数据
1)如果顺序表空间足够，那么不需要扩容，通过相关操作插入数据
2)如果空间不足或者根本没有空间，那么就得扩容。
2.1)当顺序表没有空间时，我们开辟四个空间
2.2)当顺序表空间不足，我们将当前空间扩大为两倍(扩两倍是为了防止扩容过度，或扩小了 频繁扩容，消耗过大。
//检查内存大小，不够就扩容
void SeqListCheckCapacity(SL* ps)
{
// 如果没有空间或者空间不足，那么我们就扩容
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
if (tmp == NULL)
{
printf("realloc fail
");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
}2.4 尾插(SeqListPushBack)
只需在容量充足的时候，在最后插入一个数据即可。
void SeqListPushBack(SL* ps, SLDataType x)
{
SeqListCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}
2.5尾删 （SeqListPopBack）
要注意：当顺序表没有元素时，也就是 sz 为 0 时，不可以进行删除
举例： 假如顺序表有 5 个数据，此时我们尾删 6 个数据，那么这时，我们顺序表的 size = -1。此时程序不会报错，因为本身就没有数据可以删除，但是让我们在进行尾插的时候，程序就会报错啦，因为尾插数据会访问 size 的下表 -1 此时出现了越界访问，程序就出现了错。
解决方案 ： 我们可以加入断言（assert）进行判断，也可以采用if语句，以防止size 的下标越界
//尾删
void SeqListPopBack(SL* ps)
{
// 温柔处理方式
if (ps->size > 0)
{
ps->a[ps->size - 1] = 0;
ps->size--;
}
// 暴力处理方式
assert(ps->size > 0);
ps->size--;
}2.6 头插（SeqListPushFront）
头插原理 ：头插就是将数据放在下标为 0 的地方 其余数据依次向后挪一位。
此时出现两种情况：
再向后挪数据的过程中，
（1）先从第一个数据开始挪动（不能）
（2）先从最后一个数据开始挪动
如果我们先从第一个数据开始挪动那么可能会出现下面的情况：
我们发现会发生数据覆盖。所以第一种情况不能使用
再看（2）先从最后一个数据开始挪动：
非常符合我们的预想，所以我们可以使用
//头插
void SeqListPushFront(SL* ps, SLDataType x)
{
SeqListCheckCapacity(ps);
// 挪动数据
int end = ps->size - 1;
/while (end >= 0)
{
ps->a[end + 1] = ps->a[end];
--end;
}
ps->a[0] = x;
ps->size++;
}2.7 头删（SeqListPopFront）
头删原理：头删就是将下标为 0 的数据删除，其余数据依次向前挪动，采用与头插相反的方式即可，即先从下标为 1 的数据向前挪动，而先从最后一个数据向前挪动（不能）
//头删
void SeqListPopFront(SL* ps)
{
assert(ps->size > 0);
// 挪动数据
int begin = 0;
while (begin < ps->size-1)
{
ps->a[begin] = ps->a[begin+1];
++ begin;
}
int begin = 1;
while (begin < ps->size)
{
ps->a[begin-1] = ps->a[begin];
++begin;
}
ps->size--;
}
2.8 在指定位置插入数据（SeqListInsert）
注：要实现这一功能，我们依然需要一个end下标，数据从后往前依次后挪，直到pos下标移动完毕。
另外，检查容量。
// 指定pos下标位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
// 温柔的处理方式
/*if (pos > ps->size || pos < 0)
{
printf("pos invalid
");
return;
}*/
// 粗暴的方式
assert(pos >= 0 && pos <= ps->size);
SeqListCheckCapacity(ps);
// 挪动数据
int end = ps->size - 1;
while (end >= pos)
{
ps->a[end + 1] = ps->a[end];
--end;
}
ps->a[pos] = x;
ps->size++;
}
注：该功能其实也可以实现头插和尾插，所以我们可以在头插和尾插中复用该功能
尾插：
void SeqListPushBack(SL* ps, SLDataType x)
{
SeqListInsert(ps, ps->size, x);
}头插：
void SeqListPushFront(SL* ps, SLDataType x)
{
SeqListInsert(ps, 0, x);
}2.9在指定位置删除数据（SeqListErase）
注 ：要实现这一功能，我们需要一个begin下标，数据从后往前依次后挪，直到sz-1下标移动完毕。
// 删除pos位置的数据
void SeqListErase(SL* ps, int pos)
{
assert(pos >= 0 && pos < ps->size);
int begin = pos + 1;
while (begin < ps->size)
{
ps->a[begin - 1] = ps->a[begin];
++begin;
}
ps->size--;
}注：该功能其实也可以实现头删和尾删
尾删
//尾删
void SeqListPopBack(SL* ps)
{
SeqListErase(ps, ps->size - 1);
}头删
//头删
void SeqListPopFront(SL* ps)
{
assert(ps->size > 0);
SeqListErase(ps, 0);
}
2.10 查找某一个数据的位置（SeqListFind）
遍历查找便可
int SeqListFind(SL* ps, SLDataType x)
{
for (int i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
{
return i;
}
}
return -1;
}2.11打印顺序表（SeqListPrint）
把各元素依次打印便可
//打印顺序表
void SeqListPrint(SL* ps)
{
for (int i = 0; i < ps->size; ++i)
{
printf("%d ", ps->a[i]);
}
printf("
");
}
2.12销毁顺序表（SeqListDestory）
需要把顺序表所开辟的空间释放掉，防止内存泄漏
//销毁顺序表
void SeqListDestory(SL* ps)
{
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}
三 .顺序表完整代码
SeqList.h
#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDataType;
// 动态顺序表
typedef struct SeqList
{
SLDataType* a;
int size; // 表示数组中存储了多少个数据
int capacity; // 数组实际能存数据的空间容量是多大
}SL;
// 接口函数 -- 命名风格是跟着STL走的，建议大家也跟着我们上课走，方便后续学习STL
void SeqListPrint(SL* ps);
void SeqListInit(SL* ps);
void SeqListDestory(SL* ps);
void SeqListCheckCapacity(SL* ps);
void SeqListPushBack(SL* ps, SLDataType x);
void SeqListPopBack(SL* ps);
void SeqListPushFront(SL* ps, SLDataType x);
void SeqListPopFront(SL* ps);
// 找到了返回x位置下标，没有找打返回-1
int SeqListFind(SL* ps, SLDataType x);
// 指定pos下标位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x);
// 删除pos位置的数据
void SeqListErase(SL* ps, int pos);
SeqList.c
#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"
//打印顺序表
void SeqListPrint(SL* ps)
{
for (int i = 0; i < ps->size; ++i)
{
printf("%d ", ps->a[i]);
}
printf("
");
}
//顺序表初始化
void SeqListInit(SL* ps)
{
ps->a = NULL;
ps->size = ps->capacity = 0;
}
//销毁顺序表
void SeqListDestory(SL* ps)
{
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}
//检查内存大小，不够就扩容
void SeqListCheckCapacity(SL* ps)
{
// 如果没有空间或者空间不足，那么我们就扩容
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
if (tmp == NULL)
{
printf("realloc fail
");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
}
//尾插
void SeqListPushBack(SL* ps, SLDataType x)
{
/*SeqListCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;*/
SeqListInsert(ps, ps->size, x);
}
//尾删
void SeqListPopBack(SL* ps)
{
// 温柔处理方式
//if (ps->size > 0)
//{
// //ps->a[ps->size - 1] = 0;
// ps->size--;
//}
// 暴力处理方式
/*assert(ps->size > 0);
ps->size--;*/
SeqListErase(ps, ps->size - 1);
}
//头插
void SeqListPushFront(SL* ps, SLDataType x)
{
//SeqListCheckCapacity(ps);
挪动数据
//int end = ps->size - 1;
//while (end >= 0)
//{
// ps->a[end + 1] = ps->a[end];
// --end;
//}
//ps->a[0] = x;
//ps->size++;
SeqListInsert(ps, 0, x);
}
//头删
void SeqListPopFront(SL* ps)
{
assert(ps->size > 0);
// 挪动数据
//int begin = 0;
//while (begin < ps->size-1)
//{
// ps->a[begin] = ps->a[begin+1];
// ++ begin;
//}
//int begin = 1;
//while (begin < ps->size)
//{
// ps->a[begin-1] = ps->a[begin];
// ++begin;
//}
//ps->size--;
SeqListErase(ps, 0);
}
int SeqListFind(SL* ps, SLDataType x)
{
for (int i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
{
return i;
}
}
return -1;
}
// 指定pos下标位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
// 温柔的处理方式
/*if (pos > ps->size || pos < 0)
{
printf("pos invalid
");
return;
}*/
// 粗暴的方式
assert(pos >= 0 && pos <= ps->size);
SeqListCheckCapacity(ps);
// 挪动数据
int end = ps->size - 1;
while (end >= pos)
{
ps->a[end + 1] = ps->a[end];
--end;
}
ps->a[pos] = x;
ps->size++;
}
// 删除pos位置的数据
void SeqListErase(SL* ps, int pos)
{
assert(pos >= 0 && pos < ps->size);
int begin = pos + 1;
while (begin < ps->size)
{
ps->a[begin - 1] = ps->a[begin];
++begin;
}
ps->size--;
}Test.c
#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"
void TestSeqList1()
{
SL sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
SeqListPrint(&sl);
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPopBack(&sl);
SeqListPopBack(&sl);
//SeqListPopBack(&sl);
//SeqListPopBack(&sl);
SeqListPrint(&sl);
SeqListPushFront(&sl, 10);
SeqListPushFront(&sl, 20);
SeqListPushFront(&sl, 30);
SeqListPushFront(&sl, 40);
SeqListPrint(&sl);
SeqListPushBack(&sl, 10);
SeqListPushBack(&sl, 20);
SeqListPrint(&sl);
SeqListDestory(&sl);
}
void TestSeqList2()
{
SL sl;
SeqListInit(&sl);
SeqListPushBack(&sl, 1);
SeqListPushBack(&sl, 2);
SeqListPushBack(&sl, 3);
SeqListPushBack(&sl, 4);
SeqListPushBack(&sl, 5);
SeqListPrint(&sl);
SeqListPushFront(&sl, 10);
SeqListPushFront(&sl, 20);
SeqListPushFront(&sl, 30);
SeqListPushFront(&sl, 40);
SeqListPrint(&sl);
SeqListPopFront(&sl);
SeqListPopFront(&sl);
SeqListPrint(&sl);
SeqListDestory(&sl);
}
void menu()
{
printf("1 尾插数据------2 尾删数据
");
printf("
");
printf("3 头插数据------4 头删数据
");
printf("
");
printf("5 在任意位置插入数据
");
printf("
");
printf("6 在任意位置删除数据
");
printf("
");
printf("7 查找某个数据的位置，并删除它
");
printf("
");
printf("8 打印数据
");
printf("
");
printf("-1 退出
");
printf("
");
}
int main()
{
int option = 0;
SL s;
SeqListInit(&s);
do
{
menu();
printf("请输入你的操作：>>>>>> ");
scanf("%d", &option);
int sum = 0;
int x = 0;
int y = 0;
int z = 0;
int pos = 0;
int w = 0;
switch (option)
{
case 1:
printf("请依输入尾插的数据：(-1结束)
");
scanf("%d", &sum);
while (sum != -1)
{
SeqListPushBack(&s, sum); // 1.尾插
scanf("%d", &sum);
}
break;
case 2:
SeqListPopBack(&s); // 2.尾删
break;
case 3:
scanf("%d", &x);
SeqListPushFront(&s, x); // 3.头插
break;
case 4:
SeqListPopFront(&s); // 4.头删
break;
case 5:
SeqListInsert(&s, 3, 20); // 5.在任意位置插入数据
break;
case 6:
SeqListErase(&s, 3); // 6.在任意位置删除数据
break;
case 7:
printf("请输入要删除的数字
");
scanf("%d", &z);
y = SeqListFind(&s, z); // 7.查找某个数字的位置，并且删除它
printf("%d的位置在%d处：
", z, y);
if (y != -1)
{
SeqListErase(&s, y);
}
break;
case 8:
SeqListPrint(&s);
break;
default:
if (option == -1)
{
exit(0); // 退出程序
}
else
{
printf("输入错误，请重新输入
");
}
break;
}
} while (option != -1); // 退出程序
SeqListDestory(&s);
return 0;
}
以上就是有关顺序表的实现，如果对大家有所帮助就行，感谢。
风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。
站长推荐
- SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权 - stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程） - U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决 - 【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》 - Unity创建文本时自动修改默认字体
Unity创建文本时自动修改默认字体