数据结构

WuYiLong原创大约 8 分钟

数组

稀疏数组

定义:如果一个二维数组有很多相同的值或0，那么就可以将其转为稀疏数组，稀疏数组包含几行几列和值,第一行表示的是，原始数组的行和列以及有多少个有效的值

需求: 把一个二维数组转为稀疏数组，并把稀疏数组写入文件里
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {

	// 定义初始化的二维数组
	var arr = [3][3]int{{0, 1, 0}, {0, 0, 3}, {0, 0, 0}}
	fmt.Println("****原始二维数组*****")
	for i := 0; i < len(arr); i++ {
		for j := 0; j < len(arr[i]); j++ {
			fmt.Printf("%v\t", arr[i][j])
		}
		fmt.Println()
	}

	// 判断二维数组中有多少有效的值
	sum := 0
	for _, v := range arr {
		for _, v := range v {
			if v != 0 {
				sum++
			}
		}
	}
	// 获得稀疏数组的行，遍历二维数组确定不为0的数
	var arr2 [][3]int
	a := [3]int{len(arr), len(arr[0]), sum}
	arr2 = append(arr2, a)
	for i := 0; i < len(arr); i++ {
		for j := 0; j < len(arr[i]); j++ {
			if arr[i][j] != 0 {
				a := [3]int{i, j, arr[i][j]}
				arr2 = append(arr2, a)
			}
		}
	}

	fmt.Println("*****转化后的二维数组****")
	file,err :=os.Create("1.txt")
	if err != nil {
		fmt.Printf("err->%v",err)
	}
	//file.WriteString("hello")
	write :=bufio.NewWriter(file)
	for i := 0; i < len(arr2); i++ {
		for j := 0; j < len(arr2[i]); j++ {

			write.WriteString(strconv.FormatInt(int64(arr2[i][j]),10)+"\t")
			fmt.Printf("%v\t", arr2[i][j])
		}
		fmt.Println()
		write.WriteString("\n")

	}

	// 数据写入缓存后，必须调用，才能真正把缓存中的数据写入文件中
	write.Flush()

}

 // 输出结果
 ****原始二维数组*****
0	1	0	
0	0	3	
0	0	0	
*****转化后的二维数组****
3	3	2	 // 分别表示原始数组是个3行3列的数组，并且有2个有效的值
0	1	1	 // 表示有效值1在第1行第2列
1	2	3  // 表示有效值3在第2行第3列

队列

提示

先进先出原则

数组模拟基本队列

// queue.go
// 模拟基本队列
type Queue struct {
	maxSize int    // 表示数组的容量
	array   [5]int // 初始化大小为5的数组
	front   int    // 表示 首部指针,默认-1
	tail    int    // 表示尾部指针，默认-1
}

func NewQueue(maxSize int, front int, tail int) *Queue {

	return &Queue{
		maxSize: maxSize,
		front:   front,
		tail:    tail,
	}
}

func (queue *Queue) AddQueue(n int) (err error) {
	// 判断队列元素是否已满
	if queue.tail == queue.maxSize-1 {
		return errors.New("队列已满，不能再添加元素\n")
	}

	queue.tail++
	queue.array[queue.tail] = n
	return
}

func (queue *Queue) ShowQueue() {
	for i := queue.front+1;i<queue.tail+1;i++ {
		fmt.Printf("array[%v]=%v\n",i,queue.array[i])
	}
}

func (queue *Queue) GetQueue() (value int,err error){
	if queue.front == queue.tail {
		return -1,errors.New("已经没有元素可取了")
	}
	queue.front++
	return queue.array[queue.front],nil
}

// main.go
func main() {
	queue := utils.NewQueue(5,-1,-1)
	var key int
	var val int
	for {
		fmt.Println("1.添加队列元素")
		fmt.Println("2.查看队列")
		fmt.Println("3.取出队列元素")
		fmt.Println("4.退出")
		fmt.Scanln(&key)

		switch key {
		case 1:
			fmt.Println("请输入进入队列的数字")
			fmt.Scanln(&val)
			err := queue.AddQueue(val)
			if err != nil {
				fmt.Println(err)
			}
		case 2:
			queue.ShowQueue()
		case 3:
			v,err := queue.GetQueue()
			if err != nil {
				fmt.Println("err->",err)
			}
			fmt.Printf("取出的元素是->%v\n",v)
		case 4:
			os.Exit(0)
		}
	}
}

使用链表模拟队列


// user.go
// 使用简单链表模拟队列,先进先出
type User struct {
	id       int    // 用户编号
	name     string // 用户名
	age      int    // 用户年龄
	nextUser *User  // 表示连接下一个用户节点
}

func NewUser(id int, name string, age int) *User {
	return &User{
		id:   id,
		name: name,
		age:  age,
	}
}

func (user *User) InsertUser(head *User, newUser *User) {

	for {
		temp := head
		if temp.nextUser == nil {
			temp.nextUser = newUser
			break
		}
		head = temp.nextUser
	}
}

func (user *User) ListUser(head *User) {
	for {
		temp := head
		if temp.nextUser == nil {
			break
		}
		fmt.Printf("[%v,%v,%v]->", temp.nextUser.id, temp.nextUser.name, temp.nextUser.age)
		head = temp.nextUser
	}
	fmt.Println()
}

func (user *User) DeleteUser(head *User) (User, error) {
	temp := head
	if temp.nextUser == nil {
		return User{}, errors.New("已经没有可删除的数据了")
	}
	// 保存下一个元素的值
	nextUserVal := *temp.nextUser
	head.nextUser = temp.nextUser.nextUser // 表示头结点连接下下一个节点，断开的节点等待回收
	return nextUserVal,nil

}

func (user *User) GetUser() {
	fmt.Printf("[%v,%v,%v]\n",user.id,user.name,user.age)
}

// main.go
func main() {
	// 初始化一个头结点
	head := new(utils.User)
	var key int
	var id int
	var name string
	var age int
	for {
		fmt.Println("1.添加队列元素")
		fmt.Println("2.展示队列")
		fmt.Println("3.删除队列元素")
		fmt.Println("4.退出系统")

		fmt.Scanln(&key)
		switch key {
		case 1:
			fmt.Println("输入id号")
			fmt.Scanln(&id)
			fmt.Println("输入姓名")
			fmt.Scanln(&name)
			fmt.Println("输入年龄")
			fmt.Scanln(&age)
			user := utils.NewUser(id,name,age)
			head.InsertUser(head,user)
		case 2:
			head.ListUser(head)
		case 3:
			user,err := head.DeleteUser(head)
			if err != nil {
				fmt.Printf("err->%v\n",err)
				break
			}
			user.GetUser()
		case 4:
			os.Exit(0)
		}
	}
}

链表

单向链表

需求:手写内存数据库，按照id号从小到大排序,完成对数据库的增删改查


// 有序的单向链表(增删改查) person.go
type Person struct {
	id         int     // 用户 编号
	name       string  // 用户名
	age        int     // 用户年龄
	nextPerson *Person // 表示连接下一个用户节点
}

func NewPerson(id int, name string, age int) *Person {
	return &Person{
		id:   id,
		name: name,
		age:  age,
	}
}

func (person *Person) Insert(head *Person, newPerson *Person) {
	for {
		temp := head
		if temp.nextPerson == nil {
			temp.nextPerson = newPerson
			break
		} else if temp.nextPerson.id > newPerson.id {
			newPerson.nextPerson = temp.nextPerson
			temp.nextPerson = newPerson
			break
		}
		head = temp.nextPerson
	}
}

func (person *Person) List(head *Person) {
	for {
		temp := head
		if temp.nextPerson == nil {
			break
		}
		fmt.Printf("[%v,%v,%v]->", temp.nextPerson.id, temp.nextPerson.name, temp.nextPerson.age)
		head = temp.nextPerson
	}
	fmt.Println()
}

// 根据id号删除对应的数据
func (person *Person) Delete(head *Person,id int) (err error) {
	for {
		temp := head
		if temp.nextPerson == nil {
			return errors.New("没有可删除的数据了")
		}

		if id == temp.nextPerson.id {
			temp.nextPerson = temp.nextPerson.nextPerson

			break
		}

		head = temp.nextPerson
	}
	return nil
}

// 根据id号更新对应的数据
func (person *Person) Update(head *Person,newPerson *Person) (err error) {
	for {
		temp := head
		if temp.nextPerson == nil {
			return errors.New("没有数据可更新")
		}
		if newPerson.id == temp.nextPerson.id {
			newPerson.nextPerson = temp.nextPerson.nextPerson
			temp.nextPerson = newPerson
			break
		}
		head = temp.nextPerson
	}
	return nil
}

// main.go
func main() {
// 初始化一个头结点
	head := new(utils.Person)
	var key int
	var id int
	var name string
	var age int
	for {
		fmt.Println("1.添加链表")
		fmt.Println("2.展示链表")
		fmt.Println("3.删除链表")
		fmt.Println("4.更新链表")
		fmt.Println("5.退出系统")
		fmt.Scanln(&key)
		switch key {
		case 1:
			fmt.Println("输入id号")
			fmt.Scanln(&id)
			fmt.Println("输入姓名")
			fmt.Scanln(&name)
			fmt.Println("输入年龄")
			fmt.Scanln(&age)
			person := utils.NewPerson(id,name,age)
			head.Insert(head,person)
		case 2:
			head.List(head)
		case 3:
			fmt.Println("输入要删除的id号")
			var id int
			fmt.Scanln(&id)
			err := head.Delete(head,id)
			if err != nil {
				fmt.Printf("err->%v\n",err)
				break
			}
			fmt.Println("删除成功")
		case 4:
			//fmt.Println("输入要更新的数据")
			fmt.Println("输入id号")
			fmt.Scanln(&id)
			fmt.Println("输入姓名")
			fmt.Scanln(&name)
			fmt.Println("输入年龄")
			fmt.Scanln(&age)
			person := utils.NewPerson(id,name,age)
			err := head.Update(head,person)
			if err != nil {
				fmt.Printf("err->%v\n",err)
				break
			}
			fmt.Println("更新成功")
		case 5:
			os.Exit(0)

		}
	}
}

双向链表

需求:使用双向链表，按照id号从小到大排序，和从大到小排序，并完成查询，列表，删除功能

main.go

package main

import (
	"demo/utils"
	"fmt"
	"os"
)

func main() {

	var id int
	var name string
	var age int
	head := new(utils.User)
	for {
		fmt.Println("1.添加用户")
		fmt.Println("2.展示用户列表")
		fmt.Println("3.删除用户")
		fmt.Println("3.退出系统")
		fmt.Println("提示请输入1~4")
		var key int
		fmt.Scanln(&key)
		switch key {
		case 1:
			fmt.Println("请输入用户编号:")
			fmt.Scanln(&id)
			fmt.Println("请输入用户名:")
			fmt.Scanln(&name)
			fmt.Println("请输入年龄:")
			fmt.Scanln(&age)
			user := utils.NewUser(id,name,age)
			head.InsertUser(head,user)
		case 2:
			head.ListUser(head)
			head.ListUser2(head)
		case 3:
			fmt.Println("请输入要删除的id号")
			var id int
			fmt.Scanln(&id)
			err := head.DeleteUser(head,id)
			if err !=nil {
				fmt.Println("err->",err)
			}
			fmt.Println("删除成功")
		case 4:
			os.Exit(0)
		}

	}
}

double_link.go

package utils

import (
	"errors"
	"fmt"
)

// 需求:使用双向链表，按照id号从小到大排序，和从大到小排序
// 有序的双向链表(增删改查)
type User struct {
	id       int    // 用户编号
	name     string // 用户名
	age      int    // 用户年龄
	nextUser *User  // 表示下一个用户节点
	preUser *User  // 表示上一个用户节点
}

func NewUser(id int, name string, age int) *User {
	return &User{
		id:   id,
		name: name,
		age:  age,
	}
}

func (user *User) InsertUser(head *User, newUser *User) {

	for {
		temp := head
		if temp.nextUser == nil {
			temp.nextUser = newUser
			newUser.preUser = temp
			break
		} else if temp.nextUser.id > newUser.id {
			newUser.nextUser = temp.nextUser
			temp.nextUser.preUser = newUser
			newUser.preUser = temp
			temp.nextUser = newUser
			break
		}
		head = temp.nextUser
	}
}

func (user *User) ListUser(head *User) {
	for {
		temp := head
		if temp.nextUser == nil {
			break
		}
		fmt.Printf("[%v,%v,%v]->", temp.nextUser.id, temp.nextUser.name, temp.nextUser.age)
		head = temp.nextUser
	}
	fmt.Println("从小到大打印")
}

func (user *User) ListUser2(head *User) {
	for {
		temp := head
		if temp.nextUser == nil {
			break
		}
		head = temp.nextUser
	}

	for {
		temp := head
		if temp.preUser == nil {
			break
		}
		fmt.Printf("[%v,%v,%v]->", temp.id, temp.name, temp.age)
		head = temp.preUser

	}
	fmt.Println("从大到小打印")
}

// 根据id号删除对应的数据
func (user *User) DeleteUser(head *User,id int) (err error) {
	for {
		temp := head
		if temp.nextUser == nil {
			return errors.New("没有对应的id号可删除的数据了")
		}

		if id == temp.id {
			temp.preUser.nextUser = temp.nextUser
			temp.nextUser.preUser = temp.preUser
			break
		}

		head = temp.nextUser
	}
	return nil
}

环形单向链表

### 环形链表
- carNode.go
```go
package utils

import "fmt"

// 单向环形链表
type CarNode struct {
	id   int      // 编号
	name string   // 车名
	next *CarNode // 表示连接下一个
}

func NewCarNode(id int, name string) *CarNode {
	return &CarNode{
		id:   id,
		name: name,
	}
}

func (car *CarNode) AddCar(head *CarNode, newCar *CarNode) {
	// 判断是否是第一个
	if head.next == nil {
		head.id = newCar.id
		head.name = newCar.name
		head.next = head
		return
	}
	temp := head
	for {
		if temp.next == head {
			break
		}
		temp = temp.next
	}
	temp.next = newCar
	newCar.next = head
}

func (car *CarNode) ListCar(head *CarNode) {
	temp := head
	if temp.next == nil {
		fmt.Println("这是一个空链表")
		return
	}

	for {
		if temp.next == head {
			fmt.Printf("[%v,%s,%v,%v]->\n",temp.id,temp.name,temp,temp.next)
			break
		}
		fmt.Printf("[%v,%s,%v,%v]->\n",temp.id,temp.name,temp,temp.next)
		temp = temp.next
	}
}


func (car *CarNode) DeleteCar(head *CarNode,id int)  (err error) {
	temp := head

	if temp.next == nil {
		fmt.Println("这是一个空链表")
		return
	}

	for {
		if temp.id == id {
			temp.name = temp.next.name
			temp.id = temp.next.id
			temp.next = temp.next.next
			break
		}
		if temp.next.next == head {
			if temp.next.id ==id {
				temp.next = head
				break
			}
		}
		temp = temp.next
	}
	return nil
}

main.go

package main

import (
	"demo/utils"
	"fmt"
	"os"
)
func main() {
	var id int
	var name string
	//var age int
	head := new(utils.CarNode)
	for {
		fmt.Println("1.添加车")
		fmt.Println("2.展示车列表")
		fmt.Println("3.删除列表")
		fmt.Println("4.退出系统")
		fmt.Println("提示请输入1~3")
		var key int
		fmt.Scanln(&key)
		switch key {
		case 1:
			fmt.Println("请输入车编号:")
			fmt.Scanln(&id)
			fmt.Println("请输入车名:")
			fmt.Scanln(&name)
			car := utils.NewCarNode(id,name)
			head.AddCar(head,car)
		case 2:
			head.ListCar(head)
		case 3:
			fmt.Println("输入要删除的id")
			var id int
			fmt.Scanln(&id)
			err := head.DeleteCar(head,id)
			if err != nil {
				fmt.Println("err->",err)
			}
			fmt.Println("删除成功")
		case 4:
			os.Exit(0)
		}

	}
}

约瑟夫问题

设编号为1，2，....n的n个人围坐一圈，约定编号为k(1<=k<=n)的人，从1开始报数，数到m个人出列，它的下一位又从一开始报数，数到m的那个人又出列，依此类推，直到所有的人出列为止，由此产生一个出队编号的序列。

数据结构

# 数组

# 稀疏数组

# 队列

# 数组模拟基本队列

# 使用链表模拟队列

# 链表

# 单向链表

# 双向链表

# 环形单向链表

# 约瑟夫问题

数组