数据结构与算法 之 基础

前言

数据结构：是指相互之间存在一种或多种特定关系的数据元素的集合用计算机存储、组织数据的方式。数据结构分别为逻辑结构、（存储）物理结构和数据的运算三个部分。

一、数据结构基础知识

1.1 基本概念

• 数据（Data）是能被计算机处理的符号或符号集合（原材料）。如字符、图片、音视频等。
• 数据对象（data object）是性质相同的数据元素的集合，是数据的一个子集。例如：正整数N={1，2，3，····}。
• 数据元素（data element）是数据的基本单位。例如：人Person ,汽车Car 等。
• 数据项（data item）是组成数据元素的最小单位。例如：Person 数据元素,可以为分解为眼睛,耳朵,鼻子,嘴巴,手臂这些基本的数据项,也可以从另外的角度拆解成姓名,年龄,性别,出生地址,出生日期,联系电话等数据项. 那么你如何拆解数据项, 要看你的项目来定.。
• 数据结构（data structure）是数据的组织形式，数据元素之间存在的一种或多种特定关系的数据元素集合。
• 数据类型（data type）是由若⼲类型组合⽽成，可以再分解的。在C语言中可以分为原子类型和结构类型。原子类型是不可以再分解的基本类型，包括整型、实型、字符型等。结构类型是由若干个类型组合而成，是可以再分解的。

从上至下的包含关系

//声明一个结构体类型
struct Teacher {    // struct：一种数据结构
    char *name;     // name：数据项
    char *sex;      // sex：数据项
    int  age;       // age：数据项    
};

int main(int argc, const char * argv[]) {
    struct Teacher t;           // t：数据元素
    struct Teacher tArray[10];  // tArray：多个数据元素集合组成了数据对象
    
    // 数据元素中每一项称为数据项
    t.age = 18;      
    t.name = "Dezi";
    t.sex = "男";

    return 0;
}

1.2 数据的逻辑结构

逻辑结构（logical structure）是指在数据中数据元素之间的相互关系。数据元素之间不同的逻辑关系构成了以下4种结构类型：

1. 集合结构：数据元素之间没有特殊的关系，只是属于一个集合。例如: 动物园就是一个集合：河马、熊猫、狮子、老虎、长颈鹿他们就是数据元素。
2. 线性结构：数据元素的结构关系是一对一的，并且是有先后的次序。常见的线性结构有：线性表、队列、栈（FIFO）、堆（FILO）、数组、字典、字符串（特殊的线性结构）。
3. 树形结构：数据元素的结构关系是一对多的关系。常见的树形结构：二叉树、B树、哈夫曼树、红黑树等。
4. 图形结构：数据元素的结构关系是多对多。常见的图形结构：邻近矩阵、邻接表。

逻辑结构图

1.3 数据的存储结构/物理结构

存储结构（storage structure）也称为物理结构（physical structure）：数据的逻辑结构在计算机中的存储形式。
数据的存储结构通过反映数据元素之间的逻辑关系分为顺序存储结构 和 链式存储结构。

1. 顺序存储结构：把数据元素存放在一组存储地址连续的存储单元里，其数据元素间的逻辑关系和物理关系是一致的。
2. 链式存储结构：把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的，数据元素的存储关系并不能反映其逻辑关系，因此需要借助指针来表示数据元素之间的逻辑关系。

存储结构/物理结构

二、 数据结构与算法

算法（algorithm）是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

数据结构与算法两者是不可分割的，两者既有联系又有区别：

• 联系是程序=算法+数据结构。数据结构是算法实现的基础，算法总是依赖某种数据结构来实现。算法的操作对象是数据结构。
• 区别是数据结构关注的是数据的逻辑结构、存储结构等基本操作，而算法更多的是关注如何在数据结构的基础上解决实际问题。
• 算法是编程思想，数据结构则是这些思想的基础。

2.1 算法的特性

• 输入输出：有零或多个输入，有一或多个输出。
• 有穷性：有限的执行步骤和执行时间。
• 确定性：每一步的执行条件只有一条执行路径，也就是相同输入只能有唯一的输出结果。
• 可行性：每一步操作必须可行，可以通过有限的执行次数完成。

2.2 算法的设计要求

• 正确性：输入、输出和加工处理无歧义。
• 可读性：便于阅读、理解和交流。
• 健壮性：异常情况处理。
• 高效率：算法的执行时间短。
• 低存储：占用的最大存储空间少。

2.3 算法时间复杂度

大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。

1. 大O表示法三个规则

• 用常数1取代运行时间中所有常数：3 -> O(1)。
• 在修改运行次数函数中，只保留最高阶项：n^3+ 2n^2+ 5 -> O(n^3)。
• 如果在最高阶存在且不等于1，则去除这个项目相乘的常数：2n^3 -> O(n^3)。

2. 时间复杂度：
   

   

3. 时间复杂度排序

O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

指数阶O(2^n)或者O(n!)除非是非常小的n，否则会造成噩梦般的时间消耗，这是一种不切实际的算法时间复杂度，一般不考虑！

4. 时间复杂度计算案例

• 常数阶

//1+1+1+1+1+1+1 = 7 O(1)
void testSum2(int n){
    int sum = 0;                //执行1次
    sum = (1+n)*n/2;            //执行1次
    sum = (1+n)*n/2;            //执行1次
    sum = (1+n)*n/2;            //执行1次
    sum = (1+n)*n/2;            //执行1次
    sum = (1+n)*n/2;            //执行1次
    printf("testSum2:%d\n",sum);//执行1次
    
}

• 线性阶

//x=x+1; 执行n次 O(n)
void add2(int x,int n){
    for (int i = 0; i < n; i++) {
        x = x+1;
    }
}

//1+(n+1)+n+1 = 3+2n -> O(n)
void testSum3(int n){
    int i,sum = 0;               //执行1次
    for (i = 1; i <= n; i++) {   //执行n+1次
        sum += i;                //执行n次
    }
    printf("testSum3:%d\n",sum);  //执行1次
}

• 对数阶

/*2的x次方等于n x = log2n  ->O(logn)*/
void testA(int n){
    int count = 1;         //执行1次
    //n = 10
    while (count < n) {
        count = count * 2;
    }
    
}

• 平方阶

//x=x+1; 执行n*n次 ->O(n^2)
void add3(int x,int n){
    for (int i = 0; i< n; i++) {
        for (int j = 0; j < n ; j++) {
            x=x+1;
        }
    }
}

//n+(n-1)+(n-2)+...+1 = n(n-1)/2 = n^2/2 + n/2 = O(n^2)
//sn = n(a1+an)/2
void testSum4(int n){
    int sum = 0;
    for(int i = 0; i < n;i++)
        for (int j = i; j < n; j++) {
            sum += j;
        }
    printf("textSum4:%d",sum);
    
}

//1+(n+1)+n(n+1)+n^2+n^2 = 2+3n^2+2n -> O(n^2)
void testSum5(int n){
    int i,j,x=0,sum = 0;           //执行1次
    for (i = 1; i <= n; i++) {     //执行n+1次
        for (j = 1; j <= n; j++) { //执行n(n+1)
            x++;                   //执行n*n次
            sum = sum + x;         //执行n*n次
        }
    }
    printf("testSum5:%d\n",sum);
}

• 立方阶

//1+n+n*n+n*n*n+n*n*n = 1+n+n^2+2n^3 -> O(n^2)
void testB(int n){
    int sum = 1;                         //执行1次
    for (int i = 0; i < n; i++) {        //执行n次
        for (int j = 0 ; j < n; j++) {   //执行n*n次
            for (int k = 0; k < n; k++) {//执行n*n*n次
                sum = sum * 2;          //执行n*n*n次
            }
        }
    }
}

2.4 算法空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式 记做：S(n) = n(f(n))，其中n为问题的规模，f(n)为语句句关于n所占存储空间的函数。
考量算法的空间复杂度，主要考虑算法执行时所需要的辅助空间。

1. 程序空间计算因素：

• 寄存本身的指令
• 常数
• 变量
• 输入
• 对数据进行操作的辅助空间

2. 空间复杂度计算：
   问题：数组逆序，将一维数组a中的n个数逆序存放在原数组中。

int main(int argc, const char * argv[]) {

    int n = 5;
    int a[10] = {1,2,3,4,5,6,7,8,9,10};
    
    //算法实现1 — 空间复杂度：O(1)， 因为辅助空间只用了一个临时变量
    int temp;
    for(int i = 0; i < n/2 ; i++){
        temp = a[i];
        a[i] = a[n-i-1];
        a[n-i-1] = temp;
    }

    for(int i = 0;i < 10;i++)
    {
        printf("%d\n",a[i]);
    }
    
    //算法实现2：— 空间复杂度：O(n) ，因为辅助空间用到了b数组的n个元素空间
    int b[10] = {0};
    for(int i = 0; i < n;i++){
        b[i] = a[n-i-1];
    }
    for(int i = 0; i < n; i++){
        a[i] = b[i];
    }
    for(int i = 0;i < 10;i++)
    {
        printf("%d\n",a[i]);
    }

    return 0;
}

2.5 算法的最好情况与最坏情况

例如，大家在查找一个n个随机数字数组中的某个数字，最好的情况是第一个数字就是，那么算法的时间的复杂度为O(1)。但也有可能这个数字就在最后一个位置上，也就是算法时间复杂度为O(n)，这是最坏的情况了。

最坏的情况下的运行时间是一种保证，那就是运行时间将不会比这更坏了。在应用中，这是一种最重要的需求，通常除非特别指定，我们提到的运行时间都是最坏情况下的运行时间。