【数据结构与算法】双向链表
链表的分类
单向、双向带头单链表、不带头链表循环、非循环在我们平时的学习中,最常用的两种链表:
无头单向非循环链表
带头双向循环链表
head的是哨兵位头结点,不存储数据
下文主要讲解第二种带头双向链表
创建结构体
双向链表中,每个结点除了包含下个节点的地址外,还包含前一个结点的地址,因此我们需要分别创建两个指针next和prev
创建结构体代码
typedef int LTDataType;typedef struct ListNode{struct ListNode* next;struct ListNode* prev;LTDataType data;}ListNode;
链表初始化
方法一:要完成初始化,我们需要把phead的地址传给相应的初始化函数,只有址传递才能改变phead的值,下面例子则是错误的:
下面我们来看看调用部分的phead和传入函数后的phead的地址是否相同
调用部分的phead地址如下
传入函数后的phead的地址如下
可见此时phead的地址不一样,因此无法对传入的phead指针变量进行修改,正确的操作应该是传入phead的地址,如下图
此时传入的即为指针变量的地址,可以实现对传入指针变量的修改(初始化)了
初始化函数代码(方法一)
//初始化链表void ListInit(ListNode** pphead){*pphead = BuyListNode(0);(*pphead)->next = *pphead;(*pphead)->prev = *pphead;return pphead;}
**方法二:**这种方法比较简单,不用传入二级指针,直接返回初始化函数创建的头结点赋值给phead即可完成初始化
ListNode* phead = ListInit();
初始化函数代码(方法二)
//初始化链表ListNode* ListInit(){ListNode* phead = BuyListNode(0);phead->next = phead;phead->prev = phead;return phead;}
清理数据结点
指针cur指向当前要清理的结点,next用于保存下一个待清理结点的地址
cur==phead的时候的时候,结束清理,且对phead初始化,以确保头结点继续使用
phead->next = phead;phead->prev = phead;
清理数据结点代码
void ListClear(ListNode* phead){assert(phead);//清理所有数据结点,保留头结点,可以继续使用ListNode* cur = phead->next;while (cur != phead){ListNode* next = cur->next;free(cur);cur = next;}phead->next = phead;phead->prev = phead;}
销毁链表
上面我们讲的是对链表的结点进行清理,但如果这个链表不再使用时,需要将头结点也一起销毁
销毁链表代码
//销毁链表void ListDestroy(ListNode* phead){assert(phead);ListClear(phead);free(phead);}
创建新结点
ListNode* BuyListNode(LTDataType x){ListNode*node = (ListNode*)malloc(sizeof(ListNode));//初始化node->next = NULL;node->prev = NULL;node->data = x;return node;}
链表的打印
思路:
结束条件和单链表不一样,单链表是在打印结点指向NULL时结束打印,但现在是循环链表,不存在指向NULL的问题,因此,结束条件可改为当cur(进行结点打印的指针)等于phead时结束打印
头结点phead是哨兵位结点,不储存信息,因此从phead的下一个指针开始打印
链表的打印代码
assert(phead);ListNode* cur = phead->next;while (cur != phead) //结束条件{print("%d ", cur->data);cur = cur->next;}
尾插
进行尾插,首先要找到尾结点,由上图可知双链表头结点的prev指针指向的就是尾结点
ListNode* tail = phead->prev;
尾结点找到后,我们来插入新的结点,首先我们将新结点和尾结点进行链接,如下图红色箭头
tail->next = newnode;newnode->prev = tail;
头结点与新结点链接
newnode->next = phead;phead->prev = newnode;
尾插代码
//尾插void ListPushBack(ListNode* phead, LTDataType x){assert(phead); //断言,头指针不指向NULLListNode* tail = phead->prev;ListNode* newnode = BuyListNode(x);//进行结点的链接tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}
尾删
思路:
确定尾结点
ListNode* tail = phead->prev;ListNode* tailPrev = tail->prev;
tailPrev指向的结点与头结点进行链接
phead->prev = tailPrev;tailPrev->next = phead;
删除尾结点
尾删代码
//尾删void ListPopBack(ListNode* phead){assert(phead);if (phead->next == phead) //判断是否只有哨兵位头结点{return phead;}else{ListNode* tail = phead->prev;ListNode* tailPrev = tail->prev;phead->prev = tailPrev;tailPrev->next = phead;free(tail);return phead;}}
头插
头插是指在哨兵位头结点的后面插入
思路:
定义first指针用于储存原链表中phead的后一个结点
新结点与phead链接
phead->next = newnode;newnode->prev = phead;
新结点与first链接,头插结束
newnode->next = first;first->prev = newnode;
头插代码
//头插void ListPushFront(ListNode* phead, LTDataType x){assert(phead);ListNode* first = phead->next;ListNode* newnode = BuyListNode(x);phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;}
头删
把哨兵位结点的后一个结点删除
创建两个指针first和second
ListNode* first = phead->next;ListNode* second = first->next;
phead与second链接,删除first
phead->next = second;second->prev = phead;free(first);
头删代码
//头删void ListPopFront(ListNode* phead){assert(phead);assert(phead->next!=phead);ListNode* first = phead->next;ListNode* second = first->next;phead->next = second;second->prev = phead;free(first);}
链表的查找
查找只要对链表遍历即可,逻辑和打印链表相似,直接上代码
链表的查找代码
//查找ListNode* ListFind(ListNode* phead, int x){assert(phead);ListNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;}
插入(任意结点)
要在给定结点的前面插入(例如在d2前插入),就要先得到这个给定结点的位置,那么用查找函数确定这个结点的位置pos
后面的插入和前面所提到到两种插入大同小异,这里就不赘述了
插入(任意结点)代码
//插入(任意位置)void ListInsert(ListNode* pos, LTDataType x){assert(pos);ListNode* posPrev = pos->prev;ListNode* newnode = BuyListNode(x);posPrev->next = newnode;newnode->prev = posPrev;newnode->next = pos;pos->prev = newnode;}
删除(任意结点)
删除(任意结点)代码
//删除(任意位置)void ListErase(ListNode* pos){assert(pos);ListNode* posPrev = pos->prev;ListNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;}
双链表完整代码
List.h文件
#pragma once#include<stdio.h>#include<assert.h>#include<stdlib.h>typedef int LTDataType;typedef struct ListNode{struct ListNode* next;struct ListNode* prev;LTDataType data;}ListNode;//void ListInit(ListNode** phead);ListNode* ListInit();void ListClear(ListNode* phead);void ListDestroy(ListNode* phead);ListNode* BuyListNode(LTDataType x);void ListPrint(ListNode* phead);void ListPushBack(ListNode* phead, LTDataType x);void ListPopBack(ListNode* phead);void ListPushFront(ListNode* phead, LTDataType x);void ListPopFront(ListNode* phead);ListNode* ListFind(ListNode* phead, int x);void ListInsert(ListNode* pos, LTDataType x);void ListErase(ListNode* pos);
List.c文件
#include "List.h"//初始化链表ListNode* ListInit(){ListNode* phead = BuyListNode(0);phead->next = phead;phead->prev = phead;return phead;}//创建新结点ListNode* BuyListNode(LTDataType x){ListNode*node = (ListNode*)malloc(sizeof(ListNode));node->next = NULL;node->prev = NULL;node->data = x;return node;}//清理数据结点void ListClear(ListNode* phead){assert(phead);//清理所有数据结点,保留头结点,可以继续使用ListNode* cur = phead->next;while (cur != phead){ListNode* next = cur->next;free(cur);cur = next;}phead->next = phead;phead->prev = phead;}//销毁链表void ListDestroy(ListNode* phead){assert(phead);ListClear(phead);free(phead);}//打印void ListPrint(ListNode* phead){assert(phead);ListNode* cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");}//尾插void ListPushBack(ListNode* phead, LTDataType x){assert(phead); //断言,头指针不指向NULLListNode* tail = phead->prev;ListNode* newnode = BuyListNode(x);//进行结点的链接tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}//尾删void ListPopBack(ListNode* phead){assert(phead);if (phead->next == phead) //判断是否只有哨兵位头结点{return phead;}else{ListNode* tail = phead->prev;ListNode* tailPrev = tail->prev;phead->prev = tailPrev;tailPrev->next = phead;free(tail);return phead;}}//头插void ListPushFront(ListNode* phead, LTDataType x){assert(phead);ListNode* first = phead->next;ListNode* newnode = BuyListNode(x);phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;}//头删void ListPopFront(ListNode* phead){assert(phead);assert(phead->next!=phead);ListNode* first = phead->next;ListNode* second = first->next;phead->next = second;second->prev = phead;free(first);}//查找ListNode* ListFind(ListNode* phead, int x){assert(phead);ListNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;}//插入(任意位置)void ListInsert(ListNode* pos, LTDataType x){assert(pos);ListNode* posPrev = pos->prev;ListNode* newnode = BuyListNode(x);posPrev->next = newnode;newnode->prev = posPrev;newnode->next = pos;pos->prev = newnode;}//删除(任意位置)void ListErase(ListNode* pos){assert(pos);ListNode* posPrev = pos->prev;ListNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;}
test.c
#include "List.h"void TestList1(){ListNode* phead = ListInit();ListPushBack(phead, 1);ListPushBack(phead, 2);ListPushBack(phead, 3);ListPushBack(phead, 4);ListPrint(phead);ListPopBack(phead);ListPopBack(phead);ListPopBack(phead);ListPopBack(phead);ListPopBack(phead);ListPrint(phead);ListPushFront(phead, 1);ListPushFront(phead, 2);ListPushFront(phead, 3);ListPushFront(phead, 4);ListPushFront(phead, 5);ListPrint(phead);ListPopFront(phead);ListPopFront(phead);ListPopFront(phead);ListPopFront(phead);ListPopFront(phead);ListPrint(phead);ListDestroy(phead);}void TestList2(){ListNode* phead = ListInit();ListPushBack(phead, 1);ListPushBack(phead, 2);ListPushBack(phead, 3);ListPushBack(phead, 4);ListPrint(phead);ListNode* pos = ListFind(phead, 3);ListInsert(pos, 30);ListPrint(phead);pos = ListFind(phead, 3);ListErase(pos);ListPrint(phead);ListDestroy(phead);}void main(){//TestList1();TestList2();}
如果觉得《【数据结构与算法】双向链表C语言描述》对你有帮助,请点赞、收藏,并留下你的观点哦!