1.1 什么是数据结构
1.1.1 关于数据组织
1. 定义：没有官方定义。
非官方定义：“数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”
Sartaj Sahni，《数据结构、算法与应用》
“数据结构是ADT（抽象数据类型 Abstract Data Type）的物理实现。”
Clifford A.Shaffer，《数据结构与算法分析》
“数据结构（data structure）是计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法。”
中文维基百科
关键词：数据结构、算法
例1：如何在书架上摆放图书？这个问题不科学
该问题需要考虑：新书怎么插入？怎么找到某本指定的书？
方法1：随便放！
1. 新书怎么插入？哪儿有空放哪儿
2. 怎么找到某本指定的书？累死
方法2：按照书名的拼音字母顺序排放
1. 新书怎么插入？累死
2. 怎么找到某本指定的书？二分查找
方法3：把书架划分成几块区域，每块区域指定拜访某种类别的图书；在某种类别内，按照书名的拼音字母顺序排放。
1. 新书怎么插入？先定类别，二分查找确定位置，移出空位
2. 怎么找到某本指定的书？先定类别，再二分查找
问题：空间如何分配？类别应该分多细？
（答案未给出）
1.1.2 关于空间使用
例2：写程序实现一个函数PrintN，使得传入一个正整数为N的参数后，能顺序打印从1到N的全部正整数
方法1（循环实现，推荐）：
void PrintN(int N) {
int i;
for (i = 1; i <= N; i++) {
printf("%d\n", i);
}
}
方法2（递归实现）：
void PrintN(int N) {
if (N) {
PrintN(N – 1);
printf("%d\n", N);
}
}
当N很小时，运行一切正常，但当N比较大的时候，例如：N=100000时，程序直接没有输出，这是因为递归实现在这里占用空间过大导致的。所以解决问题方法的效率，也跟空间的利用效率是有关的。
例2 测试程序：
#include <stdio.h>
void PrintN(int N);
int main() {
int n;
scanf("%d", &n);
PrintN(n);
return 0;
}
附赠：例2的Python源码实现：
方法1（循环实现，推荐）：
def PrintN(N):
for i in range(1, n + 1):
print(i)
方法2（递归实现）：
def PrintN(N):
if N:
PrintN(N – 1)
print(N)
例2测试程序（Python 3）
n = eval(input())
PrintN(n)
1.1.3 关于算法效率
例3：写程序计算给定多项式在给定点x处的值
多项式：f(x) = a0 + a1x + ... + an – 1xn – 1 + anxn
最傻最直接的算法：
double f(int n, double a[], double x) {
int i;
double p = a[0];
for (i = 1; i <= n; i++) {
p += (a[i] * pow(x, i));
}
return p;
}
专业的程序员：
多项式定义：f(x) = a0 + x(a1 + x(...(an – 1 + x(an))...))
老祖宗：秦九韶
double f(int n, double a[], double x) {
int i;
double p = a[n];
for (i = n; i > 0; i--) {
p = a[i – 1] + x * p
}
return p;
}
知识点：C语言中clock()：捕捉从程序开始运行到clock()被调用时所耗费的时间。这个时间单位是clock tick，即“时钟打点”。
常数CLK_TCK：机器时钟每秒所走的时钟打点数。
常数CLK_TCK在不同的机器上可能不一样。
模板：
#include <stdio.h>
#include <time.h>
clock_t start, stop;
/* clock_t是clock()函数返回的变量类型 */
double duration;
/* 记录被测函数运行时间，以秒为单位 */
int main() {
/* 不在测试范围内的准备工作写在clock()调用之前 */
start = clock(); /* 开始计时 */
myFunction(); /* 把被测函数加在这里 */
stop = clock(); /* 停止计时 */
duration = ((double) (stop - start)) / CLK_TCK;
/* 其他不在测试范围的处理写在后面，例如输出duration的值 */
return 0;
}
问题：如何测出不到1个tick的程序运行时间？
答案：重复
例3完整程序：
#include <stdio.h>
#include <time.h>
#include <math.h>
clock_t start, stop;
double duration;
#define MAXN 10
#define MAXK 1e7
double f1(int n, double a[], double x) {
int i;
double p = a[0];
for (i = 1; i <= n; i++) {
p += (a[i] * pow(x, i));
}
return p;
}
double f2(int n, double a[], double x) {
int i;
double p = a[n];
for (i = n; i > 0; i--) {
p = a[i - 1] + x * p;
}
return p;
}
int main() {
int i;
double a[MAXN];
for (i = 0; i < MAXN; i++) {
a[i] = (double) i;
}
start = clock();
for (i = 0; i < MAXK; i++) {
f1(MAXN - 1, a, 1.1);
}
stop = clock();
duration = ((double) (stop - start)) / CLK_TCK / MAXK;
printf("%6.2e\n", duration);
start = clock();
for (i = 0; i < MAXK; i++) {
f2(MAXN - 1, a, 1.1);
}
stop = clock();
duration = ((double) (stop - start)) / CLK_TCK / MAXK;
printf("%6.2e\n", duration);
return 0;
}
本案例告诉我们：解决问题方法的效率，跟算法的巧妙程度有关。
Python代码：
最傻最直接的算法：
def f(n, a, x):
p = a[0]
for i in range(1, n + 1):
p += (a[i] * pow(x, i))
return p
专业的程序员：
def f(n, a, x):
p = a[n];
for i in range(1, n + 1):
p = a[i - 1] + x * p
return p
例3完整
import time as t
MAXN = 10
MAXK = 10000000
def f1(n, a, x):
p = a[0]
for i in range(1, n + 1):
p += (a[i] * pow(x, i))
return p
def f2(n, a, x):
p = a[n];
for i in range(n, 0, -1):
p = a[i - 1] + x * p
return p
a = [2, 3, 4, 5, 6, 7, 8, 10, 12, 16] # 随便写的
start = t.time_ns()
for i in range(MAXK):
f1(MAXN - 1, a, 1.1)
stop = t.time_ns()
duration = (stop - start) / MAXK
print(duration)
start = t.time_ns()
for i in range(MAXK):
f2(MAXN - 1, a, 1.1)
stop = t.time_ns()
duration = (stop - start) / MAXK
print(duration)
1.1.4 抽象数据类型
所以：到底什么是数据结构？
数据对象在计算机中的组织方式
逻辑结构：树、图
物理存储结构
数据对象必定与一系列加载其上的操作相关联
完成这些操作所用的方法叫做算法
抽象数据类型（Abstract Data Type）
数据类型：数据对象集、数据集合相关联的操作集
抽象：描述数据类型的方法不依赖于具体实现
与存放数据的机器无关
与数据存储的物理结构无关
与实现操作的算法和编程语言均无关
只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题。
