这是一系列关于数据结构的笔记博客，为了练习自己的代码能力，咱将尽可能不使用 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, |
| } |
| } |
# 建表
-
头插法
| |
| func (l *LinkList) CreateListF(a []interface{}, n int) { |
| for i := 0; i < n; i++ { |
| l.Insert(0, a[i]) |
| } |
| } |
-
尾插法
| |
| func (l *LinkList) CreateListR(a []interface{}, n int) { |
| for i := 0; i < n; i++ { |
| l.Insert(i, a[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 个元素
| |
| 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() |
| } |
# 删除
| |
| 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 |
| } |
| } |
# 修改元素
| |
| 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 |
| } |
# 查找
| |
| 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 |
| } |
# 添加元素
| |
| func (l *LinkList) Add(e interface{}) { |
| l.Insert(l.length, e) |
| } |
