数据结构（C语言）

数据结构绪论

对于学完基础语法的你们来讲，去做一般的开发或者说是稍微有点难度的开发，在去借鉴别人的代码，工作是完全够了的，但是，做大型的项目或者难度很大的项目的时候，那么这些知识还不够，还得继续学习，那就是要学习数据结构，从本质上去理解和实践这些知识点，加以融会贯通，这是对自己学习能力和编写代码能力一个质的飞跃。

今天简单的介绍一下数据结构

什么是数据结构？

数据结构就是数据存储的方式，那我们学习数据结构，就是去研究数据的存储方式。

我们都知道，数据是存储在我们计算机存储空间里面的，那么这些数据存储他是有一定的规律的额，所谓无规矩不成方圆，如果没有规律，那我们计算机存储空间就乱套了，那么，我们向计算机存储数据，只有一个目的，那就是让数据得到保留，并且能够为我们所用（能够取出数据）。而对于数据结构来讲，有很多种，那么我们应该选择哪一种数据结构进行存储呢？这是我们值得去研究的，那么学习数据结构就是去研究这些数据结构类型的特点。

例如

#include <stdio.h>
#include <stdlib.h>
int main(){
    int a[] = {1,2,3,4,5};
    int i;
    for(i = 0;i < sizeof(a)/sizeof(int);i++){
        printf("a[%d] = %p\n",&a[i]);//打印数组中的每一个元素的地址
    }    
    exit(0);//函数正常结束
}
结论，通过上面这个例子的运行结果我们可以看出，数组在我们的内存区域块存储的时候，是遵守了一定的规律的。
以此同时：int a = 1;int b = 2;这样的初始化定义一样的是有一定的关系的，后面我们会介绍。

对于数据结构来讲，它不是单纯只是一个简单的数据的存储，数据结构就是把复杂话的数据进行整理，让这些数据变得有规律，方便我们工作人员进行操作。而存储方式很多，我们需要选取最优的那一种方式进行数据的存储。

数据结构的分类

数据结构可以分为线性结构、图存储结构、树结构。线性结构可以在细分为顺序表、链表、栈和队列，树结构可以细分为普通树、二叉树等。当然，这些在后面我们会一一去学习。

算法

对于学习数据结构，那么就应该要提到一个东西，那就是算法，算法和数据结构有不解的渊源，当然有的教材把算法单独拿出来和数据结构一样，而有的数就是把算法归纳到数据结构里面的，但是这些都不重要，重要的是，我们都要去学习和理解。

什么是算法？

算法通俗的说，就是去解决问题的办法，但是，不同解决问题的办法，就有不同的过程，在实现同一个结果的时候，所消耗的资源以及时间是不一样的。所以，算法也分好算法和一般算法，在这里大家可能对算法有点误解，算法不是说的那么高深，平时我们编写程序时，其实就是在写算法。那是因为我们在进行编程的时候，我们脑海里要去想如何实现，可以是数学的方式去设想，只不过在具体实现的时候，需要通过我们代码语法和逻辑进行实现而已，而针对于不同的人，那么思考问题的方式可能不同，那么写出来的代码也就不同，就会有好与不太好的算法的区分，那么如何去评判一个算法好与不好呢？

** 评判一个“好”算法的标准**

对于一个问题的算法来说，之所以称之为算法，首先它必须能够解决这个问题，这个我们称为准确性）。其次，通过这个算法编写的程序要求在任何情况下不能崩溃（称为健壮性）。
如果准确性和健壮性都满足，接下来，就要考虑最重要的一点：通过算法编写的程序，运行的效率怎么样。

运行效率体现在两方面：1、算法的运行时间。（称为“时间复杂度”）
2、运行算法所需的内存空间大小。（称为“空间复杂度”）

==好算法的标准就是：在符合算法本身的要求的基础上，使用算法编写的程序运行的时间短，运行过程中占用的内存空间少，就可以称这个算法是“好算法”。==

时间复杂度的计算

对于时间复杂度来讲，我们都知道要去实现一个算法，不可能会把所有的算法都通过程序的方式进行展示出来，并且让计算机去运行，这样做的话就已经耗时了，做的是无用功、效率低下，所以，在实际开发，作为一个优秀的程序员要学会去估算算法的时间复杂度，可能大家不太懂，通俗一点就是你这个算法实现这个功能大概所需要的时间。

---

在讲嵌入式C语言基础的时候，给大家讲过程序是由三种结构构成：顺序结构、分支结构、循环结构，对于前面两个，代码只执行一次，而对于循环结构来讲，这个需要看循环的次数，所以需要的时间也和循环次数有关系。
由于程序员喜欢通过估算算法需要的时间，并且循环结构对算法执行所消耗的时间有很大的关系，所以对于时间复杂度的计算，我们主要是通过代码的循环次数，这个我们一般可以称为“频度”，所以，次数越少，那么算法的时间复杂度就越低，算法就越好。

** example**

#include <stdio.h>
#include <stdlib.h>
int maia(){
    int i = 0,j = 0,sum = 0,n = 0;
    /*第一个，只执行一次*/
    ++n;
    sum += n;
    /*第二个，执行循环100次*/
    for(i = 1;i <=100;i++);{++n;sum +=n;}
    /*第三个，执行循环100 * 100次***/
    for(i = 1;i <=100;i++)
        for(j = 1;j <= 100;j++){
            ++n;
            sum += n;
        }
    exit(0);
}

时间复杂度的表示

O(频度)，这里需要注意一下，这个是大写的字符O，不是0，对于上面这个例子，第一次可以表示为O(1),第二个就是O(100),第三个是O(100*100)。

---

时间复杂度的估算

对于上面这个程序，整体执行的频度是O(1+100+100100)，那么假设N = 100,那么就可以得到O（1+N+N^{2）;对于学过高数求极限的同学都知道，当N的值很大的时候，那么这个值就可以等价于N}2;所以，上面的这个例子，它的频度可以是100100。

一般计算方法

简化的过程总结为3步：
1、去掉运行时间中的所有加法常数。（例如 nn+n+1，直接变为 nn+n）
2、只保留最高项。（nn+n 变成 nn）
3、如果最高项存在但是系数不是1，去掉系数。（n*n 系数为 1）

常用时间复杂度的排序

O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n2)平方阶 < O(n3)(立方阶) < O(2的n次方) (指数阶)

空间复杂度

对于空间复杂度和时间复杂度来讲，就好比鱼与熊掌不能兼得，意思就是说我们可以通过时间换取空间，同时也可以通过空间换取时间，对于空间复杂度，我们在进行编程时，尽量在算法的时间复杂度满足的情况下，给予最大的空间。举一个简单的例子，大家用百度浏览器和迅游浏览器的时候，可能大家觉得百度访问速度是不是要快一点，这是因为它占用的内存空间大，用空间换取了时间。

总结

对于今天所介绍的知识，只是一些概念性的知识，希望大家有所了解，后面我们会通过例子对数据结构进行详细的讲解，当然数据结构很难，是真的难，这里只希望大家入门就好，有了基础在去深究。本篇文章里面的内容如果有误，欢迎大家指正，非常感谢，祝大家学习愉快。