# 线性表结构
数组 链表（单向、双向、循环） 特殊的线性表：栈 特殊的线性表：队列 编程技巧：递归
# 线性表分为顺序存储结构和链式存储结构
# 线性表的顺序存储结构
- 优点：
- 无需为表示表中元素之间的逻辑关系而增加额外的存储空间（有下标）
- 可以快速的存＼取表中任意位置的元素
- 缺点：
- 插入和删除操作需要移动大量的元素，耗费时间
- 当线性表长度变化较大时，难以确定存储空间的容量
- 容易造成存储空间的＂碎片＂（申请空间是一整块申请的） Golang实现线性表顺序存取结构
package main
import (
"errors"
"fmt"
)
const MAX_LENGTH = 20 // 常量定义线性表最大长度
// 定义一个线性表顺序存储结构体
type LineList struct {
MaxLength int
Length int
LineListContent []interface{}
}
// 初始化一个线性表
func InitLineList () *LineList{
return &LineList{MaxLength:MAX_LENGTH, LineListContent:make([]interface{},0,MAX_LENGTH)}
}
// 判断当前线性表是否为空
func (l LineList) IsEmpty() bool {
if l.Length == 0{
return true
}
return false
}
// 判断当前线性表是否满了
func (l LineList) IsFull() bool{
if l.Length == l.MaxLength{
return true
}
return false
}
// 判断索引是否越界，越界返回ｔｒｕｅ
func (l LineList) indexOver(i int) bool{
if i < 1 || i >l.Length{
return true
}
return false
}
// 获取一个ｎｏｄｅ数据
func (l LineList) getData(i int )(interface{},error){
if ok:= l.indexOver(i); ok{
return "",errors.New("查找的索引不在线性表范围内")
}
return l.LineListContent[i+1],nil
}
// 任意位置删除一个ｎｏｄｅ数据
func (l *LineList) Delete(i int)(interface{},error){
if ok:= l.indexOver(i); ok{
return "",errors.New("删除的索引不在线性表范围内")
}
if ok:=l.IsEmpty();ok{
return "",errors.New("空表没有可删除的数据")
}
deleteData := l.LineListContent[i-1]
for j:=i-1; j<l.Length-1;j++{
l.LineListContent[j] = l.LineListContent[j+1]
fmt.Println(j,"个",l.LineListContent[j])
}
l.LineListContent = l.LineListContent[:l.Length-1] // 留了最后一个在，需要切除
l.Length --
return deleteData,nil
}
//末尾 ｐｏｐ 一个数据
func (l *LineList) Pop()(interface{},error){
if ok:= l.IsEmpty();ok{
return "",errors.New("空表，无法删除任何数据")
}
temp := l.LineListContent[l.Length-1]
l.LineListContent = l.LineListContent[:l.Length-1]
l.Length --
return temp,nil
}
// 末尾 Append 一个数据
func (l *LineList) Append(data interface{})(bool,error){
if ok:= l.IsFull(); ok{
return false,errors.New("线性表已满，无法添加数据")
}
l.LineListContent = append(l.LineListContent, data)
l.Length ++
return true,nil
}
// 任意位置 ｉｎｓｅｒｔ 一个数据
func (l *LineList) Insert(i int,data interface{})(bool,error){
if ok:= l.IsFull(); ok{
return false,errors.New("线性表已满，无法添加数据")
}
if ok:= l.indexOver(i);ok{
return false,errors.New("插入点越界")
}
l.Append("") // 增加一个空数据，防止下面访问越界
for j:=l.Length-1;j>i-1;j--{
//从后往前赋值，新增一个空ｎｏｄｅ，然后把数据一个个后移，直到插入的位置
//知道线性表从１开始，而切片是从０开始的
l.LineListContent[j] = l.LineListContent[j-1]
}
l.LineListContent[i-1] = data
return true,nil
}
func main(){
ls := InitLineList()
ls.Append(11)
fmt.Println(ls.LineListContent) //[11]
fmt.Println(ls.Length) // 1
ls.Insert(3,"gac")
ls.Insert(1,"gac")
fmt.Println(ls.LineListContent) //[gac 11]
fmt.Println(ls.Length) //2
ls.Delete(2)
fmt.Println(ls.LineListContent) //[gac]
fmt.Println(ls.Length) // 1
cd,err0 := ls.Pop()
if err0==nil{
fmt.Println(cd) // gac
}
fmt.Println(ls.LineListContent) //[]
fmt.Println(ls.Length) // 0
}
# 线性表的链式存储结构－－单链表
- 特点：除了要存储数据元素信息外还要存储后继元素的存储地址（指针）数据域＋指针域＝存储映像（节点node）,因为此链表的每个节点中值包含一个指针域，所以叫做单链表
package main
import (
"fmt"
)
type Node struct {
data interface{}
next *Node
}
// get the first Node
func (n *Node) getFirstNode() *Node{
if n.next == nil{
return nil
}
return n.next
}
// get the end Node
func (n *Node) getEndNode() *Node{
if n.next == nil{
return nil
}
for n.next != nil{
n = n.next
}
return n
}
// Append a Node to linkList
func (n *Node) Append(data interface{})bool{
// create a Node
tempNode := &Node{data, nil}
//i := n
for n.next!=nil{
n = n.next
}
n.next = tempNode
return true
}
// find a Node
func (n *Node) getOneNode(i int)*Node{
length := 0
for n.next!=nil{
length ++
if i == length{
return n.next
}
n = n.next
}
return nil
}
// delete a Node
func (n *Node) Delete(i int)*Node{
length:=0
for n.next!=nil{
length ++
if i == length{
temp := n.next
n.next = n.next.next
return temp
}
n = n.next
}
return nil
}
// insert into the LinkList everywere
func (n *Node) Insert (i int ,data interface{}) bool {
needAppend := &Node{ data ,nil}
if i>n.getLinkLength() || i< 1{
panic("插入位置错误")
return false
}
length := 1
for n.next != nil{
if i == length{
temp := n.next
n.next = needAppend
needAppend.next = temp
return true
}
}
return false
}
func (n *Node)getLinkLength()int{
length := 0
for n.next!=nil{
length++
n = n.next
}
return length
}
// map the LinkList all data
func (n *Node) MapTheLinkList(){
length := n.getLinkLength()
for i:=0;i<length; i++{
fmt.Println(n.next.data)
n = n.next
}
}
func (n *Node) Clear() bool{
if n.next == nil{
return true
}
n.next = nil
return true
}
// init a linkList
func initLinkList () *Node{
return &Node{"the head node",nil}
}
func main(){
li := initLinkList() // 初始化一个空单链表
fmt.Println(li)
li.Append("aaa")
fmt.Println(li)
li.Append("bbb")
li.Append("ccc")
li.Append("ddd")
fmt.Println(*li.getFirstNode()) //{aaa 0xc04204a440}
fmt.Println(*li.getEndNode()) //{ddd <nil>}
fmt.Println(li.getLinkLength()) // 4
fmt.Println("delete = ", li.Delete(1)) //delete = &{aaa 0xc04204a440}
fmt.Println(*li.getFirstNode()) //{bbb 0xc04204a460}
fmt.Println(*li.getEndNode()) //{ddd <nil>}
fmt.Println(li.getLinkLength()) // 3
li.Append("eee")
li.Append("ggg")
li.MapTheLinkList() // bbb ccc ddd eee ggg
fmt.Println(li.getLinkLength()) //5
li.Clear()
fmt.Println(li) //&{the head node <nil>}
}
- 线性表的链式存储，以及使用快慢指针找不知长度链表的中间节点
package main
import (
"fmt"
"strconv"
)
// 定义一个node结构体
type Node struct {
data string
next *Node
}
func (n *Node) Append(data string){
createNode := &Node{data,nil}
for n.next != nil{
n = n.next
}
n.next = createNode
}
func (n *Node) GetLength() int{
if n.next==nil{
return 0
}
length:= 0
for n.next!=nil{
length ++
n = n.next
}
return length
}
func (n *Node) MapLinkList()[]string{
var str []string
if n.next == nil{
return nil
}
for n.next != nil{
str = append(str,n.next.data)
n = n.next
}
return str
}
// 快慢指针法求不知道长度的链表的中间值
func (n *Node)GetCenterNode()[]string{
str := make([]string,0,2)
if n.next==nil{
return nil
}
l := n.next
s := n.next
for s.next!= nil{
// 单数情况
if l.next==nil{
str = append(str, s.data)
return str
}
// 双数情况
if l.next != nil && l.next.next == nil{
str = append(str,s.data)
str = append(str,s.next.data)
return str
}
s =s.next
l = l.next.next
}
return str
}
// 初始化一个链表
func initLinkList ()*Node{
return &Node{"genesis node", nil}
}
func Rand20List(n *Node){
for i:=0;i<3;i++{
n.Append("this is "+strconv.Itoa(i))
}
}
func main(){
link := initLinkList()
var s int
for {
fmt.Println("1.查看链表")
fmt.Println("2.创建链表20个数据")
fmt.Println("3.链表长度")
fmt.Println("4.查看中间节点值")
fmt.Println("5.退出")
fmt.Println("请输入选择：")
fmt.Scan(&s)
switch s {
case 1:
fmt.Println(link.MapLinkList())
case 2:
Rand20List(link)
case 3:
fmt.Println(link.GetLength())
case 4:
fmt.Println(link.GetCenterNode())
case 5:
return
}
}
}
← 1、Leetcode前导篇 3、排序算法 →