• 拿捏 顺序表(1)

    目录

    前言:
    一天xxx想存储一组数据, 并且能够轻松的实现删除和增加, 此时数组大胆站出, 但是每次都需要遍历一遍数组, 来确定已经存储的元素个数, 太麻烦了, 于是迎来了顺序表不屑的调侃: 数组你不行啊…

    顺序表是一种常见的数据结构，它是由一组连续的存储单元组成的线性表。顺序表的优点是可以随机存取，即可以通过下标直接访问元素，查找和更新操作的时间复杂度为O(1)。同时，顺序表还可以通过动态扩容来实现自动调整大小，使得其具有灵活性。本文将介绍顺序表的定义、操作以及一些应用场景，帮助读者更好地理解和应用顺序表。

    博客主页: 酷酷学!!! 感谢关注❤

    正文开始

    1. 顺序表的分类

    顺序表的底层结构就是数组，对数组的封装，实现了常用的增删改查等接,
    也就是顺序表是站在数组的肩膀上飞黄腾达.

    顺序表又分为静态和动态

    静态顺序表:
    概念：使用定长数组存储元素

    在这里插入图片描述
    这里有个缺陷: 空间给少了不够用, 给多了造成浪费, 于是直接pass

    动态顺序表 :
    在这里插入图片描述
    弥补了缺陷: 就你了,下面进行实现

    2. 顺序表实现

    第一步:
    首先完成顺序表我们分成三个源文件来完成, 这样看起来代码更舒服

    在这里插入图片描述

    //我们这里创建三个源文件
//Seqlist.h 用来放文件的声明已经类型的定义
//Seqlist.c 用来放顺序表实现的方法
//test.c 用来进行代码测试

    • 1
    • 2
    • 3
    • 4

    第二步:
    我们直接在头文件声明结构体, 并且进行一些函数的声明

    //直接在.h包含头文件, 以方便我们直接使用
#pragma once//以下声明只会包含一次, 提高代码效率
#include
#include
#include

typedef int SeqDataType;//自定义类型名,方便后期修改存储数据类型

typedef struct SeqList
{
	SeqDataType* arr;
	int size;
	int capacity;
}SL;//声明结构体类型,自定义类型名为SL

void SLInit(SL* ps);//初始化函数声明
void SLDestory(SL* ps);//销毁函数声明

void SLCheckCapacity(SL* ps);//判断空间容量函数声明
void SLPushBack(SL* ps, SeqDataType x);//尾插汉书声明
void SLPushFront(SL* ps, SeqDataType x);//头插函数声明

void SLprint(SL ps);//打印内容函数

void SLPopBack(SL* ps);//尾删函数
void SLpopFront(SL* ps);//头删函数


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    第三步:
    来到.Seqlist.c 封装各类函数

    初始化:

    void SLInit(SL* ps)
{
	assert(ps);//不可以给我传个NULL哦,之后每次参数为指针最好都断言一下
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    销毁操作:

    void SLDestory(SL* ps)
{
	assert(ps);
	if (ps->arr)//如果arr里面有内容,那么就释放这块内存, 我们之后会动态开辟内存
	{
		free(ps->arr);
	}
	ps->arr = NULL;//避免成为野指针
	ps->capacity = ps->size = 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    第四步:
    前期准备工作已完成, 下面进行代码高速

    首先完成怎么插入, 但是有一个问题: 如果这个顺序表大小为0, 或者大小满了的情况下我们怎么插入呢? 所以我们要进行先判断空间容量, 但是后期我们可能还要进行头插操作是不是也要判断一次, 好麻烦欸, 干脆直接封装成函数, 这样更简洁

    于是乎:

    void SLCheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)//没空间或者满了,这不就是需要扩容吗
	{
		int Newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		//如果第一次没空间让它开辟个四块内存,不够再成倍给
		SeqDataType* tmp = (SeqDataType*)realloc(ps->arr, Newcapacity * sizeof(SeqDataType));
		//不要忘记realloc申请失败可是会返回NULL,直接赋值会造成内存泄露,不如交给临时变量
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		ps->arr = tmp;//没问题再给ps->arr
		tmp = NULL;//不需要的指针变量可以拴起来
		ps->capacity = Newcapacity;//修改空间容量大小
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    第五步:实现头插尾插

    先看尾插(因为比较简单)

    //尾插
void SLPushBack(SL* ps, SeqDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	ps->arr[ps->size++] = x;
}//寥寥三行,这不比数组简单?

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    头插:

    void SLPushFront(SL* ps, SeqDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	for (int i = ps->size; i>0; i--)
	{
		ps->arr[i] = ps->arr[i-1];//最后一次ps->arr[1] = ps->arr[0]
	}//参考下图
	ps->arr[0] = x;
	ps->size++;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    在这里插入图片描述

    我们是不是需要由左图变成右图呀, 给第一个位置空出来

    第六步:
    当然了, 我们也可以实验一下前面的代码正不正确,于是乎我们可以让控制台打印, 不妨写如下函数:

    void SLprint(SL ps)
{
	for (int i = 0; i < ps.size; i++)
	{
		printf("%d ", ps.arr[i]);
	}
	printf("\n");
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    我举个栗子:
    我们不妨在test.c里面写上如下代码,看看成功与否

    #include "Seqlist.h"

int main()
{

	SL s;
	SLInit(&s);
	SLPushBack(&s, 4);
	SLPushBack(&s, 3);
	SLPushBack(&s, 2);
	SLPushBack(&s, 1);
	SLprint(s);

	SLPushFront(&s, 3);
	SLPushFront(&s, 4);
	SLprint(s);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    我只能说轻松拿捏:
    在这里插入图片描述

    最后一步:

    实现删除操作:

    先来尾删(因为简单)

    void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);
	ps->size--;
}//想一想为什么这么简单,就是这么简单,因为最后那个位置直接可以被其它值覆盖

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    接着头删:

    void SLpopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);
	for (int i = 0; i <=ps->size-2 ; i++)
	{
		ps->arr[i] = ps->arr[i + 1];//最后一次arr[size-2] = arr[size-1]
	}//看下图:
	ps->size--;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    这里我们依旧需要由左边变成右边想想看是不是
    在这里插入图片描述

    okok,到此我们顺序表已经全部结束, 欲知后事如何,请见下回讲解,点个关注不迷路

    下面直接开始今天的代码测试

    #include "Seqlist.h"

int main()
{

	SL s;
	SLInit(&s);
	SLPushBack(&s, 4);
	SLPushBack(&s, 3);
	SLPushBack(&s, 2);
	SLPushBack(&s, 1);
	SLprint(s);

	SLPushFront(&s, 3);
	SLPushFront(&s, 4);
	SLprint(s);

	SLPopBack(&s);
	SLprint(s);

	SLpopFront(&s);
	SLprint(s);
	SLDestory(&s);
	
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    没有一点容错, 学废了吗
    在这里插入图片描述

    3. 顺序表实现完整代码

    Seqlist.h

    #pragma once
#include
#include
#include

typedef int SeqDataType;

typedef struct SeqList
{
	SeqDataType* arr;
	int size;
	int capacity;
}SL;

void SLInit(SL* ps);
void SLDestory(SL* ps);

void SLCheckCapacity(SL* ps);
void SLPushBack(SL* ps, SeqDataType x);
void SLPushFront(SL* ps, SeqDataType x);

void SLprint(SL ps);

void SLPopBack(SL* ps);
void SLpopFront(SL* ps);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    Seqlist.c

    #include"Seqlist.h"

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

void SLDestory(SL* ps)
{
	assert(ps);
	if (ps->arr)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

void SLCheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		int Newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SeqDataType* tmp = (SeqDataType*)realloc(ps->arr, Newcapacity * sizeof(SeqDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = Newcapacity;
	}
}

//尾插
void SLPushBack(SL* ps, SeqDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	ps->arr[ps->size++] = x;
}

void SLPushFront(SL* ps, SeqDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	for (int i = ps->size; i>0; i--)
	{
		ps->arr[i] = ps->arr[i-1];//最后一次ps->arr[1] = ps->arr[0]
	}
	ps->arr[0] = x;
	ps->size++;
}

void SLprint(SL ps)
{
	for (int i = 0; i < ps.size; i++)
	{
		printf("%d ", ps.arr[i]);
	}
	printf("\n");
}

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

void SLpopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);
	for (int i = 0; i <=ps->size-2 ; i++)
	{
		ps->arr[i] = ps->arr[i + 1];//arr[size-2] = arr[size-1]
	}
	ps->size--;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83

    test.c

    #include "Seqlist.h"

int main()
{

	SL s;
	SLInit(&s);
	SLPushBack(&s, 4);
	SLPushBack(&s, 3);
	SLPushBack(&s, 2);
	SLPushBack(&s, 1);
	SLprint(s);

	SLPushFront(&s, 3);
	SLPushFront(&s, 4);
	SLprint(s);

	SLPopBack(&s);
	SLprint(s);

	SLpopFront(&s);
	SLprint(s);
	
	SLDestory(&s);
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    4. 总结

    顺序表是一种线性数据结构，用于存储具有相同数据类型的数据元素。它通过一片连续的存储空间来存储数据，可以按照元素的物理顺序来访问和操作。

    在顺序表中，元素的存储位置是连续的，可以通过下标来访问元素。通过下标，可以快速访问和修改顺序表中的元素，这是顺序表的一个重要特点。

    顺序表的插入操作比较复杂，需要将插入位置之后的所有元素后移一位，然后将新元素插入到空出的位置。删除操作也类似，需要将删除位置之后的所有元素前移一位，然后将最后一个元素删除。

    顺序表的优点是存储和访问元素的效率高，可以随机访问元素。而缺点是插入和删除操作的效率相对较低，需要进行大量的数据迁移。

    顺序表适用于元素数量固定且不经常变动的场景，例如存储静态的数据集合。在元素数量会经常变动的情况下，使用链表等动态数据结构更为合适。

    总之，顺序表是一种经典的线性数据结构，具有高效的存储和访问性能。但在插入和删除操作上稍显不足，适用于元素数量固定且不经常变动的场景。

    看完, 记得点个关注

  • 相关阅读:
    docker的简介--安装--操作命令
    【Spring MVC】统一功能处理
    什么是指令微调（LLM）
    java日期类选择
    013-json
    [MAUI]模仿iOS多任务切换卡片滑动的交互实现
    【.Net8教程】(二)原始字符串字面量
    59. 螺旋矩阵 II
    2台nginx只需配置一台，另外一台直接生效
    刷题记录:HDU - 3001Travelling
  • 原文地址：https://blog.csdn.net/2201_75644377/article/details/138039103