社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
我学习数据结构和相关算法的原因是受到了阿里编程go语言测试题的刺激,话不多说,先上原题,这是19年4月份的题目,当时我还没学数据结构,然后就只能勉强取用数组模拟栈。
// 设计实现一个整数单链表类型 SingleListImpl, 实现如下接口定义 SingleList,
// 并添加适当的测试代码示例。
type SingleList interface {
// 打印链表, 用 "(", ")" 括起来, 元素之间用空格分割。如 "()" "(1 3 )" 等。
Print()
// 添加一个整数到链表头。
Push(n int)
// 将链表中的整数从小到大排序。自己实现排序,不要调用库函数,不要使用数组。
Sort()
}
package main
import (
"errors"
"fmt"
)
// 设计实现一个整数单链表类型 SingleListImpl, 实现如下接口定义 SingleList,
// 并添加适当的测试代码示例。
type SingleList interface {
// 打印链表, 用 "(", ")" 括起来, 元素之间用空格分割。如 "()" "(1 3 )" 等。
Print()
// 添加一个整数到链表头。
Push(n int)
// 将链表中的整数从小到大排序。自己实现排序,不要调用库函数,不要使用数组。
Sort()
}
type List struct {
array [5]int
front int
rear int
}
//用数组模拟了栈的实现
func (this *List) Push(val int) (err error) {
if this.rear == -1 {
return errors.New("list full")
}
this.array[this.rear] = val
this.rear --
return
}
//用冒泡排序对栈中元素进行排序
func (this *List) Sort() {
for i := 0; i < len(this.array); i++ {
for j := 0; j < len(this.array)-1-i;j++ {
if this.array[j] > this.array[j+1] {
this.array[j], this.array[j+1] = this.array[j+1], this.array[j]
}
}
}
}
//头疼打印法
func (this *List) Print(){
fmt.Print("(")
for i:=this.rear+1 ; i<=this.front;i++{
fmt.Printf("%d ",this.array[i])
}
fmt.Println(")")
}
//相关测试
func main() {
l:=&List{
front:4,
rear:4,
}
for i:=1;i<=5;i++{
err:=l.Push(i)
if err!=nil{
fmt.Println(err)
}
}
fmt.Println(l.array)
l.Sort()
fmt.Println(l.array)
l.Print()
}
但凡学过数据结构的链表实现,这题简直就是送分题。然后,我痛定思痛,开始学习数据结构和相关算法,并用go语言去描述。
相关代码寄托在github上,并持续保持更新,并欢迎大家对此作出补充。
github:https://github.com/WeilaScofield/DataStructure_Go
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!