【数据结构】顺序表详解

当我们写完通讯录后，顺序表肯定难不倒你，跟着小张一起来学习顺序表吧！

线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
在这里插入图片描述

在这里插入图片描述

顺序表

概念及结构

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

  1. 静态顺序表：使用定长数组存储元素。
    在这里插入图片描述
  2. 动态顺序表：使用动态开辟的数组存储。
    在这里插入图片描述

接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

typedef struct pro
{int* p;// 指向动态开辟的数组int size;// 有效数据个数int capcity;// 容量空间的大小}pro;
void  SeqListInit(pro* ps );//初始化顺序表
void CheckCapacity(pro* ps);//判断是否空间不够，进行扩容
void  SeqListPushBack(pro* ps,int x);//尾插
void  SeqListPushFront(pro* ps, int x);//头插
void SeqListPopBack(pro* ps);//尾删
void  SeqListPopFront(pro* ps);//头删
void  SeqListPrint(pro* ps);//打印顺序表
void SeqListInsert(pro* ps, int pos, int x);//随意插
void SeqListErase(pro* ps, int pos);//随意删
void SeqListFind(pro* ps, int pos);//查找
void SeqListmodify(pro* ps, int x,int y);//修改
void SeqListDestory(pro* ps);//销毁

结构体定义和创建一个结构体变量

typedef struct pro
{int* p;// 指向动态开辟的数组int size;// 有效数据个数int capcity;// 容量空间的大小}pro;
int main()
{pro info;//定义一个结构体变量
}

初始化顺序表

void  SeqListInit(pro* ps )//初始化顺序表
{ps->p = NULL;ps->size = 0;ps->capcity = 0;}

初始化顺序表，有效数据个数为0，容量空间大小为0，还未给数据动态开辟空间，指向动态开辟空间的指针指向空地址

扩容顺序表

void CheckCapacity(pro* ps)//判断是否空间不够，进行扩容
{if (ps->size == ps->capcity){int newcapcity = ps->capcity == 0 ? 4 : (ps->capcity) * 2;int* tmp = (int*)realloc(ps->p, sizeof(int) * newcapcity);if (tmp == NULL){perror("realloc fail!!");}ps->p = tmp;ps->capcity = newcapcity;}}

什么时候需要扩容顺序表呢？？当顺序表刚被初始化，你要进行插入数据时，发现容量空间已经满了，此时必须要扩容空间，当你要插入第一个数据时，在此之前，顺序表没有任何数据，容量空间为0，然后要插入数据的话，也必须扩容。
条件判断如果有效数据个数等于容量大小时，分两种情况，第一种，刚开始的时候，有效数据个数和容量大小都为0的时候，第二种，当要插入数据时，发现此时的有效数据个数和容量大小相等时，且不等于0.对空间进行扩容， newcapcity变量是新的容量大小，当需要扩容的时候，直接新容量为原来的2倍，刚开始，他的容量是0，采用三目运算符，如果容量是0的话，就给四个空间大小，如果不是就开原来容量的2倍。将realloc来的空间的地址存放在tmp指针里面，如果realloc失败就返回空指针，打印错误信息，realloc成功的话就将tmp中存放扩容的地址交给指针p,然后容量大小更新为newcapcity。

尾插

void  SeqListPushBack(pro* ps,int x)//尾插
{CheckCapacity(ps);ps->p[ps->size] = x;ps->size++;}

每次插入都要判断是否需要扩容
在这里插入图片描述
然后有效数据+1.

头插

void  SeqListPushFront(pro* ps, int x)//头插
{CheckCapacity(ps);int end = ps->size - 1;while (end>=0){ps->p[end + 1] = ps->p[end];end--;}ps->p[0] = x;ps->size++;}

头插一个数据，必须将后面的数据向后面移动，移动的过程中可能超过容量大小，所以在插入时都需要进行扩容判断
在这里插入图片描述
如果按这个顺序移动数据当1挪到2的位置的时候，2这个数据就会被覆盖，所以我们必须从后往前面挪
在这里插入图片描述
在这里插入图片描述当数据挪到后面之后，然后在第一个位置填入x,第一个位置也就是下标为0的位置。
在这里插入图片描述

在下标为0的地方填入 插入的数据x,然后ps->size+1;

尾删

void SeqListPopBack(pro* ps)//尾删
{assert(ps);assert(ps->size > 0);ps->size--;}

尾巴要删除一个数据的话，我们需要将删除的数据改为0吗？如果要删除的数据本来就是0呢？所以我们只需要将ps->size–;因为打印的时候只打印到下标为ps->size-1的位置，打印出来看起来就像 我们删除了这个数据，注意这里用断言是因为在删除的时候ps->size–,当ps->size<0的时候，在添加数据时
ps->p[-1]=x;这个是不合理的，在ps->size<0时，直接报错，第一个断言是为了防止空指针。

头删

void  SeqListPopFront(pro* ps)//头删
{assert(ps->size > 0);int begin = 1;while (begin<ps->size){ps->p[begin - 1] = ps->p[begin];begin++;}ps->size--;}

这里的断言和上面是一个道理，然后相比尾删向后挪动数据，头删是往前挪数据，吸取尾删的教训，我们可以直到移动的顺序是
在这里插入图片描述
定义一个变量begin=1,首先是要将数据2移动到数据1的位置，对应的操作是
ps->p[begin - 1] = ps->p[begin];然后begin++,依次将数据3挪到数据2的位置，数据4挪到数据3的位置。循环最后一次是将数据5挪到数据4的位置，也就是begin=4,ps->size=5.则循环判断条件为beginsize,循环结束后将
ps->size–;

顺序表的打印

void  SeqListPrint(pro* ps)//打印顺序表
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->p[i]);}}

循环遍历顺序表，将每个数据打印出来

随意插

void SeqListInsert(pro* ps, int pos, int x)//随意插
{CheckCapacity(ps);assert(pos>=0&&pos<=ps->size);int end = ps->size - 1;while (end>=pos){ps->p[end + 1] = ps->p[end];end--;}ps->p[pos] = x;ps->size++;
}

断言是为了检查插入的位置是否合理
在这里插入图片描述
当有5个数据时，pos的可能取值如图所示，推广到一般
就是pos>=0&&pos<=ps->size,如果我们想在pos=2的位置插入一个x,我们应该怎么做呢？
1.插入一个x,我们需要将3，4，5向后移动，必须先移动5，定义一个变量end,
在这里插入图片描述
end变量的初值给ps->size-1，也就是4，要想将数据5向后挪动，对应的操作是ps->p[end + 1] = ps->p[end];然后end–;循环分别将4，3向后挪动，循环结束后，将数据x插入到pos=2的位置，对应操作为ps->p[pos] = x;然后有效数据大小ps->size++；

随意删

void SeqListErase(pro* ps, int pos)//随意删
{int begin = pos;assert(pos >= 0 && pos <= ps->size);while (begin<ps->size-1){ps->p[begin] = ps->p[begin+1];begin++;}ps->size--;
}

断言判断删除的数据的位置是否合理，和随意插的那里一样
在这里插入图片描述
如果我们要删除数3，然后数据3后面的数据向前挪动，第一步就是将数据4移动到数据3的位置，定义一个变量begin=pos=2;对应的操作为
ps->p[begin] = ps->p[begin+1];，然后begin++;将数据5移动到最开始数据4的地方。最后一次循环是将数据5移动到数据4的地方，也就是begin最后等于3，ps->size=5，则循环判断条件是begin< ps->size-1,循环结束将ps->size–;

顺序表的查找

void SeqListFind(pro* ps, int pos)//查找
{assert(pos >= 0 && pos < ps->size);printf("你查找的下标是%d,对应的数据是%d", pos, ps->p[pos]);
}

断言保证查找位置的合理性，因为函数传参pos 刚好是要查找数据的下标，直接打印出来

顺序表的修改

void SeqListmodify(pro* ps, int x,int y)//修改
{for (int i = 0; i < ps->size; i++){if (x == ps->p[i]){ps->p[i] = y;}}}

x为修改前的值，y是修改之后的值，循环遍历顺序表，将顺序表中所有的x都修改成y

顺序表的销毁

void SeqListDestory(pro* ps)//销毁
{ps->capcity = 0;ps->size = 0;free(ps->p);ps->p = NULL;}

销毁一个顺序表，将顺序表的容量置为0，顺序表的有效数据个数置为0，将p指针所指向的动态开辟的内存空间释放了，由于释放了动态开辟的内存空间，所有p指向的空间未初始化，p成为野指针，为了防止野指针，将p置为空指针。

整体代码

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct pro
{int* p;// 指向动态开辟的数组int size;// 有效数据个数int capcity;// 容量空间的大小}pro;
void  SeqListInit(pro* ps )//初始化顺序表
{ps->p = NULL;ps->size = 0;ps->capcity = 0;}
void CheckCapacity(pro* ps)//判断是否空间不够，进行扩容
{if (ps->size == ps->capcity){int newcapcity = ps->capcity == 0 ? 4 : (ps->capcity) * 2;int* tmp = (int*)realloc(ps->p, sizeof(int) * newcapcity);if (tmp == NULL){perror("realloc fail!!");}ps->p = tmp;ps->capcity = newcapcity;}}
void  SeqListPushBack(pro* ps,int x)//尾插
{CheckCapacity(ps);ps->p[ps->size] = x;ps->size++;}
void  SeqListPushFront(pro* ps, int x)//头插
{CheckCapacity(ps);int end = ps->size - 1;while (end>=0){ps->p[end + 1] = ps->p[end];end--;}ps->p[0] = x;ps->size++;}
void SeqListPopBack(pro* ps)//尾删
{assert(ps);assert(ps->size > 0);ps->size--;}
void  SeqListPopFront(pro* ps)//头删
{assert(ps->size > 0);int begin = 1;while (begin<ps->size){ps->p[begin - 1] = ps->p[begin];begin++;}ps->size--;}
void  SeqListPrint(pro* ps)//打印顺序表
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->p[i]);}}
void SeqListInsert(pro* ps, int pos, int x)//随意插
{CheckCapacity(ps);assert(pos>=0&&pos<=ps->size);int end = ps->size - 1;while (end>=pos){ps->p[end + 1] = ps->p[end];end--;}ps->p[pos] = x;ps->size++;
}
void SeqListErase(pro* ps, int pos)//随意删
{int begin = pos;assert(pos >= 0 && pos <= ps->size);while (begin<ps->size-1){ps->p[begin] = ps->p[begin+1];begin++;}ps->size--;}
void SeqListFind(pro* ps, int pos)//查找
{assert(pos >= 0 && pos < ps->size);printf("你查找的下标是%d,对应的数据是%d", pos, ps->p[pos]);
}
void SeqListmodify(pro* ps, int x,int y)//修改
{for (int i = 0; i < ps->size; i++){if (x == ps->p[i]){ps->p[i] = y;}}}
void SeqListDestory(pro* ps)//销毁
{ps->capcity = 0;ps->size = 0;free(ps->p);ps->p = NULL;}
int main()
{pro info;SeqListInit(&info);printf("尾插:");SeqListPushBack(&info, 1);SeqListPushBack(&info, 2);SeqListPushBack(&info, 3);SeqListPushBack(&info, 4);SeqListPrint(&info);printf("\n");printf("头插:");SeqListPushFront(&info, 7);SeqListPushFront(&info, 6);SeqListPushFront(&info, 5);SeqListPushFront(&info, 5);SeqListPrint(&info);printf("\n");printf("尾删:");SeqListPopBack(&info);SeqListPrint(&info);printf("\n");printf("头删:");SeqListPopFront(&info);SeqListPrint(&info);printf("\n");printf("随意插:");SeqListInsert(&info, 1, 1);SeqListPrint(&info);printf("\n");printf("随意删:");SeqListErase(&info,1,1);SeqListPrint(&info);printf("\n");printf("查找:");SeqListFind(&info, 3);printf("\n");printf("修改:");SeqListmodify(&info, 1, 2);SeqListPrint(&info);printf("\n");printf("销毁:");SeqListDestory(&info);SeqListPrint(&info);
}

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Linux_VMware_虚拟机磁盘扩容

Linux_VMware_虚拟机磁盘扩容

来源文章 &#xff1a;VMware教学-虚拟机扩容篇_vmware虚拟机扩容_系统免驱动的博客-CSDN博客 由于项目逐步的完善&#xff0c;需要搭建的中间件&#xff0c;软件越来越多&#xff0c;导致以前虚拟机配置20G的内存不够用了&#xff0c;又不想重新创建新的虚拟机&#xff0c;退…
阅读更多...
pg_database中的datlastsysoid

pg_database中的datlastsysoid

一&#xff0c;关于 pg_database 在 PostgreSQL 中&#xff0c;对于在数据库集群内创建的每个数据库,其关键信息都会被保存到 pg_database 系统表中。 PostgreSQL 确保通过 pg_database 系统表持久化存储每个数据库的属性信息&#xff0c;以方便后续管理和使用。这也让 pg_da…
阅读更多...
go锁--读写锁

go锁--读写锁

每个锁分为读锁和写锁&#xff0c;写锁互斥 没有加写锁时&#xff0c;多个协程都可以加读锁 加了写锁时&#xff0c;无法加读锁&#xff0c;读协程排队等待 加了读锁&#xff0c;写锁排队等待 Mutex用来写协程之间互斥等待 读协程使用readerSem等待写锁的释放 写协程使用writer…
阅读更多...
Android Native Code开发学习（三）对java中的对象变量进行操作

Android Native Code开发学习（三）对java中的对象变量进行操作

Android Native Code开发学习&#xff08;三&#xff09; 本教程为native code学习笔记&#xff0c;希望能够帮到有需要的人 我的电脑系统为ubuntu 22.04&#xff0c;当然windows也是可以的&#xff0c;区别不大 对java中的对象变量进行操作 首先我们新建一个java的类 pub…
阅读更多...
多目标应用：基于多目标人工蜂鸟算法（MOAHA）的微电网多目标优化调度MATLAB

多目标应用：基于多目标人工蜂鸟算法（MOAHA）的微电网多目标优化调度MATLAB

一、微网系统运行优化模型 参考文献&#xff1a; [1]李兴莘,张靖,何宇,等.基于改进粒子群算法的微电网多目标优化调度[J].电力科学与工程, 2021, 37(3):7 二、多目标人工蜂鸟算法MOAHA 多目标人工蜂鸟算法&#xff08;multi-objective artificial hummingbird algorithm&…
阅读更多...
跨数据中心Multi-Fabric解决方案：L2和L3网络的高效连接和扩展

跨数据中心Multi-Fabric解决方案：L2和L3网络的高效连接和扩展

云数据中心里&#xff0c;为什么需要DCI互通&#xff1f; 云化数据中心&#xff0c;网络资源通过虚拟化技术形成资源池&#xff0c;实现业务与物理网络解耦&#xff0c;通过网络虚拟化&#xff0c;物理网络资源可以被分成多个虚拟网络资源&#xff0c;从而提高网络资源的使用效…
阅读更多...
设计模式之装饰者模式

设计模式之装饰者模式

文章目录 星巴克咖啡订单项目&#xff08;咖啡馆&#xff09;方案 1-解决星巴克咖啡订单项目方案 1-解决星巴克咖啡订单问题分析方案 2-解决星巴克咖啡订单(好点)方案 2-解决星巴克咖啡订单问题分析装饰者模式定义装饰者模式原理装饰者模式解决星巴克咖啡订单装饰者模式下的订单…
阅读更多...
【LeetCode算法系列题解】第51~55题

【LeetCode算法系列题解】第51~55题

CONTENTS LeetCode 51. N 皇后&#xff08;困难&#xff09;LeetCode 52. N 皇后 II&#xff08;困难&#xff09;LeetCode 53. 最大子序和&#xff08;中等&#xff09;LeetCode 54. 螺旋矩阵&#xff08;中等&#xff09;LeetCode 55. 跳跃游戏&#xff08;中等&#xff09; …
阅读更多...
跨站请求伪造（CSRF）攻击与防御原理

跨站请求伪造（CSRF）攻击与防御原理

跨站请求伪造&#xff08;CSRF&#xff09; 1.1 CSRF原理 1.1.1 基本概念 跨站请求伪造&#xff08;Cross Site Request Forgery&#xff0c;CSRF&#xff09;是一种攻击&#xff0c;它强制浏览器客户端用户在当前对其进行身份验证后的Web 应用程序上执行非本意操作的攻击&a…
阅读更多...
Debian离线安装mysql

Debian离线安装mysql

PS:虽然已经分享了很多安装各种环境订的教程&#xff0c;但是每个客户的环境不一样&#xff0c;那就得重新来一次&#xff0c;其实都是大同小异的&#xff0c;但是里面其实也是存在不少坑的&#xff0c;今天我们就来安装一个新的东西&#xff0c;Debian 11离线安装mysql,为什么…
阅读更多...
Linux命令200例：bc是用于数学计算的高级计算器

Linux命令200例：bc是用于数学计算的高级计算器

&#x1f3c6;作者简介&#xff0c;黑夜开发者&#xff0c;CSDN领军人物&#xff0c;全栈领域优质创作者✌。CSDN专家博主&#xff0c;阿里云社区专家博主&#xff0c;2023年6月csdn上海赛道top4。 &#x1f3c6;数年电商行业从业经验&#xff0c;历任核心研发工程师&#xff0…
阅读更多...
单片机通用学习-​什么是寄存器？​

单片机通用学习-​什么是寄存器？​

什么是寄存器&#xff1f; 寄存器是一种特殊的存储器&#xff0c;主要用于存储和检查微机的状态。CPU寄存器用于存储和检查CPU的状态&#xff0c;具体包括计算中途数据、程序因中断或子程序分支时的返回地址、计算结果为零时的负值、计算结果为零时的信息、进位值等。 由于CP…
阅读更多...
基于Yolov5的摄像头吸烟行为检测系统（pytoch）

基于Yolov5的摄像头吸烟行为检测系统（pytoch）

目录 1.数据集介绍 1.1数据集划分 1.2 通过voc_label.py生成txt 1.3 小目标定义 2.基于Yolov5的吸烟行为检测性能提升 2.1采用多尺度提升小目标检测精度 2.2 多尺度训练结果分析 2.3基于多尺度基础上加入BiFormer: 基于动态稀疏注意力构建高效金字塔网络架构 2.3.1 BiFo…
阅读更多...
css让元素保持等比例宽高

css让元素保持等比例宽高

使用新属性 aspect-ratio: 16/9; 代码示例 <style>div {width: 60%;/* 等比例宽高 */aspect-ratio: 16/9;background-color: red;margin: auto;}</style> </head><body><div></div> </body>示例 aspect-ratio兼容性
阅读更多...
分布式系统的多数据库，实现分布式事务回滚（1.7.0 seata整合2.0.4nacos）

分布式系统的多数据库，实现分布式事务回滚（1.7.0 seata整合2.0.4nacos）

正文 1、解决的应用场景是分布式事务&#xff0c;每个服务有独立的数据库。 2、例如&#xff1a;A服务的数据库是A1&#xff0c;B服务的数据库是B2&#xff0c;A服务通过feign接口调用B服务&#xff0c;B涉及提交数据到B2&#xff0c;业务是在B提交数据之后&#xff0c;在A服…
阅读更多...
SpringBoot集成WebSocket

SpringBoot集成WebSocket

SpringBoot集成WebSocket 项目结构图 项目架构图 前端项目 socket.js 注意前端这里的端口是9000, 路劲是ws开头 function createScoket(token){var socket;if(typeof(WebSocket) "undefined") {console.log("您的浏览器不支持WebSocket");}else{var ho…
阅读更多...
git 提交错误，回滚到某一个版本

git 提交错误，回滚到某一个版本

git log 查看版本号 commit 后面跟的就是版本号git reset --hard 版本号 &#xff08;就可以回滚到你要去的版本&#xff09;git push -f &#xff08;因为本地回滚了&#xff0c;所以和远程会差几个版本。所以这时候只有强制推送&#xff0c;覆盖远程才可以&#xff09;
阅读更多...
【AIGC专题】Stable Diffusion 从入门到企业级实战0401

【AIGC专题】Stable Diffusion 从入门到企业级实战0401

一、概述 本章是《Stable Diffusion 从入门到企业级实战》系列的第四部分能力进阶篇《Stable Diffusion ControlNet v1.1 图像精准控制》第01节&#xff0c; 利用Stable Diffusion ControlNet Inpaint模型精准控制图像生成。本部分内容&#xff0c;位于整个Stable Diffusion生…
阅读更多...
常用命令之mysql命令之show命令

常用命令之mysql命令之show命令

一、mysql show命令简介 mysql数据库中show命令是一个非常实用的命令&#xff0c;SHOW命令用于显示MySQL数据库中的信息。它可以用于显示数据库、表、列、索引和用户等各种对象的信息。我们常用的有show databases&#xff0c;show tables&#xff0c;show full processlist等&…
阅读更多...
10.Redis 渐进式遍历

10.Redis 渐进式遍历

Redis 渐进式遍历 渐进式遍历scan 渐进式遍历 keys 命令一次性的把整个redis中所有的key都获取到&#xff0c;keys *但这个操作比较危险&#xff0c;可能会一下子得到太多的key,阻塞 redis 服务器。 通过渐进式遍历&#xff0c;就可以做到&#xff0c;既可以获取到所有的 key&…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023