考研数据结构 01 线性表

Morning

3 年前

线 性 表 顺 序 存 储 顺 序 表 链 式 存 储 单 链 表 双 链 表 循 环 链 表 指 针 实 现 静 态 链 表 （ 数 组 实 现 ）

考试重点：时间复杂度、空间复杂度的最优性能。

一、线性表

1.1 线性表基本概念

线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，其中n为表长，当n=0时，线性表是一个空表。若用L命名线性表，则其一般表示为L=(a₁, a₂...a_n)。

其中a₁是唯一一个“第一个”数据元素，又称表头元素；a_n是唯一一个“最后元素”，也称表尾元素。除第一个元素外，每一个元素有且仅有一个直接前驱；除最后一个元素外，每一个元素有且仅有一个直接后驱。

特点：

表中元素个数有限。
表中元素具有逻辑上的顺序性，表中元素都有先后顺序。
表中都是数据元素，每个元素都是单个元素。
表中元素数据类型相同，即每个元素占用相同的存储空间。
表中元素具有抽象性，即仅讨论元素直接的逻辑关系，而不考虑元素表示什么内容。

1.2 线性表基本操作

InitList(&L)：初始化，构造空表。
Length(L)：返回表长（元素个数）。
LocateElem(L, e)：返回元素位置，返回int posi。
GetElem(L, i)：获取指定位置的元素值，返回elemType val。
ListInsert(&L, i, e)：位置i处插入元素e，返回bool。
ListDelete(&L, i)：删除位置i处的元素，返回bool。
PrintList(L)：打印。
Empty(L)：判断是否为空，返回bool。
DestoryList(&L)：删除表。

二、顺序表

2.1 顺序表的定义

元素逻辑相邻，地址相邻，这一特性使得顺序表支持随机存储。

顺序表支持动态分配和静态分配，静态分配和平常使用的数组相同。动态分配在表满之后，需要开辟一块大于原来空间的内存，然后将当前表中的内容拷贝过去。

其结构为：

typedef struct{
    elemType data[MaxSize];
    int length;
}sqList;

优点：

随机访问，查找指定下标的时间效率为O(1)。
存储密度高，每个节点值存储数据元素本身。

缺点：

插入和删除需要移动大量元素。

2.2 顺序表的操作与实现

2.2.1 插入

插入元素ele到idx，1 <= idx <= length+1。

bool ListInsert(sqList& L, int idx, elemType ele)
{
    // 边界判断
    if (idx < 1 || idx > L.length + 1)
    {
        return false;
    }
    // 无剩余空间
    else if (L.length >= MaxSize)
    {
        return false;
    }

    // 移动idx以及之后的元素
    for (int idx_move = L.length; idx_move >= idx; --idx_move)
    {
        L.data[idx_move] = L.data[idx_move - 1];
    }
    // 插入新元素
    L[idx-1] = ele;
    L.length++;

    return true;
}

复杂度计算：

最好：O(1)，尾插idx = n + 1。
最坏：O(n)，头插idx = 1。
平均：O(n)

平均复杂度：

假设是在第i个节点上插入一个元素的概率，那么在长度为n的顺序表上插入节点的概率为：

2.2.2 删除

删除idx处的元素，1 <= idx <= length。

bool ListDelete(sqList& L, int idx)
{
    // 边界判断
    if (idx < 1 || idx > L.length)
    {
        return false;
    }

    // 元素前移
    for (int idx_move = idx; idx < L.lenth; ++idx_move)
    {
        L[idx_move-1] = L[idx_move];
    }
    L.length--;

    return true;
}

复杂度计算：

最好：O(1)，尾删idx = n。
最坏：O(n)，头插idx = 1。
平均：O(n)

平均复杂度：

假设是在第i个节点上删除一个元素的概率，那么在长度为n的顺序表上插入节点的概率为：

2.2.3 按值查找（顺序查找）

查找元素ele，1 <= idx <= length。

int LocoteElem(sqList& L, elemType e)
{
    int idx = 0;
    for (; idx < L.length; ++idx)
    {
        if (L.data[idx] == e)
        {
            return idx + 1;
        }
    }

    return 0;
}

复杂度计算：

最好：O(1)，头idx = 1。
最坏：O(n)，尾idx = n，或者元素不存在。
平均：O(n)

假设是在第i个节点上查找到一个元素的概率，那么在长度为n的顺序表上插入节点的概率为：

三、链表

3.1 单链表

线性表的链式存储结构又叫单链表，它指通过一组任意的存储单元来存储线性表中的数据元素。为了建立元素直接的线性关系，对每个链表的阶段，除了存放数据元素外，还要存放一个指向后纪元素的指针。

其节点的结构为：

typedef struct Node{
    elemType data;
    struct Node* next;
}Node;

优点：

插入删除速度快。

缺点：

查找速度慢。

3.2 单链表的操作

3.2.1 新建单链表 - 头插法

将ele插入到链表头部。

// 参数：被插入元素指针、被插入元素个数
Node* Init_Front(elemType* ele, int length)
{
    // 头结点
    Node* head = (Node*)malloc(sizeof(Node));
    head->data = *(ele);
    head->next = NULL;

    // 其余结点
    for (int i = 1; i < length; ++i)
    {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->next = head;
        newNode->data = *(ele + i);

        head = newNode;
    }

    return head;
}

3.2.2 新建单链表 - 尾插法

将ele插入到链表尾部。

// 参数：被插入元素指针、被插入元素个数
Node* Init_Back(elemType* ele, int length)
{
    // 头结点
    Node* head = (Node*)malloc(sizeof(Node));
    head->data = *(ele);
    head->next = NULL;

    // 插入动作指针
    Node* ins = head;

    // 其余结点
    for (int i = 1; i < length; ++i)
    {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = *(ele + i);
        newNode->next = NULL;

        ins->next = newNode;
    }

    return head;
}

3.2.3 按序号查找

这里下标从0开始。

Node* Get_Idx(Node* head, int idx)
{
    Node* poi = head;

    // 边界判断
    if (idx < 0)
    {
        return NULL;
    }

    // 为头结点
    if (idx == 0)
    {
        return poi;
    }

    // 为其他结点
    for (int i = 0; i < idx; ++i)
    {
        if (!poi->next)
        {
            return NULL;
        }

        poi = poi->next;
    }

    return poi;
}

3.2.4 按值查找

返回第一个找到的元素。

Node* Get_Val(Node* head, elemType val)
{
    Node* poi = head;

    while(poi)
    {
        if (poi->data == val)
        {
            return poi;
        }

        poi = poi->next;
    }

    return NULL;
}

3.2.5 插入

结点后插入：

// 参数说明：头结点、插入目标的idx、插入的元素值
bool Insert_Back(Node* head, int idx, elemType ele)
{
    // 获取插入目标
    Node* target = Get_Idx(head, idx);

    // 边界值检测
    if (!target)
    {
        return false;
    }

    // 新节点初始化
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = ele;

    // 尾部
    target->next == NULL ?
        newNode->next = NULL :          // 是尾部，新节点后无节点
    newNode->next = target->next;   // 不是尾部，新节点后接target->next

    target->next = newNode;

    return true;
}

结点前插入：

bool Insert_Front(Node* head, int idx, elemType ele)
{
    // 获取插入目标
    Node* target = Get_Idx(head, idx);

    // 边界值检测
    if (!target)
    {
        return false;
    }

    // 新节点初始化
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = ele;

    // 头部
    if (target == head)
    {
        // 连接
        newNode->next = head;
        // 移动头部指针
        head = newNode;
    }
    else if (target != head)
    {
        // 选择target的前一个节点，转换为尾插
        Insert_Back(head, idx - 1, ele);
    }

    return true;
}

3.2.6 删除节点

按序号（从0计数）删除。

bool Delete_Idx(Node* head, int idx)
{
    // 获取删除目标
    Node* target = Get_Idx(head, idx);

    // 边界值检测
    if (!target)
    {
        return false;
    }

    // 头部
    if (target == head)
    {
        Node* dele = head;
        head = head->next;
        free(dele);
    }
    // 尾部
    else if (target->next == NULL)
    {
        free(target);
    }
    // 中间节点
    else
    {
        Node* target_bf = Get_Idx(head, idx - 1);
        target_bf->next = target->next;
        free(target);
    }

    return true;
}

按值删除。

bool Delete_Val(Node* head, int idx)
{
    // 获取删除目标
    Node* target = Get_Val(head, idx);

    // 边界值检测
    if (!target)
    {
        return false;
    }

    // 头部
    if (target == head)
    {
        Node* dele = head;
        head = head->next;
        free(dele);
    }
    // 尾部
    else if (target->next == NULL)
    {
        free(target);
    }
    // 中间节点
    else
    {
        Node* target_bf = Get_Idx(head, idx - 1);
        target_bf->next = target->next;
        free(target);
    }

    return true;
}

3.2.7 求表长

int length(Node* head)
{
    Node* poi = head;

    int length = 0;

    while (poi)
    {
        length++;
        poi = poi->next;
    }

    return length;
}

3.3 双链表

结构表示如下：

typedef struct dNode
{
    elemType data;
    struct dNnode* prior, next;
}dNnode;

3.3.1 插入

// 现在我们要在prior的后面插入一个元素ele，其指针为ins
// prior为插入的目标，next为其后的一个指针
dNode* prior;
dNode* next;
dNode* ins;

ins->next = next;
ins->prior = prior;

prior->next = ins;
next->prior = ins;

3.3.1 删除

// 现在我们要删除target节点
// prior为其前的节点，next为其后的节点
dNode* prior;
dNode* target;
dNode* next;

prior->next = next;
next->prior = prior;
free(target);

3.4 循环链表和静态链表

没啥好说的，有题难到了再补充。

3.5 顺序表和链表的比较

3.5.1 存取方式

顺序表：顺序、随机。
链表：顺序。

3.5.2 逻辑结构与物理结构

顺序表：逻辑相邻、物理相邻。
链表：逻辑相邻。

3.5.3 查找、插入和删除

按值查找：均为O(n)；注意：对有序顺序表使用折半查找，复杂度为O(log₂n)
按序号查找：顺序表为O(1)，链表为O(n)。
插入与删除：顺序表需要移动元素O(n)，链表无需移动O(1)。但是两者都需要考虑是否查找节点，以及用何种方式查找节点。

3.5.4 空间分配

顺序表：需要预分配大小，如果使用动态分配，则要求内存中有足够大的连续的内存空间支持。
链表：节点在添加元素时申请，无需要求连续空间。

3.5.5 应用中的选择

存储密度：难以估计线性表的长度时或存储规模时，不宜使用线性表；链表存储密度低。
运算：需要随机访问，线性表；需要插入、删除，链表。
环境：线性表容易实现，链表则基于指针，相对难以实现。