数据结构知识梳理 第二章 线性表

本系列通用书本：数据结构（C语言版 第2版） 严蔚敏等编著

目录

前言

一、知识框架

二、知识点

1.首元节点、头节点、头指针

2.链表增加头节点的作用

3.循环链表、双向链表、双向循环链表

---

前言

对第二章 线性表 的知识梳理

---

一、知识框架

二、知识点 1.首元节点、头节点、头指针

首元节点：链表中存储第一个数据元素的节点。

头节点：首元节点之前附设的一个节点，其指针域指向首元节点。头节点的数据域可以不存储任何信息，也可以存储与数据元素类型相同的其他附加信息。

头指针：指向链表中第一个节点的指针。

若链表设有头节点，则头指针->头节点->首元节点。

2.链表增加头节点的作用

（1）便于首元节点的处理

首元节点地址保存在头节点的指针域中，则对链表的第一个数据元素的 *** 作与其他数据元素的 *** 作相同，无须特殊处理。

（2）便于空表与非空表的统一处理

无论链表是否为空，头指针都是指向头节点的非空指针。判定空表的条件可统一表示。

3.循环链表、双向链表、双向循环链表

（单向）循环链表：表中最后一个节点的指针域指向头节点，整个链表形成一个环。

双向链表：节点中有两个指针域，一个指向直接后继，另一个指向直接前驱。

双向循环链表：最后一节点的后继指针指向头节点，头节点的前驱指针指向最后一节点。