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

数据结构——双向链表（带头、循环）

article 2025/1/20 21:43:08

1、双链表

        双链表也是链表的一种，双链表的每个数据节点中都有两个指针，分别指向前驱节点和后继结点

数据节点如下图所示： 

 2、双向带头循环链表

         带头双向循环链表是链表中带头（哨兵位）、双向、循环三种属性的结合体

（1）带头（哨兵位）：哨兵位只负责存储第一个具有有效数据的节点，本身不存放数据，该处因为为双向循环链表，代表也可访问该链表的尾节点；

（2）双向：每个节点不仅能访问该节点的后一个节点，同时也可访问本节点的前一个节点；

（3）循环：第一个节点的pre指向尾节点；

3、操作

3.1 结构体声明

typedef int elementType;
typedef struct DLink_List_Node {
    struct DLink_List_Node* pre;  //指向上一个节点指针
    elementType val;  //存储节点元素
    struct DLink_List_Node* next;  //指向下一个节点指针
}DLK;

3.2 初始化链表

        链表为带头双向循环练表，因为存在哨兵位，所以在插入数据之前应给链表安排一个哨兵位，并对哨兵位进行初始化 

        在对哨兵位进行初始化时同时也要注意该链表的结构为双向循环链表，在只有哨兵位的情况下，哨兵位的next与pre都指向自己 

//辅助函数：创建新节点
DLK* create_dnode() {
    DLK* newnode = (DLK*)malloc(sizeof(DLK));
    if (newnode == NULL) {
        printf("内存申请失败！\n");
        return NULL;
    }
    memset(newnode, 0, sizeof(DLK));
    return newnode;
}

//链表初始化，初始化一个哨兵位（不包含元素）
DLK* create_dlink() {
    //创建新节点
    DLK* newnode = create_dnode();
    newnode->pre = newnode;
    newnode->next = newnode;
    printf("初始化成功！\n");
    return newnode;
}

3.3 插入

3.3.1 头插

        因为该链表存在哨兵位，故在进行头插时需要插入至头节点（哨兵位）之后         

void head_Insert(DLK* DList, elementType value) {
    //(1)创建新节点
    DLK* newnode = create_dnode();
    //(2)存储节点元素
    newnode->val = value;
    //(3)插入
    newnode->next = DList->next;
    DList->next->pre = newnode;
    newnode->pre = DList;
    DList->next = newnode;
    printf("头插成功！\n");
}

3.3.2 中间插

//链表的中间插，在指定元素的后边插入元素

void mid_insert(DLK* temp, elementType newvalue) {
    //(1)创建新节点
    DLK* newnode = create_dnode();
    //(2)存储节点元素
    newnode->val = newvalue;
    //(3)插入
    newnode->next = temp->next;
    temp->next->pre = newnode;
    temp->next = newnode;
    newnode->pre = temp;
    printf("插入成功！\n");
}

3.3.3 尾插

void tail_insert(DLK* DList, elementType value) {
    assert(DList);
    //(1)创建新节点
    DLK* newnode = create_dnode();
    //(2)存储节点元素
    newnode->val = value;
    //(3)插入
    newnode->pre = DList->pre;  //DList->pre：原链表的最后一个节点
    DList->pre->next = newnode;
    DList->pre = newnode;
    newnode->next = DList;
    printf("尾插成功！\n");
}

3.4 删除 

3.4.1 头删

        同样的带头双向循环链表在进行头删时只需要删除头节点（哨兵位）后的节点即可

void head_delete(DLK* DList) {
    assert(DList);
    //(1)保存头节点（哨兵位的下一个元素节点）
    DLK* temp = DList->next;  
    //(2)将哨兵位与头节点的下一个元素节点相连
    DList->next = temp->next;
    temp->next->pre = DList;
    //(3)释放头节点
    free(temp);
    printf("头删成功！\n");
}

3.4.2 中间删

//思路：先查找要删除的元素位置，在进行删除操作
void middle_delete(DLK* temp) {  //temp：要删除的元素节点
    temp->pre->next = temp->next;  //temp->pre：要删除的元素节点的前一个元素
    temp->next->pre = temp->pre;
    free(temp);
    printf("删除成功！\n");
}

3.4.3 尾删

 void tail_delete(DLK* DList) {
    assert(DList);
    //(1)保存尾节点（哨兵位的上一个元素节点）
    DLK* temp = DList->pre;
    //(2)将哨兵位与尾节点的上一个元素节点相连
    DList->pre = temp->pre;
    temp->pre->next = DList;
    //(3)释放尾节点
    free(temp);
    printf("尾删成功！\n");
}

3.5 链表销毁

 //思路：遍历节点，一个一个释放，最后修改DList=NULL
void destroy(DLK** DList) {
    DLK* temp = (*DList)->next;  //->的优先级高，所以要用()
    while (temp != *DList) {
        DLK* ptr = temp->next;  //保存下一个元素节点
        free(temp);
        temp = ptr;
    }
    free(*DList);  //释放哨兵位
    *DList = NULL;  
}

4、完整代码

4.1 02双向链表.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <Windows.h>
#include <stdlib.h>
#include <memory.h> 
#include <assert.h>
//双向链表
	//逻辑结构：线性结构
	//存储结构：链式存储
	//双向、带头、循环链表
typedef int elementType;
typedef struct DLink_List_Node {
	struct DLink_List_Node* pre;  //指向上一个节点指针
	elementType val;  //存储节点元素
	struct DLink_List_Node* next;  //指向下一个节点指针
}DLK;

void print_menu();
DLK* create_dnode();
DLK* create_dlink();
void head_Insert(DLK* DList, elementType value);
void print_dlink(DLK* DList);
void tail_insert(DLK* DList, elementType value);
void head_delete(DLK* DList);
void tail_delete(DLK* DList);
DLK* find_item(DLK* DList, elementType value);
void middle_delete(DLK* temp);
void mid_insert(DLK* temp, elementType newvalue);
void edit_dlink(DLK* DList, elementType value, elementType newvalue);
void destroy(DLK** DList);

void fn4();

4.2 main.c

#include "02双向链表.h"
int main() {
	fn4();
	return 0;
}

4.3 02双向链表.c

#include "02双向链表.h"
void fn4() {
	print_menu();
	int order = 0;
	DLK* DList = NULL;  //存储双链表的哨兵位
	elementType value = 0;
	DLK* temp = NULL;
	elementType newvalue = 0;
	while (1) {
		printf("请输入操作指令：");
		scanf("%d", &order);
		switch (order) {
			case 1:  //链表初始化，初始化一个哨兵位（不包含元素）
				DList = create_dlink();
				break;
			case 2:  //打印链表，遍历
				print_dlink(DList);
				break;
			case 3:  //链表头插
				printf("请输入要插入的元素：");
				scanf(" %d", &value);
				head_Insert(DList, value);
				break;
			case 4:  //链表尾插
				printf("请输入要尾插的元素：");
				scanf(" %d", &value);
				tail_insert(DList, value);
				break;
			case 5:  //链表头删，不是删除哨兵位，而是删除哨兵位的下一个元素节点
				head_delete(DList);
				break;
			case 6:  //链表尾删
				tail_delete(DList);
				break;
			case 7:  //链表的查找
				  //思路：找到了，返回当前元素节点的指针；找不到，返回NULL
				printf("请输入要查找的元素：");
				scanf(" %d", &value);
				temp = find_item(DList, value);
				if (temp == NULL) {
					printf("没有此元素！\n");
				}else {
					printf("找到了，该元素值为：%d\n", temp->val);
				}
				break;
			case 8:  //链表的中间删，至少要3个元素
				  //思路：先查找要删除的元素位置，在进行删除操作
				printf("请输入要删除的元素：");
				scanf(" %d", &value);
				temp = find_item(DList, value);
				if (temp == NULL) {
					printf("没有此元素，无法删除！\n");
				}else {
					middle_delete(temp);
				}
				break;
			case 9:  //链表的中间插，在指定元素的后边插入元素
				//要求：至少有1个元素
				printf("请输入要插入的元素：");
				scanf(" %d", &newvalue);
				printf("请输入要在哪个元素的后边插入：");
				scanf(" %d", &value);
				temp = find_item(DList, value);
				if (temp == NULL) {
					printf("没有此元素，无法插入！\n");
				}
				else {
					mid_insert(temp, newvalue);
				}
				break;
			case 10:  //元素修改，把目标元素修改成指定元素
				/*destroy(&LinkNode);*/
				printf("请输入要修改的元素：");
				scanf(" %d", &value);
				printf("请输入修改后的值：");
				scanf(" %d", &newvalue);
				edit_dlink(DList, value, newvalue);
				break;
			case 11:  //链表销毁
				destroy(&DList);
				break;
			case 12:  //退出
				return;
			default:
				printf("输入错误，请重新输入！\n");
		}
	}
}
//菜单
void print_menu() {
	system("cls");  //屏幕清空
	printf("操作指令说明：\n");
	printf("1：链表初始化\n2：打印链表\n");
	printf("3：链表头插\n4：链表尾插\n");
	printf("5：链表头删\n6：链表尾删\n");
	printf("7：链表的查找\n8：链表的中间删\n");
	printf("9：链表的中间插\n10：元素修改\n");
	printf("11：链表销毁\n12：退出\n");
	printf("************************\n");
}

//辅助函数：创建新节点
DLK* create_dnode() {
	DLK* newnode = (DLK*)malloc(sizeof(DLK));
	if (newnode == NULL) {
		printf("内存申请失败！\n");
		return NULL;
	}
	memset(newnode, 0, sizeof(DLK));
	return newnode;
}

//链表初始化，初始化一个哨兵位（不包含元素）
DLK* create_dlink() {
	//创建新节点
	DLK* newnode = create_dnode();
	newnode->pre = newnode;
	newnode->next = newnode;
	printf("初始化成功！\n");
	return newnode;
}

//链表头插
void head_Insert(DLK* DList, elementType value) {
	//(1)创建新节点
	DLK* newnode = create_dnode();
	//(2)存储节点元素
	newnode->val = value;
	//(3)插入
	newnode->next = DList->next;
	DList->next->pre = newnode;
	newnode->pre = DList;
	DList->next = newnode;
	printf("头插成功！\n");
}

//打印链表，遍历
void print_dlink(DLK* DList) {
	assert(DList);
	DLK* temp = DList->next;  //存储当前节点（哨兵位的下一个）
	while (temp != DList) {
		printf("%d ", temp->val);
		temp = temp->next;
	}
	printf("\n");
}

//链表尾插
void tail_insert(DLK* DList, elementType value) {
	assert(DList);
	//(1)创建新节点
	DLK* newnode = create_dnode();
	//(2)存储节点元素
	newnode->val = value;
	//(3)插入
	newnode->pre = DList->pre;
	DList->pre->next = newnode;
	DList->pre = newnode;
	newnode->next = DList;
	printf("尾插成功！\n");
}

//链表头删，不是删除哨兵位，而是删除哨兵位的下一个元素节点
void head_delete(DLK* DList) {
	assert(DList);
	//(1)保存头节点（哨兵位的下一个元素节点）
	DLK* temp = DList->next;  
	//(2)将哨兵位与头节点的下一个元素节点相连
	DList->next = temp->next;
	temp->next->pre = DList;
	//(3)释放头节点
	free(temp);
	printf("头删成功！\n");
}

//链表尾删
void tail_delete(DLK* DList) {
	assert(DList);
	//(1)保存尾节点（哨兵位的上一个元素节点）
	DLK* temp = DList->pre;
	//(2)将哨兵位与尾节点的上一个元素节点相连
	DList->pre = temp->pre;
	temp->pre->next = DList;
	//(3)释放尾节点
	free(temp);
	printf("尾删成功！\n");
}

//链表的查找
//思路：找到了，返回当前元素节点的指针；找不到，返回NULL
DLK* find_item(DLK* DList, elementType value) {
	assert(DList);
	//遍历链表元素，判断是否是目标元素
	DLK* temp = DList->next;
	while (temp != DList) {
		if (temp->val == value) {
			return temp;
		}
		temp = temp->next;
	}
	return NULL;
}

//链表的中间删，至少要3个元素
//思路：先查找要删除的元素位置，在进行删除操作
void middle_delete(DLK* temp) {
	temp->pre->next = temp->next;
	temp->next->pre = temp->pre;
	free(temp);
	printf("删除成功！\n");
}

//链表的中间插，在指定元素的后边插入元素
void mid_insert(DLK* temp, elementType newvalue) {
	//(1)创建新节点
	DLK* newnode = create_dnode();
	//(2)存储节点元素
	newnode->val = newvalue;
	//(3)插入
	newnode->next = temp->next;
	temp->next->pre = newnode;
	temp->next = newnode;
	newnode->pre = temp;
	printf("插入成功！\n");
}

//元素修改，把目标元素修改成指定元素
void edit_dlink(DLK* DList, elementType value, elementType newvalue) {
	assert(DList);
	//查找value元素所在的位置
	DLK* temp = find_item(DList, value);
	if (temp == NULL) {
		printf("没有此元素，无法修改！\n");
		return;
	}else {
		temp->val = newvalue;
		printf("修改成功！\n");
	}
}

//链表销毁
//思路：遍历节点，一个一个释放，最后修改DList=NULL
void destroy(DLK** DList) {
	DLK* temp = (*DList)->next;  //->的优先级高，所以要用()
	while (temp != *DList) {
		DLK* ptr = temp->next;  //保存下一个元素节点
		free(temp);
		temp = ptr;
	}
	free(*DList);  //释放哨兵位
	*DList = NULL;  
}

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

相关文章：

  • 循环队列（C语言）
  • C语言之整数转换英文表示
  • 【QT】： 初识 QWidget 控件 | QWidget 核心属性（API） | qrc 文件
  • redis-排查命中率降低问题
  • 密钥轮换时，老数据该如何处理
  • [创业之路-254]：《华为数字化转型之道》-1-华为是一个由客户需求牵引、高度数字化、高度智能化、由无数个闭环流程组成的价值创造、评估、分配系统。
  • Restormer: Efficient Transformer for High-Resolution Image Restoration解读
  • 森林网络部署，工业4G路由器实现林区组网远程监控
  • STM32 物联网智能家居 (四) 设备子系统之分层框架
  • 聊一聊如何适应AI时代
  • Android 导出CSV文件乱码问题处理
  • 【数据结构】线性表-单链表
  • macOS Sequoia 15.3 beta3（24D5055b）发布，附黑、白苹果镜像下载地址
  • Spring Boot 集成MyBatis-Plus
  • 【报错解决】Sql server 2022连接数据库时显示证书链是由不受信任的颁发机构颁发的
  • 【SSH端口转发：实现安全的远程端口映射】
  • C/C++内存管理（超详解）
  • 鸿蒙MVVM开发模式
  • 使用Flask和Pydantic实现参数验证
  • 【25考研】也很难！清华大学计算机考研复试难度分析！
  • Linux软件包管理器yum
  • 全面解析计算机网络：从局域网基础到以太网交换机！！！
  • Cursor的composer和chat的区别
  • leetcode——接雨水（java）
  • API接口技术推动电商数据处理的自动化
  • 2025.1.18——七、[GYCTF2020]Ezsqli 1