《C++》解密--顺序表

一、线性表

           线性表是n个具有相同特性的数据元素的有限序列。                                                                           线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈......

      线性表在【逻辑上】是线性结构，也就是连续的一条直线；                                                            但在【物理结构】上不一定是连续的，线性表在物理上储存时，通常是数组、链式结构等形式。

二、顺序表

1、概念

     顺序表是线性表的一种。

     顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般采用数组存储。

     【顺序表在逻辑结构、物理结构上都是线性的】

2、顺序表和数组区别

    顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口。

三、分类

1、静态顺序表

2、动态顺序表

四、动态顺序表的实现

1、创立文件

2、顺序表的初始化和销毁

【SeqList.h】
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//定义动态顺序表结构
typedef int SLDatatype;struct SeqList
{SLDatatype* arr;int capacity;   //空间大小int size;      //有效数据个数
};typedef struct SeqList SL;  //给结构体SeqList改个名字SL//顺序表的初始化
void SLInit(SL* ps);//顺序表的销毁
void SLDestory(SL* ps);
【SeqList.c】
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include"SeqList.h"//顺序表的初始化
void SLInit(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;
}//顺序表的销毁
void SLDestory(SL* ps)
{if (ps->arr)  //相当于ps->arr != NULL{free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}
【test.c】
#include"SeqList.h"void SLtest01()
{SL s;SLInit(&s);SLDestory(&s);
}int main()
{SLtest01();return 0;
}

3、打印

【SeqList.c】
void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}
【test.c】
#include"SeqList.h"void SLtest01()
{SL s;SLInit(&s);SLPrint(&s);SLDestory(&s);
}int main()
{SLtest01();return 0;
}

4、判断空间是否足够

【SeqList.c】
//判断空间是否充足
void SLCheckCapacity(SL* ps)
{//判断空间是否充足if (ps->size == ps->capacity){//增容  //0*2=0//若capacity为0，给个默认值，否则x2倍int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity *= newCapacity;}
}

5、头插

【SeqList.h】
//头插
void SLPushFront(SL* ps,SLDatatype x);
【SeqList.c】
//头插
void SLPushFront(SL* ps, SLDatatype x)
{assert(ps);//判断空间是否足够SLCheckCapacity(ps);//插入操作//数据整体后移一位for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}//下标为0的位置空出来了ps->arr[0] = x;ps->size++;
}
【test.c】
#include"SeqList.h"void SLtest01()
{SL s;SLInit(&s);//头插SLPushFront(&s, 1);SLPushFront(&s, 2);SLPushFront(&s, 3);SLPushFront(&s, 4);SLPrint(&s);   //4 3 2 1SLDestory(&s);
}int main()
{SLtest01();return 0;
}

6、尾插

【SeqList.h】
//尾插
void SLPushBack(SL* ps,SLDatatype x);
【SeqList.c】
//尾插
void SLPushBack(SL* ps, SLDatatype x)
{//方式1if (ps == NULL){return;}//方式2   粗暴--断言//assert(ps); //等价于assert(ps != NULL)SLCheckCapacity(ps);ps->arr[ps->size++] = x;
}
【test.c】
//尾插
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPrint(&s);   //1 2 3 4

7、头删

【SeqList.h】
//头删
void SLPopFront(SL* ps);
【SeqList.c】
//头删（将第一个以后的数据整体向前挪动一位）
void SLPopFront(SL* ps)
{assert(ps);assert(ps->size);for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];  //i = size-2}ps->size--;
}
【test.c】
	//头删SLPopFront(&s);SLPrint(&s);   //2 3 4

8、尾删

【SeqList.h】
//尾删
void SLPopBack(SL* ps);
【SeqList.c】
//尾删
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size);//ps->arr[ps->size-1] = -1  //多余了ps->size--;
}
【test.c】
//尾删
SLPopBack(&s);
SLPrint(&s);  //1 2 3

10、在指定位置之前插入数据

【SeqList.h】
//在指定位置之前插入数据
void SLInsert(SL* ps, SLDatatype x, int pos);
【SeqList.c】
//在指定位置之前插入数据
//空间足够才可以直接插入
void SLInsert(SL* ps, SLDatatype x, int pos)
{assert(ps);
//           头插         尾插assert(pos >= 0 && pos <= ps->size);//检查空间是否足够，是否可以直接插入SLCheckCapacity(ps);//pos及之后的数据整体向后移动一位for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];  //pos <-- pos+1}ps->arr[pos] = x;ps->size++;
}
【test.c】
//SLInsert(&s, 11, 0);  //头插11
//SLPrint(&s);     //11 1 2 3 4//SLInsert(&s, 22, s.size);  //尾插22
//SLPrint(&s);    //1 2 3 4 22SLInsert(&s, 33, 2);  //指定位置后插入（2后面插入33）
SLPrint(&s);      //1 2 33 3 4

11、删除指定位置的数据

【SeqList.h】
//删除指定位置的数据
void SLErase(SL* ps, int pos);
【SeqList.c】
//删除指定位置的数据
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//还有很多限制：如顺序表不可以为空...//pos之后的数据整体向前挪动一位（一个一个挪）for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];  //size-1 --> size-2}ps->size--;
}
【test.c】
//指定位置删除
//SLErase(&s, 0);  //删除下标为0的那个数据
//SLPrint(&s);  //2 3 4SLErase(&s, s.size-1);  //删除最后一个有效数据
SLPrint(&s);  //1 2 3

12、查找

【SeqList.h】
//查找数据
int SLFind(SL* ps, SLDatatype x);
【SeqList.c】
//查找数据
int SLFind(SL* ps, SLDatatype x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){return 1;}}//没有找到，就返回一个无效下标return -1;
}
【test.c】
//查找数据
int find = SLFind(&s, 21);    
if (find < 0)
{printf("顺序表中不存在它！\n");
}
else
{printf("find it!\n");
}

13、整体代码

【SeqList.h】

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//定义动态顺序表结构
typedef int SLDatatype;struct SeqList
{SLDatatype* arr;int capacity;   //空间大小int size;      //有效数据个数
};typedef struct SeqList SL;  //给结构体SeqList改个名字SL//顺序表的初始化
void SLInit(SL* ps);//顺序表的销毁
void SLDestory(SL* ps);//头插
void SLPushFront(SL* ps,SLDatatype x);
//尾插
void SLPushBack(SL* ps,SLDatatype x);//头删
void SLPopFront(SL* ps);
//尾删
void SLPopBack(SL* ps);//在指定位置之前插入数据
void SLInsert(SL* ps, SLDatatype x, int pos);
//删除指定位置的数据
void SLErase(SL* ps, int pos);//查找数据
int SLFind(SL* ps, SLDatatype x);

【SeqList.c】

#include<stdio.h>
#include"SeqList.h"//顺序表的初始化
void SLInit(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;
}//顺序表的销毁
void SLDestory(SL* ps)
{if (ps->arr)  //相当于ps->arr != NULL{free(ps->arr);}ps->arr = NULL;ps->size = ps->capacity = 0;
}//打印
void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}//判断空间是否充足
void SLCheckCapacity(SL* ps)
{//判断空间是否充足if (ps->size == ps->capacity){//增容  //0*2=0//若capacity为0，给个默认值，否则x2倍int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity *= newCapacity;}
}//头插
void SLPushFront(SL* ps, SLDatatype x)
{assert(ps);//判断空间是否足够SLCheckCapacity(ps);//插入操作//数据整体后移一位for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}//下标为0的位置空出来了ps->arr[0] = x;ps->size++;
}//尾插
void SLPushBack(SL* ps, SLDatatype x)
{//方式1if (ps == NULL){return;}//方式2   粗暴--断言//assert(ps); //等价于assert(ps != NULL)SLCheckCapacity(ps);ps->arr[ps->size++] = x;
}//头删（将第一个以后的数据整体向前挪动一位）
void SLPopFront(SL* ps)
{assert(ps);assert(ps->size);for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];  //i = size-2}ps->size--;
}//尾删
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size);//ps->arr[ps->size-1] = -1  //多余了ps->size--;
}//在指定位置之前插入数据
//空间足够才可以直接插入
void SLInsert(SL* ps, SLDatatype x, int pos)
{assert(ps);
//           头插         尾插assert(pos >= 0 && pos <= ps->size);//检查空间是否足够，是否可以直接插入SLCheckCapacity(ps);//pos及之后的数据整体向后移动一位for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];  //pos <-- pos+1}ps->arr[pos] = x;ps->size++;
}//删除指定位置的数据
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//还有很多限制：如顺序表不可以为空...//pos之后的数据整体向前挪动一位（一个一个挪）for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];  //size-1 --> size-2}ps->size--;
}//查找数据
int SLFind(SL* ps, SLDatatype x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){return 1;}}//没有找到，就返回一个无效下标return -1;
}

【test.c】

#include"SeqList.h"void SLtest01()
{SL s;SLInit(&s);//头插/*SLPushFront(&s, 1);SLPushFront(&s, 2);SLPushFront(&s, 3);SLPushFront(&s, 4);SLPrint(&s);  */ //4 3 2 1//尾插SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPrint(&s);   //1 2 3 4//头删/*SLPopFront(&s);SLPrint(&s);*/   //2 3 4尾删//SLPopBack(&s);//SLPrint(&s);  //1 2 3//指定位置之后插入//SLInsert(&s, 11, 0);  //头插11//SLPrint(&s);     //11 1 2 3 4//SLInsert(&s, 22, s.size);  //尾插22//SLPrint(&s);    //1 2 3 4 22//SLInsert(&s, 33, 2);  //指定位置后插入（2后面插入33）//SLPrint(&s);      //1 2 33 3 4//指定位置删除//SLErase(&s, 0);  //删除下标为0的那个数据//SLPrint(&s);  //2 3 4//SLErase(&s, s.size-1);  //删除最后一个有效数据//SLPrint(&s);  //1 2 3//查找数据int find = SLFind(&s, 21);    if (find < 0){printf("顺序表中不存在它！\n");}else{printf("find it!\n");}SLDestory(&s);
}int main()
{SLtest01();return 0;
}

五、顺序表算法题

【示例1】

int removeElement(int* nums, int numsSize, int val) {int src = 0;  int dst = 0;while(src < numsSize){if(nums[src] == val){src++;}else{nums[dst] = nums[src];dst++;src++;}}//此时dst指向的位置就是要返回的有效个数return dst;
}
【示例2】

int removeDuplicates(int* nums, int numsSize) {int dst = 0;int src = dst + 1;while(src <numsSize){//nums[dst]  nums[src]//相同（重复）src++//不相同，dst++,赋值，src++if(nums[dst] != nums[src]){dst++;nums[dst] = nums[src];}src++;}return dst+1;
}
【示例3】

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int l1 = m-1;int l2 = n-1;int l3 = m+n-1;while(l1 >= 0 && l2 >= 0){if(nums1[l1]>nums2[l2]){nums1[l3] = nums1[l1];l3--;l1--;}else{//l1==l2要么l2>l1nums1[l3] = nums2[l2];l3--;l2--;}}//跳出while循环有两种情况//要么l1<0 ; 要么l2<0while(l2>=0){nums1[l3] = nums2[l2]; l3--;l2--;}
}
【思考】

感谢观看，未完待续...

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

单调队列的实现

单调队列的实现

这是C算法基础-数据结构专栏的第二十五篇文章&#xff0c;专栏详情请见此处。 引入 单调队列就是满足单调性的队列&#xff0c;它最经典的应用就是给定一个序列和一个窗口&#xff0c;使窗口在序列中从前向后滑动&#xff0c;求出窗口在每个位置时&#xff0c;其中元素的最大/小…
阅读更多...
STM32启用FPU浮点运算

STM32启用FPU浮点运算

这篇文章产生背景&#xff1a;其他人的文章太杂了&#xff0c;对我这种菜鸡无法接受&#xff1b; 参考文章&#xff1a; stm32h743单片机嵌入式学习笔记7-FPU_stmh743vit4-CSDN博客 stm32F407 打开 FPU(浮点运算处理器)_stm32f407开启fpu-CSDN博客 STM32F4CubeMXHal库下使能…
阅读更多...
第J1周：ResNet-50算法实战与解析

第J1周：ResNet-50算法实战与解析

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 文章目录 一、前期工作1、ResNet-50总体结构2、设置GPU3、导入数据 二、数据预处理1、加载数据2、可视化数据3、再次检查数据4、配置数据集 三、构建ResNet-50…
阅读更多...
初级练习[2]:Hive SQL查询汇总分析

初级练习[2]:Hive SQL查询汇总分析

目录 SQL查询汇总分析 成绩查询 查询编号为“02”的课程的总成绩 查询参加考试的学生个数 分组查询 查询各科成绩最高和最低的分 查询每门课程有多少学生参加了考试（有考试成绩） 查询男生、女生人数 分组结果的条件 查询平均成绩大于60分的学生的学号和平均成绩 查询至少…
阅读更多...
基于python+django+vue的农业管理系统

基于python+django+vue的农业管理系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、SSM项目源码 系统展示 【2025最新】基于pythondjangovueMySQL的农…
阅读更多...
C++ push_back和emplace_back的区别

C++ push_back和emplace_back的区别

基本类型情况西&#xff0c;两者几乎没什么区别 但是再自定义类型的时候&#xff1f;emplace——back更高效&#xff0c;但是emplace_back 没有类型检查的安全&#xff1b;只有运行时候才会报错。 #include <vector> #include <iostream> using namespace std; …
阅读更多...
基于 CycleGAN 对抗网络的自定义数据集训练

基于 CycleGAN 对抗网络的自定义数据集训练

目录 生成对抗网络&#xff08;GAN&#xff09; CycleGAN模型训练 训练数据生成 下载开源项目CycleGAN 配置训练环境 开始训练 模型测试 可视化结果 生成对抗网络&#xff08;GAN&#xff09; 首先介绍一下什么是GAN网络&#xff0c;它是由生成器&#xff08;Generator…
阅读更多...
分类预测|基于差分优化DE-支持向量机数据分类预测完整Matlab程序 DE-SVM

分类预测|基于差分优化DE-支持向量机数据分类预测完整Matlab程序 DE-SVM

分类预测|基于差分优化DE-支持向量机数据分类预测完整Matlab程序 DE-SVM 文章目录 一、基本原理DE-SVM 分类预测原理和流程总结 二、实验结果三、核心代码四、代码获取五、总结 一、基本原理 DE-SVM 分类预测原理和流程 1. 差分进化优化算法&#xff08;DE&#xff09; 原理…
阅读更多...
【运维监控】Prometheus+grafana监控tomcat运行情况

【运维监控】Prometheus+grafana监控tomcat运行情况

运维监控系列文章入口&#xff1a;【运维监控】系列文章汇总索引 文章目录 一、prometheus二、grafana三、tomcat与jmx_exporter配置1、下载jmx_exporter2、部署jmx_exporter3、添加tomcat的配置信息4、修改tomcat的启动文件5、重启tomcat及验证6、其他 四、集成prometheus与gr…
阅读更多...
vue3 动态 svg 图标使用

vue3 动态 svg 图标使用

前言 在做后台管理系统中，我们经常会用到很多图标，比如左侧菜单栏的图标 当然这里 element-ui 或者 element-plus 组件库都会提供图标 但是在有些情况下 element-ui 或者 element-plus 组件库提供的图标满足不了我们的需求时，这个时候我们就需要自己去网上找一些素材或者…
阅读更多...
CAN通讯常见错误

CAN通讯常见错误

CAN通讯常见错误 1.在使用CAN设备进行数据通讯时&#xff0c;有时候参数配置不当可能就会导致通讯的失败&#xff0c;如下图1所示&#xff0c;出现通信错误的原因是两个设备的波特率配置不一致导致。 图1 2.有时候在配置参数的时候&#xff0c;不能只关注波特率速度配置一致…
阅读更多...
JEE 设计模式

JEE 设计模式

Java 数据访问对象模式 Java设计模式 - 数据访问对象模式 数据访问对象模式或DAO模式将数据访问API与高级业务服务分离。 DAO模式通常具有以下接口和类。 数据访问对象接口定义模型对象的标准操作。 数据访问对象类实现以上接口。可能有多个实现&#xff0c;例如&#xff0c…
阅读更多...
关于Redis缓存一致性问题的优化和实践

关于Redis缓存一致性问题的优化和实践

目录标题 导语正文分布式场景下无法做到强一致即使是达到最终一致性也很难缓存的一致性问题缓存是如何写入的 如何感知数据库的变化最佳实践一&#xff1a;数据库变更后失效缓存最佳实践二&#xff1a;带版本写入 总结与展望阿里XKV腾讯DCache 导语 Redis缓存一致性的问题是经…
阅读更多...
【API安全】威胁猎人发布超大流量解决方案

【API安全】威胁猎人发布超大流量解决方案

随着数字化进程加速&#xff0c;企业API接口数量激增&#xff0c;已经成为连接内外部服务的重要桥梁。然而&#xff0c;对于拥有庞大的外部客户群体和错综复杂的内部业务系统的大型企业而言&#xff0c;API安全管控面临超大流量下的性能瓶颈与数据安全双重挑战。 性能上&#…
阅读更多...
【软件测试】常用的开发、测试模型

【软件测试】常用的开发、测试模型

哈喽&#xff0c;哈喽&#xff0c;大家好~ 我是你们的老朋友&#xff1a;保护小周ღ 今天给大家带来的是 【软件测试】常用的开发、测试模型&#xff0c;首先了解, 什么是软件的生命周期, 测试的生命周期, 常见的开发模型: 瀑布, 螺旋, 增量, 迭代, 敏捷. 常用的测试模型, …
阅读更多...
Serverless 安全新杀器：云安全中心护航容器安全

Serverless 安全新杀器：云安全中心护航容器安全

作者&#xff1a;胡志广(独鳌) 云安全中心对于 Serverless 容器用户的价值 从云计算发展之初&#xff0c;各大云厂商及传统安全厂商就开始围绕云计算的形态来做安全解决方案。传统安全与云计算安全的形态与做法开始发生变化&#xff0c;同时随着这 10 多年的发展&#xff0c;…
阅读更多...
ThreeJS入门（002）：学习思维路径

ThreeJS入门（002）：学习思维路径

查看本专栏目录 - 本文是第 002篇入门文章 文章目录 如何使用这个思维导图 Three.js 学习思维导图可以帮助你系统地了解 Three.js 的各个组成部分及其关系。下面是一个简化的 Three.js 学习路径思维导图概述&#xff0c;它包含了学习 Three.js 的主要概念和组件。你可以根据这个…
阅读更多...
Redis 入门 - 收官

Redis 入门 - 收官

《Redis 入门》系列文章总算完成了&#xff0c;希望这个系列文章可以想入门或刚入门的同学提供帮助&#xff0c;希望能让你形成学习Redis系统性概念。 当时为什么要写这个系列文章&#xff0c;是因为我自己就是迷迷糊糊一路踩坑走过来的&#xff0c;我踩完的坑就踩完了&#x…
阅读更多...
Kamailio-基于Zabbix+Kamcli的SIP指标监控

Kamailio-基于Zabbix+Kamcli的SIP指标监控

什么是Kamailio? Kamailio 是一个开源的 Session Initiation Protocol (SIP) 服务器&#xff0c;它主要用于建立和管理实时通信会话&#xff0c;如语音和视频通话&#xff0c;与opensips这个产品是同根同源的存在。它们相似&#xff0c;没有更好&#xff0c;是有更合适。 此…
阅读更多...
LLM - 理解 多模态大语言模型 (MLLM) 的指令微调与相关技术 (四)

LLM - 理解 多模态大语言模型 (MLLM) 的指令微调与相关技术 (四)

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/142063880 免责声明&#xff1a;本文来源于个人知识与公开资料&#xff0c;仅用于学术交流&#xff0c;欢迎讨论&#xff0c;不支持转载。 完备(F…
阅读更多...
最新文章

Copyright @ 2022~2023