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

盛透侧视攻城狮

发布于 2024-10-22 09:24:56

2410

文章被收录于专栏：超前沿网络空间安全全栈学习宝典超前沿网络空间安全全栈学习宝典

数据结构王道第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。
什么时候要传入参数的引用“&”： 对参数的修改结果需要“带回来”，是引用类型而不是值类型

顺序表的实现-静态分配

顺序表的静态分配初始化

#define MaxSize 10      // 定义最大长度
typedef struct{
    ElemType data[MaxSize];     // 用静态的“数组”存放数据元素
    int length;     // 顺序表的当前长度
}SqList;

#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;
}

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

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

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

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

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

顺序表的实现：

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

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

#define InitSize 10     // 顺序表的初始长度
typedef struct
{
    ElemType *data;     // 指示动态分配数组的指针，这个指针指向顺序表中第一个数据元素
    int MaxSize;        // 顺序表的最大容量
    int length;     // 顺序表的当前长度
} SeqList;      // 顺序表的类型定义（动态分配方式）

// 动态申请和释放空间

// 在C语言中的函数分别是malloc和free函数
// malloc函数是申请一整片连续的内存空间，且会return一个指向这一整片存储空间开始地址的指针，需要强制转型为你定义的数据元素类型的指针
// L.data = (ElemType *)malloc(sizeof(ElemType) * InitSize);
// malloc和free包含在<stdlib.h>头文件中

// 在C++语言中分别是new和delete这两个关键字

这样就可以让顺序表的容量可变
虽然动态分配可以使顺序表的大小可以灵活改变，但是时间开销还是比较大的（复制元素）
注意malloc和free是一对函数
free函数会把p这个指针所指向的这一整片的存储空间给释放掉，归还给系统，然后由于p是局部于这个函数的变量，函数结束后，存储p这个变量的存储空间会被系统自动回收

#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;
}

顺序表的特点

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

顺序表的插入删除

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

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;
}

增加i的合法性判断：

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

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不合法，删除失败");
}

ListDelete(&L, i, &e) ：删除操作，删除表L中第i个位置的元素，并用e返回删除元素的值
因为要返回e，所以这要有一个引用操作，因此，在这个函数中操作的变量e，在内存中其实对应的是同一份数据
在删除操作中是先移动前面的元素再移动后面的元素，而在插入操作中要把元素往后移时，先把后面的元素往后移，然后再移前面的元素

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

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

顺序表的查找

顺序表的按位查找：

顺序表的按位查找代码

// 静态分配实现顺序表，动态分配实现的顺序表也是如此
ElemType GetElem(SqList L, int i)
{
    // 判断i合法性
    
    return L.data[i - 1];
}

GetElem(L, i) ：按位查找操作。获取表L中第i个位置的元素的值
正是如此，在初始化顺序表时候malloc需要强制转换为与数据元素的数据类型相对应的指针
时间复杂度= O(1)
随机存取：由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素，

顺序表的按值查找：

顺序表的按值查找代码

#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;
}

LocateElem(L, e) ：按值查找操作，在表L中查找具有给定关键字值的元素
结构类型的数据元素也能用 == 比较吗：不能！（C++可以用 == 的重载来实现）
更好的办法：定义一个函数
依次对比各个分量来判断两个结构体是否相等
最好时间复杂度= O(1)
最坏时间复杂度= O(n)
平均时间复杂度= O(n)

结构类型的比较

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

课后习题精选：

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

解题思路

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

具体代码实现：

#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);
}

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

解题思路：

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

具体代码实现：

#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);
}

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

解题思路

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

具体代码实现

#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); // 输出两个排序数组中位数
}

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

解题思路：

>将子数组逆转3次

具体代码实现：

#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);
}

~~,,,~~

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-10-21，如有侵权请联系 cloudcommunity@tencent.com 删除

函数