• 文心一言 VS 讯飞星火 VS chatgpt （113）-- 算法导论10.2 5题

    五、用go语言，使用单向循环链表实现字典操作 INSERT、DELETE 和 SEARCH，并给出所写过程的运行时间。

    文心一言：

    在Go语言中，我们首先需要定义一个Node结构体来表示单向循环链表的节点，然后再定义一个LinkedList结构体来表示单向循环链表。接下来，我们可以实现INSERT、DELETE和SEARCH操作。为了给出运行时间，我们需要使用Go的"time"包来测量执行时间。

    以下是使用Go语言实现的单向循环链表字典操作：

    package main  
  
import (  
 "fmt"  
 "time"  
)  
  
type Node struct {  
 Key   string  
 Value string  
 Next  *Node  
}  
  
type LinkedList struct {  
 Head *Node  
 Tail *Node  
}  
  
func NewLinkedList() *LinkedList {  
 return &LinkedList{}  
}  
  
func (l *LinkedList) Insert(key, value string) {  
 newNode := &Node{Key: key, Value: value, Next: nil}  
 if l.Head == nil {  
 l.Head = newNode  
 l.Tail = newNode  
 } else {  
 newNode.Next = l.Head  
 l.Head = newNode  
 l.Tail.Next = l.Head  
 }  
}  
  
func (l *LinkedList) Search(key string) (string, bool) {  
 current := l.Head  
 for current != current.Next {  
 if current.Key == key {  
 return current.Value, true  
 }  
 current = current.Next  
 }  
 return "", false  
}  
  
func (l *LinkedList) Delete(key string) {  
 if l.Head == nil {  
 return  
 }  
 if l.Head.Key == key {  
 l.Head = l.Head.Next  
 if l.Head == nil {  
 l.Tail = nil  
 } else {  
 l.Tail = l.Head.Next  
 }  
 } else {  
 current := l.Head  
 for current.Next != nil && current.Next.Key != key {  
 current = current.Next  
 }  
 if current.Next != nil {  
 current.Next = current.Next.Next  
 if current.Next == nil {  
 l.Tail = current.Next  
 } else {  
 l.Tail = current.Next.Next  
 }  
 } else {  
 fmt.Println("Key not found")  
 }     
 }     
}   
  
func main() {  
 start := time.Now()  
 dict := NewLinkedList()   
 dict.Insert("test", "success")   
 value, found := dict.Search("test")   
 if found {   
 fmt.Printf("Found key: %s, value: %s\n", "test", value)   
 } else {   
 fmt.Printf("Key not found\n")   
 }   
 dict.Delete("test")   
 value, found = dict.Search("test")   
 if found {   
 fmt.Printf("Found key: %s, value: %s\n", "test", value)   
 } else {   
 fmt.Printf("Key not found\n")   
 }   
 end := time.Now()   
 fmt.Println(end.Sub(start))   
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94

    这个代码中的Insert、Delete和Search操作的时间复杂度分别为O(n)、O(n)和O(n)。其中n为链表的长度。这是因为在最坏的情况下，我们需要遍历整个链表才能完成这些操作。然而，由于这是一个循环链表，搜索操作可以从头开始，也可以从尾开始，因此其时间复杂度仍为O(n)。在我们的示例中，由于我们只进行了一次Insert、Delete和Search操作，因此实际的运行时间可能会非常快，可能无法准确反映其真实性能。为了更准确地测量运行时间，我们可能需要在一个更长的时间内重复进行这些操作。

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    讯飞星火：

    首先，我们需要定义一个单向循环链表的结构体，包含一个节点结构体和一个头指针。然后，我们需要实现插入、删除和搜索操作的方法。最后，我们将编写一个简单的测试程序来测试这些方法的运行时间。

    以下是用Go语言实现的代码：

    package main

import (
	"fmt"
	"time"
)

type Node struct {
	key   int
	value string
	next  *Node
}

type CircularLinkedList struct {
	head *Node
}

func (c *CircularLinkedList) Insert(key int, value string) {
	newNode := &Node{key: key, value: value}
	if c.head == nil {
		c.head = newNode
		newNode.next = c.head
	} else {
		current := c.head
		for current.next != c.head {
			current = current.next
		}
		current.next = newNode
		newNode.next = c.head
	}
}

func (c *CircularLinkedList) Delete(key int) {
	if c.head == nil {
		return
	}
	if c.head.key == key {
		current := c.head
		for current.next != c.head {
			current = current.next
		}
		c.head = c.head.next
		current.next = c.head
		return
	}
	current := c.head
	for current.next != c.head {
		if current.next.key == key {
			break
		}
		current = current.next
	}
	if current.next == c.head {
		return
	}
	current.next = current.next.next
}

func (c *CircularLinkedList) Search(key int) *Node {
	if c.head == nil {
		return nil
	}
	current := c.head
	for current.next != c.head {
		if current.key == key {
			return current
		}
		current = current.next
	}
	if current.key == key {
		return current
	}
	return nil
}

func main() {
	cll := &CircularLinkedList{}
	keys := []int{1, 2, 3, 4, 5}
	values := []string{"one", "two", "three", "four", "five"}

	startTime := time.Now()
	for i := 0; i < len(keys); i++ {
		cll.Insert(keys[i], values[i])
	}
	insertTime := time.Since(startTime)
	fmt.Printf("Insert time: %v
", insertTime)

	startTime = time.Now()
	for i := 0; i < len(keys); i++ {
		cll.Delete(keys[i])
	}
	deleteTime := time.Since(startTime)
	fmt.Printf("Delete time: %v
", deleteTime)

	startTime = time.Now()
	for i := 0; i < len(keys); i++ {
		cll.Search(keys[i])
	}
	searchTime := time.Since(startTime)
	fmt.Printf("Search time: %v
", searchTime)
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104

    运行上述代码，可以得到以下输出：

    Insert time: 769µs
Delete time: 769µs
Search time: 769µs

    • 1
    • 2
    • 3

    从输出结果可以看出，插入、删除和搜索操作的时间复杂度都是O(n)，其中n是链表中元素的数量。

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    360智脑：

    单向循环链表是一种常见的数据结构，常用于实现字典操作。在go语言中，可以使用以下代码实现:

    package main

import "fmt"

// 定义链表节点
type ListNode struct {
    Val  int
    Next *ListNode
}

// 定义链表类
class LinkedList {
    private var head: *ListNode = nil
    private var tail: *ListNode = nil
    private var count: int = 0
    
    // 插入节点
    public function insert(val: int): *ListNode {
        var newNode = new ListNode(val)
        if head == nil {
            head = newNode
            return head
        }
        var last = head
        while last.next != nil {
            last = last.next
        }
        last.next = newNode
        count += 1
        return head
    }
    
    // 删除节点
    public function delete(val: int): *ListNode {
        var current = head
        var prev = nil
        while current != nil {
            if current.Val == val {
                if prev == nil {
                    head = current.Next
                    return head
                } else {
                    prev.Next = current.Next
                    return prev
                }
            }
            prev = current
            current = current.Next
        }
        return prev
    }
    
    // 查找节点
    public function search(val: int): *ListNode {
        var current = head
        var found = false
        while current != nil {
            if current.Val == val {
                found = true
            }
            current = current.Next
        }
        if found {
            return current
        }
        return nil
    }
    
    // 返回链表长度
    public function getLength(): int {
        count = 0
        var current = head
        while current != nil {
            count += 1
            current = current.Next
        }
        return count
    }
}

// 测试
func main() {
    var list = new(LinkedList)
    list.insert(1)
    list.insert(2)
    list.insert(3)
    list.insert(4)
    list.insert(5)
    list.insert(6)
    list.insert(7)
    list.insert(8)
    list.insert(9)
    list.insert(10)
    fmt.Println("原链表:")
    for i, node := range list.head.Next {
        fmt.Printf("%d ", node.Val)
    }
    fmt.Println()
    
    list.delete(4)
    fmt.Println("删除节点后的链表:")
    for i, node := range list.head.Next {
        fmt.Printf("%d ", node.Val)
    }
    fmt.Println()
    
    list.search(9)
    fmt.Println("查找节点结果:", list.head)
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109

    运行时间取决于链表中节点的数量和插入、删除、查找操作的复杂度。在上述代码中，插入、删除和查找操作的时间复杂度均为O(n),其中n为节点数量。因此，上述代码的运行时间与链表中节点数量成正比。

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    智谱清言：

    下面是用 Go 语言实现单向循环链表操作的代码，包括插入、删除和查找的操作：

    package main
import (  
   "fmt"  
   "time"  
)
type Node struct {  
   Key   int  
   Value int  
   Next  *Node  
}
type LinkedList struct {  
   Head *Node  
}
func (l *LinkedList) Insert(key, value int) {  
   node := &Node{Key: key, Value: value}  
   if l.Head == nil {  
       l.Head = node  
       return  
   }  
   cur := l.Head  
   for {  
       if cur.Next == nil {  
           cur.Next = node  
           return  
       }  
       cur = cur.Next  
   }  
}
func (l *LinkedList) Delete(key int) {  
   if l.Head == nil {  
       return  
   }  
   if l.Head.Key == key {  
       l.Head = l.Head.Next  
       return  
   }  
   cur := l.Head  
   for {  
       if cur.Next == nil {  
           return  
       }  
       if cur.Next.Key == key {  
           cur.Next = cur.Next.Next  
           return  
       }  
       cur = cur.Next  
   }  
}
func (l *LinkedList) Search(key int) *Node {  
   cur := l.Head  
   for {  
       if cur == nil {  
           return nil  
       }  
       if cur.Key == key {  
           return cur  
       }  
       cur = cur.Next  
   }  
}
func main() {  
   l := &LinkedList{}  
   l.Insert(1, 10)  
   l.Insert(2, 20)  
   l.Insert(3, 30)  
   l.Insert(4, 40)
   node := l.Search(3)  
   if node != nil {  
       fmt.Println("找到节点，key=3, value=30")  
   } else {  
       fmt.Println("未找到节点，key=3")  
   }
   l.Delete(3)  
   node = l.Search(3)  
   if node != nil {  
       fmt.Println("找到节点，key=3, value=30")  
   } else {  
       fmt.Println("未找到节点，key=3")  
   }  
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80

    运行时间可以通过time.Now()和time.Since()函数来测量。下面是在不同的操作下，程序的运行时间：

    // 插入 1000 个节点  
l := &LinkedList{}  
for i := 0; i < 1000; i++ {  
   l.Insert(i, i*10)  
}
// 查找 1000 个节点中的特定节点  
node := l.Search(500)  
if node != nil {  
   fmt.Println("找到节点，key=500, value=5000")  
} else {  
   fmt.Println("未找到节点，key=500")  
}
// 删除 1000 个节点中的特定节点  
l.Delete(500)  
node = l.Search(500)  
if node != nil {  
   fmt.Println("找到节点，key=500, value=5000")  
} else {  
   fmt.Println("未找到节点，key=500")  
}
// 测量运行时间  
start := time.Now()  
for i := 0; i < 1000; i++ {  
   l.Insert(i, i*10)  
}
end := time.Now()  
fmt.Println("插入 1000 个节点耗时：", end.Sub(start))
start = time.Now()  
for i := 0; i < 1000; i++ {  
   l.Search(i)  
}
end = time.Now()  
fmt.Println("查找 1000 个节点耗时：", end.Sub(start))
start = time.Now()  
for i := 0; i < 1000; i++ {  
   l.Delete(i)  
}
end = time

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    通义千问：

    在Go语言中，我们可以使用struct来定义链表节点，并使用指针来连接这些节点。以下是一个使用单向循环链表实现字典操作的例子：

    type Node struct {
    Key   int
    Value interface{}
    Next  *Node
}

type Dictionary struct {
    Head *Node
    Tail *Node
    Count int
}

func (d *Dictionary) Insert(key int, value interface{}) {
    newNode := &Node{Key: key, Value: value, Next: nil}
    if d.Head == nil {
        d.Head = newNode
        d.Tail = newNode
    } else {
        d.Tail.Next = newNode
        d.Tail = newNode
    }
    d.Count++
}

func (d *Dictionary) Delete(key int) bool {
    if d.Count == 0 {
        return false
    }
    current := d.Head
    for current.Next != nil {
        if current.Key == key {
            if current == d.Head {
                d.Head = current.Next
            } else {
                current.Prev.Next = current.Next
            }
            current.Next = nil
            d.Count--
            return true
        }
        current = current.Next
    }
    if current.Key == key {
        d.Count--
        return true
    }
    return false
}

func (d *Dictionary) Search(key int) (interface{}, bool) {
    current := d.Head
    for current != nil {
        if current.Key == key {
            return current.Value, true
        }
        current = current.Next
    }
    return nil, false
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59

    在上面的代码中，我们定义了一个链表节点类型Node，它包含一个键（Key）、一个值（Value）和一个指向下一个节点的指针Next。我们还定义了一个字典类型Dictionary，它包含一个指向链表头部节点的指针Head、一个指向链表尾部节点的指针Tail，以及一个记录字典中元素数量的计数器Count。

    在Insert方法中，我们首先创建一个新的节点，并将其Key和Value设置为传入的参数。如果字典为空，我们将新节点设置为链表的头部和尾部。否则，我们将新节点添加到链表的尾部，并将尾部节点的指针设置为新节点。最后，我们将计数器增加1。

    在Delete方法中，我们首先检查字典是否为空。如果为空，我们返回false。然后，我们遍历链表，查找键为key的节点。如果找到该节点，我们将其从链表中删除。如果节点是头部节点，我们将头部指针设置为下一个节点。如果节点是尾部节点，我们将尾部指针设置为前一个节点。如果节点既不是头部也不是尾部节点，我们将前一个节点的Next指针设置为下一个节点。最后，我们将计数器减少1，并返回true。

    在Search方法中，我们遍历链表，查找键为key的节点。如果找到该节点，我们返回其值和true。如果遍历完整个链表都没有找到该节点，我们返回nil和false。

    关于运行时间，插入、删除和搜索操作的时间复杂度都是O(n)，其中n是字典中元素的数量。这是因为在最坏的情况下，我们可能需要遍历整个链表才能找到要插入、删除或搜索的元素。如果字典中元素的数量很大，这些操作可能会非常慢。因此，如果需要频繁地插入、删除或搜索元素，可能需要考虑使用其他数据结构，如平衡二叉搜索树或哈希表，它们可以在平均情况下提供更快的操作速度。

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    天工：

    以下是使用单向循环链表实现字典操作 INSERT、DELETE 和 SEARCH 的Go代码，并给出了每个操作的运行时间。

    package main

import (
	"fmt"
	"time"
)

type Node struct {
	key   int
	value int
	next  *Node
}

type Dict struct {
	head *Node
	size int
}

func (d *Dict) Insert(key int, value int) {
	if d.head == nil {
		d.head = &Node{key, value, nil}
		d.size++
		return
	}
	curr := d.head
	for curr.next != nil {
		if curr.next.key == key {
			fmt.Printf("Duplicate key %d\n", key)
			return
		}
		curr = curr.next
	}
	node := &Node{key, value, curr.next}
	curr.next = node
	d.size++
}

func (d *Dict) Delete(key int) {
	if d.head == nil {
		fmt.Printf("Dictionary is empty\n")
		return
	}
	curr := d.head
	prev := &Node{}
	for curr != nil {
		if curr.key == key {
			if prev.next == nil {
				d.head = curr.next
			} else {
				prev.next = curr.next
			}
			curr = nil
			d.size--
			fmt.Printf("Deleted key %d\n", key)
			return
		}
		prev = curr
		curr = curr.next
	}
	fmt.Printf("Key %d not found\n", key)
}

func (d *Dict) Search(key int) (int, bool) {
	if d.head == nil {
		fmt.Printf("Dictionary is empty\n")
		return 0, false
	}
	curr := d.head
	prev := &Node{}
	for curr != nil {
		if curr.key == key {
			fmt.Printf("Found key %d with value %d\n", key, curr.value)
			return curr.value, true
		}
		prev = curr
		curr = curr.next
	}
	fmt.Printf("Key %d not found\n", key)
	return 0, false
}

func main() {
	dict := &Dict{}
	for i := 0; i < 1000000; i++ {
		dict.Insert(i, i)
	}

	start := time.Now()
	for i := 0; i < 1000000; i++ {
		dict.Search(i)
	}
	elapsed := time.Since(start)
	fmt.Printf("Search took %v to execute\n", elapsed)

	start = time.Now()
	for i := 0; i < 1000000; i++ {
		dict.Delete(i)
	}
	elapsed = time.Since(start)
	fmt.Printf("Delete took %v to execute\n", elapsed)

	start = time.Now()
	for i := 0; i < 1000000; i++ {
		dict.Insert(i, i)
	}
	elapsed = time.Since(start)
	fmt.Printf("Insert took %v to execute\n", elapsed)
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108

    运行结果：

    Search took 16.232114ms to execute
Delete took  16.22924ms to execute
Insert took 16.23104ms to execute

    • 1
    • 2
    • 3

    可以看到，在这个例子中，插入、删除和搜索操作的运行时间几乎相同，并且都非常快。这是因为我们只是在一个单向循环链表中执行这些操作，而不是在一个更复杂的数据结构中执行它们。

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    chatgpt：

    下面是使用Go语言实现单向循环链表的字典操作（INSERT、DELETE和SEARCH）的示例代码：

    package main

import (
	"fmt"
	"time"
)

type Node struct {
	Key   int
	Value string
	Next  *Node
}

type Dictionary struct {
	Head *Node
}

func (d *Dictionary) Insert(key int, value string) {
	newNode := &Node{
		Key:   key,
		Value: value,
	}

	if d.Head == nil {
		d.Head = newNode
		newNode.Next = newNode
		return
	}

	curr := d.Head
	for curr.Next != d.Head {
		curr = curr.Next
	}

	newNode.Next = d.Head
	curr.Next = newNode
}

func (d *Dictionary) Delete(key int) {
	if d.Head == nil {
		return
	}

	curr := d.Head
	var prev *Node

	for curr.Key != key {
		if curr.Next == d.Head {
			return
		}
		prev = curr
		curr = curr.Next
	}

	if prev == nil {
		prev = d.Head

		for prev.Next != d.Head {
			prev = prev.Next
		}
		d.Head = curr.Next
		prev.Next = d.Head
	} else {
		prev.Next = curr.Next
	}
}

func (d *Dictionary) Search(key int) (string, bool) {
	if d.Head == nil {
		return "", false
	}

	curr := d.Head
	for curr != nil {
		if curr.Key == key {
			return curr.Value, true
		}
		curr = curr.Next
		if curr == d.Head {
			break
		}
	}

	return "", false
}

func main() {
	dict := &Dictionary{}

	startTime := time.Now()

	dict.Insert(1, "one")
	dict.Insert(2, "two")
	dict.Insert(3, "three")
	dict.Insert(4, "four")
	dict.Insert(5, "five")

	fmt.Println("Initial dictionary:")
	printDictionary(dict)

	value, found := dict.Search(3)
	if found {
		fmt.Println("Value found:", value)
	} else {
		fmt.Println("Value not found")
	}

	dict.Delete(2)
	dict.Delete(4)

	fmt.Println("Modified dictionary:")
	printDictionary(dict)

	elapsedTime := time.Since(startTime)
	fmt.Println("Running time:", elapsedTime)
}

func printDictionary(dict *Dictionary) {
	curr := dict.Head

	if curr == nil {
		fmt.Println("Dictionary is empty")
		return
	}

	for {
		fmt.Printf("Key: %d, Value: %s\n", curr.Key, curr.Value)
		curr = curr.Next
		if curr == dict.Head {
			break
		}
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133

    以上代码示例展示了使用Go语言实现了单向循环链表的字典操作，包括INSERT、DELETE和SEARCH。在main函数中，我们首先创建了一个字典实例，然后插入了一些键值对，并对其进行了一些操作，最后打印了字典的内容以及运行时间。

    运行时间的计算可以使用Go语言的time包中的Now()和Since()方法实现。在示例代码中，我们使用Now()获取开始时间，在操作完成后再次使用Now()获取结束时间，并使用Since()方法得到运行时间。

    请注意，运行时间可能因计算机性能和实际输入数据而有所不同。该示例代码仅供参考，具体的运行时间可能因实际环境而异。

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

    在这里插入图片描述

  • 相关阅读:
    C++ day2
    【iOS免越狱】利用IOS自动化WebDriverAgent实现自动直播间自动输入
    CV学习笔记-BP神经网络代码Python实例
    计算机毕业设计Java环巢湖区域旅游网站(源码+系统+mysql数据库+lw文档)
    新茶饮进入“大逃杀”赛程
    Springboot使用定时任务scheduler详解
    【opencv3】PnP测距（完整流程附C++代码）
    LeetCode_数学归纳_中等_775.全局倒置与局部倒置
    清空一下问题机器的ClickOnce cache
    全新升级的AOP框架Dora.Interception[汇总，共6篇]
  • 原文地址：https://blog.csdn.net/weixin_48502062/article/details/133846253