c++ - 用O(1)时间循环删除链表?
伊谢尔伦
伊谢尔伦 2017-04-17 11:20:53
0
2
647

在一本数据结构书上看到了这个问题,是个思考题,没有给答案。网上找了找,似乎也没有。有没有大神提供个思路?

伊谢尔伦
伊谢尔伦

小伙看你根骨奇佳,潜力无限,来学PHP伐。

全部回覆(2)
左手右手慢动作

我同意上面brayden的說法,這個問題在資料結構與演算法上沒有任何意義,應該是樓主看錯題了。問題是O(1)時間刪除循環單鍊錶的某個節點才對,下面簡單給出O(1)時間刪除循環單鍊錶的某個節點的解:
假定要刪除的節點是ListNode *toBeDeleted
要求在O(1)時間內刪除,就肯定不能用遍歷了,由於是單項鍊表,不用遍歷是找不到該節點的前一個節點的,所以就不能用常規鍊錶刪除的方法了。
由於我們知道要刪除的節點ListNode *toBeDeleted,所以我們可以直接得到它的後一個節點ListNode *pNext。我們可以用pNext的內容覆蓋掉toBeDeleted節點,然後將節點toBeDeleted連結到pNext的下一個節點之後將pNext節點刪除即可。以下是一個簡單的示意圖(假設要刪除i):

原理很簡單就是:完全複製下一個節點,然後在刪除下一個節點,以達到刪除本節點的假象。

阿神

之前用過類似的資料結構,沒必要寫什麼記憶體分配函數。主要實現想法如下:

  1. 一開始就申請連續的N塊記憶體。每塊記憶體內容為該區塊記憶體是否使用的標記和鍊錶節點資料。
  2. 新增節點時在連續的記憶體中找一塊未使用的記憶體區塊,標記為使用。
  3. 釋放節點時此區塊記憶體標記為未使用。
  4. 刪除鍊錶時釋放掉連續的N塊記憶體即可。
  5. 其他如申請的連續記憶體用完之類的問題基本上有解決方法。

但是這樣的做的主要問題是:如果節點是包含資源的,那麼資源必然會洩漏。

熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板