数据结构—C语言实现双向链表

目录

1.双向带头循环链表

2.自定义头文件：

3.List.cpp 文件

 3.1 newnode()函数讲解

3.2 init() 函数 初始化

3.3 pushback()函数 尾插

3.4 pushfront()函数 头插

3.5 popback() 尾删

3.6 popfront() 函数 头删

3.7 insert()函数 在pos之后插入

3.8 popback()函数 删除

3.9 find() 函数 查找

3.10 print()函数 打印

4.test.cpp 文件

1.双向带头循环链表

结构：

 

2.自定义头文件：

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stdlib.h>
#include<string>
using namespace std;


typedef int type;

struct List
{
	type val;
	struct List* pre;
	struct List* next;
};

typedef struct List List;

void init(List** st);
List* newnode(type x);
void pushback(List* st, type x);
void print(List* st);
void pushfront(List* st, type x);
void popback(List* st);
void popfront(List* st);
void insert(List* pos, type x);
void erase(List* pos);
List* find(List* st, type x);
void destory(List* st);
void menu();

双向链表中的结点具有pre和next指针，分别连向上一个结点和下一个结点，val用来存储值。

3.List.cpp 文件

代码：

#include"Sqlist.h"


void menu()
{
	printf("******************************\n");
	printf("***1.init        2.pushback***\n");
	printf("***3.pushfront      4.print***\n");
	printf("***5.popback     6.popfront***\n");
	printf("***7.insert         8.erase***\n");
	printf("***9.destory         0.exit***\n");
	printf("******************************\n");
}

void init(List** st)
{
	*st = newnode(-1);
}
List* newnode(type x)
{
	List* nnee = (List*)malloc(sizeof(List));

	if (nnee == NULL)
	{
		perror("malloc");
		exit(0);
	}

	nnee->val = x;
	nnee->next = nnee->pre = nnee;

	return nnee;
}
void pushback(List* st, type x)
{
	if (st == NULL)
	{
		printf("st is NULL\n");
		return;
	}

	List* nnee = newnode(x);

	nnee->next = st;
	nnee->pre = st->pre;
	st->pre->next = nnee;
	st->pre = nnee;


}


void print(List* st)
{
	List* cur = st->next;

	while (cur != st)
	{
		cout << cur->val << ' ';
		cur = cur->next;
	}
	cout << endl;
	return;
}


void pushfront(List* st, type x)
{
	if (st == NULL)
	{
		printf("st is NULL\n");
		return;
	}

	List* nnee = newnode(x);

	nnee->next = st->next;
	nnee->pre = st;
	st->next->pre = nnee;
	st->next = nnee;

}


void popback(List* st)
{
	if (st == NULL)
	{
		printf("st is NULL\n");
		return;
	}
	if (st->next == st)
	{
		printf("st is empty\n");
		return;
	}

	List* cur = st->pre;
	cur->pre->next = st;
	st->pre = cur->pre;

	free(cur);
	cur = NULL;

}
void popfront(List* st)
{

	if (st == NULL)
	{
		printf("st is NULL\n");
		return;
	}
	if (st->next == st)
	{
		printf("st is empty\n");
		return;
	}

	List* del = st->next;

	st->next = del->next;
	del->next->pre = st;
	free(del);
	del = NULL;

}


void insert(List* pos, type x)//之后
{
	if (pos == NULL)
	{
		printf("NULL\n");
		return;
	}
	List* nnee = newnode(x);

	nnee->next = pos->next;
	nnee->pre = pos;

	pos->next->pre = nnee;
	pos->next = nnee;
}
void erase(List* pos)
{
	if (pos == NULL)
	{
		printf("pos is NULL\n");
		return;
	}

	pos->pre->next = pos->next;
	pos->next->pre = pos->pre;
	free(pos);
	pos = NULL;
}
List* find(List* st, type x)
{
	List* cur = st->next;
	while (cur != st)
	{
		if (cur->val == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

void destory(List* st)
{
	if (st == NULL)
	{
		printf("st is NULL\n");
		return;
	}

	List* cur = st->next;

	while (cur != st)
	{
		List* ne = cur->next;
		free(cur);
		cur = ne;
	}

	free(st);
	st = NULL;
	cur = NULL;

}

 

 3.1 newnode()函数讲解

代码：

List* newnode(type x)
{
	List* nnee = (List*)malloc(sizeof(List));

	if (nnee == NULL)
	{
		perror("malloc");
		exit(0);
	}

	nnee->val = x;
	nnee->next = nnee->pre = nnee;

	return nnee;
}

(1).使用malloc函数开辟一块空间，赋给nnee。

(2).再判断是否开辟成功。开辟成功后，将x赋值给nnee的val，并且把nnee的两个指针域都赋值为自己。最后返回该结点。

3.2 init() 函数 初始化

void init(List** st)
{
	*st = newnode(-1);
}

(1).由于我们创建的是带头循环链表，所以初始化要将链表的最开始创建一个头结点。

3.3 pushback()函数 尾插

void pushback(List* st, type x)
{
	if (st == NULL)
	{
		printf("st is NULL\n");
		return;
	}

	List* nnee = newnode(x);

	nnee->next = st;
	nnee->pre = st->pre;
	st->pre->next = nnee;
	st->pre = nnee;
}

(1).先判断链表的地址是否为空。

(2).创建一个新结点。

(3).将新结点的next指针指向头结点，再将新结点的pre指针指向st的pre。

再将头结点的pre的next(链表最后一个结点)指向新结点，再将头结点的pre指向新结点。

3.4 pushfront()函数 头插

void pushfront(List* st, type x)
{
	if (st == NULL)
	{
		printf("st is NULL\n");
		return;
	}

	List* nnee = newnode(x);

	nnee->next = st->next;
	nnee->pre = st;
	st->next->pre = nnee;
	st->next = nnee;

}

(1).创建新结点。

(2).将新结点的next指向头结点的next，再将新结点的pre指向头结点。

(3).再将头结点的next的pre指向新结点。头结点的next指向新结点。

3.5 popback() 尾删

void popback(List* st)
{
	if (st == NULL)
	{
		printf("st is NULL\n");
		return;
	}
	if (st->next == st)
	{
		printf("st is empty\n");
		return;
	}

	List* cur = st->pre;
	cur->pre->next = st;
	st->pre = cur->pre;

	free(cur);
	cur = NULL;

}

(1).首先判断链表是否有头结点，还要判断链表是否已经为空，为空则 st->next == st，头结点自己指向自己时

(2).创建一个指针cur，令cur指向链表最后一个结点，再令最后一个节点的pre(倒数第二个结点)的next指向头结点，再令头节点的pre指向cur的pre(倒数第二个指针)。

3.6 popfront() 函数 头删

void popfront(List* st)
{

	if (st == NULL)
	{
		printf("st is NULL\n");
		return;
	}
	if (st->next == st)
	{
		printf("st is empty\n");
		return;
	}

	List* del = st->next;

	st->next = del->next;
	del->next->pre = st;
	free(del);
	del = NULL;

}

(1).首先判断链表是否有头结点，还要判断链表是否已经为空，为空则 st->next == st，头结点自己指向自己时

(2).创建一个指针del，令del指向头结点的next(头结点的下一个结点)，再将头结点的next指向del的next，再将del的next的pre指向头结点。

3.7 insert()函数 在pos之后插入

void insert(List* pos, type x)//之后
{
	if (pos == NULL)
	{
		printf("NULL\n");
		return;
	}
	List* nnee = newnode(x);

	nnee->next = pos->next;
	nnee->pre = pos;

	pos->next->pre = nnee;
	pos->next = nnee;
}

 (1).创建一个新结点，令新结点的next指向pos的next。再将新结点的pre指向pos。

(2).再将pos的next的pre(pos下一个结点的pre指针)指向新结点；pos的next指向新结点。

 

3.8 popback()函数 删除

void erase(List* pos)
{
	if (pos == NULL)
	{
		printf("pos is NULL\n");
		return;
	}

	pos->pre->next = pos->next;
	pos->next->pre = pos->pre;
	free(pos);
	pos = NULL;
}

(1).将pos的pre的next(pos的前一个节点的next指针)指向pos的next(pos的下一个节点)。

(2).再将pos的next的pre(pos的下一个节点的pre指针)指向pos的pre(pos的前一个指针) 

 

 

3.9 find() 函数 查找

List* find(List* st, type x)
{
	List* cur = st->next;
	while (cur != st)
	{
		if (cur->val == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

(1).直接遍历链表即可，当遇到当前节点的val与x相同时，直接返回地址。

(2).若遍历完后还没有找到，则最后返回空。

3.10 print()函数 打印

void print(List* st)
{
	List* cur = st->next;

	while (cur != st)
	{
		cout << cur->val << ' ';
		cur = cur->next;
	}
	cout << endl;
	return;
}

(1).直接遍历链表即可，依次打印节点的每个值。

4.test.cpp 文件

代码：

#include"Sqlist.h"


int main()
{
	List* head;
	List* pos=NULL;
	type x;
	int op;
	int n;
	type y;
	init(&head);
	do
	{
		menu();
		printf("input optio\n");
		cin >> op;

		switch (op)
		{
		case 1:
			init(&head);
			break;
		case 2:
			printf("input you want push number\n");
			cin >> n;
			for (int i = 0; i < n; i++)
			{
				cin >> x;
				pushback(head, x);
			}
			break;
		case 3:
			printf("input you want push number\n");
			cin >> n;
			for (int i = 0; i < n; i++)
			{
				cin >> x;
				pushfront(head, x);
			}
			break;
		case 4:
			print(head);
			break;
		case 5:
			popback(head);
			break;
		case 6:
			popfront(head);
			break;
		case 7:
			printf("input you pos and val\n");
			cin >> y >> x;
			pos = find(head,y);
			if (pos == NULL)
			{
				printf("pos is not save\n");
			}
			else
			{
				insert(pos, x);
			}
			break;
		case 8:
			printf("input you pos \n");
			cin >> y;
			pos = find(head, y);
			if (pos == NULL)
			{
				printf("pos is not save\n");
			}
			else
			{
				erase(pos);
			}
			break;
		case 9:
			destory(head);
			break;
		case 0:
			break;


		default:
			printf("piease input correct option\n");
			break;
		}
	} while (op);

}

完. 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/587079.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【JS篇之】异常

【JS篇之】异常

前言&#xff1a;在代码编写过程中&#xff0c;最常遇到的就是程序异常。其实异常并非坏事&#xff0c;它可以让开发人员及时发现、定位到错误&#xff0c;提醒我们做正确的事情&#xff0c;甚至在某些时候&#xff0c;我们还会手动抛出异常。 1.异常的分类 在JS中&#xff0…
阅读更多...
Linux - nohup 后台启动命令

Linux - nohup 后台启动命令

目录 1. nohup启动 2. nohup与&&#xff0c;后台运行 3. nohup与>&#xff0c;日志重定向 4. nohup后台启动-综合使用(推荐) 5. 文件描述符-0 1 2 6. 知识扩展 6.1 不停止服务&#xff0c;直接清空nohup.out 6.2 只记录警告级别比较高的日志 6.3 不想输出日志 …
阅读更多...
c#word文档:1.创建空白Word文档及保存/2.添加页内容...

c#word文档:1.创建空白Word文档及保存/2.添加页内容...

---创建空白Word文档 --- &#xff08;1&#xff09;创建一个名为OfficeOperator的类库项目。引用操作Word的.NET类库 &#xff08;2&#xff09;定义用于操作Word的类WordOperator1。添加引用Microsoft.Office.Interop.Word命名空间。 &#xff08;3&#xff09;为WordOper…
阅读更多...
C#知识|汇总方法重载与静态方法应用技巧

C#知识|汇总方法重载与静态方法应用技巧

哈喽&#xff0c;你好&#xff0c;我是雷工&#xff01; 今天学习C#方法重载与静态方法应用技巧的相关内容。 01 方法重载有什么好处&#xff1f; 1.1、可以有效的减少类的对外接口&#xff08;只显示一个方法比较简洁&#xff09;&#xff0c;从而降低类的复杂度。 1.2、方便…
阅读更多...
Python 与 TensorFlow2 生成式 AI（一）

Python 与 TensorFlow2 生成式 AI（一）

原文&#xff1a;zh.annas-archive.org/md5/d06d282ea0d9c23c57f0ce31225acf76 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 序言 “想象力比知识更重要。” – 阿尔伯特爱因斯坦&#xff0c;《爱因斯坦关于宇宙宗教和其他见解与格言》&#xff08;2009&#xff09;…
阅读更多...
【Go 语言入门专栏】Go 语言的起源与发展

【Go 语言入门专栏】Go 语言的起源与发展

前言 Go 语言是当下最为流行的编程语言之一&#xff0c;大约在 2020、2021 年左右开始于国内盛行&#xff0c;许多大厂很早就将部分 Java 项目迁移到了 Go&#xff0c;足可看出其在性能方面的优越性。 相信各位都知道&#xff0c;在爬虫业务中&#xff0c;并发是一个关键的需…
阅读更多...
安居水站：古斯塔夫·勒庞：揭秘群体心理的力量

安居水站：古斯塔夫·勒庞：揭秘群体心理的力量

“群众从来不渴求真理。 他们回避那些让他们不高兴的事实&#xff0c;而更喜欢崇拜能够诱惑他们的错误。凡是懂得欺骗她的人&#xff0c;都容易成为她的主人&#xff0c;凡是试图开导她的人&#xff0c;永远都是她的牺牲品。”古斯塔夫勒邦-群体心理学/古斯塔夫勒邦&#xff08…
阅读更多...
哈希（hash）函数

哈希（hash）函数

本文已收录至《全国计算机等级考试——信息 安全技术》专栏 哈希函数&#xff0c;也称为散列函数 或杂凑函数&#xff0c;指将哈希表中元素的关键键值映射为元素存储位置的函数。是一种将任意长度的数据映射到固定长度输出的函数。哈希函数的特点包括压缩性&#xff0c;即输入数…
阅读更多...
袁庭新ES系列18节｜Spring Data Elasticsearch高级

袁庭新ES系列18节｜Spring Data Elasticsearch高级

前言 这一章节袁老师将带领同学们来学习Spring Data Elasticsearch高级操作相关的内容。我们继续来探索SDE是如何将原始操作Elasticsearch的客户端API进行封装的&#xff0c;以及通过Spring Data Elasticsearch如何来操作ES。准备好了吗&#xff1f;我们继续来探索ES的内容。 …
阅读更多...
Android Studio 调试：快速入门指南

Android Studio 调试：快速入门指南

作为一名Android应用开发人员&#xff0c;调试是你不可或缺的技能之一。通过调试&#xff0c;你可以定位和解决各种问题&#xff0c;包括崩溃、性能问题、UI错误等。在本文中&#xff0c;我们将分享一些实用的Android调试技巧&#xff0c;帮助你提高应用开发效率。 Android St…
阅读更多...
餐后血糖波动？学会在米饭里加两物

餐后血糖波动？学会在米饭里加两物

米饭里加两物&#xff0c;帮你平稳餐后血糖&#xff0c;餐后血糖稳稳的&#xff0c;别让你碗里的米饭太单调&#xff0c;搭着吃对血糖好。今天呢我教大家一招&#xff0c;在蒸米饭的时候&#xff0c;加上两种食材&#xff0c;能够改善餐后血糖。 第一就是在煮米饭的时候加点糙米…
阅读更多...
STM32 F103C8T6学习笔记17：类IIC通信—MLX90614红外非接触温度计

STM32 F103C8T6学习笔记17：类IIC通信—MLX90614红外非接触温度计

今日学习配置MLX90614红外非接触温度计 与 STM32 F103C8T6 单片机的通信 文章提供测试代码讲解、完整工程下载、测试效果图 本文需要用到的大概基础知识&#xff1a;1.3寸OLED配置通信显示、IIC通信、 定时器配置使用 这里就只贴出我的 OLED驱动方面的网址链接了&#xff1a…
阅读更多...
【热闻速递】Google 裁撤 Python研发团队

【热闻速递】Google 裁撤 Python研发团队

&#x1f308;个人主页: 鑫宝Code &#x1f525;热门专栏: 闲话杂谈&#xff5c; 炫酷HTML | JavaScript基础 ​&#x1f4ab;个人格言: "如无必要&#xff0c;勿增实体" 文章目录 【&#x1f525;热闻速递】Google 裁撤 Python研发团队引入研究结论 【&#x1f5…
阅读更多...
配置及使用OpenCV(Python)

配置及使用OpenCV(Python)

python配置OpenCV相对于c的配置方法容易的多&#xff0c;但建议在Anaconda中的Python虚拟环境中使用&#xff0c;这样更方便进行包管理和环境管理&#xff1a; 先激活Anaconda的python虚拟环境&#xff1a; conda activate GGBoy 随后下载 opencv 包&#xff1a; conda ins…
阅读更多...
数据结构——树概念以及结构

数据结构——树概念以及结构

首先我们来复习一下顺序表和链表的优缺点。 顺序表缺点&#xff1a; 1.中间或者头部插入、删除数据需要挪动覆盖&#xff0c;效率低 2.空间不够只能扩容&#xff0c;扩容有消耗 3.倍数扩容&#xff0c;空间用不完&#xff0c;存在浪费空间 顺序表优点&#xff1a; 1.可以…
阅读更多...
低代码工业组态数字孪生平台

低代码工业组态数字孪生平台

2024 两会热词「新质生产力」凭借其主要特征——高科技、高效能及高质量&#xff0c;引发各界关注。在探索构建新质生产力的重要议题中&#xff0c;数据要素被视为土地、劳动力、资本和技术之后的第五大生产要素。数据要素赋能新质生产力发展主要体现为&#xff1a;生产力由生产…
阅读更多...
电商日志项目(一)

电商日志项目(一)

电商日志项目 一、项目体系架构设计1. 项目系统架构2. 项目数据流程二、环境搭建1. NginxLog文件服务1.1. 上传，解压1.2. 编译安装1.3. 启动验证2. Flume-ng2.1. 上传解压2.2. 修改配置文件2.3. 修改环境变量2.4. 验证3. Sqoop3.1. 上传解压3.2. 配置环境变量3.3. 修改配置文件…
阅读更多...
【19】JAVASE-多线程专题【从零开始学JAVA】

【19】JAVASE-多线程专题【从零开始学JAVA】

Java零基础系列课程-JavaSE基础篇 Lecture&#xff1a;波哥 Java 是第一大编程语言和开发平台。它有助于企业降低成本、缩短开发周期、推动创新以及改善应用服务。如今全球有数百万开发人员运行着超过 51 亿个 Java 虚拟机&#xff0c;Java 仍是企业和开发人员的首选开发平台。…
阅读更多...
[高质量]2024五一数学建模A题保奖思路+代码（后续会更新）

[高质量]2024五一数学建模A题保奖思路+代码（后续会更新）

你的点赞收藏是我继续更新的最大动力&#xff0c;可点击文末卡片获取更多资料 你是否在寻找数学建模比赛的突破点&#xff1f; 作为经验丰富的数学建模团队&#xff0c;我们将为你带来2024 年华东杯&#xff08;A题&#xff09;的全面解析包。这个解决方案包不仅包括完整的代…
阅读更多...
2024年十款开源测试开发工具推荐（自动化、性能、混沌测试、造数据、流量复制）

2024年十款开源测试开发工具推荐（自动化、性能、混沌测试、造数据、流量复制）

今天为大家奉献一篇测试开发工具集锦干货。在本篇文章中&#xff0c;将给大家推荐10款日常工作中经常用到的测试开发工具神器&#xff0c;涵盖了自动化测试、性能压测、流量复制、混沌测试、造数据等。 1、AutoMeter-API 自动化测试平台 AutoMeter 是一款针对分布式服务&…
阅读更多...
最新文章

Copyright @ 2022~2023