2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】

本文涉及的产品
实时数仓Hologres,5000CU*H 100GB 3个月
检索分析服务 Elasticsearch 版,2核4GB开发者规格 1个月
智能开放搜索 OpenSearch行业算法版,1GB 20LCU 1个月
简介: 顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明

欢迎各位彦祖与热巴畅游本人专栏与博客

你的三连是我最大的动力

以下图片仅代表专栏特色 [点击箭头指向的专栏名即可闪现]

专栏跑道一

➡️网络空间安全——全栈前沿技术持续深入学习

image.gif 编辑

专栏跑道二

➡️ 24 Network Security -LJS

image.gif 编辑

image.gif 编辑

image.gif 编辑

专栏跑道三


➡️ MYSQL REDIS Advance operation

image.gif 编辑

专栏跑道四

➡️HCIP;H3C-SE;CCIP——LJS[华为、华三、思科高级网络]

image.gif 编辑

专栏跑道五

➡️RHCE-LJS[Linux高端骚操作实战篇]

image.png

专栏跑道六

➡️数据结构与算法[考研+实际工作应用+C程序设计]

image.gif 编辑

专栏跑道七

➡️RHCSA-LJS[Linux初级及进阶骚技能]

image.gif 编辑

image.gif

上节回顾



 目录

数据结构王道第2章之顺序表

顺序表的定义和基本操作

定义:

基本操作:

基本操作:

编辑

顺序表的实现-静态分配编辑

 

顺序表的静态分配初始化

如果“数组”存满了怎么办:

顺序表的实现-动态分配:

编辑

顺序表的动态分配初始化代码

顺序表的特点

顺序表的插入删除

顺序表的基本操作-插入:

编辑

增加i的合法性判断:编辑

顺序表的基本操作——删除编辑

插入和删除的时间复杂度:

顺序表的查找

顺序表的按位查找:编辑

顺序表的按位查找代码

顺序表的按值查找:编辑

顺序表的按值查找代码

结构类型的比较

课后习题精选:

(13):给定一个含n个整数的数组Q,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数

编辑

解题思路

具体代码实现:

(12):已知一个整数序列A=(a0,a1,an-1),其中若存在则称x为A的主元素。

解题思路:

具体代码实现:

(11):一个长度为L的升序序列S,处在第L/2个位置的数称为S的中位数,例如,若序列则S1的中位数是15,两个序列的中位数是11,现在有两个等长升序A和B

解题思路

具体代码实现

(10) :一个长度为L的升序序列S,处在第L/2个位置的数称为S的中位数,例如,若序列则S1的中位数是15,两个序列的中位数是11,现在有两个等长升序A和B

编辑

解题思路:

具体代码实现:


数据结构王道第2章之顺序表

顺序表的定义和基本操作

定义:

基本操作:

  • 用顺序存储的方式实现线性表顺序存储,把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中,元素之间的关系由存储单元的邻接关系来体现

基本操作:

  • InitList(&L):初始化表。构造一个空的线性表L,分配内存空间
  • DestroyList(&L):销毁操作。销毁线性表,并释放线性表L所占用的内存空间
  • ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e
  • ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素,并用e返回删除元素的值
  • LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素
  • GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值
  • Length(L):求表长。返回线性表L的长度,即L中数据元素的个数
  • PrintList(L):输出操作。按前后顺序输出线性表L的所有元素值
  • Empty(L):判空操作。若L为空表,则返回true,否则返回false
  • 什么时候要传入参数的引用“&”对参数的修改结果需要“带回来”,是引用类型而不是值类型

image.gif

顺序表的实现-静态分配 image.gif

image.gif 编辑

顺序表的静态分配初始化

#define MaxSize 10      // 定义最大长度
typedef struct{
    ElemType data[MaxSize];     // 用静态的“数组”存放数据元素
    int length;     // 顺序表的当前长度
}SqList;
image.gif
#include <stdio.h>
#define MaxSize 10
typedef struct{
    int data[MaxSize];
    int length;
}SqList;
void InitList(SqList &L)
{
    // 可以省略,但可能由于遍历时用到MaxSize有脏数据,要用length遍历
    for (int i = 0; i < MaxSize; i ++ )
        L.data[i] = 0;
    
    L.length = 0;       // 不可省略,顺序表初始长度为0
}
int main()
{
    SqList L;       // 声明一个顺序表
    InitList(L);        // 初始化顺序表
    
    return 0;
}
image.gif

如果“数组”存满了怎么办:

可以放弃治疗,顺序表的表长刚开始确定后就无法更改(存储空间是静态的),同时如果提前初始化太多的空间而不用,又会造成资源的浪费,因此动态分配应运而生。

动态申请和释放内存空间:

  • C:malloc、free函数
  • L.data = (ElemType *) malloc (sizeof(ElemType) * InitSize);
  • malloc函数返回一个指针, 空间需要强制转型为你定义的数据元素类型指针
  • malloc函数的参数指明要分配多大的连续内存空间
  • C++: new、delete关键字

顺序表的实现-动态分配:

image.gif

顺序表的实现:

  • 随机访问,即可以在O(1)时间内找到第i个元素。
  • 存储密度高,每个结点只存储数据元素
  • 拓展容量不方便(即便采用动态分配的方式实现,拓展长度的时间复杂度也比较高)
  • 插入、删除操作不方便,需要移动大量元素

顺序表的动态分配初始化代码

#define InitSize 10     // 顺序表的初始长度
typedef struct
{
    ElemType *data;     // 指示动态分配数组的指针,这个指针指向顺序表中第一个数据元素
    int MaxSize;        // 顺序表的最大容量
    int length;     // 顺序表的当前长度
} SeqList;      // 顺序表的类型定义(动态分配方式)
image.gif
// 动态申请和释放空间
// 在C语言中的函数分别是malloc和free函数
// malloc函数是申请一整片连续的内存空间,且会return一个指向这一整片存储空间开始地址的指针,需要强制转型为你定义的数据元素类型的指针
// L.data = (ElemType *)malloc(sizeof(ElemType) * InitSize);
// malloc和free包含在<stdlib.h>头文件中
// 在C++语言中分别是new和delete这两个关键字
image.gif
  • 这样就可以让顺序表的容量可变
  • 虽然动态分配可以使顺序表的大小可以灵活改变,但是时间开销还是比较大的(复制元素)
  • 注意malloc和free是一对函数
  • free函数会把p这个指针所指向的这一整片的存储空间给释放掉,归还给系统,然后由于p是局部于这个函数的变量,函数结束后,存储p这个变量的存储空间会被系统自动回收

image.gif 编辑

#include <stdlib.h>
#define InitSize 10
typedef struct
{
    int *data;
    int MaxSize;
    int length;
} SeqList;
void InitList(SeqList &L)
{
    L.data = (int *)malloc(sizeof(int) * InitSize);
    L.MaxSize = InitSize;
    L.length = 0;
}
void IncreaseSize(SeqList &L, int len)
{
    int *p = L.data;
    L.data = (int *)malloc(sizeof(int) * (L.MaxSize + len));
    for (int i = 0; i < L.length; i ++ )
        L.data[i] = p[i];
    L.MaxSize = L.MaxSize + len;
    free(p);
}
int main()
{
    SeqList L;
    InitList(L);
    // ...往顺序表中随意随便插入几个元素
    IncreaseSize(L, 5);
    return 0;
}
image.gif

顺序表的特点

  • 随机访问,即可以在O ( 1 ) O(1)O(1)时间内找到第i个元素(不论是静态分配还是动态分配代码都是d a t a [ i − 1 ] data[i - 1]data[i−1]
  • 存储密度高,每个节点只存储数据元素(链表还要存指针)
  • 拓展容量不方便(即便采用动态分配的方式实现,拓展长度的时间复杂度也比较高)
  • 插入、删除操作不方便,需要移动大量元素

image.gif

顺序表的插入删除

顺序表的基本操作-插入:

image.gif

  • ListInsert(&L, i, e) :插入操作,在表L中的第i个位置(位序)插入指定元素i
  • 本节代码建立在顺序表的“静态分配”实现方式之上,“动态分配”也雷同。
  • 时间复杂度的平均情况 :p = 1 / ( n + 1 ) p=1/(n+1)p=1/(n+1);i=1,循环n次,i=2,循环n-1次…;平均循环次数= n p + ( n − 1 ) ∗ p + . . . + 1. p = n ∗ ( n + 1 ) / 2 ∗ 1 / ( n + 1 ) = n / 2 =np+(n-1)*p+...+1.p=n*(n+1)/2*1/(n+1)=n/2=np+(n−1)∗p+...+1.p=n∗(n+1)/2∗1/(n+1)=n/2
#define MaxSize 10
typedef struct
{
    int data[MaxSize];
    int length;
} SqList;
bool ListInsert(SqList &L, int i, int e)
{
    if (i < 1 || i > L.length + 1)      // 判断i的范围是否有效
        return false;
    if (L.length == MaxSize)        // 当前存储空间已满,不能插入
        return false;
    for (int j = L.length; j >= i; j -- )       // 将第i个元素及之后的元素后移
        L.data[j] = L.data[j - 1];
    L.data[i - 1] = e;      // 在位置i处放e
    L.length ++ ;       // 长度加1
    
    return true;        // 反馈
}
int main()
{
    SqList L;
    InitList(L);
    // ...插入一些元素
    ListInsert(L, 5, 5);
    
    return 0;
}
  • image.gif

增加i的合法性判断: image.gif

顺序表的基本操作——删除 image.gif

bool ListDelete(SqList &L, int i, int &e)
{
    if (i < 1 || i > L.length)      // 判断i的范围是否有效
        return false;
    
    e = L.data[i - 1];      // 将被删除的元素赋给e
    
    for (int j = i; j < L.length; j ++ )        // 将第i个位置后的元素前移
        L.data[j - 1] = L.data[j];
    
    L.length -- ;     // 线性表长度减一
    
    return true;
}
int main()
{
    SqList L;
    InitList(L);
    // ...插入一些元素
    
    int e = -1;     // 用变量e把删除的元素“带回来”
    
    if (ListDelete(L, 3, e))
        printf("已删除第3个元素,删除元素值为=%d\n", e);
    else
        printf("位序i不合法,删除失败");
}
image.gif
  • ListDelete(&L, i, &e) :删除操作,删除表L中第i个位置的元素,并用e返回删除元素的值
  • 因为要返回e,所以这要有一个引用操作,因此,在这个函数中操作的变量e,在内存中其实对应的是同一份数据
  • 在删除操作中是先移动前面的元素再移动后面的元素,而在插入操作中要把元素往后移时,先把后面的元素往后移,然后再移前面的元素

插入和删除的时间复杂度:

  • 最好时间复杂度= O(1)
  • 最坏时间复杂度= O(n)
  • 平均时间复杂度= O(n)

image.gif

顺序表的查找

顺序表的按位查找: image.gif

顺序表的按位查找代码

// 静态分配实现顺序表,动态分配实现的顺序表也是如此
ElemType GetElem(SqList L, int i)
{
    // 判断i合法性
    
    return L.data[i - 1];
}
image.gif
  • GetElem(L, i) :按位查找操作。获取表L中第i个位置的元素的值
  • 正是如此,在初始化顺序表时候malloc需要强制转换为与数据元素的数据类型相对应的指针
  • 时间复杂度= O(1)
  • 随机存取:由于顺序表的各个数据元素在内存中连续存放,因此可以根据起始地址和数据元素大小立即找到第i个元素,

顺序表的按值查找: image.gif

顺序表的按值查找代码

#define InitSize 10
typedef struct
{
    ElemType *data;
    int MaxSize;
    int length;
} SeqList;
ElemType LocateElem(SeqList L, ElemType e)
{
    for (int i = 0; i < L.length; i ++ )
        if (L.data[i] == e)
            return i + 1;       // 返回位序
    return 0;
}
image.gif
  • LocateElem(L, e) :按值查找操作,在表L中查找具有给定关键字值的元素
  • 结构类型的数据元素也能用 == 比较吗:不能!(C++可以用 == 的重载来实现)
  • 更好的办法:定义一个函数
  • 依次对比各个分量来判断两个结构体是否相等
  • 最好时间复杂度= O(1)
  • 最坏时间复杂度= O(n)
  • 平均时间复杂度= O(n)

结构类型的比较

  • 在C语言中,结构类型的比较不能直接用“==”,需要依次对比各个分量来判断两个结构体是否相等;如果C++,则可以用重载 “= =“。
  • 但是,《数据结构》考研初试中,手写代码可以直接用“= =”,无论ElemType是基本数据类型还是结构类型。但是有的学校考《C语言程序设计》,那么也许语言就要严格一些。最好还是看一下相关的历年真题。






相关文章
|
18天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
18天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
18天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
18天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
25天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
10天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。
|
11天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。
|
12天前
|
存储 算法 决策智能
基于免疫算法的TSP问题求解matlab仿真
旅行商问题(TSP)是一个经典的组合优化问题,目标是寻找经过每个城市恰好一次并返回起点的最短回路。本文介绍了一种基于免疫算法(IA)的解决方案,该算法模拟生物免疫系统的运作机制,通过克隆选择、变异和免疫记忆等步骤,有效解决了TSP问题。程序使用MATLAB 2022a版本运行,展示了良好的优化效果。
|
11天前
|
机器学习/深度学习 算法 芯片
基于GSP工具箱的NILM算法matlab仿真
基于GSP工具箱的NILM算法Matlab仿真,利用图信号处理技术解析家庭或建筑内各电器的独立功耗。GSPBox通过图的节点、边和权重矩阵表示电气系统,实现对未知数据的有效分类。系统使用MATLAB2022a版本,通过滤波或分解技术从全局能耗信号中提取子设备的功耗信息。
|
11天前
|
机器学习/深度学习 算法 5G
基于MIMO系统的SDR-AltMin混合预编码算法matlab性能仿真
基于MIMO系统的SDR-AltMin混合预编码算法通过结合半定松弛和交替最小化技术,优化大规模MIMO系统的预编码矩阵,提高信号质量。Matlab 2022a仿真结果显示,该算法能有效提升系统性能并降低计算复杂度。核心程序包括预编码和接收矩阵的设计,以及不同信噪比下的性能评估。
30 3