当前位置：首页 > news >正文

go专业数据结构与算法

news 2025/7/23 23:10:50

go语言之专业数据结构与算法

2.数组概念
3.golang实现数组结构
4.golang实现数组迭代器
5.数组栈的高级实现
6.栈模拟低级递归
7.斐波那契数列栈模拟递归
8.递归实现文件夹遍历
9.栈模拟文件递归
10.层级展示文件夹
11.数组队列的实现
12.队列实现遍历文件夹
13.循环队列
14.链式栈
15.链式队列
16.作业
17.为什么需要排序与查找
18.选择排序
19.字符串比较大小
20.字符串选择排序
21.插入排序
22.冒泡排序
23.堆排序
24.快速排序
25.奇偶排序
26.归并排序
27.希尔排序
28.基数排序
29.统计次数排序
30.鸡尾酒
31.数据提取
32.数据排序时间
33.数据的内存搜索
34.数据的结构体数组内存模型查找
35.数据的map内存模型
36.快速排序编程实现
37.二分查找法
38.二分查找与快速排序用于数据搜索
39.内容说明
40.二分查找法
41.顺序搜索数据
42.快速排序与二分查找在数据搜索实战
43.QQ数据的快速排序与二分查找
44.改良版快速排序
45.QQ的数据20秒排序完一个亿
46.性能调优中值搜索
47.斐波那契查找
48.二分查找变形写法
49.gnomesort
50.查询第N大的QQ
51.休眠排序
52.希尔排序改良梳子排序
53.木桶排序
54.三分查找
55.哈希表原理
56.set结构
57.作业

3.golang实现数组结构

code\ArrayList\ArrayList.go

package ArrayListimport ("errors""fmt"
)// 接口
type List interface {Size() int                                  // 数组大小Get(index int) (interface{}, error)         // 抓取第几个元素Set(index int, newval interface{}) error    // 修改数据Insert(index int, newval interface{}) error // 插入数据Append(newval interface{})                  // 追加Clear()                                     // 清空Delete(index int) error                     // 删除String() string                             // 返回字符串
}// 数据结构，字符串，整数，实数
type ArrayList struct {dataStore []interface{} // 数组存储TheSize   int           // 数组的大小
}func NewArrayList() *ArrayList {list := new(ArrayList)                      // 初始化结构体list.dataStore = make([]interface{}, 0, 10) // 开辟空间10个list.TheSize = 0return list
}func (list *ArrayList) Size() int {return list.TheSize // 返回数据大小
}func (list *ArrayList) Append(newval interface{}) {list.dataStore = append(list.dataStore, newval) // 叠加数据list.TheSize++
}func (list *ArrayList) Get(index int) (interface{}, error) { // 抓取第几个元素if index < 0 || index > list.TheSize {return nil, errors.New("索引越界")}return list.dataStore[index], nil
}func (list *ArrayList) String() string {return fmt.Sprint(list.dataStore)
}

调用ArrayList.go

code\main.go

package mainimport ("fmt""./ArrayList"
)func main() {list := ArrayList.NewArrayList()list.Append(1)list.Append(2)list.Append(3)fmt.Println(list)
}

package mainimport ("fmt""./ArrayList"
)func main1() {list := ArrayList.NewArrayList()list.Append(1)list.Append(2)list.Append(3)fmt.Println(list)
}func main2() {list := ArrayList.NewArrayList()list.Append("a1")list.Append("b2")list.Append("c3")fmt.Println(list.TheSize) //TheSize大写包外可见
}func main() {var list ArrayList.List = ArrayList.NewArrayList()list.Append("a1")list.Append("b2")list.Append("c3")fmt.Println(list.Size) //Size大写包外可见
}

var list ArrayList.List = ArrayList.NewArrayList() 无法编译，由于接口中的方法没有都实现。

package ArrayListimport ("errors""fmt"
)// 接口
type List interface {Size() int                                  // 数组大小Get(index int) (interface{}, error)         // 抓取第几个元素Set(index int, newval interface{}) error    // 修改数据Insert(index int, newval interface{}) error // 插入数据Append(newval interface{})                  // 追加Clear()                                     // 清空Delete(index int) error                     // 删除String() string                             // 返回字符串
}// 数据结构，字符串，整数，实数
type ArrayList struct {dataStore []interface{} // 数组存储TheSize   int           // 数组的大小
}func NewArrayList() *ArrayList {list := new(ArrayList)                      // 初始化结构体list.dataStore = make([]interface{}, 0, 10) // 开辟空间10个list.TheSize = 0return list
}// 数组大小
func (list *ArrayList) Size() int {return list.TheSize // 返回数据大小
}// 追加
func (list *ArrayList) Append(newval interface{}) {list.dataStore = append(list.dataStore, newval) // 叠加数据list.TheSize++
}// 抓取第几个元素
func (list *ArrayList) Get(index int) (interface{}, error) {if index < 0 || index > list.TheSize {return nil, errors.New("索引越界")}return list.dataStore[index], nil
}// 返回字符串
func (list *ArrayList) String() string {return fmt.Sprint(list.dataStore)
}// 修改数据
func (list *ArrayList) Set(index int, newval interface{}) error {return nil
}// 插入数据
func (list *ArrayList) Insert(index int, newval interface{}) error {return nil
}// 清空
func (list *ArrayList) Clear() {}// 删除
func (list *ArrayList) Delete(index int) error {return nil
}

现在编译没有问题

func main() {// 定义接口对象，赋值的对象必须实现接口的所有方法var list ArrayList.List = ArrayList.NewArrayList()list.Append("a1")list.Append("b2")list.Append("c3")fmt.Println(list.Size) //TheSize大写包外可见
}

package ArrayListimport ("errors""fmt"
)// 接口
type List interface {Size() int                                  // 数组大小Get(index int) (interface{}, error)         // 抓取第几个元素Set(index int, newval interface{}) error    // 修改数据Insert(index int, newval interface{}) error // 插入数据Append(newval interface{})                  // 追加Clear()                                     // 清空Delete(index int) error                     // 删除String() string                             // 返回字符串
}// 数据结构，字符串，整数，实数
type ArrayList struct {dataStore []interface{} // 数组存储TheSize   int           // 数组的大小
}func NewArrayList() *ArrayList {list := new(ArrayList)                      // 初始化结构体list.dataStore = make([]interface{}, 0, 10) // 开辟空间10个list.TheSize = 0return list
}func (list *ArrayList) checkisFull() {if list.TheSize == cap(list.dataStore) { // 判断内存使用newdataStore := make([]interface{}, 0, 2*list.TheSize) // 开辟双倍内存copy(newdataStore, list.dataStore)                     // 拷贝list.dataStore = newdataStore                          // 赋值}
}// 数组大小
func (list *ArrayList) Size() int {return list.TheSize // 返回数据大小
}// 追加
func (list *ArrayList) Append(newval interface{}) {list.dataStore = append(list.dataStore, newval) // 叠加数据list.TheSize++
}// 抓取第几个元素
func (list *ArrayList) Get(index int) (interface{}, error) {if index < 0 || index > list.TheSize {return nil, errors.New("索引越界")}return list.dataStore[index], nil
}// 返回字符串
func (list *ArrayList) String() string {return fmt.Sprint(list.dataStore)
}// 修改数据
func (list *ArrayList) Set(index int, newval interface{}) error {if index < 0 || index > list.TheSize {return errors.New("索引越界")}list.dataStore[index] = newval // 数据设置return nil
}// 插入数据
func (list *ArrayList) Insert(index int, newval interface{}) error {if index < 0 || index > list.TheSize {return errors.New("索引越界")}list.checkisFull()                               // 检查内存，如果满了，自动追加list.dataStore = list.dataStore[:list.TheSize+1] // 插入数据，内存移动一位for i := list.TheSize; i > index; i-- {          // 从后往前移动list.dataStore[i] = list.dataStore[i-1]}list.dataStore[index] = newval // 插入数据list.TheSize++                 // 索引追加return nil
}// 清空
func (list *ArrayList) Clear() {// 把原先的内存废弃，重写开辟内存list.dataStore = make([]interface{}, 0, 10) // 开辟空间10个list.TheSize = 0
}// 删除
func (list *ArrayList) Delete(index int) error {// 重写叠加，跳过indexlist.dataStore = append(list.dataStore[:index], list.dataStore[index+1:]...)list.TheSize--return nil
}

测试

func main() {// 定义接口对象，赋值的对象必须实现接口的所有方法var list ArrayList.List = ArrayList.NewArrayList()list.Append("a1")list.Append("b2")list.Append("c3")for i := 0; i < 10; i++ {list.Insert(1, "x5")fmt.Println(list) }fmt.Println(list) 
}

内存失效

func main() {// 定义接口对象，赋值的对象必须实现接口的所有方法var list ArrayList.List = ArrayList.NewArrayList()list.Append("a1")list.Append("b2")list.Append("c3")for i := 0; i < 4; i++ {list.Insert(1, "x5")fmt.Println(list)}fmt.Println("delete")list.Delete(5)fmt.Println(list)
}

func main() {// 定义接口对象，赋值的对象必须实现接口的所有方法var list ArrayList.List = ArrayList.NewArrayList()list.Append("a1")list.Append("b2")list.Append("c3")for i := 0; i < 15; i++ {list.Insert(1, "x5")fmt.Println(list)}// fmt.Println(list)
}

优化接口的插入方法，checkisFull方法

func (list *ArrayList) checkisFull() {if list.TheSize == cap(list.dataStore) { // 判断内存使用fmt.Println("A", list.dataStore)newdataStore := make([]interface{}, 0, 2*list.TheSize) // 开辟双倍内存copy(newdataStore, list.dataStore)                     // 拷贝list.dataStore = newdataStore                          // 赋值fmt.Println("A", list.dataStore)fmt.Println("A", newdataStore)}
}

func (list *ArrayList) checkisFull() {if list.TheSize == cap(list.dataStore) { // 判断内存使用fmt.Println("A", list.dataStore)newdataStore := make([]interface{}, 0, 2*list.TheSize) // 开辟双倍内存// copy(newdataStore, list.dataStore)                     // 拷贝// 使用for循环赋值for i := 0; i < len(list.dataStore); i++ {newdataStore[i] = list.dataStore[i]}list.dataStore = newdataStore // 赋值fmt.Println("A", list.dataStore)fmt.Println("A", newdataStore)}
}

newdataStore := make([]interface{}, 0, 2*list.TheSize)

0导致并没有开辟内存，

newdataStore := make([]interface{}, 2*list.TheSize, 2*list.TheSize)

func (list *ArrayList) checkisFull() {if list.TheSize == cap(list.dataStore) { // 判断内存使用fmt.Println("A", list.dataStore)// make 中间的参数，0，没有开辟内存newdataStore := make([]interface{}, 2*list.TheSize, 2*list.TheSize) // 开辟双倍内存copy(newdataStore, list.dataStore)                     // 拷贝// 使用for循环赋值// for i := 0; i < len(list.dataStore); i++ {//	 newdataStore[i] = list.dataStore[i]// }list.dataStore = newdataStore // 赋值fmt.Println("A", list.dataStore)fmt.Println("A", newdataStore)}
}

4.golang实现数组迭代器

code\ArrayList\ArrayListIterator.go

package ArrayListimport "errors"type Iterator interface {HasNext() bool              // 是否有下一个Next() (interface{}, error) // 下一个Remove()                    // 删除GetIndex() int              // 得到索引
}type Iterable interface {Iterator() Iterator // 构造初始化接口
}// 构造指针访问数组
type ArraylistIterator struct {list         *ArrayList // 数组指针currentindex int        // 当前索引
}func (list *ArrayList) Iterator() Iterator {it := new(ArraylistIterator)it.currentindex = 0it.list = listreturn it
}func (it *ArraylistIterator) HasNext() bool {return it.currentindex < it.list.TheSize // 是否有下一个
}func (it *ArraylistIterator) Next() (interface{}, error) {if !it.HasNext() {return nil, errors.New("没有下一个")}value, err := it.list.Get(it.currentindex) // 抓取当前数据it.currentindex++return value, err
}func (it *ArraylistIterator) Remove() {it.currentindex--it.list.Delete(it.currentindex) // 删除一个元素
}func (it *ArraylistIterator) GetIndex() int {return it.currentindex
}

D:\Workspace\Go\src\projects\code\ArrayList\ArrayList.go

package ArrayListimport ("errors""fmt"
)// 接口
type List interface {Size() int                                  // 数组大小Get(index int) (interface{}, error)         // 抓取第几个元素Set(index int, newval interface{}) error    // 修改数据Insert(index int, newval interface{}) error // 插入数据Append(newval interface{})                  // 追加Clear()                                     // 清空Delete(index int) error                     // 删除String() string                             // 返回字符串Iterator() Iterator
}// 数据结构，字符串，整数，实数
type ArrayList struct {dataStore []interface{} // 数组存储TheSize   int           // 数组的大小
}func NewArrayList() *ArrayList {list := new(ArrayList)                      // 初始化结构体list.dataStore = make([]interface{}, 0, 10) // 开辟空间10个list.TheSize = 0return list
}func (list *ArrayList) checkisFull() {if list.TheSize == cap(list.dataStore) { // 判断内存使用fmt.Println("A", list.dataStore)// make 中间的参数，0，没有开辟内存newdataStore := make([]interface{}, 2*list.TheSize, 2*list.TheSize) // 开辟双倍内存copy(newdataStore, list.dataStore)                                  // 拷贝// 使用for循环赋值// for i := 0; i < len(list.dataStore); i++ {// 	newdataStore[i] = list.dataStore[i]// }list.dataStore = newdataStore // 赋值fmt.Println("A", list.dataStore)fmt.Println("A", newdataStore)}
}// 数组大小
func (list *ArrayList) Size() int {return list.TheSize // 返回数据大小
}// 追加
func (list *ArrayList) Append(newval interface{}) {list.dataStore = append(list.dataStore, newval) // 叠加数据list.TheSize++
}// 抓取第几个元素
func (list *ArrayList) Get(index int) (interface{}, error) {if index < 0 || index > list.TheSize {return nil, errors.New("索引越界")}return list.dataStore[index], nil
}// 返回字符串
func (list *ArrayList) String() string {return fmt.Sprint(list.dataStore)
}// 修改数据
func (list *ArrayList) Set(index int, newval interface{}) error {if index < 0 || index > list.TheSize {return errors.New("索引越界")}list.dataStore[index] = newval // 数据设置return nil
}// 插入数据
func (list *ArrayList) Insert(index int, newval interface{}) error {if index < 0 || index > list.TheSize {return errors.New("索引越界")}list.checkisFull()                               // 检查内存，如果满了，自动追加list.dataStore = list.dataStore[:list.TheSize+1] // 插入数据，内存移动一位for i := list.TheSize; i > index; i-- {          // 从后往前移动list.dataStore[i] = list.dataStore[i-1]}list.dataStore[index] = newval // 插入数据list.TheSize++                 // 索引追加return nil
}// 清空
func (list *ArrayList) Clear() {// 把原先的内存废弃，重写开辟内存list.dataStore = make([]interface{}, 0, 10) // 开辟空间10个list.TheSize = 0
}// 删除
func (list *ArrayList) Delete(index int) error {// 重写叠加，跳过indexlist.dataStore = append(list.dataStore[:index], list.dataStore[index+1:]...)list.TheSize--return nil
}