链表应用

2025年03月17日 | 阅读 9 分钟

本文将详细介绍链表的应用。

链表是什么意思？

链表是一种线性数据结构，由称为节点的元素组成，每个节点包含两部分：信息部分和链接部分（也称为下一个指针部分）。

链表用于各种应用，例如

多项式运算表示
大正整数相加
稀疏矩阵表示
大正整数相加
符号表创建
邮件列表
内存管理
文件的链式分配
多精度算术等

多项式运算

多项式运算是链表最重要的应用之一。多项式是数学中的一个重要部分，大多数语言本身并不支持作为数据类型。多项式是由不同的项组成的集合，每项包含系数和指数。它可以使用链表来表示。这种表示使得多项式运算高效。

在用链表表示多项式时，多项式的每一项都表示链表中的一个节点。为了提高处理效率，我们假设多项式的各项都按指数递减的顺序存储在链表中。此外，没有两个项具有相同的指数，没有项具有零系数，并且没有系数。系数的值为 1。

表示多项式的链表中的每个节点包含三个部分：

第一部分包含项的系数的值。
第二部分包含指数的值。
第三部分，LINK 指向下一项（下一个节点）。

下图显示了表示多项式的链表节点的结构：

考虑多项式 P(x) = 7x² + 15x³ - 2 x² + 9。这里的 7、15、-2 和 9 是系数，4、3、2、0 是多项式项的指数。用链表表示此多项式，我们得到：

请注意，节点的数量等于多项式中项的数量。所以我们有 4 个节点。此外，这些项按指数递减的顺序存储在链表中。使用链表表示多项式使得多项式的减法、加法、乘法等运算非常容易。

多项式加法

要将两个多项式相加，我们遍历列表 P 和 Q。我们取列表 P 和 Q 的对应项并比较它们的指数。如果两个指数相等，则将系数相加形成新的系数。如果新系数为 0，则丢弃该项；如果不为零，则将其插入到包含结果多项式的新链表的末尾。如果一个指数大于另一个，则相应的项立即放入新链表中，而具有较小指数的项将与另一个列表的下一项进行比较。如果一个列表先于另一个列表结束，则将较长列表的其余项插入到包含结果多项式的新链表的末尾。

让我们通过一个例子来说明如何执行两个多项式的加法：

P(x) = 3x⁴ + 2x³ - 4 x² + 7

Q (x) = 5x³ + 4 x² - 5

这些多项式使用链表按指数递减的顺序表示如下：

为了生成新的链表来表示给定多项式 P(x) 和 Q(x) 相加得到的结果多项式，我们执行以下步骤：

遍历列表 P 和 Q 并检查所有节点。
我们比较两个多项式对应项的指数。多项式 P 和 Q 的第一项的指数分别为 4 和 3。由于多项式 P 的第一项的指数大于另一个多项式 Q，因此具有较大指数的项被插入新列表中。新列表最初如下所示：
然后我们比较列表 P 的下一项的指数和列表 Q 的当前项的指数。由于两个指数相等，因此将它们的系数相加并追加到新列表中，如下所示：
然后我们移动到 P 和 Q 列表的下一项并比较它们的指数。由于这两项的指数相等，相加后得到 0，因此该项被丢弃，此后不会将任何节点追加到新列表中。
移动到两个列表 P 和 Q 的下一项，我们发现对应项的指数都等于 0。我们将它们的系数相加并将它们追加到新列表，用于结果多项式，如下所示：

示例

C++ 程序，用于添加两个多项式

#include <iostream>
using namespace std;
int max(int m, int n) { return (m > n)? m: n; }
int *add(int A[], int B[], int m, int n)
{
int size = max(m, n);
int *sum = new int[size];
for (int i = 0; i<m; i++)
	sum[i] = A[i];
for (int i=0; i<n; i++)
	sum[i] += B[i];
return sum;
}
void printPoly(int poly[], int n)
{
	for (int i=0; i<n; i++)
	{
	cout << poly[i];
	if (i != 0)
		cout << "x^" << i ;
	if (i != n-1)
	cout << " + ";
	}
}
int main()
{
	int A[] = { 5, 0, 10, 6 };
	int B[] = { 1, 2, 4 };
	int m = sizeof(A)/sizeof(A[0]);
	int n = sizeof(B)/sizeof(B[0]);
	cout << "First polynomial is \n";
	printPoly(A, m);
	cout << "\n Second polynomial is \n";
	printPoly(B, n);
	int *sum = add(A, B, m, n);
	int size = max(m, n);
	cout << "\n Sum of polynomial is \n";
	printPoly(sum, size);
	return 0;
}

说明

在上面的例子中，我们使用数组创建了一个两个多项式之和的例子。

输出

以下是此示例的输出。

使用链表添加大正整数

大多数编程语言都对存储的整数的最大值有限制。最大整数值为 32767，最大值为 2147483647。有时，安全算法和加密等应用程序需要存储和操作无限大小的整数。在这种情况下，最好使用链表来存储和操作任意长度的整数。

使用循环链表可以有效地添加大正整数。正如我们所知，在添加两个大整数时，给定数字的各位数字是从右到左单独遍历的，并将两个数字的相应数字以及来自先前数字的总和的进位相加。因此，要完成加法，我们必须知道链表中如何存储大整数的数字。

大整数的数字必须从右到左存储在链表中，这样列表的第一个节点包含最低有效数字，即最右边的数字，而最后一个节点包含最高有效数字，即最左边的数字。

示例：整数值 543467 可以使用链表表示为：

要执行两个大整数的加法，需要遵循以下步骤：

并行地从左到右遍历两个链表。
在遍历过程中，将相应数字和来自先前数字总和的进位相加，然后存储在结果链表的新节点中。

第一个正大整数 543467 使用链表表示，其第一个节点由 NUM1 指针指向。类似地，第二个正大整数 48315 使用第二个链表表示，其第一个节点由 NUM2 指针指向。这两个数字存储在第三个链表中，其第一个节点由 RESULT 指针指向。

示例

C++ 程序，用于使用链表添加两个多项式

#include <bits/stdc++.h>
#include <iostream.h>
using namespace std;
struct Node {
	int coeff;
	int pow;
	struct Node* next;
};
void create_node(int x, int y, struct Node** temp)
{
	struct Node *r, *z;
	z = *temp;
	if (z == NULL) {
		r = (struct Node*)malloc(sizeof(struct Node));
		r->coeff = x;
		r->pow = y;
		*temp = r;
		r->next = (struct Node*)malloc(sizeof(struct Node));
		r = r->next;
		r->next = NULL;
	}
	else {
		r->coeff = x;
		r->pow = y;
		r->next = (struct Node*)malloc(sizeof(struct Node));
		r = r->next;
		r->next = NULL;
	}
}
void polyadd(struct Node* poly1, struct Node* poly2,
			struct Node* poly)
{
	while (poly1->next && poly2->next) {
		if (poly1->pow > poly2->pow) {
			poly->pow = poly1->pow;
			poly->coeff = poly1->coeff;
			poly1 = poly1->next;
		}
		else if (poly1->pow < poly2->pow) {
			poly->pow = poly2->pow;
			poly->coeff = poly2->coeff;
			poly2 = poly2->next;
		}
		else {
			poly->pow = poly1->pow;
			poly->coeff = poly1->coeff + poly2->coeff;
			poly1 = poly1->next;
			poly2 = poly2->next;
		}
				poly->next
			= (struct Node*)malloc(sizeof(struct Node));
		poly = poly->next;
		poly->next = NULL;
	}
	while (poly1->next || poly2->next) {
		if (poly1->next) {
			poly->pow = poly1->pow;
			poly->coeff = poly1->coeff;
			poly1 = poly1->next;
		}
		if (poly2->next) {
			poly->pow = poly2->pow;
			poly->coeff = poly2->coeff;
			poly2 = poly2->next;
		}
		poly->next
			= (struct Node*)malloc(sizeof(struct Node));
		poly = poly->next;
		poly->next = NULL;
	}
}
void show(struct Node* node)
{
	while (node->next != NULL) {
		printf("%dx^%d", node->coeff, node->pow);
		node = node->next;
		if (node->coeff >= 0) {
			if (node->next != NULL)
				printf("+");
		}
	}
}
int main()
{
	struct Node *poly1 = NULL, *poly2 = NULL, *poly = NULL;
	create_node(5, 2, &poly1);
	create_node(4, 1, &poly1);
	create_node(2, 0, &poly1);
	create_node(-5, 1, &poly2);
	create_node(-5, 0, &poly2);
	printf("1st Number: ");
	show(poly1);
	printf("\n 2nd Number: ");
	show(poly2);
	poly = (struct Node*)malloc(sizeof(struct Node));
	polyadd(poly1, poly2, poly);
	printf("\n Sum of polynomial after addition: ");
	show(poly);
	return 0;
}

说明

在上面的例子中，我们使用链表创建了两个多项式之和的示例。

输出

以下是此示例的输出。

多变量多项式

我们可以表示包含多个变量的多项式，即两个或三个变量。以下节点结构适用于使用单链表表示包含三个变量 X、Y、Z 的多项式。

考虑多项式 P(x, y, z) = 10x²y²z + 17 x²y z² - 5 xy² z+ 21y⁴z² + 7。使用链表表示此多项式为：

此多项式中的项按 x 的降幂顺序排列。x 的次数相同的项按 y 的降幂顺序排列。x 和 y 的次数相同的项按 z 的降幂顺序排列。

示例

简单的 C++ 程序，用于计算两个多项式的乘积

#include <iostream>
using namespace std;
int *multiply(int A[], int B[], int m, int n)
{
int *prod = new int[m+n-1];
for (int i = 0; i<m+n-1; i++)
	prod[i] = 0;
for (int i=0; i<m; i++)
{
	for (int j=0; j<n; j++)
		prod[i+j] += A[i]*B[j];
}
return prod;
}
void printPoly(int poly[], int n)
{
	for (int i=0; i<n; i++)
	{
	cout << poly[i];
	if (i != 0)
		cout << "x^" << i ;
	if (i != n-1)
	cout << " + ";
	}
}
int main()
{
	int A[] = { 5, 0, 10, 6 };
	int B[] = { 1, 2, 4 };
	int m = sizeof(A)/sizeof(A[0]);
	int n = sizeof(B)/sizeof(B[0]);
	cout << "First polynomial is \n";
	printPoly(A, m);
	cout << "\nSecond polynomial is \n";
	printPoly(B, n);
	int *prod = multiply(A, B, m, n);
	cout << "\nProduct of two polynomial is \n";
	printPoly(prod, m+n-1);
	return 0;
}

说明

在上面的例子中，我们使用数组创建了一个两个多项式乘积的示例。

输出

以下是此示例的输出。

链表的一些其他应用

内存管理：内存管理是操作系统的一项关键功能。它决定如何为系统中运行的进程分配和回收存储。我们可以使用链表来跟踪可用于分配的内存部分。
邮件列表：链表在电子邮件应用程序中有其用途。由于很难预测多个列表，因此邮件发送程序在发送消息之前可能会构建一个地址链表。
LISP：LISP 是 LIST processor 的缩写，是人工智能领域一种重要的编程语言。该语言在执行符号处理时广泛使用链表。
文件的链式分配：大文件可能无法在磁盘上的一个位置存储。因此，必须有一些机制将文件的所有分散部分链接在一起。链表的使用允许一种高效的文件分配方法，其中文件的每个块都包含指向文件文本块的指针。但此方法仅适用于顺序访问。
虚拟内存：在系统支持虚拟内存的方式中，可以找到链表的一个有趣应用。
支持其他数据结构：可以使用链表实现栈、队列、哈希表、图等其他数据结构。

下一个主题拓扑排序

链表应用

链表是什么意思？

多项式运算

多项式加法

示例

使用链表添加大正整数

示例

多变量多项式

示例

链表的一些其他应用

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

链表应用

链表是什么意思？

多项式运算

多项式加法

示例

使用链表添加大正整数

示例

多变量多项式

示例

链表的一些其他应用

相关帖子

使用队列实现栈

树遍历

SIP 栈

二叉树的左视图

连续子数组最大和 (Kadane 算法)

创建具有 O 和 X 交替矩形的矩阵

检查给定字符串是否为 K-周期

二叉搜索树中的中序前驱和后继

创建具有 O 和 X 交替矩形的矩阵

检测并移除链表中的循环

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器