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

数据结构 链表1

article 2025/1/22 2:37:18

目录

前言

一，链表的介绍

二，数组VS链表

三，链表的实现

四，头插法

 五，任意位置插入

六，在链表种删除任意节点

总结

前言

链表是整个数据结构的基础，我将学习链表之后，才可以不如栈，队列，树，图，这里我将用c++来实现这些过程

一，链表的介绍

数组来实现动态链表，内存和消耗是十分大的，所以我们提出了链表这个概念，但为了我们可以更好地理解链表，我们就更应该了解数组在这方面都有那些限制

由于内存是一个十分至关重要的资源，所以计算机先把内存管理交给了一个组成部分和一个手下(内存管理器)上述就是内存管理器是如何操作的

内存管理器会监视内存中那一部分是空闲的或者已被占据，每当有需要内存或者内容存储都要通过它，与它进行交流

(人与它交流的话，可以通过C语言等等高级语言来交流)

利用数组进行动态分配

程序员：当int b [ 4 ]已经存储完，想再扩展数组b，存储更多的数组，跟manager下令扩展数组b

内存管理器：在分配的时候，我不期望你会这么扩展，所以在分配时周围已分配其他变量，比如上面，变量a就是在旁边，无法进行扩展

那我们该怎么做？

可以创建一个新的数组，扩展数组进行扩展数据，并把之前的数据进行拷贝，拷贝到这个新的数组里面来，但是又太大又浪费内存，太小又怕一会不够了，所以一般就是取两倍大小，公认下是最高的

所以我们就引入了链表

链表是由数据域和地址域组成的

节点的基本定义

struct Node {
    int a;
    struct Node* Next;
};

一个是值域，一个是地址域

头指针的工作

头指针的地址给我们这个链表的最开始的位置，可以让我们拥有完整的链表

二，数组VS链表

1，访问一个元素的花费

Arrary：Constant time O(1)                     List：Dynamic time O(n)

2，内存需求

我们在使用一个非常大的数组的时候，没有一个很大的连续空间时候，如果选择链表，内存很快会被链表分为很多个小块（有纪律会出现碎片化问题）有时候我们会获得很多小的存储单元，但不可能获取一个大的内存块，这也是很罕见的，这个时候就是链表展现的时候了

3 功能实现的花费

1）插入数据在开头

数组：要把每个元素都往后面移动，这样的话，数组的时间复杂度为O( n )

链表：直接插入到头部                                        链表的时间复杂度为O( 1 )

2）插入到数据的末尾

数组：数组未满的时候                       数组的时间复杂度为O( 1 )

           数组已满的时候                       数组的时间复杂度为O( n )

链表：遍历整个链表进行插入             链表的时间复杂度为O( n )

3）插入在数据的中途

两者的空间复杂度都是O( n )

4）简单使用

数组：easy             链表：no  easy

链表是很容易出错的，数组是十分简单的

三，链表的实现

1  链表的基本结构

struct Node {
    int a;              //值域
    struct Node* Next;  //地址域
};

逻辑视图

2  链表的实现 

#define MALLOC(type)(type*)malloc(sizeof(type))
#define MALLOC1(num,type)(type*)malloc(num*sizeof(type))

#include <iostream>
using namespace std;

struct Node {
	int a;
	struct Node* Next;
};

ostream& operator<<(ostream& os, const Node& node) {
	os << "a: " << node.a << ", Next: " << node.Next;
	return os;
}

int main() {
	Node* head = NULL;
	Node* temp = MALLOC(struct Node);
	temp->a = 100;
	temp->Next = NULL;
	head = temp;
	cout << *head << endl;
}

这个离我们弄了一个链表的实现，但是是以c++实现的，我为了方便就用宏设置了两种动态分配

3  C++链表的打印

到那时这里需要注意的是，c++对于链式结构的打印是需要处理的

#include <iostream>
using namespace std;

int main() {
	int a = 10;
	int b = 100;
	int c = 1000;
	cout << a << endl << b << endl << c << endl;
}

我也用int类型进行了测试，这个int，char这些基本的类型是C++它本身就已经帮你写好了，所以你不需要在写这个基本类型的链式怎么打印，基本类型的打印是这样子进行的

在 C++ 中，当你使用 cout << a << b << c; 这样的链式调用时，实际上是多次调用 operator<< 重载函数。具体来说：

  1. 第一次调用：cout << a

    • 这会调用与 a 的类型匹配的 operator<< 重载函数，例如 ostream& operator<<(ostream& os, int value)。

    • 这个函数内部会将 a 的值写入到 cout 所关联的输出流中。

    • 该函数返回 cout 的引用。

  2. 第二次调用：(cout << a) << b

    • 由于第一次调用返回的是 cout 的引用，所以 (cout << a) 仍然是 cout。

    • 这会再次调用与 b 的类型匹配的 operator<< 重载函数，例如 ostream& operator<<(ostream& os, int value)。

    • 这个函数内部会将 b 的值写入到 cout 所关联的输出流中。

    • 该函数返回 cout 的引用。

  3. 第三次调用：((cout << a) << b) << c

    • 同上，这会调用与 c 的类型匹配的 operator<< 重载函数。

    • 这个函数内部会将 c 的值写入到 cout 所关联的输出流中。

    • 该函数返回 cout 的引用

每一次的输入输出都是返回了这个cout 的引用，这个是计算机根据上下文自己做出的判断返回cout的引用

4 cout 的本质

cout 是一个全局的 ostream 对象，用于表示标准输出流（通常是屏幕）。cout 的类型是 std::ostream，它是 std::basic_ostream<char, char_traits<char>> 的特化版本。

ostream& 作为返回类型

当 operator<< 重载函数返回 ostream& 时，它返回的是 cout（或其他 ostream 对象）的引用。这样做的好处有：

  • 支持链式调用：返回引用允许你继续在同一个 ostream 对象上进行操作，从而支持链式调用。例如：

    cpp复制

    cout << a << b << c;

    这行代码实际上是：

    cpp复制

    (cout << a) << b << c;

    每次调用 operator<< 都返回 cout 的引用，使得下一次调用仍然作用于 cout。

  • 避免不必要的复制：ostream 对象通常包含大量的内部状态和资源（如文件缓冲区等），复制这样的对象是非常昂贵的操作。返回引用避免了创建临时副本，提高了效率

5  把&取掉会怎么样

当你把 ostream& 中的 & 去掉，将返回类型改为 ostream 时，会报错的原因主要有两个：

  1. ostream 的复制构造函数被删除

  2. 返回临时对象的引用

1. ostream 的复制构造函数被删除

ostream 类型的对象（如 cout）包含了大量的内部状态和资源，例如文件缓冲区等。复制这样的对象是非常昂贵的操作，而且在大多数情况下是没有必要的。因此，标准库中的 ostream 类型的复制构造函数和赋值运算符都被删除了（即 delete），这意味着你不能创建 ostream 对象的副本。

例如，ostream 的复制构造函数定义如下：

cpp复制

ostream(const ostream&) = delete;

这意味着你不能写这样的代码：

cpp复制

ostream os = cout;  // 错误，复制构造函数被删除

2. 返回临时对象的引用

当你将返回类型改为 ostream 时，函数会尝试返回一个临时的 ostream 对象。然而，这个临时对象在函数返回后会立即被销毁。因此，返回的引用会指向一个已经销毁的对象，这是未定义行为。

例如，考虑以下代码：

cpp复制

ostream operator<<(ostream os, int value) {
    os << value;  // 正确地将 value 写入 os
    return os;    // 返回临时的 os 对象，编译器会报错
}

在这段代码中：

  • os 是一个临时的 ostream 对象，它是 cout 的一个副本（如果复制构造函数没有被删除的话）。

  • 当函数返回时，os 会被销毁，返回的引用会指向一个已经销毁的对象。

编译器报错

编译器会报错，提示 ostream 的复制构造函数被删除，不能创建临时对象的副本。例如，GCC 编译器的错误信息可能如下：

error: use of deleted function 'std::basic_ostream<char>& std::basic_ostream<char>::operator=(const std::basic_ostream<char>&)'

正确的做法

正确的做法是返回 ostream 对象的引用，这样可以避免创建临时对象的副本，并且支持链式调用。例如：

cpp复制

ostream& operator<<(ostream& os, int value) {
    os << value;  // 正确地将 value 写入 os
    return os;    // 返回 os 的引用
}

在这段代码中：

  • os 是 cout 的引用。

  • 函数返回 os 的引用，这样可以继续在同一个 ostream 对象上进行操作，支持链式调用。

总结

去掉 & 会导致编译错误，因为：

  1. ostream 的复制构造函数被删除，不能创建副本。

  2. 返回临时对象的引用会导致未定义行为。

因此，返回 ostream& 是正确且必要的做法，这样可以避免不必要的复制操作，提高效率，并支持链式调用

6  引用的作用

在 C++ 中，引用（&）有“取别名”的含义，但它不仅仅限于变量的别名，也适用于函数返回类型。当用于函数返回类型时，引用的主要作用是避免创建临时对象的副本，并支持链式调用。这里的关键是理解引用在不同上下文中的作用。

 

四，头插法

常见的命名方式：

头节点：head                     虚拟头节点：dummyhead

链接：List  Link  Next         节点：Node                            链表：ListCode

#define MALLOC(type)(type*)malloc(sizeof(type))
#define MALLOC1(num,type)(type*)malloc(num*sizeof(type))

#include <iostream>
using namespace std;

struct Node {
	int a;
	struct Node* Next;
};
Node* head = NULL;

void Insert(int data) {
	struct Node* Itemp = MALLOC(struct Node);
	Itemp->a = data;
	Itemp->Next = NULL;
	if (head != NULL) {
		Itemp->Next = head;
		head = Itemp;
	}
	else {
		head = Itemp;
	}
}

void print() {
    Node* Ptemp = head;
	while (Ptemp != NULL) {
		cout << Ptemp->a << endl;
		Ptemp = Ptemp->Next;
	}
}

int main() {
	Node* temp = MALLOC(struct Node);
	Node* temp1 = MALLOC(struct Node);
	temp->a = 100;
	temp1->a = 200;
	temp->Next = temp1;
	temp1->Next = NULL;
	head = temp;
	Insert(10);
	print();
}

这个是打印一个链表进行头部的插入，然后进行打印，我们常把头指针放到全局变量，这样十分的方便，但是要注意，我们不要直接使用头指针，要用一个变量来顶替它，因为这个头指针是我们再次找到这个链表的关键 

 

 五，任意位置插入

我们在进入任意位置插入的时候，我们要找到插入位置的前一个位置，即我们要插入到n的话，我们要记录到n-·1的位置，但是这个也是由执行的先后顺序的，先执行1，再执行2，不可以反过来，要不然3这个节点就找不到了

#define MALLOC(type)(type*)malloc(sizeof(type))
#define MALLOC1(num,type)(type*)malloc(num*sizeof(type))

#include <iostream>
using namespace std;

struct Node {
	int a;
	struct Node* Next;
};
Node* head = NULL;

void Insert(int data,int n) {
	struct Node* Itemp = MALLOC(struct Node);
	Itemp->a = data;Itemp->Next = NULL;
	if (n == 1) {
		Itemp->Next = head;
		head = Itemp;
	}
	else {
		struct Node* temp1 = head;
		//找到n-1的位置
		for (int i = 0;i < n - 2;i++) {
			temp1 = temp1->Next;
		}
		Itemp->Next = temp1->Next;
		temp1->Next = Itemp;
	}
}

void print() {
    Node* Ptemp = head;
	while (Ptemp != NULL) {
		cout << Ptemp->a << endl;
		Ptemp = Ptemp->Next;
	}
}

int main() {
	head = NULL;
	Insert(2, 1);
	Insert(3, 2);
	Insert(4, 1);
	Insert(6, 3);
	print();
}

这个就是要判断插入到哪里，如果再第一个就是一种情况，如果不是第一个就是第二种情况  

 

六，在链表种删除任意节点

这个删除节点就是把节点连接到要删除节点的后面一个节点，然后将要删除的节点释放掉

#define MALLOC(type)(type*)malloc(sizeof(type))
#define MALLOC1(num,type)(type*)malloc(num*sizeof(type))

#include <iostream>
using namespace std;

struct Node {
	int a;
	struct Node* Next;
};
Node* head = NULL;

void Insert(int data,int n) {
	struct Node* Itemp = MALLOC(struct Node);
	Itemp->a = data;Itemp->Next = NULL;
	if (n == 1) {
		Itemp->Next = head;
		head = Itemp;
	}
	else {
		struct Node* temp1 = head;
		//找到n-1的位置
		for (int i = 0;i < n - 2;i++) {
			temp1 = temp1->Next;
		}
		Itemp->Next = temp1->Next;
		temp1->Next = Itemp;
	}
}

void print() {
    Node* Ptemp = head;
	while (Ptemp != NULL) {
		cout << Ptemp->a << endl;
		Ptemp = Ptemp->Next;
	}
}

void remove(int b) {
	Node* Rtemp = head;
	if (b == 1) {
		head = Rtemp->Next;
		free(Rtemp);
		return;
	}
	for (int i = 0;i < b-2;i++) {
		Rtemp = Rtemp -> Next;
	}
	struct Node* temp2 = Rtemp->Next;
	Rtemp->Next = Rtemp->Next->Next;
	free(temp2);
}

int main() {
	head = NULL;
	Insert(2, 1);
	Insert(3, 2);
	Insert(4, 1);
	Insert(6, 3);
	remove(4);
	print();
}

这个是删除任意节点，我们只需要找到前面一个节点的位置，然后用一个额外的指针标价那个删除的，然后让前面一个链接到删除节点的下一个节点，然后释放掉删除的节点就好了 

总结

我们学习了链表的基本盖概念和计算机是如何管理内存的，计算机把一个任务交给了任务管理器，让他取划分内存的区域，然后我们就对比了数组和链表的各个部分，首先就是访问一个元素，然后就是内存的花费和功能的各个优势和使用起来那个更加的简单，之后我们就用c++来模拟了链表的很多功能，在c++种如果像直接打印链表也是可以的，只需要自己写一个输出方法即可，因为cout就是输出流，然后也可以使用基本的数据类型


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

相关文章：

  • HTML语言的计算机基础
  • Linux系统 C/C++编程基础——使用make工具和Makefile实现自动编译
  • AI 新动态：技术突破与应用拓展
  • MFC 使用 32位带Alpha通道的位图
  • PyTorch使用教程(9)-使用profiler进行模型性能分析
  • Flask简介与安装以及实现一个糕点店的简单流程
  • 力扣hot100之螺旋矩阵
  • 深度学习篇---AnacondaLabelImg
  • Spring 6 第4章——原理：手写IoC
  • 《开源与合作：驱动鸿蒙Next系统中人工智能技术创新发展的双引擎》
  • STM32单片机学习记录（1.17）
  • Failed to load API definition
  • vue 如何判断每次进入都会刷新页面
  • 【WPF】WPF设置自定义皮肤主题
  • 数据结构初 - 链表
  • 第01章 11 分别使用DCMTK和gdcm库，解析DICOM文件系列的dicom标准数据信息
  • SpringBoot 搭建 SSE
  • Numpy基础01（Jupyter基本用法/Ndarray创建与基本操作）
  • vue.draggable 拖拽
  • 2025年国产化推进.NET跨平台应用框架推荐
  • MyBatis操作数据库（入门）
  • 【Java实现导出Excel使用EasyExcel快速实现数据下载到Excel功能】
  • Qt之QDjango-db的简单使用
  • 三格电子——MODBUS TCP 转 CANOpen 协议网关
  • 网络通信---MCU移植LWIP
  • 从零开始：使用 Brain.js 创建你的第一个神经网络（一）