- 信息学竞赛宝典:数据结构基础
- 张新华 梁靖韵 刘树明编著
- 586字
- 2024-07-05 17:53:13
第1章 链表
1.1 何谓链表
我们知道,数组一般需要先定义长度(事先预估数组元素个数),但这在解决某些问题时并不是特别适用。例如,记录不同学校的学生时,由于各校人数不同,开辟过大的数组会导致存储空间浪费,开辟过小的数组会导致数组元素不够用。
链表可以根据需要动态开辟内存单元,是一种常见的重要数据结构。图1.1所示为最简单的一种链表。
图1.1
链表如同铁链,一环扣一环,中间是不能断开的。例如,幼儿园教师带领小朋友出来散步,教师牵着第一个小朋友的手,第一个小朋友牵着第二个小朋友的手……最后一个小朋友的一只手是空的,这就是一个“链”。
教师即“头指针”变量,即图1.1中的“Head”,它用于存放一个地址。链表中的每一个元素被称为一个“节点”,每个节点都包含两部分:一部分是存储数据元素的数据域,另一部分是存储下一个节点地址的指针域。
最后一个元素的指针域不指向其他节点,它被称为“表尾”,以“NULL”表示。“NULL”在C++里指向“空地址”。
显然,链表使用结构体和指针变量实现是十分合适的。
由于NOIP已允许使用C++的STL(Standard Template Library,标准模板库),因此本书中许多数据结构的实现都可以使用STL轻松实现,例如队列可以使用STL的queue实现,堆栈可以使用STL的stack实现……此外,使用效率更高的数组仿真也是不错的选择。对学习时间不充裕的读者来说,本章的链表内容可以略过不看,但如果想要对数据结构有更深刻的理解以应对更高层次的挑战,建议读者还是认认真真把基础夯实。