4、数据结构——简单的线性表——双链表（三）

一、双链表

定义

​ 顾名思义，简单来说就是可以双向走的单链表，对单链表而言是无法走到前一个结点的，但是双链表可以。

image-20240215161327784

结构体定义

1
2
3
4
typedef struct DNode {
    ElemType data;
    struct DNode *prior, *next; // prior表示的是指向当前结点的前一个结点的指针变量
}DNode,*DLinkList;

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
............
bool InitLinkList(DLinkList &L) 
{
    L = (DNode *)malloc (sizeof DNode);
    if (L == NULL) return false;
    L -> prior = NULL;
    L -> next = NULL;
    return true;
}

bool Empty(DLinkList L) {
	return L -> next ==  NULL;
}

int main()
{
    DLinkList L;
    InitLinkList(L);
    ......
    return 0;
}

双链表的插入（有头结点）

1
2
3
4
5
6
7
8
9
10
11
12
.........
// p结点后面插入s结点
bool InsertNextNode(DNode *p, DNode *s)
{
    if (p == NULL || s == NULL) return false;
    s -> next = p -> next;
    if (p -> next != NULL) p -> next -> prior = s;
    // 下面的两行代码的顺序不可以变，之前也有过类似的地方，此处不做详细介绍
    s -> prior = p;
    p -> next = s;
    return true;
}
image-20240215162548282 image-20240215162909595

双链表的删除

1
2
3
4
5
6
7
8
9
10
// 刪除p的后继结点
bool DeleteNextNode(DNode *p) {
    if (p == NULL) return false;
    DNode *q = p -> next; // 寻找p的后继结点
    if (q == NULL) return false; // p无后继结点
    p -> next = q -> next;
    if (q -> next != NULL) q -> next -> prior = p; // q结点不是最后一个结点
    free(q); // 释放结点空间
    return true;
}

双链表的销毁

1
2
3
4
5
void DestroyList (DLinkList &L) {
    while (L -> next != NULL) DeleteNextNode(L);
    free(L);
    L = NULL;
}

双链表的遍历

image-20240215163927742

下一节内容是：5、简单的线性表——循环链表！！！

一定要把本节内容看懂再往下看，不然会非常痛苦的哦o(╥﹏╥)oo(╥﹏╥)oo(╥﹏╥)o……..