数据结构与算法基础

“程序=数据结构+算法”

——图灵奖获得者、Pascal语言之父Nicklaus Wirth

课程内容： this is a picture

1 绪论

1.1 数据结构研究内容

“计算机主要用千数值计算时，一般要经过如下几个步骤：首先从具体问题抽象出数学模型，然后设计一个解此数学模型的算法，最后编写程序，进行测试、调试，直到解决问题。”

实例1.线性表
- 操作==对象==：每位学生的信息（姓名，性别……）。
  
  操作==算法==：查询，插入，修改，删除等。
实例2.树结构
- 操作==对象==：各种棋局状态，即描述棋盘的格局信息。
  
  操作==算法==：走棋，使棋局状态发生变化。
实例3.图结构
- 操作==对象==：各地点及路的信息。
  
  操作==算法==：设置信号灯，求出各个可同时通行的路的集合。

“ 从上面三个实例可以看出，非数值计算问题的数学模型不再是数学方程，而是诸如==线性表、树和图的数据结构==。因此，简单地说，数据结构是一门研究==非数值计算==程序设计中的操作对象，以及这些对象之间的==关系==和==操作==的学科。“

1.2 基本概念和术语

1.2.1 数据、数据元素、数据项和数据对象

数据：各种符号的集合
- 数值型的数据：整数、实数等
- 非数值型的数据：文字、图像、图形、声音等
数据元素^a ：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理

学号姓名性别出生日期政治面貌

0001 陆宇男 1986/09/02 团员

0002 李明男 1985/12/25 党员

0003 汤晓影女 1986/03/26 团员

其中第二行整体为一个数据元素^a ,其中包含了五个数据项
数据项：构成数据元素的不可分割的最小单位
- 数据>数据元素>数据项
  - 例：学生表>个人记录>学号
数据对象：是性质相同的数据元素的集合，是数据的一个子集^b
- 例：字母字符数据对象是集合C= {‘A’,‘B’, …，‘Z’,‘a’,‘b’, …，‘z’}
数据元素和数据对象
- 数据元素与数据的关系：集合的个体
- 数据对象和数据的关系：集合的子集

学号	姓名	性别	出生日期	政治面貌
0001	陆宇	男	1986/09/02	团员
0002	李明	男	1985/12/25	党员
0003	汤晓影	女	1986/03/26	团员

1.2.2 数据结构

数据结构

数据元素之间的逻辑关系，也称为逻辑结构
数据元素及其关系在计算机存储器中的表示（又称为映像），称为数据的物理结构或数据的存储结构
数据的运算和实现，即对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现

逻辑结构
- 描述数据元素之间的逻辑关系
- 与数据的存储无关，独立于计算机
- 是从具体问题抽象出来的数学模型
物理结构（存储结构）
- 数据元素及其关系在计算机存储器中的结构（存储方式）
- 是数据结构在计算机中的表示
逻辑结构与存储结构的关系
- 存储结构是逻辑关系的映象与元素本身的映象
- 逻辑结构是数据结构的抽象，存储结构是数据结构的实现
- 两者综合起来建立了数据元素之间的结构关系
逻辑结构的种类
- 划分方法一——两类结构
  - （1）==线性结构== ：有且仅有一个开始和一个终端节点，并且所有结点都最多只有一个直接前趋和一个直接后继
    
    例如：线性表、栈、队列、串
  - （2）==非线性结构==：一个节点可能有多个直接前驱和直接后继
    
    例如：树、图
- 划分方法二——四类基本逻辑结构
  - （1）==集合结构==：数据元素之间除了 属于同一集合的关系外，别无任何其他关系。
    
    例如：确定一名学生是否为班级成员，只需将班级看做一个集合结构。
  - （2）==线性结构===结构中的数据元素之间存在着一对一的线性关系。
    
    例如：将学生信息数据按照其入学报到的时间先后顺序进行排列，将组成一个线性结构
  - （3）==树形结构==：结构中的数据元素之间存在着一对多的层次**关系。
    
    例如：在班级的管理体系中，班长管理多个组长，每位组
    
    长管理多名组员，从而构成树形结构。
  - （4）==图状结构或网状结构==：结构中的数据元素之间存在着多对多的任意关系。
    
    例如：多位同学之间的朋友关系，任何两位同学都可以是朋友，从而构成图状结构或网状结构。
存储结构的种类
- 四种基本的存储结构：
  - 顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。
    
    在C语言中用数组来实现。
  - 链式存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。
    
    在C语言中用指针来实现。~~关于“指针”的痛苦回忆浮现出来力~~。:cry:
  - 索引存储结构：存储结点信息的同时，还建立附加的索引表
    
    例如：通讯录
  - 散列存储结构：根据结点的关键字直接计算出该结点的存储地址

1.2.3 数据类型和抽象数据类型

数据类型：在使用高级程序设计语言编写程序时，必须对程序中出现的每个变量.常量或表达式，明确说明它们所属的数据类型^c。
- 例如C语言中：
  - 提供int，char, float, double等基本数据类型
  - 数组、结构、共用体、枚举等构造数据类型
  - 还有指针、空(void)类型
  - 用户也可用typedef 自己定义数据类型
- 一些最基本数据结构可以用数据类型来实现，如数组、字符串等;
- 而另一些常用的数据结构，如栈、队列、树、图等，不能直接用数据类型来表示。
- 数值类型的作用
  - 约束变量或常量的取值范围
  - 约束变量或常量的操作

抽象数据类型:是指一个数学模型以及定义在此数学模型上的一组操作。

由用户定义，从问题抽象出数据模型（逻辑结构）
还包括定义在数据模型上的一组抽象运算（相关操作）
不考虑计算机内的具体存储结构与运算的具体实现算法

抽象数据类型的形式定义：

ADT抽象数据类型名{

数据对象：<数据对象的定义>

数据关系：<数据关系的定义>

基本操作：<基本操作的定义>

}ADT 抽象数据类型名

其中：

数据对象、数据关系的定义用伪代码描述
基本操作的定义格式为：

基本操作名（参数表）

初始条件：<初始条件描述>

操作结果：<操作结果描述>

基本操作定义格式说明：

参数表：
1. 赋值参数只为操作提供输入值
2. 引用参数以&打头，除可提供输入值外，还将返回操作结果
初始条件：描述操作执行之前数据结构和参数应满足的条件，若不满足则操作失败，并返回相应出错信息。若初始条件为空，则省略之

操作结果：说明操作正常完成后，数据结构的变化情况和应返回的结果。

ADT大致结构：

ADT 抽象数据名{
    Data
        数据对象的定义
        数据元素之间的逻辑关系的定义
    Operation
        操作1
           初始条件
           操作结果描述
        操作2
            ……
        操作n
}ADT 抽象数据类型名

Circle的定义

ADT Circle{
  数据对象：D={r,x,y|rxy均为实数}
  数据关系：R={<r,x,y>|r是半径，<x,y>是圆心坐标}
  基本操作：
  Circle(&C,r,x,y)
         操作结果：构造一个圆
  double Area(C)
         初始条件：圆已存在
         操作结果：计算面积
  double Circumference(C)
         初始条件：圆已存在
         操作结果：计算周长
   ……
}ADT Cicle

复数的定义

ADT Complex{
    数据对象：D = {r1,r2|r1,r2都是实数}
    数据关系：S = { <r1,r2>|r1是实部，r2是虚部}
    基本操作：
        assign (&C,v1,v2)
        操作结果：构造复数Z，其实部和虚部，分别赋以参数V1,V2值
    destroy(&C)
        操作结果：复数Z被销毁
    getreal(C,&realPart)
        初始条件：复数已存在
        操作结果：用realpart返回复数Z的实部值。
    getlmag(C,&lmagPart)
        初始条件：复数已存在
        操作结果：用magPart返回复数Z的虚部值。
    add(C1,C2,&sum)
        初始条件：Z1,Z2是复数
        操作结果：sum返回两个复数Z1，Z2的和
}ADT Circle

以上代码均为类C语言作为描述工具

1.3 抽象数据类型的表示与实现

以下给出一个具体的实现过程

#include<stdio.h>
typedef struct complex{                   //typedef起别名的，定义一个结构体变量struct[结构体名]结构体变量名：用[struct[结构体名]等价于int
    float realpart;                      //实部
    float imagepart;                    //虚部
}complex;                                //typedef关键字把struct complex 起了个名字叫complex]
complex assign(float real,float image){  //构造复数
    complex c;
    c.realpart=real;
    c.imagepart=image;
    return c;
}
float getreal(complex c){              //取复数实部
    return c.realpart;
}
float getimage(complex c){             //取复数虚部
    return c.imagepart;
}
complex Add(complex c1,complex c2){    //求两复数c1与c2的和sum
    complex sum;
    sum.realpart=c1.realpart+c2.realpart;
    sum.imagepart=c1.imagepart+c2.imagepart;
    return sum;
}
int main(){                            //主函数
    complex c1,c2,c3;
    c1=assign(1.0,2.0);
    c2=assign(3.0,4.0);
    c3=Add(c1,c2);
    printf("c1:%.2f+%.2fi\n",c1.realpart,c1.imagepart);
    printf("c1:%.2f+%.2fi\n",c2.realpart,c2.imagepart);
    printf("c1与c2的和为:%.2f+%.2fi\n",Add(c1,c2).realpart,Add(c1,c2).imagepart);
}

1.4 算法和算法分析

算法；对特定问题求解方法和步骤的一种描述，它是指令的有限序列。其中每个指令表示一个或多个操作。
算法的描述：
1. 自然语言：英语、中文
2. 流程图：传统流程图、NS流程图 // 软件工程没白学
3. 伪代码：类语言：类C语言
4. 程序代码：C语言程序，JAVA语言程序
算法与程序：
- 算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多个算法。
- 程序是用某种程序设计语言对算法的具体实现。
  
  程序=数据结构+算法

1.4.1 算法特性

有穷性：算法总在有穷步之后结束，且每一步在有穷时间内完成。
确定性：每个指令有确切的含义，没有二义性，在任何条件下，只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出。
可行性：算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现。
输入：一个算法有零个或多个输入。
输出：一个算法有一个或多个输出。

1.4.2 算法设计的要求

正确性：
1. 程序中不含语法错误。
2. 程序对于几组输入数据能够得出满足要求的结果。
3. 程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果。
4. 程序对于一切合法的输入数据都能得出满足要求的结。
可读性：主要为了人的阅读和交流，其次才是为计算机的执行，因此算法要易于人理解。
健壮性：指当输入非法数据时，算法算法恰当的做出反应或进行相应处理，而不是产生莫名其妙的输出结果。
高效性：花费尽量少的时间和尽量地的存储需求。

1.4.3 算法的时间复杂度

算法效率以下两个方面来考虑：
1. 时间效率：指的是算法所耗费的时间。
2. 空间效率，值算法执行过程中所耗费的存储空间。
  - 时间效率和空间效率有时是矛盾的。
时间效率的度量：
- 事后统计：将算法实现，测算其时间和空间开销。
  - 缺点：编写程序实现算法将花费较多时间与精力，所得实验结果依赖于计算机的软硬件等环境因素，掩盖算法本身的优劣。
- 事前分析：对算法所消耗资源的一种估算方法。算法运行时间=一个简单操作*简单操作次数
  - 为了方便比较不同算法的时间效率，我们仅比较他们的数量级

for(i=1;i<=n;i++)                            //n+1次
    for(j+1;j<=n;j++){                      //n(n+1)次
      c[1][j]=0;                            //n*n次
        for(k=0:k<n:k++)                    //n*n*(n+1)次
            c[i][j]=c[i][j]+a[i][k]*b[k][j];//n*n*n次
    }

对于求解矩阵相乘问题，算法耗费时间：

$\large T(n)={2n^3}+{3n^2}+2n+1$

$n→∞$时，$T(n)/n3→2$,这表示n充分大时，$T(n)与n^3$是同阶或同数量级，引入大“O”记号，则T(n)可记作：
- $\large T(n)=O(n^3)$
- 原公式： $\large T(n)=O(f(n))$

分析算法时间复杂度的基本方法
1. 找出语句频度最大的那条语句作为基本语句
2. 计算基本语句的拼读得到问题规模$n$的某个函数$f(n)$
3. 取其数量级用符号“$O$”表示

x=0;y=0;
for(int k=0;k<n;k++)                    //n+1次（这里是判断次数，所以要加一）
    x++;                                //n次(这里是执行次数，所以不用加一)
for(int i=0;i<n:i++)                    //n+1次
    for(int j=0;j<n;j++)                //n*(n+1)次
        y++;                            //n*n次

$\large f(n)=n(n+1)$ $\large T(n)=O(n^2)$
- 可以直接看执行次数最多的语句，比如嵌套最深的语句

for(i=1:i<=n:i++)
    for(j+!;j<+i:j++)
        for(k=1;k<=j:k++)
            x=x+1

语句频度=$\large\sum\limits_{i=1}^n\sum\limits_{j=1}^n\sum\limits_{k=1}^n=\sum\limits_{i=1}^n\sum\limits_{j=1}^nj=\sum\limits_{i=1}^n\dfrac{i(i+1)}{2}=\dfrac{1}{2}(\sum\limits_{i=1}^ni^2+\sum\limits_{i=1}^ni)=v$
- 公式第一步是第三层嵌套，执行$\large j$次（$\large j$个1的和）
  - 公式第二步是求和公式$\large j$看做一个变量，从$\large j=1$到$\large i$一个等差数列求和直接套公式
    - 公式第三步一个平方和累加公式^d一个累加公式[^e]，轻易可得出结果
      - 直接抓大放小，可得$T(N)=O(n^3)$
分析以下程序段的时间复杂度
1
2
3
i=1;
while(i<=n)
i=i*2;
关键是找出来执行次数x与n的关系，并表示成n的函数

假设语句2执行x次，由循环条件$i<=n,所以2^x=n 所以x<=log_2n$

即$f(n)<=log_2n$,取最大值$f(n)=log_2n$

1.4.4 算法的空间复杂度

空间复杂度：算法所需存储空间的度量
- 记作:$\large S(n)=O(f(n))$

算法一：

for(i=0;i<=n/2;i++){
    t=a[i];
    a[i]=a[n-i-1];
    a[n-i-1]=t;
}

算法二：

for(i=0;i<=n;i++)
    b[i]=a[n-i-1];
for(i=0;i<=n;i++)
    a[i]=b[i];

算法一：$\large S(n)=O(1)$ 原地工作

算法二：$\large S(n)=O(n)$

[^e]:$\large \sum\limits_{k=1}^nK=\dfrac{n(n+1)}{2}$

1.5 小结

数据结构是一门研究非数值计算程序设计中操作对象，以及这些对象之间的关系和操作。
数据结构包括两个方面的内容：数据的逻辑结构和存储结构。同一逻辑结构采用不同的存储方法可以得到不同的存储结构。
1. 逻辑结构是从具体问题抽象出来的数学模型，从逻辑关系上描述数据，它与数据的存储无关。根据数据元素之间关系的不同特性，通常有四类基本逻辑结构：集合结构、线性结构、树形结构和图状结构。
2. 存储结构是逻辑结构在计算机中的存储表示，有两类存储结构：顺序存储结构和链式存储结构。
抽象数据类型是指由用户定义的、表示应用问题的数学模型 ，以及定义在这个模型上的一组操作的总称，具体包括三部分：数据对象、数据对象上关系的集合，以及对数据对象的基本操作的集合。
算法是为了解决某类问题而规定的一个有限长的操作序列。算法具有五个特性：有穷性、确定性、可行性、输入和输出。一个算法的优劣应该从以下四方面来评价：正确性、可读性、健壮性和高效性。
算法分析的两个主要方面是分析算法的时间复杂度和空间复杂度，以考察算法的时间和空间效率。一般情况下，鉴于运算空间较为充足，故将算法的时间复杂度作为分析的重点。算法执行时间的数量级称为算法的渐近时间复杂度，$T(n) = 0(f(n) )$, 它表示随着问题规模n的增大，算法执行时间的增长率和.f(n)的增长率相同，简称时间复杂度。