94.【C语言】数据结构之双向链表的初始化,尾插,打印和尾删

目录

1.双向链表

2.结构体的定义

3.示意图

3.代码示例

1.双向链表的尾插

示意图

代码

main.c

List.h

List.c

详细分析代码的执行过程

双向链表的初始化

2.双向链表的打印

代码

3.双向链表的尾删

---

1.双向链表

以一种典型的双向链表为例:带头双向循环链表(带头:带哨兵位的头节点)

2.结构体的定义

typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;

3.示意图

head为带哨兵位的头节点,无有效数值,只储存第一个有效节点的地址,负责找到第一个节点

特点:

1.prev指向前一个节点,next指向下一个节点

2.末尾的next指向哨兵位的头

3.哨兵位的头的prev指向末尾(不用像单向链表那样循环找尾节点)

3.代码示例

List.h

#pragma once
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
typedef int LTDataType;typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;void LTInit();
void LTDestory();
void LTPushBack(LTNode* phead,LTDataType x);
void LTPopBack(LTNode* phead);

用结构体定义节点,节点有三部分构成:next指针,prev指针和数据,符合双向节点的定义

 

注:prev为previous的缩写

1.双向链表的尾插

示意图

非空链表

空链表

和之前的无头的单向链表有所不同,这里的带哨兵位的头节点

未尾插之前,head->prev指向head->next,head->next指向head->prev(这样可以实现双向循环)

千万不要被箭头的指向所误导!!!!

不是head->prev=head->next;head->next=head->prev;

箭头指向的是head节点
head->prev=head;head->next=head;

尾插之后

实现过程和非空链表一样

*无论对于空链表还是非空链表,尾插都只需要4步,即修改四个指针*

tail指向尾节点

代码

main.c

#include "List.h"
void TestList()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);
}int main()
{TestList();return 0;
}

List.h

#include <assert.h>
typedef int LTDataType;typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;LTNode* LTInit();
LTNode* BuyListNode(LTDataType x);
void LTPushBack(LTNode* phead, LTDataType x);

List.c

#include "List.h"
LTNode* LTInit()
{LTNode* phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;
}LTNode* BuyListNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc");return NULL;}node->next = NULL;node->prev = NULL;node->data = x;return node;
}void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}

详细分析代码的执行过程

进入main函数-->调用TestList函数-->调用LTInit函数-->调用BuyListNode函数

在BuyListNode函数中,先为新的节点开辟空间,之后node指向新节点,如果node为NULL,则开辟失败返回NULL,如果开辟成功继续向下执行①prev和next置NULL ②写入节点的data值

返回node指针,BuyListNode函数结束

双向链表的初始化

在LTInit函数中,phead得到node的值

已知phead存储的值为00 c0 a0 98,求phead->next = phead;和phead->prev = phead;执行完后按小端序计算0x00c0a098~0x00c0a09f处的数据

解:

按照结构体成员变量定义的先后顺序

phead->prev存储在0x00C0A098~0x00C0A09B处,phead->next存储在0x00C0A09C~0x00C0A09F处

因此答案为98 a0 c0 00 98 a0 c0 00

返回phead后,LTInit函数结束

在TestList函数中,plist得到phead的值

调用LTPushBack函数

在LTPushBack函数中,phead得到plist的值(这里没有传二级指针,修改结构体成员变量的值只需要一级指针),断言phead,确保phead不为NULL

调用BuyListNode,返回新节点的地址给newnode

只有带哨兵位的头结点时,LTNode* tail = phead->prev;等价为LTNode* tail = phead;

LTPushBack函数结束

剩下的分析思想一样,略去

2.双向链表的打印

让cur指针指向head节点的下一个节点,循环打印,当cur直到head时,停止打印

代码

void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;printf("head<=>");while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}printf("\n");
}

3.双向链表的尾删

尾删要单独判断是否只有带哨兵位的头节点

写一个LTEmpty函数

bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}

直接将phead->next == phead结果的真假返回,比if判断要简洁

void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));//注意感叹号LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;//定义指向tail的前一个节点的指针tailPrev->next = phead;phead->prev = tailPrev;free(tail);tail = NULL;
}