考研数据结构 01 线性表

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

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

一、线性表

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)

平均复杂度：

假设 ${p\mathop{{}}\nolimits_{{i}}=\frac{{1}}{{n+1}}}$ 是在第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)

平均复杂度：

假设 ${p\mathop{{}}\nolimits_{{i}}=\frac{{1}}{{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)

假设 ${p\mathop{{}}\nolimits_{{i}}=\frac{{1}}{{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 应用中的选择

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

考研数据结构 01 线性表

一、线性表

1.1 线性表基本概念

1.2 线性表基本操作

二、顺序表

2.1 顺序表的定义

2.2 顺序表的操作与实现

2.2.1 插入

2.2.2 删除

2.2.3 按值查找（顺序查找）

三、链表

3.1 单链表

3.2 单链表的操作

3.2.1 新建单链表 - 头插法

3.2.2 新建单链表 - 尾插法

3.2.3 按序号查找

3.2.4 按值查找

3.2.5 插入

3.2.6 删除节点

3.2.7 求表长

3.3 双链表

3.3.1 插入

3.3.1 删除

3.4 循环链表和静态链表

3.5 顺序表和链表的比较

3.5.1 存取方式

3.5.2 逻辑结构与物理结构

3.5.3 查找、插入和删除

3.5.4 空间分配

3.5.5 应用中的选择

Comments | NOTHING

取消回复