等级考试公共基础考点分析之数据结构与算法(7)

文章作者 100test 发表时间 2007:03:10 16:45:28
来源 100Test.Com百考试题网

1.5 线性链表
考点12 线性单链表的结构及其基本运算
　　 1什么是线性链表
　　 (l)线性表顺序存储的缺点
　　 ①在一般情况下，要在顺序存储的线性表中插入一个新元素或删除一个元素时，为了保证插入或删除后的线性表仍然为顺序存储，则在插入或删除过程中需要移动大量的数据元素。因此采用顺序存储结构进行插入或删除的运算效率很低；
　　 ②当为一个线性表分配顺序存储空间后，如果出现线性表的存储空间已满，但还需要插入新的元素时栈会发生“上溢”错误；
　　 ③计算机空间得不到充分利用，并且不便于对存储空间的动态分配。
　　(2)线性表链式的基本概念
　　在定义的链表中，若只含有一个指针域来存放下一个元素地址，称这样的链表为单链表或线性链表。
　　在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点(即前件或后件)。如图1-13所示。
　　2线性单链表的存储结构
　　用一组任意的存储单元来依次存放线性表的结点，这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后件结点的地址(或位置)信息，这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构，
　　链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起。由于上述链表的每一个结点只有一个链域，故将这种链表称为单链表(Single Linked)。
　　显然，单链表中每个结点的存储地址是存放在其前驱结点Next域中，而开始结点无前驱，故应设头指针HEAD指向开始结点。同时，由于终端结点无后件，故终端结点的指针域为空，即NULL。
　　3带链的栈与队列
　　(1)栈也是线性表，也可以采用链式存储结构。在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈
(2)队列也是线性表，也可以采用链式存储结构，