1. 简介

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

数据结构(data structure)是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。

常见的数据结构：

数据结构.png

2. 基本数据单位

• 数据：信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合；
• 数据对象：具有相同性质的数据元素的集合，是数据的一个子集；
• 数据元素：数据的基本单位，通常作为一个整体进行考虑和处理；
• 数据项：构成数据元素的不可分割的最小单位；
• 数据类型：是一组值的集合和定义在该集合上的操作的总和。

基本概念.png

3. 数据结构三要素

3.1 数据的逻辑结构

反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后间关系，而与他们在计算机中的存储位置无关。

1. 集合结构：数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；

集合结构.jpeg

2. 线性结构：数据结构中的元素存在一对一的相互关系；

线性结构.jpeg

3. 树形结构：数据结构中的元素存在一对多的相互关系；

树形结构.jpeg

4. 图形结构：数据结构中的元素存在多对多的相互关系。

图形结构.jpeg

3.2 数据的存储（物理）结构

数据的物理结构是数据结构在计算机中的表示（又称映像），它包括数据元素的机内表示和关系的机内表示。即数据的逻辑结构在计算机存储空间的存放形式。

1. 顺序存储结构：用一段地址连续的存储单元依次存储线性表的数据元素。

顺序存储结构.jpeg

2. 链式存储结构：在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。不要求逻辑上相邻的元素在物理位置上也相邻。

链式存储结构.jpeg

3.3 数据的运算

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，并且每个指令表示一个或多个操作，算法代表着用系统的方法描述解决问题的策略机制。

3.3.1 五大特性

1. 有穷性（Finiteness）：算法必须能在执行有限个步骤之后终止；
2. 确切性（Definiteness）：算法的每一步骤必须有确切的定义；
3. 输入项（Input）：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；
4. 输出项（Output）：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
5. 可行性（Effectiveness）：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成（也称之为有效性）。

3.3.2 算法设计要求

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。

1. 正确性：算法的正确性是评价一个算法优劣的最重要的标准；
2. 可读性：算法的可读性是指一个算法可供人们阅读的容易程度；
3. 健壮性：健壮性是指一个算法对不合理数据输入的反应能力和处理能力，也称为容错性。
4. 时间效率⾼高和储存量量低（时间复杂度和空间复杂度）。

3.3.3 时间复杂度

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f (n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

相同大小的不同输入值仍可能造成算法的运行时间不同，因此我们通常使用算法的最坏情况复杂度，记为T(n)，定义为任何大小的输入 n 所需的最大运行时间。

计算方法

1. 用常数1取代运行时间中的所有加法常数；
2. 在修改后的运行次数函数中，只保留最高阶项;
3. 如果最高阶项存在且不是1，那么我们就去掉于这个项相乘的常数。

代码示例

//常数阶（时间复杂度为 O(1)）
void testSum(int n){
    int sum = 0;  //执行1次
    sum = (1 + n) * n / 2;  //执行1次
    printf("testSum:%d\n", sum);  //执行1次
}

/*2.线性阶(时间复杂度为 O(n))*/
void add2(int x, int n){
    for (int i = 0; i < n; i++) {  //执行 n + 1 次 
        x = x+1; //执行 n 次
    }
}

/*4.平方阶(时间复杂度为 O(n^2))*/
//1+(n+1)+n(n+1)+n^2+n^2 = 2+3n^2+2n -> O(n^2)
void testSum(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("testSum:%d\n", sum);
}

常见的算法时间复杂度以及他们在效率上的高低顺序：O(1) 常数阶 < O(logn) 对数阶 < O(n) 线性阶 < O(nlogn) < O(n^2) 平方阶 < O(n^3) < { O(2^n) < O(n!) < O(n^n) }（大括号中的这几位即便是在 n 的规模比较小的情况下仍然要耗费大量的时间，算法的时间复杂度大的离谱，基本上就是“不可用状态”。）

3.3.4 空间复杂度

对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))，其中 n 为问题的规模，f(n)为语句句关于 n 所占存储空间的函数。

计算因素

1. 寄存本身的指令；
2. 常数；
3. 变量；
4. 输入；
5. 对数据进行操作的辅助空间。

在考量算法的空间复杂度,主要考虑算法执行时所需要的辅助空间。

代码示例

    int n = 5;
    int a[10] = {1,2,3,4,5,6,7,8,9,10};
    
    int temp;
    for(int i = 0; i < n/2 ; i++){
        temp = a[i];
        a[i] = a[n-i-1];
        a[n-i-1] = temp;
    }
    // 使用了变量 temp，空间复杂度为O(1)

    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]);
    }
    //空间复杂度为O(n)