アルゴリズム4:単一チェーンテーブルに関する操作
3658 ワード
以下の操作を実現
1.空のシングルチェーンテーブルであるか否かを判断する.単一チェーンテーブルの長さ3.ヘッダノード4を取得する.ヘッダから要素5を追加する.末尾から要素6を追加する.指定の場所に要素7を追加する.指定要素8を削除する.指定位置の要素9を削除する.要素10が含むか否かを判断する.シングルチェーンテーブルの反転
linkedListパッケージコードは以下の通りです。
package linkedList
import "fmt"
type Object interface{}
type Node struct {
Data Object
Next *Node
}
type List struct {
headNode *Node //
}
//
func (this *List) IsEmpty() bool {
if this.headNode == nil {
return true
} else {
return false
}
}
//
func (this *List) Length() int {
cur := this.headNode
count := 0
for cur != nil {
count++
cur = cur.Next
}
return count
}
//
func (this *List) GetHeadNode() *Node {
return this.headNode
}
//
func (this *List) Add(data Object) {
node := &Node{Data: data}
node.Next = this.headNode
this.headNode = node
}
//
func (this *List) Append(data Object) {
node := &Node{Data: data}
if this.IsEmpty() {
this.headNode = node
} else {
cur := this.headNode
for cur.Next != nil {
cur = cur.Next
}
cur.Next = node
}
}
//
func (this *List) Insert(index int, data Object) {
if index <= 0 {
this.Add(data)
} else if index >= this.Length() {
this.Append(data)
} else {
// fmt.Println("hello")
pre := this.headNode
count := 0
for count < (index - 1) {
pre = pre.Next
count++
}
// ,pre index -1
node := &Node{Data: data}
node.Next = pre.Next
pre.Next = node
}
}
//
func (this *List) Remove(data Object) {
pre := this.headNode
if pre.Data == data {
this.headNode = pre.Next
} else {
for pre.Next != nil {
if pre.Next.Data == data {
pre.Next = pre.Next.Next
} else {
pre = pre.Next
}
}
}
}
//
func (this *List) RemoveAtIndex(index int) {
pre := this.headNode
if index <= 0 {
this.headNode = pre.Next
} else if index >= this.Length() {
fmt.Println("index out of range") // err
} else {
count := 0 //index = 3
for count != (index-1) && pre.Next != nil {
count++ //2
pre = pre.Next //2
}
pre.Next = pre.Next.Next
}
}
//
func (this *List) Contain(data Object) bool {
cur := this.headNode
for cur != nil {
if cur.Data == data {
return true
}
cur = cur.Next
}
return false
}
// ,
func (this *List) ReverseList() List {
pre := this.headNode
list := List{}
for pre != nil {
list.Add(pre.Data)
pre = pre.Next
}
return list
}
テストコードはmainです。go中は以下の通り
package main
import (
"fmt"
"test/linkedList/linkedList"
)
func main() {
list := linkedList.List{}
//1. 2, 3, 4, 5
list.Append(1)
list.Append(2)
list.Append(3)
list.Append(4)
//2. head_node
list.Add("head_node")
fmt.Println(" ======", list.Length())
//3.
bool := list.IsEmpty()
fmt.Println(bool)
//4. 2 2indexValue
list.Insert(2, "2_index_value")
travselLinkList(&list)
//5. 2_index_value
isContain := list.Contain("2_index_value")
fmt.Println("isContain[2_index_value]:", isContain)
//6. 2_index_value
list.Remove("2_index_value")
travselLinkList(&list)
//7. 2
list.RemoveAtIndex(2)
//8.
listReverse := list.ReverseList()
fmt.Println(" ======", list.Length())
travselLinkList(&list)
travselLinkList(&listReverse)
}
func travselLinkList(list *linkedList.List) {
//
head := list.GetHeadNode()
for head != nil {
fmt.Println(head.Data)
head = head.Next
}
fmt.Println("--------------------")
}