欢迎各位彦祖与热巴畅游本人专栏与博客

你的三连是我最大的动力

以下图片仅代表专栏特色 [点击箭头指向的专栏名即可闪现]

专栏跑道一

➡️网络空间安全——全栈前沿技术持续深入学习

专栏跑道二

➡️ 24 Network Security -LJS

专栏跑道三

➡️ MYSQL REDIS Advance operation

专栏跑道四

➡️HCIP；H3C-SE;CCIP——LJS[华为、华三、思科高级网络]

专栏跑道五

➡️RHCE-LJS[Linux高端骚操作实战篇]

专栏跑道六

➡️数据结构与算法[考研+实际工作应用+C程序设计]

专栏跑道七

➡️RHCSA-LJS[Linux初级及进阶骚技能]

上节回顾

1.单链表的定义

1.1顺序表：

每个结点中只存放数据元素
优点：可随机存取，存储密度高
缺点：要求大片连续空间，改变容量不方便
1
顺序表定义代码回忆

#define MaxSize 10      // 定义最大长度
typedef struct{
    ElemType data[MaxSize];     // 用静态的“数组”存放数据元素
    int length;     // 顺序表的当前长度
}SqList;
#include <stdio.h>
#define MaxSize 10
typedef struct{
    int data[MaxSize];
    int length;
}SqList;
void InitList(SqList &L)
{
    // 可以省略，但可能由于遍历时用到MaxSize有脏数据，要用length遍历
    for (int i = 0; i < MaxSize; i ++ )
        L.data[i] = 0;
    
    L.length = 0;       // 不可省略，顺序表初始长度为0
}
int main()
{
    SqList L;       // 声明一个顺序表
    InitList(L);        // 初始化顺序表
    
    return 0;
}

1.2单链表：

每个结点除了存放数据元素外，还要存储指向下一个结点的指针
优点：不要求大片连续空间，改变容量方便
缺点：不可随机存取，要耗费一定空间存放指针

2.定义一个单链表：

typedef关键字：数据类型重命名
typedef <数据类型> <别名>
typedef struct LNode LNode;
之后可以用LNode代替struct LNode
这样写每次都要有s t r u c t structstruct有些麻烦，所以教材中使用了t y p e d e f typedeftypedef关键字（C语言），可以把数据类型重命名
t y p e d e f < 数据类型 > < 别名 >

2.1 用代码定义一个单链表

struct LNode        // 定义单链表节点类型
{
    ElemType data;      // 每个节点存放一个数据元素
    struct LNode *next;     // 指针指向下一个节点
};
struct LNode *p = (struct LNode *)malloc(sizeof(struct LNode));      // 增加一个新的节点 ：在内存中申请一个节点需要的空间，并用指针p指向这个节点

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

教材中还有一种更简洁的方式

编辑

typedef struct LNode    // 定义单链表节点类型
{
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;
// LinkList - 单链表
// 上面这种写法等价于 :
struct LNode
{
    ElemType data;
    struct LNode *next;
}
typedef struct LNode LNode;
typedef struct LNode *LinkList;

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

// 声明一个指向单链表第一个结点的指针
LNode *L;
// 等价于
LinkList L;     // 代码可读性更强，详见下面例子中，
// GetElem函数的LNode *和LinkList虽然两者时等价的
//但在这个函数中它最终要返回的是第i个结点，所以把返回值的类型定义为LNode *，
// 其实它LNode *就是想强调返回的是一个结点，而LinkList想强调这是一个单链表

typedef struct LNode
{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;
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;
}

补充说明：

强调这是一个单链表 - 使用LinkList
强调这是一个结点 - 使用LNode *

3.不带头结点的单链表：

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);
}
/*如果不带头结点 ：
头指针所指向的下一个结点就是实际用于存放数据的结点；而如果带头结点的话 ：
头指针所指向的这个结点把它称为头结点，
这个头结点是不存放实际数据元素的，
只有这个头结点之后的下一个结点才用于存放数据*/

3.1带头结点的单链表：

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

编辑

3.2区别：

不带头结点，写代码更麻烦
对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑
对空表和非空表的处理需要用不同的代码逻辑
我们一般使用的都是带头结点的单链表

4.单链表的插入、删除

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

ListInsert(&L,i,e)：

插入操作，在表L中的第i个位置上插入指定元素e
找到第i-1个结点，将新结点插入其后
若带有头结点，插入更加方便，头结点可以看作“第0个”结点，直接做上面的操作即可

编辑

若i插在表中则与插在表头一样进行操作，可以插入成功
若i插在表尾则s->next为NULL（在表的定义时规定的），可以插入成功
若i插在表外（i>Lengh）则p指针指向NULL（While循环一直指向p->next），不能插入成功
最好时间复杂度= O(1)
最坏时间复杂度= O(n)
平均时间复杂度= O(n)

编辑按位序插入（带头结点）代码书写：

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

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

ListInsert(&L,i,e)：

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

编辑编辑

bool ListInsert(LinkList &L, int i, ElemType e)
{
    if (i < 1)
        return false;
    
    if (i == 1)
    {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s -> data = e;
        s -> next = L;
        L = s;
        
        return true;
    }
    
    LNode *p = L;
    int j = 1;      // 注意这里是1！！！不带头结点
    
    while (p != NULL && j < i - 1)
    {
        p = p -> next;
        j ++ ;
    }
    
    if (p == NULL)
        return false;
    
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s -> data = e;
    s -> next = p -> next;
    p -> next = s;
    
    return true;
}

若i!=1则处理方法和带头结点一模一样
值得注意的是int j =1而非带头结点的0（带头结点的头结点为第0个结点）
综上结论：不带头结点写代码更不方便，推荐用带头结点

指定结点的后插操作：

编辑

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 -> next = p -> next;
    p -> next = s;
    
    return true;
}

这一段代码是按位序插入中插入的那一部分代码
也可以直接调用InsertNextNode来执行
封装代码，以此提高代码复用性，让代码更容易维护

指定结点的前插操作：

编辑

因为仅知道指定结点的信息和后继结点的指向，因此无法直接获取到前驱结点
方法1：获取头结点然后再一步步找到指定结点的前驱
方法2：将新结点先连上指定结点p的后继，接着指定结点p连上新结点s，将p中元素复制到s中，将p中元素覆盖为要插入的元素e

方法1：前叉操作伪代码实现编辑

// 前插操作 ：在p结点之前插入元素e
// O(1)
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 -> data = p -> data;
    p -> data = e;
    
    return true;
}

// 王道书版本
bool InsertPriorNode(LNode *p, LNode *s)
{
    if (p == NULL || s == NULL)
        return false;
    
    s -> next = p -> next;
    p -> next = s;
    
    ElemType temp = p -> data;      // 交换数据域部分
    p -> data = s -> data;
    s -> data = temp;
    
    return true;
}

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

编辑

ListDelete(&L,i,&e)：

删除操作，删除表L中第i个位置的元素，并用e返回删除元素的值。
找到第i-1个结点，将其指针指向第i+1个结点，并释放第i个结点

bool ListDelete(LinkList &L, int i, ElemType &e)
{
    if (i < 1)
        return false;
    
    LNode *p = L;
    int j = 0;
    
    while (p != NULL && j < i - 1)
    {
        p = p -> next;
        j ++ ;
    }
    
    if (p == NULL)
        return false;
    if (p -> next == NULL)      // 第i-1个结点之后已无结点
        return false;
    
    LNode *q = p -> next;
    e = q -> data;
    p -> next = q -> next;
    free(q);
    
    return true;
}

指定结点的删除

编辑

删除结点p，需要修改其前趋结点的next指针
方法1 ：传入头指针，循环寻找p的前趋结点
方法2 ：偷天换日（类似于结点前插的实现）

指定结点的删除代码：

bool DeleteNode(LNode *p)
{
    if (p == NULL)
        return false;
    
    LNode *q = p -> next;
    p -> data = p -> next -> data;
    p -> next = q -> next;
    
    free(q);
    return true;
}

方法2注意！！！

如果要删除的结点p是最后一个结点：

只能从表头开始依次寻找p的前驱，时间复杂度O(n)
这就体现了单链表的局限性：无法逆向检索，有时候不太方便

5.单链表的查找【只探讨“带头结点”的情况】

按位查找：

GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。
实际上单链表的插入中找到i-1部分就是按位查找i-1个结点，如下图

因此查找第i个结点如下图

单链表的按位查找代码：

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

如果i=0则直接不满足j<i则指针p直接返回头结点L
如果i超界则当时p指向了NULL，指针p返回NULL
平均时间复杂度：O(n)

按值查找：

按值查找代码

LNode * LocateElem(LinkList L, ElemType e)
{
    LNode *p = L -> next;
    while (p != NULL && p -> data != e)
        p = p -> next;
    return p;
}

能找到的情况：p指向了e值对应的元素，返回该元素
不能找到的情况：p指向了NULL，指针p返回NULL
平均时间复杂度：O(n)

求表的长度

编辑

求表的长度代码：

int Length(LinkList L)
{
    LNode *p = L;
    int len = 0;
    while (p != NULL)
    {
        p = p -> next;
        len ++ ;
    }
    return len;
}

编辑

6.单链表的建立

尾插法：

每次插入元素都插入到单链表的表尾
方法1：套用之前学过的位序插入，每次都要从头开始往后面遍历，时间复杂度为O(n^2)

编辑

//设置变量length记录链表长度，用ListInsert，O（n^2）；设置一个表尾指针，只要每次对r指针进行后插操作InsertNextNode，然后把表尾指针往后移
// O(n)
LinkList List_TailInsert(LinkList &L)
{
    int x;
    L = (LinkList)malloc(sizeof(LNode));        // 建立头结点
    LNode *s, *r = L;
    
    scanf("%d", &x);
    while (x != 9999)
    {
        s = (LNode *)malloc(sizeof(LNode));
        s -> data = x;
        r -> next = s;
        r = s;
        scanf("%d", &x);
    }
    r -> next = NULL;
    return L;
}

方法2：增加一个尾指针r，每次插入都让r指向新的表尾结点，时间复杂度为O(n) 编辑

头插法：

每次插入元素都插入到单链表的表头
头插法和之前学过的单链表后插操作是一样的，可以直接套用
L->next=NULL;可以防止野指针

编辑

总结：

头插法、尾插法：核心就是初始化操作、指定结点的后插操作
注意设置一个指向表尾结点的指针
头插法的重要应用：链表的逆置

7.双链表

为什么要要使用双链表：

单链表：无法逆向检索，有时候不太方便
双链表：可进可退，但是存储密度更低一丢丢

双链表的初始化（带头结点）代码实现：

编辑

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

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

typedef struct LNode        // 定义单链表结点类型
{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;
// 初始化一个循环单链表
bool InitList(LinkList &L)
{
    L = (LinkList)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;
}

双链表的插入

双链表的插入代码实现：

// 在p结点之后插入s结点（后插），以下是前插法，但由于是双链表，如果要前插，只要找到前一个用后插就可以
bool InsertNextNode(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 p;
}

小心如果p结点为最后一个结点产生的空指针问题，因此循环链表应运而生（详见后面的循环链表插入删除）
注意指针的修改顺序

双链表的删除：

双链表的删除代码实现：

// 删除p结点的后继结点
bool DeleteNextNode(DNode *p)
{
    if (p == NULL)
        return false;
    DNode *q = p -> next;
    if (q == NULL)
        return false;
    p -> next = q -> next;
    if (q -> next != NULL)
        q -> next -> prior = p;
    free(q);
    return true;
}
void DestroyList(DLinkList &L)
{
    while (L -> next != NULL)
        DeleteNextDNode(L);
    free(L);        // 释放头结点
    L = NULL;       // 头结点指向NULL
}

双链表的遍历：

编辑

循环链表

循环单链表与单链表的区别：

单链表：

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

循环单链表：

表尾结点的next指针指向头结点
从一个结点出发可以找到其他任何一个结点

循环单链表初始化：

从头结点找到尾部，时间复杂度为O(n)
如果需要频繁的访问表头、表尾，可以让L指向表尾元素（插入、删除时可能需要修改L）
从尾部找到头部，时间复杂度为O(1)

循环双链表的初始化：

编辑

循环双链表的初始化代码实现：

typedef struct DNode
{
    ElemType data;
    struct DNode *prior, *next;
}DNode, *DLinkList;
bool InitDLinkList(DLinkList &L)
{
    L = (LinkList)malloc(sizeof(LNode));
    if (L == NULL)
        return false;
    L -> prior = L;
    L -> next = L;
    return true;
}
bool Empty(DLinkList L)
{
    if (L -> next == L)
        return true;
    else
        return false;
}
bool isTail(LinkList L, DNode *p)
{
    if (p -> next == L)
        return true;
    else
        return false;
}

循环链表的插入：

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

编辑

循环双链表的插入代码实现

其实是双链表插入的缩减版

bool InsertNextDNode(LNode *p, LNode *s)
{
    s -> next = p -> next;
    p -> next -> prior = s;
    s -> prior = p;
    p -> next = s;
}

循环链表的删除：

与循环链表的插入相同。
编辑

循环双链表的删除代码实现

//同上
p -> next = q -> next;
q -> next -> prior = p;
free(q);

编辑

注意点：

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

如何判空
如何判断结点p是否是表尾/表头元素（后向/前向遍历的实现核心）
如何在表头、表中、表尾插入/删除一个结点

8.静态链表

什么是静态链表：

分配一整片连续的内存空间，各个结点集中安置
每个结点由两部分组成：data（数据元素）和next（游标）
0号结点充当“头结点”，不具体存放数据
游标为-1表示已经到达表尾
游标充当“指针”，表示下个结点的存放位置，下面举一个例子：
每个数据元素4B，每个游标4B（每个结点共8B），设起始地址为addr，e1的存放地址为addr + 8*2（游标值）

定义静态链表：

方法1：

编辑

定义静态链表代码实现：

#define MaxSize 10;
struct Node
{
    ElemType data;
    int next;
};
void testSLinkList()
{
    struct Node a[MaxSize];         // 数组a作为静态链表
}

方法2：

编辑

基本操作：

初始化：

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

插入位序为i的结点：

找到一个空的结点，存入数据元素（设为一个特殊值用来表示结点空闲，如-2）
从头结点出发找到位序为i-1的结点
修改新结点的next
修改i-1号结点的next

删除某个结点：

从头结点出发找到前驱结点
修改前驱结点的游标
被删除结点next设为-2

总结：

静态链表：用数组的方式实现的链表
优点：增、删操作不需要大量移动元素
缺点：不能随机存取，只能从头结点开始依次往后查找；容量固定不可变
适用场景：（1）不支持指针的低级语言；（2）数据元素数量固定不变的场景（如操作系统的文件分配表FAT）

9.顺序表和链表的比较

顺序表和链表的比较

	顺序表	链表
逻辑结构	都属于线性表，都是线性结构	都属于线性表，都是线性结构
存储结构	优点：支持随机存取、存储密度高缺点：大片连续空间分配不方便，改变容量不方便	优点：离散的小空间分配方便，改变容量方便缺点：不可随机存取，存储密度低

开放式问题的解题思路：

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

答案：

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

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

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

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

~~...~~

2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】

欢迎各位彦祖与热巴畅游本人专栏与博客

你的三连是我最大的动力

以下图片仅代表专栏特色 [点击箭头指向的专栏名即可闪现]

专栏跑道一

➡️网络空间安全——全栈前沿技术持续深入学习

专栏跑道二

➡️ 24 Network Security -LJS

专栏跑道三

➡️ MYSQL REDIS Advance operation

专栏跑道四

➡️HCIP；H3C-SE;CCIP——LJS[华为、华三、思科高级网络]

专栏跑道五

➡️RHCE-LJS[Linux高端骚操作实战篇]

专栏跑道六

➡️数据结构与算法[考研+实际工作应用+C程序设计]

专栏跑道七

➡️RHCSA-LJS[Linux初级及进阶骚技能]

上节回顾

1.单链表的定义

1.1顺序表：

1.2单链表：

2.定义一个单链表：

2.1 用代码定义一个单链表

补充说明：

3.不带头结点的单链表：

3.1带头结点的单链表：

3.2区别：

4.单链表的插入、删除

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

ListInsert(&L,i,e)：

编辑 按位序插入（带头结点）代码书写：

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

ListInsert(&L,i,e)：

指定结点的后插操作：

指定结点的前插操作：

方法1：前叉操作伪代码实现 编辑

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

指定结点的删除

指定结点的删除代码：

方法2注意！！！

5.单链表的查找【只探讨“带头结点”的情况】

按位查找：

单链表的按位查找代码：

按值查找：

按值查找代码

求表的长度

求表的长度代码：

6.单链表的建立

尾插法：

头插法：

总结：

7.双链表

为什么要要使用双链表：

双链表的初始化（带头结点）代码实现：

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

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

双链表的插入

双链表的删除：

双链表的遍历：

循环链表

循环单链表初始化：

循环双链表的初始化：

循环双链表的初始化代码实现：

循环链表的插入：

循环双链表的插入代码实现

循环链表的删除：

循环双链表的删除代码实现

注意点：

8.静态链表

基本操作：

初始化：

插入位序为i的结点：

删除某个结点：

总结：

9.顺序表和链表的比较

开放式问题的解题思路：

视觉智能

热门文章

最新文章

编辑按位序插入（带头结点）代码书写：

方法1：前叉操作伪代码实现编辑