一.概述
1.概念
线性表是最基本、最简单、也是最常用的一种数据结构。一个线性表是n个具有相同特性的数据元素的有限序列。
可以想象成在车站买票的情况, 大家都在窗口外面排队买票,如下:
2.线性表的术语说明
- 前驱元素： 若A元素在B元素的前面，则称A为B的前驱元素
- 后继元素： 若B元素在A元素的后面，则称B为A的后继元素
3.线性表的特征
数据元素之间具有一种“一对一”的逻辑关系
- 第一个数据元素没有前驱，这个数据元素被称为头结点；
- 最后一个数据元素没有后继，这个数据元素被称为尾结点；
- 除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继
如果把线性表用数学语言来定义，则可以表示为(a1,...ai-1,ai,ai+1,...an)，ai-1领先于ai,ai领先于ai+1，称ai-1是ai的前驱元素，ai+1是ai的后继元素
4.线性表的分类
线性表中数据存储的方式可以是顺序存储，也可以是链式存储，按照数据的存储方式不同，可以把线性表分为:
- 顺序表
- 链表
二.顺序表
1.概念
顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元，依次存储线性表中的各个元素、使得线性表中在逻辑结构上响应的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。
2.顺序表的实现
go语言中，数组在初始化之后大小就无法改变，于是我们选择更加灵活的切片来初始化
2.1初始化
算法步骤：
1、为顺序表L动态分配一个预定义大小的切片。
2、将表的当前长度设为0。
--------------------------------------------------
type Book struct {ISBN stringname stringprice int
}type SqList struct {books []Book //books定义为一个由数据结构为Book组成的切片MAXSIZE int //最大长度length int //当前长度
}//顺序表的初始化
func InitList(maxsize int, arr []Book) *SqList {//初始化结构体实体list := &SqList{books: make([]Book, 0, maxsize),//即数据类型为Book，长度为0，容量为maxsizeMAXSIZE: maxsize,length: 0}//将传入的数据导入初始化的实体for i := range arr {list.books = append(list.books, arr[i])list.length++}return list
}切片(slice)又称动态数组，依托数组实现，可以方便的进行扩容和传递，通过切片的数据结构，可以将切片理解为一片连续的存储空间加上长度和容量标识
2.2顺序表的取值
取值操作是根据指定的位置序号i，获取顺序表中第i个数据元素的值
算法步骤：
1、判断指定的位置序号i值是否合理(1<=i<=L.length)，若不合理返回err。
2、若i值合理，则将第i个数据元素赋值给一变量并返回该变量。
--------------------------------------------------
//顺序表的取值
func GetElem(i int, list *SqList) (elem Book) {//判断i的值是否合理if i < 1 || i > list.MAXSIZE {fmt.Println("err")return}el := list.books[i]return el
}2.3顺序表的查找
顺序表的查找操作是根据指定的元素值e，查找顺序表中第1个与e相等的元素,若查找成功，则返回该元素在表中的位置序号，若查找失败，则返回0
算法步骤：
1、从第一个元素起，以此和e相比较，若找到与e相等的元素，则查找成功返回该元素的序号。
2、若查遍整个顺序表都没有找到，则查找失败。
--------------------------------------------------
//顺序表的查找
func locateElem(e Book, list *SqList) {for x := range list.books {if e == list.books[x] {fmt.Printf("查找成功，元素为第%d个\n", x)return}}fmt.Println("查找失败")return
}2.3顺序表的插入
线性表的插入操作是指在表的第i个位置插入一个新的数据元素e，使长度为n的线性表变成长度为n+1的线性表
算法步骤：
1、判断插入位置i是否合法(1<=i<=n+1)，不合法返回err。
2、判断顺序表的存储空间是否已满，若满则返回err。
3、将第n个至第i个位置的元素依次向后移动一个位置，空出第i个位置(i = n+1时无需移动)。
4、将要插入的新元素e放入第i个位置。
5、表长加1。
--------------------------------------------------
//顺序表的插入--将插入的新元素e放入第i个位置
func InsertElem(i int, e Book, list *SqList) {if i < 1 || i > list.MAXSIZE {//i值不合法fmt.Println("请检查i值")return}if list.MAXSIZE == list.length {//当前存储空间已满fmt.Println("存储空间已满")return}var bk Book//为新元素创建“座位”list.books = append(list.books, bk)for x := list.length - 1; x >= i-1; x-- {list.books[x+1] = list.books[x]}list.books[i-1] = elist.length++fmt.Println("插入成功")return
}2.4顺序表的删除
线性表的删除操作是指将表的第i个元素删去，将长度为n的线性表变成长度为n-1的线性表
算法步骤：
1、判断删除位置i是否合法(1<=i<=n)，若不合法则返回err。
2、将第i+1个至第n个的元素一次向前移动一个位置(i =n时无需移动)。
3、表长减1.
--------------------------------------------------
//顺序表的删除--将表的第i个元素删去
func DeleteElem(i int, list *SqList) *SqList {if i < 1 || i > list.length {fmt.Println("请检查i值")return list}//这里只展示删除点前后元素位置移动操作，直接利用append()函数特性进行“删除”更常用for x := i; x < list.length; x++ {list.books[x-1] = list.books[x]}list.length--//从i到表位整体前移1个单位长度，剔除表尾冗余。list.books = append(list.books[:list.length])fmt.Println("删除成功")return list
}
2.6完整代码
完整代码
--------------------------------------------------
package mainimport ("fmt"
)type Book struct {ISBN stringname stringprice int
}type SqList struct {books []Book //books定义为一个由数据结构为Book组成的切片MAXSIZE int //最大长度length int //当前长度
}//顺序表的初始化
func InitList(maxsize int, arr []Book) *SqList {//初始化结构体实体list := &SqList{books: make([]Book, 0, maxsize),//即数据类型为Book，长度为0，容量为maxsizeMAXSIZE: maxsize,length: 0}//将传入的数据导入初始化的实体for i := range arr {list.books = append(list.books, arr[i])list.length++}return list
}func GetElem(i int, list *SqList) (elem Book) {//判断i的值是否合理if i < 1 || i > list.MAXSIZE {fmt.Println("err")return}el := list.books[i]return el
}//顺序表的查找
func locateElem(e Book, list *SqList) {for x := range list.books {if e == list.books[x] {fmt.Printf("查找成功，元素为第%d个\n", x)return}}fmt.Println("查找失败")return
}//顺序表的插入--将插入的新元素e放入第i个位置
func InsertElem(i int, e Book, list *SqList) {if i < 1 || i > list.MAXSIZE {//i值不合法fmt.Println("请检查i值")return}if list.MAXSIZE == list.length {//当前存储空间已满fmt.Println("存储空间已满")return}var bk Book//为新元素创建“座位”list.books = append(list.books, bk)for x := list.length - 1; x >= i-1; x-- {list.books[x+1] = list.books[x]}list.books[i-1] = elist.length++fmt.Println("插入成功")return
}//顺序表的删除--将表的第i个元素删去
func DeleteElem(i int, list *SqList) *SqList {if i < 1 || i > list.length {fmt.Println("请检查i值")return list}//这里只展示删除点前后元素位置移动操作，直接利用append()函数特性进行“删除”更常用for x := i; x < list.length; x++ {list.books[x-1] = list.books[x]}list.length--//从i到表位整体前移1个单位长度，剔除表尾冗余。list.books = append(list.books[:list.length])fmt.Println("删除成功")return list
}func main() {arr := []Book{Book{"978-7-115-37950-1", "Book1", 35},Book{"978-7-115-37950-2", "Book2", 54},Book{"978-7-115-37950-3", "Book3", 31},Book{"978-7-115-37950-4", "Book4", 26},Book{"978-7-115-37950-5", "Book5", 42},Book{"978-7-115-37950-6", "Book6", 48},Book{"978-7-115-37950-7", "Book7", 16}}L := InitList(100, arr)//初始化顺序表fmt.Println(L)//顺序表的取值elem := GetElem(3, L)fmt.Println(elem)//顺序表的查找test1 := Book{"978-7-115-37950-3", "Book3", 31}locateElem(test1, L)//顺序表的插入test2 := Book{"978-7-115-37950-a", "插入测试", 66}InsertElem(5, test2, L)fmt.Println(L)//顺序表的删除L = DeleteElem(4, L)fmt.Println(L)
}2.9总结
线性表底层是一个数组,所以,查询比较快,因为底层是连续的地址,可以直接通过索引快速定位到元素,增删比较慢,每次增删都伴随着大量的元素地址修改,效率是比较低
三.链表
针对上面顺序表的效率问题,使用另外一种存储结构实现线性表，链式存储结构解决.链表是一种物理存储单元上非连续、非顺序的存储结构，其物理结构不能只管的表示数据元素的逻辑顺序，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结点（链表中的每一个元素称为结点）组成，结点可以在运行时动态生成
那如何使用链表呢？按照面向对象的思想，可以设计一个类，来描述结点这个事物，用一个属性描述这个结点存储的元素，用来另外一个属性描述这个结点的下一个结点,而链表在数据结构中又分为:
- 单向链表
- 双向链表
- 环形链表
3.1单向链表
单向链表是链表的一种，它由多个结点组成，每个结点都由一个数据域和一个指针域组成，数据域用来存储数据，指针域用来指向其后继结点。 一般来说,为了比较好的对单链表进行增删改查的操作,都会给其设置一个头结点,头结点的作用主要是用来标识链表头,本身这个结点不存放数据，指针域指向第一个真正存储数据的结点
单向链表代码实现
使用带 head 头的单向链表实现:
水浒英雄排行榜管理
完成对英雄人物的增删改查操作
在添加英雄时，直接添加到链表的尾部
package mainimport ("fmt"
)//定义一个HeroNode结构体
type HeroNode struct {no intname stringnickname stringnext *HeroNode //表示指向下一个结点
}//给链表插入一个结点
//编写第一种插入方式:在单链表的最后插入
func InsertHeroNode(head *HeroNode, newHeroNode *HeroNode) {//1.先找到链表最后这个结点//2.创建一个辅助结点temp := headfor {if temp.next == nil { //表示找到了最后break}temp = temp.next //让temp不断指向下一个结点}//当for结束时,temp一定是找到了最后一个节点的//3.将newHeroNode加入道最后temp.next = newHeroNode
}//编写第二种插入方式: 根据no的编号从小到大插入
func InsertHeroNode2(head *HeroNode, newHeroNode *HeroNode) {//1.先找适当的结点//2.创建一个辅助结点temp := headflag := true//让插入结点的no和temp的下一个结点的no比较for {if temp.next == nil { //表示到了最后的链表break} else if temp.next.no > newHeroNode.no {//说明newHeroNode就应该插入到temp后面break} else if temp.next.no == newHeroNode.no {//说明链表中已经有这个no,就不允许插入了flag = falsebreak}temp = temp.next //让temp不断指向下一个结点}if !flag {fmt.Println("已存在no=", newHeroNode.no)return} else {newHeroNode.next = temp.nexttemp.next = newHeroNode}
}//显示链表的所有结点信息
func ListHeroNode(head *HeroNode) {//1.创建一个辅助结点temp := head//先判断该链表是不是空的链表if temp.next == nil { fmt.Println("空的链表")return}//2.遍历链表for {fmt.Printf("[%d, %s, %s] ==> ", temp.next.no, temp.next.name, temp.next.nickname)//判断链表是否最后temp = temp.nextif temp.next == nil {break}}
}//删除一个结点
func DelHeroNode(head *HeroNode, id int) {temp := headflag := false//找到要删除的结点的no,和temp的下一个结点的no比较for {if temp.next == nil {//说明到了链表的最后break} else if temp.next.no == id {//说明找到了flag = truebreak}temp = temp.next}if flag {//找到了,就行删除操作temp.next = temp.next.next // 这样目标结点就会成为一个垃圾结点,被系统回收} else {fmt.Println("要删除的结点id不存在")}
}
func main() {//1.先创建一个头结点head := &HeroNode{}//2.创建一个新的结点head1 := &HeroNode{no: 1,name: "宋江",nickname: "及时雨",}head2 := &HeroNode{no: 2,name: "陆静怡",nickname: "玉骑铃",}head3 := &HeroNode{no: 3,name: "零充",nickname: "包子头",}//3.加入//第一种方法// InsertHeroNode(head, head1)// InsertHeroNode(head, head3)// InsertHeroNode(head, head2)//第二种方法InsertHeroNode2(head, head1)InsertHeroNode2(head, head3)InsertHeroNode2(head, head2)//4.列表ListHeroNode(head)//5.删除fmt.Println()DelHeroNode(head, 2)ListHeroNode(head)
}3.2双向链表
双向链表也叫双向表，是链表的一种，它由多个结点组成，每个结点都由一个数据域和两个指针域组成，数据域用来存储数据，其中一个指针域用来指向其后继结点，另一个指针域用来指向前驱结点。链表的头结点的数据域不存储数据，指向前驱结点的指针域值为null，指向后继结点的指针域指向第一个真正存储数据的结点。
使用带 head 头的双向链表实现：水浒英雄排行榜管理
单向链表的缺点分析:
(1).单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找
(2).单向链表不能自我删除，需要靠辅助节点，而双向链表，则可以自我删除，所以前面单链表删除时节点，总是找到 temp 的下一个节点来删除
package mainimport ("fmt"
)//定义一个HeroNode结构体
type HeroNode struct {no intname stringnickname stringpre *HeroNode //表示指向上一个结点next *HeroNode //表示指向下一个结点
}//给链表插入一个结点
//编写第一种插入方式:在链表的最后插入
func InsertHeroNode(head *HeroNode, newHeroNode *HeroNode) {//1.先找到链表最后这个结点//2.创建一个辅助结点temp := headfor {if temp.next == nil { //表示找到了最后break}temp = temp.next //让temp不断指向下一个结点}//当for结束时,temp一定是找到了最后一个节点的//3.将newHeroNOde加入道最后temp.next = newHeroNode//4.再将temp指向newHeroNode.prenewHeroNode.pre = temp
}//编写第二种插入方式: 根据no的编号从小到大插入
func InsertHeroNode2(head *HeroNode, newHeroNode *HeroNode) {//1.先找适当的结点//2.创建一个辅助结点temp := headflag := true//让插入结点的no和temp的下一个结点的no比较for {if temp.next == nil { //表示到了最后的链表break} else if temp.next.no > newHeroNode.no {//说明newHeroNode就应该插入到temp后面break} else if temp.next.no == newHeroNode.no {//说明链表中已经有这个no,就不允许插入了flag = falsebreak}temp = temp.next //让temp不断指向下一个结点}if !flag {fmt.Println("已存在no=", newHeroNode.no)return} else {newHeroNode.next = temp.nextnewHeroNode.pre = tempif temp.next != nil {temp.next.pre = newHeroNode}temp.next = newHeroNode}
}//显示链表的所有信息:顺序方式
func ListHeroNode(head *HeroNode) {//1.创建一个辅助结点temp := head//先判断该链表是不是空的链表if temp.next == nil { fmt.Println("空的链表")return}//2.遍历链表for {fmt.Printf("[%d, %s, %s] ==> ", temp.next.no, temp.next.name, temp.next.nickname)//判断链表是否最后temp = temp.nextif temp.next == nil {break}}
}//显示链表的所有信息:逆序方式
func ListHeroNode2(head *HeroNode) {//1.创建一个辅助结点temp := head//先判断该链表是不是空的链表if temp.next == nil { fmt.Println("空的链表")return}//2.让temp定位到双向链表的最后结点for {if temp.next == nil {break}temp = temp.next}//2.遍历链表for {fmt.Printf("[%d, %s, %s] <== ", temp.no, temp.name, temp.nickname)//判断链表是否到headtemp = temp.preif temp.pre == nil {break}}
}//删除一个结点
func DelHeroNode(head *HeroNode, id int) {temp := headflag := false//找到要删除的结点的no,和temp的下一个结点的no比较for {if temp.next == nil {//说明到了链表的最后break} else if temp.next.no == id {//说明找到了flag = truebreak}temp = temp.next}if flag {//找到了,就行删除操作temp.next = temp.next.next // 这样目标结点就会成为一个垃圾结点,被系统回收if temp.next != nil { //当下一个结点存在时,才操作temp.next.pre = temp}} else {fmt.Println("要删除的结点id不存在")}
}
func main() {//1.先创建一个头结点head := &HeroNode{}//2.创建一个新的结点head1 := &HeroNode{no: 1,name: "宋江",nickname: "及时雨",}head2 := &HeroNode{no: 2,name: "陆静怡",nickname: "玉骑铃",}head3 := &HeroNode{no: 3,name: "零充",nickname: "包子头",}//3.加入//第一种方法InsertHeroNode(head, head1)InsertHeroNode(head, head2)InsertHeroNode(head, head3)//第二种方法// InsertHeroNode2(head, head1)// InsertHeroNode2(head, head3)// InsertHeroNode2(head, head2)// //4.列表//顺序ListHeroNode(head)fmt.Println()//逆序ListHeroNode2(head)// //5.删除// fmt.Println()DelHeroNode(head, 2)ListHeroNode(head)
}3.3链表反转
需求：
原链表中数据为：1->2->3>4
反转后链表中数据为：4->3->2->1使用递归可以完成反转，递归反转其实就是从原链表的第一个存数据的结点开始，依次递归调用反转每一个结点，直到把最后一个结点反转完毕，整个链表就反转完毕。
package mainimport "fmt"// 定义链表节点结构体
type ListNode struct {Val intNext *ListNode
}// 单链表反转的递归实现
func reverseList(head *ListNode) *ListNode {// 递归终止条件：当前节点为空或者下一个节点为空if head == nil || head.Next == nil {return head}// 反转后续链表，并将当前节点指向它newHead := reverseList(head.Next)head.Next.Next = headhead.Next = nil // 断开当前节点的next引用，防止循环链接return newHead
}func main() {// 创建一个示例链表：1->2->3->4->5head := &ListNode{Val: 1}p := headfor i := 2; i <= 5; i++ {p.Next = &ListNode{Val: i}p = p.Next}// 反转链表newHead := reverseList(head)// 打印反转后的链表：5->4->3->2->1for p := newHead; p != nil; p = p.Next {fmt.Printf("%d ", p.Val)}
}3.4快慢指针
快慢指针指的是定义两个指针，这两个指针的移动速度一快一慢，以此来制造出自己想要的差值,这个差值可以找到链表上相应的结点。一般情况下，快指针的移动步长为慢指针的两倍
案例:为了判断一个链表或一串渐进式变化的数据是否存在“环”，可以使用这种方法，一般慢指针走一步，快指针走两步，最终一定会相遇。使用快慢指针的思想，把链表比作一条跑道，链表中有环， 那么这条跑道就是一条圆环跑道，在一条圆环跑道中，两 个人有速度差，那么迟早两个人会相遇，只要相遇那么就说明有环
3.5单向环形链表
循环链表，顾名思义，链表整体要形成一个圆环状。在单向链表中，最后一个节点的指针为null，不指向任何结点，因为没有下一个元素了。要实现循环链表，我们只需要让单向链表的最后一个节点的指针指向头结点即可。
josephu 问题:
设编号为1, 2 ，... n 的n个人围坐一圈, 约定编号为 k (1<=k<=n ）的人从 1 开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列
提示：
用一个不带头结点的循环链表来处理josephu问题,先构成一个有 n 个结点的单循环链表，然后由 k 结点起从1开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除,算法结束
案例:
完成对单向环形链表的添加结点,删除结点和显示
删除一个环形单向琏表的思路如下：
1.先让 temp 指向 head
2.让 helper 指向环形链表最后
3.让temp 和要删除的id进行比较,如果相同，则同helper完成删除(这里必须考虑如果删除的就是头结点)
package mainimport ("fmt"
)//定义一个CatNode结构体
type CatNode struct {no int //猫的编号name string //名字next *CatNode //下一个结点
}//插入环形链表
func InsertCatNode(head *CatNode, newCatNode *CatNode) {//判断是不是添加第一只猫if head.next == nil {head.no = newCatNode.nohead.name = newCatNode.namehead.next = head // 构成一个环形fmt.Println(newCatNode, "加入到环形的链表")return } //先定义一个临时的变量,找到环形的最后结点temp := headfor {if temp.next == head {break}temp = temp.next}//加入到链表temp.next = newCatNodenewCatNode.next = head
}//显示环形链表
func ListCircleLink(head *CatNode) {temp := headif temp.next == nil {fmt.Println("空的链表")return}for {fmt.Printf("猫的信息为:no=%d,name=%s, =>\n", temp.no, temp.name)if temp.next == head {//说明链表环状查询完毕break}temp = temp.next}
}//删除
func DelCircleCatNode(head *CatNode, id int) *CatNode {temp := headhelper := head//空链表if temp.next == nil {fmt.Println("空链表")return head}//如果只有一个结点if temp.next == head {temp.next = nilreturn head}//将helper定位到环形链表最后for {if helper.next == head {break}helper = helper.next}//如果有两个以及以上的结点flag := truefor {if temp.next == head { //说明已经比较到最后一个(最后一个还没比较)break}if temp.no == id { // 找到了if temp == head { // 说明删除的是头结点head = temp.next}//可以在这里删除helper.next = temp.nextfmt.Printf("猫:%d已经被删除了\n", id)flag = falsebreak}temp = temp.next // 移动,目的是为了 "比较"helper = helper.next // 移动,目的是为了删除结点}//这里还要比较一次if flag { // 如果flag为true,则上面没有删除if temp.no == id {helper.next = temp.nextfmt.Printf("猫:%d已经被删除了\n", id)} else {fmt.Printf("没有该猫,no=%d\n", id)}}return head
}
func main() {//初始化一个环形链表的头结点head := &CatNode{}//创建一只猫cat1 := &CatNode{no: 1,name: "tom",}cat2 := &CatNode{no: 2,name: "jack",}cat3 := &CatNode{no: 3,name: "mary",}InsertCatNode(head, cat1)InsertCatNode(head, cat2)InsertCatNode(head, cat3)ListCircleLink(head)head = DelCircleCatNode(head, 2)ListCircleLink(head)
}创建一个链表模拟队列,实现数据入队列,数据出队列,显示队列
package mainimport ("fmt""errors""os"
)//定义一个结构体管理环形队列
type CircleQueue struct {maxSize int //队列最大值:5array [5]int //使用数组 =>队列head int //指向队列队首:0tail int //指向队列队尾:0
}//入队列 AddQueue(push)
func (this *CircleQueue) Push(val int) (err error) {//判断环形队列是否满了if this.IsFull() {return errors.New("queue full")}//this.tail在队列尾部,但是不包含最后一个元素this.array[this.tail] = val //把值给尾部this.tail = (this.tail + 1) % this.maxSizereturn
}//出队列 GetQueue(pop)
func (this *CircleQueue) Pop() (val int, err error) {//判断环形队列是否为空if this.IsEmpty() {return 0, errors.New("queue empty")}//取出:head是指向队首,并且含队首元素val = this.array[this.head]this.head = (this.head + 1) % this.maxSizereturn val, err
}//判断环形队列是否满了
func (this *CircleQueue) IsFull() bool {return (this.tail+1)%this.maxSize == this.head
}//判断环形队列是否为空
func (this *CircleQueue) IsEmpty() bool {return this.tail == this.head
}//取出环形队列有多少个元素
func (this *CircleQueue) Size() int {//这是个关键的点return (this.tail + this.maxSize - this.head) % this.maxSize
}//显示队列
func (this *CircleQueue) ListQueue() {fmt.Println("环形队列情况如下:")//取出当前队列有多少个元素size := this.Size()if size == 0 {fmt.Println("队列为空")}//定义一个临时变量,指向headtempHead := this.headfor i := 0; i < size; i++ {fmt.Printf("array[%d] = %d\n", tempHead, this.array[tempHead])tempHead = (tempHead + 1) % this.maxSize}}
func main() {//先创建一个队列queue := &CircleQueue{maxSize: 5,head: 0,tail: 0,}var key stringvar val intfor {fmt.Println("1. 输入push,表示添加数据到队列")fmt.Println("2. 输入pop,表示从队列获取数据")fmt.Println("3. 输入list,表示显示队列")fmt.Println("4. 输入exit,表示退出队列")fmt.Scanln(&key)switch key {case "push":fmt.Println("输入要入队的对数:")fmt.Scanln(&val)err := queue.Push(val)if err != nil {fmt.Println(err.Error())} else {fmt.Println("加入队列成功")}case "pop":val, err := queue.Pop()if err != nil {fmt.Println(err.Error())} else {fmt.Printf("从队列中取出的数为:%d\n", val)}case "list":queue.ListQueue()case "exit":os.Exit(0)default:fmt.Println("输入有误,请重新输入")}}
}约瑟夫问题
josephu 问题:
设编号为1, 2 ，... n 的n个人围坐一圈, 约定编号为 k (1<=k<=n ）的人从 1 开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列
提示：
用一个不带头结点的循环链表来处理josephu问题,先构成一个有 n 个结点的单循环链表，然后由 k 结点起从1开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除,算法结束
代码如下:
package mainimport ("fmt"
)//定义一个结构体
type Boy struct {no int //编号next *Boy // 指向下一个小孩的指针
}//编写一个函数,构建一个单向环形链表
//num:表示要构建的小孩个数
//*Boy:返回环形链表的第一个小孩的指针
func AddBoy(num int) *Boy {first := &Boy{} // 空指针curBoy := &Boy{} // 空指针: 由逻辑分析得出,要构成一个循环单向链表,需要一个辅助指针//判断num是否符合要求if num < 1 {fmt.Println("num不正确")return first}//循环构建环形链表for i := 1; i <= num; i++ {boy := &Boy{no: i,}//1.第一个小孩比较特殊if i == 1 {first = boycurBoy = boycurBoy.next = first // 形成一个环形链表} else {curBoy.next = boycurBoy = boycurBoy.next = first // 形成一个环形链表}}return first
}//显示单向环形链表
func ShowBoy(first *Boy) {//处理环形链表为空的情况if first.next == nil {fmt.Println("链表为空")return}//创建一个辅助指针,帮助遍历curBoy := firstfor {fmt.Printf("小孩编号:%d\n", curBoy.no)//退出条件: curBoy.next == firstif curBoy.next == first {break}//下一个curBoy = curBoy.next}
}//获取小孩总的个数
func GetNum(first *Boy) (num int) {//处理环形链表为空的情况if first.next == nil {fmt.Println("链表为空")return num}//创建一个辅助指针,帮助遍历curBoy := firstfor {//退出条件: curBoy.next == firstif curBoy.next == first {break}//下一个curBoy = curBoy.nextnum++}return num
}/*
编号为1,2,...,n个小孩围坐在一圈,约定编号为k(1<=k<=n)的人从1开始报数,
数到m的那个人出列,它的下一位又从1开始报数,数到m的那个人又出列,依次类推,
直到所有人出列为止,由此产生一个出队编号的序列
*/
//分析:
//1.编写一个函数PlayGame(first *Boy, startNo int, countNum int)
//2.最后使用一个算法,按照要求,在环形链表中留下最后一个人
func PlayGame(first *Boy, startNo int, countNum int) {//1.空的链表处理if first.next == nil {fmt.Println("空链表")return}//2.判断startNo <= 小孩个数num := GetNum(first)if startNo > num {fmt.Println("开始小孩个数不正确")return}//定义一个辅助指针,帮助删除tail := first//3.让tail指向最后一个小孩,这个tail非常重要,因为在删除小孩的时候需要用到for {if tail.next == first { // 说明tail到了最后一个小孩了break}tail = tail.next}//3.让first移动到startNo(后面删除时,就以first为准)for i := 1; i <= startNo - 1; i++ {first = first.nexttail = tail.next}//5.开始数countNum,然后删除first指向的小孩for {//开始数countNum -1 次for i := 1; i <= countNum - 1; i++ {first = first.nexttail = tail.next}fmt.Printf("小孩编号为%d 出圈 -> \n", first.no)//删除first执行的小孩first = first.nexttail.next = first//判断 如果 tail == first 说明只有一个小孩了if tail == first {break}}fmt.Printf("小孩编号为%d 最后出圈 -> \n", first.no)
}func main() {first := AddBoy(5)ShowBoy(first)PlayGame(first, 2, 3)
}四.栈
1.概念
生活中的栈
存储货物或供旅客住宿的地方,可引申为仓库、中转站 。例如现在生活中的酒店，在古时候叫客栈，是供旅客休息的地方，旅客可以进客栈休息，休息完毕后就离开客栈。
计算机中的栈
生活中的栈的概念引入到计算机中，就是供数据休息的地方，它是一种数据结构，数据既可以进入到栈中，又可以从栈中出去.栈是一种基于先进后出(FILO)的数据结构，是一种只能在一端进行插入和删除操作的特殊线性表
有些程序员也把栈称为堆栈：即栈和堆栈是同一个概念
(1).栈的英文为（ stack)
(2).栈是一个先入后出(FILO-First In Last Out)的有序列表
(3).栈(stack)是限制线性表中元素的插入和删除,只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom).数据进入到栈的动作为压栈，数据从栈中出去的动作为出栈
(4).根据堆栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除
2.栈的应用场景
(1).子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中
(2).处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中
(3).表达式的转换与求值
(4).二叉树的遍历
(5).图形的深度优先(depth-first)搜索法
3.栈的案例
用数组模拟栈的使用，由于堆栈是一种有序列表，当然可以使用数组的结构来储存栈的数据内容，数组模拟栈的出栈，入栈等操作
package mainimport("fmt""errors"
)//使用数组模拟一个栈的作用
type Stack struct {MaxTop int //栈最大可以存放数个数Top int //表示栈顶,因为栈顶固定,因此直接使用Toparr [5]int //数组模拟栈
}func (this *Stack) Push(val int) (err error) {//先判断栈是否满了if this.Top == this.MaxTop - 1 {fmt.Println("栈满了")return errors.New("栈满了")}this.Top++//放入数据this.arr[this.Top] = valreturn
}func (this *Stack) Pop() (val int, err error) {//先判断栈是否为空if this.Top == - 1 {fmt.Println("栈空了")return 0, errors.New("栈空了")}//先取值,再top--val = this.arr[this.Top]this.Top--return val, nil
}//遍历栈,注意需要从栈顶开始遍历
func (this *Stack) List() {//先判断栈是否满了if this.Top == - 1 {fmt.Println("栈空了")return}for i := this.Top; i >= 0; i-- {fmt.Printf("arr[%d] = %d\n", i, this.arr[i])}
}func main() {//初始化一个栈stack := &Stack {MaxTop: 5, //表示最多存放5个数到栈中Top: -1, //当栈顶为-1,表示栈为空}//入栈stack.Push(1)stack.Push(2)stack.Push(3)stack.Push(4)stack.Push(5)//遍历stack.List()//出栈val, _ := stack.Pop()fmt.Printf("出栈:%d\n", val)stack.List()//出栈val, _ = stack.Pop()fmt.Printf("出栈:%d\n", val)stack.List()//出栈val, _ = stack.Pop()fmt.Printf("出栈:%d\n", val)stack.List()//出栈val, _ = stack.Pop()fmt.Printf("出栈:%d\n", val)stack.List()//出栈val, _ = stack.Pop()fmt.Printf("出栈:%d\n", val)stack.List()//出栈val, _ = stack.Pop()if val == 0 {fmt.Println("栈空了")}
}4.栈实现综合计算器
package mainimport("fmt""errors""strconv"
)//使用数组模拟一个栈的作用
type Stack struct {MaxTop int //栈最大可以存放数个数Top int //表示栈顶,因为栈顶固定,因此直接使用Toparr [20]int //数组模拟栈
}func (this *Stack) Push(val int) (err error) {//先判断栈是否满了if this.Top == this.MaxTop - 1 {fmt.Println("栈满了")return errors.New("栈满了")}this.Top++//放入数据this.arr[this.Top] = valreturn
}func (this *Stack) Pop() (val int, err error) {//先判断栈是否为空if this.Top == - 1 {fmt.Println("栈空了")return 0, errors.New("栈空了")}//先取值,再top--val = this.arr[this.Top]this.Top--return val, nil
}//遍历栈,注意需要从栈顶开始遍历
func (this *Stack) List() {//先判断栈是否满了if this.Top == - 1 {fmt.Println("栈空了")return}for i := this.Top; i >= 0; i-- {fmt.Printf("arr[%d] = %d\n", i, this.arr[i])}
}//判断一个字符是不是一个运算符(+,-,*,/),利用ASCII
func (this *Stack) IsOper(val int) bool {if val == 42 || val == 43 || val == 45 || val == 47 {return true} else {return false}
}//运算的方法
func (this *Stack) Cal(num1 int, num2 int, oper int) int {res := 0switch oper {case 42:res = num2 * num1case 43:res = num2 + num1case 45:res = num2 - num1case 47:res = num2 / num1default:fmt.Println("运算符错误")} return res
}//编写方法,返回某个运算符的优先级[程序员规定]
//*,/ ==> 1, +,- ==> 0
func (this *Stack) Priority(oper int) int {res := 0if oper == 42 || oper == 47 {res = 1} else if oper == 43 || oper == 45 {res = 0}return res
}func main() {//初始化栈//数栈numStack := &Stack {MaxTop: 20, //表示最多存放5个数到栈中Top: -1, //当栈顶为-1,表示栈为空}//符号栈operStack := &Stack {MaxTop: 20, //表示最多存放5个数到栈中Top: -1, //当栈顶为-1,表示栈为空}exp := "30+20*6-21"//定义一个index,帮助扫描index := 0//为了配合运算,定义需要的变量num1 := 0num2 := 0oper := 0result := 0keepNum := "" // 处理多位数问题: 目的是用来做拼接的for {ch := exp[index:index+1] // 字符串temp := int([]byte(ch)[0]) // 这个就是字符串对应的ASCII值if operStack.IsOper(temp) { // 说明是符号//如果operStack是一个空栈,直接入栈if operStack.Top == -1 {operStack.Push(temp)} else {//如果发现operStack栈顶的运算符的优先级大于等于当前准备入栈的运算符的优先级,//就从符号栈Pop出,并从数栈也Pop两个数,进行运算,运算后的结果再重新入栈到数栈,//符号再入符号栈if operStack.Priority(operStack.arr[operStack.Top]) >=operStack.Priority(temp) {num1, _ = numStack.Pop()num2, _ = numStack.Pop()oper, _ = operStack.Pop()result = operStack.Cal(num1, num2, oper)//将计算的结果重新入栈numStack.Push(result)//将当前的符号压入符号栈operStack.Push(temp)} else {operStack.Push(temp)}}} else { // 说明是数字//处理多位数问题,思路://1.定义一个变量keepNum string, 做拼接keepNum += ch//2.每次要向index的后面字符测试一下,看看是不是运算符,然后处理//如果已经到表达式的最后了,则直接把keepNum Pushif index == len(exp) - 1 {val, _ := strconv.ParseInt(keepNum, 10, 64)numStack.Push(int(val))} else {// 向index后面测试看看是不是运算符if operStack.IsOper(int([]byte(exp[index + 1: index + 2])[0])) {val, _ := strconv.ParseInt(keepNum, 10, 64)numStack.Push(int(val))keepNum = ""}}}//继续扫描//先判断index是否扫描到计算表达式的最后if index + 1 == len(exp) {break} else {index++}}//如果扫描表达式完毕,依次从符号栈取出符号,然后从数栈取出两个数,//运算后的结果,入数栈,直到符号栈为空for {if operStack.Top == -1 { //退出条件break}num1, _ = numStack.Pop()num2, _ = numStack.Pop()oper, _ = operStack.Pop()result = operStack.Cal(num1, num2, oper)//将计算的结果重新入栈numStack.Push(result)}//如果以上逻辑没有问题,那么结果就是数栈的最后一个数res, _ := numStack.Pop()fmt.Printf("表达式%s = %v\n", exp, res)
}5.栈实现括号匹配问题
给定一个字符串，里边可能包含"()"小括号和其他字符，请编写
程序检查该字符串的中的小括号是否成对出现。
例如：
"(上海)(长安)"：正确匹配
"上海((长安))"：正确匹配
"上海(长安(北京)(深圳)南京)":正确匹配
"上海(长安))"：错误匹配
"((上海)长安"：错误匹配栈来分析解决方案
- 1.创建一个栈用来存储左括号
- 2.从左往右遍历字符串，拿到每一个字符
- 3.判断该字符是不是左括号，如果是，放入栈中存储
- 4.判断该字符是不是右括号，如果不是，继续下一次循环
- 5.如果该字符是右括号，则从栈中弹出一个元素t；
- 6.判断元素t是否为null，如果不是，则证明有对应的左括号，如
- 果不是，则证明没有对应的左括号
- 7.循环结束后，判断栈中还有没有剩余的左括号，如果有，则不
- 匹配，如果没有，则匹配
6.逆波兰表达式求值问题
逆波兰表达式求值问题是计算机中经常遇到的一类问题，要研究明白这个问题，首先得搞清楚什么是逆波兰表达式？要搞清楚逆波兰表达式，得从中缀表达式说起。
中缀表达式
中缀表达式就是平常生活中使用的表达式，例如：1+3*2,2-(1+3)等等，中缀表达式的特点是：二元运算符总是置于两个操作数中间。中缀表达式是人们最喜欢的表达式方式，因为简单，易懂。但是对于计算机来说就不是这样了，因为中缀表达式的运算顺序不具有规律性。不同的运算符具有不同的优先级，如果计算机执行中缀表达式，需要解析表达式语义，做大量的优先级相关操作。
逆波兰表达式(后缀表达式)
逆波兰表达式是波兰逻辑学家J・卢卡西维兹(J・ Lukasewicz)于1929年首先提出的一种表达式的表示方法，后缀表达式的特点：运算符总是放在跟它相关的操作数之后。
需求：
给定一个只包含加减乘除四种运算的逆波兰表达式的数组表示方式，求出该逆波兰表达式的结果。
package mainimport ("fmt""strconv"
)// evalRPN 函数用于计算逆波兰表达式的结果
func evalRPN(tokens []string) float64 {stack := []float64{}for _, token := range tokens {switch token {case "+":// 弹出栈顶的两个元素进行加法运算b := stack[len(stack)-1]stack = stack[:len(stack)-1]a := stack[len(stack)-1]stack = stack[:len(stack)-1]stack = append(stack, a+b)case "-":// 弹出栈顶的两个元素进行减法运算b := stack[len(stack)-1]stack = stack[:len(stack)-1]a := stack[len(stack)-1]stack = stack[:len(stack)-1]stack = append(stack, a-b)case "*":// 弹出栈顶的两个元素进行乘法运算b := stack[len(stack)-1]stack = stack[:len(stack)-1]a := stack[len(stack)-1]stack = stack[:len(stack)-1]stack = append(stack, a*b)case "/":// 弹出栈顶的两个元素进行除法运算b := stack[len(stack)-1]stack = stack[:len(stack)-1]a := stack[len(stack)-1]stack = stack[:len(stack)-1]stack = append(stack, a/b)default:// 将数字转换为浮点数并压入栈中num, err := strconv.ParseFloat(token, 64)if err != nil {panic(err) // 处理转换错误}stack = append(stack, num)}}// 最终栈中只会剩下一个元素，即为结果return stack[0]
}func main() {tokens := []string{"2", "1", "+", "3", "*"} // 示例逆波兰表达式result := evalRPN(tokens)fmt.Printf("Result: %v\n", result) // 输出结果
}
代码说明
- 栈的使用：我们使用一个
stack来存储操作数。遇到操作符时，弹出栈顶的两个元素进行计算，然后将结果压入栈中。- 运算符处理：根据不同的运算符（
+,-,*,/），执行相应的操作。- 数字处理：对于数字，我们使用
strconv.ParseFloat将字符串转换为浮点数并压入栈中。- 结果输出：最终，栈中只会剩下一个元素，即为计算结果。
使用示例
在
main函数中，定义了一个逆波兰表达式{"2", "1", "+", "3", "*"}，该表达式表示的是(2 + 1) * 3，运行程序后将输出结果9.
五.队列
1.概念
队列是一种基于先进先出(FIFO)的数据结构，是一种只能在一端进行插入,在另一端进行删除操作的特殊线性表，它按照先进先出的原则存储数据，先进入的数据，在读取数据时先读被读出来,可以用数组或是链表来实现.
2.数组模拟队列
队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下:其中 maxSize 是该队列的最大容量
因为队列的输出、输入是分别从前后端来处理，因此需要两个变量front及rear分别记录队列前后端的下标， front 会随着数据输出而改变，而rear则是随着数据输入而改变,如图所示：
将数据存入队列时称为"addqueue", addqueue 的处理需要有两个步骤
(1).将尾指针往后移： rear + 1 , front ==real ［空］
(2).若尾指引 rear 小于等于队列的最大下标 MaxSize -1, 则将数据存入 rear 所指的数组元素,否则无法存入数据
package mainimport ("fmt""errors""os"
)//定义一个结构体,存放队列相关数据
type Queue struct {maxSize int //队列最大数array [5]int // 数组=>模拟队列front int //指向队列首部 rear int //指向队列尾部
}//添加队列数据
func (this *Queue) AddQueue(val int) (err error) {//判断队列是否已满if this.maxSize -1 == this.rear { // rear是队列尾部(含最后一个元素)return errors.New("queue full")} this.rear++ //rear后移this.array[this.rear] = valreturn
}//显示队列:找到队首,然后遍历
func (this *Queue) ShowQueue () {fmt.Println("队列当前情况:")//this.front是不包含队首的元素for i := this.front + 1; i <= this.rear; i++ {fmt.Printf("arrar[%d]=%d\n", i, this.array[i])}
}//从队列中取出数据
func (this *Queue) GetQueue() (val int, err error) {//先判断队列是否为空if this.rear == this.front { //队列为空了return -1, errors.New("queue empty")}this.front++val = this.array[this.front]return val, err
}func main() {//先创建一个队列queue := &Queue {maxSize: 5,front: -1,rear: -1,}var key stringvar val intfor {fmt.Println("1. 输入add,表示添加数据到队列")fmt.Println("2. 输入get,表示从队列获取数据")fmt.Println("3. 输入show,表示显示队列")fmt.Println("4. 输入exit,表示退出队列")fmt.Scanln(&key)switch key {case "add":fmt.Println("输入要入队的对数:")fmt.Scanln(&val)err := queue.AddQueue(val)if err != nil {fmt.Println(err.Error())} else {fmt.Println("加入队列成功")}case "get":val, err := queue.GetQueue()if err != nil {fmt.Println(err.Error())} else {fmt.Printf("从队列中取出的数为:%d\n", val)}case "show":queue.ShowQueue()case "exit":os.Exit(0)default:fmt.Println("输入有误,请重新输入")}}
}对上面代码的小节和说明:
(1).上面代码实现了基本队列结构，但是役有有效的利用数组空间
(2).请思考:如何使用数组实现一个环形的队列
3.环形数组队列
对前面的数组模拟队列的优化，充分利用数组,因此将数组看做是一个环形的( 通过取模的方式来实现即可）
提醒：
(1).尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定,这个在做判断队列满的时候需要注意(tail+1)%maxSize == head(满)
(2).tail == head (空)
分析思路:
(1).什么时候表示队列满? (tail+1)%maxSize == head
(2).什么时候表示队列空? tail == head
(3).初始化时,tail == 0,head == 0
(4).怎么统计该队列有多少个元素? (tail + maxSize - head) % maxSize
package mainimport("fmt""errors""os"
)//定义一个结构体管理环形队列
type CircleQueue struct{ maxSize int //队列最大值:5array [5]int //使用数组 =>队列head int //指向队列队首:0tail int //指向队列队尾:0
}//入队列 AddQueue(push)
func (this *CircleQueue) Push(val int) (err error) {//判断环形队列是否满了if this.IsFull() {return errors.New("queue full")}//this.tail在队列尾部,但是不包含最后一个元素this.array[this.tail] = val //把值给尾部this.tail = (this.tail + 1) % this.maxSizereturn
}//出队列 GetQueue(pop)
func (this *CircleQueue) Pop() (val int, err error) {//判断环形队列是否为空if this.IsEmpty() {return 0, errors.New("queue empty")}//取出:head是指向队首,并且含队首元素val = this.array[this.head]this.head = (this.head + 1) % this.maxSizereturn val, err
}//判断环形队列是否满了
func (this *CircleQueue) IsFull() bool {return (this.tail + 1) % this.maxSize == this.head
}//判断环形队列是否为空
func (this *CircleQueue) IsEmpty() bool {return this.tail == this.head
}//取出环形队列有多少个元素
func (this *CircleQueue) Size() int {//这是个关键的点return (this.tail + this.maxSize - this.head) % this.maxSize
}//显示队列
func (this *CircleQueue) ListQueue() {fmt.Println("环形队列情况如下:")//取出当前队列有多少个元素size := this.Size()if size == 0 {fmt.Println("队列为空")}//定义一个临时变量,指向headtempHead := this.headfor i := 0; i < size; i++ {fmt.Printf("array[%d] = %d\n", tempHead, this.array[tempHead])tempHead = (tempHead + 1) % this.maxSize}}
func main() {//先创建一个队列queue := &CircleQueue {maxSize: 5,head: 0,tail: 0,}var key stringvar val intfor {fmt.Println("1. 输入push,表示添加数据到队列")fmt.Println("2. 输入pop,表示从队列获取数据")fmt.Println("3. 输入list,表示显示队列")fmt.Println("4. 输入exit,表示退出队列")fmt.Scanln(&key)switch key {case "push":fmt.Println("输入要入队的对数:")fmt.Scanln(&val)err := queue.Push(val)if err != nil {fmt.Println(err.Error())} else {fmt.Println("加入队列成功")}case "pop":val, err := queue.Pop()if err != nil {fmt.Println(err.Error())} else {fmt.Printf("从队列中取出的数为:%d\n", val)}case "list":queue.ListQueue()case "exit":os.Exit(0)default:fmt.Println("输入有误,请重新输入")}}
}4.优先队列
普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在某些情况下，可能需要找出队列中的最大值或者最小值，例如使用一个队列保存计算机的任务，一般情况下计算机的任务都是有优先级的，需要在这些计算机的任务中找出优先级最高的任务先执行，执行完毕后就需要把这个任务从队列中移除。普通的队列要完成这样的功能，需要每次遍历队列中的所有元素，比较并找出最大值，效率不是很高，这个时候，就可以使用一种特殊的队列来完成这种需求，优先队列
好了,线性表相关数据结构就基本上差不多了, 从上面可知,线性表分为顺序表,链表(单向,双向),栈,队列等,他们存储的是单值情况,那么如果要存储多值情况,如:key-value情况,怎么办呢,这里就需要使用符号表了