golang中线性表的实现
- 线性表的类型定义
- 线性表的顺序表示和实现
- 线性表的链式表示和实现
(一) 线性表的类型定义
线性表是一个具有n个数据元素的有序序列。线性表的数据元素可以是不同类型的，但同一线性表中的数据元素必定具有相同的特征，如int，string，float，bool，结构体等。如下图所示：
| a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 | a9 |
|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
- a1为a2的直接前驱元素，a3为a2的直接后继元素。
- 当元素个数为0时，线性表为空表。
- 基础操作为线性表的增删改查。平均时间复杂度为O(n)
(二)线性表的顺序表示和实现
- 顺序表定义：用一组地址连续的存储单元依次存储线性表的数据元素。
- 设l为存储单元的存储空间大小，则第i个元素存储位置: Local(a1) +(i-1)×l ,如下图：
| 地址 | 数据 | 位序 |
|---|---|---|
| b | a1 | 1 |
| b+l | a2 | 2 |
| b+(3-1)l | a3 | 3 |
| b+(4-1)l | a4 | 4 |
| b+(5-1)l | a5 | 5 |
基本操作
1.增加元素
2.删除元素
3.查找元素
4.代码演示：
package main
import (
"errors"
"fmt"
)
const MaxSize int = 10
type SeqListClass struct {
data []int
length int
}
// 分配空间
func NewList() *SeqListClass {
if MaxSize == 0 {
return nil
}
return &SeqListClass{
data: make([]int, MaxSize, MaxSize),
length: 0,
}
}
//为顺序表填值
func (this *SeqListClass) creatList(data []int, n int) (err error) {
for i := 0; i < n; i++ {
this.data[i] = data[i]
}
this.length = n
fmt.Println(this.data)
return nil
}
//输出顺序表
func (this *SeqListClass) dispList() (err error) {
if this.length == 0 {
fmt.Println("顺序表为0！")
}
for i := 0; i < this.length; i++ {
fmt.Printf("%d\t", this.data[i])
}
return nil
}
//表长
func (this *SeqListClass) listLength() int {
return this.length
}
//根据index查找
func (this *SeqListClass) getEleme(i int) (int, error) {
if i < 0 || i > this.length {
return -1, errors.New("out of range!")
}
return this.data[i-1], nil
}
//依据输入元素查找index
func (this *SeqListClass) LocateElem(value int) (int, error) {
var i int
for i = 0; i < this.length; i++ {
if value == this.data[i] {
break
}
}
if i >= this.length {
return -1, errors.New("out of range")
}
return i + 1, nil
}
//增
func (this *SeqListClass) ListInsert(i, value int) error {
if i < 0 || i >= this.length {
return errors.New("out of range")
}
for j := this.length; j >= i; j-- {
this.data[j] = this.data[j-1]
}
this.data[i] = value
this.length++
return nil
}
// 删
func (this *SeqListClass) ListDelete(i int) error {
if i < 0 || i >= this.length {
return errors.New("out of range")
}
for j := i; j < this.length; j++ {
this.data[j] = this.data[j+1]
}
this.length--
return nil
}
// 反转列表
func (this *SeqListClass) Reserve() {
for i := 0; i < this.length/2; i++ {
tmp := this.data[i]
this.data[i] = this.data[this.length-i-1]
this.data[this.length-i-1] = tmp
}
}
func main() {
//先新建一个表
lst := NewList()
// 创建一个data切片
data := []int{12, 2, 13, 4, 23, 10, 5, 8}
//为顺序表填值
lst.creatList(data, 8)
lst.dispList()
n := lst.listLength()
fmt.Println("表长为", n)
n, _ = lst.getEleme(5)
fmt.Println("查找到元素为", n)
n, _ = lst.LocateElem(5)
fmt.Println("查找到的位置为", n)
lst.ListInsert(4, 5)
fmt.Println("插入新元素后的列表为：", lst.data)
lst.ListDelete(5)
fmt.Println("删除元素后的列表为：", lst.data)
lst.Reserve()
fmt.Println("列表反转后为：", lst.data)
}
执行结果为：
(三)线性表的链式表示和实现
- 单链表
- 双链表
- 循环单链表
- 循环双链表
单链表
1.线性链表的定义：用一组任意的储存单元储存线性表的数据元素(可以时连续的，也可以时非连续的)，对于每个单元来说，除了存储数据本身信息，还要储存一个指示后继者的信息(后继者的存储位置)，即数据域和指针域。如图：
2.单链表分为有头节点和无头结点的单链表。在单链表第一个节点的附件设立一个节点，无数据域，但指针域存第一个节点的地址,这个节点称为单链表的头节点。
3.单链表的查找。不同于顺序表，相邻节点在物理位置上紧邻，每个节点的位置都可以由头节点计算所得，而单链表中，节点与下一个节点的联系仅为指针域，因此必须从头节点开始出发寻找，因此单链表为非随机存储结构。
基本操作
1.增加元素
假设在 a和b节点中插入一个p元素，则需要使a节点的指针域指向p节点，p节点的指针域指向b节点。如图：
2.删除元素：
假设要删除a和c节点中的b元素，则需要使a节点的指针域更改指向为c节点。如图：
3.查找元素
从头节点开始循环，一直循环到下一个节点的指针域指向nil。
代码演示：
package main
import (
"fmt"
)
type Object interface{}
type Node struct {
Data Object //定义数据域
Next *Node //定义地址域(指向下一个表的地址)
}
type List struct {
headNode *Node //头节点
}
//判断是否为空表 ,只需要判断头节点即可
func (this *List) isEmpty() bool {
if this.headNode == nil {
return true
} else {
return false
}
}
//判断表长
func (this *List) Length() int {
//获取链表头结点
cur := this.headNode
//定义一个计数器，初始值为0
count := 0
for cur != nil {
//如果头节点不为空，则count++
count++
//对地址进行逐个位移
cur = cur.Next
}
return count
}
//从链表头部添加元素
func (this *List) Add(data Object) *Node {
node := &Node{Data: data}
node.Next = (*this).headNode
(*this).headNode = node
return node
}
//从链表尾部添加元素
func (this *List) Append(data Object) {
//创建新元素，通过data赋值
node := &Node{Data: data}
if this.isEmpty() {
this.headNode = node
} else {
cur := this.headNode //获得表头
for cur.Next != nil {
cur = cur.Next //链表位移
}
cur.Next = node
}
}
//在链表指定位置后添加元素
func (this *List) Insert(index int, data Object) {
if index < 0 {
this.Add(data)
} else if index > this.Length() {
this.Append(data)
} else {
count := 0
pre := this.headNode
for count < (index - 1) {
pre = pre.Next
count++
}
node := &Node{Data: data}
node.Next = pre.Next //新链表元素的地址指向上一个链表的储存地址
pre.Next = node //上一个链表的储存地址指向新元素地址
}
}
// 删除链表指定值的元素
func (this *List) Remove(data Object) {
pre := this.headNode
if pre.Data == data {
this.headNode = pre.Next
} else {
for pre.Next != nil {
if pre.Next.Data == data {
//pre.next的数据等于data,这pre.next 指向pre.next.next
pre.Next = pre.Next.Next
} else {
// 否则,继续移动 pre = pre.nxt
pre = pre.Next //继续
}
}
}
}
// 删除指定位置的元素
func (this *List) RemoveIndex(index int) {
pre := this.headNode
if index <= 0 {
//位于表头
this.headNode = pre.Next
} else if index > this.Length() {
//超出链表
fmt.Println("out of index!")
} else {
count := 0
for count < index-1 && pre.Next == nil {
pre = pre.Next // 开始遍历，如果为达到index继续，达到则跳出循环 pre.next == nil
count++
}
pre.Next = pre.Next.Next
}
}
func (this *List) Contain(data Object) bool {
cur := this.headNode
for cur.Next != nil {
if cur.Data == data {
return true
}
cur = cur.Next
}
return false
}
//遍历所有节点
func (this *List) ShowList() {
if this.isEmpty() == true {
fmt.Println("遍历链表为空！")
} else {
cur := this.headNode
fmt.Printf("当前元素为：%d\t",cur)
for cur.Next != nil {
cur = cur.Next
fmt.Printf("当前元素为：%d\t", cur.Data)
}
}
}
func main() {
//先初始化一个链表
lst := List{}
//追加元素
for i := 0; i < 10; i++ {
lst.Append(i)
}
//从头部添加
new := lst.Add("newNode")
fmt.Println(new.Data)
//指定位置插入元素
lst.Insert(4, 33)
//删除元素
lst.Remove(5)
//删除指定位置元素
lst.RemoveIndex(7)
//是否包含指定元素
n := lst.Contain(9)
fmt.Println("列表包含9：", n)
//显示链表元素
lst.ShowList()
//判断表是否为空
t := lst.isEmpty()
fmt.Println("目前表为空:", t)
//判断表长
length := lst.Length()
fmt.Println("表长：", length)
}
运行结果：
双链表
1.与单链表类似，有数据域和指针域，但指针域有两部分，前指针域和后指针域。如下图：
2.设在双链表中节点b和c中增加节点p，应当让节点b的后指针指向p，节点c的前指针指向p，p的前指针指向b，后指针指向c。如下图：
基本操作
package main
import (
"fmt"
)
type object interface{}
type node struct {
data object //数据域
pre *node //前指针
next *node //后指针
}
type DelinkList struct {
head *node //头节点
}
//判断为空
func (this *DelinkList) isEmpty() bool {
if this.head == nil {
return true
}
return false
}
//判断表长
func (this *DelinkList) length() int {
count := 0
head := this.head
for head != nil {
count++
head = head.next
}
return count
}
//头部插入
func (this *DelinkList) addData(value object) {
newNode := &node{data: value}
if this.head == nil {
this.head = newNode
} else {
newNode.next = this.head //新增后指针指向原头节点
this.head.pre = newNode //原头指针前指针指向新增节点
this.head = newNode //原头指针变为新增指针
}
}
//尾部插入
func (this *DelinkList) appendData(value object) {
newNode := &node{data: value}
if this.isEmpty() {
this.head = newNode
} else {
head := this.head
for head.next != nil {
head = head.next
}
newNode.pre = head
head.next = newNode
}
}
// 删除任意位置的元素, todo 需要处理: 删除的元素在头部, 中部,尾部三种情况
func (this *DelinkList) deletData(value object) {
head := this.head
//删除头部
if head.data == value {
head = head.next
}
for head != nil {
if head.data == value {
//修改元素前的前一个尾指针指向后一个元素
head.pre.next = head.next //
if head.next != nil {
head.next.pre = head.pre //尾巴元素的前指针指向倒是第三个元素
}
break
} else {
head = head.next //继续扫描
}
}
}
//在任意位置插入数据，todo 需要处理: 删除的元素在头部, 中部,尾部三种情况
func (this *DelinkList) insertData(index, value int) {
if index <= 0 {
this.addData(value)
} else if index > this.length() {
this.appendData(value)
} else {
count := 0
cur := this.head
// 插入的数据位于链表中间
for count < index {
count++
cur = cur.next
}
newNode := &node{data: value}
newNode.pre = cur.pre // 新前为head前
newNode.next = cur //新后为head
cur.pre.next = newNode //head前后为xin
cur.pre = newNode //head前为新
}
}
//显示所有元素
func (this *DelinkList) showList() {
if this.isEmpty() {
fmt.Println("链表为空！")
} else {
cur := this.head
fmt.Println("当前元素为：", cur.data)
for cur.next != nil {
cur = cur.next
fmt.Println("当前元素为：", cur.data)
}
}
}
func main() {
//初始化
lst := &DelinkList{}
for i := 0; i < 10; i++ {
lst.appendData(i)
}
//头部插入数据
lst.addData("newNode")
//指定位置插入元素
lst.insertData(7, 100)
//删除元素
lst.deletData(4)
n := lst.length()
fmt.Println("表长为：", n)
//显示所有元素
lst.showList()
}
运行结果：
循环单链表
1.循环单链表和单链表大致一样，但不同的地方在于，尾指针并不是指向nil，而是指向表头。如图所示：
基本操作：
其基本操作大致和单链表相同，只是头部和尾部添加数据略有不同。需要将尾部元素的指针域指向头部元素！就不作图演示了。
2.代码演示：
package main
import (
"fmt"
)
type object interface{}
type node struct {
data object //数据域
next *node //指针域
}
type cLinkList struct {
num uint64 //数量
head *node //头节点
}
//初始化链表
func newList() *cLinkList {
return &cLinkList{
num: 0,
head: nil,
}
}
//获取表头节点
func (this *cLinkList) getHead() *node {
return this.head
}
//获取节点数量
func (this *cLinkList) getNum() uint64 {
return (*this).num
}
//添加表尾数据,在头部和尾巴添加数据效果一样
func (this *cLinkList) appenData(data object) {
newNode := &node{data: data}
if this.getNum() == 0 {
// 无数据，将data作为表头
(*this).head = newNode
} else {
//尾巴
cur := this.getHead()
for ; (*cur).next != this.getHead(); cur = (*cur).next {
}
(*cur).next = newNode
}
(*newNode).next = (*this).getHead()
(*this).num++
}
//index后添加数据
func (this *cLinkList) insertData(index int, data object) {
newNode := &node{data: data}
if index < 0 || uint64(index) > this.getNum() {
this.appenData(data)
} else {
cur := this.getHead()
count := 0
for count < index-1 {
cur = cur.next
count++
}
newNode.next = cur.next
cur.next = newNode
}
}
//删除元素
func (this *cLinkList) removeData(data object) {
elem := &node{data: data}
if elem == nil {
fmt.Println("输入元素有误！")
}
cur := this.getHead()
//遍历到elem节点之前
for ; (*cur).next != elem; cur = (*cur).next {
}
(*cur).next = (*elem).next
this.num--
}
//获取下一个节点
func (this *node) getTail() object {
return this.next
}
//显示列表所有元素
func (this *cLinkList) showList() {
if this.getNum() == 0 {
fmt.Println("当前为空表！")
} else {
cur := this.head
fmt.Println("当前元素为：", cur.data)
for cur.next != this.getHead() {
if cur.next == this.getHead() {
break
}
cur = cur.next
fmt.Println("当前元素为：", cur.data)
}
}
}
func main() {
//初始化链表
lst := newList()
//添加数据
for i := 0; i < 9; i++ {
lst.appenData(i)
}
//指定位置插入元素
lst.insertData(6, 100)
//删除指定元素
lst.removeData(6)
//显示所有元素
lst.showList()
}
运行结果：由于电脑故障，控制台一直输出不了，因此结果有带点问题。方法insertData()存在问题!
循环双链表
1.循环双链表和双链表也类似，但时尾部指针的后指针域指向头部元素，头部元素的前指针域指向尾部元素。如图：
2.基本操作与双链表类似，但操作难度更高，作者水平有限，此处代码转载于：https://studygolang.com/artic... 作者：JimPang 时间： 2018-08-30 11:10:32
其他：头插法和尾插法
package main
import (
"fmt"
)
type object interface{}
type list struct {
data object
next *list //指向1下一个地址
}
//遍历全表
func (l *list) showall() {
for l.next != nil {
fmt.Println(l.data)
}
}
func main() {
//建立表头和尾巴
head := &list{data: 1}
tail := &list{data: 2}
//链接头尾
head.next = tail
func() {
header := list{data: 0}
temp := &header
for i := 0; i < 10; i++ {
headerNext := list{data: i, next: temp} //创建结构体实例，因为是头插法，所以应该将上一个节点的地址作为next值传入。默认首次为头节点的存储地址
temp = &headerNext //进行下一次插入时，因为是头插法，所以此次的结构体实例作为下一次的next值，所以进行更改temp
}
}()
func() {
header := list{data: 0}
temp := &header
for i := 0; i < 10; i++ {
headerlast := list{data: i}
temp.next = &headerlast //将上一个结构体的next字段，设为本次循环结构体实例的地址，由于是尾插法。
temp = &headerlast // 进行循环，将上一个结构体的实例改为本次循环的结构体实例
}
}()
}
本章内容部分转载！
有疑问加站长微信联系（非本文作者）
