线性表基本概念
线性表是最基本、最简单、最常用的一种数据结构之一。在实际应用中，线性表都是以数组、字符串、链表、栈、队列、位图等特殊线性表的形式来使用的。因为这些特殊线性表都具有自己的特性，所以掌握这些特殊线性表的特性，对于数据运算的可靠性和提高操作效率是至关重要的。
线性表.png
线性表是一个线性结构，它是一个含有n≥0个节点的有限序列。在节点中，有且仅有一个开始节点没有前驱并有一个后继节点，有且仅有一个终端节点没有后继并有一个前驱节点。
其他的节点都有且仅有一个前驱和一个后继节点。
通常可以把一个线性表表示成一个线性序列：k1，k2，…，kn，其中k1是开始节点，kn是终端节点。
1.线性结构的特征
在编程领域中，线性结构具有如下两个基本特征：
- （1）列表中必存在唯一的“第一元素”和唯一的“最后元素”。
- （2）除最后一个元素之外，均有唯一的后继和唯一的前驱。
由n（n≥0）个数据元素（节点）a1，a2，…，an组成的有限序列，数据元素的个数n定义为表的长度。
当n=0时称为空表，我们通常将非空的线性表（n>0）记作：
(a1,a2,…,an)数据元素ai（1≤i≤n）没有特殊含义，大家不必去“刨根问底”地研究它。它只是一个抽象的符号，其具体含义在不同的情况下可以不同。
2.线性表的基本操作过程
线性表虽然只是一个线性序列，但是其操作功能非常强大，具备了很多操作技能。
线性表的基本操作过程如下所示：
- （1）用Setnull(L)置空表。
- （2）用Length(L)求表的长度和表中各元素的个数。
- （3）用Get(L,i)获取表中的第i个元素（1≤i≤n）。
- （4）用Prior(L,i)获取i的前趋元素。
- （5）用Next(L,i)获取i的后继元素。
- （6）用Locate(L,x)返回指定元素在表中的位置。
- （7）用Insert(L,i,x)插入新元素。
- （8）用Delete(L,x)删除已存在的元素。
- （9）用Empty(L)来判断表是否为空。
3.线性表的结构特点
- 均匀性：虽然不同数据表的数据元素是各种各样的，但同一线性表的各数据元素必须有相同的类型和长度。
- 有序性：各数据元素在线性表中的位置只取决于它们的序。数据元素之前的相对位置是线性的，
即存在唯一的“第一个”和“最后一个”的数据元素，除了第一个和最后一个外，其他元素前面只有一个数据元素直接前趋，后面只有一个直接后继。
4.两种实现线性表存储方式：
1.顺序存储结构： 连续内存的线性存储结构，如数组、切片。
顺序表有一个硬性规定，即用连续的存储单元顺序存储线性表中的各元素。
根据这条硬性规定，当对顺序表进行插入和删除操作时，必须移动数据元素才能实现线性表逻辑上的相邻关系。
很不幸的是，这种操作会影响运行效率。
数组.jpg
2.链式存储结构： 存储的值可以是不连续内存，每个节点都持有下一节点（或上一节点）的指针，链式存储结构不需要用地址连续的存储单元来实现，而是通过“链”建立起数据元素之间的次序关系。
所以它不要求逻辑上相邻的两个数据元素在物理结构上也相邻，在插入和删除时无须移动元素，从而提高了运行效率。
链式存储结构主要有单链表、循环链表、双向链表、静态链表等几种形式。
链表.png
Go中的数组和链表
大多数语言在底层已经提供数组的实现，且是最基本的数据结构，是其他数据结构的基础。Go语言除数组外，更常用的是切片，在标准包中也提供了双向链表的包。这里为了演示线性表的这两种结构，我写了一些模拟代码：
数组模拟
// 自定义切片类型，切片底层为数组
type ListArray []interface{}
// 数组工厂方法
func NewArray(n int) *ListArray {
slice := make([]interface{}, 0, n)
a := ListArray(slice)
return &a
}
// 计算顺序表长度；
func (a *ListArray) Len() int {
return len(*a)
}
// 计算顺序表容量；
func (a ListArray) Cap() int {
return cap(a)
}
// 清空操作；
func (a *ListArray) Clean() {
*a = nil
}
// 判断是否为空；
func (a *ListArray) IsEmpty() bool {
return len(*a) == 0
}
// 判断是否为满；
func (a *ListArray) IsFilled() bool {
return len(*a) == cap(*a)
}
// 尾部追加
func (a *ListArray) Append(element ...interface{}) {
*a = append(*a, element...)
}
// 任意元素插入
func (a *ListArray) Insert(i int, element ...interface{}) {
slice := []interface{}(*a)
if i > len(*a)-1 {
slice[i] = element
return
}
if i < 0 {
i = 0
}
var b []interface{}
b = append(slice[:i], element...)
b = append(b, slice[i:]...)
c := ListArray(b)
*a = c
}
// 删除任意元素
func (a *ListArray) Remove(i int) {
slice := []interface{}(*a)
b := append(slice[:i], slice[i+1:]...)
c := ListArray(b)
*a = c
}
// 按值查找
func (a *ListArray) Contain(element interface{}) int {
for k, v := range *a {
if v == element {
return k
}
}
return -1
}
链表
go标准包 container/list 已提供双向链表实现：
常用操作:
1.Init() 创建链表并初始化
2.Len() 保存于链表结构字段中
3.Front() 返回链表第一个元素
4.Back() 返回链表最后一个元素
5.Remove(element) 移除链表元素
6.PushFront(v) 插入元素到表头
7.PushBack(v) 插入元素到表尾
8.InsertBefore(v,mark) 在某个元素前插入
9.InsertAfter(v,mark) 在某个元素后插入
10.MoveToFront(e) 移动元素到表头
11.MoveToBack(e) 移动元素到表尾
12.MoveBefore(e,mark) 移动元素到某个元素之前
13.MoveAfter(e,mark) 移动元素到某个元素之后
14.PushBackList() 从另一个链表拷贝元素追加到当前链尾
15.PushFrontList() 从另一个链表拷贝元素追加到当前链头
以下参照标准包修改一个单向链表的代码：
// 实现单向链表
type Element struct {
next *Element
list *List
Value interface{}
}
// 链表元素迭代方法
func (e *Element) Next() *Element {
if p := e.next; e.list != nil && p != &e.list.root {
return p
}
return nil
}
// 链表
type List struct {
root Element // 哨兵根节点
len int // 维护一个长度属性
}
// 初始化
func (l *List) Init() *List {
l.root.next = &l.root
l.len = 0
return l
}
// 链表工厂方法
func New() *List { return new(List).Init() }
// 长度保存于链表结构字段中
func (l *List) Len() int { return l.len }
// 返回链表的第一个元素
func (l *List) Front() *Element {
return l.root.next
}
// 返回链表最后一个元素
func (l *List) Back() *Element {
e := l.root.next // root为哨兵头节点，第一个节点为root.next
if e == &l.root {
// 没有元素时还是返回root
return e
}
for {
if e.next == nil {
return e
}
e = e.Next()
}
}
// 内部方法：插入元素
func (l *List) insert(e, at *Element) *Element {
n := at.next
at.next = e
e.next = n
e.list = l
l.len++
return e
}
// 内部方法：插入值
func (l *List) insertValue(v interface{}, at *Element) *Element {
return l.insert(&Element{Value: v}, at)
}
// 内部方法：删除元素
func (l *List) remove(e *Element) *Element {
var prev *Element
ele := l.root.next // 第一个元素
for {
if ele.next == nil { // 尾元素
return nil
}
if ele == e { // 找到该删除的元素
prev.next = ele.next // 前一个元素接链
l.len--
return ele
}
prev = ele // 暂存当前迭代元素
ele = ele.Next() // 迭代下一个
}
return nil
}
// 内部方法，移动元素
func (l *List) move(e, at *Element) *Element {
if e == at {
return e
}
n := at.next
at.next = e
e.next = n
return e
}
// 删除链表元素
func (l *List) Remove(e *Element) *Element {
return l.remove(e)
}
// 插入元素到表头
func (l *List) PushFront(v interface{}) {
l.insertValue(v, &l.root)
}
// 插入元素到表尾
func (l *List) PushBack(v interface{}) {
var tail *Element
for {
e := l.root.Next()
if e.next == nil {
tail = e
break
}
}
l.insertValue(v, tail)
}
// 在某个元素前插入
func (l *List) InsertBefore(v interface{}, mark *Element) *Element {
return l.insertValue(v, mark)
}
// 在某个元素后插入
func (l *List) InsertAfter(v interface{}, mark *Element) *Element {
return l.insertValue(v, mark)
}
// 移动元素到表头
func (l *List) MoveToFront(e *Element) {
l.move(e,&l.root)
}
// 移动元素到表尾
func (l *List) MoveToBack(e *Element) {
var tail *Element
for {
e := l.root.Next()
if e.next == nil {
tail = e
break
}
}
l.move(e,tail)
}
// 移动元素到某个元素之前
func (l *List) MoveBefore(e, mark *Element) {
l.move(e,mark)
}
// 移动元素到某个元素之后
func (l *List) MoveAfter(e, mark *Element) {
l.move(e,mark)
}
// 从另一个链表拷贝元素追加到当前链尾
func (l *List) PushList(other *List) {
l.lazyInit()
for i, e := other.Len(), other.Front(); i > 0; i, e = i-1, e.Next() {
l.PushBack(e.Value)
}
}
// lazyInit lazily initializes a zero List value.
func (l *List) lazyInit() {
if l.root.next == nil {
l.Init()
}
}
网友评论