重温数据结构01 基本概念

目录

• 什么是数据结构
  • 关于数据组织
  • 关于空间使用
  • 关于算法效率
  • 抽象数据类型
• 算法(Algorithm)
  • 算法(Algorithm)的定义：
  • 算法的衡量指标
    • 复杂度的渐进表示法
    • 复杂度分析技巧：
• 算法举例

什么是数据结构

关于数据组织

数据结构没有官方的统一定义。

例1：如何在书架上摆放图书？

图书的摆放应使2个相关操作方便实现：

• 新书如何插入？
• 怎么找到某本指定的书？

1. 随便放
   • 操作1：哪里有空放哪里
   • 操作2：一本一本找，图书数量多的话会很累
2. 按照书名的拼音字母顺序排放
   • 操作1：
   • 操作2：二分查找
3. 把书架划分成几个区域，每块区域摆放指定类别的书籍；在每种类别内按照书名拼音字母顺序排放
   • 操作1：确定类别，二分查找确定位置，移出空位
   • 操作2：先确定类别，在二分查找

那么如何分配空间？类别应该分多细？

关于空间使用

例2 实现PrintN函数，使得传一个正整数为N的参数后，能顺序打印从1到N的全部正整数。

循环实现：

void PrintN(int N){
    int i;
    for(i = 1;i <= N;i++){
        printf("%d
", i);
    }
    return;
}

递归实现：

void PrintN(int N){
    if(N){
        PrintN(N - 1);
        printf("%d
", N);
    }
    return;
}

当输入为10、100、1000、10000时两个函数都可以正常输出，但是当输入为100000时，递归实现会内存溢出，所以只输出了100000。这就说明了：

解决问题方法的效率跟空间的利用效率有关。

关于算法效率

例3：计算给定多项式在定点 (x) 处的值

代码：

double f(int n, double a[], double x){
    int i;
    double p = a[0];
    for(i = 1 ; i <= n ; i++){
        p += (a[i] * pow(x, i));
    }
    return p;
}

标准多项式形式为：

[f left(x ight) = a_0 + a_1x + cdotcdotcdot + a_{n-1}x^{n-1} + a_nx^n ]

根据秦九韶算法可变形为：

[f left(x ight) = a_0 + xleft(a_1 + xleft( cdotcdotcdot left(a_{n-1} + xleft(a_n ight) ight) cdotcdotcdot ight) ight) ]

实现代码为：

double f(int n, double a[], double x){
    int i;
    double p = a[n];
    for(i = n ; i > 0 ; i--){
        p = a[n - 1] + x * p;
    }
    return p;
}

利用 clock（） 函数可以计算从程序运行到 clock() 被调用时所耗费的时间，这个时间单位是 clock tick ，即时钟打点。常数 CLK_TCK 即表示机器时钟每秒所走的时钟打点数。常用的代码模板：

#include <stdio.h>
#include <time.h>

clock_t start, stop;

//记录被测函数的运行时间
double duration;

int main(){
    start = clock();//开始计时
    MyFunction();
    stop = clock();//结束计时
    duration = ((double)(stop - start)) / CLK_TCK;
    
    return 0;
}

以多项式 (f(x)=sum_{9}^{i=0} i cdot x^i) 为例，可用以下代码进行测试：

#include <stdio.h>
#include <time.h>
#include <math.h>

clock_t start, stop;

//记录被测函数的运行时间
double duration;

#define MAXN 10
#define MAXK 1e7

double f1(int n, double a[], double x){
    int i;
    double p = a[0];
    for(i = 1 ; i <= n ; i++){
        p += (a[i] * pow(x, i));
    }
    return p;
}
double f2(int n, double a[], double x){
    int i;
    double p = a[n];
    for(i = n ; i > 0 ; i--){
        p = a[n - 1] + x * p;
    }
    return p;
}

int main(int argc, char const *argv[])
{
    int i;
    double a[MAXN];
    for(i = 0 ; i < MAXN ; i++){
        a[i] = (double)i;
    }

    start = clock();
    for (int i = 0; i < MAXK; i++){
        f1(MAXN - 1, a , 1.1);
    }
    stop = clock();
    double duration1 = (((double)(stop - start)) / CLK_TCK) / MAXK;
    printf("ticks1 = %f
", (double)(stop - start));
    printf("duration1 = %6.2e
", duration1);

    start = clock();
    for (int i = 0; i < MAXK; i++)
    {
        f2(MAXN - 1, a , 1.1);
    }
    stop = clock();
    double duration2 = (((double)(stop - start)) / CLK_TCK) / MAXK;
    printf("ticks1 = %f
", (double)(stop - start));
    printf("duration2 = %6.2e
", duration2);

    return 0;
}

解决问题的效率与所使用的方法有关。

抽象数据类型

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

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

完成这些操作的方法被称为算法。

抽象数据类型（Abstract Data Type，ADT） 用于描述数据结构。

• 数据类型
  • 数据对象集
  • 数据集合相关的操作集
• 抽象：描述数据类型的方法不依赖于具体实现
  • 与存放数据的机器无关
  • 与数据存储的物理结构无关
  • 与实现操作的算法和编程语言无关

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

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

• 类型名称：矩阵(Matrix)
• 数据对象集：一个 (M imes N) 的矩阵 (A_{M imes N} = left(a_{ij} ight)(i=1,...,N)) 由 (M imes N) 个三元组 (<a, i, j>) 构成，其中 (a) 是矩阵元素的值， (i) 是元素所在的行号， (j) 是元素所在的列号。
• 操作集：对于任意矩阵 (A、B、C in Matrix) ，以及整数 (i、j、M、N)
  • Matrix Create( int M, int N) ：返回一个 (M imes N) 的空矩阵；
  • (cdotcdotcdot)

算法(Algorithm)

算法(Algorithm)的定义：

• 一个有限的指令集
• 接受一些输入（有些情况下不需要输入）
• 产生输出
• 一定是在有限步骤之后终止
• 每一条指令不能有歧义且在计算机处理范围内
• 每一条指令必须不依赖于任何一种计算机语言及具体实现的手段

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

void SelectionSort(int List[], int N){
    //将N个整数List[0]...List[N]进行非递减排序
    for(i = 0;i < N;i++){
        //从 List[i] 到 List[N-1] 中找到最小值，并将其所在位置赋值给MinPosition;
        MinPosition = SacnForMin(List, i, N-1);
        //将未排序部分的最小元素换到有序部分的最后位置;
        Swap(List[i], List[MinPosition]);
    }
}

算法的衡量指标

• 空间复杂度 (Sleft(n ight)) ——根据算法写成的程序在执行时占用存储单元的长度。
• 时间复杂度 (Tleft(n ight)) ——根据算法写成的程序在执行时耗费的时间长度。

在分析一般算法的效率时，常用以下两种复杂度：

• 最坏情况复杂度 (T_{worst} (n))
• 平均复杂度 (T_{avg} (n))

[T_{avg} (n) leqslant T_{worst} (n) ]

复杂度的渐进表示法

• (T(n) = O(f(n))) 表示存在常数 (C > 0, n_0 > 0) 使得当 (n geqslant n_0) 时有 (T(n) leqslant C cdot f(n))
• (T(n) = Omega (g(n))) 表示存在常数 (C > 0, n_0 > 0) 使得当 (n geqslant 0) 时有 (T(n) geqslant C cdot g(n))
• (T(n) = Theta(h(n))) 表示同时有 (T(n) = O(h(n))) 和 (T(n) = Omega(h(n)))

复杂度分析技巧：

• 若两段算法分别有复杂度 (T_1(n) = O(f_1(n))) 和 (T_2(n) = O(f_2(n))) ，则有：
  • (T_1(n) + T_2(n) = max(O(f_1(n)), O(f_2(n))))
  • (T_1(n) imes T_2(n) = O(f_1(n) imes f_2(n)))
• 若 (T(n)) 是关于 (n) 的 (k) 阶多项式，那么 (T(n) = Theta(n^k))
• for 循环的时间复杂度 = 循环次数 ( imes) 循环体时间复杂度
• if-else 结构的复杂度取决于 if 的条件判断复杂度和两个分支部分的复杂度，总体复杂度取三者中最大

算法举例

例1：最大子列和问题：给定 (N) 个整数的序列 ({A_1,A_2,cdotcdotcdot,A_n}) ，求函数 (f(i, j) = max{0, sum_{k=1}^{j}A_k }) 的最大值

算法1（时间复杂度为 (T(n) = O(n^3))）：

int  MaxSubSeqSum1(int A[], int N){
    int ThisSum, MaxSum = 0;
    int i, j, k;
    //i为子列左端位置
    for(i = 0;i < N;i++){
        //j为子列右端位置
        for(j = i;j < N;j++){
            ThisSum = 0;
            // ThisSum为A[i]到A[j]的子列和
            for(k = i;k <= j;k++){
                ThisSum += A[k];
            }
            if(ThisSum > MaxSum)
                MaxSum = ThisSum;
        }
    }
    return MaxSum;
}

算法2（时间复杂度为 (T(n) = O(n^2))）：

int  MaxSubSeqSum2(int A[], int N){
    int ThisSum, MaxSum = 0;
    int i, j;
    //i为子列左端位置
    for(i = 0;i < N;i++){
        //ThisSum为A[i]到A[j]的子列和
        ThisSum = 0;
        //j为子列右端位置
        for(j = i;j < N;j++){
            //对于相同的i，不同的j，只要在j-1次循环的基础上累加1项即可
            ThisSum += A[j];
            if(ThisSum > MaxSum)
                MaxSum = ThisSum;
        }
    }
    return MaxSum;
}

算法3 分而治之（时间复杂度为 (T(n) = O(nlog n))）：

int Max3( int A, int B, int C ){ 
    /* 返回3个整数中的最大值 */
    return A > B ? A > C ? A : C : B > C ? B : C;
}

int DivideAndConquer( int List[], int left, int right ){ 
    /* 分治法求List[left]到List[right]的最大子列和 */
    int MaxLeftSum, MaxRightSum; /* 存放左右子问题的解 */
    int MaxLeftBorderSum, MaxRightBorderSum; /*存放跨分界线的结果*/

    int LeftBorderSum, RightBorderSum;
    int center, i;

    if( left == right )  { /* 递归的终止条件，子列只有1个数字 */
        if( List[left] > 0 )  return List[left];
        else return 0;
    }

    /* 下面是"分"的过程 */
    center = ( left + right ) / 2; /* 找到中分点 */
    /* 递归求得两边子列的最大和 */
    MaxLeftSum = DivideAndConquer( List, left, center );
    MaxRightSum = DivideAndConquer( List, center+1, right );

    /* 下面求跨分界线的最大子列和 */
    MaxLeftBorderSum = 0; LeftBorderSum = 0;
    for( i=center; i>=left; i-- ) { /* 从中线向左扫描 */
        LeftBorderSum += List[i];
        if( LeftBorderSum > MaxLeftBorderSum )
            MaxLeftBorderSum = LeftBorderSum;
    } /* 左边扫描结束 */

    MaxRightBorderSum = 0; RightBorderSum = 0;
    for( i=center+1; i<=right; i++ ) { /* 从中线向右扫描 */
        RightBorderSum += List[i];
        if( RightBorderSum > MaxRightBorderSum )
            MaxRightBorderSum = RightBorderSum;
    } /* 右边扫描结束 */

    /* 下面返回"治"的结果 */
    return Max3( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum );
}

int MaxSubseqSum3( int List[], int N ){ 
    /* 保持与前2种算法相同的函数接口 */
    return DivideAndConquer( List, 0, N-1 );
}

算法4 在线处理算法（时间复杂度为 (T(n) = O(n))）：

int MaxSubseqSum4( int A[], int N )  
{   int ThisSum, MaxSum;
    int i;
    ThisSum = MaxSum = 0;
    for( i = 0; i < N; i++ ) {
          ThisSum += A[i]; /* 向右累加 */
          if( ThisSum > MaxSum )
                  MaxSum = ThisSum; /* 发现更大和则更新当前结果 */
          if( ThisSum < 0 ) /* 如果当前子列和为负 */
                  ThisSum = 0; /* 则不可能使后面的部分和增大，抛弃之 */
    }
    return MaxSum;  
}