线性表 - 顺序存储结构

 提示:转载请注明原文链接

 本文永久链接:https://360us.net/article/44.html

线性表顺序存储结构是指在内存上用连续的存储空间来存储数据。

这就导致这种结构需要在初始化的时候就申请好需要的全部空间。

如下图,每一个格子代表一片内存的存储区域,如果我们初始化了一个最大5个元素的顺序存储的线性表,那么它在内存中的存储位置,可能是0,1,2,3,4,也可能只2,3,4,5,6,总之他们的内存地址是连续的。

2015-12-22 22-29-36屏幕截图.png

这种结构用完空间之后就没有了,申请多大的空间也不好把握,如果申请的比较大,没有存储数据的空间别的程序也不能使用,只能浪费在哪里了,所以灵活性较小。

这种结构和数组很相似,所以可以用数组来实现。

Go 代码实现:

package main

import (
   "fmt"
   "errors"
   "os"
)

//最大长度
const MAXSIZE = 10

type List struct {
   node [MAXSIZE]int //链表节点
    len int  //链表当前长度
}

func main() {
    l := NewList()
   for i := 0; i < 9; i++ {
      n := i + 1
      _,_ = l.Insert(i, n)
   }

   //插入
   _, error := l.Insert(2, 5)
   if error != nil {
      fmt.Println(error)
      os.Exit(1)
   }
   fmt.Println(l)

   //删除
   _, error = l.Delete(5)
   if error != nil {
      fmt.Println(error)
      os.Exit(1)
   }
   fmt.Println(l)
}

//初始化链表
func NewList() *List {
   return new(List)
}

//链表长度
func (l *List) ListLen() int {
   return l.len
}

//指定位置插入元素
func (l *List) Insert(position, node int) (bool, error) {
    if position < 0 || position >= len(l.node) {
      return false, errors.New("溢出")
   }

   //存储的元素长度等于空间长度时,链表已满
   if l.len == len(l.node) {
      return false, errors.New("已满")
   }

   for i := len(l.node) - 1; i >= 0; i-- {
      //找到位置
      if i == position {
         break
      }
      //没有找到位置,上一个元素移到当前位置
      l.node[i] = l.node[i-1]
   }

   l.node[position] = node
   l.len += 1
   return true, nil
}

//删除指定位置的元素
func (l *List) Delete(position int) (bool, error) {
   if position < 0 || position >= len(l.node) {
      return false, errors.New("溢出")
   }
   if l.node[position] == 0 {
      return false, errors.New("没有这个元素")
   }

   l.node[position] = 0
   //空出来的位置前移
   for ; position < len(l.node); position++ {
      if position == len(l.node) - 1 {
         l.node[position] = 0
         break
      }
      l.node[position] = l.node[position+1]
   }
   l.len -= 1
   return true, nil
}


 评论
暂无评论