1、绪论的思维导图

数据结构算法绪论.xmind
数据结构算法绪论.xmind

2、基本概念和术语

A.数据结构相关概念

数据**（Data）：是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素（Data Element）：是数据的基本单位，也称结点（Node）或记录（Record**）在程序中通常作为一个整体来进行考虑和处理。有时，一个数据元素可由若干数据项组成。
一个**数据元素可由若干个数据项（Data Item）组成。数据项（也称域[field]）是数据的不可分割的最小单位。是数据记录中最基本的，不可分割的数据单位。
数据对象（Data Object**）：是性质相同的数据元素的集合，是数据的一个子集。如字符集合Z={‘A’,’B’,’c’,…}。
数据结构**（Data Structure）：是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括3个方面：逻辑结构、存储结构和数据的运算。
逻辑结构是对数据之间关系的描述，与数据的存储结构无关。分为两大类：线性和非线性
数据元素之间的逻辑结构有四种基本类型：
①集合：结构中的数据元素除了“同属于一个集合”外，没有其他关系。
②线性结构：结构中的数据元素之间存在一对一的关系。
③树型结构：结构中的数据元素之间存在一对多的关系。
④图状结构或网状结构：结构中的数据元素之间存在多对多的关系。**

B.数据结构的定义形式：二元组

D**ata_Structure=（D，S）**

  • D**是数据元素的有限集**
  • S**是D上关系的有限集**

例：复数是一种数据结构
**Complex=(C, R)
 C={C1,C2}
R=**

C.数据结构的定义2

按某种逻辑关系**组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示 方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。具体来说，数据结构包含三个方面的内容，即数据的逻辑结构，数据的存储结构和对数据所施加的运算（操作）**

  • 数据的逻辑结构独立于计算机，是数据本身所固有的
  • 存储结构是逻辑结构在计算机存储器中的映像，必须依赖于计算机
  • 运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必须依赖于存贮结构

逻辑结构：集合、线性、树形、图
存储结构（Storge Structure):数据结构在计算机中的表示(或称映象）称为数据的存储结构，又称为物理结构
顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系
链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系
索引存储方法
散列存储方法

D.数据的逻辑结构与存储结构密切相关

算法设计 → 逻辑结构
算法实现 → 存储结构

E.抽象数据类型

抽象数据类型（ADT-Abstract Data Type）：是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。通常用（数据对象、数据关系、基本操作集）这样的三元组来表示抽象数据类型。

Q1：数据类型与抽象数据类型的区别？

数据类型：是一个值的集合和定义在该值上的一组操作的总称
抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）
它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）

Q2 ：抽象数据类型如何定义？

抽象数据类型可以用以下的三元组来表示：
ADT = （D[数据对象]，S[D上的关系集]，P[D上的操作集]）

ADT常用定义格式

ADT抽象数据类型名{
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作 ：<基本操作的定义>
} ADT抽象数据类型名

ADT Complex {
 数据对象：D＝{e1,e2｜e1,e2∈RealSet }
 数据关系：R1＝{ | e1是复数的实数部分| e2 是
复数的虚数部分 }
 基本操作：
 AssignComplex( &Z, v1, v2 )
 操作结果：构造复数 Z,其实部和虚部分别被赋以参数 v1
和 v2 的值
 DestroyComplex( &Z)
 操作结果：复数Z被销毁。
 GetReal( Z, &realPart )
 初始条件：复数已存在。
 操作结果：用realPart返回复数Z的实部值。
} ADT Complex**

ADT有两个重要特征

数据抽象：用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）
数据封装：将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节

3、数据结构的三要素

A.逻辑结构

数据的逻辑结构.xmind
数据的逻辑结构.xmind

B.存储结构

物理结构/存储结构：是数据的逻辑结构在计算机中的表示（又称映像）。
物理结构是描述数据具体在内存中的存储
数据结构中常见的4种存储方式：

1，顺序存储

顺序存储方法是存储结构类型中的一种，该方法是把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储结构称为顺序存储结构，通常顺序存储结构是借助于计算机程序设计语言（如C/C++）的数组来描述的。

2，链式存储

链式存储方法不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储结构表示称为链式存储结构，通常借助于计算机程序设计语言（如C/C++）的指针类型来描述它。

3，索引存储

索引存储方法在存储结点信息时除建立结点信息外，还建立附加的索引表来标识结点的地址。索引项的一般形式是<关键字，地址>，关键字标识唯一一个结点，地址作为指向结点的指针。

4，散列存储

散列存储方法的基本思想是根据结点的关键字通过散列函数直接计算出该结点的存储地址。这种存储方法本质上是顺序存储方法的扩展。

C.数据的运算

  1.  在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的操作步骤。<br />数据结构的主要运算包括：
  1. 建立（Create）一个数据结构；
  2. 消除（Destroy）一个数据结构；
  3. 从一个数据结构中删除（Delete）一个数据元素；
  4. 把一个数据元素插入（Insert）到一个数据结构中；
  5. 把一个数据结构进行访问（Access）；
  6. 对一个数据结构（中的数据元素）进行修改（Modify）；
  7. 对一个数据结构进行排序（Sort）；
  8. 对一个数据结构进行查找（Search）。

    4、算法

    算法是由基本运算及规定的运算顺序所构成的完成的解题步骤，或者看成按照要求设计好的有限的确切的计算序列。
    算法的五个特征：
    有穷性：指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一步在可接受的时间内完成。
    确定性：算法的每一步都具有确定的含义，不会出现二义性。
    可行性：算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。
    输入：一个算法有零个或多个输入。
    输出：一个算法有一个或多个输出。

    A.算法的评价

    一个算法可以用多种方法描述，主要有：使用自然语言描述；使用形式语言描述；使用计算机程序设计语言描述。
    算法和算法评价是两个不同的概念。一个计算机程序是对一个算法使用某种程序设计语言的具体体现。算法必须可终止意味着不是所有的计算机程序都是算法。
    评价一个好的算法有以下几个标准：
  • 正确性（Correctness）：算法应满足具体问题的需求
  • 可读性（Readability）：算法应容易满足供人阅读和交流。可读性好的算法有助于对算法的理解和修改。
  • 健壮性（Robustness）：算法应具有容错处理。当输入非法或错误数据时，算法应能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。

  • 通用性（Generality）：算法应具有一般性，即算法的处理结果对于一般的数据集合都成立。

    B.算法效率的度量

    算法效率的度量是通过时间复杂度和空间复杂度来描述的。
    算法效率：用依据该算法编制的程序在计算机上执行所消耗的时间来度量
    事后统计：利用计算机内记时功能，不同算法的程序可以用一组或多组相同的统计数据区分
    缺点

    • 必须先运行依据算法编制的程序
    • 所得时间统计量依赖于硬件、软件等环境 因素，掩盖算法本身的优劣

事前分析估计：一个高级语言程序在计算机上运行所消耗的时间取决于：

  • 依据的算法选用何种策略
  • 问题的规模
  • 程序语言
  • 编译程序产生机器代码质量

  • 机器执行指令速度

     **同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，———所以使用****绝对时间单位****衡量算法效率****不合适**<br />**从算法中选取一种对于所研究的问题来说是 ****基本操作**** 的原操作，以该基本操作 ****在算法中重复执行的次数**** 作为算法运行时间的衡量准则**<br />**通常它是最深层循环内的语句中的原操作**

1.时间复杂度

算法中基本操作重复执行的次数是问题规模n的某个函数，其时间度量记作T(n)=O(f(n))，称作算法的渐近时间复杂度（Asymptotic Time complexity），简称时间复杂度。
一般地，常用最深层循环内的语句中的原操作的执行频度（重复执行的次数）来表示。
“O”的定义：若f(n)是正整数n的一个函数，则O(f(n))表示 M≥0，使得当n≥n0时，|f(n)|≤M|f(n0)|。
表示时间复杂度的阶有：

  1. O(1)：常量时间阶
  2. O(n)：线性时间阶
  3. O(㏒ n)：对数时间阶
  4. O(n ㏒ n)：线性对数时间阶

定理：若A(n)=amnm+am-1nm-1+…+a1n+a0是一个m次多项式，则A(n)=O(nm)
最坏时间复杂度是指在最坏情况下，算法的时间复杂度。
平均时间复杂度是指所有可能输入实例在等概率出现的情况下，算法的期望运行时间。
最好时间复杂度是指在最好的情况下，算法的时间复杂度。
一般总是考虑在最坏的情况下的时间复杂度，以保证算法的运行时间不会比它更长，在分析一个程序的时间复杂性时，有以下两条规则：

  • 加法准则

T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))

  • 乘法准则

T(n)=T1(n)×T2(n)=O(f(n))×O(g(n))=O((f(n)×g(n)))
时间复杂度：算法的执行时间与原操作执行次数之和成正比。
常见的渐进式时间复杂度为：
O(1)<O(logn)<O(n)<O(nlogn)<O(n)<O(n)<O(2)<O(n!)<O(n)

2.空间复杂度

空间复杂度：算法的空间复杂度通过计算算法所需的存储空间实现。
算法原地工作是指算法所需辅助空间是常量，即O(1)。
空间复杂度（Space complexity）：是指算法编写成程序后，在计算机中运行时所需存储空间大小的度量。记作：S(n)=O(f(n))，其中：n为问题的规模（或大小），该存储空间一般包括三个方面：

  • 指令常数变量所占用的存储空间；
  • 输入数据所占用的存储空间；
  • 辅助（存储）空间。

一般地，算法的空间复杂度指的是辅助空间。
一维数组a[n]：空间复杂度O(n)
二维数组a[n][m]：空间复杂度O(n*m)

5、递归

程序对自身的调用，递归在计算机中是借助栈来实现的；
递归可以通过简单的函数调用来完成，如计算阶乘的程序在数学上可以定义为：
1、绪论 - 图1
斐波那契数列
0,1,1,2,3,5,8,13,21,34,55,89,144….依次类推下去，就会发现他后一个数等于前面两个数的和。
递归思想：一个数等于前面两个数的和。
递归表达式
1、绪论 - 图2

8、附录-练习题

1.数据的最小单位是（**A**）
A.数据项 B.数据类型 C.数据元素 D.数据变量
2.数据元素是数据的最小单元（**×**）
3.数据结构是（**D**）
A.一种数据类型 B.数据的存储结构 C.一组性质相同的数据元素的集合
D.相互之间存在一种或多种特定关系的数据元素的集合
4.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（**C**）
A.数据的处理方法 B.数据元素的类型
C.数据元素之间的关系 D.数据的存储方法
5.数据结构中，与所使用的计算机无关的是数据的（**C**）结构
A.存储 B.物理 C.逻辑 D.物理和存储
6.下列4种基本的逻辑结构中，数据元素之间关系最弱的是（**A**）
A.集合 B.线性结构 C.树形结构 D.图形结构
7.一个算法应该是（B）
A.程序 B.问题求解步骤的描述 C.要满足五个基本特征 D.A和C
8.某算法的时间复杂度为O(n2)，表明该算法的（C）
A.问题规模是n**2 B.执行时间等于n2 C.执行时间与n2**成正比 D.问题规模与n2成正比
9.以下算法的时间复杂度为（）

void fun(int n){
    int i = 1;
    while(i<=n)
        i = i*2;
}

A.O(n) B.O(n**2) C.O(nlog2n) D.O(log2**n)
解：i=i2 当i<=n时，i这边就为2*t次方，即2t <=n，t=log2n
10.下面程序片段的时间复杂度是（A）**

x = 2;
while( x<n/2 )
    x=2*x;

A.O(logn) B.O(n) C.O(nlogn) D.O(n)
11.下面程序段的时间复杂度为（C）

count = 0;
for(k=1;k<=n;k*=2)
    for(j=1;j<=n;j++)
        count++;

A.O(logn) B.O(n) C.O(nlogn) D.O(n)
解：两层for循环的时间复杂度进行相乘
k层的时间复杂度为：k=k2，则2*t**<=n，有t=log2n，
j层的时间复杂度为：n
则该程序片的时间复杂度为O(nlog**2**n)