C语言带头双向循环链表怎么实现(c语言,开发技术)

带头双向循环链表的结构

实际上，单链表也存在一个比较大的缺陷：

1.不能从后往前遍历

2.无法找到前驱

除了单链表之外，我们自然还有双向链表，我们要说的就是带头双向循环链表，简单理解为：带头结点的，有两个方向的。循环的。结构图如下：

结构虽然比较复杂，但是极大方便我们找结点，比如可以直接找到尾结点，然后再进入相关的操作。实际代码的操作将会比单链表简单，极为方便，这里不做过多说明，直接上手代码

代码操作

我们直奔主题，进入代码实现的操作，之前的操作如果理解了，那我相信这个对于你来说肯定是不难的。下面直接给出源码：

List.h

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<assert.h>#include<stdbool.h>typedefintLTDataType;//带头双向循环--最优链表结构，在任意位置插入删除数据都是O（1）typedefstructlistNode{ structListNode*next; structListNode*prev; LTDataTypedata;}ListNode;//初始化ListNode*ListInit();//销毁voidListDestory(ListNode*phead);//打印voidListPrint(ListNode*phead);//尾插voidListPushBack(ListNode*phead,LTDataTypex);//头插voidListPushFront(ListNode*phead,LTDataTypex);//头删voidListPopFront(ListNode*phead);//尾删voidListPopBack(ListNode*phead);ListNode*ListFind(ListNode*phead,LTDataTypex);//在pos位置之前插入xvoidListInsert(ListNode*pos,LTDataTypex);//删除pos位置的值voidListErase(ListNode*pos);

List.c

#include"List.h"//开辟一个新结点ListNode*BuyListNode(LTDataTypex){ ListNode*newnode=(ListNode*)malloc(sizeof(ListNode)); newnode->data=x; newnode->next=NULL; newnode->prev=NULL; returnnewnode;}//初始化ListNode*ListInit(){ ListNode*phead=BuyListNode(0); phead->next=phead; phead->prev=phead; returnphead;}//销毁voidListDestory(ListNode*phead){ assert(phead); ListNode*cur=phead->next; while(cur!=phead) { ListNode*next=cur->next; free(cur); cur=next; } free(phead); phead=NULL;}//打印voidListPrint(ListNode*phead){ ListNode*cur=phead->next; while(cur!=phead) { printf("%d",cur->data); cur=cur->next; } printf("\n");}//尾插voidListPushBack(ListNode*phead,LTDataTypex){ assert(phead); ListNode*tail=phead->prev; ListNode*newnode=BuyListNode(x); tail->next=newnode; newnode->prev=tail; newnode->next=phead; phead->prev=newnode;}//头插voidListPushFront(ListNode*phead,LTDataTypex){ assert(phead); ListNode*first=phead->next; ListNode*newnode=BuyListNode(x); newnode->next=first; first->prev=newnode; phead->next=newnode; newnode->prev=phead;}//头删voidListPopFront(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;}//尾删voidListPopBack(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,LTDataTypex){ assert(phead); ListNode*cur=phead->next; while(cur!=phead) { if(cur->data==x) { returncur; } cur=cur->next; } returnNULL;}//在pos位置之前插入xvoidListInsert(ListNode*pos,LTDataTypex){ assert(pos); ListNode*prev=pos->prev; ListNode*newnode=BuyListNode(x); prev->next=newnode; newnode->prev=prev; newnode->next=pos; pos->prev=newnode;}//删除pos位置的值voidListErase(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"voidTestList1(){ 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);}voidTestList2(){ 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);}intmain(){ TestList2(); return0;}