Go数据结构之顺序表(SqList)

浏览数：38 / 时间：2015年06月12日

顺序表－SqList

顺序表是在计算机内存中以数组的形式保存的，是一组地址连续的存储单元依次存储的结构，特点：查询是常数时间，添加和删除是线性时间O(n)。

以下是我用Go语言实现的顺序表，其实里面还是用Go自身的Slice存储，程序还是相对简单：

/**
 * Created with IntelliJ IDEA.
 * Date: 4/24/14
 * Time: 5:11 PM
 * 这是一个自定义的顺序表数据结构.
 * Author: [email protected]
 * Copyright 2014 Requelqi. All rights reserved.
 */
package SqList

import (
    "errors"
    "fmt"
)

const (
    DefaultSize = 100
)

//定义顺序表中的元素类型
type ElementType interface{}

//定义顺序表的结构体
type SqList struct {
    elems []ElementType //元素数组
    pos   int           // 当前顺序表的下标
}

/**
  根据指定的大小创建一个顺序表
*/
func NewSqListBySize(size int) *SqList {
    return &SqList{make([]ElementType, size), -1}
}

/**
 *创建默认大小的顺序表
 */
func NewSqListDefault() *SqList {
    return NewSqListBySize(DefaultSize)
}

/**
 * 清空顺序表
 */
func (list *SqList) ClearList() {
    list.pos = -1
}

/**
 * 判断顺序表是否为空
 */
func (list *SqList) IsEmptyList() bool {
    return list.pos == -1
}

/**
 * 顺序表的长度
 */
func (list *SqList) Length() int {
    return list.pos + 1
}

/**
 * 顺序表当前容量
 */
func (list *SqList) Capacity() int {
    return cap(list.elems)
}

/**
 * 获取指定下标的元素
 */
func (list *SqList) GetElem(pos int) (ElementType, error) {
    err := list.validPostion(pos)
    if (err != nil) {
        return nil, err
    }
    if list.pos == -1 {
        return nil, nil
    }
    return list.elems[pos], nil
}

/**
 *顺序表后面追加元素
 */
func (list *SqList) AddElement(x ElementType) error {
    if cap(list.elems) == list.pos + 1 {
        return errors.New("The SqList is full.")
    }else {
        list.elems[list.pos + 1] = x
        list.pos++
    }
    return nil
}

/**
 * 指定位置插入
 */
func (list *SqList) Insert(x ElementType, pos int) error {
    err := list.validInsertPostion(pos)
    if (err != nil) {
        return err
    }
    for i := list.pos; i >= pos; i-- {
        list.elems[i + 1] = list.elems[i]
    }
    list.elems[pos] = x
    list.pos++
    return nil
}

/**
    删除指定位置的元素，之后元素前移
 */
func (list *SqList) Remove(pos int) error {
    err := list.validPostion(pos)
    if (err != nil) {
        return err
    }
    for i := pos; i < list.pos; i++ {
        list.elems[i] = list.elems[i + 1]
    }
    list.pos--
    return nil
}

/**
    更新指定位置的元素
 */
func (list *SqList) Update(x ElementType, pos int) error {
    err := list.validPostion(pos)
    if err != nil {
        return err
    }
    list.elems[pos] = x
    return nil
}

/**
 * 打印顺序表中的内容
 */
func (list *SqList) PrintList() {
    fmt.Println("The elements is:")
    for i := 0; i <= list.pos; i++ {
        tmp, _ := list.GetElem(i)
        fmt.Println(" ", tmp)
    }
}

/**
    包内可见方法，校验插入的时候输入的pos是否合法。
 */
func (list *SqList) validInsertPostion(pos int) error {
    if pos > cap(list.elems) || pos < 0 {
        return errors.New("SqList pos out 0f bounds error.")
    }
    if pos > list.pos + 1 || pos < 0 {
        return errors.New("you set a wrong position.")
    }
    return nil
}
/**
    包内可见方法，校验修改（update Or remove Or get）的时候输入的pos是否合法。
 */
func (list *SqList) validPostion(pos int) error {
    if pos > cap(list.elems) || pos < 0 {
        return errors.New("SqList pos out 0f bounds error.")
    }
    if pos > list.pos || pos < 0 {
        return errors.New("you set a wrong position.")
    }
    return nil
}