数据结构：详解【顺序表】的实现

1. 顺序表的定义

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。动态顺序表与数组的本质区别是——根据需要动态的开辟空间大小。

2. 顺序表的功能

动态顺序表的功能一般有如下几个：

  • 初始化顺序表
  • 打印顺序表中的数据
  • 检查顺序表的容量
  • 顺序表头部插入数据
  • 顺序表尾部插入数据
  • 顺序表头部删除数据
  • 顺序表尾部删除数据
  • 顺序表任意位置插入数据
  • 顺序表任意位置删除数据
  • 顺序表中查找数据
  • 顺序表中修改指定位置数据
  • 顺序表的销毁

3.顺序表各功能的实现

3.1 创建顺序表

typedef int SQDateType;//对int进行重命名，可增加代码的普适性。

typedef struct SeqList
{
	SQDateType* a;
	size_t size; //有效数据
	size_t capacity;//容量的空间大小
}SL;//对这个结构体重命名为SL，书写方便

在这里插入图片描述

3.2 初始化顺序表
由于建立顺序表后并没有原始空间，所以我们自行动态开辟空间，又因为后续要进行扩容，所以我们必须初始化容量大小。

void SeqListInit(SL*ps)
{
	ps->a = (SQDateType*)malloc(sizeof(SQDateType) * 4);//初始化开辟4个int类型的空间
	//检查是否开辟成功
	if (ps->a == NULL)
	{
		printf("malloc fail!\n");
		return;
	}
	ps->capacity = 4;//初始化容量大小为4
	ps->size = 0;
}

3.3 打印顺序表中的数据
对顺序表进行增删查改等操作后，我们要把数据打印在控制台以便观察。

void SeqListPrint(SL* ps)
{
	//判断顺序表中是否有数据
	assert(ps->size > 0);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

3.4 检查顺序表的容量
对顺序表进行插入（增加）数据的操作时，我们必须先对顺序表进行容量的检查，若容量不够，则扩容。
并且扩容的幅度一般是原来容量的2倍。

void CheckSeqListCapacity(SL*ps)
{
	assert(ps);//断言
	//检查容量是否已满
	if (ps->capacity == ps->size)
	{
		//扩容
		SQDateType* tmp = (SQDateType*)realloc(ps->a, ps->capacity * 2 * sizeof(SQDateType*));
		if (tmp == NULL)
		{
			printf("realloc fail!\n");
			return;
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;//容量增大为原来的两倍
		}
	}
}

3.5 顺序表头部插入数据
头插，意思是在顺序表的最前面插入一个数据。我们需要把顺序表里的原数据（如果原来有数据的话）从后往前向后挪一个空间，再把要插入的数据放到第一个位置即可。
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/1b879d6df276406d8a11e8655d9e8cb0.png
代码实现如下：

void SeqListPushFront(SL* ps, SQDateType x)
{
     assert(ps);
	//检查是否要扩容
	CheckSeqListCapacity(ps);

	int end = ps->size;
	for (end = ps->size ; end >0; end--)
	{
		ps->a[end] = ps->a[end - 1];
	}
	ps->a[end] = x;
	ps->size++;//有效数据+1
}

3.6 顺序表尾部插入数据
尾插，意思是在顺序表的最后面插入一个数据。只需要找到该位置的下标（ps->size处)直接插入即可。
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/11372c84deae44a7b1dc038142252cc9.png

代码实现如下：

void SeqListPushBack(SL* ps, SQDateType x)
{
     assert(ps);
     //检查是否要扩容
	CheckSeqListCapacity(ps);

	ps->a[ps->size] = x;
	ps->size++;//有效数据+1
}

3.7 顺序表头部删除数据
头删，意思是删除一个顺序表最前面的数据。只需把原数据从前往后开始向前覆盖一个空间即可。
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/589b3cd1ddcc4189be625c3189619a32.png

代码实现如下：

void SeqListPopFront(SL* ps)
{
	assert(ps->size > 0);//断言，当顺序表内有数据时才删除
	
	for (int start = 0; start < ps->size; start++)
	{
		ps->a[start] = ps->a[start + 1];
	}
	ps->size--;//有效数据-1
}

3.8 顺序表尾部删除数据
尾删，直接删除顺序表中最后一个数据即可。

void SeqListPopBack(SL* ps)
{
	assert(ps->size > 0);
	ps->size--;//有效数据-1
}

3.9 顺序表任意位置插入数据
在顺序表的pos位置处插入一个数据，先要把pos处及其后面的原数据向后挪一个空间，再把数据放入pos处。
在这里插入图片描述
代码实现如下：

void SeqListInsert(SL* ps, int pos, SQDateType x)
{
	assert(ps && pos < ps->size);//pos<size时才满足
	CheckSeqListCapacity(ps);

	int end = ps->size ;
	for (end = ps->size ; end > pos; end--)
	{
		ps->a[end] = ps->a[end-1];
	}
	ps->a[pos] = x;//在pos的位置放入数据
	ps->size++;//有效数据+1
}

3.10 顺序表任意位置删除数据
在顺序表的pos位置处删除一个数据，只要把pos处后面的数据向前覆盖一个空间。
在这里插入图片描述
代码实现如下：

void SeqListEarse(SL* ps, int pos)
{
	assert(ps && pos < ps->size);//pos<size时才满足
	int start = pos;
	for (start = pos; start < ps->size; start++)
	{
		ps->a[start] = ps->a[start + 1];
	}
	ps->size--;//有效数据-1
}

3.11 顺序表中查找数据
把顺序表中的数据循环遍历，判断每个数据与查找数据是否相等，若相等，返回1，否则返回-1。

int  SeqListFind(SL* ps, SQDateType x)
{
	assert(ps && ps->size > 0);//表中有数据时才能查找
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return 1;
			break;
		}
	}
	return -1;
}

3.12 顺序表中修改指定位置数据
只要在顺序表中找到指定位置，把修改的值赋给它即可。

void SeqListModify(SL* ps, int pos, SQDateType x)
{
	assert(ps && pos < ps->size);//要修改的位置要小于数据个数
	ps->a[pos] = x;
}

3.13 顺序表的销毁
顺序表的空间的动态开辟的，最后需要free释放空间，避免造成空间泄漏。

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

4. 完整代码

SeqList.h

#pragma once

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

typedef int SQDateType;

typedef struct SeqList
{
	SQDateType* a;
	size_t size; //有效数据
	size_t capacity;//容量的空间大小
}SL;

//初始化顺序表
void SeqListInit(SL* ps);

//头部插入数据
void SeqListPushFront(SL* ps, SQDateType x);

//尾部插入数据
void SeqListPushBack(SL* ps, SQDateType x);

//头部删除数据
void SeqListPopFront(SL* ps);

//尾部删除数据
void SeqListPopBack(SL* ps);

//任意位置插入数据
void SeqListInsert(SL* ps, int pos,SQDateType x);

//任意位置删除数据
void SeqListEarse(SL* ps, int pos);

//打印数据函数
void SeqListPrint(SL* ps);

//查找数据
int SeqListFind(SL* ps, SQDateType x);

//修改指定位置数据
void SeqListModify(SL* ps, int pos, SQDateType x);

//销毁顺序表
void SeqListDestory(SL* ps);

SeqList.c

#define _CRT_SECURE_NO_WARNINGS 

#include "SeqList.h"

void SeqListInit(SL*ps)
{
	ps->a = (SQDateType*)malloc(sizeof(SQDateType) * 4);//初始化开辟4个int类型的空间
	if (ps->a == NULL)
	{
		printf("malloc fail!\n");
		return;
	}
	ps->capacity = 4;
	ps->size = 0;
}

void CheckSeqListCapacity(SL*ps)
{
	assert(ps);
	//检查容量是否已满
	if (ps->capacity == ps->size)
	{
		//扩容
		SQDateType* tmp = (SQDateType*)realloc(ps->a, ps->capacity * 2 * sizeof(SQDateType*));
		if (tmp == NULL)
		{
			printf("realloc fail!\n");
			return;
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}
}


void SeqListPushFront(SL* ps, SQDateType x)
{
	assert(ps);
	CheckSeqListCapacity(ps);

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

void SeqListPrint(SL* ps)
{
	//判断顺序表中是否有数据
	assert(ps->size > 0);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

void SeqListPushBack(SL* ps, SQDateType x)
{
	CheckSeqListCapacity(ps);

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

void SeqListPopFront(SL* ps)
{
	assert(ps->size > 0);
	for (int start = 0; start < ps->size; start++)
	{
		ps->a[start] = ps->a[start + 1];
	}
	ps->size--;
}

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

void SeqListInsert(SL* ps, int pos, SQDateType x)
{
	assert(ps && pos < ps->size);
	CheckSeqListCapacity(ps);

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

void SeqListEarse(SL* ps, int pos)
{
	assert(ps && pos < ps->size);
	int start = pos;
	for (start = pos; start < ps->size; start++)
	{
		ps->a[start] = ps->a[start + 1];
	}
	ps->size--;
}

int  SeqListFind(SL* ps, SQDateType x)
{
	assert(ps && ps->size > 0);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return 1;
			break;
		}
	}
	return -1;
}

void SeqListModify(SL* ps, int pos, SQDateType x)
{
	assert(ps && pos < ps->size);
	ps->a[pos] = x;
}

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

test.c

#define _CRT_SECURE_NO_WARNINGS 

#include "SeqList.h"

void SeqListTest()
{
	SL sl;
	
	//在这里调用各数据接口（函数）进行测试
}

int main()
{

	SeqListTest();

	return 0;
}

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

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

相关文章

计算机组成原理-3-系统总线

计算机组成原理-3-系统总线

3. 系统总线 文章目录 3. 系统总线3.1 总线的基本概念3.2 总线的分类3.3 总线特性及性能指标3.4 总线结构3.5 总线控制3.5.1 总线判优控制3.5.2 总线通信控制 本笔记参考哈工大刘宏伟老师的MOOC《计算机组成原理&#xff08;上&#xff09;_哈尔滨工业大学》、《计算机组成原理…
阅读更多...
spring suite搭建springboot操作

spring suite搭建springboot操作

一、前言 有时候久了没开新项目了&#xff0c;重新开发一个新项目&#xff0c;搭建springboot的过程都有点淡忘了&#xff0c;所有温故知新。 二、搭建步骤 从0开始搭建springboot 1&#xff0e;创建work空间。步骤FileNewJava Working Set。 2.选择Java Working Set。 3.自…
阅读更多...
微信小程序接口请求出错:request:fail url not in domain list:xxxxx

微信小程序接口请求出错:request:fail url not in domain list:xxxxx

一、微信小程序后台和开发者工具配的不一样导致了这个错误 先说结论&#xff1a; 开发者工具配置了https://www.xxx.cn/prod-api/ 微信后台配置了 https://www.xxx.cn 一、最开始 开发者工具配置了https://www.xxx.cn:7500 微信后台配置了 https://www.xxx.cn 报错:reques…
阅读更多...
OPTEE v3.20.0 FVP环境搭建

OPTEE v3.20.0 FVP环境搭建

目录 一、前提条件 二、下载fvp代码 三、下载工具链 四、下载Foundation_Platform FVP平台 五、编译及运行 一、前提条件 1、安装如下的依赖工具 sudo apt-get install android-tools-adb android-tools-fastboot autoconf \ automake bc bison build-essential ccache c…
阅读更多...
2024精灵传信系统支持电脑PC端+小程序双端源码

2024精灵传信系统支持电脑PC端+小程序双端源码

2024精灵传信系统支持电脑PC端小程序双端源码 精灵传信支持在线提交发送短信&#xff0c;查看回复短信&#xff0c;在线购买额度&#xff0c;自定义对接易支付&#xff0c;设置违禁词&#xff0c;支持网站小程序双端。 搭建环境&#xff1a; PHP > 73 MySQL>5.6 Nginx…
阅读更多...
当两会热词碰上“人工智能+”，你知道哪些企业算是行业弄潮儿吗？

当两会热词碰上“人工智能+”，你知道哪些企业算是行业弄潮儿吗？

最近正值全国“两会”的召开&#xff0c;一大批新词热词涌现&#xff0c;聚焦了各行各业的发展&#xff0c;也一定程度上代表了未来的主要发展方向。“未来产业”、“人工智能”、“全国一体化算力体系”等热词的出圈充分表明了信息技术行业是一大发展重点&#xff0c;尤其是人…
阅读更多...
护航容器安全：私有Registry在镜像审核中的关键角色与实战策略

护航容器安全：私有Registry在镜像审核中的关键角色与实战策略

在容器化技术日益普及的今天&#xff0c;Docker镜像的质量与安全性成为了构建稳定、可靠应用的关键要素。私有Registry作为镜像的集中存储和分发中心&#xff0c;不仅可以提供镜像的统一管理&#xff0c;还能通过集成镜像审核机制&#xff0c;确保进入生产环境的镜像符合安全与…
阅读更多...
如何解决MySQL死锁（看懂MySQL锁日志）

如何解决MySQL死锁（看懂MySQL锁日志）

有时候系统在生产运行着&#xff0c;会突然爆出 [40001][1213] Deadlock found when trying to get lock; try restarting transaction 这个时候每个人都会很紧张&#xff0c;因为死锁会影响DB性能&#xff0c;严重时甚至拖垮整个系统。在实际的环境中&#xff0c;很多服务会共…
阅读更多...
【电路笔记】-达林顿晶体管

【电路笔记】-达林顿晶体管

达林顿晶体管 文章目录 达林顿晶体管1、概述2、基本达林顿晶体管配置3、示例4、达林顿晶体管应用5、Sziklai 晶体管对6、ULN2003A 达林顿晶体管阵列7、总结两个双极晶体管的达林顿晶体管配置可针对给定基极电流提供更大的电流切换。 1、概述 达林顿晶体管以其发明者 Sidney Da…
阅读更多...
文件包含漏洞之包含NGINX日志文件（常用）

文件包含漏洞之包含NGINX日志文件（常用）

条件&#xff1a;知道目标服务器的日志文件存贮路径&#xff0c;并且存在文件包含漏洞 首先对目标服务器发送一次含有木马的请求&#xff0c;目的是让目标服务器日志中生成含有木马的日志记录。因为发送过程中&#xff0c;使用了url编码&#xff0c;我们抓包进行更改成能够执行…
阅读更多...
【Python爬虫】详解BeautifulSoup()及其方法

【Python爬虫】详解BeautifulSoup()及其方法

文章目录 &#x1f354;准备工作&#x1f339;BeautifulSoup()⭐代码实现✨打印标签里面的内容✨快速拿到一个标签里的属性✨打印整个文档&#x1f386;获取特定标签的特定内容 &#x1f339;查找标签&#x1f388;在文档查找标签 find_all&#x1f388;正则表达式搜索 &#x…
阅读更多...
echarts geo地图加投影两种方法

echarts geo地图加投影两种方法

方法1&#xff0c;geo中加多个地图图形&#xff0c;叠加。缩放时 可能会不一致&#xff0c;需要捕捉georoam事件&#xff0c;使下层的geo随着上层的geo一起缩放拖曳 geo: [{zlevel: 3,//geo显示级别&#xff0c;默认是0 【最顶层图形】map: BJ,//地图名roam: true,scaleLimit: …
阅读更多...
虚拟机VMware上 centos7 的网络配置

虚拟机VMware上 centos7 的网络配置

第一步&#xff1a;权限的切换 由普通用户切换到管理者/超级用户 用户名为&#xff1a;root 密码为&#xff1a;自己安装 linux 时第一次设置的密码 su -root管理者/超级用户的命令提示符是“#”&#xff0c;普通用户的命令提示符是“$”。当看到你的命令提示符为“$”时&…
阅读更多...
VScode 设置个性化背景（保姆级教程）

VScode 设置个性化背景（保姆级教程）

VS Code设置个性化背景的作用主要体现在以下几个方面&#xff1a; 提升编程体验&#xff1a;个性化背景能够让编程环境更符合个人的审美和习惯&#xff0c;使得长时间在VS Code中进行代码编辑时&#xff0c;能够保持愉悦的心情&#xff0c;从而提高编程效率。减少视觉疲劳&…
阅读更多...
微隔离是什么，有什么作用

微隔离是什么，有什么作用

传统的网络安全架构通常是基于较大的安全区域&#xff08;如子网或虚拟局域网&#xff09;&#xff0c;在这些区域内的设备可以相互通信。然而&#xff0c;这也意味着一旦内部的设备被威胁或遭到入侵&#xff0c;攻击者可能会在整个安全区域内进行横向移动和渗透。 微隔离通过…
阅读更多...
GNSS载波相位平滑伪距基本原理

GNSS载波相位平滑伪距基本原理

相位平滑技术&#xff1a;削弱伪距欢测值的随机误差影响 差分技术&#xff1a;削弱欢测方程中的系统误差影响 相位平滑伪距原理&#xff1a; GPS接收机除了提供伪距测量外&#xff0c;可同时提供载波相位测量&#xff0c;由于载波相位测量的精度比码相位的测量精度高2个数量…
阅读更多...
蓝桥杯嵌入式第十届省赛 真题＋代码

蓝桥杯嵌入式第十届省赛 真题＋代码

led.c文件 #include "led.h"void Led(uint16_t addr,uint16_t enable) {static uint16_t temp 0x0000;static uint16_t temp_old 0xffff;HAL_GPIO_WritePin(GPIOC, GPIO_PIN_All, GPIO_PIN_SET);if(enable)temp | 0x0100 << addr;elsetemp & ~(0x0100 &…
阅读更多...
在sql server 2016 always on集群里新增一个数据库节点

在sql server 2016 always on集群里新增一个数据库节点

本篇博客有对应的word版本&#xff0c;有需要的可以点击这里下载。 一 环境介绍 二 操作步骤 2.1 在新节点上安装sql server软件 略 2.2 在新节点上开启‘故障转移群集功能’ 打开‘服务管理器’&#xff1a; 点击‘添加角色和功能’&#xff1a; 勾选’DNS服务器’&#…
阅读更多...
【Godot4.2】2D导航01 - AStar2D及其使用方法

【Godot4.2】2D导航01 - AStar2D及其使用方法

概述 对于2D平台跳跃或飞机大战&#xff0c;以及一些直接用键盘方向键操控玩家的游戏&#xff0c;是根本用不到寻路的&#xff0c;因为只需要检测碰撞就可以了。 但是对于像RTS或战棋这样需要操控玩家到地图指定位置的移动方式&#xff0c;就绝对绕不开寻路了。 导航、碰撞与…
阅读更多...
企业培训考试系统数字化解决方案优势有哪些？

企业培训考试系统数字化解决方案优势有哪些？

企业员工内部培训考试系统&#xff0c;用数字技术和互联网平台&#xff0c;为企业提供高效、便捷、个性化的员工培训服务的解决方案。 企业员工培训考试数字化解决方案不仅能够提供更加高效、灵活和互动的学习体验&#xff0c;还能够帮助企业实现长期的人才发展战略&#xff0…
阅读更多...
最新文章

Copyright @ 2022~2023