【数据结构golang版】第二篇:线性表实现

今天用golang实现了线性表的基本操作。
注释还是很多,读的书是那一本《数据结构C语言版 严蔚敏》,上课的时候我就用的是这个。逻辑什么的都差不多,但是golang的代码全部自己写成的。下面上代码

package main

//线性表的相关算法实现
import (
	"fmt"
)

//定义List数据结构
type Element int64

const (
	MAX_SIZE = 10 //最大Size
	ERROR    = -1 //出错值
	NULL     = 0  //空值
)

type Sqlist struct {
	data   []Element //数据数组
	length int       //当前长度
	size   int       //最大size
}

//定义List的Interface,这里写出所有用到的方法
type Lister interface {
	//初始化构造一个线性表
	InitList(sl *Sqlist) bool
	//清空一个线性表
	ClearList(sl *Sqlist) bool
	//判断线性表是否为空
	IsListEmpty(sl *Sqlist) bool
	//判断线性表是否为满
	IsListFull(sl *Sqlist) bool
	//获取线性表长度
	Listlength(sl Sqlist) int
	//根据index获取数据
	GetData(sl Sqlist, index int) Element
	//根据数据返回index
	GetIndex(sl Sqlist, data Element) int
	//在index位置插入元素
	InsertList(sl *Sqlist, index int, data Element) bool
	//删除index的元素
	DeleteList(sl *Sqlist, index int) Element
	//遍历List
	TraverseList(sl *Sqlist) bool
}

//新建一个线性表
func InitList() Sqlist {
	var sl Sqlist
	sl.data = make([]Element, MAX_SIZE)
	sl.length = 0
	sl.size = MAX_SIZE
	return sl
}

//清空一个线性表
func ClearList(sl *Sqlist) bool {
	for i := 0; i < sl.size; i++ {
		sl.data[i] = NULL //全部都置空
	}
	return true
}

//判断线性表是否为空
func IsListEmpty(sl *Sqlist) bool {
	return sl.length == 0
}

//判断线性表是否为满
func IsListFull(sl *Sqlist) bool {
	return sl.length == MAX_SIZE
}

//获取线性表长度
func Listlength(sl Sqlist) int {
	return sl.length
}

//根据index获取数据
func GetData(sl *Sqlist, index int) Element {
	if index < 0 && index > MAX_SIZE {
		fmt.Println("please check index")
		return ERROR
	} else {
		return sl.data[index]
	}

}

//根据数据返回index
func GetIndex(sl *Sqlist, data Element) int {
	var index int = 0
	for i := 0; i < sl.length; i++ {
		if data == sl.data[i] {
			index = i
			break
		}
	}
	return index

}

//在index位置插入元素
/**
第一要判断index是否合法,然后判断index的位置,注意移动过程,最后要把length加1
**/
func InsertList(sl *Sqlist, index int, data Element) bool {
	if index < 0 && index > sl.length {
		fmt.Println("please check index")
		return false
	}
	if !IsListFull(sl) {
		if index == 0 && sl.length != 0 {
			for i := sl.length; i < 1; i-- {
				sl.data[i] = sl.data[i-1] //千万注意
			}
		} else if index > 0 && index < sl.length {
			for i := sl.length; i < index; i-- {
				sl.data[i] = sl.data[i-1] //注意这一块儿
			}
		} else if index > sl.length {
			fmt.Println("beyoug length")
			return false
		}
		sl.data[index] = data
		sl.length++
		return true
	} else {
		fmt.Println("list is full")
		return false
	}
}

//删除index的元素
/**
第一要判断index是否合法,然后判断index的位置,注意移位的时候要想清楚怎么移动,最后要把length减一
**/
func DeleteList(sl *Sqlist, index int) Element {
	if index < 0 && index > sl.length {
		fmt.Println("please check index")
		return ERROR
	}
	if !IsListEmpty(sl) {
		var data Element = sl.data[index]
		if index == 0 {
			for i := 0; i < sl.length; i++ {
				sl.data[i] = sl.data[i+1] //注意这个
			}
		}
		if index > 0 && index < sl.length {
			for i := index; i < sl.length-1; i++ {
				sl.data[i] = sl.data[i+1] //要注意
			}
		}
		sl.data[sl.length-1] = NULL
		sl.length--
		return data

	} else {
		fmt.Println("list is empty!")
		return ERROR
	}
}

//遍历List
func TraverseList(sl *Sqlist) bool {
	for i := 0; i < sl.length; i++ {
		fmt.Println(sl.data[i])
	}
	return true
}
func main() {
	list := InitList()
	fmt.Println(list.length)
	for i := 0; i < MAX_SIZE; i++ {
		InsertList(&list, i, Element(i*100))
	}
	TraverseList(&list)
	DeleteList(&list, 4)
	fmt.Println(list.data)
	fmt.Println(GetData(&list, 0))
	fmt.Println(GetIndex(&list, 600))
	ClearList(&list)
}

我尽量每天写一点儿数据结构的东西吧,虽然简单,但写起来还是不那么简单的。归根到底还是不熟悉。
自己给自己加油!

刘凯宁@C2P
20140812

Share