这篇“C语言带头双向循环链表怎么实现”文章的知识点大部分人都不太理解,所以小编给大家总结了以下内容,内容详细,步骤清晰,具有一定的借鉴价值,希望大家阅读完这篇文章能有所收获,下面我们一起来看看这篇“C语言带头双向循环链表怎么实现”文章吧。
实际上,单链表也存在一个比较大的缺陷:
1.不能从后往前遍历
2.无法找到前驱
除了单链表之外,我们自然还有双向链表,我们要说的就是带头双向循环链表,简单理解为:带头结点的,有两个方向的。循环的。结构图如下:
结构虽然比较复杂,但是极大方便我们找结点,比如可以直接找到尾结点,然后再进入相关的操作。实际代码的操作将会比单链表简单,极为方便,这里不做过多说明,直接上手代码
我们直奔主题,进入代码实现的操作,之前的操作如果理解了,那我相信这个对于你来说肯定是不难的。下面直接给出源码:
List.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <malloc.h> #include <assert.h> #include <stdbool.h> typedef int LTDataType; //带头双向循环--最优链表结构,在任意位置插入删除数据都是O(1) typedef struct listNode { struct ListNode* next; struct ListNode* prev; LTDataType data; }ListNode; //初始化 ListNode*ListInit(); //销毁 void ListDestory(ListNode* phead); //打印 void ListPrint(ListNode* phead); //尾插 void ListPushBack(ListNode* phead, LTDataType x); //头插 void ListPushFront(ListNode* phead, LTDataType x); //头删 void ListPopFront(ListNode* phead); //尾删 void ListPopBack(ListNode* phead); ListNode* ListFind(ListNode* phead, LTDataType x); //在pos位置之前插入x void ListInsert(ListNode* pos, LTDataType x); //删除pos位置的值 void ListErase(ListNode* pos);
List.c
#include "List.h" //开辟一个新结点 ListNode* BuyListNode(LTDataType x) { ListNode* newnode =(ListNode*)malloc(sizeof(ListNode)); newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } //初始化 ListNode* ListInit() { ListNode*phead = BuyListNode(0); phead->next = phead; phead->prev = phead; return phead; } //销毁 void ListDestory(ListNode* phead) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { ListNode* next = cur->next; free(cur); cur = next; } free(phead); phead = NULL; } //打印 void ListPrint(ListNode* phead) { ListNode* cur = phead->next; while (cur != phead) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); } //尾插 void ListPushBack(ListNode* phead, LTDataType x) { assert(phead); ListNode* tail = phead->prev; ListNode* newnode = BuyListNode(x); tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; } //头插 void ListPushFront(ListNode* phead, LTDataType x) { assert(phead); ListNode* first = phead->next; ListNode* newnode = BuyListNode(x); newnode->next = first; first->prev = newnode; phead->next = newnode; newnode->prev = phead; } //头删 void ListPopFront(ListNode* phead) { assert(phead); assert(phead->next != phead); ListNode* first = phead->next; ListNode* second = first->next; phead->next = second; second->prev = phead; free(first); first = NULL; } //尾删 void ListPopBack(ListNode* phead) { assert(phead); assert(phead->next != phead); ListNode* tail = phead->prev; ListNode* prev = tail->prev; prev->next = phead; phead->prev = prev; free(tail); tail = NULL; } ListNode* ListFind(ListNode* phead, LTDataType x) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } //在pos位置之前插入x void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* prev = pos->prev; ListNode* newnode = BuyListNode(x); prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; } //删除pos位置的值 void ListErase(ListNode* pos) { assert(pos); ListNode* prev = pos->prev; ListNode* next = pos->next; prev->next = next; next->prev = prev; free(pos); }
Test.c
#include "List.h" void TestList1() { ListNode* plist = ListInit(); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPrint(plist); ListPushFront(plist, 0); ListPushFront(plist, -1); ListPrint(plist); ListPopFront(plist); ListPopFront(plist); ListPopFront(plist); ListPrint(plist); ListPopBack(plist); ListPrint(plist); } void TestList2() { ListNode* plist = ListInit(); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPrint(plist); ListNode* pos = ListFind(plist, 3); if (pos) { pos->data *= 10; printf("找到了,并且*10\n"); } else { printf("没找到\n"); } ListPrint(plist); ListInsert(pos, 300); ListPrint(plist); ListErase(pos); ListPrint(plist); } int main() { TestList2(); return 0; }
以上就是关于“C语言带头双向循环链表怎么实现”这篇文章的内容,相信大家都有了一定的了解,希望小编分享的内容对大家有帮助,若想了解更多相关的知识内容,请关注亿速云行业资讯频道。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。