考研数据结构 01 线性表

发布于 2021-08-31  77 次阅读


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

一、线性表

1.1 线性表基本概念

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

  其中a1是唯一一个“第一个”数据元素,又称表头元素;an是唯一一个“最后元素”,也称表尾元素。除第一个元素外,每一个元素有且仅有一个直接前驱;除最后一个元素外,每一个元素有且仅有一个直接后驱。

  特点:

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

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(log2n)
  • 按序号查找:顺序表为O(1),链表为O(n)。
  • 插入与删除:顺序表需要移动元素O(n),链表无需移动O(1)。但是两者都需要考虑是否查找节点,以及用何种方式查找节点。

3.5.4 空间分配

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

3.5.5 应用中的选择

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