顺序表-Go语言实现

简单理解就是数组；

优缺点及使用场景

优点：

• 随机访问，在O（1）时间内找到第i个元素；

  数据表中的数据是连续存放的，因此只要知道数据表中第一个元素的地址，那么后面的数据元素的地址就可以马上算出来。

• 存储密度高，每个节点只存储数据元素本身；

  无需为表中元素之间的逻辑关系添加额外的存储空间；

缺点：

• 扩展容量不方便；

  静态分配不能拓展容量；即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高；

• 插入、删除操作不方便，需要移动大量元素

  ⚠️：尾插效率高！

使用场景：

• 存储密度高；
• 对头，中插入删除操作不频繁，可对尾频繁插入，删除；
• 创建顺序表之前需要对MaxSize有合理预估；

常用操作

顺序表结构，一般有：表体、描述（如length）；

const MaxSize int = 100
 
type SeqList struct {
	data []int
	length int
}

插入：把插入位置i之后的所有元素往后移再插入；

//InsertList 把value插入第i位置，i-1为index；i从1开始
func (s *SeqList) InsertList(value, i int) error {
	if i < 1 || i > s.length+1 {
		return errors.New("error insert location")
	}
	for j := s.length; j >= i-1; j-- {
		s.data[j] = s.data[j-1]
	}
	s.data[i-1] = value
	s.length++
	return nil
}

删除：把删除位置i之后的所有元素往前移，覆盖掉原来第i个；

//DeleteList 删除第i个
func (s *SeqList) DeleteList(i int) error {
	if i < 1 || i > s.length {
		return errors.New("delete error location")
	}
	for j := i; j < s.length; j++ {
		s.data[j-1] = s.data[j]
	}
	s.length--
	return nil
}

Golang实现

package main

import (
	"errors"
	"fmt"
)

const MaxSize int = 100

type SeqList struct {
	data   []int
	length int
}

//NewSeqList 声明并初始化顺序表，为顺序表分配内存空间；
func NewSeqList() *SeqList {
	if MaxSize == 0 {
		return nil
	}
	return &SeqList{
		data:   make([]int, MaxSize, MaxSize),
		length: 0,
	}

}

//CreateList 给表里添加初始元素
func (s *SeqList) CreateList(data []int, n int) error {
	if n > MaxSize {
		return errors.New("表长不足")
	}
	for i, value := range data {
		s.data[i] = value
	}
	s.length = n
	return nil
}

//InsertList 把value插入第i位置，i-1为index；i从1开始
func (s *SeqList) InsertList(value, i int) error {
	if i < 1 || i > s.length+1 {
		return errors.New("error insert location")
	}
	for j := s.length; j >= i-1; j-- {
		s.data[j] = s.data[j-1]
	}
	s.data[i-1] = value
	s.length++
	return nil
}

//DeleteList 删除第i个
func (s *SeqList) DeleteList(i int) error {
	if i < 1 || i > s.length {
		return errors.New("delete error location")
	}
	for j := i; j < s.length; j++ {
		s.data[j-1] = s.data[j]
	}
	s.length--
	return nil
}

func main() {
	seqList := NewSeqList()
	initDate := []int{0, 1, 2, 3, 4, 5, 6}
	err := seqList.CreateList(initDate, len(initDate))
	if err != nil {
		fmt.Println(err)
	}
	seqList.InsertList(10, 2)
	seqList.SeqListPrint()
	seqList.DeleteList(2)
	seqList.SeqListPrint()
}

//SeqListPrint 答应顺序表
func (s *SeqList) SeqListPrint() {
	fmt.Println("-------------------")
	fmt.Print("data: ")
	for i := 0; i < s.length; i++ {
		fmt.Printf("%v ", s.data[i])
	}
	fmt.Println()
	fmt.Println("length: ", s.length)
}