探索数据结构：深入了解顺序表的奥秘


✨✨ 欢迎大家来到贝蒂大讲堂✨✨

🎈🎈养成好习惯，先赞后看哦~🎈🎈

所属专栏：数据结构与算法
贝蒂的主页：Betty’s blog

1. 什么是顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，它与数组非常类似，但是相比于数组顺序表有一个非常明显的优点——可以动态内存增长空间大小

2. 顺序表的功能

顺序表可以大致包含以下几个功能：

  1. 初始化顺序表中的数据。

  2. 打印顺序表中的数据。

  3. 对顺序表进行尾插(末尾插入数据)。

  4. 对顺序表中数据进行尾删(末尾删除数据)。

3. 顺序表的定义

定义顺序表我们首先需要一个动态内存开辟的空间，当前数据的个数(size)，以及方便扩容的容量大小(capacity)。

typedef int SLDataType; //类型重命名，方便后续修改类型
#define N 4 //初始化空间大小
typedef struct SeqList
{
	SLDataType* a;    //指向动态开辟的数组
	size_t size;      //有效数据个数
	size_t capacity;  //容量大小
}SeqList;

4. 功能的具体实现

4.1 初始化顺序表

(1) 代码实现

初始化顺序表时我们可以先开辟四个空间，之后不够再进行扩容。

void SeqListInit(SeqList* p)
{
	assert(p);  //断言
	p->a =(SLDataType*)malloc(N*sizeof(SLDataType));  //初始顺序表为四个空间
	if (p == NULL)
	{
		perror("malloc fail:");
                return ;
	}
	p->size = 0;  //初始数据个数为0
	p->capacity = 4;  //初始空间容量为4
}
(2) 复杂度分析
  • 时间复杂度：由于没有其他未知数的引入，所以所需时间是个常数，也就是O(1)。
  • 空间复杂度：动态开辟N个空间，所以空间复杂度为O(N)。

4.2 打印数据

(1) 代码实现

打印数据只用循环打印就可以了。

void SeqListPrint(const SeqList* p)
{
	assert(p);  //断言
	if (p->size == 0)  //判断顺序表是否为空
	{
		printf("顺序表为空\n");
		return;
	}

	int i = 0;
	for (i = 0; i < p->size; i++)  //打印顺序表
	{
		printf("%d ", p->a[i]);
	}
	printf("\n");
}
(2) 复杂度分析
  • 时间复杂度：因为会打印顺序表中的所有数据，所以时间复杂度为O(N)。
  • 空间复杂度：打印顺序表并不需要开辟格外的空间，所以空间复杂度为O(N)。

4.3 尾插数据

尾插数据，顾名思义就是在顺序表末尾插入数据，在插入数据之前我们应该检查顺序表是否为满。

(1) 检查是否已满
void CheckCapacity(SeqList* p)
{
	assert(p);  //断言
	if (p->size == p->capacity)  //检查容量，满了则增容
	{
		size_t newcapacity = 2 * p->capacity;  //，扩容为原来的2倍
		SLDataType* prt = (SLDataType*)realloc(p->a, newcapacity * sizeof(SLDataType));  //扩容
		if (prt == NULL)
		{
			perror("realloc fail:");
			return ;
		}
		p->a = prt;  // prt不为空，开辟成功
		p->capacity = newcapacity;  //更新容量
	}
}
(2) 插入数据
void SeqListPushBack(SeqList* p, SLDataType x)
{
	assert(p);  //断言
	CheckCapacity(p);  //检查顺序表容量是否已满
	p->a[p->size] = x;  //尾插数据
	p->size++;  //有效数据个数+1
}
(3) 复杂度分析
  • 时间复杂度：没有变量影响时间，时间复杂度为O(1)。
  • 空间复杂度：以最坏的情况考虑，会进行扩容，空间复杂度为O(N)。

4.4 尾删数据

同理，尾删数据就是删除顺序表中最后一个元素，我们只需将size–。注意：删除之前要保证顺序表中有数据。

(1) 代码实现
void SeqListPopBack(SeqList* p)
{
	assert(p);  //断言
	assert(p->size > 0);  //顺序表不能为空
	p->size--;  //有效数据个数-1
}
(2) 复杂度分析
  • 时间复杂度：没有变量影响时间，时间复杂度为O(1)。
  • 空间复杂度：没有变量影响空间，空间复杂度为O(N)。

4.5 头插数据

头部插入数据就是在第一个元素位置插入一个元素。

(1) 代码实现
void SeqListPushFront(SeqList* p, SLDataType x)
{
	assert(p);  //断言
	CheckCapacity(p);  //检查顺序表容量是否已满

	int i = 0;
	for (i = p->size - 1; i >= 0; i--)  //顺序表中[0,size-1]的元素依次向后挪动一位
	{
		p->a[i + 1] = p->a[i];
	}
	p->a[0] = x;  //头插数据
	p->size++;  //有效数据个数+1
}
(2) 复杂度分析
  • 时间复杂度：因为从头部插入数据，后续数据需要依次覆盖，所以时间复杂度为O(N)。
  • 空间复杂度：因为可能会进行扩容，按最坏的情况来算，空间复杂度为O(N)。

4.5 头删数据

从头部删除数据，与尾部删除数据不同，需要依次往前覆盖。

(1) 代码实现
void SeqListPopFront(SeqList* p)
{
	assert(p);  //断言
	assert(p->size > 0);  //顺序表不能为空

	int i = 0;
	for (i = 1; i < p->size; i++)  //顺序表中[1,size-1]的元素依次向前挪动一位
	{
		p->a[i - 1] = p->a[i];
	}
	p->size--;  //有效数据个数-1
}
(2) 复杂度分析
  • 时间复杂度：因为需要往前覆盖数据，所以时间复杂度自然为O(N)。
  • 空间复杂度：因为并没有开辟其他空间，所以空间复杂度为O(1)。

4.6 查找指定值

根据输入参数，在顺序表中查找指定的值并返回其下标，若未找到则返回-1。

(1) 代码实现
int SeqListFind(const SeqList* p, SLDataType x)
{
	assert(p);  //断言

	int i = 0;
	for (i = 0; i < p->size; i++)
	{
		if (p->a[i] == x)
		{
			return i;  //查找到，返回该值在数组中的下标
		}
	}
	return -1;  //没有查找到
}
(2) 复杂度分析
  • 时间复杂度：以最坏的情况分析，时间复杂度为O(N)。
  • 空间复杂度：并没有格外的空间消耗，空间复杂度为O(1)。

4.7 指定位置修改

我们可以通过指定下标或者查找指定值的下标来修改任意位置的值。

(1) 代码实现
void SeqListModify(SeqList* p, int pos, SLDataType x)
{
	assert(p);  //断言
	assert(p->size > 0);  //顺序表不能为空
	assert(pos >= 0 && pos < p->size);  //检查pos下标的合法性
	p->a[pos] = x;  //修改pos下标处对应的数据
}
(2) 复杂度分析
  • 时间复杂度：因为是通过指定下标修改，所以时间复杂度为O(1)。
  • 空间复杂度：没有开辟额外的空间，所以空间复杂度为O(1)。

4.8 指定位置插入

和前面其他插入一样，指定位置插入也需要判断是否扩容。

(1) 代码实现
void SeqListInsert(SeqList* p, int pos, SLDataType x)
{
	assert(p);//断言
	assert(pos <= p->size); //检查pos下标的合法性
	SeqListCheck(p);//扩容
	int cur = p->size;
	while (cur > pos)
	{
		p->a[cur] = p->a[cur - 1];//覆盖
		--cur;
	}
	p->a[pos] = x;
	p->size++;
}
(2) 复杂度分析
  • 时间复杂度：需要依次覆盖，时间复杂度为O(N)。
  • 空间复杂度：可能需要扩容，空间复杂度为O(N)。

4.9 指定位置删除

和前面的删除差不多，但是指定删除可能会依次覆盖。

(1) 代码实现
void SeqListErase(SeqList* p, int pos)
{
	assert(p);  //断言
	assert(p->size > 0);  //顺序表不能为空
	assert(pos >= 0 && pos < p->size);  //检查pos下标的合法性
	int i = 0;
	for (i = pos + 1; i < p->size; i++)  //将pos位置后面的数据依次向前挪动一位
	{
		p->a[i - 1] = p->a[i];
	}
	p->size--;  //有效数据个数-1
}
(2) 复杂度分析
  • 时间复杂度：需要依次覆盖，时间复杂度为O(N)。
  • 空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。

4.10 回收空间

在结束操作之后，需要释放开辟的空间，以防止内存泄漏。

(1) 代码实现
void SeqListDestory(SeqList* p)
{
	assert(p);  //断言
	free(p->a);   //释放动态开辟的空间
	p->a = NULL;  //置空
	p->size = 0;  //数据个数置0
	p->capacity = 0;  //空间容量大小置0
}
(2) 复杂度分析
  • 时间复杂度：没有额外的时间消耗，时间复杂度为O(1)。
  • 空间复杂度：没有额外的空间消耗，空间复杂度为O(1)。

5. 完整代码

5.1 SeqList.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define N 4 //初始化空间大小
typedef int SLDataType; //类型重命名，方便后续修改类型
typedef struct SeqList
{
	SLDataType* a;    //指向动态开辟的数组
	size_t size;      //有效数据个数
	size_t capacity;  //容量大小
}SeqList;

void SeqListInit(SeqList* p);//初始化顺序表
void SeqListPrint(const SeqList* p);//打印顺序表
void SeqListPushBack(SeqList* p, SLDataType x);//尾插
void SeqListPopBack(SeqList* p);//尾删
void SeqListPushFront(SeqList* p, SLDataType x);//头插
void SeqListPopFront(SeqList* p);//头删
int SeqListFind(const SeqList* p, SLDataType x);//查找数据
void SeqListModify(SeqList* p, int pos, SLDataType x);//修改数据
void SeqListInsert(SeqList* p, int pos, SLDataType x);//指定插入
void SeqListErase(SeqList* p, int pos);//指定删除
void SeqListDestory(SeqList* p);//释放空间

5.2 SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
void SeqListInit(SeqList* p)
{
	assert(p);  //断言
	p->a =(SLDataType*)malloc(N*sizeof(SLDataType));  //初始顺序表为四个空间
	if (p == NULL)
	{
		perror("malloc fail:");
		return ;
	}
	p->size = 0;  //初始数据个数为0
	p->capacity = 4;  //初始空间容量为4
}
void CheckCapacity(SeqList* p)
{
	assert(p);  //断言

	if (p->size == p->capacity)  //检查容量，满了则增容
	{
		size_t newcapacity = 2 * p->capacity;  //，扩容为原来的2倍
		SLDataType* prt = (SLDataType*)realloc(p->a, newcapacity * sizeof(SLDataType));  //扩容
		if (prt == NULL)
		{
			perror("realloc");
			return ;
		}
		p->a = prt;  // prt不为空，开辟成功
		p->capacity = newcapacity;  //更新容量
	}
}
void SeqListPushBack(SeqList* p, SLDataType x)
{
	assert(p);  //断言
	CheckCapacity(p);  //检查顺序表容量是否已满
	p->a[p->size] = x;  //尾插数据
	p->size++;  //有效数据个数+1
}
void SeqListPrint(const SeqList* p)
{
	assert(p);  //断言
	if (p->size == 0)  //判断顺序表是否为空
	{
		printf("顺序表为空\n");
		return;
	}

	int i = 0;
	for (i = 0; i < p->size; i++)  //打印顺序表
	{
		printf("%d ", p->a[i]);
	}
	printf("\n");
}
void SeqListPopBack(SeqList* p)
{
	assert(p);  //断言
	assert(p->size > 0);  //顺序表不能为空
	p->size--;  //有效数据个数-1
}
void SeqListPushFront(SeqList* p, SLDataType x)
{
	assert(p);  //断言
	CheckCapacity(p);  //检查顺序表容量是否已满

	int i = 0;
	for (i = p->size - 1; i >= 0; i--)  //顺序表中[0,size-1]的元素依次向后挪动一位
	{
		p->a[i + 1] = p->a[i];
	}
	p->a[0] = x;  //头插数据
	p->size++;  //有效数据个数+1
}
void SeqListPopFront(SeqList* p)
{
	assert(p);  //断言
	assert(p->size > 0);  //顺序表不能为空

	int i = 0;
	for (i = 1; i < p->size; i++)  //顺序表中[1,size-1]的元素依次向前挪动一位
	{
		p->a[i - 1] = p->a[i];
	}
	p->size--;  //有效数据个数-1
}
int SeqListFind(const SeqList* p, SLDataType x)
{
	assert(p);  //断言

	int i = 0;
	for (i = 0; i < p->size; i++)
	{
		if (p->a[i] == x)
		{
			return i;  //查找到，返回该值在数组中的下标
		}
	}
	return -1;  //没有查找到
}
void SeqListModify(SeqList* p, int pos, SLDataType x)
{
	assert(p);  //断言
	assert(p->size > 0);  //顺序表不能为空
	assert(pos >= 0 && pos < p->size);  //检查pos下标的合法性
	p->a[pos] = x;  //修改pos下标处对应的数据
}
void SeqListInsert(SeqList* p, int pos, SLDataType x)
{
	assert(p);//断言
	assert(pos <= p->size); //检查pos下标的合法性
	SeqListCheck(p);//扩容
	int cur = p->size;
	while (cur > pos)
	{
		p->a[cur] = p->a[cur - 1];//覆盖
		--cur;
	}
	p->a[pos] = x;
	p->size++;
}
void SeqListErase(SeqList* p, int pos)
{
	assert(p);  //断言
	assert(p->size > 0);  //顺序表不能为空
	assert(pos >= 0 && pos < p->size);  //检查pos下标的合法性
	int i = 0;
	for (i = pos + 1; i < p->size; i++)  //将pos位置后面的数据依次向前挪动一位
	{
		p->a[i - 1] = p->a[i];
	}
	p->size--;  //有效数据个数-1
}
void SeqListDestory(SeqList* p)
{
	assert(p);  //断言
	free(p->a);   //释放动态开辟的空间
	p->a = NULL;  //置空
	p->size = 0;  //数据个数置0
	p->capacity = 0;  //空间容量大小置0
}

http://www.niftyadmin.cn/n/5402851.html

相关文章

【贪心算法】 55. 跳跃游戏

【贪心算法】 55. 跳跃游戏

55. 跳跃游戏 解题思路 定义变量 n 来存储数组 nums 的长度。初始化 farthest 变量为 0&#xff0c;用于记录当前能够到达的最远距离。使用一个 for 循环遍历数组&#xff0c;但是不包括数组的最后一个元素&#xff0c;因为我们的目标是看是否能到达最后一个位置。在循环内部…
阅读更多...
『大模型笔记』Sora：探索大型视觉模型的前世今生、技术内核及未来趋势

『大模型笔记』Sora：探索大型视觉模型的前世今生、技术内核及未来趋势

Sora：探索大型视觉模型的前世今生、技术内核及未来趋势 文章目录 一. 摘要二. 引言杨立昆推荐的关于世界模型的真正含义（或应该是什么）的好文章。原文：Sora: A Review on Background, Technology, Limitations, and Opportunities of Large Vision Models译文：Sora探索大型…
阅读更多...
Laravel Octane 和 Swoole 协程的使用分析

Laravel Octane 和 Swoole 协程的使用分析

之前在工作中使用 Laravel Octane 的 concurrently 处理并发时&#xff0c;发现在队列和定时任务中不会触发并发效果。经过分析&#xff0c;作了如下猜测&#xff1a;队列和定时任务都属于一个独立的进程&#xff0c;与 Octane 服务无关&#xff0c;而 Octane concurrently 恰恰…
阅读更多...
【Spring连载】使用Spring Data访问 MongoDB----对象映射之基于类型的转换器

【Spring连载】使用Spring Data访问 MongoDB----对象映射之基于类型的转换器

【Spring连载】使用Spring Data访问 MongoDB----对象映射之基于类型的转换器 一、自定义转换二、转换器消歧(Disambiguation)三、基于类型的转换器3.1 写转换3.2 读转换3.3 注册转换器 一、自定义转换 下面的Spring Converter实现示例将String对象转换为自定义Email值对象: R…
阅读更多...
Linux笔记-1

Linux笔记-1

概述 简介 Linux是现在服务器上最常用的操作系统(OS - Operating system) - 所谓的操作系统本质上也是一个软件&#xff0c;是一个可以运行其他软件的容器如果一台服务器&#xff0c;没有安装操作系统&#xff0c;此时称之为裸机。裸机可以使用&#xff0c;在使用的时候需要使…
阅读更多...
spring-data Page/Sort类型 jackson序列化模块

spring-data Page/Sort类型 jackson序列化模块

版本 springboot:3.2.2 问题 使用Page/Sort类型作为controller参数时无法被正确解析 添加jackson模块支持反序列化 注&#xff1a;如果项目使用了spring-cloud-openfeign-core模块则会自动配置这两个类型的反序列化支持 Page import com.fasterxml.jackson.databind.Mod…
阅读更多...
线段树模型及例题整理

线段树模型及例题整理

线段树的应用范围非常广&#xff0c;可以处理很多与区间有关的题目。 将区间抽象成一个节点&#xff0c;在这个节点中储存这个区间的一些值&#xff0c;那么如果看成节点的话&#xff0c;这就很像一棵满二叉树&#xff0c;所以我们可以用一维数组来储存节点。那么就要考虑父子节…
阅读更多...
python 基础知识点（蓝桥杯python科目个人复习计划57）

python 基础知识点（蓝桥杯python科目个人复习计划57）

今日复习计划&#xff1a;做题 例题1&#xff1a;笨笨的机器人 问题描述&#xff1a; 肖恩有一个机器人&#xff0c;他能根据输入的指令移动相应的距离。但是这个机器人很笨&#xff0c;他永远分不清往左边还是往右边移动。肖恩也知道这一点&#xff0c;所以他设定这个机器人…
阅读更多...
最新文章

Copyright @ 2022~2023