亲宝软件园·资讯

展开

C语言带头双向环形链表

aiyubaobei 人气:0

双向循环链表

上一次我们讲了单向无头非循环链表的实现,单向无头非循环链表的特点是:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构。而带头双向循环链表则恰恰与无头单向非循环链表相反,它的结构最复杂,一般用来单独存储数据。这个结构虽然复杂,但是使用单吗实现后会发现,这个结构用起来很简单。

结构示意图

带头双向循环链表在逻辑上大概就是这样的一个样子,链表的最后一个节点的后继指向的是头结点。而头结点的前驱则是指向链表的最后一个结点。所以,一个空的带头双向循环链表的逻辑结构应该是这样的:

它的前驱和后继都是指向的头结点。

实现带头双向循环链表

#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;
}

加载全部内容

相关教程
猜你喜欢
用户评论