目录
接下来的日子会顺顺利利,万事胜意,生活明朗-----------林辞忧
引言
我们所知道链表有八种结构,是由循环与不循环,带头不带头,单向与双向相互组合而成的,头节点是不存储任何数据的,其中我们主要学习的为带头循环双向和无头不循环单向链表(单链表),接下来我们将深入了解关于带头循环双向链表的魅力
一:结构定义
typedef int DLDataType;
typedef struct DList
{
struct DList* next;
struct DList* prev;
DLDataType data;
}DLNode;
二:带头循环双向链表的各种操作
1.初始化
DLNode* DLInit()//初始化
{
DLNode* phead = DLBuyNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
2.创建节点
DLNode* DLBuyNode(DLDataType x)//创建节点
{
DLNode* newnode = (DLNode*)malloc(sizeof(DLNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->next = NULL;
newnode->prev = NULL;
newnode->data = x;
return newnode;
}
3.尾插
void DLPushBack(DLNode* phead, DLDataType x)//尾插
{
assert(phead);
//DLInster(phead, x);
DLNode* newnode = DLBuyNode(x);
DLNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
4.头插
void DLPushFront(DLNode* phead, DLDataType x)//头插
{
assert(phead);
//DLInster(phead->next, x);
DLNode* newnode = DLBuyNode(x);
DLNode* next = phead->next;
newnode->next = next;
next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}
5.打印数据
void DLPrint(DLNode* phead)//打印数据
{
assert(phead);
DLNode* cur = phead->next;
printf("guard<=>");
while (cur != phead)
{
printf("%d<=>",cur->data);
cur = cur->next;
}
printf("\n");
}
6.判空
bool DLEmpty(DLNode* phead)//判空
{
assert(phead);
return phead->prev == phead;
}
7.尾删
void DLPopBack(DLNode* phead)//尾删
{
assert(phead);
assert(!DLEmpty(phead));
//DLErase(phead->prev);
DLNode* tail = phead->prev;
DLNode* tailPrev = tail->prev;
tailPrev->next = phead;
phead->prev = tailPrev;
free(tail);
}
8.头删
void DLPopFront(DLNode* phead)//头删
{
assert(phead);
assert(!DLEmpty(phead));
//DLErase(phead->next);
DLNode* del = phead->next;
DLNode* next = del->next;
phead->next = next;
next->prev = phead;
free(del);
}
9.查找
DLNode* DLFind(DLNode* phead, DLDataType x)//查找
{
DLNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
10.销毁
void DLDestroy(DLNode* phead)//销毁
{
assert(phead);
DLNode* cur = phead->next;
while (cur != phead)
{
DLNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
11.pos位置之前插入
void DLInster(DLNode* pos, DLDataType x)//pos位置之前插入
{
assert(pos);
DLNode* newnode = DLBuyNode(x);
DLNode* Prev = pos->prev;
Prev->next = newnode;
newnode->prev = Prev;
newnode->next = pos;
pos->prev = newnode;
}
12.删除pos位置的值
void DLErase(DLNode* pos)//删除pos位置的值
{
assert(pos);
DLNode* posPrev = pos->prev;
DLNode* posnext = pos->next;
posPrev->next = posnext;
posnext->prev = posPrev;
free(pos);
}
三:结束语
可以看出带头循环双向链表这个结构设计的非常巧妙,解决了单链表找尾难的问题,大大提高了效率