这是一系列关于数据结构的笔记博客，为了练习自己的代码能力，咱将尽可能不使用C++来实现这些数据结构

线性表的简单介绍

  • 线性表是具有相同特性的数据元素的一个有限序列。
  • 所有数据元素类型相同。
  • 线性表是有限个数据元素构成的。
  • 线性表中数据元素与位置相关，即每个数据元素有唯一的序号。

咱们的线性表需要如下的方法：

createList(a[])：由整数数组a中的全部元素建立线性表的相应存储结构。
add(e)：将元素e添加到线性表末尾。
getLength()：求线性表的长度。
getElem(i)：求线性表中序号为i的元素。
setElem(i, e)：设置线性表中序号i的元素值为e。
getNo(e)：求线性表中第一个值为e的元素的序号。
insert(i, e)：在线性表中插入数据元素e作为第i个元素。
delete(i)：在线性表中删除第i个数据元素。
dispList()：输出线性表的所有元素。

顺序表

顺序表是线性表中的顺序存储结构，通常是一段连续的空间。

const initCap = 5
type SqList struct {
	data []int
	capacity int
	length int
}

方法

构造函数(伪)

func NewSqList() SqList {
    return SqList{
        data:     make([]interface{}, initCap),//用切片将就着吧
        capacity: initCap,
        Length:   0,
    }
}

重新调整容量

其实是多此一举

func (list *SqList) reCap(newCap int) {
    if newCap <= 0 {
        return
    }
    list.capacity = newCap
    var newData = make([]interface{}, newCap)
    for i := 0; i < list.Length; i++ {
        newData[i] = list.data[i]
    }
    list.data = newData
}

建表

func (list *SqList) CreateList(a []interface{}, n int) {
    for i := 0; i < n; i++ {
        if list.Length == list.capacity {
            list.reCap(2 * list.Length)
        }
        list.data[list.Length] = a[i]
        list.Length++
    }
}

添加元素

func (list *SqList) Add(e interface{}) {
    if list.Length == list.capacity {
        list.reCap(2 * list.Length)
    }
    list.data[list.Length] = e
    list.Length++
}

修改元素

func (list *SqList) SetElem(i int, e interface{}) bool {
    if i <= 0 || i >= list.Length {
        return false
    }
    list.data[i] = e
    return true
}

查找

func (list *SqList) GetNo(e interface{}) int {
    for i := 0; i < list.Length; i++ {
        if list.data[i] == e {
            return i
        }
    }
    return -1
}

插入

func (list *SqList) Insert(i int, e interface{}) bool {
    if i <= 0 || i >= list.Length {
        return false
    }
    if list.Length == list.capacity {
        list.reCap(2 * list.Length)
    }
    for j := list.Length; j > i; j-- {
        list.data[j] = list.data[j-1]
    }
    list.data[i] = e
    list.Length++
    return true
}

删除

func (list *SqList) Delete(i int) bool {
    if i <= 0 || i >= list.Length {
        return false
    }
    for j := i; j < list.Length-1; j++ {
        list.data[j] = list.data[j+1]
    }
    list.Length--
    if list.capacity > initCap && list.Length <= list.capacity/4 {
        list.reCap(list.capacity / 2)
    }
    return true
}

打印

func (list *SqList) DispList() {
    fmt.Print("顺序表内容是:[")
    for i := 0; i < list.Length-1; i++ {
        fmt.Print(list.data[i], ",")
    }
    fmt.Print(list.data[list.Length-1], "]\n")
}

链表

链表是线性表的链式存储结构，这边就实现一个单链表好了

  • 结点

    type LinkNode struct {
	data interface{}
	next *LinkNode
}

  • 链表

    type LinkList struct {
	head   *LinkNode
	tail   *LinkNode
	length int
}

方法

构造函数（伪）

  • 结点

    func NewLinkNode() *LinkNode {
	return &LinkNode{
		next: nil,
	}
}
func NewLinkNodeWithData(d interface{}) *LinkNode {
	return &LinkNode{
		data: d,
		next: nil,
	}
}

  • 链表

    func NewLinkList() *LinkList {
	return &LinkList{
		head:   NewLinkNode(),
		tail:   NewLinkNode(),
		length: 0,
	}
}

建表

  • 头插法

    // CreateListF 头插法建表
func (l *LinkList) CreateListF(a []interface{}, n int) {
	for i := 0; i < n; i++ {
		l.Insert(0, a[i])
	}
}

  • 尾插法

    // CreateListR 尾插法建表
func (l *LinkList) CreateListR(a []interface{}, n int) {
	for i := 0; i < n; i++ {
		l.Insert(i, a[i])
	}
}

插入

// Insert 在第i个位置插入元素
func (l *LinkList) Insert(i int, e interface{}) bool {
	if i < 0 {
		return false
	}
	s := NewLinkNodeWithData(e)
	p := l.GetI(i - 1)
	if p != nil {
		s.next = p.next
		p.next = s
		if s.next == nil {
			l.tail = s
		}
		l.length++
		return true
	} else {
		return false
	}
}

返回第i个元素

// GetI 返回第i个元素
func (l *LinkList) GetI(i int) *LinkNode {
	p := l.head
	for j := -1; j < i && p != nil; j++ {
		p = p.next
	}
	return p
}

打印

func (l *LinkList) DispList() {
	p := l.head.next
	for p != nil {
		fmt.Print(p.data, " ")
		p = p.next
	}
	fmt.Println()
}

删除

// Delete 在单链表中删除序号i位置的结点
func (l *LinkList) Delete(i int) bool {
	if i < 0 {
		return false
	}
	p := l.GetI(i - 1)
	if p != nil {
		q := p.next
		if q != nil {
			p.next = q.next
			q = nil
			l.length--
			return true
		} else {
			return false
		}
	} else {
		return false
	}
}

修改元素

// SetElem 设置序号i的结点值
func (l *LinkList) SetElem(i int, e interface{}) bool {
	if i < 0 {
		return false
	}
	p := l.GetI(i)
	if p != nil {
		p.data = e
		return true
	}
	return false
}

查找

// GetNo 查找第一个为e的元素的序号
func (l *LinkList) GetNo(e interface{}) int {
	no := 0
	p := l.head.next
	for p != nil && p.data != e {
		no++
		p = p.next
	}
	if p == nil {
		return -1
	}
	return no
}

添加元素

// Add 在末尾添加元素
func (l *LinkList) Add(e interface{}) {
	l.Insert(l.length, e)
}