Author：Liedra
https://www.cnblogs.com/LieDra/

Ch1绪论

0x01 绪论

程序 = 数据结构+算法
同样的数据对象，用不同的数据结构来表示，运算效率可能有明显差异。

数据结构研究内容

表：学生选课课表，人员表，图书检索等
树：文件系统磁盘目录，人机对弈派生格局等
图：地图导航（最短路径等场景）
共性：研究非数值计算，数学模型是表、数、图之类的有逻辑关系的数据，以及研究操作对象之间的关系和操作。
数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

0x02 基本概念和术语

数据、数据元素、数据项、数据对象
数据：信息载体，各种符号集合。人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。
数据元素：是表示一个事物的一组数据。数据的基本单位，在计算机程序中通常作为一个整体。（也叫做元素、记录、结点或顶点）
数据项：构成数据元素的不可分割的最小单位，一个数据元素可以由多个数据项构成。
数据>数据元素>数据项

例子

例如，
学生信息可包括学生的学号、姓名、性别、年龄等数据。
这些数据构成学生情况的描述的数据项；
包括学号、姓名、性别、年龄等数据项的一组数据就构成学生信息的一个数据元素。

数据对象：性质相同的数据元素的集合（如整数，字母字符，学籍表等）是数据的子集。
数据结构：数据元素相互之间的关系成为结构。包括逻辑关系，物理结构（存储结构），数据的运算和实现（操作）。
逻辑结构：与存储无关（数据元素之间的相互联系方式）
物理结构：存储器中的结构（数据元素在计算机中的存储方式）
逻辑结构的种类：线性结构（1对1，线性表、栈、队列、串）和非线性结构（1对多或多对多，树，图）或者划分为集合、线性、树、图四种结构。
存储结构的种类：

• 顺序存储结构（一组连续存储单元依次存储数据元素，数组实现，特点是逻辑上相邻的数据元素在物理存储上也相邻）
• 链式存储结构（不连续的存储单元，c/c++中用指针来实现，使用指针把相互直接关联的结点(即直接前驱结点或直接后继结点)链接起来，其特点是逻辑上相邻的数据元素在物理上不一定相邻）
• 索引存储结构（存结点同时还建立附加的索引表）
• 散列存储结构（根据某种公式直接计算结点存储地址，查找章节详细介绍）

数据类型：明显或隐含规定了变量的取值范围以及在该范围内所允许进行的操作。

抽象数据类型：没有确切定义的数据类型。是一个数学模型以及定义在此数学模型上的一组操作。包含数据对象，数据关系，数据操作的三元组。在程序语言中用已有数据类型定义存储结构，用函数定义相关的数据操作。

0x03算法与算法分析

算法：描述求解问题方法的操作步骤集合。在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
算法描述可以用自然语言，也可以用流程图、NS流程图等描述。还可以用伪代码描述，更可以用程序代码直接描述。

• 文字形式:用中文或英文这样的文字来描述算法。
• 伪码形式:用一种仿程序设计语言的语言来描述算法。
• 程序设计语言形式:用某种程序设计语言描述算法。其优点是算法不用修改，直接作为程序语句输入计算机，计算机能调用和运行。

例1-1
设计一个把存储在数组中的有n个抽象数据元素a0,a1,…,an-1逆置的算法，即要求逆置后的数组中数据元素序列为an-1 , … , a1 , a0,并要求原数组中的数据元素值不能被改变。

void Reverse(int n,DataType a[],DataType b[])
{
    int i;
    for(i=0;i<n;i++)
    b[i]=a[n-1-i];     //把数组a的元素逆置后赋给数组b
}

例1-2
设计一个把存储在数组中的有n个抽象数据元素a0,a1,…,an-1就地逆置的算法，即要求逆置后的数组中数据元素序列为an-1 , … , a1 , a0,并要求原数组中的数据元素值被改变。

void Reverse(int n,DataType a[])
{
    int i,m=n/2;
    DataType temp;
    for(i=0;i<m;i++)     //进行m次调换
    {
        temp=a[i];
        a[i]=a[n-1-i];
        a[n-1-i]=temp;
    }
}

算法特性：

• 输入性：具有0个或者多个输入。
• 输出性：产生1个或多个有意义的输出。
• 有限性：算法执行有穷步之后结束，且每一步有穷时间内完成。执行语句的序列是有限的。
• 确定性：无二义性，对于相同的输入只能得到相同的输出（带随机的除外）。每一条语句的含义明确，无二义性。
• 可行性（可执行性）：算法是可执行的，每一条语句都应在有限的时间内完成。

算法设计的要求：

• 正确性：对于一切合法输入都能得到满足要求的结果
• 可读性：应易于人的理解
• 健壮性：鲁棒性，对于非法数据和错误，应恰当做出反应或处理。
• 高效性：尽量少的时间和空间要求（尽量高时间效率、高空间效率）

算法效率

时间效率和空间效率（常矛盾）
算法时间效率：依据程序消耗时间度量（事后统计和事前分析两种度量方法）

• 事后统计：运行完后根据花费时间得到。设计测试数据，运行程序，统计时间。缺陷是必须运行程序，测试数据设计困难。
• 事前分析：根据单个操作花费时间（假设执行每条语句所需时间均为单位时间）与操作执行次数计算算法运行时间。

程序运行消耗时间的有关因素：

• 所用程序设计语言
• 编译产生的机器语言代码质量
• 机器执行指令的速度
• 问题规模

一般比较算法的时间效率时，仅比较数量级。即算法的渐进时间复杂度O(f(n))。

• O(2n + 3) = O(2n)
• O(2n^2) = O(n^2)
• O(n^3) > O(n^2)

n在排序中可以表示记录数，在矩阵中可以表示矩阵阶数，多项式中可以表示多项式项数，树中可以表示为树结点数目······。
分析方法：找出执行次数（频度）最大的语句（基本是找循环最深），计算频度得到f(n),得到渐进时间复杂度T(n)=O(f(n))。

最坏时间复杂度，平均时间复杂度，最好时间复杂度。一般考虑最坏时间复杂度。

例1-3
n*n矩阵相乘（三重循环）量级为n的三次方。

for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
    c[i][j]=0;                            //基本语句1
    for(k=0;k<n;k++)
          c[i][j]=c[i][j]+a[i][k]*b[k][j];  //基本语句2
}
//设基本语句的执行次数为f(n),有f(n)=c1×n2次方+c2×n3次方，最后得到大O。

例1-4
下边的算法是用冒泡排序法对数字a中的n个整数类型的数据元素(a[0]~a[n-1])，从小到大进行排序，求该算法的时间复杂度。

void BubbleSort(int a[],int n)
{   int i,j,flag=1;
    int temp;
    for(i=1;i<n&&flag==1;i++)
    {       flag=0;
        for(j=0;j<n-i;j++)
        {   if(a[j]>a[j+1])
            {   flag=1;
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
}
/*第一次交换n-1次，第二次交换n-2次……..1次，用等差数列求和公式求和，每次交换有4个赋值操作，所以乘4，另外flag=0执行了n次。
最坏情况下为f(n) ≈n+2* n的2次方，大O为n的二次方
*/

例1-5
下面的算法是在一个有n个数据元素的数组a中删除第I个位置的数组元素，要求当删除成功时数组元素个数减1，求该算法的时间复杂度。其中数组下标从0至n-1。

int Delete(int a[],int &n,int i)
{
    int j;
    if(i<0||i>=n) return 0;                  //删除位置错误，失败返回
    for(j=i+1;j<n;j++) a[j-1]=a[j];   //顺次移位填补
    n--;                                                //数组元素个数减1
    return 1;                                      //删除成功返回
}
/*
对于顺序表，所谓删除就是把其后元素依次前移。
这里其实for循环里面值从0---n-1，求平均得到平均时间复杂度大O为O(n)。
*/

算法时间效率的比较。
O(1) < O(log n ) < O(n) < O(nlog n ) < O(n方) < < O(n三次方) < ··· < O(n的k次方) < O(2的n次方)
（即常数阶-对数阶-线性阶-线性对数阶-平方阶-立方阶-k次方阶-指数阶）

算法空间复杂度，算法所需存储空间的度量。（包括算法本身占据空间，和运行时使用的辅助空间）。基本与时间类似，一般不太考虑。

算法的书写规范：主要是算法的符号命名和书写格式上。类似于代码规范。