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

本文涉及的产品
视觉智能开放平台,视频资源包5000点
视觉智能开放平台,图像资源包5000点
视觉智能开放平台,分割抠图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

上节回顾



课后习题精选:

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

image.gif 编辑

解题思路

>定义标记数组
>记录A中出现正整数情况

image.gif

具体代码实现:

#include <iostream>
#include <string.h>
using namespace std;
#define Maxsize 50
// 定义顺序表结构
typedef struct
{
    int data[Maxsize];  // 存储顺序表中的数据
    int length = 0;     // 当前顺序表的长度
} SqList;
// 插入测试数据函数
void ListInsert(SqList &L)
{
    int val = 0;
    // 从标准输入读取整数
    while (cin >> val)
    {
        // 将输入值存储到顺序表中,并更新长度
        L.data[L.length++] = val;
        // 判断是否为输入行的结束符(回车),若是则停止读取
        if (cin.get() == '\n')
        {
            break;
        }
    }
}
// 打印顺序表函数
void PrintList(SqList L)
{
    for (int i = 0; i < L.length; i++)
    {
        // 打印顺序表中的每个元素,以制表符分隔
        cout << L.data[i] << '\t';
    }
    cout << endl; // 打印换行符
}
// 找到1到n范围内的最小缺失正整数
int FindMin(SqList &L, int n)
{
    int i;
    // 动态分配一个大小为n的数组B
    int *B = new int[n];
    // 将数组B初始化为0
    memset(B, 0, sizeof(int) * n);
    // 遍历顺序表中的数据
    for (i = 0; i < n; i++)
    {
        // 若数据在1到n范围内,则在数组B中对应位置标记为1
        if (L.data[i] > 0 && L.data[i] <= n)
        {
            B[L.data[i] - 1] = 1;
        }
    }
    // 查找数组B中第一个未被标记的位置
    for (i = 0; i < n; i++)
    {
        if (B[i] == 0)
        {
            break;
        }
    }
    // 返回缺失的最小正整数
    return i + 1;
}
int main()
{
    SqList L;      // 创建一个顺序表
    ListInsert(L); // 从输入中插入测试数据
    // 查找并打印1到5范围内的最小缺失正整数
    cout << FindMin(L, 5);
}

image.gif

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

image.gif 编辑

解题思路:


>算法关键就是扫描数组
>标记处一个可能成为主元的元素,然后重新计数
image.gif

具体代码实现:

#include <iostream>
using namespace std;
#define Maxsize 50
// 定义顺序表结构
typedef struct
{
    int data[Maxsize];  // 存储顺序表中的数据
    int length = 0;     // 当前顺序表的长度
} SqList;
// 插入测试数据
void ListInsert(SqList &L)
{
    int val = 0;
    // 从标准输入读取整数
    while (cin >> val)
    {
        // 将输入值存储到顺序表中,并更新长度
        L.data[L.length++] = val;
        // 判断是否为输入行的结束符(回车),若是则停止读取
        if (cin.get() == '\n')
        {
            break;
        }
    }
}
// 打印顺序表
void PrintList(SqList L)
{
    for (int i = 0; i < L.length; i++)
    {
        // 打印顺序表中的每个元素,以制表符分隔
        cout << L.data[i] << '\t';
    }
    cout << endl; // 打印换行符
}
// 查找出现次数超过一半的元素
int MainValue(SqList &L, int n)
{
    int i, c, count = 1;
    c = L.data[0]; // 初始候选元素为第一个元素
    // 遍历顺序表中的数据,确定可能的多数元素
    for (i = 1; i < n; i++)
    {
        if (L.data[i] == c)
        {
            count++; // 如果当前元素等于候选元素,则计数器加1
        }
        else
        {
            if (count > 0)
            {
                count--; // 如果当前元素与候选元素不同且计数器大于0,则计数器减1
            }
            else
            {
                c = L.data[i]; // 选择新的候选元素
                count = 1;    // 重置计数器为1
            }
        }
    }
    // 再次遍历确认候选元素是否真的出现次数超过一半
    if (count > 0)
    {
        for (i = count = 0; i < n; i++)
        {
            if (L.data[i] == c)
            {
                count++; // 统计候选元素的实际出现次数
            }
        }
    }
    // 如果候选元素的出现次数超过一半,则返回该元素,否则返回-1
    if (count > n / 2)
    {
        return c;
    }
    else
    {
        return -1;
    }
}
int main()
{
    SqList L;      // 创建一个顺序表
    ListInsert(L); // 从输入中插入测试数据
    // 查找并打印出现次数超过一半的元素
    cout << MainValue(L, 5);
}

image.gif

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

image.gif 编辑

解题思路

>分成3种情况,相等、小于、大于
>等于直接返回
>小于、大于分别减半
image.gif

具体代码实现

#include <iostream>
using namespace std;
#define Maxsize 50
// 定义顺序表结构
typedef struct
{
    int data[Maxsize];  // 存储数据的数组
    int length = 0;     // 顺序表的当前长度
} SqList;
// 插入测试数据
void ListInsert(SqList &L)
{
    int val = 0;
    while (cin >> val) // 从标准输入读取数据
    {
        L.data[L.length++] = val; // 将读取的值插入顺序表,并增加长度
        if (cin.get() == '\n') // 检测到换行符,结束输入
        {
            break;
        }
    }
}
// 打印顺序表
void PrintList(SqList L)
{
    for (int i = 0; i < L.length; i++)
    {
        cout << L.data[i] << '\t'; // 打印顺序表中的每个元素
    }
    cout << endl;
}
// 题目功能函数:查找两个排序数组中的中位数
int SearchMid(SqList &L1, SqList &L2, int n)
{
    int s1 = 0, d1 = n - 1; // L1 的开始和结束下标
    int m1, s2 = 0, d2 = n - 1; // L2 的开始和结束下标
    int m2;
    while (s1 != d1 || s2 != d2) // 当两个数组还没有缩小到只有一个元素时
    {
        m1 = (s1 + d1) / 2; // L1 的中间下标
        m2 = (s2 + d2) / 2; // L2 的中间下标
        if (L1.data[m1] == L2.data[m2]) // 如果中间元素相等,则找到中位数
        {
            return L1.data[m1];
        }
        if (L1.data[m1] < L2.data[m2]) // 如果 L1 中的中间元素小于 L2 中的中间元素
        {
            if ((s1 + d1) % 2 == 0) // 如果 L1 的当前区间大小为偶数
            {
                s1 = m1; // 将 L1 的起始位置更新为 m1
                d2 = m2; // 将 L2 的结束位置更新为 m2
            }
            else // 如果 L1 的当前区间大小为奇数
            {
                s1 = m1 + 1; // 将 L1 的起始位置更新为 m1 + 1
                d2 = m2; // 将 L2 的结束位置更新为 m2
            }
        }
        else // 如果 L1 中的中间元素大于 L2 中的中间元素
        {
            if ((s2 + d2) % 2 == 0) // 如果 L2 的当前区间大小为偶数
            {
                d1 = m1; // 将 L1 的结束位置更新为 m1
                s2 = m2; // 将 L2 的起始位置更新为 m2
            }
            else // 如果 L2 的当前区间大小为奇数
            {
                d1 = m1; // 将 L1 的结束位置更新为 m1
                s2 = m2 + 1; // 将 L2 的起始位置更新为 m2 + 1
            }
        }
    }
    // 返回最终中位数,取两个数组中当前位置的较小值
    return L1.data[s1] < L2.data[s2] ? L1.data[s1] : L2.data[s2];
}
int main()
{
    SqList L1, L2;  // 创建两个顺序表
    ListInsert(L1); // 插入测试数据到 L1
    ListInsert(L2); // 插入测试数据到 L2
    cout << SearchMid(L1, L2, 5); // 输出两个排序数组中位数
}

image.gif

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

image.gif 编辑

解题思路:

>将子数组逆转3次
image.gif

具体代码实现:

#include <iostream>
using namespace std;
#define Maxsize 50
// 定义顺序表结构
typedef struct
{
    int data[Maxsize];  // 存储顺序表中的数据
    int length = 0;     // 当前顺序表的长度
} SqList;
// 插入测试数据
void ListInsert(SqList &L)
{
    int val = 0;
    // 从标准输入读取整数
    while (cin >> val)
    {
        // 将输入值存储到顺序表中,并更新长度
        L.data[L.length++] = val;
        // 判断是否为输入行的结束符(回车),若是则停止读取
        if (cin.get() == '\n')
        {
            break;
        }
    }
}
// 打印顺序表
void PrintList(SqList L)
{
    for (int i = 0; i < L.length; i++)
    {
        // 打印顺序表中的每个元素,以制表符分隔
        cout << L.data[i] << '\t';
    }
    cout << endl; // 打印换行符
}
// 逆转数组的部分元素
void Reverse(SqList &L, int left, int right)
{
    // 将指定区间 [left, right] 的元素交换以实现逆转
    for (int i = 0; i < (right - left + 1) / 2; i++)
    {
        int temp = L.data[i + left];
        L.data[i + left] = L.data[right - i];
        L.data[right - i] = temp;
    }
}
// 逆转顺序表的两部分以及整个数组
void ReverseList(SqList &L, int p)
{
    // 逆转前 p 个元素
    Reverse(L, 0, p - 1);        
    // 逆转从 p 到最后的元素
    Reverse(L, p, L.length - 1); 
    // 逆转整个数组
    Reverse(L, 0, L.length - 1); 
}
int main()
{
    SqList L;      // 创建一个顺序表
    ListInsert(L); // 从输入中插入测试数据
    // 逆转顺序表中的前 3 个元素,以及从第 3 个元素开始的其余部分,然后逆转整个数组
    ReverseList(L, 3);
    // 打印逆转后的顺序表
    PrintList(L);
}
image.gif

,,,

相关文章
|
29天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
29天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
27天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
123 9
|
18天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
22 1
|
5天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
26 5
|
20天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
23天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。

热门文章

最新文章