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

数据结构——单链表基本操作的实现

article 2024/11/15 16:30:56

前言

参考

该部分知识参考于《数据结构（C语言版 第2版）》29 ~ 36页

注意

这里的ElemType是以Book类型的数据作为举例，如果需要更改可以自行改变！

🌈每一个清晨，都是世界对你说的最温柔的早安：ૢ(≧▽≦)و✨

目录

前言

1、单链表的基本概念

2、宏定义

3、链表数据内容进行定义

4、单链表的初始化

5、单链表的销毁

6、清空链表数据

7、求链表的长度

8、判断链表是否为空

9、按位查找

10、按值查找

11、单链表数据的插入

12、单链表数据的删除

13、创建单链表

13.1 头插法

13.2 尾插法 

14、遍历打印链表

15、总代码

测试结果

结语

1、单链表的基本概念

单链表（Singly Linked List）是链表中最简单的一种形式，它是一系列节点的集合，每个节点都包含两个部分：一是存储数据的数据域（Data Field），二是存储下一个节点地址的指针域（或称为链接域，Link Field）。单链表中的节点以单向方式连接，即每个节点只能顺序地访问其后续节点（如果有的话），而不能直接访问其前驱节点（除非使用额外的数据结构来辅助）

 我们废话不多时直接开始进行单链表代码的实现

2、宏定义

#include<iostream>
using namespace std;

//初始化定义
#define OK 1
#define ERROR 0
#define OVERFLOW -1
//Status是函数返回值类型，其值是函数结果状态代码
typedef int Status;

3、链表数据内容进行定义

//图书的数据结构
typedef struct
{
	char no[20];
	char name[50];
	float peice;
}Book;

//单链表的结构
typedef struct LNode
{
	Book data;
	struct LNode* next;
}LNode,*LinkList;

//声明链表
LinkList L;

这里我们解释一些内容

typedef struct LNode
{
...
}LNode,*LinkList;

对于这个代码，目的是定义线性表的单链表储存结构。

关键在于LNode与*LinkList

抽象出两个句子：
typedef struct Node LNode;
typedef struct Node* LinkList;

  • LNode，参照typede的用法，可以得知LNode就是struct LNode的别名，即LNode==struct LNode；
  • LinkList，是一个指向该结构体的的指针的别名。其实这个*应该不是跟着LinkList，而是跟在LNode后面的,即LNode* == LinkList。

可以通过这样一个例子可以这样来理解
typedef struct int ElemType
typedef struct int* ElemTypePtr
第一个是 定义整型变量的别名 ElemType
第二个是 定义指向整型变量的指针的别名 ElemTypePtr

LNode Node;//定义结构体变量Node；
LinkList Ptr;//定义指向结构体的指针变量Ptr；

4、单链表的初始化

//链表初始化
Status InitLink(LinkList &L)
{
	L = new LNode;  //让L指针指向新开辟的结点
	L->next = NULL;  //让L指针指向结点的next域置为NULL
	return OK;
}

5、单链表的销毁

//链表销毁
Status DestroyLink(LinkList& L)
{
	LinkList p;  //p作为中间变量用于释放结点
	while (L)
	{
		p = L;
		L = L->next;
		delete p;
	}
	//循环结束后，L将置为NULL
	return OK;
}

6、清空链表数据

//清空链表
Status CleanLink(LinkList& L)
{
	LinkList p; //作为中间变量
	p = L->next;  //p指向该链表的首元节点
	while (p)
	{
		L->next = p->next;
		delete p;
		p = L->next;
	}
	L->next = NULL; //最后需要将头指针置为NULL，否则会成为野指针
	return OK;
}

7、求链表的长度

//求表长
int GetLengthLink(LinkList L)
{
	LinkList p;
	p = L->next;
	int count = 0;//用于计数
	while (p)
	{
		++count;
		p = p->next;
	}
	return count;
}

8、判断链表是否为空

//判空
Status EmptyLink(LinkList L)
{
	if (L->next)
		return ERROR;  //不为空
	else
		return OK;     //为空
}

9、按位查找

//按照序号进行查找
Status GetElemLink(LinkList L, int i, Book& e)
{
	LinkList p;
	p = L->next;
	int j = 1;
	while (p && j < i)
	{
		p = p->next;
		++j;
	}
	if (!p || j > i)
	{
		return ERROR;  //如果没找到返回0
	}
	else
	{
		e = p->data;  //用引用返回得到的参数数据
		return OK;
	}
}

10、按值查找

//按照元素进行查找
LNode* LocateElem(LinkList L, Book e)
{
	LinkList p;
	p = L->next;
	while (p && p->data.no != e.no)  //这里按照书号查找，基本可以保证唯一性
	{
		p = p->next; 
	}
	return p;   //查找到后返回e元素的结点地址p，查找失败后返回为NULL
}

11、单链表数据的插入

//链表插入
//将e节点元素插入到i节点的前面，则需要移动到i-1的位置
Status InsertLink(LinkList& L, int i, Book e)
{
	LinkList p;
	p = L;
	int j = 0;
	while (p && j < i - 1)
	{
		++j;
		p = p->next;
	}
	if (!p && j > i - 1)
	{
		return ERROR;
	}//该情况出现，即插入位置非法
	//循环结束后，已经移动到了i节点的前一个位置，进行尾插即可
	LinkList s = new LNode; //为即将要插入位置开辟一个结点
	s->data = e;
	s->next = p->next;//首先进行尾部连接
	p->next = s;//随后进行头部连接
	return OK;
}

 

12、单链表数据的删除

//链表删除某个结点
Status DeleteLink(LinkList& L, int i, Book e)
{
	LinkList p;
	p = L;
	int j = 0;
	while (p && j < i - 1)
	{
		p = p->next;
		j++;
	}//循环结束后，p会指向要删除节点的前驱节点
	if (!(p->next) || j > i - 1)
	{
		return ERROR;
	}//要判断位置是否非法
	//进行删除
	LinkList q;
	q = p->next;    //临时保存被删除节点的地址以备后续释放
	p->next = q->next;  //改变被删除节点的前驱节点的指针域
	e = q->data;  //删除时拿出来被删除节点的数据
	delete q;
	return OK;
}

 

13、创建单链表

13.1 头插法

//头插法
void CreatLink_F(LinkList &L, int n)
{
	L = new LNode;
	L->next = NULL;
	for (int i = 0; i < n; i++)
	{
		LinkList p = new LNode;
		cout << "依次输入书的书号，书名和价格" << endl;
		cin >> p->data.no;
		cin >> p->data.name;
		cin >> p->data.peice;
		p->next = L->next;
		L->next = p;
	}
}

13.2 尾插法 

//尾插法
void CreatLink_L(LinkList& L, int n)
{
	L = new LNode;
	L->next = NULL;
	LinkList r = L;
	for (int i = 0; i < n; i++)
	{
		LinkList p = new LNode;
		cout << "依次输入书的书号，书名和价格" << endl;
		cin >> p->data.no;
		cin >> p->data.name;
		cin >> p->data.peice;
		p->next = NULL;
		r = p;
	}
}

14、遍历打印链表

//遍历打印链表
void TraverseList(LinkList L)
{
	if (L == nullptr || L->next == nullptr) {
		cout << "链表为空" << endl;
		return;
	}
	LinkList p;
	p = L->next;
	while (p)
	{
		cout << p->data.no << "  " << p->data.name << "  " << p->data.peice << endl;
		p = p->next;
	}
}

15、总代码

#include<iostream>
using namespace std;

//初始化定义
#define OK 1
#define ERROR 0
#define OVERFLOW -1
//Status是函数返回值类型，其值是函数结果状态代码
typedef int Status;

//图书的数据结构
typedef struct
{
	char no[20];
	char name[50];
	float peice;
}Book;

//单链表的结构
typedef struct LNode
{
	Book data;
	struct LNode* next;
}LNode,*LinkList;

//声明链表
LinkList L;

//链表初始化
Status InitLink(LinkList &L)
{
	L = new LNode;
	L->next = NULL;
	return OK;
}

//链表销毁
Status DestroyLink(LinkList& L)
{
	LinkList p;
	while (L)
	{
		p = L;
		L = L->next;
		delete p;
	}
	//循环结束后，L将置为NULL
	return OK;
}

//清空链表
Status CleanLink(LinkList& L)
{
	LinkList p; //作为中间变量
	p = L->next;  //p指向该链表的首元节点
	while (p)
	{
		L->next = p->next;
		delete p;
		p = L->next;
	}
	L->next = NULL; //最后需要将头指针置为NULL，否则会成为野指针
	return OK;
}

//求表长
int GetLengthLink(LinkList L)
{
	LinkList p;
	p = L->next;
	int count = 0;//用于计数
	while (p)
	{
		++count;
		p = p->next;
	}
	return count;
}

//判空
Status EmptyLink(LinkList L)
{
	if (L->next)
		return ERROR;  //不为空
	else
		return OK;     //为空
}

//按照序号进行查找
Status GetElemLink(LinkList L, int i, Book& e)
{
	LinkList p;
	p = L->next;
	int j = 1;
	while (p && j < i)
	{
		p = p->next;
		++j;
	}
	if (!p || j > i)
	{
		return ERROR;  //如果没找到返回0
	}
	else
	{
		e = p->data;  //用引用返回得到的参数数据
		return OK;
	}
}

//按照元素进行查找
LNode* LocateElem(LinkList L, Book e)
{
	LinkList p;
	p = L->next;
	while (p && p->data.no != e.no)
	{
		p = p->next; 
	}
	return p;   //查找到后返回e元素的结点地址p，查找失败后返回为NULL
}

//链表插入
//将e节点元素插入到i节点的前面，则需要移动到i-1的位置
Status InsertLink(LinkList& L, int i, Book e)
{
	LinkList p;
	p = L;
	int j = 0;
	while (p && j < i - 1)
	{
		++j;
		p = p->next;
	}
	if (!p && j > i - 1)
	{
		return ERROR;
	}//该情况出现，即插入位置非法
	//循环结束后，已经移动到了i节点的前一个位置，进行尾插即可
	LinkList s = new LNode; //为即将要插入位置开辟一个结点
	s->data = e;
	s->next = p->next;//首先进行尾部连接
	p->next = s;//随后进行头部连接
	return OK;
}

//链表删除某个结点
Status DeleteLink(LinkList& L, int i, Book e)
{
	LinkList p;
	p = L;
	int j = 0;
	while (p && j < i - 1)
	{
		p = p->next;
		j++;
	}//循环结束后，p会指向要删除节点的前驱节点
	if (!(p->next) || j > i - 1)
	{
		return ERROR;
	}//要判断位置是否非法
	//进行删除
	LinkList q;
	q = p->next;    //临时保存被删除节点的地址以备后续释放
	p->next = q->next;  //改变被删除节点的前驱节点的指针域
	e = q->data;  //删除时拿出来被删除节点的数据
	delete q;
	return OK;
}

//创建单链表
//头插法
void CreatLink_F(LinkList &L, int n)
{
	L = new LNode;
	L->next = NULL;
	for (int i = 0; i < n; i++)
	{
		LinkList p = new LNode;
		cout << "依次输入书的书号，书名和价格" << endl;
		cin >> p->data.no;
		cin >> p->data.name;
		cin >> p->data.peice;
		p->next = L->next;
		L->next = p;
	}
}
//尾插法
void CreatLink_L(LinkList& L, int n)
{
	L = new LNode;
	L->next = NULL;
	LinkList r = L;
	for (int i = 0; i < n; i++)
	{
		LinkList p = new LNode;
		cout << "依次输入书的书号，书名和价格" << endl;
		cin >> p->data.no;
		cin >> p->data.name;
		cin >> p->data.peice;
		p->next = NULL;
		r = p;
	}
}

//遍历打印链表
void TraverseList(LinkList L)
{
	if (L == nullptr || L->next == nullptr) {
		cout << "链表为空" << endl;
		return;
	}
	LinkList p;
	p = L->next;
	while (p)
	{
		cout << p->data.no << "  " << p->data.name << "  " << p->data.peice << endl;
		p = p->next;
	}
}

int main()
{
	cout << "初始化创建链表时需要输入3个数据" << endl;
	CreatLink_F(L, 3);
	TraverseList(L);
}

测试结果

结语

该部分内容，大家不要手懒，勤思考勤练习，一定可以学会的，加油！


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

相关文章：

  • 前端vue 列表中回显并下拉选择修改标签
  • 【C语言】值传递和地址传递
  • 更改Ubuntu22.04锁屏壁纸
  • 贪心算法入门（二）
  • 俏美韵从心出发，与女性一道为健康生活贡献力量
  • mongoDB的安装及使用
  • 我与Linux的爱恋：自动化构建工具-make/Makefile
  • 测试-Gatling 与性能测试
  • 98、RS485全自动收发电路入坑笔记
  • Gmtracker_深度学习驱动的图匹配多目标跟踪项目启动与算法流程
  • ES机制原理
  • linux ubuntu编译 openjdk11
  • 中国科技统计年鉴1991-2020年
  • JDBC客户端连接Starrocks 2.5
  • python-回文数（一）
  • 4G MQTT网关在物联网应用中的优势-天拓四方
  • 组播 2024 9 11
  • 为什么mac打不开rar文件 苹果电脑打不开rar压缩文件怎么办
  • 基于Java-SpringBoot+vue实现的前后端分离信息管理系统设计和实现
  • element实现动态路由+面包屑
  • Vue的学习(三)
  • vue2响应式系统是如何实现的（手写）
  • 代码随想录刷题day32丨动态规划理论基础，509. 斐波那契数， 70. 爬楼梯， 746. 使用最小花费爬楼梯
  • 基于Python实现一个庆祝国庆节的小程序
  • Kubernetes 与 springboot集成
  • 【九盾安防】叉车使用安全新升级！指纹识别锁，验证司机操作权限