(17)--第2章线性表第4讲-单链表的基本算法.pdfVIP

2.3线性表的链式表示和实现

2.3.1线性链表R

线性表的单链表存储方法：用一个指针表示结点间

Z

的逻辑关系。因此单链表的一个存储结点包含两个部，

结点的形式如下：L

-

datanext

U

data：为数据域，用于存储线性表的一个数据元素，

D

也就是说在单链表中一个结点存放一个数据元素。

Q

next：为指针域或链域，用于存放一个指针，该指针

指向后继元素对应的结点，也就是说单链表中结点的

指针用于表示后继关系。

特点

每个数据元素由结点(Node)构成。

datanextR

线性结构Z

L

heada1a2-a3a4a5∧

结点可以连续，可以不连续存储。

U

结点的逻辑顺序与物理顺序可以不一致。

表可扩充。D

链表中第一个元素结点称为首结点；最后一个元素称为

Q

尾结点，其指针域(next)为空(NULL)。

单链表分为带头结点和不带头结点两种类型。在

许多情况下，带头结点的单链表能够简化运算的

实现过程。R

Z

因此在后续讨论的单链表，除特别指出外均指带

L

头结点的单链表。-

U

D

Q

假设数据元素的类型为ElemType。单链表的结点类

型声明如下：R

typedefintElemType;Z

typedefintStatus;L

#defineOK1

-

#defineERROR0

//结点的C语言描述

U

typedefstructnode{

D

ElemTypedata;

structnode*next;

Q

}LNode,*LinkList;

2