天天看點

離散存儲【連結清單】

定義:什麼是連結清單

    1、n個節點離散分布

    2、彼此通過指針相連

    3、每個節點隻有一個前驅節點,每個節點隻有一個後續節點

    4、首節點沒有前驅節點,尾節點沒有後續節點

專業術語:

    1、首節點:第一個存放有效資料的節點

    2、尾節點:最後一個存放有效數組的節點

    3、頭節點:頭節點的資料類型和首節點類型一樣,第一個存放有效資料節點(首節點)

       之前的節點,頭節點不存放有效資料,加頭節點的目的主要是為了友善對連結清單的操作。

    4、頭指針:指向頭節點的指針變量

    5、尾指針:指向尾節點的指針變量

如果希望通過一個函數來對連結清單進行處理,至少需要接受連結清單的哪些參數:

    隻需要一個參數:頭指針

    因為通過頭指針可以推算對外連結表的其他所有資訊

    一個節點整體來說隻包含兩部分,一部分是資料域,一部分是指針域,

    資料域是節點存放的有效資料,指針域是指向下一個與自身類型一樣的節點

分類:

    1、單向連結清單

    2、雙向連結清單

       每一個節點有兩個指針域

    3、循環連結清單

       能通過任何一個節點找到其他所有的節點,尾節點指向頭節點

    4、非循環連結清單

算法:

    1、周遊

    2、查找

    3、清空

    4、銷毀

    5、求長度

    6、排序

    7、删除節點

    8、插入節點

    9、反轉