数据结构笔记（Go语言描述）1基本概念
说明
本文实际上是基于中国大学MOOC网中浙江大学陈越、何钦铭老师的国家精品课《数据结构》的笔记。课程中主要使用C来描述，但由于本人正在学习Go并且对Go语言很感兴趣，因此想要用Go来实现课程中的所有程序。
为什么需要研究数据结构
例1：图书馆如何存放书和查找书
启示：解决问题方法的效率，跟数据的组织方式有关。
例2：写程序实现一个函数PrintN，使得传入一个正整数为N的参数后，能顺序打印从1到N的全部正整数。
循环实现
func PrintN(N int) {
for i := 1; i <= N; i++ {
fmt.Println(i)
}
}
递归实现
func PrintN(N int) {
if N != 0 {
PrintN(N - 1)
fmt.Println(N)
}
}
运行结果显示，当使用循环实现时，即使输入N=10^7也就是一千万时都能正常运行，只是运行时间会比较久
但当我们使用递归调用时，如果输入N=一千万，会出现如下错误：
runtime: goroutine stack exceeds 1000000000-byte limit
runtime: sp=0xc0200e1370 stack=[0xc0200e0000, 0xc0400e0000]
fatal error: stack overflow
出现了数据溢出的情况。
启示：解决问题方法的效率，跟空间的利用效率有关。
例3：写程序计算给定多项式在给定点x处的值
f
(
x
)
=
a
0
+
a
1
x
+
.
.
.
+
a
n
−
1
x
n
−
1
+
a
n
x
n
f(x) = a_{0} + a_{1}x + ... + a_{n-1}x^{n-1}+a_{n}x^{n}
f(x)=a0+a1x+...+an−1xn−1+anxn
写出来会被笑话的方法
func f1(n int, a [MAXN]float64, x float64) {
p := a[0]
for i := 1; i <= n; i++ {
p += a[i] * math.Pow(x, float64(i))//这里使用了次方，一定会对运算效率有影响
}
}
比较聪明的方法
func f2(n int, a [MAXN]float64, x float64) {
p := a[n]
for i := n; i > 0; i-- {
p = p*x + a[i-1]
}
}
运行结果
package main
import (
"fmt"
"math"
"time"
)
const MAXN = 1e7
func main() {
var a [MAXN]float64
for i := 0; i < MAXN; i++ {
a[i] = float64(i)
}
start1 := time.Now().UnixNano()
f1(MAXN-1, a, 1.1)
end1 := time.Now().UnixNano()
fmt.Println("程序运行时间为", float64(end1-start1), "纳秒")
start2 := time.Now().UnixNano()
f2(MAXN-1, a, 1.1)
end2 := time.Now().UnixNano()
fmt.Println("程序运行时间为", float64(end2-start2), "纳秒")
}
程序运行时间为 1.1897897e+09 纳秒
程序运行时间为 4.78713e+07 纳秒
可以看到，第一种方法的运行时间比第二种方法要多出将近2个数量级。
启示：解决问题方法的效率，跟算法的巧妙程度有关。
到底什么是数据结构
【数据对象】在计算机中的组织方式
逻辑结构
物理存储结构
数据对象必定与一系列加在其上的【操作】相关联
完成这些操作所用的方法就是【算法】
抽象数据类型ADT
数据类型
数据对象集
数据集合相关联的操作集
抽象：描述数据类型的方法不依赖于具体实现
与存放数据的机器无关
与数据存储的物理结构无关
与实现操作的算法和编程语言均无关
只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题
例4：“矩阵矩阵”的抽象数据类型定义
类型名：Matrix
数据对象集：一个M×N的矩阵
A
m
∗
n
=
(
a
i
j
)
(
i
=
1
,
.
.
.
,
M
;
j
=
1
,
.
.
.
,
N
)
A_{m*n}=(a_{ij})(i=1,...,M;j=1,...,N)
Am∗n=(aij)(i=1,...,M;j=1,...,N)
由M×N个三元组<a,i,j>构成，其中a是矩阵元素的值，i是元素所在的行号，j是元素所在的列号。
type Matrix struct {
a float64
i, j int
}
操作集：
func NewMatrix(M int, N int) //返回一个M*N的空矩阵
func (A Matrix) GetMaxRow() int //返回矩阵A的总行数
func (A Matrix) GetMaxCol() int //返回矩阵A的总列数
func (A Matrix) GetEntry(i int, j int) float64//返回i行j列的元素
func Add(A Matrix, B Matrix) Matrix //如果A B同形则返回C=A+B，否则返回错误标志
func Multiply(A Matrix, B Matrix) Matrix //如果A的列数等于B的行数则返回C=AB，否则返回错误标志