例 1：如何在书架上摆放图书？
图书的摆放要使得2个相关操作方便实现：
-
操作1：新书怎么插入？
-
操作2：怎么找到某本指定的书？
-
方法1：随便放
-
插入：很方便
-
查找：效率极低
-
-
方法2：按照书名的拼音字母顺序排放
-
插入：二分查找确定位置后插入，书多了之后插入会很困难
-
查找：二分查找
-
-
方法3：把书架划分成几块区域，每块区域指定摆放某种类别的图书；在每种类别内，按照书名的拼音字母顺序排放
-
先定类别，二分查找确定位置，移出空位
-
先定类别，再二分查找
-
问题：空间如何分配？类别应该分多细？
-
可能造成空间的浪费
-
结论：
解决问题方法的效率，跟数据的组织方式有关
例 2：写程序实现一个函数PrintN，使得传入一个正整数为N的参数后，能顺序打印从1 到 N的全部正整数
循环实现：
public void printN1(int n) {
for (int i = 1; i <= n; i++) {
System.out.println(i);
}
}
递归实现：
public void printN2(int n) {
if (n > 0) {
printN2(n - 1);
System.out.println(n);
}
}
递归方式，当n逐渐变大时，可能导致内存空间不足
结论：
解决问题方法的效率，跟空间的利用效率有关
例 3：写程序计算给定多项式在给定点x处的值
直接法：
/**
* 乘方
*
* @param n [0,n]
* @param a 数组
* @param x 系数
* @return
*/
double f1(int n, double[] a, double x) {
int i;
double p = a[0];
for (i = 1; i <= n; i++) {
p += (a[i] * Math.pow(x, i));
}
return p;
}
秦九韶法：
/**
* 分解成乘法
*
* @param n [0,n]
* @param a 数组
* @param x 系数
* @return
*/
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;
}
经过多次调用测试，第二种方式相比第一种方式，执行更快，运行时间更短
结论：
解决问题方法的效率，跟算法的巧妙程度有关
所以到底什么是数据结构？？？
-
即使解决一个非常简单的问题，往往也有多种方法，且不同方法之间的效率可能相差甚远
-
解决问题方法的效率
-
跟数据的组织方式有关（如例1）
-
跟空间的利用效率有关（如例2）
-
跟算法的巧妙程度有关（如例3）
-
-
数据对象 在计算机中的组织方式
-
例1中的图书
-
逻辑结构：分为线性、树、图
-
物理存储结构：顺序存储、链式存储
-
-
数据对象必定与一系列加在其上的 操作 相关联
- 例1中图书的查找、插入
-
完成这些操作所用的方法就是 算法
- 例3中的直接法、秦九韶法
抽象数据类型（Abstract Data Type）
-
数据类型
-
数据对象集
-
数据集合相关联的操作集
-
-
抽象：描述数据类型的方法不依赖于具体实现
-
与存放数据的机器无关
-
与数据存储的物理结构无关
-
与实现操作的算法和编程语言均无关
-
只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题
例 4 ： “矩阵”的抽象数据类型定义
-
类型名称：矩阵（Matrix）
-
数据对象集：一个 \(M* N\) 的矩阵 \(A_{M*N} = (a_{ij}) (i=1, …, M; j=1, …, N )\) 由 \(M* N\) 个三元组 \(< a, i, j >\) 构成，其中 a 是矩阵元素的值，i 是元素所在的行号，j是元素所在的列号。
-
操作集：对于任意矩阵 $A、B、C \epsilon Matrix $ ，以及整数i 、 j 、 M 、 N
-
Matrix Create( int M, int N )：返回一个M*N的空矩阵； -
int GetMaxRow( Matrix A )：返回矩阵A的总行数； -
int GetMaxCol( Matrix A )：返回矩阵A的总列数； -
int GetMaxCol( Matrix A )：返回矩阵A的总列数； -
ElementType GetEntry( Matrix A, int i, int j )：返回矩阵 A的第i行、第j列的元素； -
Matrix Add( Matrix A, Matrix B )：如果A 和 B的行、列数一致，则返回矩阵C=A+B，否则返回错误标志； -
Matrix Multiply( Matrix A, Matrix B )：如果A的列数等于B的行数，则返回矩阵C=AB，否则返回错误标志； -
……
-