亚洲中文字幕无码乱线,亚洲成h人无码动漫无遮挡,欧美大片一区

主頁(yè) > 知識(shí)庫(kù) > 詳解go語(yǔ)言單鏈表及其常用方法的實(shí)現(xiàn)

詳解go語(yǔ)言單鏈表及其常用方法的實(shí)現(xiàn)

目的

在刷算法題中經(jīng)常遇到關(guān)于鏈表的操作，在使用go語(yǔ)言去操作鏈表時(shí)不熟悉其實(shí)現(xiàn)原理，目的是為了重溫鏈表這一基礎(chǔ)且關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)。

1、鏈表的特點(diǎn)和初始化

1.1、鏈表的特點(diǎn)
用一組任意的存儲(chǔ)單元存儲(chǔ)線(xiàn)性表的數(shù)據(jù)元素(這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的)

1.2、結(jié)點(diǎn)

結(jié)點(diǎn)(node)

數(shù)據(jù)域 => 存儲(chǔ)元素信息
指針域 => 存儲(chǔ)結(jié)點(diǎn)的直接后繼，也稱(chēng)作指針或鏈

首元結(jié)點(diǎn) 是指鏈表中存儲(chǔ)的第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)
頭結(jié)點(diǎn) 是在首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，其指針域指向首元結(jié)點(diǎn)(非必須)
頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針

1.3、單鏈表
特點(diǎn)

每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域
單鏈表是非隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)，要取得第i個(gè)數(shù)據(jù)元素必須從頭指針出發(fā)，順鏈進(jìn)行尋找，也稱(chēng)為順序存取的存取結(jié)構(gòu)

1.4、單鏈表的常用操作

本文主要實(shí)現(xiàn)了單鏈表的以下操作

判斷是否為空
獲取鏈表長(zhǎng)度
在頭部插入元素
在尾部插入元素
刪除指定位置元素
刪除指定值的元素
查找是否包含指定值
查找指定位置元素的值
遍歷鏈表所有結(jié)點(diǎn)

1.5、單鏈表的初始化

//定義單鏈表結(jié)構(gòu)體
type Node struct {
  data interface{} //數(shù)據(jù)域
  next *Node    //指針域
}
type List struct {
  length  int //儲(chǔ)存鏈表的長(zhǎng)度
  headNode *Node
}

/*單鏈表的初始化
1、生成新結(jié)點(diǎn)作為頭結(jié)點(diǎn)，用頭指針指向頭結(jié)點(diǎn)
2、頭結(jié)點(diǎn)的指針域置空
*/
func InitList() *List {
  //即構(gòu)造一個(gè)空的單鏈表L(包含頭指針)
  node := new(Node)
  L := new(List)
  L.headNode = node
  return L
}

2、單鏈表的插入

先講單鏈表的插入有利于后續(xù)相關(guān)操作的實(shí)現(xiàn)

2.1、在指定位置插入元素

/*單鏈表的插入=>將值為e的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上，即插入到結(jié)點(diǎn)a(i-1)與a(i)之間
1、查找結(jié)點(diǎn)a(i-1)并由指針p指向該結(jié)點(diǎn)
2、生成一個(gè)新結(jié)點(diǎn)*s
3、將新結(jié)點(diǎn)*s的數(shù)據(jù)域置為e
4、將新結(jié)點(diǎn)*s的指針域指向結(jié)點(diǎn)a(i)
5、將結(jié)點(diǎn)*p的指針域指向新結(jié)點(diǎn)*s
*/
func (list *List) InsertElem(index int, v interface{}) {
  if index = 0 || index > list.length {
    fmt.Println("err")
  } else {
    pre := list.headNode
    node := Node{data: v}
    if index == 1 {
      node.next = pre
      list.headNode = node
    } else {
      for count := 1; count  index-1; count++ {
        pre = pre.next
      }
      node.next = pre.next
      pre.next = node
    }
    list.length--
  }
}

2.2、在頭部插入元素

func (list *List) AddElem(v interface{}) {
  node := Node{data: v}
  if list.IsNull() { //處理空表的插入，否則會(huì)導(dǎo)致一個(gè)空的頭結(jié)點(diǎn)后移
    list.headNode = node
    list.length++
    return
  }
  node.next = list.headNode
  list.headNode = node
  list.length++
  return
}

2.3、在尾部插入元素

func (list *List) AppendElem(v interface{}) {
  node := Node{data: v}
  if list.IsNull() {
    list.headNode.next = node
  } else {
    cur := list.headNode
    for cur.next != nil {
      cur = cur.next
    }
    cur.next = node
  }
  list.length++
  return
}

3、單鏈表的刪除

3.1、刪除指定值的元素

/*單鏈表的刪除
1、查找結(jié)點(diǎn)a(i-1)并由指針p指向該結(jié)點(diǎn)
2、臨時(shí)保存待刪除結(jié)點(diǎn)a(i)的地址在q中，以備釋放
3、將結(jié)點(diǎn)*p的指針域指向a(i)的直接后繼結(jié)點(diǎn)
4、釋放結(jié)點(diǎn)a(i)的空間
*/
func (list *List) DeleteElem(index int) {
  if index = 0 || index > list.length {
    fmt.Println("刪除位置不合理")
    return
  } else {
    pre := list.headNode
    if index == 1 {
      list.headNode = pre.next
    } else {
      pre := list.headNode
      for count := 1; count  index-1; count++ {
        pre = pre.next
      }
      pre.next = pre.next.next
    }
    list.length--
  }
}

3.2、刪除指定位置的元素

func (list *List) RemoveElem(v interface{}) {
  pre := list.headNode
  if pre.data == v {
    list.headNode = pre.next
    fmt.Println("ok")
  } else {
    for pre.next != nil {
      if pre.next.data == v {
        pre.next = pre.next.next
        fmt.Println("ok")
        return
      } else {
        pre = pre.next
      }
    }
    fmt.Println("fail")
    return
  }
}

4、單鏈表的查詢(xún)

4.1、查找是否包含指定值

/*單鏈表的按值查找
1、用指針p指向首元結(jié)點(diǎn)
2、從首元結(jié)點(diǎn)開(kāi)始以此順著鏈域next向下查找，只要指向當(dāng)前結(jié)點(diǎn)的指針p不為空，
并且p所指結(jié)點(diǎn)的數(shù)據(jù)域不等于給定值e，則執(zhí)行以下操作：p指向下一個(gè)結(jié)點(diǎn)
3、返回p。若查找成功，p此時(shí)即為結(jié)點(diǎn)的地址值，若查找失敗，p的值即為NULL。
*/
func (list *List) LocateElem(v interface{}) bool {
  if IsNull() {
    fmt.Println("err")
  } else {
    pre := list.headNode
    for pre != nil {
      if pre.data == v {
        return true
      }
      pre = pre.next
    }
    return false
  }
}

4.2、查找指定位置的值

/*單鏈表的取值
1、用指針P指向首元結(jié)點(diǎn)，用j做計(jì)數(shù)器初值賦為1
2、從首元結(jié)點(diǎn)開(kāi)始依次順著鏈域(指針域)next向下訪(fǎng)問(wèn)，
只要指向當(dāng)前結(jié)點(diǎn)的指針P不為空，并且沒(méi)有達(dá)到序號(hào)為i的結(jié)點(diǎn)，則循環(huán)執(zhí)行以下操作：
  2.1、P指向下一個(gè)結(jié)點(diǎn)
  2.2、計(jì)數(shù)器j相應(yīng)加1
3、退出循環(huán)時(shí)，如果指針P為空，或者計(jì)數(shù)器j大于i，說(shuō)明指定的序號(hào)i值不合法(i大于表長(zhǎng)n或i小于等于0)，
取值失敗返回ERROR；否則取值成功，
此時(shí)j==i時(shí)，P所指的結(jié)點(diǎn)就是要找的第i個(gè)結(jié)點(diǎn)，用參數(shù)e保存當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域，返回OK
*/
func (list *List) GetElem(index int) int {
  if index = 0 || index > list.length {
    fmt.Println("err")
    return
  } else {
    pre := list.headNode
    for j := 0; j  index; j++ {
      if pre != nil {
        pre = pre.next
      }
    }
    return pre.data
  }
}

4.3、遍歷單鏈表

func (list *List) ShowList() {
  if !list.IsNull() {
    cur := list.headNode
    for {
      fmt.Printf("\t%v", cur.data)
      if cur.next != nil {
        cur = cur.next
      } else {
        break
      }
    }
  }
}

5、完整代碼及結(jié)果展示

package main

import "fmt"

//定義單鏈表結(jié)構(gòu)體

type Node struct {
  data interface{} //數(shù)據(jù)域
  next *Node    //指針域
}
type List struct {
  length  int //儲(chǔ)存鏈表的長(zhǎng)度
  headNode *Node
}

/*
type Method interface {
  IsNull() bool          //1、判斷是否為空
  GetLength() int         //2、獲取鏈表長(zhǎng)度
  InsertElem(i int, v interface{}) //3、在指定位置添加元素
  AddElem(v interface{})      //4、在頭部插入元素
  AppendElem(v interface{})    //5、在尾部插入元素
  DeleteElem(i int)        //6、刪除指定位置元素
  RemoveElem(v interface{})    //7、刪除指定值的元素
  ContaineElem(v interface{}) bool //8、是否包含指定值的元素
  LocateElem(i int) interface{}  //9、查找指定位置元素的值
  ShowList()            //10、遍歷鏈表所有結(jié)點(diǎn)
}
*/
/*單鏈表的初始化
1、生成新結(jié)點(diǎn)作為頭結(jié)點(diǎn)，用頭指針指向頭結(jié)點(diǎn)
2、頭結(jié)點(diǎn)的指針域置空
*/
func InitList() *List {
  //即構(gòu)造一個(gè)空的單鏈表L(包含頭指針)
  node := new(Node)
  L := new(List)
  L.headNode = node
  return L
}

/*單鏈表的取值
1、用指針P指向首元結(jié)點(diǎn)，用j做計(jì)數(shù)器初值賦為1
2、從首元結(jié)點(diǎn)開(kāi)始依次順著鏈域(指針域)next向下訪(fǎng)問(wèn)，只要指向當(dāng)前結(jié)點(diǎn)的指針P不為空，
并且沒(méi)有達(dá)到序號(hào)為i的結(jié)點(diǎn)，則循環(huán)執(zhí)行以下操作：
  2.1、P指向下一個(gè)結(jié)點(diǎn)
  2.2、計(jì)數(shù)器j相應(yīng)加1
3、退出循環(huán)時(shí)，如果指針P為空，或者計(jì)數(shù)器j大于i，說(shuō)明指定的序號(hào)i值
不合法(i大于表長(zhǎng)n或i小于等于0)，取值失敗返回ERROR；否則取值成功，
此時(shí)j==i時(shí)，P所指的結(jié)點(diǎn)就是要找的第i個(gè)結(jié)點(diǎn)，用參數(shù)e保存當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域，返回OK
*/
func (list *List) GetElem(index int) int {
  if index = 0 || index > list.length {
    return 0
  } else {
    pre := list.headNode
    for j := 0; j  index-1; j++ {
      if pre != nil {
        pre = pre.next
      }
    }
    return pre.data.(int)
  }
}

/*單鏈表的按值查找
1、用指針p指向首元結(jié)點(diǎn)
2、從首元結(jié)點(diǎn)開(kāi)始以此順著鏈域next向下查找，只要指向當(dāng)前結(jié)點(diǎn)的
指針p不為空，并且p所指結(jié)點(diǎn)的數(shù)據(jù)域不等于給定值e，則執(zhí)行以下操作：
  2.1、p指向下一個(gè)結(jié)點(diǎn)
3、返回p。若查找成功，p此時(shí)即為結(jié)點(diǎn)的地址值，若查找失敗，p的值即為NULL。
*/
func (list *List) LocateElem(v interface{}) bool {
  if list.IsNull() {
    fmt.Println("err")
    return false
  } else {
    pre := list.headNode
    for pre != nil {
      if pre.data == v {
        return true
      }
      pre = pre.next
    }
    return false
  }
}

/*單鏈表的插入=>將值為e的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上，即插入到結(jié)點(diǎn)a(i-1)與a(i)之間
1、查找結(jié)點(diǎn)a(i-1)并由指針p指向該結(jié)點(diǎn)
2、生成一個(gè)新結(jié)點(diǎn)*s
3、將新結(jié)點(diǎn)*s的數(shù)據(jù)域置為e
4、將新結(jié)點(diǎn)*s的指針域指向結(jié)點(diǎn)a(i)
5、將結(jié)點(diǎn)*p的指針域指向新結(jié)點(diǎn)*s
*/
func (list *List) InsertElem(index int, v interface{}) {
  if index = 0 || index > list.length {
    fmt.Println("err")
  } else {
    pre := list.headNode
    node := Node{data: v}
    if index == 1 {
      node.next = pre
      list.headNode = node
    } else {
      for count := 1; count  index-1; count++ {
        pre = pre.next
      }
      node.next = pre.next
      pre.next = node
    }
    list.length--
  }
}

/*單鏈表的刪除
1、查找結(jié)點(diǎn)a(i-1)并由指針p指向該結(jié)點(diǎn)
2、臨時(shí)保存待刪除結(jié)點(diǎn)a(i)的地址在q中，以備釋放
3、將結(jié)點(diǎn)*p的指針域指向a(i)的直接后繼結(jié)點(diǎn)
4、釋放結(jié)點(diǎn)a(i)的空間
*/
func (list *List) DeleteElem(index int) {
  if index = 0 || index > list.length {
    fmt.Println("刪除位置不合理")
    return
  } else {
    pre := list.headNode
    if index == 1 {
      list.headNode = pre.next
    } else {
      pre := list.headNode
      for count := 1; count  index-1; count++ {
        pre = pre.next
      }
      pre.next = pre.next.next
    }
    list.length--
  }
}

func (list *List) RemoveElem(v interface{}) {
  pre := list.headNode
  if pre.data == v {
    list.headNode = pre.next
  } else {
    for pre.next != nil {
      if pre.next.data == v {
        pre.next = pre.next.next
        return
      } else {
        pre = pre.next
      }
    }
    fmt.Println("fail")
    return
  }
}

func (list *List) IsNull() bool {
  if list.length == 0 {
    return true
  } else {
    return false
  }
}

func (list *List) AddElem(v interface{}) {
  node := Node{data: v}
  if list.IsNull() { //處理空表的插入，否則會(huì)導(dǎo)致一個(gè)空的頭結(jié)點(diǎn)后移
    list.headNode = node
    list.length++
    return
  }
  node.next = list.headNode
  list.headNode = node
  list.length++
  return
}

func (list *List) AppendElem(v interface{}) {
  node := Node{data: v}
  if list.IsNull() {
    list.headNode.next = node
  } else {
    cur := list.headNode
    for cur.next != nil {
      cur = cur.next
    }
    cur.next = node
  }
  list.length++
  return
}

func (list *List) ShowList() {
  if !list.IsNull() {
    cur := list.headNode
    for {
      fmt.Printf("\t%v", cur.data)
      if cur.next != nil {
        cur = cur.next
      } else {
        break
      }
    }
    fmt.Printf("\n")
  }
}

func main() {
  L := InitList()
  msg := []int{12, 5, 3, 8, 55, 13}
  for i := range msg {
    L.AddElem(msg[i])
  }
  fmt.Println("---- 添加元素 ----")
  L.AppendElem(66)
  L.ShowList()
  fmt.Println("---- 按位刪除元素 ----")
  L.DeleteElem(3)
  L.ShowList()
  fmt.Println("---- 按值刪除元素 ----")
  L.RemoveElem(13)
  L.ShowList()
  fmt.Println("---- 插入元素 ----")
  L.InsertElem(1, 88)
  L.ShowList()
  fmt.Println("---- 按值尋找元素 ----")
  fmt.Println(L.LocateElem(88))
  fmt.Println("---- 按位尋找元素 ----")
  fmt.Println(L.GetElem(4))
}

結(jié)果
---- 添加元素 ----
        13      55      8       3       5       12      66
---- 按位刪除元素 ----
        13      55      3       5       12      66
---- 按值刪除元素 ----
        55      3       5       12      66
---- 插入元素 ----
        88      55      3       5       12      66
---- 按值尋找元素 ----
true
---- 按位尋找元素 ----
5

6、總結(jié)

本文中除了初始化時(shí)為鏈表添加了一個(gè)空的頭結(jié)點(diǎn)，其他情況下均無(wú)頭結(jié)點(diǎn)，正如書(shū)中所說(shuō)，為單鏈表添加頭結(jié)點(diǎn)會(huì)方便很多，對(duì)鏈表進(jìn)行相關(guān)操作時(shí)，不需要對(duì)首元結(jié)點(diǎn)做額外的處理，也便于對(duì)空表和非空表做統(tǒng)一處理
關(guān)于刪除時(shí)釋放結(jié)點(diǎn)空間及指針回收，我們交由go強(qiáng)大的垃圾回收來(lái)完成

參考博客
Golang之單鏈表實(shí)現(xiàn)
go語(yǔ)言實(shí)現(xiàn)單鏈表

到此這篇關(guān)于詳解go語(yǔ)言單鏈表及其常用方法的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)go語(yǔ)言單鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

python/golang 刪除鏈表中的元素
python/golang實(shí)現(xiàn)循環(huán)鏈表的示例代碼
Go實(shí)現(xiàn)雙向鏈表的示例代碼
golang雙鏈表的實(shí)現(xiàn)代碼示例
Go語(yǔ)言單鏈表實(shí)現(xiàn)方法
go實(shí)現(xiàn)反轉(zhuǎn)鏈表

標(biāo)簽：松原泰安黔西宜春武漢河池保定鷹潭

巨人網(wǎng)絡(luò)通訊聲明：本文標(biāo)題《詳解go語(yǔ)言單鏈表及其常用方法的實(shí)現(xiàn)》，本文關(guān)鍵詞詳解,語(yǔ)言,單鏈表,及其,；如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問(wèn)題，煩請(qǐng)?zhí)峁┫嚓P(guān)信息告之我們，我們將及時(shí)溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò)，涉及言論、版權(quán)與本站無(wú)關(guān)。