首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >1.Go-copy函数、sort排序、双向链表、list操作和双向循环链表

1.Go-copy函数、sort排序、双向链表、list操作和双向循环链表

作者头像
zhang_derek
发布2019-08-06 14:39:31
7520
发布2019-08-06 14:39:31
举报
文章被收录于专栏:有趣的django有趣的django

1.1.copy函数

通过copy函数可以把一个切片内容复制到另一个切片中

(1)把长切片拷贝到短切片中

package main

import "fmt"

func main() {
	s1 := []int {1,2}
	s2 := []int{3,4,5,6}
	//copy的是角标,不会增加元切片的长度
	copy(s1,s2)
	fmt.Println(s1)        //[3 4]
	fmt.Println(s2)		   //[3 4 5 6]
}

(2)把短切片拷贝到长切片中 

package main

import "fmt"

func main() {
	s1 := []int {1,2}
	s2 := []int{3,4,5,6}
	//copy的是角标,不会增加元切片的长度
	copy(s2,s1)
	fmt.Println(s1)        //[1 2]
	fmt.Println(s2)		   //[1 2 5 6]
}

(3)把切片片段拷贝到切片中

package main

import "fmt"

func main() {
	s1 := []int {1,2}
	s2 := []int{3,4,5,6}
	//copy的是角标,不会增加元切片的长度
	copy(s1,s2[1:3])
	fmt.Println(s1)        //[[4 5]
	fmt.Println(s2)		   //[3 4 5 6]
}

1.2.sort排序

package main

import (
	"fmt"
	"sort"
)

func main() {
	num := []int{1,7,3,5,2}
	//升序排序
	sort.Ints(num)
	fmt.Println(num)      //[1 2 3 5 7]

	//降序排序
	sort.Sort(sort.Reverse(sort.IntSlice(num)))
	fmt.Println(num)     //[7 5 3 2 1]
}

1.3.双向链表

 (1)双向链表的结构

双向链表结构中元素在内存中不是紧邻空间,而是每个元素中存放上一个元素和后一个元素的地址

  • 第一个元素称为(头)元素,前连接(前置指针域)为nil
  • 最后一个元素称为 尾(foot)元素,后连接(后置指针域)尾nil

 双向链表的优点

  • 在执行新增元素或删除元素时效率高,获取任意一个元素,可以方便的在这个元素前后插入元素
  • 充分利用内存空间,实现内存灵活管理
  • 可实现正序和逆序遍历
  • 头元素和尾元素新增或删除时效率较高

  双向链表的缺点

  •  链表增加了元素的指针域,空间开销比较大
  • 遍历时跳跃性查找内容,大量数据遍历性能低

 (2)双向链表容器List

在Go语言标准库的container/list包提供了双向链表List

List结构体定义如下

  • root表示根元素
  • len表示链表中有多少元素
// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
type List struct {
	root Element // sentinel list element, only &root, root.prev, and root.next are used
	len  int     // current list length excluding (this) sentinel element
}

 其中Element结构体定义如下

  • next表示下一个元素,使用Next()可以获取到
  • prev表示上一个元素,使用Prev()可以获取到
  • list表示元素属于哪个链表
  • Value表示元素的值,interface()在Go语言中表示任意类型 
// Element is an element of a linked list.
type Element struct {
	// Next and previous pointers in the doubly-linked list of elements.
	// To simplify the implementation, internally a list l is implemented
	// as a ring, such that &l.root is both the next element of the last
	// list element (l.Back()) and the previous element of the first list
	// element (l.Front()).
	next, prev *Element

	// The list to which this element belongs.
	list *List

	// The value stored with this element.
	Value interface{}
}

1.4.操作List

(1)直接使用container/list包下的New()新建一个空的List

添加,遍历,取首尾,取中间元素

package main

import (
	"container/list"
	"fmt"
)

func main() {
	//实例化
	mylist := list.New()
	fmt.Println(mylist)

	//添加
	mylist.PushFront("a")                        //["a"]
	mylist.PushBack("b")                         //["a","b"]
	mylist.PushBack("c")                         //["a","b","c"]
	//在最后一个元素的前面添加
	mylist.InsertBefore("d",mylist.Back())       //["a","b","d","c"]
	mylist.InsertAfter("e",mylist.Front())       //["a","e","b","d","c"]

	//遍历
	for e := mylist.Front(); e != nil; e = e.Next(){
		fmt.Print(e.Value, " ")     //a e b d c
	}
	fmt.Println("")

	//取首尾
	fmt.Println(mylist.Front().Value)     //a
	fmt.Println(mylist.Back().Value)      //c

	//取中间的元素,通过不断的Next()
	n := 3
	var curr *list.Element
	if n > 0 && n <= mylist.Len(){
		if n == 1 {
			curr = mylist.Front()
		}else if n == mylist.Len(){
			curr = mylist.Back()
		}else {
			curr = mylist.Front()
			for i := 1; i < n; i++{
				curr = curr.Next()
			}
		}
	}else {
		fmt.Println("n的数值不对")
	}
	fmt.Println(curr.Value)        //b
}

(2)移动元素 

package main

import (
	"container/list"
	"fmt"
)

func main() {
	//实例化
	mylist := list.New()
	fmt.Println(mylist)

	//添加
	mylist.PushFront("a")                        //["a"]
	mylist.PushBack("b")                         //["a","b"]
	mylist.PushBack("c")                         //["a","b","c"]
	//在最后一个元素的前面添加
	mylist.InsertBefore("d",mylist.Back())       //["a","b","d","c"]
	mylist.InsertAfter("e",mylist.Front())       //["a","e","b","d","c"]

	//移动,把第一个元素一道最后一个元素的前面
	mylist.MoveBefore(mylist.Front(),mylist.Back())
	//mylist.MoveAfter(mylist.Back(),mylist.Front())
	
	//把最后一个元素移动到最前面
	//mylist.MoveToFront(mylist.Back())
	//把第一个元素移动到最后面
	//mylist.MoveToBack(mylist.Front())

	for e := mylist.Front(); e != nil; e = e.Next(){
		fmt.Print(e.Value, " ")     //e b d a c
	}
}

(3)删除

mylist.Remove(mylist.Front())

1.5.双向循环列表

(1)循环链表特点是没有节点的指针域为nil,通过任何一个元素都可以找到其它元素

环形链表结构如下

双向循环链表和双向链表区别

  • 双向循环链表没有严格意义上的头元素和尾元素
  • 没有元素的前连接和后连接为nil
  • 一个长度为n的双向循环链表,通过某个元素向某个方向移动,在查找最多n-1次,一定会找到另一个元素

(2)在container/ring包下结构体Ring源码如下

  • 官方明确说明了Ring是循环链表的元素,又是环形链表
  • 实际使用时Ring遍历就是环形链表第一个元素
// A Ring is an element of a circular list, or ring.
// Rings do not have a beginning or end; a pointer to any ring element
// serves as reference to the entire ring. Empty rings are represented
// as nil Ring pointers. The zero value for a Ring is a one-element
// ring with a nil Value.
//
type Ring struct {
	next, prev *Ring
	Value      interface{} // for use by client; untouched by this library
}

(3)创建和查看  

package main

import (
	"container/ring"
	"fmt"
)

func main() {
	//r代表整个循环链表,又代表第一个元素
	r := ring.New(5)
	r.Value = 0
	r.Next().Value = 1
	r.Next().Next().Value = 2
	//r.Next().Next().Next().Value = 3
	//r.Next().Next().Next().Next().Value = 4
	r.Prev().Value = 4
	r.Prev().Prev().Value = 3
	//查看元素内容
	//循环链表有几个元素,func就执行几次,i当前执行元素的内容
	r.Do(func(i interface{}) {
		fmt.Print(i, " ")      //0 1 2 3 4
	})
	fmt.Println("")
	//取中间元素,用移动
	fmt.Println(r.Move(3).Value)   //3


}

(4)增加

package main

import (
	"container/ring"
	"fmt"
)

func main() {
	//r代表整个循环链表,又代表第一个元素
	r := ring.New(5)
	r.Value = 0
	r.Next().Value = 1
	r.Next().Next().Value = 2
	//r.Next().Next().Next().Value = 3
	//r.Next().Next().Next().Next().Value = 4
	r.Prev().Value = 4
	r.Prev().Prev().Value = 3

	//增加
	r1 := ring.New(2)
	r1.Value = 5
	r1.Next().Value = 6
	r.Link(r1)

	r.Do(func(i interface{}) {
		fmt.Print(i, " ")    //0 5 6 1 2 3 4 
	})
}

(5)删除

package main

import (
	"container/ring"
	"fmt"
)

func main() {
	//r代表整个循环链表,又代表第一个元素
	r := ring.New(5)
	r.Value = 0
	r.Next().Value = 1
	r.Next().Next().Value = 2
	//r.Next().Next().Next().Value = 3
	//r.Next().Next().Next().Next().Value = 4
	r.Prev().Value = 4
	r.Prev().Prev().Value = 3

	//删除
	r.Unlink(1)

	r.Do(func(i interface{}) {
		fmt.Print(i, " ")    //0 2 3 4 
	})
}

删除后面两个

//删除
	r.Unlink(2)

	r.Do(func(i interface{}) {
		fmt.Print(i, " ")    //0 3 4 
	})

r.Next()删除

//删除
	r.Next().Unlink(2)

	r.Do(func(i interface{}) {
		fmt.Print(i, " ")    //0 1 4 
	})qu  

超出范围,取5的余数

//删除
	r.Unlink(6)

	r.Do(func(i interface{}) {
		fmt.Print(i, " ")    //0 2 3 4
	})
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019-08-04 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1.1.copy函数
  • 1.2.sort排序
  • 1.3.双向链表
  • 1.4.操作List
  • 1.5.双向循环列表
相关产品与服务
容器服务
腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档