数据结构之顺序表——动态顺序表(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)
{//首先进行动态内存分配mallocint 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)
{//首先进行动态内存分配mallocint 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;
}
相关文章:

数据结构之顺序表——动态顺序表(C语言版)
静态顺序表我们已经实现完毕了,下来我们实现一下动态顺序表 静态链接:数据结构之顺序表——动态顺序表(C语言版) 首先来了解一下两个顺序表的差别 一、内存管理的灵活性 动态分配与释放:动态顺序表能够在运行时根据需要动态地分配和释放内存…...
Python 网络爬虫入门与实战
目录 1 引言 2 网络爬虫基础知识 2.1 什么是网络爬虫 2.2 爬虫的工作原理 2.3 爬虫的应用场景 3 Python 爬虫环境搭建 3.1 安装 Python 3.2 安装必要的库 4 使用 Requests 库进行基本爬虫 4.1 发送 GET 请求 4.2 发送 POST 请求 4.3 处理响应 5 使用 BeautifulSoup…...

成都睿明智科技有限公司电商服务可靠不?
在这个短视频风起云涌的时代,抖音不仅成为了人们娱乐消遣的首选平台,更是众多商家竞相追逐的电商新蓝海。成都睿明智科技有限公司,作为抖音电商服务领域的佼佼者,正以其独到的洞察力和专业的服务,助力无数品牌在这片沃…...

fmql之Linux Uart
正点原子第48章。 串口收发测试 正点原子教程 RS232和RS485的串口收发测试是一样的。 // 设置串口波特率为115200 stty -F /dev/ttyPS1 ispeed 115200 ospeed 115200 cs8// 发送字符串 echo "www.openedv.com" >/dev/ttyPS1// 接收数据 cat /dev/ttyPS1 fmql测…...

【火山引擎】调用火山大模型的方法 | SDK安装 | 配置 | 客户端初始化 | 设置
豆包 (Doubao) 是字节跳动研发的大规模预训练语言模型。 目录 1 安装 2 配置访问凭证 3 客户端初始化 4 设置地域和访问域名 5 设置超时/重试次数 1 安装 通过pip安装PYTHON SDK。 pip install volcengine-python-sdk[ark] 2 配置访问凭证 获取 API Key 访问凭证具体步…...

前端实现下载功能汇总(下载二进制流文件、数组下载成csv、将十六进制下载成pcap、将文件下载成zip)
前言:汇总一下做过的下载功能,持续补充中 一、将后端传过来的二进制流文件下载(需要提取headers里面的文件名) const { herders,data }res; // 创建下载链接元素 const link document.createElement("a");// 创建 Bl…...

iLogtail 开源两周年:UC 工程师分享日志查询服务建设实践案例
作者:UC 浏览器后端工程师,梁若羽 传统 ELK 方案 众所周知,ELK 中的 E 指的是 ElasticSearch,L 指的是 Logstash,K 指的是 Kibana。Logstash 是功能强大的数据处理管道,提供了复杂的数据转换、过滤和丰富…...
【MySQL】入门篇—基本数据类型:NULL值的概念
在关系数据库中,NULL值是一个特殊的标记,表示缺失或未知的值。 NULL并不等同于零(0)或空字符串(),它表示一个字段没有任何值。 这一概念在数据库设计和数据管理中至关重要,因为它影…...
Java设计模式10 - 观察者模式
观察者模式 观察者模式也叫作发布-订阅模式,也就是事件监听机制。观察者模式定义了一种一对多的依赖关系,让多个观察者对象同时监听某一个主题对象,这个主题对象在状态上发生变化时,会通知所有观察者对象,使他们能够自…...

LabVIEW示波器通信及应用
基于LabVIEW平台开发的罗德与施瓦茨示波器通信与应用系统实现了示波器的远程控制及波形数据的实时分析,通过TCP/IP或USB接口与计算机通信,利用VISA技术进行指令传输,从而实现高效的数据采集与处理功能。 项目背景 随着现代电子测试需求的日益…...

西门子PLC中Modbus通讯DATA_ADDR通讯起始地址设置以及RTU轮询程序设计。
1 DATA_ADDR通讯起始地址设置 因为西门子PLC保持型寄存器的是40001~49999和400001~465536, 那么什么时候用40001什么时候用400001呢? 当需要的地址超过49999的话就用400001。 比如从站的某个地址是#16 48D518645 4000118645超过了49999 这边因为前…...

趋势(一)利用python绘制折线图
趋势(一)利用python绘制折线图 折线图( Line Chart)简介 折线图用于在连续间隔或时间跨度上显示定量数值,最常用来显示趋势和关系(与其他折线组合起来)。折线图既能直观地显示数量随时间的变化…...

【含文档】基于Springboot+Vue的采购管理系统(含源码+数据库+lw)
1.开发环境 开发系统:Windows10/11 架构模式:MVC/前后端分离 JDK版本: Java JDK1.8 开发工具:IDEA 数据库版本: mysql5.7或8.0 数据库可视化工具: navicat 服务器: SpringBoot自带 apache tomcat 主要技术: Java,Springboot,mybatis,mysql,vue 2.视频演示地址 3.功能 系统定…...

【C++11入门基础】
我没有那么想你,那只是偶尔醉意会催人提起.......................................................................... 目录 前言 一、【C11的介绍】 二、【C11引入的一些实用语法】 2.1、【统一的列表初始化({ }的初始化)】 2.2、【initi…...

Pytest中fixture的scope详解
pytest作为Python技术栈下最主流的测试框架,功能极为强大和灵活。其中Fixture夹具是它的核心。而且pytest中对Fixture的作用范围也做了不同区分,能为我们利用fixture带来很好地灵活性。 下面我们就来了解下这里不同scope的作用 fixture的scope定义 首…...

Springboot 接入 WebSocket 实战
Springboot 接入 WebSocket 实战 前言: WebSocket协议是基于TCP的一种新的网络协议。它实现了浏览器与服务器全双工(full-duplex)通信——允许服务器主动发送信息给客户端。 简单理解: 1,常见开发过程中我们知道 Http协议,客户端…...

数据结构之红黑树的实现
红黑树的实现 1. 红⿊树的概念1.1 红⿊树的规则:1.2 思考⼀下,红⿊树如何确保最⻓路径不超过最短路径的2倍的?1.3 红⿊树的效率: 2. 红⿊树的实现2.1 红⿊树的结构2.2 红⿊树的插⼊2.2.1 红⿊树树插⼊⼀个值的⼤概过程2.2.2 情况1…...
智能工厂的设计软件 中的AI操作系统的“三维时间”(历时/共时/等时)构建的“能力成熟度-时间规模”平面
本文要点 “智能工厂的设计软件提出 “三维时间”的一个时间立方体(cube)。 “三维时间”的概念--历时diachronic(一维的)、共时synchronic(二维的)和等时isochronic(三维的)。 即…...

Spring Boot常见错误与解决方法
White graces:个人主页 🙉专栏推荐:Java入门知识🙉 ⛳️点赞 ☀️收藏⭐️关注💬卑微小博主🙏 ⛳️点赞 ☀️收藏⭐️关注💬卑微小博主🙏 目录 创建第一个SpringBoot项目 SpringBoot项目各个…...

Mac中安装以及配置adb环境
一、adb介绍 Android 调试桥 (Android Debug Bridge) 是一种功能多样的命令行工具,可让您与设备进行通信。adb 命令可用于执行各种设备操作,例如安装和调试应用。adb 提供对 Unix shell(可用来在设备上运行各种命令)的访问权限。…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

R语言速释制剂QBD解决方案之三
本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...
怎么让Comfyui导出的图像不包含工作流信息,
为了数据安全,让Comfyui导出的图像不包含工作流信息,导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo(推荐) 在 save_images 方法中,删除或注释掉所有与 metadata …...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...
6个月Python学习计划 Day 16 - 面向对象编程(OOP)基础
第三周 Day 3 🎯 今日目标 理解类(class)和对象(object)的关系学会定义类的属性、方法和构造函数(init)掌握对象的创建与使用初识封装、继承和多态的基本概念(预告) &a…...

FFmpeg avformat_open_input函数分析
函数内部的总体流程如下: avformat_open_input 精简后的代码如下: int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...
DAY 26 函数专题1
函数定义与参数知识点回顾:1. 函数的定义2. 变量作用域:局部变量和全局变量3. 函数的参数类型:位置参数、默认参数、不定参数4. 传递参数的手段:关键词参数5 题目1:计算圆的面积 任务: 编写一…...