©2020-2024 ioDraw All rights reserved,
Privacy Policy
双向循环链表的组成
只有一个节点的时候，把头指针和尾指针都指向自己，形成了一个环形，通常把这种链表叫作双向循环链表
多个节点形成环形
双向循环链表主要分为三部分
*
前项指针
*
后项指针
*
数据域
*
第一个节点的前项指针指向最后一个节点，最后一个节点的后项指针指向第一个节点
双向循环链表的结构体描述(节点)
#include <stdio.h> #include <stdlib.h> #include <assert.h> typedef struct Node
{ int data; //数据域 struct Node* front; //前项指针 struct Node* tail; //后项指针
}NODE,*LPNODE,*LPDLIST;
创建节点
把用户的数据变成一个结构体变量
LPNODE createNode(int data) { //申请内存 LPNODE newNode =
(LPDLIST)malloc(sizeof(NODE)); //断言处理 assert(newNode); //前项指针、后项指针置为空
newNode->front = NULL; newNode->tail = NULL; //给数据做初始化 newNode->data = data;
return newNode; }
创建链表
*
描述链表最初的状态，创建一个不带数据的链表，链表就是结构体变量和结构体变量连接在一起
*
需要一个表头，由于是环形，如果没有表头不方便表示，创建一个表头起区分作用。创建无头链表也可以，但是也需要有一个节点表示这个链表
LPDLIST createList() { LPDLIST headNode = (LPDLIST)malloc(sizeof(NODE)); //头节点
做动态内存申请 assert(headNode); headNode->front = headNode; //头指针指向自身 尾指针指向自身 数据不做处理
headNode->tail = headNode; return headNode; }
头插法
创建新节点做插入四步操作，不需要考虑空的情况，不存在空的情况，注意插入的顺序一定是先连后断
先求出来表头 headNode->tail
①原来链表的尾节点的前项指针指向新节点
②新节点的前项指针指向原来链表
③原来链表的后项指针指向新节点
④新节点的后项指针指向原来链表的尾节点
//要插入的链表 插入的数据 void push_front(LPDLIST headNode,int data) { //创建新节点 LPNODE
newNode = createNode(data); //就算只有一个节点、只有一个表头headNode->tail不可能为空 直接做连接就可以了
headNode->tail->front = newNode; newNode->front = headNode; newNode->tail =
headNode->tail; headNode->tail = newNode; } //测试代码 LPDLIST list = createList();
push_front(list, 1); //1 push_front(list, 2); //2 1 printByFront(list); //1 2
通过前项指针做打印 从后往前 printByTail(list); //2 1 通过后项指针做打印 从前往后
打印链表
可以通过前项指针去做打印，也可以通过后项指针去做打印
<>通过前项指针做打印
可以通过前项指针去做打印，由于是环形，所以打印条件不太一样，不可能用空来做判定。环形的结束状态就是跑一圈又回到自己这个位置，我们可以从第二个节点开始打印，如果不等于头节点就一直做打印
void printByFront(LPDLIST headNode) { //头节点的前项指针就是最后一个节点 LPNODE pmove =
headNode->front; //最后一个不等于头节点 while (pmove != headNode) { //打印数据 printf("%d\t",
pmove->data); pmove = pmove->front; } printf("\n"); }
通过后项指针做打印
void printByTail(LPDLIST headNode) { LPNODE pmove = headNode->tail; while
(pmove != headNode) { printf("%d\t", pmove->data); pmove = pmove->tail; }
printf("\n"); }
尾插法
错误的画法，指针的方向反，两个指针指向同一个位置
先求出来表尾 headNode->front
①原来链表的尾节点的后项指针指向新节点
②新节点的后项指针指向原来链表的第一个节点
③新节点的前项指针指向原来链表的尾节点
④原来链表的第一个节点的前项指针指向新节点
void push_back(LPDLIST headNode, int data) { //创建新节点 LPNODE newNode =
createNode(data); headNode->front->tail = newNode; newNode->tail = headNode;
newNode->front = headNode->front; headNode->front = newNode; } //测试代码
push_back(list, 888); printByTail(list); //2 1 888 printByFront(list); //888 2 1
在指定位置前做插入
找指定位置，定义一个移动的指针从第一个节点开始找，头节点不用找，找一个环形代表没找到
void push_appoin(LPDLIST headNode, int posData, int data) { //前驱节点置为头节点 LPNODE
preNode = headNode; //从第一个节点开始找 LPNODE curNode = headNode->tail;
//1.当前节点不等于头节点表示没有形成一个环形 2.当前节点的数据不等于指定数据 while (curNode !=
headNode&&curNode->data!=posData) { //并排往下走 preNode = curNode; curNode =
preNode->tail; } //分析结果做插入 if (curNode == headNode) {
printf("未找到指定位置,无法插入!\n"); } else { //找到了 创建一个新节点做插入 LPNODE newNode =
createNode(data); //tail指向 preNode->tail = newNode; newNode->tail = curNode;
//front指向 curNode->front = newNode; newNode->front = preNode; } } //测试代码
push_appoin(list, 888, 666); printByTail(list); //2 1 666 888
printByFront(list); //888 666 2 1 push_appoin(list, 2, 999);
printByFront(list); //999 2 1 666 888 printByTail(list); //2 1 666 888 999
头删法
①头节点的下一个指向要删除节点的下一个
②要删除节点的下一个的前项指针指向头节点
void pop_front(LPDLIST headNode) { //头指针、尾指针指向自己 这个链表就是空的 if
(headNode==NULL||headNode->front == headNode) { printf("链表为空无法删除!\n"); } else {
//保存头部的下一个 LPNODE nextNode = headNode->tail; //连接 headNode->tail =
nextNode->tail; nextNode->tail->front = headNode; //释放 free(nextNode); //置空
nextNode = NULL; } } //测试代码 pop_front(list); printByTail(list); //2 1 666 888
printByFront(list); //888 666 1 2
尾删法
①最后一个节点的前一个节点的后项指针指向头节点
②头节点的前项指针指向最后一个节点的前一个节点
void pop_back(LPDLIST headNode) { if (headNode == NULL || headNode->front ==
headNode) { printf("链表为空无法删除!\n"); } else { //保存尾部的上一个 LPNODE backNode =
headNode->front; backNode->front->tail = headNode; headNode->front =
backNode->front; //释放 free(backNode); //置空 backNode = NULL; } } //测试代码
pop_back(list); printByTail(list); //2 1 666 printByFront(list); //666 1 2