上篇文章简述讲解了链表的基本概念并且实现了无头单向不循环链表:链接未来:深入理解链表数据结构(一.c语言实现无头单向非循环链表)-CSDN博
那今天接着给大家带来带头双向循环链表的实现:
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* next;//下一个节点
struct ListNode* prev;//上一个节点
LTDataType val;//数据
}LTNode;
LTNode* LTInit();//初始化
void LTPrint(LTNode* phead);//打印数据
void LTPushBack(LTNode* phead, LTDataType x);//尾插
void LTPopBack(LTNode* phead);//尾删
void LTPushFront(LTNode* phead, LTDataType x);//头插
void LTPopFront(LTNode* phead);//头删
LTNode* LTFind(LTNode* phead, LTDataType x);//查找
void LTInsert(LTNode* pos, LTDataType x);//在pos前插入
void LTErase(LTNode* pos);//删除pos
void LTDestroy(LTNode* phead);//销毁
因为后面尾插,头插,插入,初始化都要用到创建新节点,所以抽出来作为一个函数
LTNode* CreateLTNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//动态开辟
if (newnode == NULL)
{
perror("malloc");
return -1;
}
newnode->val = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
1.第一种:返回动态开辟的地址(不会销毁)
LTNode* LTInit()
{
LTNode* a =CreateLTNode(-1);
a->next = a;//一开始一个节点时,下一个和上一个都指向自己
a->prev = a;//
return a;
}
2.第二种:传入二级指针(要直接改变头节点的值)
void LTInit(LTNode** pphead)
{
*pphead = CreateLTNode(-1);
(*pphead)->next = *pphead;
(*pphead)->prev = *pphead;
}
这两种皆可
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;//头结点数据无效,不需要打印
while (cur != phead)
{
printf("%d ", cur->val);
cur = cur->next;
}
printf("\n");
}
void LTPushBack(LTNode* phead, LTDataType x)//无有效节点也适用
{
assert(phead);
LTNode* newnode = CreateLTNode(x);
LTNode* tail = phead->prev;
// phead tail newnode 位置展示
newnode->next = phead;
phead->prev = newnode;
newnode->prev = tail;
tail->next = newnode;
}
void LTPopBack(LTNode* phead)//只有一个有效节点也适用
{
assert(phead);
LTNode* tail = phead->prev;
LTNode* pretail = tail->prev;
// phead pretail tail 位置展示
free(tail);
tail = NULL;
phead->prev = pretail;
pretail->next = phead;
}
void LTPushFront(LTNode* phead, LTDataType x)//无有效节点也适用
{
assert(phead);
LTNode* newnode = CreateLTNode(x);
//phead newnode firest tail 位置展示
newnode->next = phead->next;
phead->next->prev = newnode;
newnode->prev = phead;
phead->next = newnode;
}
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);//只有哨兵位时不能删
LTNode* first = phead->next;
LTNode* second = first->next;
//phead first second tail 位置展示
free(first);
first = NULL;
phead->next = second;
second->prev = phead;
}
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
assert(phead->next != phead);//只有哨兵位时没必要查
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->val == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = CreateLTNode(x);
LTNode* pre = pos->prev;
//pre newnode pos tail 位置展示
pre->next = newnode;
newnode->prev = pre;
newnode->next = pos;
pos->prev = newnode;
}
pre
的 next
指针指向新节点 newnode
newnode
的 prev
指针指向前一个节点 pre
newnode
的 next
指针指向指定节点 pos
pos
的 prev
指针指向新节点 newnode
void LTErase(LTNode* pos)
{
assert(pos);
LTNode* pre = pos->prev;
LTNode* next = pos->next;
//pre pos next tail 位置展示
pre->next = next;
next->prev = pre;
free(pos);
pos = NULL;
}
因为每个节点时malloc动态开辟出来的,要把每个节点都依次销毁
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur->next != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
phead = NULL;
}
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTInsert(phead, x);//尾插就是在phead前插入
}
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTErase(phead->prev);
}
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTInsert(phead->next, x);//头插就是插入到phead的下一个
}
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTErase(phead->next);
}