数据结构：顺序表的奥秘

🎉个人名片：

🐼作者简介：一名乐于分享在学习道路上收获的大二在校生
🐻‍❄个人主页🎉：GOTXX
🐼个人WeChat：ILXOXVJE
🐼本文由GOTXX原创，首发CSDN🎉🎉🎉
🕊系列专栏：零基础学习C语言----- 数据结构的学习之路
🐓每日一句：如果没有特别幸运，那就请特别努力！🎉🎉🎉
————————————————

🎉文章简介：

🎉本篇文章对   用C语言实现顺序表 学习的相关知识进行分享！🎉

如果您觉得文章不错，期待你的一键三连哦，你的鼓励是我创作动力的源泉，让我们一起加油，一起奔跑，让我们顶峰相见！！！🎉🎉🎉

目录

一.顺序表的概念及存储结构

1.1储存结构

二.顺序表的实现

一.功能函数的实现

1.初始化函数

2.顺序表的销毁

3.顺序表的打印

4.扩容函数

5.尾插函数

6.尾删函数

7.头插函数

8.头删函数

9.插入函数

10.删除函数

11.查找函数

12.修改函数

三.总代码

四.顺序表的性能分析

一.顺序表的概念及存储结构

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

顺序表可以分为静态顺序表和动态顺序表。

1.1储存结构

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

动态顺序表：数组的大小是根据存储的数据个数，如果满了就动态开辟出来的，相对而言不会造成空间的浪费；

二.顺序表的实现

静态顺序表 只适用于确定知道需要存多少数据的场景；

静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。例如：如果数组的大小定为200，却只储存了几十个数据，和动态的顺序表相比，空间浪费更大；所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

一.功能函数的实现（含图解）

1.初始化函数

功能：对结构体内成员进行初始化操作；

代码实现：

void InitList(SL* s)
{
	assert(s);        //断言，防止传入空指针

	s->a = (SLDateType* )malloc(sizeof(SLDateType) * 4);  
	if (s->a == NULL)   //这里最开始开辟四个存储数据类型的大小
	{
		perror("malloc fail");
		exit(-1);
	}
	s->size = 0;            //存储的有效数据个数为0
	s->capacity = 4;       //空间置成4
}

2.顺序表的销毁

功能：对动态开辟的空间进行销毁，空间释放

代码实现：

void DestoryList(SL* s)
{
	assert(s);

	free(s->a);       //释放动态开辟的空间
	s->a = NULL;      //置空
	s->capacity = s->size = 0;
}

3.顺序表的打印

代码实现：

void SListPrintf(SL* s)
{
	assert(s);

	if (s->size < 0)     //如果没有数据，则直接返回
	{
		return;
	}
	for (int i = 0; i < s->size; i++)
	{
		printf("%d ", s->a[i]);       //遍历依次打印
	}
	printf("\n");        //打印完换行
}

4.扩容函数

功能：检查是否需要扩容

代码实现：

void CheckCapacity(SL* s)
{
	assert(s);

	if (s->capacity == s->size)    //相等则说明空间已经满了
	{
		SLDateType* tmp = realloc(s->a, sizeof(SLDateType)* 2 * s->capacity);  //二倍扩容
		if (tmp == NULL)    
		{
			perror("realloc fail");
			exit(-1);
		}

		s->a = tmp;
		s->capacity *= 2;

	}
}

5.尾插函数

功能：在顺序表最后插入一个数据

代码实现：

void PushBack(SL* s, SLDateType n)
{
	assert(s);

	CheckCapacity(s);  //检查空间是否满
	s->a[s->size] = n;    //直接插入到数组最后
	s->size++;       //有效数据个数++
}

6.尾删函数

功能: 删除顺序表的最后一个数据

代码实现：

void PopBack(SL* s)
{
	assert(s);
	assert(s->size > 0);     //当数组中有效数据个数为0时，不能再删除

	s->size--;         //数据个数--

}

7.头插函数

功能：在顺序表最前面插入一个数据

代码实现：

void PushFront(SL* s, SLDateType n)
{
	assert(s);
	CheckCapacity(s);    //检查扩容

	int end = s->size;    
	while (end>0) 
	{
		s->a[end] = s->a[end - 1];   //挪动数据
		end--;
	}
	s->a[0] = n;         
	s->size++;
}

图解：

性能分析：头插一个数据，首先需要将全部数据一次往后挪一个位置，时间复杂度：O(N)   

是在原数组上进行挪动的，空间复杂度：O(1)

8.头删函数

功能：删除表中第一个元素

代码实现：

void Popfront(SL* s)
{
	assert(s);
	assert(s->size > 0);   //size为0时，不能再删除

	for (int i = 0; i < s->size; i++)
	{
		s->a[i] = s->a[i+1];      //向前挪动数据
	}

	s->size--;
}

图解：

性能分析：头删一个数据，首先需要将全部数据一次往前挪一个位置，将第一个元素覆盖掉，时间复杂度：O(N)   

是在原数组上进行挪动的，空间复杂度：O(1)

9.插入函数

功能：在某个位置插入一个数据

代码实现：


void SListInsert(SL* s, int pos, SLDateType n)
{
	assert(s);
	assert(pos >= 0 && pos <= s->size);    //判断pos合法

	int end = s->size;
	int begin = pos;
	while (begin < end)
	{
		s->a[end] = s->a[end - 1];   //挪动数据
		end--;
	}
	s->a[pos] = n;       //修改数据
	s->size++;
}

图解：

性能分析：中间插入一个数据和头插差不多，首先需要将该位置后面的全部数据依次往后挪一个位置，将该位置空出来，再将该数据插入，时间复杂度：O(N)   

是在原数组上进行挪动的，空间复杂度：O(1)

10.删除函数

功能：删除数组中任何位置的数据

代码实现：

void SListErase(SL* s, int pos)
{
	assert(s);
	assert(pos >= 0 && pos < s->size);    //pos范围合法判断

	int cur = pos;
	while (cur < s->size)
	{
		s->a[cur] = s->a[cur+1];    //挪动位置
		cur++;
	}
	s->size--;

}

图解：

性能分析：删除一个数据与头删差不多，首先需要待删数据位置后面全部数据依次往前挪一个位置，将待删元素覆盖掉，时间复杂度：O(N)   

是在原数组上进行挪动的，空间复杂度：O(1)

11.查找函数

功能：查找顺序表中某个数据，返回下标

代码实现：

int SListFind(SL* s,SLDateType n)
{
	assert(s);

	for (int i = 0; i < s->size; i++)    //遍历寻找
	{
		if (s->a[i] == n)     //找到了返回下标
		{ 
			return i;
		}
	}

	printf("顺序表中无该数据\n");   
	exit(-1);

}

性能分析：将数组中的数据遍历一遍；时间复杂度：O(N)

空间复杂度：O(1)

12.修改函数

功能：修改数组中某个数据

代码实现：

void SListModify(SL* s, int pos,SLDateType n)
{
	assert(s);
	assert(pos >= 0 && pos < s->size);

	s->a[pos] = n;     //直接通过下标访问修改
}

三.总代码

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


typedef int SLDateType;

struct SeqList
{
	SLDateType* a;      //指向一个数组的指针
	int size;           //记录数据个数
	int capacity;       //记录容量，如果与数据个数相等就扩容
};

typedef struct SeqList SL;


void InitList(SL* s);

void SListPrintf(SL* s);

void PushBack(SL* s, SLDateType n);
void PushFront(SL* s, SLDateType n);
void PopBack(SL* s);
void Popfront(SL* s);

int SListFind(SL* s,SLDateType n);

void SListModify(SL* s, int pos, SLDateType n);
void SListErase(SL* s, int pos);
void SListInsert(SL* s, int pos, SLDateType n);


void DestoryList(SL* s);


#include"SeqList.h"



void InitList(SL* s)
{
	assert(s);        //断言，防止传入空指针

	s->a = (SLDateType* )malloc(sizeof(SLDateType) * 4);  
	if (s->a == NULL)   //这里最开始开辟四个存储数据类型的大小
	{
		perror("malloc fail");
		exit(-1);
	}
	s->size = 0;            //存储的有效数据个数为0
	s->capacity = 4;       //空间置成4
}

void SListPrintf(SL* s)
{
	assert(s);

	if (s->size < 0)     //如果没有数据，则直接返回
	{
		return;
	}
	for (int i = 0; i < s->size; i++)
	{
		printf("%d ", s->a[i]);       //遍历依次打印
	}
	printf("\n");        //打印完换行
}


void CheckCapacity(SL* s)
{
	assert(s);

	if (s->capacity == s->size)    //相等则说明空间已经满了
	{
		SLDateType* tmp = realloc(s->a, sizeof(SLDateType)* 2 * s->capacity);  //二倍扩容
		if (tmp == NULL)    
		{
			perror("realloc fail");
			exit(-1);
		}

		s->a = tmp;
		s->capacity *= 2;

	}
}

void PushBack(SL* s, SLDateType n)
{
	assert(s);

	CheckCapacity(s);  //检查空间是否满
	s->a[s->size] = n;    //直接插入到数组最后
	s->size++;       //有效数据个数++
}

void PushFront(SL* s, SLDateType n)
{
	assert(s);
	CheckCapacity(s);    //检查扩容

	int end = s->size;    
	while (end>0) 
	{
		s->a[end] = s->a[end - 1];   //挪动数据
		end--;
	}
	s->a[0] = n;         
	s->size++;
}

void PopBack(SL* s)
{
	assert(s);
	assert(s->size > 0);     //当数组中有效数据个数为0时，不能再删除

	s->size--;         //数据个数--

}


void Popfront(SL* s)
{
	assert(s);
	assert(s->size > 0);   //size为0时，不能再删除

	for (int i = 0; i < s->size; i++)
	{
		s->a[i] = s->a[i+1];      //向前挪动数据
	}

	s->size--;
}


int SListFind(SL* s,SLDateType n)
{
	assert(s);

	for (int i = 0; i < s->size; i++)    //遍历寻找
	{
		if (s->a[i] == n)     //找到了返回下标
		{ 
			return i;
		}
	}
	printf("顺序表中无该数据\n");   
	exit(-1);
}

void SListModify(SL* s, int pos,SLDateType n)
{
	assert(s);
	assert(pos >= 0 && pos < s->size);

	s->a[pos] = n;     //直接通过下标访问修改
}


void SListErase(SL* s, int pos)
{
	assert(s);
	assert(pos >= 0 && pos < s->size);    //pos范围合法判断

	int cur = pos;
	while (cur < s->size)
	{
		s->a[cur] = s->a[cur+1];    //挪动位置
		cur++;
	}
	s->size--;

}

void SListInsert(SL* s, int pos, SLDateType n)
{

	assert(s);
	assert(pos >= 0 && pos <= s->size);    //判断pos合法

	int end = s->size;
	int begin = pos;
	while (begin < end)
	{
		s->a[end] = s->a[end - 1];   //挪动数据
		end--;
	}

	s->a[pos] = n;       //修改数据
	s->size++;
}


void DestoryList(SL* s)
{
	assert(s);

	free(s->a);       //释放动态开辟的空间
	s->a = NULL;      //置空
	s->capacity = s->size = 0;
}

四.顺序表的性能分析

问题：


1. 中间/头部的插入删除，时间复杂度为O(N);
2. 增容需要申请新空间，拷贝数据，释放旧空间,会有不小的消耗;
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间;

思考：如何解决以上问题呢？

下一章链表结构就可以解决这个问题；

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

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

相关文章

医药行业五大难题深度剖析：CRM解决方案助力突围

医药行业五大难题深度剖析：CRM解决方案助力突围

医疗行业关系着民生、经济乃至战备&#xff0c;是国民经济的重要组成部分。虽然近20年来我国医疗行业年均增长率维持在15%之上&#xff0c;但行业发展仍存在诸多问题。引进CRM管理系统可能是一个行之有效的解决方法。文中将为您整理医疗行业目前的五大挑战&#xff0c;以及CRM如…
阅读更多...
跟无神学AI之Tensorflow笔记搭建网络八股

跟无神学AI之Tensorflow笔记搭建网络八股

虽然Pytorch在论文中使用较多&#xff0c;但是像Alphafold在蛋白质结构预测的模型&#xff0c;仍然是用Tensorflow写成&#xff0c;遂近期在学其中的语法。 本系列来自慕课北大软微曹健老师的Tensorflow笔记&#xff0c;摘选其中重要部分。 1.导包 2.定义训练集测试集和数据…
阅读更多...
专题1 - 双指针 - leetcode 15. 三数之和 - 中等难度

专题1 - 双指针 - leetcode 15. 三数之和 - 中等难度

leetcode 15. 三数之和 - 点击直达 leetcode 15. 三数之和 中等难度 双指针1. 题目详情1. 原题链接2. 基础框架 2. 解题思路1. 题目分析2. 算法原理3. 时间复杂度 3. 代码实现4. 知识与收获 leetcode 15. 三数之和 中等难度 双指针 1. 题目详情 给你一个整数数组 nums &#…
阅读更多...
代码第二十四天-寻找旋转排序数组中的最小值Ⅱ

代码第二十四天-寻找旋转排序数组中的最小值Ⅱ

寻找旋转排序数组中的最小值Ⅱ 题目要求 解题思路 二分法 当遇到两个left、right两个位置值相同时候&#xff0c;可以选择将 right right-1 代码 class Solution:def findMin(self, nums: List[int]) -> int:left,right0,len(nums)-1while left<right:mid(leftright…
阅读更多...
Python编程作业五：面向对象编程

Python编程作业五：面向对象编程

目录 一、类的定义和方法 二、图书管理系统 一、类的定义和方法 定义一个学生类&#xff08;Student&#xff09;&#xff0c;包括学号(id)、姓名(name)、出生日期(birthday)和分数(score)4个属性&#xff0c;其中出生日期是私有属性&#xff0c;不能被外界直接访问。该类应具…
阅读更多...
华容道问题求解_详细设计(三)之查找算法1_DFS

华容道问题求解_详细设计(三)之查找算法1_DFS

&#xff08;续上篇&#xff09; 使用DFS查找算法的原因是因为它符合本人的思考习惯&#xff0c;另外在第一版时用的就是这个方法&#xff0c;后来知道这不是查找这类问题的最好方法。 在前面的概要设计中的框图里描述的方法就是DFS&#xff0c;它可以找到一个解法&#xff0c;…
阅读更多...
某省内存取证真题详解

某省内存取证真题详解

需要环境的私我 题目描述： 一，从内存中获取到用户admin的密码并且破解密码，以Flag{admin,password}形式提交(密码为6位) 二，获取当前系统ip地址及主机名，以Flag{ip:主机名}形式提交； 三，当前系统中存在的挖矿进程，请获取指向的矿池地址，以Flag{ip}形式提交 四，恶意进…
阅读更多...
大数据冷热分离方案

大数据冷热分离方案

数据冷热分离方案 1、背景 ​ 随着业务的发展&#xff0c;在线表中的数据会逐渐增加。常规业务都有冷热数据现象明显的特性&#xff08;需要访问的都是近期产生的热数据&#xff1b;时间久远的冷数据出于备份、备案溯源等诉求会进行在线保留&#xff09;。在业务表数据 量可控…
阅读更多...
问题总结，web自动化测试元素无法操作？shadowDOM节点元素解决......

问题总结，web自动化测试元素无法操作？shadowDOM节点元素解决......

前言 web自动化遇到shadowDOM你会操作吗&#xff1f; 之前在做web自动化的时候&#xff0c;发现页面上有些元素&#xff0c;在selenium中无法通过xpath来定位&#xff0c;各种原因找了半天都没找到解决方案&#xff0c;最后发现元素在一个叫做shadow-root的节点下面&#xff…
阅读更多...
艺术与科技的结合，AI绘画图生图怎么样？

艺术与科技的结合，AI绘画图生图怎么样？

AI绘画图生图是指通过人工智能技术生成的具有艺术价值的图像。它可以根据用户提供的参考图像或描述&#xff0c;自动生成具有艺术风格的新图像。这些图像可以是风景、人物、抽象画等各种形式。那么ai绘画图生图到底怎么样&#xff1f; AI绘画图生图的优点在于它可以快速、高效地…
阅读更多...
R语言安装IDE工具，RStudio 安装

R语言安装IDE工具，RStudio 安装

R语言安装IDE工具&#xff0c;RStudio 安装 介绍下载安装包安装使用运行结果快捷键和使用技巧常用快捷键使用技巧 介绍 RStudio是一个集成开发环境&#xff08;IDE&#xff09;&#xff0c;专门用于R编程语言的开发和数据分析。它提供了许多工具和功能&#xff0c;使R编程更加…
阅读更多...
初始网络 --- 网络基础

初始网络 --- 网络基础

目录 0、 前言 1、 计算机网络发展背景 1.1. 局域网(LAN) && 广域网(WAN) 2、 认识并理解协议 3、 初始网络协议 3.1. 协议分层 4、 TCP/IP 五层(或四层)模型 4.1. 简单了解TCP/IP层状体系 4.2. TCP/IP协议层状结构和计算机层状结构的关系 5、 OSI七层模型 …
阅读更多...
七.AV Foundation 视频播放 - 图片进度条

七.AV Foundation 视频播放 - 图片进度条

引言 播放器的功能功能已经十分完善了&#xff0c;接下来我们给它添加一些提升用户体验的功能。当前市面上的主流播放器几乎都有一个非常友善的功能&#xff0c;用户在退拽进度条的时候可以看见进度条所处进度的视频画面&#xff0c;这对于用户来说是一种直观而且便捷的体验。…
阅读更多...
noetic ros配置因时机械夹爪的驱动

noetic ros配置因时机械夹爪的驱动

noetic ros配置因时机械夹爪的驱动文件 配置编译教程解决方案 配置编译教程 1.inspire_robot 包支持因时机器人公司的机械夹爪在ROS平台上的使用&#xff0c;我们在ros noetic环境下进行了测试。 2.为了使程序能够正常运行&#xff0c;需要执行以下环境配置操作&#xff1a;&a…
阅读更多...
php：下拉列表查询（静态数据+数据库数据）

php：下拉列表查询（静态数据+数据库数据）

一、在php中嵌套 效果 1、从php中嵌套html语句 下拉列表的显示 echo <div class"text-nav-1 required "><div> . _(在职状态) . :</div> <select name"work_status">; // 定义选项数组 $options [all > _(全部),inwork &g…
阅读更多...
越南电力展|2024年第17届越南国际电力设备与技术展览会

越南电力展|2024年第17届越南国际电力设备与技术展览会

2024年第17届越南国际电力设备与技术展览会 The 17th International Exhibition on ELECTRICAL TECHNOLOGY & EQUIPMENT VIETNAM ETE 2023 同期举办&#xff1a;2024 年第 14 届越南节能和绿色能源科技产品博览会 The 14th International Exhibition on PRODUCTS TECHNO…
阅读更多...
C语言--- qsort函数

C语言--- qsort函数

目录 一.qsort函数 1.qsort函数的功能 2.四个参数讲解 (1)base (2)num (3)size (4)compare 3.使用qsort函数对一个整形数组进行排序 4.qsort函数排序结构体数据 第一种&#xff1a;按照年龄进行比较 第二种&#xff1a;按照名字进行排序 二.利用冒泡排序模仿qsort函…
阅读更多...
慢sql优化记录1

慢sql优化记录1

慢sql为&#xff1a; select count(*) from t_wf_process p left join t_wf_core_dofile dofile on p.wf_instance_uid dofile.instanceid join zwkj_department d on p.userdeptid d.department_guid ,t_wf_core_item i,wf_node n where (p.IS_DUPLICATE ! true or p.IS_DU…
阅读更多...
Leetcoder Day39｜ 动态规划part06 完全背包问题

Leetcoder Day39｜ 动态规划part06 完全背包问题

完全背包理论 有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]&#xff0c;得到的价值是value[i] 。每件物品都有无限个&#xff08;也就是可以放入背包多次&#xff09;&#xff0c;求解将哪些物品装入背包里物品价值总和最大。 示例&#xff1a; 背包最大…
阅读更多...
2023第二届陇剑杯网络安全大赛 SS Writeup

2023第二届陇剑杯网络安全大赛 SS Writeup

sevrer save_1 打开流量包文件过滤http流量 从这个/helloworld/greeting开始追踪TCP流 直接百度搜索payload 搜索得到这题flag就是CVE-2022-22965 sevrer save_2 追踪TCP流&#xff0c;在tcp.stream eq 106&#xff0c;发现反弹shell的IP和端口 这题flag为192.168.43.128:2333…
阅读更多...
最新文章

Copyright @ 2022~2023