链表
单向链表
定义一个HeroNode
// 定义一个HeroNode
type HeroNode1 struct{
no int
name string
nickname string
next *HeroNode
}
给链表添加一个节点
- 方式一：直接在链表最后加入
func InsertHeroNode1(head, newHeroNode *HeroNode){
// 1.先找到该链表的最后节点
// 2.创建一个辅助节点
temp := head
for {
if temp.next == nil {
// 表示已经找到最后
break
}
temp = temp.next // 让temp不断指向下一个节点
}
// 3.将newHeroNode 加入到链表的最后
temp.next = newHeroNode
}
- 方式二：根据no的编号从小到大插入
func InsertHeroNode2(head, newHeroNode *HeroNode){
// 1.找到适当的节点
// 2.创建辅助节点
temp := head
// 让插入的节点no，和temp的下一个节点的no比较
for{
if temp.next == nil {
// 说明到链表的最后
break
}else if temp.next.no >= newHeroNode.no{
// 说明newHeroNode 就应该插入到temp后面
break
}
temp = temp.next
}
newHeroNode.next = temp.next
temp.next = newHeroNode
}
显示链表所有节点
func ListHeroNode1(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.next
if temp.next == nil {
break
}
}
}
删除一个节点
// 删除一个节点
func DelHeroNode1(head *HeroNode, id int){
temp := head
for{
if temp.next == nil {
// 说明已经到链表的最后了
break
}else if temp.next.no == id {
// 说明找到了需要删除的节点
temp.next = temp.next.next
return
}
temp = temp.next
}
}
双向链表
定义一个HeroNode
type HeroNode struct{
no int
name string
nickname string
pre *HeroNode // 这个表示指向前一个节点
next *HeroNode // 这个表示指向下一个节点
}
给链表添加一个节点
- 方式一: 在双向链表最后加入
// 方式一：在双链表最后加入
func InsertHeroNode(head,newHeroNode *HeroNode){
// 先找到该链表的最后节点
// 创建一个辅助节点
temp := head
for {
if temp.next == nil {
// 表示找到最后
break
}
temp = temp.next // 让temp不断的指向下一个节点
}
// 将newHeroNode加入到链表的最后
temp.next = newHeroNode
newHeroNode.pre = temp
}
- 方式二: 在双向链表指定位置加入
func InsertHeroNode2(head, newHeroNode *HeroNode){
temp := head
for{
// 判断链表是否已经到最后了
if temp.next == nil {
break
}else if temp.next.no >= newHeroNode.no{
// 说明就应该插入到temp后面
break
}
temp = temp.next
}
newHeroNode.next = temp.next // 找到自己后面的，正向连接
newHeroNode.pre = temp // 找到自己前面的,反向连接
if temp.next != nil {
temp.next.pre = newHeroNode // 自己后面的节点与自己反向连接
}
temp.next = newHeroNode // 自己前面的和自己正向连接
}
显示双向链表
- 正序显示
// 显示链表所有的节点信息
func ListHeroNode11(head *HeroNode){
temp := head
if temp.next == nil {
fmt.Println("空空如也")
return
}
// 遍历整个链表
for {
fmt.Printf("[%d,%s,%s]==>",temp.next.no,temp.next.name,temp.next.nickname)
temp = temp.next
if temp.next == nil {
// 表明已经到链表结尾了
return
}
}
}
- 倒序显示
// 倒序显示双向链表所有信息
func ListHeroNode22(head *HeroNode){
temp := head
// 先判断该链表是不是一个空链表
if temp.next == nil {
fmt.Println("空空如也。。。")
return
}
// 让temp定位到双向链表的最后节点
for {
if temp.next == nil {
break
}
temp = temp.next
}
// 遍历这个链表
for {
fmt.Printf("[%d,%s,%s]==>",temp.no,temp.name,temp.nickname)
// 判断是否链表表头
temp = temp.pre
if temp.pre == nil {
break
}
}
}
删除指定节点
// 删除指定节点
func DelHeroNode(head *HeroNode, id int){
temp := head
for{
if temp.next == nil {
// 说明到链表最后了
return
}else if temp.next.no == id {
temp.next = temp.next.next
if temp.next != nil {
temp.next.pre = temp
}
}
temp = temp.next
}
}
环形单向链表
定义HeroNode
type HeroNode struct{
no int
name string
nickname string
next *HeroNode
}
插入一个节点
func InsertHeroNode(head, newHeroNode *HeroNode){
// 判断是不是添加第一个英雄
if head.next == nil {
head.no = newHeroNode.no
head.name = newHeroNode.name
head.nickname = newHeroNode.nickname
head.next = head // 构成一个环路
return
}
// 定义一个临时变量，帮忙找到环形的最后节点
temp := head
for {
if temp.next == head {
break
}
temp = temp.next
}
// 加入环形链表中
temp.next = newHeroNode
newHeroNode.next = head
}
显示环形链表
func ListCircleLink(head *HeroNode){
// 定义临时变量
temp := head
if temp.next == nil {
fmt.Println("空空如也的环形链表")
return
}
for{
fmt.Printf("[%d,%s,%s]",temp.no,temp.name,temp.nickname)
if temp.next == head {
break
}
temp = temp.next
}
}
删除一个节点
func DelHeroNode(head *HeroNode, id int)*HeroNode{
temp := head
helper := head
// 空链表
if temp.next == nil {
fmt.Println("这是一个空的环形链表")
return head
}
// 如果只有一个节点
if temp.next == head {
// 只有一个节点
if temp.no == id{
temp.next = nil
}
return head
}
// 将helper定位到链表最后
for {
if helper.next == head {
break
}
helper = helper.next
}
flag := true
for {
if temp.next == head {
// 如果到这里，说明比较到了最后一个节点[不包含最后一个]
break
}
if temp.no == id {
if temp == head {
// 说明删除的节点是头节点
head = head.next
}
helper.next = temp.next
flag = false
break
}
temp = temp.next
helper = helper.next
}
if flag{
if temp.no == id{
helper.next = temp.next
}
}
return head
}
环形单向链表应用实例
- Josephu问题
Josephu问题为：设编号为1,2，... n的n个人围坐一圈，约定编号为k(1<=k<=n)的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m那个人又出列，依次类推，直到所有人都出列为止，由此产生一个出队编号的序列。
提示
用一个不带头节点的循环链表来处理Josephu问题：先构成一个有n个节点的单循环链表，然后由k节点起从1开始计数，计到m时，对应节点从链表中删除，然后再从被删除节点的下一个节点又从1开始计数，直到最后一个节点从链表删除，算法结束。
type Boy struct{
No int // 编号
Next *Boy // 指向下一个小孩的指针【默认值是nil】
}
// 编写一个函数，构成单向环形链表
// num:表示小孩的个数
// *Boy:返回该环形链表的第一个小孩的指针
func AddBoy(num int)*Boy{
first := &Boy{} // 空节点
temp := &Boy{} // 空节点
if num < 1{
fmt.Println("num的值不对")
return first
}
// 循环构建这个环形链表
for i := 1;i <= num ; i ++ {
boy := &Boy{
No: i,
}
// 分析构成循环链表，需要一个辅助指针
// 因为第一个小孩比较特殊
if i == 1{
first = boy // 不要动
temp = boy
temp.Next = first
} else {
temp.Next = boy
temp = boy
temp.Next = first // 构成环形链表
}
}
return first
}
// 显示单向环形链表
func ShowBoy(first *Boy){
// 判断环形链表是否为空
if first.Next == nil {
fmt.Println("链表为空,没有小孩。。。")
return
}
// 创建一个指针，帮助遍历
temp := first
for {
fmt.Printf("小孩编号=%d->",temp.No)
if temp.Next == first{
break
}
temp = temp.Next
}
}
func PlayGame(first *Boy, startNo int, countNum int){
// 判断是否为空
if first.Next == nil {
fmt.Println("空空如也")
return
}
// 需要定义辅助指针，来帮助我们删除小孩
temp := first
// 让temp找到最后一个小孩，在删小孩时候需要使用到
for{
if temp.Next == first{
// 说明已经到了最后一个小孩
break
}
temp = temp.Next
}
// 让first移动到startNo
for i := 0; i <= startNo; i ++{
first = first.Next
temp = temp.Next
}
for{
// 开始数countNum,然后删除first指向的小孩
for i := 1; i <= countNum - 1; i ++ {
first = first.Next
temp = temp.Next
}
fmt.Printf("小孩编号为%d出圈
",first.No)
// 删除
first = first.Next
temp.Next = first
// 判断如果temp == first,则只剩下一个小孩
if temp == first{
break
}
}
fmt.Printf("最后一个小孩编号为%d
",first.No)
}
func main() {
first := AddBoy(500)
ShowBoy(first)
PlayGame(first,20,31)
}