当前位置： 首页 > article >正文

《链表之美：C语言中的灵活数据结构》

article 2025/1/21 9:45:37

大家好，这里是小编的博客频道
小编的博客：就爱学编程

很高兴在CSDN这个大家庭与大家相识，希望能在这里与大家共同进步，共同收获更好的自己！！！

目录

  • 引言
  • 正文
    • 一、节点结构
    • 二、基本操作
      • 1. 创建链表
      • 2. 插入节点
      • 3. 删除节点
      • 4. 查找节点
      • 5. 修改节点数据
    • 三、应用场景
    • 四、源码
      • LT.h
      • LT.c
      • Test.c
    • 五、总结
  • 快乐的时光总是短暂，咱们下篇博文再见啦！！！不要忘了，给小编点点赞和收藏支持一下，在此非常感谢！！！

引言

在C语言中，数据结构的掌握对于高效编程至关重要。其中，双链表作为一种基础且常用的数据结构，具有独特的优势和应用场景。下面将对双链表进行详细介绍，并概述其实现方法。一起来看看吧！！！
在这里插入图片描述

那接下来就让我们开始遨游在知识的海洋！

正文

一、节点结构

在C语言中，可以使用结构体来定义一个双向链表的节点。每个节点通常包含以下三个部分：

  • 数据域：用于存储节点的数据。
  • 前驱指针（ prev ）：指向当前节点的前一个节点。
  • 后继指针（ next ）：指向当前节点的下一个节点。

下面是一个常见的定义方式：

 
typedef struct Node {
    int data;          // 数据域
    struct Node* prev; // 前驱指针
    struct Node* next; // 后继指针
} Node;

二、基本操作

1. 创建链表

创建带头双向循环链表需要先创建一个头节点，并初始化它的两个指针。初始时，头节点的前驱和后继都指向自己，表示这是一个空链表。

 
Node* createDoublyLinkedList() {
    Node* head = (Node*)malloc(sizeof(Node)); // 创建头节点
    head->prev = head;                       // 初始时头节点的前驱指向自己
    head->next = head;                       // 初始时头节点的后继也指向自己
    return head;
}

2. 插入节点

在带头双向循环链表中插入节点需要确定新节点的位置，并调整相关节点的指针。根据插入位置的不同，可以分为以下几种情况：

  • 在头部插入：将新节点作为新的头节点，并更新原头节点的前驱指针和新节点的后继指针。
  • 在中间插入：找到要插入位置的前一个节点，然后将新节点插入到该节点之后，同时更新相关节点的指针。
  • 在尾部插入：找到链表的最后一个节点，然后将新节点添加到其后，同时更新最后一个节点的后继指针和新节点的前驱指针。

以下是相应的代码示例：

 
void insertAtBeginning(Node** head_ref, int data) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->prev = NULL;
    new_node->next = *head_ref;
    if (*head_ref != NULL) {
        (*head_ref)->prev = new_node;
    }
    *head_ref = new_node;
}

void insertAfter(Node* prev_node, int data) {
    if (prev_node == NULL) {
        printf("The given previous node cannot be NULL
");
        return;
    }
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->prev = prev_node;
    new_node->next = prev_node->next;
    prev_node->next = new_node;
    if (new_node->next != NULL) {
        new_node->next->prev = new_node;
    }
}

void insertAtEnd(Node** head_ref, int data) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    Node* last = *head_ref;
    new_node->data = data;
    new_node->next = NULL;
    if (*head_ref == NULL) {
        new_node->prev = NULL;
        *head_ref = new_node;
        return;
    }
    while (last->next != NULL) {
        last = last->next;
    }
    last->next = new_node;
    new_node->prev = last;
}

3. 删除节点

删除双带头双向循环链表中的节点也需要调整相关节点的指针。根据删除节点的位置，可以分为以下几种情况：

  • 删除头节点：更新头指针为下一个节点，并将新头节点的前驱指针设为NULL。
  • 删除中间节点：找到要删除的节点，将其前一个节点的后继指针指向其后的节点，并将其后一个节点的前驱指针指向其前的节点。
  • 删除尾节点：找到倒数第二个节点，将其后继指针设为NULL，并释放尾节点的内存。

以下是相应的代码示例：

 
void delete(Node* head, Node* del) {
    if (head == del) { // 如果要删除的是头节点
        head = del->next;
        head->prev = NULL;
        free(del);
        return;
    }
    if (del->next == del) { // 如果要删除的是尾节点
        del->prev->next = NULL;
        free(del);
        return;
    }
    if (del->prev == del) { // 如果要删除的是孤立节点（没有前驱和后继）
        free(del);
        return;
    }
    del->prev->next = del->next; // 把del的前一个节点的next指针指向del的后一个节点
    del->next->prev = del->prev; // 把del的后一个节点的prev指针指向del的前一个节点
    free(del); // 释放del的内存
}

4. 查找节点

查找指定元素的节点需要从表头开始依次遍历链表中的节点，直到找到目标节点或到达链表末尾为止。

int selectElem(Node* head, int elem) {
    Node* t = head;
    int i = 1;
    while (t) {
        if (t->data == elem) {
            return i;
        }
        i++;
        t = t->next;
    }
    // 程序执行至此处，表示查找失败
    return -1;
}

5. 修改节点数据

修改带头双向循环链表中指定节点的数据需要在查找到该节点的基础上直接更改其数据域的值。

 
void amendElem(Node* p, int oldElem, int newElem) {
    Node* temp = p;
    int find = 0; // 找到要修改的目标节点标志
    while (temp) {
        if (temp->data == oldElem) {
            find = 1;
            break;
        }
        temp = temp->next;
    }
    // 成功找到，则进行更改操作
    if (find == 1) {
        temp->data = newElem;
        return;
    }
    // 查找失败，输出提示信息
    printf("链表中未找到目标元素，更改失败
");
}

三、应用场景

带头双向循环链表由于其灵活的插入和删除特性，在许多场景中都有广泛的应用，包括但不限于：

  • 浏览器历史记录：使用双向链表存储用户的导航历史记录，方便用户前进和后退浏览页面。
  • 缓存机制：在实现LRU（最近最少使用）缓存策略中非常有用，可以快速找到并移除最久未使用的项目。
  • 音乐播放器的播放列表：用来存储播放列表，允许用户轻松地在歌曲之间前后跳转。
  • 数据库管理系统：某些类型的数据库索引，如B树中的叶节点，可能使用链表来连接，以便于快速查找和遍历。
  • 图形用户界面：可以用来管理窗口堆栈，使应用程序可以轻松地在窗口之间切换。
  • 游戏开发：可以用来管理游戏对象，如敌人、子弹等，以便于快速添加和删除对象。

四、源码

LT.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType _data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

// 创建返回链表的头结点.
ListNode* ListCreate();

//创造节点
ListNode* Buy_ListNode(LTDataType x);

// 双向链表销毁
void ListDestory(ListNode* phead);

// 双向链表打印
void ListPrint(ListNode* phead);

// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x);

// 双向链表尾删
void ListPopBack(ListNode* phead);

// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x);

// 双向链表头删
void ListPopFront(ListNode* phead);

// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x);

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

LT.c

#include"LT.h"

// 创建并返回链表的头结点（哨兵位）.
ListNode* ListCreate() {
	ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
	if (phead == NULL) {
		perror("malloc fail");
		//return NULL;
		exit(-1);
	}
	phead->_data;
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
//创造节点
ListNode* Buy_ListNode(LTDataType x)
{
	ListNode* cur = (ListNode*)malloc(sizeof(ListNode));
	if (cur == NULL) {
		perror("malloc fail");
		//return NULL;
		exit(-1);
	}
	cur->next = NULL;
	cur->prev = NULL;
	cur->_data = x;

	return cur;
}

// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x) {
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead) {
		if (x == cur->_data) {
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x) {
	assert(pos);
	ListNode* cur = Buy_ListNode(x);
	pos->prev->next = cur;
	cur->prev = pos->prev;
	pos->prev = cur;
	cur->next = pos;
}

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos) {
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;            //无用，但为了保持习惯
}

// 双向链表打印
void ListPrint(ListNode* phead) {
	assert(phead);
	printf("<=head=>");
	ListNode* cur = phead->next;
	while (cur != phead) {
		printf("<=%d=>", cur->_data);
		cur = cur->next;
	}
	printf("\n");
}

// 双向链表销毁
void ListDestory(ListNode* phead) {
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead) {
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
}

// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x) {
	ListInsert(phead, x);
}

// 双向链表尾删
void ListPopBack(ListNode* phead)
{
	ListErase(phead->prev);
}

// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x) {
	ListInsert(phead->next, x);
}

// 双向链表头删
void ListPopFront(ListNode* phead) {
	ListErase(phead->next);
}

Test.c

#include"LT.h"
void test1() {

	ListNode* phead = ListCreate();
	/*ListNode* n1 = Buy_ListNode(1);
	ListNode* n2 = Buy_ListNode(2);
	ListNode* n3 = Buy_ListNode(3);
	ListNode* n4 = Buy_ListNode(4);
	ListNode* n5 = Buy_ListNode(5);*/

	
	ListInsert(phead, 1);
	ListInsert(phead, 2);
	ListInsert(phead, 3);
	ListInsert(phead, 4);
	ListInsert(phead, 5);

	ListPrint(phead);

	ListNode* pos = ListFind(phead, 2);
	if (pos != NULL) {
		ListErase(pos);
		pos = NULL;
	}
	ListPrint(phead);

	ListPushBack(phead, 2);

	ListPrint(phead);

	ListPopBack(phead);

	ListPrint(phead);

	ListPushFront(phead, 6);

	ListPrint(phead);

	ListPopFront(phead);

	ListPrint(phead);

	ListDestory(phead);
}
int main() {
	test1();
	return 0;
}

五、总结

双向链表是一种复杂但功能强大的数据结构，它提供了在两个方向上进行操作的灵活性。通过合理地使用双向链表，可以高效地解决许多实际问题。

快乐的时光总是短暂，咱们下篇博文再见啦！！！不要忘了，给小编点点赞和收藏支持一下，在此非常感谢！！！


http://www.kler.cn/a/511914.html

相关文章：

  • 【Maven】resources-plugin
  • InVideo AI技术浅析（五）：生成对抗网络
  • C# 解析 HTML 实战指南
  • [计算机网络]一． 计算机网络概论第一部分
  • 华为数据中心CE系列交换机级联M-LAG配置示例
  • Spring Web MVC综合案例
  • PostgreSql 创建稀疏索引
  • Java基础（2）
  • 语言模型的价值定位与技术突破：从信息处理到创新认知
  • 20250120 深入了解 Apache Flink 的 Checkpointing
  • Perplexity AI 周六向 TikTok 母公司字节跳动递交了一项提案
  • Linux：SystemV通信
  • 【2024 年度总结】从小白慢慢成长
  • 数据库高可用方案-04-删除策略
  • MySQL和SQL server的区别
  • DATAGerry 终端节点接口敏感信息泄露漏洞复现（CVE-2024–50967）（附脚本）
  • 基于STM32的智能门锁安防系统（开源）
  • React Context 实现全局组件注册
  • 【2024 CSDN博客之星】技术洞察类：从DeepSeek-V3的成功，看MoE混合专家网络对深度学习算法领域的影响（MoE代码级实战）
  • postgresql的用户、数据库和表
  • 内存原理：计算机存储的核心奥秘
  • Python预训练视觉和大语言模型——精彩试读
  • hive表修改字段类型没有级连导致历史分区报错
  • iOS 内购接入StoreKit2 及低与iOS 15 版本StoreKit 1 兼容方案实现
  • 【算法学习笔记】34：扩展欧几里得算法
  • nginx伪静态配置解释和Nginx 常见的配置