一、结构定义
//带头双向循环链表的结构定义 typedef int LTDataType; typedef struct ListNode { LTDataType val; struct LTNode* next; struct LTNode* prev; }LTNode;
二、结点创建
//带头双向循环链表结点创建 LTNode* CreateLTNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malLoc fail:"); exit(-1); } newnode->val = x; newnode->next = NULL; newnode->prev = NULL; return newnode; }
三、头结点初始化
//带头双向循环链表的初始化 LTNode* LTInit(LTNode* phead) { phead = CreateLTNode(-1); phead->next = phead; phead->prev = phead; return phead; }
四、链表打印
//带头双向循环链表的打印 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;//尾指针 //尾插 tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }
六、头插
//带头双向循环链表的头插 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = CreateLTNode(x); LTNode* first = phead->next; newnode->next = first; first->prev = newnode; phead->next = newnode; newnode->prev = phead; }
七、尾删
//带头双向循环链表的尾删 void LTPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead);//空链表不能删 LTNode* tail1 = phead->prev;//尾1结点 LTNode* tail2 = tail1->prev;//尾2结点 tail2->next = phead; phead->prev = tail2; free(tail1); tail1 = NULL; }
八、头删
//带头双向循环链表的头删 void LTPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead);//空链表不能删 LTNode* first = phead->next; LTNode* second = first->next; free(first); first = NULL; phead->next = second; second->prev = phead; }
九、查找（返回结点）
//带头双向循环链表的查找 LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->val == x) return cur; else cur = cur->next; } return NULL; }
十、任意位置插入
如果插入位置是哨兵位，那么相当于尾插
如果插入位置是哨兵位的后一结点，那么相当于头插
//带头双向循环链表的任意位置插入 void LTInsert(LTNode* pos, LTDataType x) { assert(pos);//插入位置必须有效 LTNode* newnode = CreateLTNode(x); LTNode* posPrev = pos->prev; newnode->next = pos; pos->prev = newnode; posPrev->next = newnode; newnode->prev = posPrev; }
十一、任意位置删除
如果删除位置是哨兵位的后一结点，那么相当于头删
如果删除位置是哨兵位的前一结点，那么相当于尾删
//带头双向循环链表的任意位置删除 void LTErase(LTNode* pos) { assert(pos); LTNode* posPrev = pos->prev; LTNode* posNext = pos->next; posPrev->next = posNext; posNext->prev = posPrev; free(pos); }
十二、利用LTInsert写尾插函数
//利用LTInsert写尾插函数 void LTPushBackInsert(LTNode* phead, LTDataType x) { assert(phead); LTInsert(phead, x); }
十三、利用LTInsert写头插函数
//利用LTInsert写头插函数 void LTPushFrontInsert(LTNode* phead, LTDataType x) { assert(phead); LTInsert(phead->next, x); }
十四、利用LTErase写尾删函数
//利用LTErase写尾删函数 void LTPopBackErase(LTNode* phead) { assert(phead->next != phead);//链表为空不能删除 LTErase(phead->prev); }
十五、利用LTErase写头删函数
//利用LTErase写头删函数 void LTPopFrontErase(LTNode* phead) { assert(phead->next != phead); LTErase(phead->next); }
十六、销毁链表
//销毁带头双向循环链表 void LTDestroy(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* tmp = cur; cur = cur->next; free(tmp); } free(phead); }
十七、测试代码
void test01() { //初始化哨兵位 LTNode* plist = NULL; plist = LTInit(plist); //LTNode* plist = LTInit(plist); //尾插 LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPushBack(plist, 5); LTPushBack(plist, 6); //头插 LTPushFront(plist, 1); LTPushFront(plist, 2); LTPushFront(plist, 3); LTPushFront(plist, 4); LTPushFront(plist, 5); LTPushFront(plist, 6); //打印 LTPrint(plist); //尾删 LTPopBack(plist); LTPopBack(plist); LTPopBack(plist); //打印 LTPrint(plist); //头删 LTPopFront(plist); LTPopFront(plist); LTPopFront(plist); //打印 LTPrint(plist); //查找值为2的结点并在该位置插入值为10的结点 LTNode* pos1 = LTFind(plist, 2); LTInsert(pos1, 10); //打印 LTPrint(plist); //查找值为3的结点并删除该结点 LTNode* pos2 = LTFind(plist, 3); LTErase(pos2); //打印 LTPrint(plist); //尾插 LTPushBackInsert(plist, 1); LTPushBackInsert(plist, 2); LTPushBackInsert(plist, 3); LTPushBackInsert(plist, 4); //打印 LTPrint(plist); //头插 LTPushFrontInsert(plist, 1); LTPushFrontInsert(plist, 2); LTPushFrontInsert(plist, 3); LTPushFrontInsert(plist, 4); //打印 LTPrint(plist); //尾删 LTPopBackErase(plist); LTPopBackErase(plist); LTPopBackErase(plist); //打印 LTPrint(plist); //头删 LTPopFrontErase(plist); LTPopFrontErase(plist); LTPopFrontErase(plist); //打印 LTPrint(plist); //销毁链表 //LTDestroy(plist); //plist=NULL; } int main() { test01(); return 0; }
