2011年计算机二级公共基础知识辅导笔记（5）

文章作者 100test 发表时间 2011:03:18 18:47:49
来源 100Test.Com百考试题网

　　1.5 链表

　　在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点（即前件或后件）。

　　链式存储方式既可用于表示线性结构，也可用于表示非线性结构。

　　（1）线性链表

　　线性表的链式存储结构称为线性链表。

　　在某些应用中，对线性链表中的每个结点设置两个指针，一个称为左指针，用以指向其前件结点；另一个称为右指针，用以指向其后件结点。这样的表称为双向链表。

　　在线性链表中，各数据元素结点的存储空间可以是不连续的，且各数据元素的存储顺序与逻辑顺序可以不一致。在线性链表中进行插入与删除，不需要移动链表中的元素。

　　线性单链表中，HEAD称为头指针，HEAD=NULL（或0）称为空表。

　　如果是双项链表的两指针：左指针（Llink）指向前件结点，右指针（Rlink）指向后件结点。

　　线性链表的基本运算：查找、插入、删除。

　　（2）带链的栈

　　栈也是线性表，也可以采用链式存储结构。带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。

　　#ff0000>