2.3.3 单链表其它算法举例

例题 例2-8 以链表作存储结构解例2-5的问题，即将线性表 ( ,,…,,,,…, ) 改变成 ( ,,…,,,,…, ) 。

　解题分析：
　　因为对链表来说，"插入"和"删除"仅需修改指针即可完成，并且由于前 m 个元素之间和后 n 个元素之间的链接关系分别都不需要改变，则算法的实际操作为：动画

　　(1) 从链表中删除( ,,…, )；

　　(2) 将( ,,…, )链接到头结点之后；

　　(3) 将( ,,…, )链接到 之后。
　
  

  思考题 在以顺序表作存储结构时，我们曾分析过它的一个简单算法就是，将从 起到 的数据元素从原地删除后再插入到 之前，而在以顺序表作存储结构时因为需要大量移动元素而不能采用。那么在以链表作存储结构时能否采用这个算法呢？
　
　 		 
  算法 算法2.20
　　void exchange_L( SLink &L，int m )
　{
　　// 本算法实现单链表中前 m 个结点和后 n 个结点的互换
　　if ( m && L->next ) 　　　　// 链表不空且 m!=0
　　{
　　　p = L->next; k = 1;
　　　while( k< m && p )　　　　// 查找 所在结点
　　　{
　　　　p = p->next; ++k;
　　　} // while		  
  思考题 循环的条件中为什么要有p!=NULL的判断？

　　由于参数中没有给出 n 的值，只有在找到 之后加以判别。
　		  
  　　　if (p && p->next) 　　　　// n!=0 时才需要修改指针
　　　{
　　　　ha = L->next; 　　　　　 // 以指针 ha 记 结点的位置
　　　　L->next = p->next;　　　 // 将 结点链接在头结点之后
　　　　p->next = NULL;　　　　　// 设 的后继为空
　　　　q = L->next;　　　　　　 // 令q 指向 结点
　　　　while (q->next) q = q->next; // 查找 结点
　　　　q->next = ha; 　　　　　 // 将 结点链接到 结点之后
　　　} // if(p)
　　} // if(m)
　} // exchange_L

　　算法的时间复杂度为O (ListLength(L))。

  
  思考题 如果这里不加 p->next 是否为空的判别条件，下面哪一个语句会出问题？

　　整个算法就是对链表从头巡视到尾，两个单循环次数之和恰为表长。因此算法的时间复杂度为O(ListLength(L))。
　　此例充分显示了用"指针"指示"后继"的灵活性。