package list 代码
代码语言：javascript复制 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 }测试代码
代码语言：javascript复制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()
}
