数据结构

2024-01-17 21:22| 来源: 网络整理| 查看: 265

一、双向循环链表

带头双向循环链表是链表中结构较为复杂的一种，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

首先，顾名思义，一个双向链表的节点中有一个数据域和两个指针域，其一个指针（next）指向后继，另一个指针(prior)指向前驱。如下图1：

图1 双向链表节点示意图

其 C 语言可描述如下：

typedef struct DuLNode{ ElemType data; struct DuLNode* prior; struct DuLNode* next; }DuLNode;

那么双向循环链表示意图可由图2表示如下：

图2 双向循环链表示意图二、代码实现双向循环链表

我们需要实现的功能有双向循环链表的头插、头删、尾插、尾删、指定位置的删除、指定位置后的插入、查找、链表打印。

直接上代码吧，需要注意的地方已在注释中说明：

#include #include typedef int Type; typedef struct Node { Type data; struct Node* next; struct Node* prev; }Node; typedef struct List { Node* header; }List; Node* creatNode(Type val) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = val; newNode->next = newNode->prev = NULL; return newNode; } void listInit(List* dl) { dl->header = creatNode(0); dl->header->next = dl->header; dl->header->prev = dl->header; } // 头插 void listPushFront(List* dl, Type val) { Node* node = creatNode(val); Node* front = dl->header->next; front->prev = node; node->prev = dl->header; node->next = front; dl->header->next = node; } // 头删 void listPopFront(List* dl) { if (dl->header->next == dl->header->prev) { //只有头节点，不删除 return; } Node* front = dl->header->next; Node* next = front->next; next->prev = dl->header; dl->header->next = next; free(front); } // 尾插 void listPushBack(List* dl, Type val) { Node* newNode = creatNode(val); Node* last = dl->header->prev; //头的prev指向尾 newNode->prev = last; last->next = newNode; newNode->next = dl->header; dl->header->prev = newNode; } // 尾删 void listPopBack(List* dl) { if (dl->header->next == dl->header->prev) { // 只有头节点，不删除 return; } Node* last = dl->header->prev; Node* prev = last->prev; prev->next = dl->header; dl->header->prev = prev; free(last); } //插入pos前 void listInsert(Node* pos, Type val) { Node* newNode = creatNode(val); Node* prev = pos->prev; prev->next = newNode; newNode->prev = prev; newNode->next = pos; pos->prev = newNode; } // 删除pos位置 void listErase(Node* pos) { if (pos->next == pos) { return; } Node* prev = pos->prev; Node* next = pos->next; prev->next = next; next->prev = prev; free(pos); } // 查找节点 Node* listFind(List dl, Type val) { if (dl.header->next == dl.header) { return NULL; } Node* cur = dl.header->next; while (cur != dl.header) { // cur 等于头了，说明遍历完了 if (cur->data == val) { return cur; } cur = cur->next; } return NULL; } // 打印 void listPrint(List*dl) { Node* cur = dl->header->next; while (dl->header != cur) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); } // 测试 int main() { List dl; listInit(&dl); listPushBack(&dl, 1); listPushBack(&dl, 2); listPushBack(&dl, 3); listPrint(&dl); listPushFront(&dl,5); listPrint(&dl); system("pause"); return 0; }

【本文地址】

公司简介

联系我们