双向循环链表
上一次我们讲了单向无头非循环链表的实现,单向无头非循环链表的特点是:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构。而带头双向循环链表则恰恰与无头单向非循环链表相反,它的结构最复杂,一般用来单独存储数据。这个结构虽然复杂,但是使用单吗实现后会发现,这个结构用起来很简单。
结构示意图
带头双向循环链表在逻辑上大概就是这样的一个样子,链表的最后一个节点的后继指向的是头结点。而头结点的前驱则是指向链表的最后一个结点。所以,一个空的带头双向循环链表的逻辑结构应该是这样的:
它的前驱和后继都是指向的头结点。
实现带头双向循环链表
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int ltdatatype; // 定义链表的节点 typedef struct listnode { ltdatatype data; struct listnode* prev; struct listnode* next; }ltnode; // 创建返回链表的头结点. ltnode* listcreate(); // 双向链表销毁 void listdestory(ltnode* phead); // 双向链表打印 void listprint(ltnode* phead); // 双向链表尾插 void listpushback(ltnode* phead, ltdatatype x); // 双向链表尾删 void listpopback(ltnode* phead); // 双向链表头插 void listpushfront(ltnode* phead, ltdatatype x); // 双向链表头删 void listpopfront(ltnode* phead); // 双向链表查找 ltnode* listfind(ltnode* phead, ltdatatype x); // 双向链表在pos的前面进行插入 void listinsert(ltnode* pos, ltdatatype x); // 双向链表删除pos位置的节点 void listerase(ltnode* pos);
首先我们得定义一个结点的结构,它由前驱指针、后继指针和数据这三部分组成。
// 定义链表的节点 typedef struct listnode { ltdatatype data; struct listnode* prev; struct listnode* next; }ltnode;
定义好之后,我们要创建一个头结点。我们把创建头结点的过程也封装成一个函数,这个函数的返回值就是头结点的指针。我们在使用的时候就创建一个变量来接收这个指针。
**注意:**头结点创建的时候,它的data部分是不存数据的,它的前驱和后继都是指向它自己
ltnode* listcreate() { ltnode* head = (ltnode*)malloc(sizeof(ltnode)); head->next = head; head->prev = head; return head; } // 在main函数中是这样使用的 int main(){ ltnode* head = listcreate(); return 0; }
创建好头结点之后就可以向链表中插入数据了,首先实现尾插,就是在链表的最后一个结点后面再插入一个结点。然后就是头插法,头插法就是在头结点的后面插入一个新节点。
// 双向链表尾插 void listpushback(ltnode* phead, ltdatatype x) { assert(phead); ltnode* newnode = (ltnode*)malloc(sizeof(ltnode)); // 创建的新节点 newnode->data = x; // 将新节点插入到链表中 ltnode* prev = phead->prev; prev->next = newnode; newnode->prev = prev; newnode->next = phead; phead->prev = newnode; }
// 双向链表头插 void listpushfront(ltnode* phead, ltdatatype x) { assert(phead); // 创建新节点 ltnode* newnode = (ltnode*)malloc(sizeof(ltnode)); newnode->data = x; //将新节点插入链表 ltnode* next = phead->next; phead->next = newnode; newnode->prev = phead; newnode->next = next; next->prev = newnode; }
有插入数据就有删除数据,同样的删除数据也有两种,一个是头删一个是尾删。头删就是将头结点的next指向的那个结点删除。尾删,就是将最后一个节点删掉。带头双向循环链表,在我们尾删的时候就很方便。因为头结点的前驱指向的节点就是链表的最后一个节点,就不需要我们再遍历链表去找最后一个节点的地址。
// 双向链表头删 void listpopfront(ltnode* phead) { assert(phead); assert(phead->next != phead); // 定义一个临时变量来保存我们要删掉的节点的位置 ltnode* popnode = phead->next; // 将要删除节点的链都断掉 ltnode* next = popnode->next; phead->next = popnode->next; next->prev = phead; // free掉那个节点 free(popnode); popnode = null; }
// 双向链表尾删 void listpopback(ltnode* phead) { assert(phead); assert(phead->prev != phead); ltnode* popnode = phead->prev; ltnode* prev = popnode->prev; prev->next = phead; phead->prev = prev; free(popnode); popnode = null; }
在实现了增加和删除节点之后,我们就实现查找结点。方法也是遍历整个链表,如果有一个节点的data的值和x相同就返回这个节点的地址。如果没找到就返回空。
// 双向链表查找 ltnode* listfind(ltnode* phead, ltdatatype x) { if (phead->next == phead) { return null; } ltnode* find = phead->next; while (find != phead) { if (find->data == x) { return find; } find = find->next; } return null; }
实现随机插入数据,这里的随机插入的意思是,我们把新节点插入到我们指定的节点的后面一个或前面一个。这个节点可以是在链表的任何一个地方。我们这个函数会传入一个节点的地址,通过那个地址可以找到要出入的那个节点,把新节点连接到那个节点后面就可以了
// 双向链表删除pos位置的节点 void listerase(ltnode* pos) { assert(pos); ltnode* prev = pos->prev; ltnode* next = pos->next; prev->next = next; next->prev = prev; free(pos); pos = null; }
打印双向循环链表,也是通过遍历链表来打印
// 双向链表打印 void listprint(ltnode* phead) { assert(phead); ltnode* tail = phead->next; while (tail != phead) { printf("%d->", tail->data); tail = tail->next; } }
在我们使用完链表后,要记得销毁链表,防止内存泄漏
// 双向链表销毁 void listdestory(ltnode* phead) { assert(phead); ltnode* tail = phead->next; while (tail != phead) { ltnode* tmp = tail->next; free(tail); tail = tmp; } free(phead); phead = null; }
以上就是c/c++开发分享C语言实现带头双向环形链表的全部内容,希望对大家的学习有所帮助,也希望大家多多支持<计算机技术网(www.ctvol.com)!!>。
需要了解更多c/c++开发分享C语言实现带头双向环形链表,都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)!
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/965394.html