数据结构之顺序表——动态顺序表(C语言版)

静态顺序表我们已经实现完毕了,下来我们实现一下动态顺序表

静态链接:数据结构之顺序表——动态顺序表(C语言版)
首先来了解一下两个顺序表的差别
一、内存管理的灵活性
动态分配与释放:动态顺序表能够在运行时根据需要动态地分配和释放内存空间。这意味着,当数据量增加时,它可以自动扩容以容纳更多的数据;而当数据量减少时,理论上也可以相应地释放不再需要的内存空间(尽管这通常需要程序员手动操作或依赖垃圾回收机制,具体取决于编程语言)。这种灵活性使得动态顺序表能够更高效地管理内存资源。
避免内存浪费:与静态顺序表相比,动态顺序表能够更准确地根据实际需求分配内存空间,从而避免了因预先分配过多内存而导致的内存浪费问题。同时,它也能够在数据量减少时释放部分内存空间,进一步提高了内存资源的利用率。
二、操作的便捷性
插入与删除操作的灵活性:在动态顺序表中,插入和删除操作可以更加灵活地进行。由于内存空间是动态分配的,因此可以在不移动大量元素的情况下完成插入和删除操作(尽管在某些情况下仍然需要移动部分元素以保持数据的连续性)。相比之下,静态顺序表在进行插入和删除操作时通常需要移动大量的元素,这降低了操作的效率。
适应数据变化的能力:动态顺序表能够更好地适应数据量的变化。当数据量增加时,它可以自动扩容以容纳更多的数据;而当数据量减少时,它也可以相应地调整内存空间的大小。这种能力使得动态顺序表在处理不确定大小的数据集时更加高效和便捷

总而言之,就是为了使我们的顺序表更加灵活,长度不够去动态开辟。
下来我们通过代码来实现一下动态顺序表。
首先还是一样,我们从头文件开始写起

#pragma once
//包含头文件
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
// 定义顺序表存储的数据类型 
typedef int SQDataType;
// 定义顺序表的结构体  
typedef struct {
	SQDataType* arr;// 指向动态分配数组的指针(数组的首地址)  
	int size; // 顺序表当前存储的元素个数(有效长度)
	int capacity; // 顺序表的容量(即数组的总大小)  
}SL;
void SListInIt(SL* ps);//初始化函数

为了方便测试,我们完成打印函数

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

下来我们完成初始化函数:

//包含我们自己写的头文件
#include"SList_02.h"
// 初始化顺序表  
// 为顺序表分配初始内存,并设置size为0,capacity为指定的初始容量  
void SListInIt(SL* ps)
{
	ps->arr = NULL;//将数组的首地址赋值为空
	ps->size = 0;//数组的有效长度
	ps->capacity = 0;//容量
}

OK,经过调试我们知道我们的初始化已经完成了
在这里插入图片描述
下来我们写尾插函数

void SListPushback(SL* ps,SQDataType x)
{
	//首先进行动态内存分配malloc
	int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
	if (ps->capacity == ps->size)
	{
		SQDataType* temp = malloc(newcapacity * sizeof(SQDataType));
		if (temp == NULL)
		{
			printf("erro\n");
			exit(-1);
		}
		else
		{
			ps->arr = temp;
			ps->capacity = newcapacity;
		}
	}
	ps->arr[ps->size] = x;
	ps->size++;
}

运行一下
在这里插入图片描述
尾插成功
由于我们每次都需要检查一下剩余的空间是否足够所以我们这里写一个检查函数,就会方便很多

void SqListCheck(SL* ps)
{
	int newcapacity = ps->capacity == 0 ? 4 : ps->capacity*2;//创建一个变量newcapacity,如果原来的容量为0则修改为4,如果不为0,则为原来的二倍
	if (ps->capacity == ps->size)//说明容量满了,需要扩容了
	{
		SQDataType *tmp=realloc(ps->arr, newcapacity * sizeof(SQDataType));//扩容二倍
		//如果扩容失败
		if (tmp == NULL)
		{
			printf("error\n");
			exit(-1);//非正常退出程序
		}
		//正常执行
		else
		{
			ps->arr = tmp;//扩容的新地址给原来的变量
			ps->capacity = newcapacity;//新容量赋值给原来的容量
		}
	}
}

头插函数

void SListPushFront(SL* ps, SQDataType x)
{
	//程序开始先检查一下需不需要扩容
	SqListCheck(ps);//ps已经是指针变量了指向SL类型
	//头插就是把所有的数据往后挪动一位,空出来索引为0的位置,将新数据插入进去
	int end = ps->size - 1;//由于我们每次插入数据之后,size都会++所以这里end表示的是索引值
	while (end >= 0)
	{
		ps->arr[end + 1] = ps->arr[end];
		end--;
	}
	ps->arr[0] = x;
	ps->size++;
}

测试一下没有问题
在这里插入图片描述
头删函数:

void SqListDeleteFront(SL* ps)
{
	//和静态一样,只需要覆盖就好了
	int start = 0;
	while (start < ps->size)
	{
		ps->arr[start] = ps->arr[start + 1];
		start++;
	}
	ps->size--;
}

在这里插入图片描述

调用了两次,成功删除
尾删函数:

void SqListDeleteback(SL* ps)
{
	//直接把有效长度减一就可以了,很简单
	ps->size--;
}

在这里插入图片描述
删除成功
随机插入函数:

void SqListInter(SL* ps, int pos, SQDataType x)
{	
	assert(pos < ps->size);//断言一下看是否插入合法
	SqListCheck(ps);//检查一下,长度不够的话就扩容
	int end = ps->size - 1;//跟头插差不多,循环条件改到pos 就可以了
	while (end >= pos)
	{
		ps->arr[end + 1] = ps->arr[end];
		end--;
	}
	ps->arr[pos] = x;//赋值要插入的值给索引pos的位置
	ps->size++;

}

在这里插入图片描述

成功插入
随机删除函数:

void SqListDelete(SL* ps, int pos)
{
	assert(pos < ps->size);//断言一下看是否删除合法
	int start = pos;
	while (start < ps->size)
	{
		ps->arr[start - 1] = ps->arr[start];
		start++;
	}
	ps->size--;

}

在这里插入图片描述
删除成功,这里不是按照索引删除的,是按照数字的真实位置删除,如果需要按照索引删除,只需要改一下代码:

void SqListDelete(SL* ps, int pos)
{
	assert(pos < ps->size);//断言一下看是否删除合法
	int start = pos+1;
	while (start < ps->size)
	{
		ps->arr[start - 1] = ps->arr[start];
		start++;
	}
	ps->size--;

}

在这里插入图片描述

现在就是根据索引删除啦

改函数:

void SqListModity(SL* ps, int pos, SQDataType x)
{
	assert(pos < ps->size);//断言一下看是否改变合法
	//改直接改就行了,看是根据索引改,还是根据真实序号改
	//这里我们以索引为例
	ps->arr[pos] = x;

}

在这里插入图片描述
成功修改了
查函数:是按照索引来显示的,如果要按照真实位置则需要在打印的时候换成 i + 1

void SqListFound(SL* ps, SQDataType x)
{
	int count = 0;
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			printf("此元素是第%d个元素\n", i);
			count++;
			break;
		}
	}
	if (count == 0)
	{
		printf("顺序表中没有这个元素\n");
	}
	
}

在这里插入图片描述
而且我们也可以用排序的方式来查,这里提供接口函数

//快速排序
void SqListSort(SL* ps)
{
	qsort(ps->arr, ps->size, sizeof(SQDataType), cmp);
}
//排序方法
int cmp(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}
//二分查找
int Binary_Search(struct Sq* ps, int x)
{
	int min = 0;
	int max = ps->size - 1;
	int mid = 0;
	while (min <= max)
	{
		mid = (min + max) / 2;
		if (ps->arr[mid] < x)
		{
			min = mid + 1;
		}
		else if (ps->arr[mid] > x)
		{
			max = mid - 1;
		}
		else
		{
			return mid;
		}
	}
	return -1;
}

大家可以试一下
关于qsort函数,大家可以看qsort快速排序以及冒泡模拟实现
最后我们还得释放多余的空间,释放函数:

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

以下是完整代码:

头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SQDataType;
typedef struct {
	SQDataType* arr;
	int size;
	int capacity;
}SL;
void SListInit(SL* ps);//初始化函数
void SListPushback(SL* ps,SQDataType x);//尾插函数
void SListPushFront(SL* ps, SQDataType x);//头插函数
void PrintSList(SL* ps);//打印函数
void SqListDeleteFront(SL* ps);//头删
void SqListDeleteback(SL* ps);//尾删
void SqListInter(SL* ps, int pos, SQDataType x);//随即插入
void SqListDelete(SL* ps, int pos);//随机删除
void SqListModity(SL* ps, int pos, SQDataType x);//改函数
void SqListFound(SL* ps, SQDataType x);//查函数
void SqListCheck(SL* ps);//检查函数
void SqListDestory(SL* ps);//释放函数

函数

#include"SList_02.h"
void SListInit(SL* ps)
{
	ps->arr = NULL;//将数组的首地址赋值为空
	ps->size = 0;//数组的有效长度
	ps->capacity = 0;//容量
}
void PrintSList(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d  ", ps->arr[i]);
	}
	printf("\n");
}
void SqListCheck(SL* ps)
{
	int newcapacity = ps->capacity == 0 ? 4 : ps->capacity*2;//创建一个变量newcapacity,如果原来的容量为0则修改为4,如果不为0,则为原来的二倍
	if (ps->capacity == ps->size)//说明容量满了,需要扩容了
	{
		SQDataType *tmp=realloc(ps->arr, newcapacity * sizeof(SQDataType));//扩容二倍
		//如果扩容失败
		if (tmp == NULL)
		{
			printf("error\n");
			exit(-1);//非正常退出程序
		}
		//正常执行
		else
		{
			ps->arr = tmp;//扩容的新地址给原来的变量
			ps->capacity = newcapacity;//新容量赋值给原来的容量
		}
	}
}
//void SqListCheck(SL* ps)
//{
//	int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//	//如果满了就要扩容
//	if (ps->size == ps->capacity)
//	{
//		/*ps->capacity=realloc(ps->arr,ps->capacity=ps->capacity*2)*/
//		SQDataType* temp = realloc(ps->arr, newcapacity * sizeof(SQDataType));
//		if (temp == NULL)
//		{
//			printf("fail\n");
//			exit(-1);
//		}
//		else
//		{
//			ps->arr = temp;
//			ps->capacity = newcapacity;
//		}
//	}
//}
void SListPushback(SL* ps,SQDataType x)
{
	//首先进行动态内存分配malloc
	int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
	if (ps->capacity == ps->size)
	{
		SQDataType* temp = malloc(newcapacity * sizeof(SQDataType));
		if (temp == NULL)
		{
			printf("erro\n");
			exit(-1);
		}
		else
		{
			ps->arr = temp;
			ps->capacity = newcapacity;
		}
	}
	ps->arr[ps->size] = x;
	ps->size++;
}

void SListPushFront(SL* ps, SQDataType x)
{
	//程序开始先检查一下需不需要扩容
	SqListCheck(ps);//ps已经是指针变量了指向SL类型
	//头插就是把所有的数据往后挪动一位,空出来索引为0的位置,将新数据插入进去
	int end = ps->size - 1;//由于我们每次插入数据之后,size都会++所以这里end表示的是索引值
	while (end >= 0)
	{
		ps->arr[end + 1] = ps->arr[end];
		end--;
	}
	ps->arr[0] = x;
	ps->size++;
}
void SqListDeleteFront(SL* ps)
{
	//和静态一样,只需要覆盖就好了
	int start = 0;
	while (start < ps->size)
	{
		ps->arr[start] = ps->arr[start + 1];
		start++;
	}
	ps->size--;
}
void SqListDeleteback(SL* ps)
{
	//直接把有效长度减一就可以了,很简单
	ps->size--;
}
void SqListInter(SL* ps, int pos, SQDataType x)
{	
	assert(pos < ps->size);//断言一下看是否插入合法
	SqListCheck(ps);//检查一下,长度不够的话就扩容
	int end = ps->size - 1;//跟头插差不多,循环条件改到pos 就可以了
	while (end >= pos)
	{
		ps->arr[end + 1] = ps->arr[end];
		end--;
	}
	ps->arr[pos] = x;//赋值要插入的值给索引pos的位置
	ps->size++;

}
void SqListDelete(SL* ps, int pos)
{
	assert(pos < ps->size);//断言一下看是否删除合法
	int start = pos+1;
	while (start <=ps->size)
	{
		ps->arr[start-1] = ps->arr[start];
		start++;
	}
	ps->size--;

}
void SqListModity(SL* ps, int pos, SQDataType x)
{
	assert(pos < ps->size);//断言一下看是否改变合法
	//改直接改就行了,看是根据索引改,还是根据真实序号改
	//这里我们以索引为例
	ps->arr[pos] = x;

}
void SqListFound(SL* ps, SQDataType x)
{
	int count = 0;
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			printf("此元素是第%d个元素\n", i);
			count++;
			break;
		}
	}
	if (count == 0)
	{
		printf("顺序表中没有这个元素\n");
	}
	
}
void SqListDestory(SL* ps)
{
	free(ps->arr);
	ps->arr = NULL;
	ps->capacity = ps->size = 0;
}

测试函数

#include"SList_02.h"
void test()
{
	SL s;
	SListInit(&s);
	SListPushback(&s, 5);
	SListPushback(&s, 7);
	PrintSList(&s);
	SListPushFront(&s, 3);
	SListPushFront(&s, 9);
	SListPushFront(&s, 6);
	PrintSList(&s);
	SListPushFront(&s, 8);
	SListPushFront(&s, 11);
	SListPushFront(&s, 16);
	SListPushFront(&s, 15);
	SListPushFront(&s, 1);
	PrintSList(&s);
	SqListDeleteFront(&s);
	SqListDeleteFront(&s);
	PrintSList(&s);
	SqListDeleteback(&s);
	SqListDeleteback(&s);
	PrintSList(&s);
	SqListInter(&s, 2, 50);
	PrintSList(&s);
	SqListInter(&s, 5, 60);
	PrintSList(&s);
	SqListDelete(&s, 2);
	PrintSList(&s);
	SqListDelete(&s, 5);
	PrintSList(&s);
	SqListModity(&s, 3, 25);
	PrintSList(&s);
	SqListModity(&s, 3, 29);
	PrintSList(&s);
	SqListFound(&s, 29);
	SqListFound(&s, 1);
	SqListDestory(&s);

}
int main()
{
	test();
	return 0;
}

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

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

相关文章

Prometheus+Grafana 监控 Kubernetes

文章目录 一、Prometheus介绍二、Prometheus组件与监控三、Prometheus基本使用&#xff1a;怎么来监控四、Kubernetes监控指标五、Prometheus的基本使用&#xff1a;部署1.基于docker部署prometheusgrafana2. 查看prometheus配置文件3. 监控Linux服务器3.1找到自己相应的系统去…

C# 中循环的应用说明

一循环的概念说明 在C#编程中&#xff0c;循环结构是一种非常重要的控制流语句&#xff0c;它允许我们重复执行一段代码&#xff0c;直到满足某个特定条件为止。C#提供了几种不同类型的循环结构&#xff0c;包括for循环、while循环、do-while循环和foreach循环。 循环语句允许…

【华为HCIP实战课程十一】OSPF网络NBMA网络解决方案,网络工程师

上节我们讲解了DR DBR 选举,每台设备可以学到全网路由,但是通信是有问题的 DR BDR的选举是基于接口的,而不是基于路由器的 一、OSPF路由通信问题 R5虽然可以学到全网的OSPF路由,但是R5无法ping通44.1.1.1 原因是R5到达R4 lo0的下一跳是10.1.1.4, 而R5和R4直连无法ping通…

40款主流的AI工具集盘点,这些好用的AI软件一定要知道!

AI工具哪款好&#xff0c;有哪些值得推荐&#xff1f; 不可否认&#xff0c;当下各式各样的AI工具层出不穷&#xff0c;面对不断涌现的AI工具&#xff0c;各位在选用时是否无从下手&#xff0c;或是抽不出时间&#xff0c;逐一体验对比不同AI工具的差异…… 这也是现如今许多…

根据PFX证书文件合成Nginx所需的SSL证书

具体步骤如下&#xff1a; 1、安装openssl 工具地址&#xff1a;http://slproweb.com/products/Win32OpenSSL.html 并配置环境变量。 2、生成证书 &#xff08;1&#xff09;以管理员身份运行cmd&#xff0c;进入到pfx文件的目录&#xff1a; &#xff08;2&#xff09;根据…

一款零依赖、跨平台的流媒体协议处理工具,支持 RTSP、WebRTC、RTMP 等视频流协议的处理

大家好&#xff0c;今天给大家分享一款功能强大的流媒体协议处理工具go2rtc&#xff0c;支持多种协议和操作系统&#xff0c;具有零依赖、零配置、低延迟等特点。 项目介绍 go2rtc可以从各种来源获取流&#xff0c;包括 RTSP、WebRTC、HomeKit、FFmpeg、RTMP 等&#xff0c;并…

Cherno游戏引擎笔记(73~90)

------- scene viewport ---------- 》》》》做了两件事&#xff1a;设置视口和设置相机比例 》》》》为什么要设置 m_ViewportSize 为 glm::vec2 而不是 ImVec2 ? 因为后面需要进行 ! 运算&#xff0c;而 ImVec2 没有这个运算符的定义&#xff0c;只有 glm::vec2 有这个运算…

atcoder abc375

A seats 代码&#xff1a; #include <bits/stdc.h> using namespace std;int main() {int n;cin >> n;vector<char> a(n 1);for(int i 1; i < n; i ) cin >> a[i];int cnt 0;for(int i 1; i < n - 2; i ) {if(a[i] # && a[i 1…

LeetCode刷题日记之回溯算法(五)

目录 前言重新安排行程N皇后解数独总结 前言 今天是学习回溯算法的第五天&#xff0c;我们继续来一起学习回溯算法蕴含的逻辑处理&#xff0c;希望博主记录的内容能够对大家有所帮助 &#xff0c;一起加油吧朋友们&#xff01;&#x1f4aa;&#x1f4aa;&#x1f4aa; 重新安…

IDEA中git如何快捷的使用Cherry-Pick功能

前言 我们在使用IDEA开发时&#xff0c;一般是使用GIT来管理我们的代码&#xff0c;有时候&#xff0c;我们需要在我们开发的主分支上合并其他分支的部分提交代码。注意&#xff0c;是部分&#xff0c;不是那个分支的全部提交&#xff0c;这时候&#xff0c;我们就需要使用Che…

重学SpringBoot3-集成Spring Boot Actuator

更多SpringBoot3内容请关注我的专栏&#xff1a;《SpringBoot3》 期待您的点赞&#x1f44d;收藏⭐评论✍ 重学SpringBoot3-集成Spring Boot Actuator 1. 什么是 Spring Boot Actuator&#xff1f;2. Spring Boot Actuator 的核心功能3. Spring Boot 3 中集成 Actuator3.1 添加…

RBTree(红黑树)的介绍和实现

欢迎来到杀马特的主页&#xff1a;羑悻的小杀马特.-CSDN博客 目录 ​编辑 一红黑树介绍&#xff1a; 1.1红黑树概念&#xff1a; 1.2红黑树遵循的原则&#xff1a; 1.3红黑树效率分析&#xff1a; 二.红黑树的实现&#xff1a; 2.1红黑树结构&#xff1a; 2.2红黑树节点…

PAT甲级-1127 ZigZagging on a Tree

题目 题目大意 给出一棵树的中序和后序遍历&#xff0c;要求按层序输出这棵树&#xff0c;但是按照从左到右&#xff0c;再从右到左&#xff0c;再从左到右的顺序。 思路 由中序遍历和后序遍历可以构造出一棵二叉树。观察题目中要求的输出顺序&#xff0c;发现层数为奇数的都…

第十五章 RabbitMQ延迟消息之延迟插件

目录 一、引言 二、延迟插件安装 2.1. 下载插件 2.2. 安装插件 2.3. 确认插件是否生效 三、核心代码 四、运行效果 五、总结 一、引言 上一章我们讲到通过死信队列组合消息过期时间来实现延迟消息&#xff0c;但相对而言这并不是比较好的方式。它的代码实现相对来说比…

等保制度要求企业保障数据存储安全,天锐绿盾强大加密技术实现文档防泄密

网络安全等级保护&#xff08;等保&#xff09;制度是我国信息安全保障工作的基本制度和基本国策&#xff0c;是开展信息安全工作的基本方法&#xff0c;是促进信息化、维护国家信息安全的基本保障。等保不仅是对网络&#xff08;含信息系统、数据&#xff09;实施分等级保护、…

TypeScript数据类型限定(基本数据类型,void,数组,元组,枚举,any,unknown,never,函数,自定义数据类型,联合类型和交叉类型)

一、安装解析ts的工具包 node.js只认识js代码&#xff0c;不认识ts代码。 需要将ts代码转化为js&#xff0c;然后就可以在node.js中运行了。 安装步骤&#xff1a;打开终端&#xff0c;输入命令npm i -g typescript回车 typescript是用来解析ts的工具包。提供了tsc命令&…

基于SpringBoot+Vue+Uniapp微信小程序快递管理系统(源码+lw+部署文档+讲解等)

项目运行截图 技术框架 后端采用SpringBoot框架 Spring Boot 是一个用于快速开发基于 Spring 框架的应用程序的开源框架。它采用约定大于配置的理念&#xff0c;提供了一套默认的配置&#xff0c;让开发者可以更专注于业务逻辑而不是配置文件。Spring Boot 通过自动化配置和约…

量化策略交易之PTrade量化软件如何获取逐笔委托行情!get_individual_entrust

get_individual_entrust– 获取逐笔委托行情 get_individual_entrust(stocksNone, data_count50, start_pos0, search_direction1, is_dictFalse) 使用场景 该函数在交易模块可用 接口说明 该接口用于获取当日逐笔委托行情数据。 注意事项&#xff1a; 1、沪深市场都有逐…

C++,STL 033(24.10.15)

内容 queue容器&#xff08;队列&#xff09;的常用接口。 代码 #include <iostream> #include <string> #include <queue> // 注意包含queue容器&#xff08;队列&#xff09;的头文件using namespace std;class Person { public:string m_Name;int m_Age…

Android targetSdkVersion 升级为34 问题处理

原因是发布到GooglePlay遭到拒绝&#xff0c;需要最低API level为34。之前为31&#xff0c;感觉还挺高的&#xff0c;但是GooglePlay需要的更高。 记录下处理问题&#xff1a; 1.升级gradle版本为8.0.2 之前是&#xff1a; classpath com.android.tools.build:gradle:7.1.0-…