熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構考研分類復習真題 第二章 答案[40]

2013-11-15 15:23:04  來源: 數據結構 

  類似本題的另外敘述題的解答

  ()[題目分析] 本題應先查找第i個結點記下第i個結點的指針然後從第i+個結點起直至第m(<i<m)個結點止依次插入到第i個結點之後最後將暫存的第i個結點的指針指向第m結點形成新的循環鏈表結束了倒置算法

  LinkedList PatternInvert(LinkedList Lint  im)∥L是有m個結點的鏈表的頭結點的指針表中從第i(<i<m)個結點到第m個結點構成循環部分鏈表本算法將這部分循環鏈表倒置
  {if(i<|| i>=m || m<){printf(%d%d參數錯誤\nim);exit();}
  p=L>next>next;∥p是工作指針初始指向第二結點(已假定i>)
  pre=L>next;∥pre是前驅結點指針最終指向第i個結點
  j=;∥計數器
  while(j<i)∥查找第i個結點
  {j++;pre=p;p=p>next;}∥查找結束p指向第i個結點
  q=p;∥暫存第i個結點的指針
  p=p>next;∥p指向第i+個結點准備逆置
  j+=;∥上面while循環結束時j=i現從第i+結點開始逆置
  while(j<=m)
  {r=p>next;∥暫存p的後繼結點
  p>next=pre>next;∥逆置p結點
  pre>next=p;
  p=r;∥p恢復為當前待逆置結點
  j++;∥計數器增
  }
  q>next=pre>next;∥將原第i個結點的後繼指針指向原第m個結點

  [算法討論] 算法中未深入討論imj的合法性因題目的條件是m><i<m因此控制循環並未用指針判斷(如一般情況下的p!=null)結束循環也未用指針判斷注意最後一句q>next=pre>next實現了從原第i個結點到原第m個結點的循環最後pre>next正是指向原第m個結點不可用p>next代替pre>next

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  


From:http://tw.wingwit.com/Article/program/sjjg/201311/23331.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.