等级考试三级数据库考点分析：数据结构与算法

2．2线性表

　　线性表的逻辑结构是由n个数据元素组成的一个有限序列。线性表中所包含元素的个数叫线性表的长度．它是可变的．可同线性表中增加或删除元素。线性表包括顺序表、链表、散列表和串等。

1、线性链表
　　线性链表也称为单链表，其每个一节点中只包含一个指针域。对链表进行插人、删除运算时只需改变节点中指针域的值。
　　（1） 在指针一P后插人指针9的关键运算步骤：        
q ↑. link：＝P↑．link：
        p ↑. link：＝q；
　　（２）删除指针P后继节点q的关键运算步骤：
        q：＝p↑ . link；
        p↑. link：＝q↑．link；
　　（3）在第一个节点（或称头节点）前插人一个指针P的关键运算步骤：
        p↑. link：＝head；
          head：二P；
　　（４）删除表中头节点的关键运算步骤：
        head：＝head↑ . link：

 2、双链表
　　在双链表中，每个节点中设置有两个指针域，分别用以指向其前驱节点和后继节点。rlink指向节点的后继，llink指向节点的前驱，这样的结构方便向后和向前查找。
　　（l）若要在双链表中删除指针P所指的节点时，只需修改其前驱的rlink字段和后继的Mink字段，步骤如下：
        p↑ . llink↑. rlink：＝p↑. rlink；
        P↑T．rlink↑. llink：＝P↑．llink；
　　 (2)如果要在指针P后面插人指针q所指的新节点，只需修改P指针所指节点的rlink字段和原来后继均Ilink字段，并重新设置q所指节点的Mink和rlink值，步骤如下：
        q ↑. Mink：＝P：
        q↑．rlink：＝P↑．rlink;
        P↑．rlink r. Rink：＝q；
        p↑．rlink：＝q;
 
3、可利用空间表
 
　　可利用空间表的作用是管理可用于链表插人和删除的节点，当链表插人需要一个新节点时，就从可利用空间表中删除第一个节点，用这个节点去做链表插人；当从链表中删除一个节点时，就把这个节点插人到可利用空间表的第一个节点前面。