go例子(一) 使用go语言实现linux内核中的list_head

  1 package list
  2 import (
  3     "fmt"
  4 )
  5 // 数据接口
  6 type ElemType interface{}
  7 // 节点
  8 type Node struct{
  9     Data ElemType
 10     Pre *Node
 11     Next *Node
 12 }
 13 // 初始化链表
 14 func InitList(s *Node)(){
 15     //s := new(Node)
 16     s.Next,s.Pre = s,s
 17     s.Data = nil
 18     //return &Node{nil,s,s} //相当于用s重新构造了一个对象，新的对象的地址不是s，不能和s构成一个环
 19     return 
 20 }
 21 // 在after和before之间添加s
 22 func add(s,after,before *Node){
 23     after.Next = s
 24     s.Pre = after
 25     s.Next = before
 26     before.Pre = s
 27 }
 28 // 将x元素添加到链表尾部
 29 func (list *Node)Add_tail(x ElemType){
 30     s := new(Node)
 31     s.Data = x
 32     add(s,list.Pre,list)
 33 }
 34 // 将x元素添加到链表头部
 35 func (list *Node)Add_head(x ElemType){
 36     s := new(Node)
 37     s.Data = x
 38     add(s,list,list.Next)
 39 }
 40 // 判断链表是否为空
 41 func (list *Node)IsEmpty() bool {
 42     if list.Pre == list {
 43         return true
 44     }
 45     return false
 46 }
 47 // 从头到尾查找元素
 48 func (list *Node)Find(x ElemType) *Node{
 49     if list.IsEmpty() {
 50         return nil
 51     }
 52     s := list.Next
 53     for s != list{
 54         if x == s.Data{
 55             return s
 56         } else {
 57             s = s.Next
 58         }
 59     }
 60     return nil
 61 }
 62 func delete(pre,next *Node){
 63     pre.Next = next
 64     next.Pre = pre
 65 }
 66 // 删除节点
 67 func (list *Node)Delete(s *Node){
 68     delete(s.Pre,s.Next)
 69     s.Pre,s.Next = nil,nil
 70 }
 71 // 删除从头到尾找到的第一个元素
 72 func (list *Node)DeleteVal(x ElemType) bool {
 73     result := list.Find(x)
 74     if result == nil {
 75         return false
 76     }
 77     list.Delete(result)
 78     return true
 79 }
 80 func (list *Node)MoveToHead(s *Node){
 81     list.Delete(s)
 82     add(s,list,list.Next)
 83 }
 84 // 将元素移到队首
 85 func (list *Node)MoveValToHead(x ElemType) bool {
 86     result := list.Find(x)
 87     if result == nil {
 88         return false
 89     }
 90     list.MoveToHead(result)
 91     return true
 92 }
 93 func (list *Node)MoveToTail(s *Node){
 94     list.Delete(s)
 95     add(s,list.Pre,list)
 96 }
 97 // 将元素移到队尾
 98 func (list *Node)MoveValToTail(x ElemType) bool {
 99     result := list.Find(x)
100     if result == nil {
101         return false
102     }
103     list.MoveToTail(result)
104     return true
105 }
106 func list_splice(add,after,before *Node){
107     first,last := add.Next,add.Pre
108     first.Pre = after
109     after.Next = first
110     last.Next = before
111     before.Pre = last
112 }
113 // 将链表add尾插到list链表上
114 func (list *Node)List_splice_tail(add *Node)bool {
115     if list == add {
116         return false
117     }
118     if !add.IsEmpty(){
119         list_splice(add,list.Pre,list)
120         InitList(add)
121     }
122     return true
123 }
124 // 将链表add头插到list链表上
125 func (list *Node)List_splice_head(add *Node)bool {
126     if list == add {
127         return false
128     }
129     if !add.IsEmpty(){
130         list_splice(add,list,list.Next)
131         InitList(add)
132     }
133     return true
134 }
135 // 对列表中的所有元素均执行 参数为函数
136 func (list *Node)Foreach(f func(*Node)) bool {
137     if list.IsEmpty(){
138         return false
139     }
140     s := list.Next
141     for s != list{
142         f(s)
143         s = s.Next
144     }
145     return true
146 }
147 func (list *Node) Print() error {
148     fmt.Println("++++Print begin++++")
149     defer fmt.Println("-----Print end-----")
150     if list.IsEmpty() {
151         fmt.Println("list is empty")
152         return nil
153     }
154     s := list.Next
155     for s != list {
156         fmt.Println("Data is :",s.Data)
157         s = s.Next
158     }
159     return nil
160 }

package main
import (
    "fmt"
    "./list"
)
func test_03(){
    list_i := new(list.Node)
    list.InitList(list_i)
    val := []int{1,2,3,4,5}
    list_i.Print()
    for _,v := range val {
        list_i.Add_tail(v)
    }
    list_i.Print()
}
func test_04(){
    list_s := new(list.Node)
    list.InitList(list_s)
    val := []string{"wo","shi","cheng","xu","yuan"}
    list_s.Print()
    for _,v := range val {
        list_s.Add_tail(v)
    }
    list_s.Print()
}

func test_05(){
    list_s := new(list.Node)
    list.InitList(list_s)
    val := []string{"wo","shi","cheng","xu","yuan"}
    list_s.Print()
    for _,v := range val {
        list_s.Add_head(v)
    }
    list_s.Print()
    list_s.MoveValToHead("shi")
    list_s.Print()
    list_s.MoveValToTail("xu")
    list_s.Print()
    list_s.DeleteVal("shi")
    list_s.Print()
    list_s.DeleteVal("xu")
    list_s.Print()
}
func test_06(){
    list_s := new(list.Node)
    list.InitList(list_s)
    list_s2 := new(list.Node)
    list.InitList(list_s2)
    val := []string{"wo","shi","cheng","xu","yuan"}
    list_s.Print()
    list_s2.Print()
    for _,v := range val {
        list_s.Add_head(v)
        list_s2.Add_tail(v)
    }
    list_s.Print()
    list_s2.Print()
    ok := list_s.List_splice_head(list_s)
    if ok {
        fmt.Println("success")
        list_s.Print()
        list_s2.Print()
    }else{
        fmt.Println("fail")
    }
    ok = list_s.List_splice_head(list_s2)
    if ok {
        fmt.Println("success")
        list_s.Print()
        list_s2.Print()
    }else{
        fmt.Println("fail")
    }
}
func test_07(){
    list_s := new(list.Node)
    list.InitList(list_s)
    list_s2 := new(list.Node)
    list.InitList(list_s2)
    val := []string{"wo","shi","cheng","xu","yuan"}
    list_s.Print()
    list_s2.Print()
    for _,v := range val {
        list_s.Add_head(v)
        list_s2.Add_tail(v)
    }
    list_s.Print()
    list_s2.Print()
    ok := list_s.List_splice_tail(list_s)
    if ok {
        fmt.Println("success")
        list_s.Print()
        list_s2.Print()
    }else{
        fmt.Println("fail")
    }
    ok = list_s.List_splice_tail(list_s2)
    if ok {
        fmt.Println("success")
        list_s.Print()
        list_s2.Print()
    }else{
        fmt.Println("fail")
    }
}
func printNode(s *list.Node){
    fmt.Println("Data:",s.Data)
}
func changeData(s *list.Node){
    s.Data = "123"
}
func test_08(){
    list_s := new(list.Node)
    list.InitList(list_s)
    val := []string{"wo","shi","cheng","xu","yuan"}
    list_s.Print()
    for _,v := range val {
        list_s.Add_head(v)
    }
    list_s.Foreach(printNode)
    list_s.Foreach(changeData)
    list_s.Foreach(printNode)
}
func main(){
    //test_03()
    //test_04()
    //test_05()
    //test_06()
    //test_07()
    test_08()
}