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

數據結構之單鏈表基本運算的實現[9]

2013-11-15 15:13:17  來源: 數據結構 

  if (!p)

  { printf(參數 i 錯);

  return (); /*第i個結點不存在不能刪除*/

  }

  q=p>next; /*q指向第i個結點*/

  p>next=q>next; /*從鏈表中刪除*/

  free(q); /*釋放*s */

  return ();

  }

  該算法同插入算法一樣時間主要消耗在查找第i個元素結點上故其時間復雜度為O(n)

  另外在上面插入和刪除的算法中第一個元素結點的處理和其它結點是相同的因為在第一個元素結點之前有一個頭結點(可以看作是第 個結點)所以我們在查找第i個元素結點時只要i值合法總能找到第i個結點的指針處理起來非常方便;如果采用不帶頭結點的單鏈表則需要對插入位置具體考慮在第一個元素結點之前插入時它沒即可有直接前驅結點需修改頭指針;而在其它結點之前插入時只要找到前驅結點地址(指針)進行正常插入即可在不帶頭結點的鏈表中刪除結點時刪除第一個結點和其它結點的處理也是不同的刪除第一個結點要修改頭指針變量其它結點刪除只要修改其直接前驅的指針域即可有興趣的讀者可以考慮用不帶頭結點的單鏈表實現插入刪除操作比較一下它們的區別以便進一步理解單鏈表的插入和刪除操作的實現總之在通常情況下無表頭結點的單鏈表在處理時往往比有表頭結點的單鏈表更為復雜

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


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