目录
1、带头双向循环链表功能
#pragma once
// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
LTDataType _data;
struct ListNode* _next;
struct ListNode* _prev;
}ListNode;
//动态申请一个节点
ListNode* BuyListNode(LTDataType x);
// 链表初始化
ListNode* ListInit();
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
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, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
2、带头双向循环链表功能实现
2.1动态申请一个节点
ListNode* BuyListNode(LTDataType x)
{
ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
if (NewNode == NULL)
{
std::cout << "内存分配失败" << std::endl;
exit(-1);//非正常退出
}
NewNode->_prev = NewNode->_next = NULL;
NewNode->_data = x;
return NewNode;
}
2.2、链表初始化
ListNode* ListInit()
{
ListNode* pHead = BuyListNode(0);//头节点数据0;
pHead->_prev = pHead->_next = plist;
return pHead;
}
2.3、双向链表销毁
void ListDestory(ListNode* pHead)
{
ListNode* cur = pHead->_next;
while (cur != pHead)
{
ListNode* node = cur;
cur = cur->_next;
free(node);
node = NULL;
}
free(pHead);
pHead = NULL;
}
2.4、双向链表打印
void ListPrint(ListNode* pHead)
{
ListNode* cur = pHead->_next;
while (cur != pHead)
{
std::cout << cur->_data;
cur = cur->_next;
}
std::cout << std::endl;
}
2.5、双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
ListNode* newnode = BuyListNode(x);
ListNode* tail = pHead->_prev;
newnode->_prev = tail;
newnode->_next = pHead;
tail->_next = newnode;
pHead->_prev = newnode;
}
2.6、双向链表尾删
void ListPopBack(ListNode* pHead)
{
if (pHead->_next != pHead)
{
ListNode* tail = pHead->_prev;
ListNode* next = tail->_prev;
pHead->_prev = next;
next->_next = pHead;
free(tail);
tail = NULL;
}
}
2.7、双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
ListNode* newnode = BuyListNode(x);
ListNode* next = pHead->_next;
pHead->_next = newnode;
newnode->_next = next;
next->_prev = newnode;
newnode->_prev = pHead;
}
2.8、双向链表头删
void ListPopFront(ListNode* pHead)
{
if (pHead->_next != pHead)
{
ListNode* pHeadnext = pHead->_next;
ListNode* next = pHeadnext->_next;
pHead->_next = next;
next->_prev = pHead;
free(pHeadnext);
pHeadnext = NULL;
}
}
2.9、双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
if (pHead->_next == pHead)
return NULL;
ListNode* cur = pHead->_next;
while (cur != pHead)
{
if (cur->_data == x)
return cur;
cur = cur->_next;
}
}
2.10、 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
ListNode* prev = pos->_prev;
ListNode* newnode = BuyListNode(x);
pos->_prev = newnode;
prev->_next = newnode;
newnode->_next = pos;
newnode->_prev = prev;
}
2.11、双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
ListNode* posPrev = pos->_prev;
ListNode* posNext = pos->_next;
posPrev->_next = posNext;
posNext->_prev = posPrev;
free(pos);
pos = NULL;
}
3、代码测试
void Text()
{
ListNode* plist = ListInit();
//test front
ListPushFront(plist, 3);
ListPrint(plist);//3
ListPushFront(plist, 2);
ListPrint(plist);//23
ListPushFront(plist, 1);
ListPrint(plist);//123
ListPopFront(plist);
ListPrint(plist);//23
//test Back
ListPushBack(plist, 4);
ListPrint(plist);//234
ListPushBack(plist, 5);
ListPrint(plist);//2345
ListPushBack(plist, 6);
ListPrint(plist);//23456
ListPopBack(plist);
ListPrint(plist);//2345
//pos insert & delete
ListNode* pos = ListFind(plist, 4);
// 双向链表在pos的前面进行插入
ListInsert(pos, 7);
ListPrint(plist);//23745
// 双向链表删除pos位置的节点
ListErase(pos);
ListPrint(plist);//2375
}
int main()
{
Text();
return 0;
}