作者:一个喜欢猫咪的的程序员
专栏:《数据结构》
喜欢的话:世间因为少年的挺身而出,而更加瑰丽。 ——《人民日报》
目录
带头双向循环链表
本篇我们来介绍一个结构比较复杂的链表——带头双向循环链表
它的结构看上去十分复杂但代码实现这个链表确实很简单的。
如果对其中函数实现思想不太懂的话可以看看我的另外一篇博客:
List.h
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int LTDateType; typedef struct ListNode { struct ListNode* prev; LTDateType date; struct ListNode* next; }LTNode; LTNode* BuyListNode(LTDateType x); LTNode* LTInit(); void LTPrint(LTNode* phead); void LTPushBack(LTNode* phead, LTDateType x); void LTPopBack(LTNode* phead); void LTPushFront(LTNode* phead, LTDateType x); void LTPopFront(LTNode* phead); LTNode* LTFind(LTNode* phead, LTDateType x); void LTInsert(LTNode* pos, LTDateType x); void LTErase(LTNode* pos); bool LTEmpty(LTNode*phead); size_t LTSize(LTNode* phead); void LTDestroy(LTNode* phead);
List.c
#include"List.h" LTNode* BuyListNode(LTDateType x) { LTNode* node = (LTNode*)malloc(sizeof(LTNode)); if (node == NULL) { perror("malloc fail"); exit(-1); } node->date = x; node->next = NULL; node->prev = NULL; return node; } LTNode* LTInit() { LTNode*phead = BuyListNode(-1); phead->next = phead; phead->prev = phead; return phead; } void LTPushBack(LTNode* phead, LTDateType x) { assert(phead); /*LTNode* newnode = BuyListNode(x); LTNode* tail = phead->prev; tail->next = newnode; newnode->prev = tail; phead->prev = newnode; newnode->next = phead;*/ LTInsert(phead, x); } void LTPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead); /*LTNode* tail = phead->prev; LTNode* tailPrev = tail->prev; tailPrev->next = phead; phead->prev = tailPrev; free(tail);*/ LTErase(phead->prev); } void LTPushFront(LTNode* phead, LTDateType x) { /*LTNode* newnode = BuyListNode(x); LTNode* cur = phead->next; phead->next = newnode; newnode->prev = phead; newnode->next = cur; cur->prev = newnode;*/ LTInsert(phead->next, x); } void LTPrint(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur!=phead) { printf("%d->", cur->date); cur = cur->next; } printf("\n"); } void LTPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead); //LTNode* first = phead->next; //LTNode* second = first->next; //phead->next = second; //second->prev = phead; //free(first); LTErase(phead->next); } LTNode* LTFind(LTNode* phead, LTDateType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->date == x) return cur; cur = cur->next; } return NULL; } void LTInsert(LTNode* pos, LTDateType x) { assert(pos); LTNode* newnode = BuyListNode(x); LTNode* front = pos->prev; front->next = newnode; newnode->prev = front; pos->prev = newnode; newnode->next = pos; } void LTErase(LTNode* pos) { assert(pos); LTNode* prev = pos->prev; LTNode* next = pos->next; free(pos); prev->next = next; next->prev = prev; } bool LTEmpty(LTNode* phead) { assert(phead); return phead == phead->next; } size_t LTSize(LTNode* phead) { assert(phead); size_t size = 0; LTNode* cur = phead->next; while (cur != phead) { ++size; cur = cur->next; } return size; } void LTDestroy(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; } free(phead); //phead = NULL; }
Test.c
#include"List.h" void test1() { LTNode* phead = LTInit(); LTPushBack(phead,1); LTPushBack(phead, 2); LTPushBack(phead, 3); LTPushBack(phead, 4); LTPrint(phead); LTPopBack(phead); //LTPopBack(phead); //LTPopBack(phead); /*LTPopBack(phead);*/ LTPrint(phead); LTPushFront(phead,10); LTPrint(phead); LTPopFront(phead); LTPrint(phead); } void test2() { LTNode* phead = LTInit(); LTPushBack(phead, 1); LTPushBack(phead, 2); LTPushBack(phead, 3); LTPushBack(phead, 4); LTPrint(phead); LTNode* pos = LTFind(phead, 3); if (pos) { pos->date = pos->date * 10; LTPrint(phead); } LTPushFront(phead, 10); LTPrint(phead); } int main() { test2(); return 0; }