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

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

考点13 线性链表的基本运算
　　线性链表的运算主要有以下几个：
　　(l)在线性链表中包含指定元素的结点之前插入一个新元素；
　　(2)在线性链表中删除包含指定元素的结点；
　　(3)将两个线性链表按要求合并成一个线性表；
　　 (4)将一个线性链表按要求进行分解；
　　 (5)逆转线性链表；
　　 (6)复制线性链表；
　　 (7)线性链表的排序；
　　 (8)线性链表的查找。
　　1在线性镬表中查找指定元素
　　在对线性链表进行插入或删除的运算中，总是首先需要找到插入或删除的位置，这就需要对线性链表进行扫描查找，在线性链表中寻找包含指定元素的前一个结点。
　　在线性链表中，即使知道被访问结点的序号a，也不能像顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域Next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。
　　在链表中，查找是否有结点值等于给定值x的结点，若有的话，则返回首次找到的其值为x的结点的存储位置；否则返回NULL。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值x作比较。
　　2线性链表的插入
　　线性链表的插入是指在链式存储结构下的线性链表中插入一个新元素。
　　插入运算是将值为X的新结点插入到表的第i个结点的位置上，即插入到ai-1，与ai之间。因此，我们必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点*p，并令结点，p的指针域指向新结点，新结点的指针域指向结点ai
　　由线性链表的插入过程可以看出，由于插入的新结点取自于可利用栈，因此，只要可利用栈不空，在线性链表插入时总能取到存储插入元素的新结点，不会发生“上溢”的情况。而且，由于可利用栈是公用的，多个线性链表可以共享它，从而很方便地实现了存储空间的动态分配。另外，线性链表在插入过程中不发生数据元素移动的现象，只要改变有关结点的指针即可，从而提高了插入的效率。
　　3多线性链表的删除
　　线性链表的删除是指在链式存储结构下的线性链表中删除包含指定元素的结点。
　　删除运算是将表的第i个结点删去。因为在单链表中结点a的存储地址是在其直接前趋结点ai-1，的指针域Next中，所以我们必须首先找到ai-1的存储位置p。然后令p->Next指向ai的直接后件结点，即把ai从链上摘下。最后释放结点a的空间。
　　从线性链表的删除过程可以看出，从线性链表中删除一个元素后，不需要移动表中的数据元素，只要改变被删除元素所在结点的前一个结点的指针域即可。另外，由于可利用栈是用于收集计算机中所有的空闲结点，因此，当从线性链表中删除一个元素后，该元素的存储结点就变为空闲，应将空闲结点送回到可利用栈。
考点14 线性双向链表的结构及其基本运算
　　1什么是双向链表
　　在单链表中，从某个结点出发可以直接找到它的直接后件，时间复杂度为O(1)，但无法直接找到它的互接前件；在单循环链表中，从某个结点出发可以直接找到它的直接后件，时间复杂度仍为O(1)，直接找到它的直接前件，时间复杂度为O(n)。有时，希望能快速找到一个结点的直接前件，这时，可以在单链表中的结点中增加一个指针域指向它的直接前件，这样的链表，就称为双向链表(一个结点中含有两个指针)。如果每条链构成一个循环链表，则会得到双向循环链表
　　2双向链表的基本运算
　　(l)插入：在HEAD为头指针的双向链表中，在值为Y的结点之后插入值为X的结点，插入结点的指针变化。如图1-20所示(若改为在值为Y的结点之前插入值为X的结点，可以做类似分析)。
(2)删除：在以HEAD为头指针的双向链表中删除值为X的结点，删除算法的指针变化，如图1-21所示。
考点15 循环链表的结构及其基本运算
　　单链表上的访问是一种顺序访问，从其中的某一个结点出发，可以找到它的直接后件，但无法找到它的直接前件。
　　在前面所讨论的线性链表中，其插入与删除的运算虽然比较方便，但还存在一个问题，在运算过程中对于空表和对第一个结点的处理必须单独考虑，使空表与非空表的运算不统一。
　　因此，我们可以考虑建立这样的链表，具有单链表的特征，但又不需要增加额外的存贮空间，仅对表的链接方式稍做改变，使得对表的处理更加方便灵活。从单链表可知，最后一个结点的指针域为NULL，表示单链表已经结束。如果将单链表最后一个结点的指针域改为存放链表中头结点(或第一个结点)的地址，就使得整个链表构成一个环，又没有增加额外的存储空间