数据结构1

Before：此中文版的数据结构用于整理翁阿姨课上的笔记，以周为单位更新

数据结构 1 引言

数据的逻辑结构

集合结构：两两无关
线性结构：除首尾元素外，每个元素仅有一个前驱和一个后驱
树形结构：除根元素外，每个元素都只有一个前驱，后驱数量不限
图型结构：每个元素可以有任意数量的前驱和后驱

数据结构的操作

创建和释放：构造函数 + 析构函数
更新：插入 更新（修改）删除
查找：访问 搜索 遍历

数据结构存储实现

存储结点：每个存储结点存放一个数据元素
结点间的关系：比如链表中指向next结点的指针是一种链接存储；而vector类中我们使用的是数组存储；而对于集合结构这种杂乱的数据结构时，可用哈希存储，用一个哈希函数将数据元素与元素存储位置关联起来；另外还有索引存储，分别设置数据区和索引区
附加信息：比如链表中的头尾结点

算法效率分析

三个时间性能：

• 最好情况下的时间复杂度
• 最坏情况下的时间复杂度
• 平均情况下的时间复杂度

时间复杂度的表示一般有2种方法：大O表示法（取运行时间函数的主项）和 F（n）表示法（通常选择比较简单的函数形式）。有：O（1）< O(logN)< O(N)< O(NlogN)< O(N^2)< O(N^3) ; O(2^N)< O(N!)< O(N^N)
那么时间复杂度应该如何计算呢?
核心在于：在整个程序中找出最复杂、运行时间最长的程序段的时间复杂度
空间性能：

• 存储被处理数据所需的空间
• 实现操作所需的额外空间
  空间复杂度一般按最坏情况处理，和时间复杂度一样同样使用大O表示法

经典举例：最大连续子序列和问题

方法一：O(N^3)

int MaxSum;
for(int i = 0 ; i < n ; i ++){
    for(int j = i ; j < n ; j ++){
        int sum = 0;
        for(int k = i ; k <= j ; k ++){
            sum += a[k];
        } 
        if(sum > MaxSum){
            MaxSum = sum;
        }
    }
}

方法二：O(N^2)

int MaxSum = 0 ;
for(int i = 0 ; i < size ; i ++){
    int sum = 0 ;
    for(int j = i ; j < size ; j ++){
        sum += a[j];
        if(sum > MaxSum ){
            MaxSum = sum;
            start = i;
            end = j;
        }
    }
}

方法三：分治法 O(NlogN)
共有3种情况：

• 全部出现在前半部分，直接递归计算
• 全部出现在前半部分，直接递归计算
• 前半部分开始，后半部分结束

那么方法也是相对应的：

• 递归计算前半部分最大连续子序列和
• 递归计算后半部分最大连续子序列和
• 通过2个连续循环计算前半部分开始，后半部分结束的最大连续子序列和

下面是代码实现：

int MaxSum(int a[],int left,int right ,int &start,int &end){
    if(left == right){
        start = left;
        end = right;
        if(a[left] > 0){
            return left;
        }else{
            return 0;
        }
    }
    int MaxLeft = 0;
    int MaxRight = 0;
    int MaxLeftTmp = 0;
    int MaxRightTmp = 0;
    int startL,endL,startR,endR;
    int center = (left + right)/2;
    MaxLeft = MaxSum(a,left,center,startL,endL);
    MaxRight = MaxSum(a,center + 1,right,startR,endR);
    int leftSum,rightSum;
    start = center;
    for(int i = center;i >= left;i --){
        leftSum += a[i];
        if(leftSum > MaxLeftTmp){
            MaxLeftTmp = leftSum;
            start = i; 
        }
    }
    end = center + 1;
    for(int i = center + 1;i <= right;i ++){
        rightSum += a[i];
        if(rightSum > MaxRightTmp){
            MaxRightTmp = rightSum;
            end = i;
        }
    }
    int MaxTmp = MaxLeftTmp + MaxRightTmp;
    if(MaxTmp >= MaxLeft && MaxTmp >= MaxRight){
        return MaxTmp;
    }else if(MaxLeft >= MaxTmp && MaxLeft >= MaxRight){
        start = startL;
        end = endL;
        return MaxLeft;
    }else{
        start = startR;
        end = endR;
        return MaxRight;
    }
}

计算以下复杂度，得到T(N) = 2T(N/2) + N; 可以解得复杂度为O（NlogN）

方法四：穷举法的再优化 O(N)
通过一点逻辑判断，我们可以知道，所有与最大连续子序列毗连的连续子序列一定有负的（或0），否则会包含它们。故我们可以做出改进：当检测出一个负子序列时，可以直接让start增加到j + 1。这样一来，我们只需要：

$$
一个循环
$$

下面给出代码实现：

int MaxSumProcess(int a[],int size){
    int MaxSum = 0;
    int thisSum = 0;
    int start = 0;
    int tmp = 0;
    int end = 0;
    for(int i = 0;i < size;i ++){
        thisSum += a[i];
        if(thisSum <= 0){
            thisSum = 0;
            MaxSum = 0;
            tmp = i + 1;
        }else if(thisSum > MaxSum){
            MaxSum = thisSum;
            start = tmp;
            end = j;
        }
    }
    if(start == size){
        MaxSum = 0;
    }
    return MaxSum;
}

显然，这种类似于动态规划的方法，时间复杂度达到了O(N)!

数据结构的实现

过程化程序设计 VS 面向对象程序设计：过程化程序设计通过定义一组变量进行存储实现，通过一组算法进行运算实现，但是无法将数据结构定义成一个真正的程序，程序员必须掌握每个数据结构的实现。而面向对象的程序设计将存储与运算封装为类，每个数据结构可表示为一个类模板，有利于代码的重用。
每种数据结构用一个抽象类描述，指出该数据结构提供的操作。而每种数据结构可以有若干种实现的方法，每种实现就是一个类（从抽象类继承）。