【Golang】十三、golang数据结构

数据结构 一、稀疏数组1. 什么是稀疏数组？2. 案例演示 二、队列1. 单向队列2. 环形队列 三、链表1、单向链表2、双向链表3、环型链表4、环型链表问题：约瑟夫环5、链表问题：链表反转 四、栈五、哈希散列表代码实现 六、二叉树1、前序遍历2、中序遍历3、后序遍历 七、排序1. 选择排序2. 插入排序3. 希尔排序4. 快速排序

一、稀疏数组 1. 什么是稀疏数组？

>  如果一个二维数组非常大，并且大部分都是默认值的情况下，我们就认为很稀疏。
>  所以我们可以将二维数据中有数据的坐标和值记录下来，保存在数据结构里，这就称之为稀疏数组！

2. 案例演示

我们以一个6*5的二维数组为例子

结构体

type spare struct {
	row int  // 行
	col int  // 列
	val int  // 值
}

数组（golang数组默认值都是0）

arr := [6][5]int{}
// 不同坐标设置默认值
arr[4][2] = 2
arr[4][4] = 3
arr[2][2] = 1
arr[5][2] = 2

存储数据

func saveSpaceArr(arr []int) []spare {
	spareArr := []spare{}
	// 遍历数组中所有不为0的元素
	for i := 0; i < len(arr); i++ {
		for j := 0; j < len(arr[i]); j++ {
			if arr[i][j] != 0 {
				// 记录坐标和值
				space := spare{
					col: j,
					row: i,
					val: arr[i][j],
				}
				spareArr = append(spareArr, space)
			}
		}
	}
	return spareArr
}

读取数据

func readSpaceArr(spareArr []spare) []int{
	arr = [6][5]int{}
	for i := 0; i < len(spareArr); i++ {
		// 读取行列值
		row := spareArr[i].row
		col := spareArr[i].col
		val := spareArr[i].val
		arr[row][col] = val
	}
	return arr
}

二、队列

我们这里使用数组来模拟

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除 *** 作，而在表的后端（rear）进行插入 *** 作。进行插入 *** 作的端称为队尾，进行删除 *** 作的端称为队头

1. 单向队列

1、起始位置

2、添加一个元素

3、添加满元素时

4、删除元素

5、队列满员

结构体

type query struct {
	arr [5]int
	// 最大长度
	maxSize int
	// 首指针(不包含首位)
	front int
	// 尾指针
	real int
}

增加、删除、判断满或者空的方法

// 是否为空？
func (this *query) isNil() bool {
	return (this.front == this.real)
}
// 是否为以满？
func (this *query) isFull() bool {
	return (this.maxSize - 1 == this.real)
}
// 插入数据
func (this *query) push(val int) error {
	if isFull(){
		return errors.New("队列以满")
	}
	this.real++
	this.arr[this.real] = val
	return nil
}
// d出数据
func (this *query) pop() (int, error) {
	if isNil(){
		return -9999, errors.New("队列以空")
	}
	popVal := this.arr[this.front]
	this.front++
	return popVal, nil
}
// 显示数据
func (this *query) show(){
	if isNil(){
		fmt.Println([]int{})
	}
	// 注意此处this.front要加1，this.front指向的是d出的值
	for i:=this.front+1; i<=this.real;i++ {
		fmt.Println(this.arr[i])
	} 
}

初始化队列

func main(){
	query := &query{
		maxSize: 5,
		front: -1,
		real: -1,
	}
	query.push(11)
	query.push(22)
	query.push(33)
	query.push(44)
	// 先进先出
	val, err := query.pop()
	if err != nil {
		fmt.Println(err.Error())
	}
	// 显示数据
	query.show()
}

2. 环形队列

环形队列，故名思议，是一个环状，相对于单向队列来说是一个升级（单向列表一次性添加数据添加满了再删除无法继续使用队列），环形队列可以循环利用队列，只要队列有空余的位置就可以添加新的元素。

1、满员队列

2、删除元素

3、环形增加节点

4、环形满员状态

结构体

type circleQuery struct {
	maxlen 		int
	arr 		[5]int
	// head包含队首元素，tail比队尾元素多1位
	head, tail 	int
}

func (this circleQuery) String() string {
	str, _ := json.Marshal(this)
	return string(str)
}

增、删、查看个数等 *** 作

// 是否为空
func (this *circleQuery) isNil() bool {
	return (this.head == this.tail)
}
// 是否以满
func (this *circleQuery) isFull() bool {
	return ( (this.tail + 1) % this.maxLen == this.head )
}
// 队列元素个数
func (this *circleQuery) count() int {
	return ( (this.maxlen + this.tail - this.head) % this.maxlen )
}
// 添加元素
func (this *circleQuery) push(newVal int) {
	if isFull() {
		return
	}
	this.arr[this.tail] = newVal
	this.tail = (this.tail + 1) % this.maxLen
}
func (this *circleQuery) pop() int {
	if isNil() {
		return
	}
	popVal := this.arr[this.head]
	this.head = (this.head + 1) % this.maxLen
	return popVal
}

初始化环形队列

func main(){
	cq := circleQuery{
	head: 0,
	tail: 0,
	maxlen: 5,
	}
	cq.push(11)
	cq.push(22)
	cq.push(33)
	cq.push(44)
	fmt.Println(cq.pop())
	cq.push(55)
	
	cq.show()
}

三、链表 1、单向链表

1、初始状态

2、添加元素的状态

准备结构体

type linkListNode struct {
	No 			int
	Name 		string
	Next 		*linkListNode // 指向下一个节点
}
// json序列化结构体
func (l *linkListNode) String() string {
	str, _ := json.Marshal(l)
	return string(str)
}

添加、删除、显示节点

// 插入节点
func insert(head *linkListNode, new *linkListNode){
	temp := head
	// 先找到最后一个节点，将新值插入到最后
	for {
		// 当节点Next为nil代表后续没有节点，直接插入即可
		if temp.Next == nil {
			temp.Next = new
			break
		}
		temp = temp.Next
	}
}

// 有序差入节点 (此方法按照No的大小排序)
func orderInsert(head *linkListNode, new *linkListNode){
	temp := head
	for {
		if temp.Next == nil {
			temp.Next = new
			break
		} else if temp.Next.No > new.No {
			new.Next = tmep.Next
			tmep.Next = new
			break
		}
		temp = temp.Next
	}
}

// 删除节点
func delete(head *linkListNode, no int) {
	temp := head
	for {
		if temp.Next == nil {
			fmt.Println("未找到该节点")
			break
		} else if temp.Next.No == no {
			temp.Next = temp.Next.Next
			break
		} 
		temp = temp.Next
	}
}

// 显示节点
func show(head *linkListNode){
	temp := head
	for {
		if temp.Next != nil {
			temp = temp.Next
			fmt.Println(temp.String())
		} else {
			break
		}
	}
}

初始化节点

func main(){
	// 头节点，默认为空
	head := linkListNode{}
	fmt.Println(1)

	realHead1 := linkListNode{
		No: 3,
		Name: "张三",
		Nickname: "傻逼",
	}
	//insert(&head, &realHead1)
	sortInsert(&head, &realHead1)

	fmt.Println(2)
	realHead2 := linkListNode{
		No: 4,
		Name: "李四",
		Nickname: "呆子",
	}
	//insert(&head, &realHead2)
	sortInsert(&head, &realHead2)

	realHead3 := linkListNode{
		No: 1,
		Name: "赵一",
		Nickname: "傻逼",
	}
	//insert(&head, &realHead1)
	sortInsert(&head, &realHead3)

	delete(&head, 3)

	show(&head)
}

2、双向链表

双向链表相对于单链表多了一个前指针，指向了上一个元素

3、环型链表

// 环形列表
type circleLinkList struct {
	No int
	Name string
	next *circleLinkList
}

func (c *circleLinkList) String() string {
	str,_ := json.Marshal(c)
	return string(str)
}

func insertCircleLinkList(head *circleLinkList, new *circleLinkList)  {
	// 判断是否是第一支猫
	if head.next == nil {
		head.No = new.No
		head.Name = new.Name
		head.next = head
		return
	}
	// 定义一个临时变量，找到最后一个节点
	temp := head
	for true {
		if temp.next == head {
			temp.next = new
			new.next = head
			break
		}
		temp = temp.next
	}
}

func deleteCircleLinkList(head *circleLinkList, no int) *circleLinkList {
	if head.next == nil {
		fmt.Println("空链表")
		return head
	}
	temp := head

	// 环形链表只有一个节点的情况
	if temp.next == head {
		temp.next = nil
		return head
	}

	for true {
		if temp.next.No == no {
			if temp.next == head {
				head = temp.next.next
			}
			temp.next = temp.next.next
		}
		if temp.next == head {
			break
		}
		temp = temp.next
	}

	return head
}
func showCircleLinkList(head *circleLinkList) {
	if head.next == nil {
		fmt.Println("链表为空")
		return
	}
	temp := head
	for true {
		fmt.Println(temp)
		if temp.next == head {
			break
		}
		temp = temp.next
	}
}

func main()  {
	head := &circleLinkList{}

	new1 := &circleLinkList{
		No: 1,
		Name: "new1",
	}
	new2 := &circleLinkList{
		No: 2,
		Name: "new2",
	}
	new3 := &circleLinkList{
		No: 3,
		Name: "new3",
	}
	new4 := &circleLinkList{
		No: 4,
		Name: "new4",
	}

	insertCircleLinkList(head, new1)
	insertCircleLinkList(head, new2)
	insertCircleLinkList(head, new3)
	insertCircleLinkList(head, new4)


	head = deleteCircleLinkList(head, 1)

	showCircleLinkList(head)
}

4、环型链表问题：约瑟夫环

丢手帕
设编号为1,2,n个人围坐一圈，约定编号为K（1=

type dsp struct {
	Id int
	Name string
	next *dsp
}

func (d *dsp) String() string {
	str, _ := json.Marshal(d)
	return string(str)
}

func insertDsp(head *dsp, new *dsp)  {
	if head.next == nil {
		head.Name = new.Name
		head.Id = new.Id
		head.next = head
		return
	}
	temp := head
	for true {
		if temp.next == head {
			temp.next = new
			new.next = head
			break
		}
		temp = temp.next
	}
}

func showDsp(head *dsp) {
	if head.next == nil {
		fmt.Println("空链表")
		return
	}
	temp := head
	for true {
		if temp.next == head {
			break
		}
		temp = temp.next
	}
}

func deleteDsp(head *dsp, k int, m int) (*dsp, int) {
	if head.next == nil {
		fmt.Println("空链表")
		return head, -1
	}
	if head.next == head {
		head.next = nil
		return head, head.Id
	}

	flagTemp := -1
	temp := head
	flag := 1
	flagK := 1
	for true {
		if flagK == k {
			flag++
		} else {
			flagK++
		}
		if flag == m {
			if temp.next == head {
				head = temp.next.next
			}
			flagTemp = temp.next.Id
			temp.next = temp.next.next
			break
		}
		temp = temp.next
	}
	return head, flagTemp
}

func main() {
	head := &dsp{}
	n1 := &dsp{
		Id: 1,
		Name: "100",
	}
	n2 := &dsp{
		Id: 2,
		Name: "102",
	}
	n3 := &dsp{
		Id: 3,
		Name: "103",
	}
	n4 := &dsp{
		Id: 4,
		Name: "104",
	}
	insertDsp(head, n1)
	insertDsp(head, n2)
	insertDsp(head, n3)
	insertDsp(head, n4)

	showDsp(head)

	query := []int{}
	index := -1
	k := 2
	m := 3
	for true {
		head, index = deleteDsp(head, k, m)
		if index != -1 {
			fmt.Println(index)
			query = append(query, index)
		}
		if head.next == nil {
			break
		}
	}
	fmt.Println(query)
}

5、链表问题：链表反转

链表反转的核心思想就是反转next的指针
使用两个指针作为临时指针

type link struct {
	id int
	next *link
}
func reversal(head *link) {
	// 当前节点
	cur := head
	// 上一个节点
	pre := nil
	for {
		if pre.next == nil {
			break
		}
		// 暂存cur的下一个节点
		temp := cur.next
		// 将当前指针指针指向上一个节点
		cur.next = pre
		// 后移cur和pre两个指针
		pre = cur
		cur = temp
	}
}

四、栈

1、初始化top指针下标为-1，同理top为-1表示栈为空

2、添加一个元素，top++

3、栈满时，top+1 = max

数据结构

type stack struct {
	max int // 最大存放个数
	top int // 栈顶
	arr [5]int
}

增删该查

// 入栈
func (s *stack) push(new int)  {
	if s.top == (s.max - 1) {
		fmt.Println("栈以满")
		return
	}
	s.top++
	s.arr[s.top] = new
}

// 出栈
func (s *stack) pop() (int, error) {
	if s.top == -1 {
		fmt.Println("栈为空")
		return -1, errors.New("空栈")
	}
	val := s.arr[s.top]
	s.top--
	return val, nil
}

// 显示栈内的数据
func (s *stack) showStack() {
	if s.top == -1 {
		return
	}
	for i := 0; i <= s.top; i++ {
		fmt.Println(s.arr[i])
	}
}

初始化

func ShowStack() {
	stack := stack{
		max: 5,
		top: -1,
		arr: [5]int{0, 0, 0, 0, 0},
	}
	// 先进后出
	stack.push(2)
	stack.push(1)
	stack.push(4)
	stack.push(9)
	stack.push(10)

	stack.pop() // 先出10
	stack.pop() // 先出9

	stack.showStack()
}

五、哈希散列表

所谓的散列表，就是将一组值，按照一定的规律，比如取模、取余等，分散在对应不同的链表中，查找只需要定位到对应的呢根链表中就可以加快查询速度。
比如，之前有100个数据，分为十组，每组就只有10个数据，这样，只需要从10个数据中查找，数据量越大，散列的优势就会大大加快了查询速度。

代码实现 结构体

// 存放结构体head的数组
type hashTable struct {
	Heads [7]*userLink
}

// 头节点
type userLink struct {
	Head *userState
}

// 节点
type userState struct {
	Id int
	State byte
	next *userState
}

添加节点

// 节点长度是7
// 依据 id 来判断，放入第几根根的链表中
func (this *hashTable) push(userState *userState)  {
	mod := userState.Id % 7
	this.Heads[mod].insert(userState)
}
// userState 插入的新节点
func (this *userLink) insert(userState *userState) {
	temp := this.Head
	if temp.next == nil {
		temp.next = userState
		return
	}
	for true {
		if temp.next == nil {
			temp.next = userState
			break
		} else if temp.next.Id == userState.Id {
			temp.next.State = userState.State
			break
		} else if temp.next.Id > userState.Id {
			userState.next = temp.next
			temp.next = userState
			break
		}
		temp = temp.next
	}
}

查找节点

func (this *hashTable) getState(id int)  {
	// 1. id 取模判断是那根节点
	mod := id % 7
	// 2. 获取对应节点的根节点
	temp := this.Heads[mod].Head
	// 3. 去对应的节点查找
	for true {
		if temp.next == nil {
			fmt.Println("没有找到")
			break
		}
		if temp.next.Id == id {
			fmt.Println("找到了：", temp.next)
			break
		}
		temp = temp.next
	}
}

输出节点

func (this *hashTable) show() {
	for i := 0; i < len(this.Heads); i++ {
		temp := this.Heads[i].Head
		fmt.Print("第",i,"个队列：")
		for true {
			if temp.next == nil {
				break
			}
			fmt.Print(temp.next, "  ")
			temp = temp.next
		}
		fmt.Println()
	}
}

六、二叉树

构建如下结构的二叉树



初始化：

type tree struct {
	id int
	left *tree
	right *tree
}
func ShowTree() {
	
	tree3 := &tree{
		id: 3,
	}

	tree4 := &tree{
		id: 4,
	}

	tree6 := &tree{
		id: 6,
	}

	tree5 := &tree{
		id: 5,
		left: tree6,
	}

	tree1 := &tree{
		id: 1,
		left: tree5,
	}

	tree2 := &tree{
		id: 2,
		left: tree3,
		right: tree4,
	}

	headTree := &tree{
		id: 0,
		left: tree1,
		right: tree2,
	}
	//  前序遍历
	headTree.Preface()
}

1、前序遍历

遍历顺序：先根节点，再左边所有节点，再右边所有节点

func (this *tree) Preface()  {
	if this == nil {
		return
	}
	fmt.Println("当前节点id：", this.id)
	this.left.Preface()
	this.right.Preface()
}

2、中序遍历

遍历顺序：先左边所有节点，再根节点，再右边所有节点

func (this *tree) MidOrder()  {
	if this == nil {
		return
	}
	this.left.MidOrder()
	fmt.Println("当前节点id：", this.id)
	this.right.MidOrder()
}

3、后序遍历

遍历顺序：先左边所有节点，再右边所有节点，再根节点

func (this *tree) Postscript()  {
	if this == nil {
		return
	}
	this.left.Postscript()
	this.right.Postscript()
	fmt.Println("当前节点id：", this.id)
}

七、排序

此处省略冒泡排序…

1. 选择排序

这个排序就是冒泡的升级版本，顺序依次遍历数组，没有都将数组中最小/最大的元素遍历出来放在标志位。

func SelectSort(flag int, arr []int) {
	if flag == len(arr) {
		return
	}
	// 标记最小位置下标
	tag := flag
	for i := flag; i < len(arr); i++ {
		if arr[i] < arr[tag] {
			tag = i
		}
	}
	arr[flag], arr[tag] = arr[tag], arr[flag]
	// 递归遍历+1位后的数组
	SelectSort(flag + 1, arr)
}

2. 插入排序

	func InsertSort(arr []int){
		for i:=1;i<len(arr);i++{
			// 记录当前排序的值、下标
			insertVal := arr[i]
			insertIndex := i - 1
			// 循环判断，如果满足条件就将insertIndex+1的值变为insertIndex的值
			for insertIndex >= 0 && arr[insertIndex] > insertVal {
				arr[insertIndex+1] = arr[insertIndex]
				insertIndex--
			}
			// 因为最后满足条件时insertIndex--
			// 若insertIndex + 1 == i则表示不满足条件无序置换
			// 故insertIndex+1的下标才为当前需要插入的值
			if insertIndex + 1 != i {
				arr[insertIndex+1] = insertVal
			}
		}
	}

3. 希尔排序

希尔排序其实也是一种插入排序，缩小增量的插入排序
希尔是将数组依次划分等间距的数组，对等间距数组进行排序

	func ShellSort(arr []int){
		// 1、划分为凉快数组
		for i := len(arr)/2; i > 0;i /= 2 {
			// 2、分别对两个数组进行插入排序
			for j := i; j < len(arr);j += i {
				insertVal := arr[j]
				insertIndex := j - i 
				for insertIndex >= 0 && arr[insertIndex] > insertVal {
					arr[insertIndex + i] = arr[insertIndex]
					insertIndex -= i
				}
				if insertIndex + i != j {
					arr[insertIndex + i] = insertVal
				}
			}
		}
	}

4. 快速排序

在我看来快速排序是效率最快的，也是最好理解的一种排序方式，写起来非常复合大脑的思考的结果，思路并不反人类

	func QuickSort(arr []int, left, right int) {
		if left > right {
			return
		}
		i := left
		j := right
		// 将最左元素作为基准数
		base := arr[left]
	
		for i != j {
			for arr[j] > base && i < j {
				j--
			}
			for arr[i] < base && i < j {
				i++
			}
			// 左右两边相交换
			arr[i], arr[j] = arr[j], arr[i]
		}
		
		// 此时i、j的位置相交，左边比基准大，右边比基准小
		// 第一轮循环结束，将基准与i、j相交的位置进行交换
		arr[left], arr[i] = arr[i], arr[left]

		// 先递归排序左边
		QuickSort(arr, left, i-1)
		// 再递归排序右边
		QuickSort(arr, i+1, right)
	}