全国计算机等级考试三级数据库考点分析之数据结构与算法(5)

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

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、可利用空间表

　　可利用空间表的作用是管理可用于链表插人和删除的节点，当链表插人需要一个新节点时，就从可利用空间表中删除第一个节点，用这个节点去做链表插人；当从链表中删除一个节点时，就把这个节点插人到可利用空间表的第一个节点前面。