对于数据结构,官方没有统一概念,以下是三个经典著作中数据结构的定义

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

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

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

解决问题方法的效率,往往与数据的组织形式,跟空间的利用效率,跟算法的巧妙程度等等有关

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

  • 逻辑结构
  • 物理存储结构

数据对象必定与一系列加在其上的操作相关联,完成这些操作所用的方法就是算法
(数据结构研究逻辑结构和物理结构以及它们之间的相互关系,并对这种结构定义相适应的运算,设计出相应的算法)

抽象数据类型(Abstract Data Type)

  • 数据类型
  • 数据对象集(数据结构)
  • 数据集合相关联的操作集(数据结构对应的操作)
    1__数据结构、算法、抽象数据类型.png

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

  • 与存放的机器无关
  • 与数据存储的物理结构无关
  • 与实现操作的算法和编程语言均无关

只描述数据对象集和相关操作集“是什么”,并不涉及“如何做到”的问题(不考虑操作的具体实现,即不考虑算法)

例:矩阵的抽象数据类型定义
数据类型名:Matrix      (不考虑存储结构)
数据对象集:一个M*N的矩阵A=(Aij)(i=1,…,M;j=1,…,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的总列数;
ElamentType 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,否则返回错误标志

算法(Algorithm)

  • 有限指令集
  • 接受一些输入(有些情况下不需要输入)
  • 产生输出
  • 一定在有限步骤后停止
  • 每一条指令必须
  • 有充分明确的目标,不可以有歧义
  • 计算机能处理的范围之内
  • 描述应不依赖于任何一种计算机语言以及具体的实现手段
例:简单选择排序的伪代码描述
// 将N个整数List[0],…,List[N-1]进行非递减排序
void SelectionSort()
{
    for(i=0;i<N;i++)
    {
        //从List[i]到List[N-1]中选择最小元,并将其位置赋给MinPosition;
        MinPosition=ScanForMin(List,i,N-1);
        //将未排序的最小元换到有序部分的最后位置;
        Swap(List(i),List(MinPosition));
    }
}

伪代码的特点:抽象
———比如:上例中
List既可以用数组实现,又可以用函数实现
Swap既可以是函数实现,也可以是宏等方式实现

什么是好的算法?

  • 空间复杂度S(n)S(n)——根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。
    空间复杂度过高的算法可能导致内存超限,造成程序非正常中断。
  • 时间复杂度T(n)T(n)——根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模有关。
    时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。

分析一般算法的效率时,经常关注两种复杂度

  • 最坏情况复杂度Tworst(n)Tworst(n)
  • 平均复杂度Tavg(n)Tavg(n)
  • Tavg(n)<=Tworst(n)Tavg(n)<=Tworst(n)

复杂度的渐进表示法

  • T(n)=O(f(n))T(n)=O(f(n))表示存在常数C>0n0>0C>0,n_0>0使得当n>=n0n>=n_0时有T(n)<=Cf(n)T(n)<=C·f(n)
  • T(n)=Ω(g(n))T(n)=Ω(g(n))表示存在常数C>0n0>0C>0,n_0>0使得当n>=n0n>=n_0时有T(n)>=Cg(n)T(n)>=C·g(n)
  • T(n)=Θ(h(n))T(n)=Θ(h(n))表示同时有T(n)=O(h(n))T(n)=O(h(n))T(n)=Ω(h(n))T(n)=Ω(h(n))

若两段算法分别有复杂度T1(n)=O(f1(n))T_1(n)=O(f_1(n))T2(n)=O(f2(n))T_2(n)=O(f_2(n)),则

  • T1(n)+T2(n)=max(O(f1(n)),O(f2(n)))T_1(n)+T_2(n)=max(O(f_1(n)),O(f_2(n)))
  • T1(n)T2(n)=O(f1(n)f2(n))T_1(n)*T_2(n)=O(f_1(n)*f_2(n)) (类似于嵌套)
  • T(n)T(n)是关于n的k阶多项式,那么T(n)=Θ(nk)T(n)=Θ(n^k)
  • 一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度
  • if-else结构的复杂度取决于if的条件判断复杂度和两个分支部分的复杂度,总体复杂度取三者中最大