Go语言链表操作
有时可以让 Struct 的一个指针成员指向它自己,利用这种特性 Struct 对象可以作为链表或者二叉树的元素,通常叫做节点(Node)。
链表则没有这种缺点,它会根据需要动态开辟内存单元,不会造成内存的浪费。另外,链表还可以动态增添新节点、删除旧节点。下图所表示的是一种最简单的单向链表的结构。
图:单向链表
单向链表中有一个头指针变量,图中以 Head 表示,头指针存放链表第一个元素的地址。链表中每一个元素称为“节点”,每个节点都应包括两个部分:用户数据和下一个节点的地址。
从上图可以看出,Head 指向第一个元素,第一个元素又指向第二个元素……直到最后一个元素 Tail。Tail 不再指向其他元素,它称为“表尾”,它的地址部分是“nil”,表示没有,链表到此结束。
可以看出,链表各元素在内存中可以不连续存放。在链表中要找到一个元素,必须先找到上一个元素,根据它提供的 Next 地址才能找到要找的目标。如果不提供“头指针”Head,则整个链表都无法访问。另外,链表节点之间必须一环扣一环,中间不能断开。否则,链表将丢失节点、不完善。
通过上面的介绍可以看到,链表这种数据结构,必须利用指针变量才能实现,即一个节点中应包含一个指针变量,用它存放下一个节点的地址。
例如,可以定义这样一个结构体类型:
对于一个链表,链表头部 Head 最重要。所以要建立一个链表,首先要声明一个指向 Node 的指针类型的 Head,然后再让 Head 的 Next 指向链表的第一个节点,如果还有第二个节点,第一个节点的 Next 再指向第二个节点……直到最后一个节点,让它的 Next 为 nil,即链表到此结束。使用这种方法,就可以建立如上面图中所示的单向链表。
下面是一个链表综合操作的例子,该例中使用链表动态存储学生基本信息。学生基本信息使用结构体 Student 来记录,共有两个字段:学号(Id)和姓名(Name)。链表节点 Node 也包含两个字段:匿名字段(Student)和 Next 指针。
该例不但要使用 Node 节点建立一个能管理学生信息的单向链表,还要使用 Go语言面向对象程序设计思想,在 Node 对象上实现 4 个操作方法,以方便对链表的管理和维护。
在设计过程中,Student 和 Node 的定义,以及 4 个方法的实现在 link 包中完成,最后程序总体功能的验证和测试在 main 包中完成。由于篇幅所限,4 个操作方法的相关算法实现本教程就不再赘述,有兴趣的读者可以参阅数据结构方面的教程。
Link 包中的代码如下:
链表简介
链表是一种常见的重要数据结构,它的主要特点是能动态地进行存储分配。我们在使用数组存放数据时,必须事先分配固定长度的存储空间(即元素个数)。比如,有的班级有 60 名学生,而有的班级只有 30 名学生,如果要用同一个数组先后存放不同班级的学生信息,则数组长度至少为60。如果班级人数难以确定,则必须把数组定义得足够大,显然这将会浪费内存。链表则没有这种缺点,它会根据需要动态开辟内存单元,不会造成内存的浪费。另外,链表还可以动态增添新节点、删除旧节点。下图所表示的是一种最简单的单向链表的结构。
图:单向链表
单向链表中有一个头指针变量,图中以 Head 表示,头指针存放链表第一个元素的地址。链表中每一个元素称为“节点”,每个节点都应包括两个部分:用户数据和下一个节点的地址。
从上图可以看出,Head 指向第一个元素,第一个元素又指向第二个元素……直到最后一个元素 Tail。Tail 不再指向其他元素,它称为“表尾”,它的地址部分是“nil”,表示没有,链表到此结束。
可以看出,链表各元素在内存中可以不连续存放。在链表中要找到一个元素,必须先找到上一个元素,根据它提供的 Next 地址才能找到要找的目标。如果不提供“头指针”Head,则整个链表都无法访问。另外,链表节点之间必须一环扣一环,中间不能断开。否则,链表将丢失节点、不完善。
通过上面的介绍可以看到,链表这种数据结构,必须利用指针变量才能实现,即一个节点中应包含一个指针变量,用它存放下一个节点的地址。
Struct 和 Method 设计单链表
利用 Struct 可以包容多种数据类型的特性,使用它作为链表的节点是最合适不过了。一个结构体内可以包含若干成员,这些成员可以是基本类型、自定义类型、数组类型,也可以是指针类型。这里可以使用指针类型成员来存放下一个节点的地址。例如,可以定义这样一个结构体类型:
type Node struct {
Data int
Next * Node
}
对于一个链表,链表头部 Head 最重要。所以要建立一个链表,首先要声明一个指向 Node 的指针类型的 Head,然后再让 Head 的 Next 指向链表的第一个节点,如果还有第二个节点,第一个节点的 Next 再指向第二个节点……直到最后一个节点,让它的 Next 为 nil,即链表到此结束。使用这种方法,就可以建立如上面图中所示的单向链表。
下面是一个链表综合操作的例子,该例中使用链表动态存储学生基本信息。学生基本信息使用结构体 Student 来记录,共有两个字段:学号(Id)和姓名(Name)。链表节点 Node 也包含两个字段:匿名字段(Student)和 Next 指针。
该例不但要使用 Node 节点建立一个能管理学生信息的单向链表,还要使用 Go语言面向对象程序设计思想,在 Node 对象上实现 4 个操作方法,以方便对链表的管理和维护。
- Creat() 方法创建一个新链表,并返回 head 指针。
- PrintLink() 用于链表的输出打印。
- Insert() 方法可以将新节点插入链表,并返回 head 指针。
- Delete() 方法会将节点从链表删除,并返回 head 指针。
在设计过程中,Student 和 Node 的定义,以及 4 个方法的实现在 link 包中完成,最后程序总体功能的验证和测试在 main 包中完成。由于篇幅所限,4 个操作方法的相关算法实现本教程就不再赘述,有兴趣的读者可以参阅数据结构方面的教程。
Link 包中的代码如下:
package link import ( "fmt" ) type Student struct { Id int Name string } type Node struct { Student Next *Node } func (head *Node) Creat() *Node { head = nil return head } func (p *Node) PrintLink() { for p != nil { fmt.Printf("%d, %s\n", p.Id, p.Name) p = p.Next } } func (newNode *Node) Insert(head *Node) *Node { var p0, p1, p2 *Node p0 = newNode p1 = head if head == nil { head = p0 p0.Next = nil } else { for (p0.Id > p1.Id) && p1.Next != nil { p2 = p1 p1 = p1.Next } if p0.Id <= p1.Id { if head == p1{ head = p0 } else { p2.Next = p0 p0.Next = p1 } } else { p1.Next = p0 p0.Next = nil } } return head } func (delNode *Node) Delete(head *Node) *Node { var p1, p2 *Node if head == nil { fmt.Println("List nil!") goto End } p1 = head for delNode.Id != p1.Student.Id && p1.Next != nil { p2 = p1 p1 = p1.Next } if delNode.Id == p1.Student.Id { if p1 == head { head = p1.Next } else { p2.Next = p1.Next } fmt.Printf("Delete %d\n", delNode.Id) } else { fmt.Printf("Node %d not been found!\n", delNode.Id) } End: return head }【示例】链表综合操作。
// 链表综合操作 package main import ( "link" ) func main() { var head *link.Node stu1 := link.Node{link.Student{100, "李明"}, nil} stu2 := link.Node{link.Student{101, "张晓"}, nil} stu3 := link.Node{link.Student{102, "赵琼"}, nil} stu4 := link.Node{link.Student{103, "王乐"}, nil} //创建新链表 head = head.Creat() //插入节点 head = stu1.Insert(head) head = stu2.Insert(head) head = stu3.Insert(head) head = stu4.Insert(head) //输出链表 head.PrintLink() //删除节点 head = stu3.Delete(head) head.PrintLink() }编译并运行该程序,输出结果为:
100, 李明
101, 张晓
102, 赵琼
103, 王乐
Delete 102
100, 李明
101, 张晓
103, 王乐
所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频