第二章线性表

2.1.1线性表的定义

定义：

线性表(Linear List)是具有相同数据类型的n（n≥0）个数据元素的有限序列，其中n为表长，当n = 0时线性表是一个空表

若用L命名线性表，则其一般表示为L = (a1, a2, … , ai, ai+1, … , an)

存储/物理结构分为顺序存储和链式存储

注：需理解以下几个概念

每个数据元素的数据类型都一样且所占空间一样大

表序列有次序，位序从1开始，数组下标从0开始，位序号=数组号+1

ai是线性表中的“第i个”元素线性表中的位序。a1是表头元素；an是表尾元素。

表头元素无前驱，表尾元素无后继：除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继

2.1.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。

注：

1.对数据的操作（记忆思路）： 创销、增删改查 （所有数据结构都适用）

2.C语言函数的定义 ：<返回值类型> 函数名 (<参数1类型> 参数1，<参数2类型> 参数2，……)

3.实际开发中，可根据实际需求定义其他的基本操作

4.函数名和参数的形式、命名都可改变，但要有可读性

5.什么时候要传入引用“&” —对参数的修改结果需要“带回来” （重点理解）

2.2.1顺序表的定义

定义：

顺序表—用顺序存储的方式实现的线性表

顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

设线性表第一个元素a1的存放位置是 LOC (L)，则an=LOC (L)+(n-1)×数据元素的大小

如何知道一个数据元素大小：C语言 sizeof(ElemType)，ElemType 是顺序表中存放的数据元素类型

顺序表的实现-静态分配：存储空间是静态的

 //顺序表的定义
 #define MaxSize 10 //定义最大长度
 typedef struct{
 ElemType data[MaxSize]; //用静态的“数组”存放数据元素
 int length; //顺序表的当前长度
 }SqList; //顺序表的类型定义（静态分配方式）
 ​
 //初始化顺序表
 void InitList(SqList &L){
 ②    for(int i=0; i<MaxSize; i++)
         L.data[i]=0;     //将所有数据元素设置为默认初始值 
 ③    L.length=0;     //顺序表初始长度为0
 }

1. 在内存中分配存储顺序表 L 的空间。包括存储各个数据元素连续的存储空间MaxSize*sizeof(ElemType)和 存储 length 的空间

2. 把各个数据元素的值设为默认值 （可省略）

3. 将 Length 的值设为0（不可省略，因为内存中可能有脏数据）

注：顺序表的表长刚开始确定后就无法更改，同时如果刚开始就申请一片很大的空间而不用，又会造成资源的浪费

顺序表的实现-动态分配：存储空间是动态的

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

C：malloc、free函数

L.data = (ElemType *) malloc (sizeof(ElemType) * InitSize);

malloc函数返回一个指针， 需要强制转型为你定义的数据元素类型指针

malloc函数的参数，指明要分配多大的连续内存空间

C++： new、delete关键字 L.data=new ElemType[InitSize]

 #include <stdlib.h> //使用malloc、free函数需要的头文件
 //定义一个顺序表
 #define InitSize 10 //顺序表的初始长度
 typedef struct{
 ElemType *data; //指示动态分配数组的指针，指向表中第一个元素
 int MaxSize; //顺序表的最大容量
 int length; //顺序表的当前长度
 } SeqList; //顺序表的类型定义（动态分配方式）
 ​
 //初始化顺序表
 void InitList(SeqList &L){
     //用 malloc 函数申请一片连续的存储空间
     L.data=(ElemType *)malloc(InitSize*sizeof(ElemType));
     L.length=0;
     L.MaxSize=InitSize;
 }
 ​
 //增加动态数组的长度
 void IncreaseSize(SeqList &L, int len){
     int *p=L.data;
     L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));
     for(int i=0; i<L.length; i++){
         L.data[i]=p[i];}        //将数据复制到新区域
     L.MaxSize=L.MaxSize+len;    //顺序表最大长度增加len
     free(p);                    //释放原来的内存空间
 }          //拓展空间的时间开销大

顺序表的优缺点：

1. 随机访问，即可以在O(1)时间内找到第i个元素。

2. 存储密度高，每个结点只存储数据元素

3. 拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）

4. 插入、删除操作不方便，需要移动大量元素

2.2.2顺序表的基本操作

插入：ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。

代码实现：静态分配 元素要后移

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

时间复杂度分析： 问题规模 n = L.length （表长）

删除：ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

代码实现：静态分配 元素要前移

 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--;                 //线性表长度减1
     return true;
 }

时间复杂度分析： 问题规模 n = L.length （表长）

<img src="C:\Users\hanyu\AppData\Roaming\Typora\typora-user-images\image-20260124175319675.png" alt="image-20260124175319675" style="zoom: 80%;" />

查找：

按位查找:GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。

代码实现：静/动态分配

 ElemType GetElem(SeqList L, int i){
     return L.data[i-1];
 } 

采用动态分配时，ElemType *data 如果一个 ElemType 占 6B，即 sizeof(ElemType)==6，

那么data[0]（从2000开始的6B）—data[1]（从2006开始的6B）—data[2]（从2012开始的6B) …

时间复杂度分析：

时间复杂度是O(1) —— “随机存取”特性

随机存取：由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素，

按值查找：LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。

代码实现：

 //在顺序表L中查找第一个元素值等于e的元素，并返回其位序
 int LocateElem(SeqList L,ElemType e){
     for(int i=0;i<L.length;i++)
         if(L.data[i]==e)
            return i+1; //数组下标为i的元素值等于e，返回其位序i+1
      return 0;         //退出循环，说明查找失败
 }

基本数据类型：int、char、double、float 等基本数据类型 可以直接用运算符“==”比较，结构类型不可以（初试不算错,机试不可以）

时间复杂度分析： 问题规模 n = L.length （表长）

2.3.1单链表的定义

定义：对比理解

顺序表：

每个结点中只存放数据元素

优点：可随机存取，存储密度高

缺点：要求大片连续空间，改变容量不方便

单链表：

每个结点除了存放数据元素外，还要存储指向下一个结点的指针

优点：不要求大片连续空间，改变容量方便

缺点：不可随机存取，要耗费一定空间存放指针

代码定义单链表：

增加一个新的结点：在内存中申请一个结点所需空间，并用指针 p 指向这个结点

struct LNode * p = (struct LNode *) malloc(sizeof(struct LNode));

typedef关键字：数据类型重命名 typedef <数据类型> <别名>

typedef关键字举例：

• typedef int zs; int x=1; 等价于 zs x=1;

• typedef int* zs; int* p; 等价于 zs p; //int* p、int *p、int * p都是一样

typedef struct LNode LNode;

之后可以用LNode代替struct LNode

 struct LNode{             //定义单链表结点类型
     ElemType data;        //每个节点存放一个数据元素
     struct LNode *next;   //指针指向下一个节点
 };
 ​
 typedef struct LNode LNode;
 typedef struct LNode *LinkList;
 等价于
 typedef struct LNode{             //定义单链表结点类型
     ElemType data;               //每个节点存放一个数据元素
     struct LNode *next;          //指针指向下一个节点
 }LNode, *LinkList;

要表示一个单链表时，只需声明一个头指针 L，指向单链表的第一个结点。

即LNode * L; 或LinkList L;

两行代码等价，Lnode * 强调返回的是一个结点，LinkList强调的是一个单链表，代码可读性更强

不带头结点的单链表：

 //初始化不带头结点的单链表
 bool InitList(LinkList &L) {
     L = NULL;  //空表，暂时还没有任何结点
     return true;
 }
 ​
 //判断单链表是否为空
 bool Empty(LinkList L) {
     if (L == NULL)
         return true;
     else
         return false;
 }
 或:
 bool Empty(LinkList L) {
     return (L==NULL);
 }

带头结点的单链表：头结点不储存数据

 //初始化一个带头结点的单链表
 bool InitList(LinkList &L) {
     L = (LNode *) malloc(sizeof(LNode));  //分配一个头结点
     if (L==NULL)  //内存不足，分配失败
         return false;
     L->next = NULL;  //头结点之后暂时还没有节点
     return true;
 }
 ​
 //判断单链表是否为空（带头结点）
 bool Empty(LinkList L) {
     if (L->next == NULL)
         return true;
     else
         return false;
 }

不带头结点和带头结点的区别：

不带头结点，写代码更麻烦

对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑

对空表和非空表的处理需要用不同的代码逻辑

我们一般使用的都是带头结点的单链表，头结点不储存数据

2.3.2单链表的基本操作

单链表的插入

按位序插入（带头结点）：

ListInsert(&L,i,e)：插入操作，在表L中的第i个位置上插入指定元素e（即找到第i-1个结点，将新结点插入其后）

若带有头结点，头结点可以看作“第0个”结点

//在第 i 个位置插入元素 e (带头结点)
bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1)
        return false;
    LNode *p;    //指针p指向当前扫描到的结点
    int j=0;     //当前p指向的是第几个结点
    p = L;       //L指向头结点，头结点是第0个结点（不存数据）
    while (p!=NULL && j<i-1) {  //循环找到第 i-1 个结点
        p=p->next;
        j++;
    }
    if(p==NULL)   //i值不合法
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next=p->next;
    p->next=s;   //将结点s连到p之后
    //注意这4行代码顺序颠倒链子不能断喵~
    return true;  //插入成功
}

最好时间复杂度：插在表头，O(1)

最坏时间复杂度：插在表尾，O(n)

平均时间复杂度：插在表中，O(n)

按位序插入（不带头结点）：

ListInsert(&L,i,e)：插入操作，在表L中的第i个位置上插入指定元素e（即找到第i-1个结点，将新结点插入其后）

不带头结点，即不存在“第0个”结点，因此i=1时需要特殊处理，插入、删除第1个元素时，需要更改头指针L

若i!=1则处理方法和带头结点一模一样，注意int j =1而非带头结点的0（带头结点的头结点为第0个结点）

bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1)
        return false;
    if(i==1){  //插入第1个结点的操作与其他结点操作不同
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = e;
        s->next=L;
        L=s;      //头指针指向新结点
        return true;
    }
    LNode *p;    //指针p指向当前扫描到的结点
    int j=1;     //当前p指向的是第几个结点
    p = L;       //p指向第1个结点（注意：不是头结点）
    while (p!=NULL && j<i-1) {  //循环找到第 i-1 个结点
        p=p->next;
        j++;
    }
    if(p==NULL)   //i值不合法
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next=p->next;
    p->next=s;
    return true;  //插入成功
}

结论：不带头结点写代码更不方便，推荐用带头结点

指定结点的后插操作：其实就是前面代码的后插部分

//后插操作：在p结点之后插入元素 e
bool InsertNextNode (LNode *p, ElemType e){
    if (p==NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s==NULL)    //内存分配失败，某些情况下有可能分配失败（如内存不足）
        return false;
    s->data = e;    //用结点s保存数据元素e
    s->next=p->next;
    p->next=s;      //将结点s连到p之后
    return true;
}

时间复杂度：O(1）

指定结点的前插操作：

因为仅知道指定结点的信息和后继结点的指向，因此无法直接获取到前驱结点

方法1：传入头指针，循环查找p的前驱q，再对q后插

时间复杂度：O(n)

方法2：将新结点s先连到指定结点p的后继，将p中元素复制到s中，将p中元素覆盖为要插入的元素e

//前插操作：在p结点之前插入元素 e
bool InsertPriorNode (LNode *p, ElemType e){
    if (p==NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s==NULL)    //内存分配失败
        return false;
    s->next=p->next;
    p->next=s;      //新结点 s 连到 p 之后
    s->data=p->data; //将p中元素复制到s中 
    p->data=e;      //p 中元素覆盖为 e
    return true;
}

时间复杂度：O(1)

补充：王道书版本代码

//前插操作：在p结点之前插入结点 s
bool InsertPriorNode (LNode *p, LNode *s){
    if (p==NULL || s==NULL)
        return false;
    s->next=p->next;
    p->next=s;      //s连到p之后
    ElemType temp=p->data;  //声明一个temp变量，保存p结点内容
    p->data=s->data;
    s->data=temp;
    return true;
}

单链表的删除

按位序删除（带头结点）：

ListDelete(&L,i,&e)：删除操作，删除表L中第i个位置的元素，并用e返回删除元素的值。

(即找到第i-1个结点，将其指针指向第i+1个结点，并释放第i个结点)

头结点可以看作“第0个”结点

bool ListDelete(LinkList &L, int i, ElemType &e){
    if(i<1)
        return false;
    LNode *p;    //指针p指向当前扫描到的结点
    int j=0;     //当前p指向的是第几个结点
    p = L;       //L指向头结点，头结点是第0个结点（不存数据）
    while (p!=NULL && j<i-1) {  //循环找到第 i-1 个结点
        p=p->next;
        j++;
    }
    if(p==NULL)   //i值不合法
        return false;
    if(p->next == NULL)  //第i-1个结点之后已无其他结点
        return false;
    LNode *q=p->next;    //令q指向被删除结点
    e = q->data;         //用e返回元素的值
    p->next=q->next;     //将*q结点从链中“断开”
    free(q);             //释放结点的存储空间
    return true;         //删除成功
}

最好时间复杂度：删除表头元素，O(1)

最坏时间复杂度：删除表尾元素，O(n)

平均时间复杂度：删除表中元素，O(n)

指定结点的删除：

删除结点p，需要修改其前驱结点的next指针，和指定结点的前插操作一样

方法1：传入头指针，循环寻找p的前驱结点

• 只能从表头开始依次寻找p的前驱，时间复杂度O(n)

• 这就体现了单链表的局限性：无法逆向检索，有时候不太方便

方法2：偷天换日（类似于结点前插的实现）

//删除指定结点 p
bool DeleteNode (LNode *p){
    if (p==NULL)
        return false;
    LNode *q=p->next;    //令q指向*p的后继结点
    p->data=p->next->data; //和后继结点交换数据域
    p->next=q->next;     //将*q结点从链中“断开”
    free(q);             //释放后继结点的存储空间
    return true;         //后续区域可能是指向一个结点，也可能是指向NULL，都无所谓
}

时间复杂度：O(1)

拓展：

封装：小功能模块化，代码逻辑清晰

单链表的查找

按位查找：

GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。

//按位查找，返回第 i 个元素（带头结点）
LNode * GetElem(LinkList L, int i){
    if(i<0)
        return NULL;
    LNode *p;    //指针p指向当前扫描到的结点
    int j=0;     //当前p指向的是第几个结点
    p = L;       //L指向头结点，头结点是第0个结点（不存数据）
    while (p!=NULL && j<i) {  //循环找到第 i 个结点
        p=p->next;
        j++;
    }
    return p;
}

最好时间复杂度：查找表头元素，O(1)

最坏时间复杂度：查找表尾元素，O(n)

平均时间复杂度：查找表中元素，O(n)

补充：王道书代码

LNode * GetElem(LinkList L, int i) {
    int j=1;
    LNode *p = L->next;
    if(i==0)
        return L;
    if(i<1)
        return NULL;
    while(p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

按值查找：

LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。

//按值查找，找到数据域为e 的结点
LNode * LocateElem(LinkList L,ElemType e) {
    LNode *p = L->next;
    //从第1个结点开始查找数据域为e的结点
    while (p != NULL && p->data != e)
        p = p->next;
    return p;   //找到后返回该结点指针，否则返回NULL
}

最好时间复杂度：查找表头元素，O (1)

最坏时间复杂度：查找表尾元素，O (n)

平均时间复杂度：查找表中元素，O (n)

求表的长度：

//求表的长度
int Length(LinkList L){
    int len = 0;    //统计表长
    LNode *p = L;
    while (p->next != NULL){
        p = p->next;
        len++;
    }
    return len;
}

时间复杂度：O(n)

单链表的建立

头插法、尾插法的核心就是初始化操作、指定结点的后插操作

尾插法：每次插入元素都插入到单链表的表尾

方法1：套用之前学过的位序插入，每次都要从头开始往后面遍历

//在第i个位置插插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1)
        return false;
    LNode *p;   //指针p指向当前扫描到的结点
    int j=0;    //当前p指向的是第几个结点
    p = L;      //L指向头结点，头结点是第0个结点（不存数据）
    while (p!=NULL && j<i-1) {  //循环找到第i-1个结点
        p=p->next;
        j++;
    }
    if(p==NULL)  //i值不合法
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next=p->next;
    p->next=s;   //将结点s连到p之后
    return true; //插入成功
}

时间复杂度为O(n²)

方法2：注意设置一个指向表尾结点的指针r，每次插入都让r指向新的表尾结点

LinkList List_TailInsert(LinkList &L){  //正向建立单链表
    int x;                              //设局部变量ElemType为整型
    L=(LinkList)malloc(sizeof(LNode));  //建立头结点，初始化空表
    LNode *s,*r=L;                      //r为表尾指针
    scanf("%d",&x);                     //输入结点的值
    while(x!=9999){                     //输入9999表示结束
        s=(LNode *)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;                      //在r结点之后插入元素x
        r=s;                            //r指向新的表尾结点，永远保持 r 指向最后一个结点
        scanf("%d",&x);
    }
    r->next=NULL;                       //尾结点指针置空
    return L;
}

时间复杂度为O(n)

头插法：每次插入元素都插入到单链表的表头位置

头插法和之前学过的单链表后插操作本质是一样的

头插法的重要应用：链表的逆置

LinkList List_HeadInsert(LinkList &L){  //逆向建立单链表
    LNode *s;
    int x;
    L=(LinkList)malloc(sizeof(LNode));  //创建头结点
    L->next=NULL;                       //初始为空链表，可以防止野指针指向脏数据
    scanf("%d",&x);                     //输入结点的值
    while(x!=9999){                     //输入9999表示结束
        s=(LNode*)malloc(sizeof(LNode)); //创建新结点
        s->data=x;
        s->next=L->next;
        L->next=s;                      //将新结点插入表中，L为头指针
        scanf("%d",&x);
    }
    return L;
}

2.3.3双链表

为什么要要使用双链表：

单链表：无法逆向检索，有时候不太方便

双链表：可进可退，但是存储密度更低一丢丢

双链表的代码定义：

typedef struct DNode{                 //定义双链表结点类型
    ElemType data;                   //数据域
    struct DNode *prior,*next;       //前驱和后继指针
}DNode, *DLinklist;

双链表的初始化（带头结点）：

//初始化双链表
bool InitDLinkList(DLinklist &L){
    L = (DNode *) malloc(sizeof(DNode));   //分配一个头结点
    if (L==NULL)                           //内存不足，分配失败
        return false;
    L->prior = NULL;                       //头结点的 prior 永远指向 NULL
    L->next = NULL;                        //头结点之后暂时还没有节点
    return true;
}

双链表的判空（带头结点）：

//判断双链表是否为空（带头结点）
bool Empty(DLinklist L) {
    if (L->next == NULL)
        return true;
    else
        return false;
}

双链表的插入（后插）：

注意新插入结点、前驱结点、后继结点的指针修改

边界情况：新插入结点在最后一个位置，需特殊处理

//在p结点之后插入s结点
bool InsertNextDNode(DNode *p, DNode *s){
    if (p==NULL || s==NULL)    //非法参数
        return false;
    s->next=p->next;
    if (p->next != NULL)    //如果p结点有后继结点
    p->next->prior=s;
    s->prior=p;
    p->next=s;
    return true;
}

双链表的删除（后插）：

注意删除结点的前驱结点、后继结点的指针修改

边界情况：如果被删除结点是最后一个数据结点，需特殊处理

bool DeleteNextDNode(DNode *p){
    if (p==NULL)  return false;
    DNode *q = p->next;      //找到p的后继结点q
    if (q==NULL)  return false;  //p没有后继
    p->next=q->next;
    if (q->next!=NULL)      //q结点不是最后一个结点
    q->next->prior=p;
    free(q);                //释放结点空间
    return true;
}

双链表的销毁：

销毁表时，释放所有数据结点，才能删除头结点

void DestoryList(DLinklist &L){
    //循环释放各个数据结点
    while (L->next != NULL)
        DeleteNextDNode(L);
    free(L);       //释放头结点
    L=NULL;        //头指针指向NULL
}

双链表的遍历：

后向遍历

while (p!=NULL){
    //对结点p做相应处理，如打印
    p = p->next;
}

前向遍历

while (p!=NULL){
    //对结点p做相应处理
    p = p->prior;
}

前向遍历（跳过头节点）

while (p->prior != NULL){
    //对结点p做相应处理
    p = p->prior;
}

双链表不可随机存取，按位查找、按值查找操作都只能用遍历的方式实现。时间复杂度 O(n)

2.3.4循环链表

循环单链表

循环单链表与单链表的对比：

单链表：表尾结点的next指针指向 NULL，从一个结点出发只能找到后续的各个结点

循环单链表：表尾结点的next指针指向头结点，从一个结点出发可以找到其他任何一个结点

循环单链表的操作：

定义

typedef struct LNode{
    ElemType data;          //每个节点存放一个数据元素
    struct LNode *next;     //指针指向下一个节点
}LNode, *LinkList;

初始化

bool InitList(LinkList &L) {
    L = (LNode *) malloc(sizeof(LNode));  //分配一个头结点
    if (L==NULL)                //内存不足，分配失败
        return false;
    L->next = L;                //头结点next指向头结点
    return true;
}

判空

bool Empty(LinkList L) {
    if (L->next == L)
        return true;
    else
        return false;
}

判断结点 p 是否为循环单链表的表尾结点

bool isTail(LinkList L, LNode *p){
    if (p->next==L)
        return true;
    else
        return false;
}

从头结点找到尾部，时间复杂度为O(n)

从尾部找到头部，时间复杂度为O(1)

很多时候对链表的操作都是在头部或尾部，但是如果需要频繁的访问表头、表尾，可以让L指向表尾元素（插入、删除时可能需要修改L）

循环双链表

循环双链表与双链表的对比：

双链表：表头结点的 prior 指向 NULL；表尾结点的 next 指向 NULL

循环双链表：表头结点的 prior 指向表尾结点；表尾结点的 next 指向头结点

循环双链表的操作：

循环双链表的定义

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

循环双链表的初始化

//初始化空的循环双链表
bool InitDLinkList(DLinklist &L){
    L = (DNode *) malloc(sizeof(DNode));  //分配一个头结点
    if (L==NULL)                //内存不足，分配失败
        return false;
    L->prior = L;              //头结点的 prior 指向头结点
    L->next = L;               //头结点的 next 指向头结点
    return true;
}

循环双链表的判空

//判断循环双链表是否为空
bool Empty(DLinklist L) {
    if (L->next == L)
        return true;
    else
        return false;
}

判断结点p是否为循环双链表的表尾结点

//判断结点p是否为循环双链表的表尾结点
bool isTail(DLinklist L, DNode *p){
    if (p->next==L)
        return true;
    else
        return false;
}

循环双链表的插入

对于双链表来说如果p结点为最后一个结点，因为next结点为null，p->next->prior=s会产生的空指针问题

对于循环双链表来说因为最后结点的next结点为头结点因此不会发生问题

//在p结点之后插入s结点
bool InsertNextDNode(DNode *p, DNode *s){
    s->next=p->next;    //将结点*s插入到结点*p之后
    p->next->prior=s;
    s->prior=p;
    p->next=s;
}

循环双链表的删除

对于双链表来说如果被删除结点是最后一个数据结点，需特殊处理

对于循环双链表来说没有这样的问题

//删除p的后继结点q
p->next=q->next;
q->next->prior=p; 
free(q);

注意：写代码时候注意以下几点，以此规避错误：

• 如何判空

• 如何判断结点p是否是表尾/表头元素（后向/前向遍历的实现核心）

• 如何在表头、表中、表尾插入/删除一个结点

2.3.5静态链表

静态链表的定义：

单链表：各个结点在内存中散落分布。

静态链表：分配一整片连续的内存空间，各个结点集中安置。

每个结点由两部分组成：data（数据元素）和next（游标）

0号结点充当“头结点”，不具体存放数据

游标为-1表示已经到达表尾

游标充当“指针”，表示下个结点的存放位置，如下举例：

每个数据元素4B，每个游标4B（每个结点共8B），设起始地址为addr，e1的存放地址为addr + 8*2（游标值）

静态链表的代码定义：

#define MaxSize 10    //静态链表的最大长度
typedef struct {       //静态链表结构类型的定义
    ElemType data;     //存储数据元素
    int next;          //下一个元素的数组下标
} SLinkList[MaxSize];
等价于
#define MaxSize 10    //静态链表的最大长度
struct Node{           //静态链表结构类型的定义
    ElemType data;     //存储数据元素
    int next;          //下一个元素的数组下标
};
typedef struct Node SLinkList[MaxSize];
//用SLinkList定义了一个长度为 MaxSize 的Node 型数组

静态链表的基本操作：

初始化：

• 把a[0]的next设为-1

• 把其他结点的next设为一个特殊值用来表示结点空闲，如-2

判空：

让next为某特殊值，如-2

查找：

• 从头结点出发挨个往后遍历结点,时间复杂度O(n)

插入位序为i的结点：

• 找到一个空的结点，存入数据元素（设为一个特殊值用来表示结点空闲，如-2）

• 从头结点出发找到位序为i-1的结点

• 修改新结点的next

• 修改i-1号结点的next

删除位序为i结点：

• 从头结点出发找到前驱结点，即找到位序为 i-1 的结点

• 修改前驱结点的游标

• 被删除结点next设为-2

总结：

• 静态链表：用数组的方式实现的链表

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

• 缺点：不能随机存取，只能从头结点开始依次往后查找；容量固定不可变

• 适用场景：①不支持指针的低级语言；②数据元素数量固定不变的场景（如操作系统的文件分配表FAT）

2.3.6顺序表和链表的比较

逻辑结构：

都属于线性表，都是线性结构

存储结构：

顺序表：

• 顺序存储

• 优点：支持随机存取、存储密度高

• 缺点：大片连续空间分配不方便，改变容量不方便

链表：

• 链式存储

• 优点：离散的小空间分配方便，改变容量方便

• 缺点：不可随机存取，存储密度低

基本操作：

顺序表：

创建

• 需要预分配大片连续空间。

• 若分配空间过小，则之后不方便拓展容量；

• 若分配空间过大，则浪费内存资源

• 静态分配：静态数组实现，容量不可改变

• 动态分配：动态数组（malloc、free）实现，容量可改变，但需要移动大量元素，时间代价高

销毁

• 修改Length = 0

• 静态分配：静态数组，系统自动回收空间

• 动态分配：动态数组（malloc、free），需要手动free

插入/删除

• 插入/删除元素要将后续元素都后移/前移

• 时间复杂度O(n)，时间开销主要来自移动元素

• 若数据元素很大，则移动的时间代价很高

查找

• 按位查找：O(1)

• 按值查找：O(n)若表内元素有序，可在O(log2n)时间内找到

链表：

创建

• 只需分配一个头结点（也可以不要头结点，只声明一个头指针），之后方便拓展

销毁

• 依次删除各个结点（free）

插入/删除

• 插入/删除元素只需修改指针即可

• 时间复杂度O(n)，时间开销主要来自查找目标元素

• 查找元素的时间代价更低

查找

• 按位查找：O(n)

• 按值查找：O(n)

用顺序表 or 链表？：

	顺序表	链表
容量（弹性）	×	√
插入/删除	×	√
查找	√	×

• 表长难以预估、经常要增加/删除元素——链表

• 表长可预估、查询（搜索）操作较多——顺序表

开放式问题的解题思路：

问： 请描述顺序表和链表的bla bla bla…实现线性表时，用顺序表还是链表好？

答：

• 顺序表和链表的逻辑结构都是线性结构，都属于线性表。

• 但是二者的存储结构不同，顺序表采用顺序存储…(特点，带来的优点缺点)；链表采用链式存储…（特点、导致的优缺点）。

• 由于采用不同的存储方式实现，因此基本操作的实现效率也不同。

• 当初始化时…；当插入一个数据元素时…；当删除一个数据元素时…；当查找一个数据元素时…