• <sup id="mk476"></sup>
    <dl id="mk476"></dl>
  • <progress id="mk476"><tr id="mk476"></tr></progress>
    <div id="mk476"><tr id="mk476"></tr></div>
    <sup id="mk476"><ins id="mk476"></ins></sup>
  • <progress id="mk476"></progress>
    <div id="mk476"></div>
    <div id="mk476"><tr id="mk476"></tr></div>
  • <div id="mk476"></div>
    <dl id="mk476"><s id="mk476"></s></dl><dl id="mk476"></dl><div id="mk476"></div>
  • <div id="mk476"></div>
    <dl id="mk476"><ins id="mk476"></ins></dl>

    第一節 如何用Go實現單鏈表

    一、概念介紹

    下面這副圖是我們單鏈表運煤車隊。

    每節運煤車就是單鏈表里的元素,每節車廂里的煤炭就是元素中保存的數據。前后車通過鎖鏈相連,作為單鏈表運煤車,從1號車廂開始,每節車廂都知道后面拉著哪一節車廂,卻不知道前面是哪節車廂拉的自己。第一節車廂沒有任何車廂拉它,我們就叫它車頭,第五節車廂后面拉其他車廂,我們稱為車尾。

    作為單鏈表它最大的特點就是能隨意增加車隊的長度,也能隨意減少車隊的長度。這是比數組公交車最大的優點。

    二、Go語言實現講解

    1、節點

    每節車廂都由車體、繩索和煤炭構成。在Go語言中表示這種自定義組合體的類型就是結構,當然為了通用性,我們這里要把車廂轉換成節點也就是元素,煤炭轉換成數據,繩索轉換成指針。

        type Node struct {
            data Object
            next *Node
        }

    用張圖來描述這種對應關系。

    這里結構體Node表示車廂,data表示煤炭用Object類型,next是牽著下節車廂的繩索,用指針表示。

    對于車廂來說,除了放煤炭外,還能放瓜果、衣物、飯菜等等,所以這里data的類型必須通用,當然Go里是沒有Java里的Object類型的,所以我們就自己定義了一個。

        type Object interface{}

    2、鏈表

    光有車廂還不夠,我們還要描述車廂組成的車隊。每個單鏈表車隊都有車頭、車尾和車廂數量,我們同樣以結構來表現。

        type List struct {
            size uint64 // 車輛數量
            head *Node  // 車頭
            tail *Node  // 車尾
        }

    3、方法

    (1)初始化

    第一步就是組裝單鏈表車隊,這就是初始化。不過開始的時候車隊是個空殼,一個車廂沒有。

        func (list *List) Init() {
            (*list).size = 0    // 此時鏈表是空的
            (*list).head = nil  // 沒有車頭
            (*list).tail = nil  // 沒有車尾
        }

    (2)添加元素

    當前的單鏈表是空的,所以我們要向里面添加元素。

        func (list *List) Append(node *Node) {
            (*list).head = node // 這是單鏈表的第一個元素,也是鏈表的頭部
            (*list).tail = node // 同時是單鏈表的尾部
            (*list).size = 1    // 單鏈表有了第一個元素
        }

    現在單鏈表有了第一個元素,我還想再添加一個元素,當然是添加到單鏈表尾部。

        func (list *List) Append(node *Node) {
            if (*list).size == 0 { // 無元素的時候添加
                (*list).head = node // 這是單鏈表的第一個元素,也是鏈表的頭部 
                (*list).tail = node // 同時是單鏈表的尾部
                (*list).size = 1    // 單鏈表有了第一個元素
            } else { // 有元素了再添加
                oldTail := (*list).tail
                (*oldTail).next = node  // node放到尾部元素后面
                (*list).tail = node     // node成為新的尾部
                (*list).size++          // 元素數量增加
            }
        }

    分析上面的代碼存在3處疑點,元芳你怎么看?屬下認為
    第一,node如果為空,則添加無任何意義;
    第二,代碼中存在重復的地方;
    這第三么,卑職如何才能知道新增結果?
    下面大衛哥順著元芳的思路改進下代碼。

        func (list *List) Append(node *Node) bool {
            if node == nil {
                return false
            }
            
            (*node).next = nil
            // 將新元素放入單鏈表中
            if (*list).size == 0 { 
                (*list).head = node  
            } else { 
                oldTail := (*list).tail
                (*oldTail).next = node  
            }
        
            // 調整尾部位置,及鏈表元素數量
            (*list).tail = node // node成為新的尾部  
            (*list).size++      // 元素數量增加
        
            return true
        }

    (3)插入元素

    一天領導讓大衛哥把他小舅子安排到第一個,于是大衛哥為了拍好領導馬屁。絞盡腦汁弄了一個方法。

       func (list *List) Insert(node *Node) bool {
          if node == nil {
              return false
          }
     
          (*node).next = (*list).head   // 領導小舅子排到之前第一名前面
          (*list).head = node           // 領導小舅子成為第一名
          (*list).size++
          return true
      }

    來托關系插隊的人越來越多,領導的關系戶不能動,只能插后面人的隊了。于是大衛哥又修改了代碼,增加了位置參數。

        func (list *List) Insert(i uint,node *Node) bool {
            // 空的節點、索引超出范圍和空鏈表都無法做插入操作
            if node == nil || i > (*list).size || (*list).size == 0 {
                return false
            }
        
            if i == 0 { // 直接排第一,也就領導小舅子才可以
                (*node).next = (*list).head
                (*list).head = node
            } else {
                // 找到前一個元素
                preItem := (*list).head
                for j := 1 ; j < i; j++ { // 數前面i個元素
                    preItem = (*preItem).next
                }
                // 原來元素放到新元素后面,新元素放到前一個元素后面
                (*node).next = (*preItem).next
                (*preItem).next = preItem
            }
        
                (*list).size++ 
        
                return true
        }

    (4)刪除元素

    插隊的關系戶太多,影響了正常排隊的人,被人投訴,大衛哥只好想辦法刪除一些。

        func (list *List) Remove(i uint, node *Node) bool {
            if i >= (*list).size {
                return false
            }
            
            if i == 0 { // 刪除頭部
                node = (*list).head
                (*list).head = (*node).next
                if (*list).size == 1 { // 如果只有一個元素,那尾部也要調整
                    (*list).tail = nil
                }
            } else {
                preItem := (*list).head
                for j := 1; j < i; j++ {
                    preItem = (*preItem).next
                }
            
                node = (*preItem).next
                (*preItem).next = (*node).next
        
                if i == ((*list).size - 1) { // 若刪除的尾部,尾部指針需要調整
                    (*list).tail = preItem
                }
            }
            (*list).size--
            return true
        }

    (5)獲取

    為了獲取某個位置的元素,我們需要一個方法。

        func (list *List) Get(i uint) *Node {
            if i >= (*list).size {
                return nil
            }
        
            item := (*list).head
            for j := 0; j < i ; j++ {    // 從head數i個
                item = (*item).next
            }
        
            return item
        }

    到這里基本框架已經出來了,不過還有幾個接口還沒實現,作為課后作業。

    三、小結

    單鏈表就和列車類似,一個接著一個,所以本節從列車類比介紹了單鏈表的Go語言實現。在接口實現部分大衛哥以序號作為鏈表中每個節點的操作關鍵字。在實際應用中,我們往往以data中的某一個字段作為操作關鍵字。所以這也衍生出鏈表的不同接口,大家可以參考大衛哥留的鏈接中的代碼實現作為理解。同時有些實現將表頭獨立出來并不存放數據,這在一定程度上簡化了代碼的實現。

    代碼下載

    四、習題

    (1)補全GetSize,RemoveAll,GetHead和GetTail的定義和實現。
    (2)以data作為參數,考慮單鏈表的實現。
    (3)將單鏈表的head獨立出來,此時的head是獨立的,不存放data,如下圖,考慮單鏈表的實現,并比較這種實現。

    (4)如果將head和tail都獨立出來,都不存放data,此時的單鏈表如何實現?這樣實現的代碼在插入刪除操作時候是不是更容易點?

    posted @ 2018-09-22 21:02 懶人記 閱讀(...) 評論(...) 編輯 收藏
    江苏11选5软件