网易云课堂-数据结构-第一讲-基本概念

1.1什么是数据结构

数据对象在计算机中的组织方式

逻辑结构（eg，一对一——线性结构、一对多——树，多对多——图）

物理存储结构（eg，在机器内存里的存放方式：链表还是数组）

数据对象必定与一系列加在其上的操作相关联

完成这些操作所用的方法就是算法

抽象数据类型（Abstract Data Type）

数据类型

数据对象集

数据集合相关联的操作集

抽象：描述数据类型的方法不依赖于具体实现

与存放数据的机器无关

与数据存储的物理结构无关

与实现操作的算法和编程语言均无关

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

例4：“矩阵”的抽象数据类型定义

类型名称：矩阵（Matrix）

数据对象集：一个M×N的矩阵……由M×N个三元组< a , i , j >构成，其中a是矩阵元素的值，i是元素所在的行号，j是元素所在的列号。

操作集：对于任意矩阵A、B、C∈Matrix，以及整数i、j、M、N

Matrix Create（int M，int N）：返回一个M×N的空矩阵；

int GetMaxRow（Matrix A）：返回矩阵A的总行数；

int GetMaxCol（Matrix A）：返回矩阵A的总列数；

Element Type GetEntry（Matrix A，int i，int j）：返回矩阵A的第i行、第j列的元素；

Matrix Add（Matrix A，MatrixB）：如果A和B的行、列数一致，则返回矩阵C=A+B，否则返回错误标志；

MatrixMultiply（Matrix A，MatrixB）：如果A的列数等于B的行数，则返回矩阵C=AB，否则返回错误标志；

……

/*-- 抽象一下，不管具体是怎么实现的，避免了狭隘的定义，通用性更强。--*/

/*《计算机概论》：抽象让我们学会更高层次地看问题，从而将事物的本质表现出来，而将其中的细节隐藏起来；它让我们更有效地使用时间和大脑；它让我们分析问题时不至于陷入泥潭*/

/*复杂问题简单化；同类问题同质化；相同情况复用化*/

1.2什么是算法

算法（Algorithm）

一个有限指令集

接受一些输入（有些情况下不需要输入）

产生输出

一定在有限步骤之后终止

每一条指令必须

有充分明确的目标，不可以有歧义

计算机能处理的范围之内

描述应不依赖于任何一种计算机语言以及具体的实现手段

例1：选择排序法算法的伪码描述

void SelectionSort(int List[ ],int N)

{

/* 将N个整数List[0]……List[N-1]进行非递减排序*/

for(i = 0;i < N;i++)

{

MinPositon = ScanForMin(List,i,N-1);

/*从List[i]到List[N-1]中找最小元，并将其位置赋给MinPosition*/

Swap(List[i],List[MinPosition]);

/*将未排序部分的最小元换到有序部分的最后位置*/

}

}

抽象——

List到底是数组还是链表（虽然看上去很像数组）

Swap用函数还是宏去实现？

/*在描述算法时，不关心具体的实现细节*/

1.2什么是好的算法？

衡量算法的两个指标：

~

~

/*写成n的函数是因为，两个指标与要处理的数据的规模直接相关

1.1 例2：~

~

调用函数之前要把当前函数所有的现有的状态存到系统的内存中

1.1 例3：

~

~

每一次循环用~次乘法

n充分大的时候

在分析一般算法的效率时，我们经常关注下面两种复杂度

最坏情况复杂度Tworst(n)

平均复杂度Tavg(n)

Tavg(n)≤Tworst(n)

/*由于什么是平均很难下统一的定义，所以一般选择最坏情况复杂度来分析效率

二分法的伪码描述：

low = 0;

high = List.length - 1;

当low < high时

mid = (low + high)/2;

如果List[mid] < X

low = mid + 1;

如果List[mid] > X

high = mid - 1;

否则

返回mid

最坏时间复杂度为O(log2n)

空间复杂度为O(1)