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