数据结构第一讲：基本概念（一）—

定义

数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。 —–Sartaj Sahni, 《数据结构、算法与应用》

数据结构是ADT(抽象数据类型Abstract Data Type)的物理实现 —–Cliffor A.Shaffer, 《数据结构与算法分析》

数据结构（data structure）是计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法。 —中文维基百科

例一：书架如何放书

方法一随便发

哪里有空放哪
找书是个噩梦

方法二按照书名的拼音字母顺序排放

操作一：新书怎么插入
- 如果书位置靠前，所有的书都要腾位置
操作二：怎么找到指定的某本书
- 二分查找

方法三把书架划分成几块区域，每块区域指定拜访某种类别的图书；在每种类别内，按照书名的拼英字母顺序排放

操作一：新书怎么插入
- 先定类别，二分查找确定位置，移出空位
操作二：怎么找到指定的某本书
- 先定类别，再二分查找
问题：每种书类的规模，类别大小

例一总结

解决问题方法的效率，跟数据的组织方式有关。

例二：写程序实现一个函数PrintN，是的传入一个正整数为N的参数后，能顺序打印从1到N的全部正整数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
// 循环实现
const PrintN = (N:number) => {
    for(let i = 1; i<=N; i++){
        console.log(i);
    }
}
//10万 正常打印

// 递归
const PrintN1 = (N: number) => {
    if(N) {
        PrintN1(N - 1);
        console.log(N);
    }
}
//10万 内存溢出

例二总结

解决问题方法的效率，跟空间的利用效率有关。

例三：写程序计算给定多项式在给定点X处的值

题目： $$ f(x) = a_0 +a_1x +…+ a_{n -1 }x^{n-1}+a_nx^n $$

1
2
3
4
5
6
7
const f = (n: number, a:number[], x:number) => {
    let p = a[0];
    for(let i = 1;i<=n;i++){
        p+=(a[i] * Math.pow(x,i));
    }
    return p;
}

转化为结合律 $$ f(x)=a_0+x(a_1 + x(…(a_{n-1}+x(a_n))…)) $$

1
2
3
4
5
6
7
const f = (n: number, a:number[], x:number) => {
    let p = a[n];
    for(i = n;i>0li--){
        p = a[i-1] + x*p;
    }
    return p;
}

例三总结

解决问题方法的效率，跟算法的巧妙程度有关。

到底什么是数据结构

数据对象在计算机中的组织方式
- 逻辑结构
- 物理存储结构
数据对象必定与一系列加在其上的操作相关联
完成这些操作所用的方法就是算法

抽象数据类型（Abstract Data Type）

数据类型
- 数据对象集
- 数据集合相关联的操作集
抽象：描述数据类型的方法不依赖于具体实现
- 与存放数据的机器无关
- 与数据存储的物理结构无关
- 与实现操作的算法和编程语言无关

只描述数据对象集合相关操作集是什么，并不涉及如何做到的问题

例四 `矩阵`的抽象数据类型定义

类型名称：矩阵（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 c Matrix, 以及整数i、j、M、N
- Matrix Create (int M, int N ):返回一个M×N的空矩阵；
- int GetMaxRow(Matrix A): 返回矩阵A的总行数；
- int GetMaxCol(Matrix A): 返回矩阵A的总列数；
- ElementType GetEntry(Matrix A, int i, init 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，否则返回错误标志；

定义