目录
1.顺序表-线性表顺序存储结构
1.1顺序表结构体定义
1.2顺序表初始化创建
1.3顺序表查找元素k第一次出现时的下标
1.4顺序表插入元素
1.5顺序表删除元素
1.6最终代码和实现效果
2.单向链表-线性表链式存储结构
2.1单向链表的定义
2.2单向链表的初始化创建
2.3单向链表插入元素
2.4单向链表删除元素
2.5查询索引位置i的数据
2.6查询K值第一次出现时所在的索引位置
2.7最终代码实现和效果
线性表的抽象数据类型描述
数据对象集：线性表是n(>=0)个元素构成的有序序列。
操作集：
- 初始化一个空线性表；
- 根据位序K，返回相应元素；
- 在线性表中查找X的第一次出现的位置；
- 在指定位置插入元素；
- 在指定位置删除元素；
- 返回线性表的长度；
1.顺序表-线性表顺序存储结构
1.1顺序表结构体定义
type SeqList struct {
data []int
maxSize int //最大长度
length int //当前长度
}
1.2顺序表初始化创建
func initSeqList(maxSize int) (list *SeqList) {
var data []int
list = &SeqList{
data: data,
maxSize: maxSize,
length: 0,
}
return list
}
1.3顺序表查找元素k第一次出现时的下标
func (sl *SeqList) find(k int) (int, error) {
i := 0
for sl.maxSize != i && sl.data[i] != k {
i++
}
if sl.maxSize == i {
return -1, errors.New("没有查到")
} else {
return i, nil
}
}
1.4顺序表插入元素
func initSeqList(maxSize int) (list *SeqList) {
var data []int
list = &SeqList{
data: data,
maxSize: maxSize,
length: 0,
}
return list
}
1.3顺序表查找元素k第一次出现时的下标
func (sl *SeqList) find(k int) (int, error) {
i := 0
for sl.maxSize != i && sl.data[i] != k {
i++
}
if sl.maxSize == i {
return -1, errors.New("没有查到")
} else {
return i, nil
}
}
1.4顺序表插入元素
在下标为i的位置插入元素
func (sl *SeqList) insert(i int, v int) error {
if sl.maxSize == sl.length {
return errors.New("线性表元素已满")
}
if i < 0 || i >= sl.maxSize {
return errors.New("下标位置不合法")
}
if i == sl.length { //i的位置在最后时或者线性表中没有元素时
sl.data[i] = v
sl.length++
} else {
for j := sl.length - 1; j >= i; j-- {
sl.data[j+1] = sl.data[j]
}
sl.data[i] = v
sl.length++
}
return nil
}
1.5顺序表删除元素
在下标为i的位置删除元素
func (sl *SeqList) delete(i int) error {
if sl.length == 0 {
return errors.New("线性表为空")
}
if i < 0 || i >= sl.maxSize {
return errors.New("下标位置不合法")
}
if i == sl.length { //i的位置在最后时或者线性表中没有元素时
sl.length--
sl.data = append(sl.data[:sl.length-1])
} else {
for j := i; j < sl.length-1; j++ {
sl.data[j] = sl.data[j+1]
}
sl.length--
sl.data = append(sl.data[:sl.length-1])
}
return nil
}
1.6最终代码和实现效果
package main
import (
"errors"
"fmt"
)
type SeqList struct {
data []int
maxSize int //最大长度
length int //当前长度
}
func main() {
list1 := initSeqList(10)
fmt.Println("初始化线性表:", *list1)
//顺序插入
for i := 0; i < 6; i++ {
err := list1.insert(i, i)
if err != nil {
fmt.Println(err.Error())
}
fmt.Println("顺序插入值后的线性表:", *list1)
}
//中间插入
err := list1.insert(1, 100)
if err != nil {
fmt.Println(err.Error())
}
fmt.Println("中间插入值后的线性表:", *list1)
index1, err := list1.find(4)
if err != nil {
fmt.Println(err.Error())
}
fmt.Println("4的值在索引:", index1)
err = list1.delete(3)
if err != nil {
fmt.Println(err.Error())
}
fmt.Println("删除索引后的线性表:", *list1)
}
func initSeqList(maxSize int) (list *SeqList) {
var data []int
list = &SeqList{
data: data,
maxSize: maxSize,
length: 0,
}
return list
}
func (sl *SeqList) find(k int) (int, error) {
i := 0
for sl.maxSize != i && sl.data[i] != k {
i++
}
if sl.maxSize == i {
return -1, errors.New("没有查到值相同的元素")
} else {
return i, nil
}
}
func (sl *SeqList) insert(i int, v int) error {
if sl.maxSize == sl.length {
return errors.New("线性表元素已满")
}
if i < 0 || i >= sl.maxSize {
return errors.New("下标位置不合法")
}
if i == sl.length { //i的位置在最后时或者线性表中没有元素时
sl.data = append(sl.data, v)
sl.length++
} else {
sl.data = append(sl.data, 0) //切片最后append加入站位
for j := sl.length - 1; j >= i; j-- {
sl.data[j+1] = sl.data[j]
}
sl.data[i] = v
sl.length++
}
return nil
}
func (sl *SeqList) delete(i int) error {
if sl.length == 0 {
return errors.New("线性表为空")
}
if i < 0 || i >= sl.maxSize {
return errors.New("下标位置不合法")
}
if i == sl.length { //i的位置在最后时或者线性表中没有元素时
sl.length--
sl.data = append(sl.data[:sl.length-1])
} else {
for j := i; j < sl.length-1; j++ {
sl.data[j] = sl.data[j+1]
}
sl.length--
sl.data = append(sl.data[:sl.length-1])
}
return nil
}
2.单向链表-线性表链式存储结构
无头节点的单向链表
有头节点的单向链表
2.1单向链表的定义
LinkNode结构体定义链表的节点。
LinkList结构体定义链表的头节点和链表长度，链表头节点其实就是LinkNode。
type LinkNode struct {
data int
next *LinkNode
}
type LinkList struct {
head *LinkNode
length int
}
2.2单向链表的初始化创建
初始化一个有头节点的单向链表
func initLinkList() (linkList *LinkList) {
linkList = &LinkList{
head: &LinkNode{
data: -1,
next: nil,
},
length: 0,
}
return linkList
}
2.3单向链表插入元素
在下标为i的位置插入元素
func (ll *LinkList) insert(i int, v int) error {
if i < 0 {
return errors.New("索引位置不合法")
} else if i > ll.length {
return errors.New("插入位置超出链表长度")
}
//创建需要新增的节点
newNode := &LinkNode{
data: v,
next: nil,
}
tmpNode := ll.head
tmpIndex := 0
//获取要插入位置的前一个节点
for tmpNode != nil && tmpIndex < i {
tmpNode = tmpNode.next
tmpIndex++
}
newNode.next = tmpNode.next //新节点的next，指向原索引位置为i的元素
tmpNode.next = newNode //原索引位置i-1的元素的nex，指向新节点
ll.length++ //链表长度+1
return nil
}
2.4单向链表删除元素
删除下标为i的元素
func (ll *LinkList) delete(i int) error {
if i < 0 {
return errors.New("索引位置不合法")
} else if i >= ll.length {
return errors.New("插入位置超出链表长度")
} else if ll.length == 0 {
return errors.New("链表为空")
}
tmpNode := ll.head
//获取要插入位置的前一个节点
for tmpIndex := 0; tmpIndex < i; tmpIndex++ {
tmpNode = tmpNode.next
}
//获取要删除位置节点
indexNode := tmpNode.next
tmpNode.next = indexNode.next //将索引位置i-1节点的指针指向索引位置i+1节点
indexNode.next = nil //将要删除的节点指针清空
ll.length-- //链表长度-1
return nil
}
2.5查询索引位置i的数据
func (ll *LinkList) searchIndex(i int) (int, error) {
if i < 0 {
return -1, errors.New("索引位置不合法")
} else if i >= ll.length {
return -1, errors.New("插入位置超出链表长度")
} else if ll.length == 0 {
return -1, errors.New("链表为空")
}
tmpNode := ll.head
for tmpIndex := 0; tmpIndex <= i; tmpIndex++ {
tmpNode = tmpNode.next
}
return tmpNode.data, nil
}
2.6查询K值第一次出现时所在的索引位置
func (ll *LinkList) searchValue(k int) (int, error) {
i := 0
tmpNode := ll.head
for ll.length != i && tmpNode.data != k {
i++
}
if ll.length == i {
return -1, errors.New("没有查到值相同的元素")
} else {
return i, nil
}
}
2.7最终代码实现和效果
package main
import (
"errors"
"fmt"
)
type LinkNode struct {
data int
next *LinkNode
}
type LinkList struct {
head *LinkNode
length int
}
func main() {
linkList1 := initLinkList()
//插入数据
linkList1.insert(0, 100)
linkList1.insert(1, 200)
linkList1.insert(0, 1)
v1, _ := linkList1.searchIndex(0)
fmt.Println("索引为0的位置的值:", v1)
v2, _ := linkList1.searchIndex(2)
fmt.Println("索引为2的位置的值:", v2)
v3, _ := linkList1.searchValue(100)
fmt.Println("值为100时的索引位置:", v3)
fmt.Println("---删除索引位置0的节点---")
linkList1.delete(0)
v4, _ := linkList1.searchIndex(0)
fmt.Println("索引为0的位置的值:", v4)
}
func initLinkList() (linkList *LinkList) {
linkList = &LinkList{
head: &LinkNode{
data: -1,
next: nil,
},
length: 0,
}
return linkList
}
func (ll *LinkList) insert(i int, v int) error {
if i < 0 {
return errors.New("索引位置不合法")
} else if i > ll.length {
return errors.New("插入位置超出链表长度")
}
//创建需要新增的节点
newNode := &LinkNode{
data: v,
next: nil,
}
tmpNode := ll.head
tmpIndex := 0
//获取要插入位置的前一个节点
for tmpNode != nil && tmpIndex < i {
tmpNode = tmpNode.next
tmpIndex++
}
newNode.next = tmpNode.next //新节点的next，指向原索引位置为i的元素
tmpNode.next = newNode //原索引位置i-1的元素的nex，指向新节点
ll.length++ //链表长度+1
return nil
}
func (ll *LinkList) delete(i int) error {
if i < 0 {
return errors.New("索引位置不合法")
} else if i >= ll.length {
return errors.New("插入位置超出链表长度")
} else if ll.length == 0 {
return errors.New("链表为空")
}
tmpNode := ll.head
//获取要插入位置的前一个节点
for tmpIndex := 0; tmpIndex < i; tmpIndex++ {
tmpNode = tmpNode.next
}
//获取要删除位置节点
indexNode := tmpNode.next
tmpNode.next = indexNode.next //将索引位置i-1节点的指针指向索引位置i+1节点
indexNode.next = nil //将要删除的节点指针清空
ll.length-- //链表长度-1
return nil
}
func (ll *LinkList) searchValue(k int) (int, error) {
i := 0
tmpNode := ll.head.next
for i < ll.length && tmpNode.data != k {
tmpNode = tmpNode.next
i++
}
if ll.length == i {
return -1, errors.New("没有查到值相同的元素")
} else {
return i, nil
}
}
func (ll *LinkList) searchIndex(i int) (int, error) {
if i < 0 {
return -1, errors.New("索引位置不合法")
} else if i >= ll.length {
return -1, errors.New("插入位置超出链表长度")
} else if ll.length == 0 {
return -1, errors.New("链表为空")
}
tmpNode := ll.head
for tmpIndex := 0; tmpIndex <= i; tmpIndex++ {
tmpNode = tmpNode.next
}
return tmpNode.data, nil
}
func (ll *LinkList) searchValue(k int) (int, error) {
i := 0
tmpNode := ll.head
for ll.length != i && tmpNode.data != k {
i++
}
if ll.length == i {
return -1, errors.New("没有查到值相同的元素")
} else {
return i, nil
}
}
