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

发布于：2024-10-18 ⋅ 阅读:(13) ⋅ 点赞:(0)

前言

介绍

 🍃数据结构专区：数据结构

参考

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

补充

后序代码中会遇见这个结构体

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；

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

目录

前言

1、单链表的基本概念

2、单链表的基本操作

2.1 宏定义和结构体

2.2 初始化  O(1)

2.3 销毁  O(n)

2.4 判空  O(1)

2.5 求表长  O(n)

2.6 取值（按序号查找）  O(n)

2.7 按值查找  O(n)

2.8 指定插入  O(n)

2.9 删除  O(n)

2.10 输出链表

2.11 头插法  O(n)

2.12 尾插法  O(n)

2.13 整体代码（含测试）

结语

1、单链表的基本概念

单链表（Singly Linked List）是一种常见的数据结构，用于存储一系列的元素，其中每个元素称为节点（Node）。在单链表中，每个节点包含两部分：一部分存储数据（data），另一部分存储指向下一个节点的指针（pointer 或 next）。以下是单链表的一些基本概念：

  1. 节点（Node）：
    • 节点是单链表的基本单元。
    • 每个节点包含两个部分：
      • 数据域（data）：存储实际的数据。
      • 指针域（next）：存储指向下一个节点的指针（如果当前节点是最后一个节点，则指针为 null 或 NULL）。
  2. 头节点（Head Node）：
    • 单链表通常有一个头节点，它指向链表的第一个实际数据节点（如果链表不为空）。
    • 头节点本身不存储数据，也可以存储一个哨兵值（dummy value）或者作为链表操作的辅助。
  3. 尾节点（Tail Node）：
    • 链表的最后一个节点，其 next 指针为 null 或 NULL。
  4. 链表长度（Length）：
    • 链表中节点的数量。
    • 通常通过一个额外的变量来维护链表的长度，以加快获取链表长度的操作。
  5. 操作：
    • 插入（Insert）：在链表的特定位置插入一个新节点。
    • 删除（Delete）：删除链表中的某个节点。
    • 查找（Search）：在链表中查找特定值的节点。
    • 遍历（Traversal）：从头节点开始，依次访问链表中的每个节点。
  6. 时间复杂度：
    • 插入、删除和查找操作的时间复杂度通常为 O(n)，其中 n 是链表的长度。这是因为这些操作在最坏情况下需要遍历链表的一部分或全部节点。
    • 遍历链表的时间复杂度为 O(n)。
  7. 内存管理：
    • 单链表使用动态内存分配来创建节点，因此在使用完毕后需要手动释放每个节点的内存，以避免内存泄漏。

单链表相比于数组，其优势在于插入和删除操作的时间复杂度较低（在已知位置的情况下），但劣势在于访问特定位置的节点需要从头节点开始遍历，不如数组那样高效。 

2、单链表的基本操作

2.1 宏定义和结构体

#include<iostream>
using namespace std;

//控制最大值
#define MAXSIZE 1000
//声明Status用于记录返回结果
typedef int Status;
#define OK 1
#define ERROR 0
#define OVERFLOW -1

typedef int ElemType;
typedef struct LNode
{
	ElemType data;
	struct LNode* next;
}LNode, *LinkList;

2.2 初始化  O(1)

//初始化 O(1)
Status InitList(LinkList& L)
{
	L = new LNode;
	//等价于
	//L = (LNode*)malloc(sizeof(LNode));
	L->next = NULL;
	return OK;
}

2.3 销毁  O(n)

//链表销毁 O(n),n为链表中数据节点的个数
Status DestroyLink(LinkList& L)
{
	LNode* pre = L;
	LNode* p = L->next;  //pre指向节点p的前驱节点
	while (p)
	{
		free(pre);  //释放pre节点
		pre = p;    //pre , p 同步向后移动一位
		p = pre->next;
	}
	//循环结束后，p为NULL,pre指向尾节点，释放它
	free(pre);
	return OK;
}

2.4 判空  O(1)

//判空 O(1)
Status ListEmpty(LinkList L)
{
	return(L->next == NULL);
}

2.5 求表长  O(n)

//求表长  O(n),n为链表中数据节点的个数
int ListLength(LinkList L)
{
	int n = 0;
	LNode* p = L->next;
	while (p)
	{
		n++;
		p = p->next;
	}
	return n;
}

2.6 取值（按序号查找）  O(n)

//取值  O(n),n为链表中数据节点的个数
//按照序号进行查找
Status GetElemLink(LinkList L, int i, ElemType& e)
{
	LNode* p = L->next;
	int j = 1;
	while (p && j < i)  //顺链表域向后查找，直到p为空或p指向第i个元素
	{
		p = p->next;
		++j;
	}
	if (!p || j > i)  //i值不合法
	{
		return ERROR;  
	}
	else
	{
		e = p->data;  //用引用返回得到的参数数据
		return OK;
	}
}

2.7 按值查找  O(n)

//按照元素进行查找  O(n),n为链表中数据节点的个数
LNode* LocateElem(LinkList L, ElemType e)
{
	LNode* p;
	p = L->next;
	while (p && p->data != e)  //顺链表域向后查找，直到p为空或者p所指节点的数据域为e
	{
		p = p->next;
	}
	return p;   //查找到后返回e元素的结点地址p，查找失败后返回为NULL
}

2.8 指定插入  O(n)

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

 

2.9 删除  O(n)

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

 

2.10 输出链表

//遍历打印链表  O(n),n为链表中数据节点的个数
void TraverseList(LinkList L)
{
	if (L == nullptr || L->next == nullptr) {
		cout << "链表为空" << endl;
		return;
	}
	LNode* p;
	p = L->next;
	while (p)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}

2.11 头插法  O(n)

//头插法  O(n),n为链表中数据节点的个数
void CreatLink_F(LinkList& L, int n)
{
	L = new LNode;
	L->next = NULL;
	for (int i = 0; i < n; i++)
	{
		LinkList p = new LNode;
		cin >> p->data;
		p->next = L->next;
		L->next = p;
	}
}

2.12 尾插法  O(n)

//尾插法  O(n),n为链表中数据节点的个数
void CreatLink_L(LinkList& L, int n)
{
	L = new LNode;
	L->next = NULL;
	LNode* r = L;
	for (int i = 0; i < n; i++)
	{
		LNode* p = new LNode;
		cin >> p->data;
		p->next = NULL;
		r->next = p;
	}
}

2.13 整体代码（含测试）

#include<iostream>
using namespace std;

//控制最大值
#define MAXSIZE 1000
//声明Status用于记录返回结果
typedef int Status;
#define OK 1
#define ERROR 0
#define OVERFLOW -1

typedef int ElemType;
typedef struct LNode
{
	ElemType data;
	struct LNode* next;
}LNode, *LinkList;

//初始化 O(1)
Status InitList(LinkList& L)
{
	L = new LNode;
	//等价于
	//L = (LNode*)malloc(sizeof(LNode));
	L->next = NULL;
	return OK;
}

//链表销毁 O(n),n为链表中数据节点的个数
Status DestroyLink(LinkList& L)
{
	LNode* pre = L;
	LNode* p = L->next;  //pre指向节点p的前驱节点
	while (p)
	{
		free(pre);  //释放pre节点
		pre = p;    //pre , p 同步向后移动一位
		p = pre->next;
	}
	//循环结束后，p为NULL,pre指向尾节点，释放它
	free(pre);
	return OK;
}

//判空 O(1)
Status ListEmpty(LinkList L)
{
	return(L->next == NULL);
}

//求表长  O(n),n为链表中数据节点的个数
int ListLength(LinkList L)
{
	int n = 0;
	LNode* p = L->next;
	while (p)
	{
		n++;
		p = p->next;
	}
	return n;
}

//取值  O(n),n为链表中数据节点的个数
//按照序号进行查找
Status GetElemLink(LinkList L, int i, ElemType& e)
{
	LNode* p = L->next;
	int j = 1;
	while (p && j < i)  //顺链表域向后查找，直到p为空或p指向第i个元素
	{
		p = p->next;
		++j;
	}
	if (!p || j > i)  //i值不合法
	{
		return ERROR;  
	}
	else
	{
		e = p->data;  //用引用返回得到的参数数据
		return OK;
	}
}

//按照元素进行查找  O(n),n为链表中数据节点的个数
LNode* LocateElem(LinkList L, ElemType e)
{
	LinkList p;
	p = L->next;
	while (p && p->data != e)  //顺链表域向后查找，直到p为空或者p所指节点的数据域为e
	{
		p = p->next;
	}
	return p;   //查找到后返回e元素的结点地址p，查找失败后返回为NULL
}

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

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

//遍历打印链表  O(n),n为链表中数据节点的个数
void TraverseList(LinkList L)
{
	if (L == nullptr || L->next == nullptr) {
		cout << "链表为空" << endl;
		return;
	}
	LNode* p;
	p = L->next;
	while (p)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;
}

//头插法  O(n),n为链表中数据节点的个数
void CreatLink_F(LinkList& L, int n)
{
	L = new LNode;
	L->next = NULL;
	for (int i = 0; i < n; i++)
	{
		LinkList p = new LNode;
		cin >> p->data;
		p->next = L->next;
		L->next = p;
	}
}

//尾插法  O(n),n为链表中数据节点的个数
void CreatLink_L(LinkList& L, int n)
{
	L = new LNode;
	L->next = NULL;
	LNode* r = L;
	for (int i = 0; i < n; i++)
	{
		LNode* p = new LNode;
		cin >> p->data;
		p->next = NULL;
		r->next = p;
	}
}

int main() {
	LinkList L;
	ElemType e;

	cout << "开始测试单链表操作函数：" << endl;

	// 测试初始化函数
	cout << "\n1. 测试初始化函数 InitList" << endl;
	if (InitList(L) == OK) {
		cout << "链表初始化成功" << endl;
	}
	else {
		cout << "链表初始化失败" << endl;
		return 1;
	}

	// 测试插入函数
	cout << "\n2. 测试插入函数 InsertLink" << endl;
	for (int i = 1; i <= 5; i++) {
		if (InsertLink(L, i, i * 10) == OK) {
			cout << "成功在位置 " << i << " 插入元素 " << i * 10 << endl;
		}
		else {
			cout << "在位置 " << i << " 插入元素失败" << endl;
		}
	}

	// 测试遍历打印函数
	cout << "\n3. 测试遍历打印函数 TraverseList" << endl;
	cout << "当前链表内容：";
	TraverseList(L);

	// 测试取值函数
	cout << "\n4. 测试取值函数 GetElemLink" << endl;
	if (GetElemLink(L, 3, e) == OK) {
		cout << "第3个元素的值为：" << e << endl;
	}
	else {
		cout << "获取第3个元素失败" << endl;
	}

	// 测试查找函数
	cout << "\n5. 测试查找函数 LocateElem" << endl;
	e = 30;
	LNode* found = LocateElem(L, e);
	if (found) {
		cout << "元素 " << e << " 在链表中" << endl;
	}
	else {
		cout << "元素 " << e << " 不在链表中" << endl;
	}

	// 测试删除函数
	cout << "\n6. 测试删除函数 DeleteLink" << endl;
	if (DeleteLink(L, 2, e) == OK) {
		cout << "成功删除第2个元素，删除的元素值为：" << e << endl;
		cout << "删除后的链表内容：";
		TraverseList(L);
	}
	else {
		cout << "删除第2个元素失败" << endl;
	}

	// 测试求长度函数
	cout << "\n7. 测试求长度函数 ListLength" << endl;
	cout << "当前链表的长度为：" << ListLength(L) << endl;

	// 测试判空函数
	cout << "\n8. 测试判空函数 ListEmpty" << endl;
	if (ListEmpty(L) == OK) {
		cout << "链表为空" << endl;
	}
	else {
		cout << "链表不为空" << endl;
	}

	// 测试头插法创建链表
	cout << "\n9. 测试头插法创建链表 CreatLink_F" << endl;
	LinkList L1;
	cout << "请输入3个元素用于头插法创建链表：";
	CreatLink_F(L1, 3);
	cout << "头插法创建的链表内容：";
	TraverseList(L1);

	// 测试尾插法创建链表
	cout << "\n10. 测试尾插法创建链表 CreatLink_L" << endl;
	LinkList L2;
	cout << "请输入3个元素用于尾插法创建链表：";
	CreatLink_L(L2, 3);
	cout << "尾插法创建的链表内容：";
	TraverseList(L2);

	// 测试销毁函数
	cout << "\n11. 测试销毁函数 DestroyLink" << endl;
	if (DestroyLink(L) == OK && DestroyLink(L1) == OK && DestroyLink(L2) == OK) {
		cout << "链表销毁成功" << endl;
	}
	else {
		cout << "链表销毁失败" << endl;
	}

	cout << "\n所有测试完成" << endl;

	return 0;
}

结语

该部分内容需要大家实操才可以有所收获，同时这部分又是后续学习中的基础，希望大家可以认真对待！ 

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布