C语言实现双向链表

这篇具有很好参考价值的文章主要介绍了C语言实现双向链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.版本一

由于节点之间的连接变多 所以我们最好提前将前驱节点和后继节点用变量保存下来 以免等下在进行节点之间的指向时出错

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// 节点类
typedef struct Node {
	// 数据域
	int data;
	// 指针域
	struct Node* next;
	struct Node* pre;
}Node;// 别名
// 初始化链表
Node* initList() {
	Node* list = (Node*)malloc(sizeof(Node));
	list->data = 0;
	list->next = NULL;
	list->pre = NULL;
	return list;
}
// 头插法
void headInsert(int data, Node* list) {
	Node* node = (Node*)malloc(sizeof(Node));
	Node* pre = list;
	Node* next = list->next;
	node->data = data;
	pre->next = node;
	node->pre = pre;
	node->next = next;
	if (list->data != 0) {
		next->pre = node;
	}
	// 更新链表长度
	list->data++;
}
// 尾插法
void tailInsert(int data, Node* list) {
	// 为待插入节点分配内存
	Node* node = (Node*)malloc(sizeof(Node));
	// 获取待插入节点的前驱节点 前驱节点其实就是原来的尾节点
	Node* pre = list->next;
	while (pre->next) {
		pre = pre->next;
	}
	Node* next = pre->next;
	node->data = data;
	pre->next = node;
	node->pre = pre;
	node->next = next;
	// 更新链表长度
	list->data++;
}
// 删除方法
bool delete(int data, Node* list) {
	// 我们需要做的是删除指定节点值对应的第一个节点
	Node* cur = list->next;
	while (cur) {
		// 如果一旦遇到符合指定节点值的节点的话 那么就执行相关操作
		if (cur->data == data) {
			// 需要先考虑头删、尾删和中间删以及删除之后链表为空四种情况 总结之后 我们可以发现尾删和删除之后链表为空同属一种情况 都是只需要设置一条线即可 即前驱指向后继 但是其他情况需要设置两条线 即前驱指向后继 后继指向前驱
			cur->pre->next = cur->next;
			if (cur->next) {
				cur->next->pre = cur->pre;
			}
			free(cur);
			list->data--;
			return true;
		}
		cur = cur->next;
	}
	return false;
}
// 打印链表方法
void printList(Node* list) {
	Node* cur = list->next;
	while (cur) {
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
int main() {
	Node* list = initList();
	headInsert(1, list);
	headInsert(2, list);
	headInsert(3, list);
	tailInsert(4, list);
	tailInsert(5, list);
	printList(list);// 3 2 1 4 5
	if (delete(5, list) == true) {
		printf("删除成功\n");
	}
	else {
		printf("删除失败\n");
	}
	printList(list);// 2 1 4 5
}

2.版本二(mj版本的双向链表 带有虚拟头节点)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ELEMENT_NOT_FOUND -1
// 我们的设计理念就是引入一个虚拟头节点 但是不引入头节点的标识以及尾节点的标识
// 节点类
typedef struct Node {
	int data;// 数据域
	struct Node* pre;
	struct Node* next;// 指针域
}Node;
// 初始化链表
Node* initList() {
	Node* list = (Node*)malloc(sizeof(Node));
	list->data = 0;
	list->pre = NULL;
	list->next = NULL;
	return list;
}
// 索引越界的处理
void outOfBounds(int index) {
	printf("索引为%d 索引越界了\n", index);
}
// 边界检查
void rangeCheck(int index, Node* list) {
	if (index < 0 || index >= list->data)
		outOfBounds(index);
}
// 针对添加方法的边界检查
void rangeCheckForAdd(int index, Node* list) {
	if (index < 0 || index > list->data)
		outOfBounds(index);
}
// 根据指定索引获取节点
Node* node(int index, Node* list) {
	// 对参数索引进行边界检查
	rangeCheck(index, list);
	Node* cur = list->next;
	for (int i = 0; i < index; ++i) {
		cur = cur->next;
	}
	return cur;
}
// 添加方法
void add(int index, int data, Node* list) {
	// 需要分成三种情况进行分析 一种情况是中间插入 需要设置四条线 一种情况是尾插 需要设置三条线 一种情况是头插 需要设置四条线 一种情况是对空链表进行插入操作 需要设置三条线 所以我们可以分成两种情况 一种是尾插的特殊情况 一中是其他位置插入
	// 对参数索引进行边界检查
	rangeCheckForAdd(index, list);
	// 为待插入节点分配内存
	Node* cur = (Node*)malloc(sizeof(Node));
	// 获取待插入节点的前驱节点 如果是头插的话 那么就需要特殊处理了
	Node* pre = index == 0 ? list : node(index - 1, list);
	// 获取待插入节点的后继节点
	Node* next = pre->next;
	cur->data = data;
	// 四种情况都要设置三条线 
	pre->next = cur;
	cur->pre = pre;
	cur->next = next;
	if (next)
		next->pre = cur;
	// 无论执行的是哪一种情况 都需要更新链表长度
	list->data++;
}
// 删除方法
int delete(int index, Node* list) {
	// 我们需要将问题分成三种情况去讨论 一种情况是中间删除 一种情况是尾删 一种情况是头删 如果是中间删除的话 那么我们需要操作的指针有两条 分别是前驱节点的后继节点还有后继节点的前驱节点 如果是尾删的话 那么就需要操作一条 即前驱节点指向后继节点 如果是头删的话 那么需要操作两条 同中间删除一样 如果是删除之后链表为空的话 那么就归结到尾删的情况中去考虑即可 并且复用尾删的代码
	Node* cur = node(index, list);
	// 我们保存一下待删除节点的节点值
	int delete = cur->data;
	// 通过待删除节点获取到他的前驱节点以及后继节点
	Node* pre = cur->pre;
	Node* next = cur->next;
	pre->next = next;
	if (next)
		next->pre = pre;
	// 我们还要去释放一下cur的内存 同时也解决了从cur指出的两条指针
	free(cur);
	// 更新一下链表的长度
	list->data--;
	// 返回待删除节点的节点值
	return delete;
}
// 定义一个方法 用于获取指定节点值对应的位置
int indexOf(int data, Node* list) {
	Node* cur = list->next;
	for (int i = 0; i < list->data; ++i) {
		if (cur->data == data)return i;
		cur = cur->next;
	}
	// 如果上述循环没有返回值的话 那么说明没有找到指定的节点值对应的节点
	return ELEMENT_NOT_FOUND;
}
// 获取指定索引处的节点值
int get(int index, Node* list) {
	return node(index, list)->data;
}
// 重置指定位置处的节点值
int set(int index, int newData, Node* list) {
	int data = node(index, list)->data;
	node(index, list)->data = newData;
	return data;
}
// 清空方法
void clear(Node* list) {
	Node* cur = list->next;
	Node* next;
	for (int i = 0; i < list->data; ++i) {
		next = cur->next;
		free(cur);
		cur = next;
	}
	// 清空链表之后链表长度为0
	list->data = 0;
}
// 判断链表是否包含指定节点值
bool contains(int data, Node* list) {
	return indexOf(data, list) != ELEMENT_NOT_FOUND;
}
// 判断链表是否为空
bool isEmpty(Node* list) {
	return list->data == 0;
}
// 获取链表长度
int size(Node* list) {
	return list->data;
}
// 打印链表的方法
void printList(Node* list) {
	Node* cur = list->next;
	while (cur) {
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
// 定义一个主函数
int main() {
	// 创建一个链表
	Node* list = initList();
	// 头部添加 尾部添加
	add(0, 1, list);// 1
	add(0, 2, list);// 2 1
	add(0, 3, list);// 3 2 1
	add(0, 4, list);// 4 3 2 1
	add(size(list), 5, list);// 4 3 2 1 5
	// 打印链表
	printList(list);// 4 3 2 1 5
	// 头部删除 尾部删除
	delete(0, list);// 3 2 1 5
	delete(size(list) - 1, list);// 3 2 1
	// 打印链表
	printList(list);// 3 2 1
	// 获取头部元素
	printf("%d\n", get(0, list));// 3
	// 重置头部元素
	printf("%d\n", set(0, 4, list));// 3
	// 打印链表
	printList(list);// 4 2 1
	printf("%d\n", contains(4, list));// true
	printf("%d\n", isEmpty(list));// false
	// 清空链表
	clear(list);
	printf("%d\n", size(list));// 0
	return 0;
}

测试结果显示 这个代码符合预期文章来源地址https://www.toymoban.com/news/detail-795717.html

到了这里,关于C语言实现双向链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构初阶】四、线性表里的链表(带头+双向+循环 链表 -- C语言实现)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】三、 线性表里的链表(无头+单向+非循环链表 -- C语言实现)-CSDN博客  ====

    2024年02月08日
    浏览(43)
  • 算法村第一关黄铜|链表|单链表与双向链表(c语言&c++实现)

    1.理解C 语言里是如何构造出链表的 2.链表增加元素,首部、中间和尾部分别会有什么问题,该如何处理? 3.链表删除元素,首部、中间和尾部分别会有什么问题,该如何处理? 4.双向链表是如何构造的,如何实现元素的插入和删除。 链表是一种常见的数据结构,由一系列节

    2024年02月15日
    浏览(38)
  • 链接未来:深入理解链表数据结构(二.c语言实现带头双向循环链表)

    上篇文章简述讲解了链表的基本概念并且实现了无头单向不循环链表:链接未来:深入理解链表数据结构(一.c语言实现无头单向非循环链表)-CSDN博客 那今天接着给大家带来带头双向循环链表的实现 : 头文件DoubleList.h:用来基础准备(常量定义,typedef),链表表的基本框架

    2024年01月16日
    浏览(60)
  • 数据结构_链表_双向循环链表的初始化、插入、删除、修改、查询打印(基于C语言实现)

    版本: 2024年4月26日 V1.0 发布于博客园 目录 目录 双向循环链表公式 初始化双向循环链表 构建双向循环链表结点 创建一个空链表(仅头结点) 创建一个新结点 插入数据 头插 中插 尾插 删除数据 头删 中删 尾删 查询打印数据 遍历打印 测试 测试结果: 完整代码 DoubleCirLList.h

    2024年04月27日
    浏览(51)
  • 双向链表(数据结构)(C语言)

    目录 概念 带头双向循环链表的实现 前情提示 双向链表的结构体定义 双向链表的初始化 关于无头单向非循环链表无需初始化函数,顺序表、带头双向循环链表需要的思考 双向链表在pos位置之前插入x 双向链表的打印 双链表删除pos位置的结点 双向链表的尾插 关于单链表的尾

    2024年02月04日
    浏览(61)
  • C语言数据结构-双向链表

    带头链表的头结点,实际是\\\"哨兵位\\\",哨兵位节点不存储任何有效元素,只是站在这里\\\"放哨的\\\". 哨兵位的意义:遍历循环链表避免死循环. 笔者在删除,插入数据时,画好图后,也好了代码,但是在调试中多次出现 代码位置出错 ,导致写的代码的含义不符合预期. 所以说思路一定要清晰

    2024年02月04日
    浏览(48)
  • Go语言数据结构(一)双向链表

    Go语言中list容器定义在\\\"container/list\\\"包中,实现了一个双向链表。本文第一部分总结源码包中的方法,第二部分展示使用list包的常见示例用法以及刷题时的用法。 食用指南:先看第二部分的常用示例用法然后再用到时在第一部分找对应的方法。 更多内容以及其他Go常用数据结

    2024年01月19日
    浏览(38)
  • C语言双向链表的增删操作

    2024年04月24日
    浏览(42)
  • 数据结构——双向链表(C语言版)

    上一章: 数据结构——单向链表(C语言版)-CSDN博客 目录 什么是双向链表? 双向链表的节点结构 双向链表的基本操作 完整的双向链表示例 总结 什么是双向链表? 双向链表是一种常见的数据结构,它由一系列节点组成,每个节点包含两个指针:一个指向前一个节点,一个

    2024年03月26日
    浏览(52)
  • C语言双向链表的含义与链表数据操作代码详解!

    引言: 于本文中,我们将讲到C语言数据结构中的双向链表的含义,以及对于双向链表的增删查改函数。该函数相比于单向链表,反而还更加的简单。希望这篇文章可以对你有帮助,也希望同样热爱代码编程的你能给我支持,您的支持就是我最大的动力! 关于顺序表以及单链

    2024年04月17日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包