关注

顺序表 --＞增、删、查、改等详细操作

在这里插入图片描述


个人主页： 流年如梦

专栏： 《C语言》 《数据结构》

文章目录

Ladies and gentlemen，本篇文章先了解一下线性表和顺序表，其中主要学习动态顺序表（重点）；全程高能，不容错过！！！

前言

顺序表是数据结构中最基础、最常用的线性表结构，它以一段物理连续的内存空间存储数据，是数组的封装与升级。本篇文章会实现动态顺序表的初始化、增删查改、扩容、销毁等核心接口，并通过测试代码验证功能；为后续学习链表、栈、队列等数据结构打下扎实基础

一.线性表

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

线性表又分为逻辑结构和物理结构，其中：

逻辑结构 --> 线性结构，连续一条直线
物理结构 --> 不一定连续

(物理储存通常是以数组（顺序表）和链式结构（链表）这两种方式)

二.顺序表

2.1概念与结构

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

顺序表和数组的区别👇：

数组 --> 原生存储空间
顺序表 --> 对数组的封装，实现增、删、改、查等完整接口

可以理解为👇：

数组 --> 基础原料
顺序表 --> 封装好的成品结构（在基础原料的基础上）

2.2静态顺序表

使用定长数组存储元素：

#define N 7
typedef struct SeqList
{
    SLDataType a[N];
    int size;
}SL;

分析：其中a[N]为定长数组，size为有效数据个数；但缺点是空间给少了不够用，给多了造成空间浪费

2.3动态顺序表

2.3.1动态顺序表结构体

动态顺序表按需申请、释放空间，更灵活

typedef struct SeqList
{
    SLDataType* a;
    int size;
    int capacity;
}SL;

分析：其中SLDataType* a为指向动态开辟的数组，size为有效数据个数，capacity为空间容量

2.3.2头文件声明 --> SeqList.h

参考代码如下：

#pragma once
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

//初始容量
#define INIT_CAPACITY 4

//顺序表存储的数据类型
typedef int SLDataType;//SLDataType为int类型

//动态顺序表结构体
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);

//指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x);
//指定位置之前删除数据
void SLErase(SL* ps, int pos);

//查找
int SLFind(SL* ps, SLDataType x);

2.3.3源文件实现 --> SeqList.c

2.3.3.1初始化

对动态顺序表进行初始化

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

🧐分析：把数组指针置空，有效数据个数和容量都清0，assert防止传进来空指针

2.3.3.2销毁

销毁动态顺序表，释放内存

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

🧐分析：必须free掉动态开辟的数组，避免内存泄漏；指针置空、数据置0，防止野指针

2.3.3.3打印

遍历打印顺序表中所有有效数据

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

判断空间是否满了，满了就扩容（一般扩 2 倍，没了再扩）

void SLCheckCapacity(SL* ps)
{
	assert(ps);

	if (ps->size == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? INIT_CAPACITY : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));

		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}
}

🧐分析：第一次扩容给INIT_CAPACITY（4），之后每次扩2倍，用realloc更高效；👉所有插入操作前都要调用它

2.3.3.5尾插尾删

尾插（在顺序表最后插入一个数据）：

void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);

	ps->a[ps->size] = x;
	ps->size++;
}

🧐分析：插入操作先检查扩容，再把数据放到size位置；时间复杂度为O(1)

尾删（删除顺序表最后一个数据）：

void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);

	ps->size--;
}

🧐分析：不用真正删除，只需size--，逻辑删除；使用之前必须断言size>0，防止删空表导致程序崩溃

2.3.3.6头插头删

头插（在顺序表最前面插入数据）：

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++;
}

🧐分析：插入操作先检查扩容，所有数据先向后挪一位，再把数据放在下标为0的位置；时间复杂度为O(N)，效率低

头删（删除第一个数据）：

void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);

	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}

	ps->size--;
}

🧐分析：后面所有数据向前覆盖；时间复杂度为O(N)，效率低

2.3.3.7指定位置插入与删除

插入（在下标pos前插入数据x）：

void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheckCapacity(ps);

	for (int i = ps->size; i > pos; i--)
	{
		ps->a[i] = ps->a[i - 1];
	}

	ps->a[pos] = x;
	ps->size++;
}

🧐分析：pos位置及之后的数据整体后移；必须检查pos合法性 --> 0 ≤ pos ≤ size

删除（删除下标pos位置的数据）：

void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}

	ps->size--;
}

🧐分析：pos后面的数据整体前移覆盖并且注意pos范围为 0 ≤ pos < size

2.3.3.8查找

查找x，找到返回下标，没找到则返回-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;
}

🧐分析：顺序遍历，时间复杂度为O(N)；常用于修改、删除前先定位位置

2.3.4主函数 --> test.c

参考代码如下：

#include "SeqList.h"

void TestSeqList()
{
	SL sl;
	//初始化
	SLInit(&sl);

	//尾插
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	printf("尾插 1 2 3 4：");
	SLPrint(&sl);

	//头插
	SLPushFront(&sl, 0);
	printf("头插 0：");
	SLPrint(&sl);

	//指定位置插入
	SLInsert(&sl, 3, 99);
	printf("在下标3插入99：");
	SLPrint(&sl);

	//查找
	int pos = SLFind(&sl, 3);
	if (pos != -1)
	{
		printf("找到 3，下标是：%d\n", pos);
	}

	//删除指定位置
	SLErase(&sl, 3);
	printf("删除下标3：");
	SLPrint(&sl);

	//头删
	SLPopFront(&sl);
	printf("头删：");
	SLPrint(&sl);

	//尾删
	SLPopBack(&sl);
	printf("尾删：");
	SLPrint(&sl);

	//销毁
	SLDestroy(&sl);
	printf("销毁成功\n");
}

int main()
{
	TestSeqList();//调用函数

	return 0;
}

运行结果：
在这里插入图片描述

🎯总结（动态顺序表）

  1. 动态顺序表是对数组的封装，用连续物理内存存储数据，支持动态扩容
  2. 结构包含三要素：数据指针a、有效数据size、容量capacity
  3. 核心操作：尾插与尾删、头插与头删、指定位置插入删除、查找
  4. 所有接口按模块化实现：.h声明、.c实现、test.c测试
  5. 扩容规则：初始空间容量为4，满了2倍扩容，需要用realloc
  6. 尾插尾删时间复杂度为O(1)，头插头删、中间插入删除的时间复杂度为O(N)（因为需要挪动数据）

⚠️易错点

  1. 忘记断言（assert），空指针访问导致崩溃
  2. 扩容判断错误，未判断size == capacity就扩容
  3. realloc直接赋值，不用临时变量（tmp）接收，易丢失数据
  4. 插入或删除的循环方向或边界写错，造成数据覆盖或越界
  5. 不检查pos合法性，插入删除越界
  6. 空表执行删除，size变负，逻辑异常
  7. 销毁后未置空（NULL），free后不置NULL产生野指针
  8. 扩容后不更新capacity，导致容量逻辑混乱

👀 关注 我们一路同行，从入门到大师，慢慢沉淀、稳步成长
❤️ 点赞 鼓励原创，让优质内容被更多人看见
⭐ 收藏 收好核心知识点与实战技巧，需要时随时查阅
💬 评论 分享你的疑问或踩坑经历，一起交流避坑、共同进步

转载自CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/2502_91744920/article/details/160569609

评论

赞0

评论列表

微信小程序
QQ小程序

关于作者

点赞数：0
关注数：0
粉丝：0
文章：0
关注标签：0
加入于：--