目的
- 重新温习一遍数据结构，但不过多纠结于数据结构的概念，使用go语言实现，结合go的一些特性，分析其实现原理。
1、顺序表的概念和初始化
1.1、顺序表的概念
- 顺序表的顺序表示指的是用一组地址连续的存储单元以此存储线性表的数据元素，这种表示也称作线性表的顺序存储结构或存储映像，一般称这种存储结构的线性表为顺序表。其特点是，逻辑上相邻的数据元素，其物理次序也是相邻的。
1.2、顺序表的初始化
通常我们会使用数组来描述数据结构中的顺序存储，但是在go语言中，数组在初始化之后大小就无法改变，于是我们选择更加灵活的切片来初始化：
算法步骤：
1、为顺序表L动态分配一个预定义大小的切片。
2、将表的当前长度设为0。
--------------------------------------------------
type Book struct {
ISBN string
name string
price 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，容量为maxsize
MAXSIZE: maxsize,
length: 0}
//将传入的数据导入初始化的实体
for i := range arr {
list.books = append(list.books, arr[i])
list.length++
}
return list
}
- 切片(slice)又称动态数组，依托数组实现，可以方便的进行扩容和传递，通过切片的数据结构，可以将切片理解为一片连续的存储空间加上长度和容量标识。
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
}
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
}
4、顺序表的插入
- 线性表的插入操作是指在表的第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] = e
list.length++
fmt.Println("插入成功")
return
}
5、顺序表的删除
- 线性表的删除操作是指将表的第i个元素删去，将长度为n的线性表变成长度为n-
的线性表。
算法步骤：
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
}
注意：在go语言中并没有提供删除切片元素的语法或接口，而是利用append()函数的特性来“删除”元素，即把待删除位置前后切分为两个新切片，再将其连接起来
6、总结
完整代码
--------------------------------------------------
package main
import (
"fmt"
)
type Book struct {
ISBN string
name string
price 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，容量为maxsize
MAXSIZE: 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] = e
list.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)
}
