Page 54 - 高中 信息技术 选择性必修1 数据与数据结构

第二章 数据的存储方式  2.3 数据的链式存储与组织

2.3.2 链表

在计算机程序中，我们通过链表（Linked Lists）这种数据结构来实现链式结构的数据

存储与组织，链表由一系列结点组成，结点可以动态生成。每个结点包括两个部分：一个
是存储数据的数据域，另一个是存储下一个结点物理地址的指针域。数据元素的逻辑顺序
是通过链表中的指针链接次序实现的。
链表有多种不同的类型，如单向链表、单向循环链表、双向链表、双向循环链表等，
本节我们学习的是单向链表。

因为链表是由若干个结点链接而成的，每个结点都具有相同的结构，因此我们定义链
表的结构时只需要定义链表结点的结构即可。以下是链表结点的类型定义：
广东教育出版社
//定义链表结点的结构
struct LinkNode{
string data; //结点数据
LinkNode *next； //下一结点指针

};
typedef struct LinkNode *LinkList;
在上面的定义中，结构LinkNode代表链表的一个结点，一个结点包括两个内容：data

存储结点需要存储的数据，其数据类型根据实际需要定义；next是一个LinkNode类型的指
针，它指向下一个链表结点。
定义最后还利用typedef关键字定义了一个名为LinkList的数据类型，它只是“struct
LinkNode *”的别名。也就是说，LinkList其实是一个链表结点指针类型的别名。Typedef关
键字用于为指定的类型声明一个新的名字，该名字可以像其他数据类型名称一样用于变量
的定义。Typedef的一般用法为：
typedef 类型声明 类型别名;

因为链表就像铁链一样，一环扣一环，只要记住第一环，那整个链表就被记住了。所
以，只需要定义一个LinkList类型的变量L（即LinkNode的指针变量），就可以记录和使用
整个链表，L就称为链表的头指针，其定义如下：
LinkList L=NULL; //定义链表头指针

在定义链表头指针L时，可将其初始值设为NULL。这是因为，对于指针变量，如果没
有指向任何存储单元，我们通常会把它赋值为NULL，NULL是一个常量值，表示指针不指
向任何一个存储单元。这样的指针称为空指针。
为了链表操作的方便，一般会在链表的第一个结点（保存第一个数据元素的结点）前
面增加一个结点，这个结点的data域不保存数据（也可以保存链表长度或别的信息），我
们将这个特殊的结点称为头结点。使用头结点的单向链表如图2-10所示，图中的符号

“∧”表示指针域为空指针（赋值为NULL）。

图2-10 单向链表
46 46

21X2204.indd 46 2019/9/26 13:53:08