数据结构：是指相互之间存在一种或多种特定关系的数据元素的集合用计算机存储、组织数据的方式。数据结构分别为逻辑结构、（存储）物理结构和数据的运算三个部分。
常见的数据结构有：队列，树，堆，数组，栈，链表，涂，散列表

数据结构常见

第1节：数据结构概述

数据结构的主要任务是通过分析数据对象的结构特征，包括逻辑结构及数据对象之间的关系，然后把逻辑结构表示成计算机课实现的物理结构，从而便于计算机处理。

1.1 概念术语

（1）数据（Data）是能被计算机处理的符号或符号集合，含义广泛，可理解为“原材料”。如字符、图片、音视频等。

（2）数据元素（data element）是数据的基本单位。例如一张学生统计表。

（3）数据项（data item）组成数据元素的最小单位。例如一张学生统计表，有编号、姓名、性别、籍贯等数据项。

（4）数据对象（data object）是性质相同的数据元素的集合，是数据的一个子集。例如正整数N={1，2，3，····}。

（5）数据结构（data structure）是数据的组织形式，数据元素之间存在的一种或多种特定关系的数据元素集合。

（6）数据类型（data type）是按照数据值的不同进行划分的可操作性。在C语言中还可以分为原子类型和结构类型。原字类型是不可以再分解的基本类型，包括整型、实型、字符型等。结构类型是由若干个类型组合而成，是可以再分解的。

他们的关系可以从以下表中看出：

数据结构图

1.2数据的逻辑结构

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

（1）集合结构：集合的数据元素没有其他关系，仅仅是因为他们挤在一个被称作“集合”的盒子里。

集合结构

（2）线性结构：线性的数据元素结构关系是一对一的，并且是一种先后的次序，就像a-b-c-d-e-f-g·····被一根线穿连起来。

线性结构

（3）树形结构：树形的数据元素结构关系是一对多的，这就像公司的部门级别，董事长-CEO\CTO-技术部\人事部\市场部.....。

树形结构

（4）图结构：图的数据元素结构关系是多对多的。就是我们常见的各大城市的铁路图，一个城市有很多线路连接不同城市。

图结构

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

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

（1）顺序存储结构：是把数据元素存放在一组存储地址连续的存储单元里，其数据元素间的逻辑关系和物理关系是一致的。

顺序存储结构

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

链式存储结构

小结：数据的逻辑结构和物理结构是密切相关的，在学习数据的过程中会发现，任何一个算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于所采用的存储结构。

1.4抽象数据类型

抽象数据类型（abstract data type，ADT）是描述具有某种逻辑关系的数据模型，并对在数学模型上进行的一组操作。抽象数据类型描述的是一组逻辑上的特性，与在计算机内部表示无关，计算机中的整数数据类型是一个抽象数据类型，不同处理器可能实现方法不同，但其逻辑特性相同，即加、减、乘、除等运算是一致的。“抽象”的意思是数据类型的数学抽象特性而不是指它们的实现方法。抽象数据类型体现了程序设计中的问题分解、抽象、信息隐藏等特性，可以把现实中的大问题分解为多个规模小且容易处理的小问题，然后建立起一个能被计算机处理的数据，并把每个功能模块的实现细节作为一个独立的单元，从而使具体实现过程隐藏起来。就类似建一栋房子，分成若干个小任务，如地皮规划、图纸设计、施工、装修等，整个过程与抽象数据类型中的问题分解类似。而搬砖人不需要了解图纸设计如何，设计图纸人员不需要了解施工的地基、砌墙的具体细节，装修工人不用关系图纸和搬砖过程，这就是抽象类型中的信息隐藏。

抽象数据类型的概念可能让初学者不太容易理解。例如线性表的抽象数据类型的描述数据对象集合：线性表的数据对象集合为{a1,a2,a3,····,an},每个元素的类型均为DataType。其中，除了第一个元素a1外，每一个元素有且只有一个直接前驱元素；除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的。

1.5算法

算法（algorithm）是解决特定问题求解步骤的描述，在计算机中表现为有限的操作序列。在数据类型建立起来之后，就要对这些数据类型进行操作，建立起运算的集合即程序。运算的建立、方法好坏直接决定着计算机程序原型效率的高低。

（1）数据结构和算法的关系

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

（2）算法的五大特性

1.有穷性，是指算法在执行有限的步骤之后，自动结束而不是出现无限循环，并且每一个步骤在可接受的时间内完成。

2.确定性，是指算法执行的每一步骤在一定条件下只有一条执行路径，也就是相同输入只能有一个唯一的输出结果。

3.可行性，是指算法每一步骤都必须可行，能够通过有限的执行次数完成。

4.输入，是指算法具有零个或多个输入。

5.输出，是指算法至少有一个或多个输出。

（3）算法的设计要求

1.正确性
2.可读性
3.健壮性
4.时间效率高和存储量低

所以数据结构和算法紧密相关，他们的关系可以从下图中看出：

数据结构与算法

1.6时间复杂度

在进行算法分析时，语句总是执行次数 T(n) 是关于问题规模 n 的函数。进而分析次数T(n)随规模n的变化情况并确定T(n)的数量级。算法的时间复杂度就是算法的时间度量，记作T(n) = O（f（n））。它表示随问题规模n的增大，算法的执行时间的增长率和f（n）的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中，f（n）是问题规模n的某个函数。

算法的时间复杂度是衡量一个算法好坏的重要指标。一般情况下，随着规模n的增大，次数T(n)的增长较慢的算法为最优算法。常见时间复杂度从小到大依次排列：O(1) < O(log2n) < O(n) < O(n²）<O(n³) ····<O(n!)

ADEDE439-EEBF-46ED-A747-77808665EE79.png

一般情况下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次
            }
        }
    }
}
这个算法的时间复杂度就是O(n^3)

//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);
}
这个算法的时间复杂度就是O(n^2)

/*3.对数阶*/
/*2的x次方等于n x = log2n  ->O(logn)*/
void testA(int n){
    int count = 1;         //执行1次
    //n = 10
    while (count < n) {
        count = count * 2;
    }
    
}
这个算法的时间复杂度就是O(logn)

时间复杂度的计算方法

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

1.7空间复杂度

空间复杂度（space complexity）作为算法所需存储空间的量度，记做S(n) = O (f(n))。其中，n为问题的规模；f（n）为语句关于n的所占存储空间的函数。

一般情况下，一个程序在机器上运行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需要存储对数据操作的存储单位。若输入数据所占空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常量，则称此算法为原地工作，空间复杂度为O(1)。
举个例子：

 int n = 5;
 int a[10] = {1,2,3,4,5,6,7,8,9,10};    //算法实现(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;
 }
以上例子只需要用到辅助空间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];
}
这个例子中需要用到b(n）的辅助空间，所以空间复杂度为O(n)