链表基础知识详解.pdf资源-CSDN文库

数据结构

需积分: 1 176 浏览量 2024-12-19 10:18:32 上传评论收藏 782KB PDF 举报

资源推荐

资源详情

资源评论

链表基础知识详解

本文档通过解释、图示、示例代码和练习相结合的方式，介绍了构建链表的基本结构和技术。

如果你想要理解链表，或者想要看到一个现实且实用的、涉及大量指针操作的代码示例，那么

这份资料将对你非常有用。

学习链表有两个主要原因。最显而易见的是，链表是一种你可能想在真实程序中使用的数据结

构。了解链表的优点和缺点将使你更加深入地理解在考虑任何数据结构时都需要关注的时间、

空间和代码问题。另一个不那么显而易见的原因是，链表是学习指针的绝佳方式。事实上，你

可能从未在真实程序中使用过链表，但你肯定会频繁使用指针。链表问题巧妙地结合了算法和

指针操作。传统上，链表一直是初学者程序员真正理解指针的实践领域。

第 1 节 — 链表基础

为何使用链表？

链表和数组在存储数据集合方面具有相似性。术语上，数组和链表都是代表“客户端”代码存储

“元素”。元素的具体类型并不重要，因为相同的结构基本上可以存储任何类型的元素。理解链

表的一种方式是，先了解数组的工作原理，然后思考其他可能的替代方法。

数组回顾

数组可能是用于存储元素集合的最常见数据结构。在大多数编程语言中，数组声明起来很方便，

并且提供了便捷的[ ]语法来通过索引号访问任何元素。以下示例展示了一些典型的数组代码，

以及数组在内存中可能呈现的图示。该代码分配了一个名为 int scores[100]的数组，将前三个

元素设置为包含数字 1、2、3，而数组的其余部分则保持未初始化状态……

void ArrayTest() {

int scores[100];

// operate on the elements of the scores array...

scores[0] = 1;

scores[1] = 2;

scores[2] = 3;

}

以下是 scores 数组在内存中可能呈现的图示说明。关键点在于，整个数组是作为一块连续的内

存块来分配的。数组中的每个元素都在该数组中有自己的空间。可以使用[ ]语法直接访问任何

元素。

一旦数组设置完成，使用[ ]操作符访问任何元素都变得方便且快速。（专家额外信息）通过诸

如 scores[i]的表达式访问数组几乎总是使用快速地址算术来实现的：元素的地址是通过从数组

起始位置计算偏移量得出的，这仅需要一次乘法和一次加法。

数组的缺点包括……

1）数组的大小是固定的——在此例中为 100 个元素。大多数情况下，这个大小是在编译时通

过简单的声明（如上述示例）来指定的。虽然通过一些额外的努力，可以将数组的大小推迟到

运行时再确定，但之后它仍然保持不变。（专家额外信息）你可以费心地在堆中动态分配一个

数组，然后使用 realloc()动态调整其大小，但这需要程序员付出真正的努力。

2）由于（1）的原因，程序员最方便的做法是分配看起来“足够大”的数组（例如 scores 示例中

的 100）。虽然这样做很方便，但这种策略有两个缺点：（a）大多数情况下数组中只有 20 或

30 个元素，而数组中 70%的空间实际上都被浪费了。（b）如果程序需要处理超过 100 个分数，

代码就会崩溃。令人惊讶的是，大量商业代码都采用了这种天真的数组分配方式，这在大多数

情况下会浪费空间，并在特殊情况下导致崩溃。（专家额外信息）对于相对较大的数组（大于

8KB），虚拟内存系统可能会部分补偿这个问题，因为“浪费”的元素从未被访问过。

3）（次要）在数组前面插入新元素可能代价很高，因为需要移动现有元素以腾出空间。

链表有自己的优势和劣势，但它们恰好在数组薄弱的地方表现出色。数组的所有特性都源于其

为所有元素在一块内存中分配内存的策略。链表则使用了一种完全不同的策略。我们将看到，

链表为每个元素单独分配内存，并且只在必要时进行分配。

指针复习

以下是关于指针的术语和规则的快速回顾。接下来的链表代码将依赖于这些规则。

 指针/指向物：“指针”存储了对另一个变量的引用，有时这个变量也被称为其“指向物”。另

外，指针也可以被设置为 NULL 值，表示它当前不指向任何指向物。（在 C 和 C++中，NULL

值可以用作布尔假值。）

 解引用 Dereference：对指针进行解引用操作可以访问其指向物。只有在指针被设置为指向

特定的指向物之后，才能对其进行解引用。没有指向物的指针是“坏的”（下文详述），并

且不应该被解引用。

 坏指针：没有分配指向物的指针是“坏的”，并且不应该被解引用。在 C 和 C++中，对坏指

针进行解引用有时会导致立即崩溃，有时则会随机破坏正在运行的程序的内存，导致后续

崩溃或计算错误。这种随机出现的错误很难追踪。在 C 和 C++中，所有指针一开始都有坏

值，因此很容易意外地使用坏指针。正确的代码会在使用指针之前为其设置一个有效的值。

意外使用坏指针是指针代码中最常见的错误。在 Java 和其他面向运行时的语言中，指针自

动以 NULL 值开始，因此解引用坏指针会立即被检测到。出于这个原因，Java 程序更容易

调试。

 指针赋值：两个指针之间的赋值操作，如 p=q;，会使两个指针指向同一个指向物。它不会

复制指向物的内存。赋值后，两个指针将指向相同的指向物内存，这被称为“共享”情况。

 malloc()：malloc()是一个系统函数，它在“堆”中分配一块内存，并返回一个指向新内存块

的指针。malloc()和其他堆函数的原型在 stdlib.h 中。malloc()的参数是需要分配的内存块的

大小（以字节为单位）。与局部（“栈”）变量不同，堆内存不会在创建它的函数退出时自

动释放。如果 malloc()无法满足请求，它会返回 NULL。（专家额外信息）如果你希望确保

安全，可以使用 assert()来检查 NULL 情况。大多数现代编程系统会在内存分配器中抛出异

常或进行其他自动错误处理，因此源代码需要显式检查分配失败的情况变得越来越少见。

 free()：free()是 malloc()的反操作。对堆内存块调用 free()以向系统指示你不再需要它。free()

的参数是指向堆中内存块的指针——这个指针之前是通过调用 malloc()获得的。

链表的样子：

数组为其所有元素分配了一块连续的内存空间。相比之下，链表则为每个元素单独分配内存空

间，这个空间被称为“链表元素”或“节点”。链表通过使用指针将所有节点像链条中的链环一样

连接在一起，从而形成了其整体结构。

在链表中，每个节点都包含两个字段：一个是“数据”字段，用于存储列表为其客户端所持有的

任何元素类型；另一个是“next”字段，它是一个指针，用于将一个节点链接到下一个节点。每

个节点都是通过调用 malloc()在堆上分配的，因此节点内存会一直存在，直到显式地通过调用

剩余28页未读，继续阅读

评论收藏

内容反馈

icysmile131

粉丝: 4631
资源: 735

链表基础知识详解.pdf

JAVA实现链表,双向链表.pdf

计算机二级公共基础知识习题详解.pdf

一线互联网大厂Android面试真题详解.pdf

c++游戏开发经典案例详解.pdf分享

计算机二级考试基础知识汇总.pdf

Java学习攻略详解.pdf

计算机二级公共基础知识资料.pdf

2014年3月计算机二级考试公共基础知识资料.pdf

JAVA单向链表的实现.pdf

2017计算机二级公共基础知识完整.pdf

全国计算机二级c语言基础知识部分.pdf

北京工业大学数据结构十套卷及答案详解.pdf

uCOS-II源码详解.pdf

java集合详解.pdf

全国计算机二级考试题库及答案(基础知识).pdf

FAT32文件系统详解.pdf

C语言指针详解（通俗易懂）.pdf

LwIP协议栈源码详解.pdf

2005年9月全国计算机等级考试二级VB笔试试卷.详解.pdf

2012年3月计算机二级VF考试真题及答案详解.pdf

2012全国计算机二级C语言公共基础知识.pdf

全国计算机等级考试二级公共基础知识考点说课.pdf

全国计算机二级考试基础知识.pdf

我国的计算机二级公共基础知识.pdf

全国计算机二级考试题库及答案的基础知识.pdf

二级C++公共基础知识.pdf

三月份全国计算机二级考试公共基础复习知识题.pdf

计算机二级公共基础120题详解版.pdf

九月份全国计算机二级考试公共基础复习知识题.pdf

最新资源