2011年计算机二级公共基础知识考点知识5

　　1.5.1线性链表的基本概念 (P20—P23)

　　由于线性表的顺序存储结构存在以上这些缺点，对于大的线性表，特别是元素变动频繁的大线性表不宜采用顺序存储结构，而是采用下面要介绍的链式存储结构。

　　在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。

　　在链式存储结构中，存储数据结构的存储空间可以下连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。

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

　　1. 线性链表

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

　　2. 带链的栈

　　栈也是线性表，也可以采用链式存储结构。

　　3. 带链的队列

　　与栈类似，队列也是线性表，也可以采用链式存储结构。

　　1.5.2线性链表的基本运算 (P23—P25)

　　线性链表在插入过程中不发生数据元素移动的现象，只需改变有关结点的指针即可，从而提高了插入的效率。

　　从线性链表的删除过程可以看出，在线性链表中删除一个元素后，不需要移动表的数据元素，只需改变被删除元素所在结点的前一个结点的指针域即可。

　　1.5.3循环链表及其基本运算 (P25—P26)

　　循环链表具有以下两个特点：

　　(1) 在循环链表中增加了一个表头结点，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。

　　(2) 循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。