线性表

HuPei2025/9/4大约 31 分钟

线性表

2.1 线性表的定义和基本操作

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

2.2 线性表的顺序表示

2.2.1 顺序表的实现

线性表的顺序存储称为顺序表。特点是表中元素的逻辑顺序与其物理顺序相同，是一种随机存取的数据结构，通常用高级程序设计语言中的数组来描述线性表的顺序存储结构。

注意：线性表中元素的位序从1开始，而数组元素下标从0开始。

顺序表的实现——静态分配

#include <stdio.h>
#define MaxSize 10      //定义最大长度 
typedef struct{
    int data[MaxSize];  //用静态的“数组”存放数据元素 ElemType:int
    int Length;         //顺序表的当前长度
}SqList;                //顺序表的类型定义

//基本操作——初始化一个顺序表
void InitList(SqList &L){
    for(int j=0; j<MaxSize; j++){
        L.data[j]=0;  //将数据元素设置为默认初始值0,内存中可能有遗留的“脏数据”
    }
    L.Length=0;        //顺序表初始长度为0
}

//主函数
int main(){            
    SqList L;          //声明一个顺序表  在内存里分配存储顺序表L的空间
                       //包括MaxSize*sizeof(ElemType)和存储length的空间
    InitList(L);       //初始化这个顺序表
    //...
    return 0;
}

顺序表的实现——动态分配

malloc函数:

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

其中(ElemType*)可强制转换数据类型

#include <stdlib.h>       //malloc,free函数的头文件
#define InitSize 10       //默认的最大初始长度

typedef struct{
    int *data;            //指示动态分配数组的指针
    int MaxSize;         //顺序表的最大容量
    int length;          //顺序表的当前长度
}SeqList;

int main(){
    SeqList L;
    InitList(L);
    //...其余操作
    IncreaseSize(L,5);
    return 0;
}
void InitList(SeqList &L){
    L.data = (int*)malloc(InitSize*sizeof(int));  //用malloc函数申请一片连续的存储空间
    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);                 //释放原来的内存空间
}

2.2.2 顺序表上基本操作的实现 (插入和删除)

顺序表基本操作——插入

基于静态分配的代码实现

#define MaxSize 10      //定义最大长度 
typedef struct{
    int data[MaxSize];  //用静态的“数组”存放数据元素
    int Length;         //顺序表的当前长度
}SqList;                //顺序表的类型定义

//基本操作——在L的位序i处插入元素e
bool ListInsert(SqList &L, int i, int e){ 
    //判断i的范围是否有效
    if(i<1||i>L.length+1) 
        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;
}

int main(){
    SqList L;          //声明一个顺序表
    InitList(L);       //初始化这个顺序表
    //...插入几个元素
    ListInsert(L,3,3);
    return 0;
}

时间复杂度分析

关注最深层循环语句——L.data[j]=L.data[j-1]的执行次数与问题规模n——L.length的关系;
最好情况：插入表尾，不需要移动元素，i=n+1，循环0次；最好时间复杂度 = O(1)
最坏情况：插入表头，需要将原有的n个元素全都向后移动，i=1，循环n次；最坏时间复杂度 = O(n)

平均情况：假设新元素插入到任何一个位置的概率p(=1/n+1)相同

插入到第i个位置	循环次数
1	n
2	n-1
3	n-2
…	…
n+1	0

平均循环次数 = np + (n-1)p + (n-2)p + … + 1×p = [ n(n+1)/2 ]×[ 1/(n+1) ] = n/2

平均时间复杂度 = O(n)

顺序表基本操作——删除

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

基于静态分配的代码实现

#define MaxSize 10      //定义最大长度 
typedef struct{
    int data[MaxSize];       //用静态的“数组”存放数据元素 
    int Length;             //顺序表的当前长度
}SqList;                   //顺序表的类型定义

bool ListDelete(SqList &L, int i, int &e){       // 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;
}

int main(){
    SqList L;            //声明一个顺序表
    InitList(L);         //初始化这个顺序表
    //省略代码...插入几个元素
    int e = -1;          //用变量e把删除的元素“带回来”
    if(ListDelete(L,3,e))
        printf("已删除第三个元素，删除元素值=%d\n",e);
    else
        printf("位序i不合法，删除失败\n");
    return 0;
}

时间复杂度分析

关注最深层循环语句——L.data[j-1]=L.data[j]的执行次数与问题规模n——L.length的关系;
最好情况：删除表尾元素，不需要移动元素，i=n，循环0次；最好时间复杂度 = O(1);
最坏情况：删除表头元素，需要将后续的n-1个元素全都向前移动，i=1，循环n-1次；最坏时间复杂度 = O(n);

平均情况：假设删除任何一个元素(1,2,3,…,length)的概率相同 p=1/n

删除第i个元素	循环次数
1	n-1
2	n-2
3	n-3
…	…
n	0

平均循环次数 = (n-1)p + (n-2)p + … + 1×p = [ n(n-1)/2 ]×[ 1/(n) ] = n-1/2

平均时间复杂度 = O(n)

顺序表基本操作——按位查找(顺序表)

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

基于静态分配的代码实现

#define MaxSize 10            //定义最大长度 
typedef struct{
    ElemType data[MaxSize];  //用静态的“数组”存放数据元素 
    int Length;              //顺序表的当前长度
}SqList;                     //顺序表的类型定义

ElemType GetElem(SqList L, int i){
    // ...判断i的值是否合法
    return L.data[i-1];      //注意是i-1
}

基于动态分配的代码实现

#define InitSize 10  //顺序表的初始长度

typedef struct{
    ElemType *data;  //指示动态分配数组的指针
    int MaxSize;     //顺序表的最大容量
    int length;      //顺序表的当前长度
}SeqList;

ElemType GetElem(SqList L, int i){
    // ...判断i的值是否合法
    return L.data[i-1];       //就算是指针也能用数组下标哦!
}

时间复杂度分析
O(1)

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

顺序表基本操作——按值查找

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

基于动态分配的代码实现

#define InitSize 10            //定义最大长度 
typedef struct{
    ElemTyp *data;            //用静态的“数组”存放数据元素
    int MaxSize;             //顺序表的最大容量
    int Length;              //顺序表的当前长度
}SqList;                     //顺序表的类型定义（动态分配方式）

//在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SqList 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;                 //退出循环，说明查找失败
}

Q: 如果顺序表里存放的是结构类型的数据元素，可不可以用 == 进行比较？
A: 不能！结构类型的比较，需要依次对比各个分量来判断两个结构体是否相等；

例： hedui

typedef struct{
    int num;
    int people;
}Customer;

void test(){
    Customer a;
    a.num = 1; a.people = 1;
    Customer b;
    b.num = 1; b.people = 1;
    //...
    if (a.num == b.num && a.people == b.people){
        printf("相等");
    }else{
        printf("不相等");
    }
}

bool isCustomerEqual(Customer a,Customer b){
      if(a.num == b.num && a.people == b.people)
      return true;
      else
      return false;
}

时间复杂度分析

最深处循环语句: if(L.data[i] == e) 与问题规模n=L.length(表长)的关系；
最好情况：查找目标元素在表头，循环1次，最好时间复杂度=O(1)
最坏情况：查找目标元素在表尾，循环n次，最好时间复杂度=O(n)
平均情况：假设目标元素出现在任何一个位置的概率相同，p=1/n

目标元素所在位置i	循环次数
1	1
2	2
3	3
…	…
n	n

平均循环次数 = 1×1/n + 2×1/n +…+ n×1/n = [ n(n+1)/2 ] × 1/n = (n+1)/2

平均时间复杂度 = O(n)

2.3 线性表的链式表示

2.3.1 单链表的定义

何为单链表？

链式存储
每个结点存储：数据元素自身信息 & 指向下一个结点(后继)的指针
优点：不要求大片连续空间，改变容量方便
缺点：不可随机存取，要耗费一定空间存放指针

代码定义单链表

struct LNode{            //定义单链表节点类型  LNode:结点
    ElemType data;       //每个结点存放一个数据元素 data:数据域
    struct LNode *next;  //指针指向下一个结点 next:指针域
};

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

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

如果每次都要写struct很麻烦，所以可以利用typedef关键字——数据类型重命名：type<数据类型><别名>
Eg:

typedef int zhengshu;
typedef int *zhengshuzhizhen;  //指向int型的指针

上面操作可以化简为:

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

最简洁代码实现:

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

以上代码等同于：

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

typedef struct LNode LNode; //重命名
typedef struct LNode *LinkList;

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

LNode *L;    // 声明一个指向单链表第一个结点的指针，强调这是结点
LinkList L;  // 声明一个指向单链表第一个结点的指针，强调这是链表

单链表两种实现方法

不带头结点的单链表

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

//初始化一个空的单链表
bool InitList(LinkList &L){      //注意用引用 &，要'带回来'
    L = NULL;                   //空表，暂时还没有任何结点
    return true;
}

void test(){
    LinkList L;            //声明一个指向单链表的指针: 头指针
    InitList(L);          //初始化一个空表
    //...后续代码...
}

//判断单链表是否为空
bool Empty(LinkList L){
    if (L == NULL)
        return true;
    else
        return false;
}
//或者：等价于判断单链表是否为空
bool Empty(LinkList L){
   return (L == NULL);
}

带头结点的单链表

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 = NULL;           //头结点之后暂时还没有结点
    return true;
}

void test(){
    LinkList L;            //声明一个指向单链表的指针: 头指针
    InitList(L);           //初始化一个空表
    //...后续代码
}

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

不带头结点 V.S. 带头结点

不带头结点：写代码麻烦！对第一个数据节点和后续数据节点的处理需要用不同的代码逻辑，对空表和非空表的处理也需要用不同的代码逻辑; 头指针指向的结点用于存放实际数据;
带头结点：头指针指向的头结点不存放实际数据,头结点指向的下一个结点才存放实际数据;
单链表设置头结点的目的是方便运算的实现。

2.3.2 单链表上基本操作的实现

1. 单链表的插入

按位序插入 (带头结点)

ListInsert(&L, i, e): 在表L中的第i个位置上插入指定元素e = 找到第i-1个结点(前驱结点)，将新结点插入其后；其中头结点可以看作第0个结点，故i=1时也适用。

代码实现 hedui

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

//在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, ElemType e){  
    //判断i的合法性, i是位序号(从1开始)
    if(i<1)
        return false; 
    LNode *p;           //指针p指向当前扫描到的结点 
    int j = 0;          //当前p指向的是第几个结点
    p = L;              //L指向头结点，头结点是第0个结点（不存数据）
    
    //循环找到第i-1个结点
    while(p!=NULL && j<i-1){     //如果i>lengh, p最后会等于NULL
        p = p->next;             //p指向下一个结点
        j++;
    }
    if (p==NULL)                 //i值不合法
        return false;    
    //在第i-1个结点后插入新结点
    LNode *s = (LNode *)malloc(sizeof(LNode)); //申请一个结点
    s->data = e;
    s->next = p->next;
    p->next = s;                 //将结点s连到p后,后两步千万不能颠倒qwq
    return true;
}

时间复杂度分析

最好情况：插入第1个位置 O(1)
最坏情况：插入表尾 O(n)
平均时间复杂度 = O(n)

按位序插入 (不带头结点)

ListInsert(&L, i, e): 在表L中的第i个位置上插入指定元素e = 找到第i-1个结点(前驱结点)，将新结点插入其后; 因为不带头结点，所以不存在“第0个”结点，因此！i=1 时，需要特殊处理——插入(删除)第1个元素时，需要更改头指针L;

代码实现 hedui

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

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

    //i>1的情况与带头结点一样！唯一区别是j的初始值为1
    LNode *p;       //指针p指向当前扫描到的结点 
    int j=1;        //当前p指向的是第几个结点
    p = L;          //L指向头结点，头结点是第0个结点（不存数据）
   
     //循环找到第i-1个结点
    while(p!=NULL && j<i-1){     //如果i>lengh, p最后会等于NULL
        p = p->next;             //p指向下一个结点
        j++;
    }
    if (p==NULL)                 //i值不合法
        return false;  
    //在第i-1个结点后插入新结点
    LNode *s = (LNode *)malloc(sizeof(LNode)); //申请一个结点
    s->data = e;
    s->next = p->next;
    p->next = s;          
    return true;
}

除非特别声明，否则之后的代码都默认为带头结点哦，做题注意审题

指定结点的后插操作

InsertNextNode(LNode *p, ElemType e): 给定一个结点p，在其之后插入元素e; 根据单链表的链接指针只能往后查找，故给定一个结点p，那么p之后的结点我们都可知，但是p结点之前的结点无法得知;

代码实现 hedui

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

//后插操作：在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)


//有了后插操作，那么在第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个结点（不存数据）

    //循环找到第i-1个结点
    while(p!=NULL && j<i-1){     //如果i>lengh, p最后会等于NULL
        p = p->next;             //p指向下一个结点
        j++;
    }

    return InsertNextNode(p, e)
}

指定结点的前插操作

Q: 如何找到p结点的前驱节点？

A: 传入头指针L！就可以知道整个链表的信息了！

InsertPriorNode(LinkList L, LNode *p, ElemType e)：循环查找p的前驱q，再对q进行后插操作，时间复杂度为O(n);

Q: 那如果不传入头指针L呢？

不传入头指针L的代码实现 hedui

//前插操作：在p结点之前插入元素e
bool InsertPriorNode(LNode *p, ElenType 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)

王道书版本代码 hedui

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;        //交换数据域部分
    p->data = s->data;
    s->data = temp;
    return true;
}

2. 单链表的删除

按位序删除(带头结点)

ListDelete(&L, i, &e): 删除操作，删除表L中第i个位置的元素，并用e返回删除元素的值;头结点视为“第0个”结点；

思路：找到第i-1个结点，将其指针指向第i+1个结点，并释放第i个结点；

代码实现 hedui

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

bool ListDelete(LinkList &L, int i, ElenType &e){
    if(i<1)
       return false;
    LNode *p;           //指针p指向当前扫描到的结点 
    int j=0;            //当前p指向的是第几个结点
    p = L;              //L指向头结点，头结点是第0个结点（不存数据）

    //循环找到第i-1个结点
    while(p!=NULL && j<i-1){     //如果i>lengh, p最后会等于NULL
        p = p->next;             //p指向下一个结点
        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(n)
最好时间复杂度：删除第一个结点 O(1)

指定结点的删除

删除结点p，需要修改其前驱结点的next指针(两个方法)；

"偷天换日"代码实现 hedui

bool DeleteNode(LNode *p){
    if(p==NULL)
        return false;
    LNode *q = p->next;            //令q指向*p的后继结点
    p->data = p->next->data;       //让p和后继结点交换数据域
    p->next = q->next;             //将*q结点从链中“断开”
    free(q);
    return true;
}                         //时间复杂度 = O(1)

但是如果p是最后一个结点，那么p->next = q->next and p->data = p->next->data 就会出错，只能从表头开始依次寻找o的前驱，时间复杂度为O(n); 这就是单链表的局限性——无法逆向检索。
3. 单链表的查找

探讨带头结点！

按位查找

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

代码实现 hedui

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;               //返回p指针指向的值
}

平均时间复杂度 = O(n)
王道书版本代码 hedui

LNode * GetElem(LinkList L, int i){
    int j=1;                      //从第一个结点开始
    LNode *p = L->next;           //p先指向第一个结点
    if(i==0)
         return L;
    if(i<1)  
         return NULL;
    while(p!=NULL && j<i){        //循环找到第i个结点
        p = p->next;
        j++;
    }
    return p;                 //返回p指针指向的值
}

那么上一节的按位插入和按位删除就可以封装了！

按值查找

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

代码实现 hedui

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

注意当ElemType是结构体时的操作
4. 求单链表的长度

Length(LinkList L)

代码实现 (带头结点)

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

平均时间复杂度= O(n)
5. 单链表的建立

思路： 初始化一个单链表 -> 每取一个数据元素，插入到表尾/表头

核心： 初始化操作 and 指定结点的后插操作

探讨带头结点！

尾插法建立单链表

解决方法：设置一个表尾指针r，对r这个结点进行后插操作InsertNextNode()

最终代码实现 hedui

LinkList List_TailInsert(LinkList &L){       //正向建立单链表
    int x;                                   //设ElemType为整型int
    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 = s;                             //r指针指向新的表尾结点
        scanf("%d", &x);   
    }
    r->next = NULL;                          //尾结点指针置空
    return L;
}

平均时间复杂度：O(n)

头插法建立单链表

对头结点进行后插操作InsertNextNode()

最终代码实现 hedui

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

PS: 只要是初始化单链表，都先将头指针指向NULL —L->next = NULL;

重要应用：链表的逆置

算法思想：逆置链表初始为空，原表中结点从原链表中依次“删除”，再逐个插入逆置链表的表头（即“头插”到逆置链表中），使它成为逆置链表的“新”的第一个结点，如此循环，直至原链表为空；

LNode *Inverse(LNode *L)
{
	LNode *p, *q;
	p = L->next;     //p指针指向第一个结点
	L->next = NULL;  //头结点指向NULL

	while (p != NULL){
		q = p;
		p = p->next;
		q->next = L->next;  
		L->next = q;
	}
	return L;

2.3.3 双链表

双链表的初始化 (带头结点) hedui

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

void testDLinkList(){     
    DLinklist L;         //初始化双链表，定义指向头结点的指针L
    InitDLinkList(L);    //申请一片空间用于存放头结点，指针L指向这个头结点
    //...后续代码
}

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

与单链表中一样，DLinklist 强调链表， DNode *强调结点，二者本质上等价;

双链表的插入操作

后插操作

InsertNextDNode(p, s): 在p结点后插入s结点

代码实现:

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

按位序插入操作

思路：从头结点开始，找到某个位序的前驱结点，对该前驱结点执行后插操作；

前插操作

思路：找到给定结点的前驱结点，再对该前驱结点执行后插操作；

双链表的删除操作

删除p的后继结点q

p->next = q->next;
q->next->prior = p;
free(q);

如果要删除的结点q是最后一个结点，会出现错误，故增加条件判断以提高代码健壮性
代码实现 hedui

//删除p结点的后继结点
bool DeletNextDNode(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)
        DeletNextDNode(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 循环链表

1. 循环单链表

最后一个结点的指针不是NULL,而是指向头结点hedui

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(n)的时间复杂度;
循环单链表：从一个结点出发，可以找到其他任何一个结点；设立尾指针，从尾部找到头部的时间复杂度为O(1)，即对表头和表尾进行操作都只需要O(1)的时间复杂度;

可以让L指向表尾元素(插入，删除时可能需要修改L)
2. 循环双链表

表头结点的prior指向表尾结点，表尾结点的next指向头结点

循环双链表的初始化 hedui

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指向头结点
}

void testDLinkList(){
    //初始化循环单链表
    DLinklist L;
    InitDLinkList(L);
    //...后续代码
}

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

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

双链表 & 循环双链表

插入操作

对于循环双链表，操作 p->next->prior = s 不会出问题辣！因为就算p是最后一个结点，也不会出现空指针现象了(这个问题在双链表里会出现！)

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

删除操作

和插入操作一样！q->next->prior 对于循环双链表不会出错了

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

2.3.5 静态链表

何为静态链表

单链表: 各个结点散落在内存中的各个角落，每个结点有指向下一个节点的指针(下一个结点在内存中的地址);
静态链表——用数组的方式实现的链表: 分配一整片连续的内存空间，各个结点集中安置，包括了——数据元素and下一个结点的数组下标(游标)
- 其中数组下标为0的结点充当"头结点"
- 游标为-1表示已经到达表尾
- 若每个数据元素为4B，每个游标为4B，则每个结点共8B；假设起始地址为addr，则数据下标为2的存放地址为：addr+8*2
- 注意：数组下标——物理顺序，位序——逻辑顺序；
- 优点：增、删操作不需要大量移动元素；
- 缺点：不能随机存取，只能从头结点开始依次往后查找，容量固定不变！

代码定义一个静态链表 hedui

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

//用数组定义多个连续存放的结点
void testSLinkList(){
    struct Node a[MaxSize];  //每一个数组元素的类型都是struct Node
    //...后续代码
}

也可以这样：

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

void testSLinkList(){
    SLinkList a;
}

上面这个代码等同于

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

//重命名struct Node，用SLinkList定义一个长度为MaxSize的Node型数组;
typedef struct Node SLinkList[MaxSize];

PS: SLinkList a 强调a是静态链表；struct Node a 强调a是一个Node型数组；

静态链表基本操作的实现

初始化静态链表：把a[0]的next设为-1
查找某个位序（不是数组下标，位序是各个结点在逻辑上的顺序）的结点：从头结点出发挨个往后遍历结点，时间复杂度O=(n)
在位序为i上插入结点：① 找到一个空的结点，存入数据元素；② 从头结点出发找到位序为i-1的结点；③修改新结点的next；④ 修改i-1号结点的next；

Q：如何判断结点为空？
A：在初始化时，将空闲结点的next设置为某个特殊值，eg：-2；

删除某个结点：① 从头结点出发找到前驱结点；② 修改前驱节点的游标；③ 被删除节点next设为-2；

2.3.6 顺序表和链表的比较

1. 逻辑结构

顺序表和链表都属于线性表，都是线性结构

2. 存储结构

顺序表：顺序存储
- 优点：支持随机存取，存储密度高
- 缺点：大片连续空间分配不方便，改变容量不方便
链表：链式存储
- 优点：离散的小空间分配方便，改变容量方便
- 缺点：不可随机存取，存储密度低

3. 基本操作 - 创

顺序表：需要预分配大片连续空间。若分配空间过小，则之后不方便拓展容量；若分配空间过大，则浪费内存资源；
- 静态分配：静态数组，容量不可改变
- 动态分配：动态数组，容量可以改变，但是需要移动大量元素，时间代价高（malloc(),free()）
链表：只需要分配一个头结点或者只声明一个头指针，之后方便拓展

4. 基本操作 - 销毁

顺序表：修改 Length = 0

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

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

动态分配：动态数组——需要手动free

//创
L.data = (ELemType *)malloc(sizeof(ElemType) *InitSize)
//销
free(L.data);

//！malloc() 和 free() 必须成对出现

链表：依次删除各个结点 free()

5. 基本操作 - 增/删

顺序表：插入/删除元素要将后续元素后移/前移；时间复杂度=O(n)，时间开销主要来自于移动元素；
链表：插入/删除元素只需要修改指针；时间复杂度=O(n)，时间开销主要来自查找目标元素

6. 基本操作 - 查

顺序表
- 按位查找：O(1)
- 按值查找：O(n)，若表内元素有序，可在O(log2n)时间内找到
链表：
- 按位查找：O(n)
- 按值查找：O(n)

7. 开放式问题答题思路

Q: 请描述顺序表和链表的balabalabala…实现线性表时，用顺序表还是链表好？

A: 顺序表和链表的存储结构都是线性结构，都属于线性表；但是二者的存储结构不同，顺序表采用顺序存储…(特点，优缺点)；链表采用链式存储…(特点，优缺点)；由于采用不同的存储方式实现，因此基本操作的实现效率也不同；当初始化时…；当插入一个数据元素时…；当删除一个数据元素时…；当查找一个数据元素时…；

贡献者

hupei