文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >顺序表（一）：手撕动态顺序表

顺序表（一）：手撕动态顺序表

作者头像
用户11831438
发布于 2025-12-30 13:31:59
发布于 2025-12-30 13:31:59
740
举报
一、线性表

线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、栈、队列、字符串……

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常是以数组和链式结构的形式存储。

相同特性分为：

  1. 逻辑结构 --人为想象出来的结构，一定是线性的
  2. 物理结构 --不一定是线性的
二、顺序表
2.1 概念与结构

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

1

2

3

4

5

6

7

顺序表：逻辑结构：线性；物理结构：线性 。

顺序表和数组的关系？ 顺序表的底层结构是数组，顺序表使用数组来实现的。这段话是啥意思？让我们通过画图来分析一下。

数组就好比如是苍蝇馆子，顺序表就比如是米其林餐厅，苍蝇馆子里面有的，米其林餐厅里面也有，但米其林餐厅有的，苍蝇馆子里面可没有哦。在顺序表里面，我们可以对数组进行增加数据，删除数据，修改数据，查找数据……

2.2 顺序表的功能

可以概括为增删改查四个功能：

  • 增：在指定位置添加元素
  • 删：删除指定位置的元素
  • 查：查找指定位置的元素
  • 改：修改指定位置的元素
2.3 顺序表的分类
2.3.1 静态顺序表

静态顺序表的创建：

代码语言：javascript
复制
typedef int SLDataType;
#define N 7
typedef struct SeqList {
	SLDataType a[N];	//定长数组
	int size;			//有效数据个数
}SL;

由于静态顺序表是使用定长数组存储元素，所以可能会造成空间上的浪费。

2.3.2 动态顺序表

动态顺序表的创建：

代码语言：javascript
复制
//动态顺序表--按需申请
typedef int SLDataType;
typedef struct SeqList {
	SLDataType* arr;
	int size;			//有效数据个数
	int capacity;		//空间容量
}SL;
三、动态顺序的具体实现（纯C语言）

创建一个动态顺序表，我们首先要开辟一片连续的空间用来存储顺序表中的数据，并且要保证这片空间的大小可以调节，那么我们可以创建一个指针来存储，因此，我们还要创建变量来存储顺序表的大小和这片空间的空间容量

代码语言：javascript
复制
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* arr;//存储数据
	int size;//有效数据个数
	int capcity;//空间大小
}SL;
3.1 顺序表的初始化
代码语言：javascript
复制
//初始化
void SLInt(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capcity = 0;
}
3.2 增加数据

首先，我们要先创建一个函数来检查空间容量，当空间容量不够的时候，可以增加容量：

代码语言：javascript
复制
void SLcheckcapcity(SL* ps)
{
	if (ps->size == ps->capcity)
	{
		int newcapcity = ps->capcity == 0 ? 4 : 2 * ps->capcity;
		ps->capcity = newcapcity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, ps->capcity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}
		ps->arr = tmp;
	}
}
3.2.1 在顺序表的尾部增加数据（尾插）

检查空间容量，当空间容量足够的时候，直接在尾部增加数据，如果容量不够，需要扩容,添加完之后，size++。

代码语言：javascript
复制
//尾插法
void SLpushBack(SL* ps, SLDataType num)
{
	//空间不够,需要扩容
	SLcheckcapcity(ps);
	//空间足够
	ps->arr[ps->size++] = num;
}
3.2.2 在顺序表的开头增加数据（头插）

检查空间容量，当空间容量足够的时候，将所有元素向后移动一位，再把要添加的数据添加到开头，添加完之后，size++。

代码语言：javascript
复制
//头插法
void SLpushFront(SL* ps, SLDataType num)
{
	//空间不够
	SLcheckcapcity(ps);
	//空间足够
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = num;
	ps->size++;
}
3.2.3 在顺序表的指定位置前增加数据

首先要检查空间容量，在顺序表的指定位置前增加数据，需要将从该位置开始所有元素向后移动一位，将元素添加到指定位置,添加完之后，size++。

代码语言：javascript
复制
//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType num)
{
	//判断是否为空
	assert(ps->arr&&pos>=0&&pos<ps->size);
	//空间不够,扩容
	SLcheckcapcity(ps);
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = num;
	ps->size++;
}
3.2.4 在顺序表的指定位置后增加数据

在指定位置后添加元素：从该位置后一位元素开始，所有元素向后移动一位，再将指定元素添加到指定位置，添加完之后，size++。

代码语言：javascript
复制
//在指定位置之后插入数据
void SLInsertAfter(SL* ps, int pos, SLDataType num)
{
	//判段是否为空
	assert(ps->arr && pos >= 0 && pos < ps->size);
	//空间够不够，扩容
	SLcheckcapcity(ps);
	for (int i = ps->size; i > pos + 1; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos + 1] = num;
	ps->size++;
}
3.3 删除数据
3.3.1 尾部删除

尾部删除在顺序表中式最容易实现的一种删除方式，我们仅仅需要将size自减就可以了，但是在删除之前，我们需要先判断此顺序表中是否存在元素

代码语言：javascript
复制
//尾删
void SLpopback(SL* ps)
{
	//顺序表是否为空
	assert(ps->arr && ps->size);
	ps->size--;
}
3.3.2 头部删除

从下标为1的位置开始的所有元素向前移动一位，然后size--。

代码语言：javascript
复制
//头删
void SLpopFront(SL* ps)
{
	//顺序表是否为空
	assert(ps->arr && ps->size);
	for (int i = 0; i < ps->size; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}
3.3.3 指定位置删除

该位置以后的所有元素都向前移动一位，移动完之后，size--。

代码语言：javascript
复制
//删除pos位置上的数据
void SLdelete(SL* ps, int pos)
{
	//顺序表是否为空
	assert(ps->arr && ps->size);
	for (int i = pos; i < ps->size; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}
3.4 查找数据的位置

在代码中，如果我们自己主动输入位置是不是显得有那么一点多余，所以我们可以让代码自己查找数据的坐标，然后我们通过下标就可以完成相应的操作，接下来让我们看看如何得到我们想要的数据的位置：

代码语言：javascript
复制
//查找位置
int SLfindmember(SL* ps, SLDataType num)
{
	//判断是否为空
	assert(ps->arr);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == num)
		{
			return i;
		}
	}
	return -1;
}
3.5 修改数据
代码语言：javascript
复制
//修改指定位置的数据
void SLChange(SL* ps, int pos, SLDataType num)
{
	//判段顺序表是否为空以及位置是否在限度内
	assert(ps->arr && pos >= 0 && pos <= ps->size);
	ps->arr[pos] = num;
}
3.6 顺序表的打印
代码语言：javascript
复制
//顺序表打印
void SLprint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
}
3.7 顺序表的销毁
代码语言：javascript
复制
//结束时释放空间
void SLfree(SL* ps)
{
	ps->arr = NULL;
	ps->capcity = ps->size = 0;
}
3.8 完整代码

SeqList.h（头文件、函数声明）：

代码语言：javascript
复制
#pragma once
#include<assert.h>
#include<stdio.h>
#include<stdlib.h>
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* arr;//存储数据
	int size;//有效数据个数
	int capcity;//空间大小
}SL;
//结束时释放空间
void SLfree(SL* ps);
//打印
void SLprint(SL* ps);
//初始化顺序表
void SLInt(SL* ps);
//尾插法
void SLpushBack(SL* ps, SLDataType num);
//头插法
void SLpushFront(SL* ps, SLDataType num);
//尾删
void SLpopback(SL* ps);
//头删
void SLpopFront(SL* ps);
//查找位置
int SLfindmember(SL* ps, SLDataType num);
//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType num);
//在指定位置之后插入数据
void SLInsertAfter(SL* ps, int pos, SLDataType num);
//修改指定位置的数据
void SLChange(SL* ps, int pos, SLDataType num);
//删除pos位置上的数据
void SLdelete(SL* ps, int pos);

SeqList.c(具体操作代码):

代码语言：javascript
复制
#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"
//结束时释放空间
void SLfree(SL* ps)
{
	ps->arr = NULL;
	ps->capcity = ps->size = 0;
}
//顺序表打印
void SLprint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
}
//初始化
void SLInt(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capcity = 0;
}
void SLcheckcapcity(SL* ps)
{
	if (ps->size == ps->capcity)
	{
		int newcapcity = ps->capcity == 0 ? 4 : 2 * ps->capcity;
		ps->capcity = newcapcity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, ps->capcity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}
		ps->arr = tmp;
	}
}
//尾插法
void SLpushBack(SL* ps, SLDataType num)
{
	//空间不够,需要扩容
	SLcheckcapcity(ps);
	//空间足够
	ps->arr[ps->size++] = num;
}
//头插法
void SLpushFront(SL* ps, SLDataType num)
{
	//空间不够
	SLcheckcapcity(ps);
	//空间足够
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = num;
	ps->size++;
}
//尾删
void SLpopback(SL* ps)
{
	//顺序表是否为空
	assert(ps->arr && ps->size);
	ps->size--;
}
//头删
void SLpopFront(SL* ps)
{
	//顺序表是否为空
	assert(ps->arr && ps->size);
	for (int i = 0; i < ps->size; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}
//查找位置
int SLfindmember(SL* ps, SLDataType num)
{
	//判断是否为空
	assert(ps->arr);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == num)
		{
			return i;
		}
	}
	return -1;
}
//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType num)
{
	//判断是否为空
	assert(ps->arr&&pos>=0&&pos<ps->size);
	//空间不够,扩容
	SLcheckcapcity(ps);
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = num;
	ps->size++;
}
//在指定位置之后插入数据
void SLInsertAfter(SL* ps, int pos, SLDataType num)
{
	//判段是否为空
	assert(ps->arr && pos >= 0 && pos < ps->size);
	//空间够不够，扩容
	SLcheckcapcity(ps);
	for (int i = ps->size; i > pos + 1; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos + 1] = num;
	ps->size++;
}
//删除pos位置上的数据
void SLdelete(SL* ps, int pos)
{
	//顺序表是否为空
	assert(ps->arr && ps->size);
	for (int i = pos; i < ps->size; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}
//修改指定位置的数据
void SLChange(SL* ps, int pos, SLDataType num)
{
	//判段顺序表是否为空以及位置是否在限度内
	assert(ps->arr && pos >= 0 && pos <= ps->size);
	ps->arr[pos] = num;
}

test.c(测试代码):

代码语言：javascript
复制
#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"
int main()
{
	SL sl;
	//初始化
	SLInt(&sl);
	SLpushBack(&sl, 1);
	SLpushBack(&sl, 2);
	SLpushBack(&sl, 3);
	SLpushBack(&sl, 4);
	SLpushBack(&sl, 5);
	SLpushFront(&sl, 6);
	int pos = SLfindmember(&sl, 2);
	//SLInsertAfter(&sl, pos, 0);
	SLdelete(&sl, pos);
	SLChange(&sl, pos, 8);
	SLprint(&sl);
	SLfree(&sl);
	return 0;
}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-12-30，如有侵权请联系 cloudcommunity@tencent.com 删除
存储
ps
size
数据
数组

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

存储
ps
size
数据
数组
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 一、线性表
  • 二、顺序表
    • 2.1 概念与结构
    • 2.2 顺序表的功能
    • 2.3 顺序表的分类
      • 2.3.1 静态顺序表
      • 2.3.2 动态顺序表
  • 三、动态顺序的具体实现（纯C语言）
    • 3.1 顺序表的初始化
    • 3.2 增加数据
      • 3.2.1 在顺序表的尾部增加数据（尾插）
      • 3.2.2 在顺序表的开头增加数据（头插）
      • 3.2.3 在顺序表的指定位置前增加数据
      • 3.2.4 在顺序表的指定位置后增加数据
    • 3.3 删除数据
      • 3.3.1 尾部删除
      • 3.3.2 头部删除
      • 3.3.3 指定位置删除
    • 3.4 查找数据的位置
    • 3.5 修改数据
    • 3.6 顺序表的打印
    • 3.7 顺序表的销毁
    • 3.8 完整代码
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2026 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论