Skip to content

0x02 线性表

一、线性表总述

1.1 线性表的特征

  • 数据元素具有相同的数据类型（所占空间相等）
  • 数据元素为有限个
  • 是序列，有次序，除第一个元素外每个元素都有唯一前驱，除最后一个元素外每个元素都有唯一后继
  • 数据元素的位序：从1开始

1.2 线性表的基本操作

  • 初始化表。构造一个空的线性表L，并分配内存空间

  • 销毁表，释放L所占用的内存空间

  • 插入。在表L的第i个位置上插入指定元素e
  • 删除。删除表L中第i个位置的元素，并用e返回删除元素的值
  • 按值查找
  • 按位查找
  • 求表长
  • 输出操作
  • 判空操作

二、顺序表

2.1 顺序表的定义

顺序表——用顺序存储（物理结构）方式实现线性表（逻辑结构）

2.2 顺序表的实现

静态分配：事先在内存中开辟一整片连续空间

typedef struct{
    ElemType *data;
    int MaxSize;
    int length;
} SeqList;

动态分配：malloc 返回一个指针变量，这个指针变量存放所申请的内存空间的起始地址；free释放空间。注意，顺序表结构中只有一个指针变量表明顺序表内存空间起始地址，所以像链表一样在已有的基础上追加空间是不可能的。这里的动态分配实际上是：按新的大小需求重新开辟一片连续空间→让顺序表指针指向新空间的起始地址→将原空间上的数据复制到新空间→释放原空间。

typedef struct{
    int *data;      //指示分配到的内存空间的起始地址
    int MaxSize;
    int length;
} SeqList;

2.3 顺序表的特点

  • 随机访问，即可以在$O(1)$时间内找到第$i$个元素
  • 存储密度高，每个节点都只存储数据元素（而不用像链表一样需要额外空间供指针使用）
  • 拓展容量不方便（即使是动态分配，时间复杂度也较高）
  • 插入、删除元素不方便，需要移动大量元素

2.4 顺序表的基本操作

插入

void ListInsert(SqList &L, int i, int e){
    for (int j = L.length; j>=i; j--){
        L.data[j] = L.data[j-1];
    }
    // 全部后移，直到腾出下标为i-1的位置
    L.data[i-1] = e;
    L.length ++;
}

时间复杂度分析：

  • 最好：$O(1)$
  • 最坏：$O(n)$
  • 平均时间复杂度：$O(n)$

删除

bool ListDelete(SqList &L, int i, int &e){
    if (i<1 || i>L.length) return false;
    e = L.data[i-1]; // 参数i是从1起计的位序，对应的实际下标是i-1
    for(int j=i; j<L.length; j++){
        L.data[j-1] = L.data[j];
    }
    //全部前移
    L.length -- ;
    return true;
}

时间复杂度分析：

  • 最好：$O(1)$
  • 最坏：$O(n)$
  • 平均时间复杂度：$O(n)$

按位查找

  • 最好：$O(1)$
  • 最坏：$O(1)$
  • 平均时间复杂度：$O(1)$

按值查找

时间复杂度分析：

  • 最好：$O(1)$
  • 最坏：$O(n)$
  • 平均时间复杂度：$O(n)$

三、单链表

3.1 单链表的定义

单链表——用链式存储的方式实现的线性表。

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;
//等价于以下声明
//typedef struct LNode LNode;
//typedef struct LNode *LinkList;

这样声明可以很好地区分一个指针代表的一整个链表 和 单个结点

LinkList L; //强调声明的是一个指针所代表的一整个链表，实际上是LNode* L;

LNode* p; //强调声明的是单个结点
  • 带头节点和不带头节点的区别
  • 不带头节点：空表判断L==NULL
  • 带头节点：头节点不存储数据，只是为了操作方便，空表判断L->next==NULL

3.2 单链表的插入删除

带头结点的插入

注意：参数中的i是位序，表示插入到头节点后的第i个结点

bool ListInsert(LinkList &L, int i, ElemType e){
    if( i < 1 ) return false;
    LNode *p;   //当前扫描到的结点
    int j = 0;  //当前扫描到的结点是头节点后的第j个结点
    p = L;      //首先从头节点开始扫描
    while( p != NULL && j < i-1){
        p = p -> next;
        j ++;
    }
    //跳出循环，但无法确定是因为p==NULL跳出的还是因为j==i-1跳出的
    if (p == NULL) return false;
    //若判断通过，此时p一定为头节点后的第i-1个结点
    //将新插入的结点接到p后面，即可保证新节点是头节点后的第i个结点
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

不带头结点的插入

指定结点的后插操作

bool InsertNextNode(LNode *p, ElemType e){
    if (p==NULL) return false;
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

指定结点的前插操作

思路：结点保留，数据转移。如需要在p结点前插入一个含数据e的新结点，则直接在p结点后插一个新结点，让p结点中的数据移到新结点，再将数据e赋给p结点即可。

按位序删除

指定结点的删除

3.3 单链表的查找

3.4 单链表的建立

  • 尾插法：每次都在链表末尾元素的后面插入新元素
bool CreateList_TailInsert(LinkList &L){
  int x;
    L = (LinkList)malloc(sizeof(LNode));
    L -> next = NULL;
    LNode *s, *r = L;
    scanf("%d", &x);
    while(x!=9999){ //9999为结束标志
        LNode *t = (LNode*)malloc(sizeof(LNode));
        t->data = x;
        r->next = t;
        r = t;
        scanf("%d", &x);
    }
    r->next = NULL;
    return L;
}
  • 头插法：每次都在头结点的后面插入新元素

可以用于链表的逆转

bool CreateListList_HeadInsert(LinkList &L){
  L = (LinkList)malloc(sizeof(LNode));
    L -> next = NULL;
    int x;
    scanf("%d", &x);
    while(x!=9999){
        LNode *t = (LNode*)malloc(sizeof(LNode));
        t->data = x;
        t->next = L->next;
        L->next = t;
        scanf("%d", &x);
  }
    return L;
}

四、双链表

既有前驱指针又有后继指针的链表为双链表。

 typedef struct DNode{
    ElemType data;
    struct DNode *prior,*next;
 }DNode, *DLinklist;

4.1 双链表的初始化

bool InitDLinkList(DLinklist &L){
    L = (DLinklist)malloc(sizeof(DNode));
    if (L == NULL) return false;
    L->prior = NULL;
    L->next = NULL;
    return true;
}

4.2 双链表的插入

bool ListInsert(DNode* p, DNode* s){ //在指定结点p后插入结点s
    if(p == NULL || s == NULL) return false;
    s->next = p->next; //此时s的后继要么是NULL，要么是一个结点
    s->prior = p;
    if(p->next != NULL){
        p->next->prior = s;
    }
    p->next = s;
}

4.3 双链表的删除

bool DeleteNextNode(DNode *p){  //删除指定结点p的后一个结点
    if (p == NULL || p->next == NULL) return false;
    DNode *q = p->next;
    p->next = q->next; //要么是NULL要么是一个结点
    if(q->next != NULL){
        q->next->prior = p;
    }
    free(q);
    return true;
}

4.4 双链表的遍历

五、循环链表

循环链表的最后一个元素的后继指针一定指向头结点。

对于空的循环双链表，有L->next = L，L->prior = L

//判空
bool isEmpty(LinkList L){
    return L->next == L;
}
//判表尾 
bool isTail(LinkList L, LNode *p){
    return p->next == L;
}

六、静态链表

分配一整片连续的内存空间，各个结点集中安置。但物理结构上仍是链式存储的。

特点在于后继/前驱结点的指向不必使用指针，直接使用一个整型作为下标来代表即可，因为内存空间是连续的，可以根据整型算出下一个结点地址。然而由于指向是灵活的，虽然各结点都在同一片内存空间中，逻辑上相邻的结点在物理上仍可以不相邻。

对于表尾结点的后继结点，下标为-1

6.1 操作

  • 查找：仍是O(n)的，因为逻辑上的第i个结点在物理上不一定是第i个，无法随机访问
  • 插入：设要在位序i插入一个新节点。先找到一个空结点，再找到位序i-1的结点，然后修改新结点的next为i-1结点的next，再修改i-1结点的next为新结点。
  • 结点判空：next为特殊值如-2，即视为空结点

6.2 优缺点

优点：增、删操作不需要大量移动元素

缺点：不能随机存取，容量固定不可变

6.3 应用

适用于在不支持指针的低级语言、数据元素数量固定不变的场景。

如操作系统的文件分配表FAT

七、比较与评价

比较不同数据结构的优缺点，从以下三方面考虑：

  1. 逻辑结构：特点与优缺点
  2. 物理结构：特点与优缺点
  3. 基本操作（增删查）：时间复杂度