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


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

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

所属专栏：数据结构与算法
贝蒂的主页：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
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/423211.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

迪杰斯特拉算法的具体应用

迪杰斯特拉算法的具体应用

fill与memset的区别介绍 例一 #include <iostream> #include <algorithm> using namespace std; const int maxn500; const int INF1000000000; bool isin[maxn]{false}; int G[maxn][maxn]; int path[maxn],rescue[maxn],num[maxn]; int weight[maxn]; int cityn…
阅读更多...
011 Linux_线程概念与创建

011 Linux_线程概念与创建

前言 本文将会向你介绍线程的概念&#xff0c;以及线程是怎么被创建的 线程概念 一、进程是承担系统资源的基本实体&#xff0c;线程是cpu调度的基本单位 首先&#xff0c;地址空间在逻辑上相当于进程的资源窗口&#xff0c; 每个进程都有这样一个资源窗口。通过地址空间页…
阅读更多...
《热辣滚烫》：用坚持不懈开启逆境中的职场出路

《热辣滚烫》：用坚持不懈开启逆境中的职场出路

"你只活一次&#xff0c;所以被嘲笑也没有关系&#xff0c;想哭也没有关系&#xff0c;失败更没有关系。" “人生就像一场拳击赛&#xff0c;你站不起来&#xff0c;就永远不知道自己有多强” “命运只负责洗牌&#xff0c;出牌的永远是自己。” 在今年的贺岁档电影市…
阅读更多...
MySQL的21个SQL经验

MySQL的21个SQL经验

1. 写完SQL先explain查看执行计划（SQL性能优化） 日常开发写SQL的时候，尽量养成这个好习惯呀：写完SQL后，用explain分析一下，尤其注意走不走索引。 explain select userid,name,age from user where userid =10086 or age =18;2、操作delete或者update语句，加个limit(S…
阅读更多...
C++之stack

C++之stack

1、stack简介 stack是实现的一个先进后出&#xff0c;后进先出的容器。它只有一个出口&#xff0c;只能操作最顶端元素。 2、stack库函数 &#xff08;1&#xff09;push() //向栈压入一个元素 &#xff08;2&#xff09;pop() //移除栈顶元素 &#xff08;3…
阅读更多...
IO多路转接

IO多路转接

1.select 初识select 系统提供 select 函数来实现多路复用输入 / 输出模型 . select 系统调用是用来让我们的程序监视多个文件描述符的状态变化的 ; 程序会停在 select 这里等待&#xff0c;直到被监视的文件描述符有一个或多个发生了状态改变 ; select函数模型 select的函…
阅读更多...
LaTeX-设置表格大小

LaTeX-设置表格大小

文章目录 LaTeX-设置表格大小1.创建表格2.设置表格的宽度2.1控制表格每一列的宽度2.2控制整个表格的宽度 3.设置表格的外观4.LaTeX绘制三线表 LaTeX-设置表格大小 本文介绍了LaTeX如何设置表格的大小、改变表格的外观以及如何绘制三线表。 1.创建表格 在LaTeX中创建表很耗时…
阅读更多...
RocketMQ学习笔记一

RocketMQ学习笔记一

课程来源&#xff1a;002-MQ简介_哔哩哔哩_bilibili &#xff08;尚硅谷老雷&#xff0c;时长19h&#xff09; 第1章 RocketMQ概述 1. MQ是什么&#xff1f; 2. MQ用途有哪些&#xff1f; 限流削峰&#xff1b;异步解耦&#xff1b;数据收集。 3. 常见MQ产品有哪些&对比…
阅读更多...
10-Java装饰器模式 ( Decorator Pattern )

10-Java装饰器模式 ( Decorator Pattern )

Java装饰器模式 摘要实现范例 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其结构 装饰器模式创建了一个装饰类&#xff0c;用来包装原有的类&#xff0c;并在保持类方法签名完整性的前提下&#xff0c;提供…
阅读更多...
测试/测试开发八股——找大厂测试实习基础篇

测试/测试开发八股——找大厂测试实习基础篇

第一部分：基础概念 1. 软件测试是什么？ 在规定的条件下对一个产品或者程序进行操作，以发现程序错误，衡量软件质量，并对其是否能满足设计要求进行评估的过程。 软件测试工程师的任务 2. 软件测试工程师的任务 软件测试工程师主要工作是检查软件是否有bug、是否具有稳定…
阅读更多...
【深度学习笔记】计算机视觉——图像增广

【深度学习笔记】计算机视觉——图像增广

图像增广 sec_alexnet提到过大型数据集是成功应用深度神经网络的先决条件。 图像增广在对训练图像进行一系列的随机变化之后&#xff0c;生成相似但不同的训练样本&#xff0c;从而扩大了训练集的规模。 此外&#xff0c;应用图像增广的原因是&#xff0c;随机改变训练样本可以…
阅读更多...
Spring对IoC的实现

Spring对IoC的实现

个人名片&#xff1a; &#x1f43c;作者简介&#xff1a;一名大三在校生&#xff0c;喜欢AI编程&#x1f38b; &#x1f43b;‍❄️个人主页&#x1f947;&#xff1a;落798. &#x1f43c;个人WeChat&#xff1a;hmmwx53 &#x1f54a;️系列专栏&#xff1a;&#x1f5bc;️…
阅读更多...
GO-并发

GO-并发

1. 并发 有人把Go语言比作 21 世纪的C语言&#xff0c;第一是因为Go语言设计简单&#xff0c;第二则是因为 21 世纪最重要的就是并发程序设计&#xff0c;而 Go 从语言层面就支持并发。同时实现了自动垃圾回收机制。 先来了解一些概念&#xff1a; 进程/线程 进程是程序在操…
阅读更多...
Bootstrap的使用

Bootstrap的使用

目录 js的引入&#xff1a; 1.行内式 2.嵌入式 3.外链式 Bootstrap:的引入 注意事项&#xff1a; 条件注释语句&#xff1a; 栅格系统&#xff1a; 列嵌套&#xff1a; 列偏移&#xff1a; 列排序&#xff1a; 响应式工具&#xff1a; Bootstrap的字体图标的使用&a…
阅读更多...
探讨苹果 Vision Pro 的 AI 数字人形象问题

探讨苹果 Vision Pro 的 AI 数字人形象问题

Personas 的设计模糊性&#xff1a; 部分人认为这种模糊设计可能是出于安全考虑&#x1f6e1;️。安全角度&#xff1a;Personas 代表着你的 AI 数字形象&#xff0c;在创建时&#xff0c;它相当于你的 AVP&#xff08;生物识别扫描器的存在增加了冒充的难度&#xff09;。如果…
阅读更多...
mysql服务治理

mysql服务治理

一、性能监控指标和解决方案 1.QPS 一台 MySQL 数据库&#xff0c;大致处理能力的极限是&#xff0c;每秒一万条左右的简单 SQL&#xff0c;这里的“简单 SQL”&#xff0c;指的是类似于主键查询这种不需要遍历很多条记录的 SQL。 根据服务器的配置高低&#xff0c;可能低端…
阅读更多...
Java ZooKeeper-RocketMQ 面试题

Java ZooKeeper-RocketMQ 面试题

Java ZooKeeper-RocketMQ 面试题 前言1、谈谈你对ZooKeeper的理解 &#xff1f;2、Zookeeper的工作原理&#xff08;Zab协议&#xff09;3、谈谈你对分布式锁的理解&#xff0c;以及分布式锁的实现&#xff1f;4、 zookeeper 是如何保证事务的顺序一致性的&#xff1f;5、 zook…
阅读更多...
使用lnmp环境部署laravel框架需要注意的点

使用lnmp环境部署laravel框架需要注意的点

1&#xff0c;上传项目文件后&#xff0c;需要chmod -R 777 storage授予文件权限&#xff0c;不然会报错file_put_contents(/): failed to open stream: Permission denied。 如果后面还是报错没有权限的话&#xff0c;就执行ps -ef |grep php查询php运行用户。然后执行chown …
阅读更多...
STM32-ADC一步到位学习手册

STM32-ADC一步到位学习手册

1.按部就班陈述概念 ADC 是 Analog-to-Digital Converter 的缩写&#xff0c;指的是模拟/数字转换器。它将连续变量的模拟信号转换为离散的数字信号。在 STM32 中&#xff0c;ADC 具有高达 12 位的转换精度&#xff0c;有多达 18 个测量通道&#xff0c;其中 16 个为外部通道&…
阅读更多...
小朋友来自多少小区 - 华为OD统一考试(C卷)

小朋友来自多少小区 - 华为OD统一考试(C卷)

OD统一考试&#xff08;C卷&#xff09; 分值&#xff1a; 100分 题解&#xff1a; Java / Python / C 题目描述 幼儿园组织活动&#xff0c;老师布置了一个任务&#xff1a; 每个小朋友去了解与自己同一个小区的小朋友还有几个。 我们将这些数量汇总到数组 garden 中。 请…
阅读更多...
最新文章

Copyright @ 2022~2023