【数据结构-C】双向循环链表基本操作及图解分析

目录

?双向链表介绍

?双向链表的基本操作及图解分析

?1.双向链表创建新的结点

?2.双向链表初始化

?3.双向链表的尾插

?4.双向链表的头插

?5.双向链表的头删

?6.双向链表的尾删

?7.查找某个结点并返回该节点地址

?8.在某结点前插入一个新的结点

?9.删除某个结点

?10.销毁双向链表

总结

?双向链表介绍

双向链表的结点：指针域1+数据域+指针域2

?指针域1：指向该结点前面一个结点

?指针域2：指向该结点后面一个结点

结构体表示结点：

typedef struct DulNode { struct DulNode *prev; struct DulNode *next; ElemType data; }DulNode; 

带头循环双向链表的头结点：当链表为空时，头结点的指针域1指向自身，头结点的指针域2指向自身。

注意?：头结点的数据域不储存数据，在初始化时可以随机给一个数，但是这个数不具有任何作用。

 ➖一条简单的带头双向循环链表

⚙物理结构：

⚙逻辑结构：

?双向链表的基本操作及图解分析

?1.双向链表创建新的结点

DulNode* BuyNewNode(ElemType data) { DulNode* newNode = (DulNode*)malloc(sizeof(DulNode)); //结点初始化 newNode->data = data; newNode->prev = NULL; newNode->next = NULL; return newNode; }

?2.双向链表初始化

初始化：创建一个头结点，使得头结点的指针域指向自己，并返回头结点的地址。

DulNode* InitList() { DulNode* newNode = BuyNewNode(0); //让该结点的指针域指向自己，作为头结点 newNode->next = newNode; newNode->prev = newNode; return newNode; }

?3.双向链表的尾插

?Step1:创建新结点，找到尾结点并保存

?Step2:将尾结点与新结点连接

?Step3:将头结点与新结点连接

void ListPushBack(DulNode* phead, ElemType data) { assert(phead); DulNode* newNode = BuyNewNode(data);//创建新结点 DulNode* tail = phead->prev;//找到尾结点 //尾结点与新结点连接 tail->next = newNode; newNode->prev = tail; //头结点与新结点连接 newNode->next = phead; phead->prev = newNode; }

?4.双向链表的头插

?Step1：找到第一个结点。

?Step2：将第一个结点与新结点连接。

?Step3：将新结点与头结点连接

void ListPushFront(DulNode* phead, ElemType data) { assert(phead); DulNode* newNode = BuyNewNode(data); DulNode* first = phead->next;//找到第一个结点 //新结点与第一个结点连接 first->prev = newNode; newNode->next = first; //新结点与头结点连接 newNode->prev = phead; phead->next = newNode; }

?5.双向链表的头删

?Step1：找到第一个结点和第二个结点

?Step2：将第二个结点与头结点连接

?Step3：释放第一个结点

注意?：当链表为空时，使用该操作会将链表销毁，所以当链表为空时使用assert()打印错误信息。

void ListPopFront(DulNode* phead) { assert(phead); assert(phead->next != phead);//当链表为空时 DulNode* first = phead->next;//记录第一个结点 DulNode* second = first->next;//记录第二个结点 //将头结点与第二个结点连接 second->prev=phead; phead->next=second; //释放第一个结点 free(first); first = NULL; }

?6.双向链表的尾删

?Step1:找到最后一个结点和倒数第二个结点

?Step2:将倒数第二个结点与头结点连接

 ?Step2:将最后一个结点释放

注意?：当链表为空时，使用该操作会将链表销毁，所以当链表为空时使用assert()打印错误信息。

void ListPopBack(DulNode* phead) { assert(phead); assert(phead->next != phead); DulNode* end = phead->prev;//记录尾结点 DulNode* prev = end->prev;//记录倒数第二个结点 //将头结点与倒数第二个结点 prev->next = phead;//尾结点的前一个结点后继尾头结点 phead->prev = prev;//头结点的前驱为尾结点的前一个结点 free(end); end = NULL; }

?7.查找某个结点并返回该节点地址

DulNode* ListFind(DulNode* phead, ElemType data) { DulNode* cur = phead->next;//定义一个遍历链表的指针 while (cur !=phead) { if (cur->data == data) { return cur; } cur = cur->next; } return NULL; }

?8.在某结点前插入一个新的结点

?Step1:找到某结点的前一个结点

?Step2：将新结点与某结点连接

?Step3：将新结点与某结点的前一个结点连接

void ListInsert(DulNode* pos, ElemType data) { assert(pos); DulNode* newNode = BuyNewNode(data); DulNode* prev = pos->prev;//记录插入位置的前一个结点 //新结点和pos结点连接 newNode->next = pos; pos->prev = newNode; //pos前一个结点和新结点连接 newNode->prev = prev; prev->next = newNode; }

?9.删除某个结点

?Step1:找到某结点的前一个结点和后一个结点

?Step2:将前一个结点和后一个结点连接

 ?Step3:释放删除结点

void ListEarst(DulNode* pos) { assert(pos); DulNode* prev = pos->prev; DulNode* next = pos->next; //将删除结点的前后结点进行连接 prev->next = next; next->prev = prev; free(pos); pos = NULL; }

?10.销毁双向链表

void ListErase(DulNode *phead) { DulNode *cur=phead->next; while(cur != phead) { DulNode *next=cur->next;//先找到下一个结点 free(cur);//释放该结点 cur=next; } }

总结

链表包括八种

?：单向带头循环链表

?：单向带头非循环链表

?：单向不带头循环链表

?：单向不带头非循环链表

?：双向带头循环链表

?：双向带头非循环链表

?：双向不带头循环链表

?：双向不带头非循环链表

?单向不带头非循环链表 一般不会单独用来存数据。实际中更多是作为其他数据结 构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多

?双向带头循环链表：
结构最复杂
，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带 来很多优势，实现反而简单了，

能力有限，有错误之处还请能够指出。谢谢大家的观看。

最后祝大家：岁岁平安，虎虎生威。