数据结构与算法

1.数据结构

数据结构是描述多个数据之间的逻辑结构和物理结构。

根据定义，将数据结构按逻辑结构分类：

1.线性结构

对于线性接口，除去第一个节点与最后一个节点，各个节点都具有一个前驱结构与后继结构

2.树形结构

树状结构是一种非线性结构，模拟自然界中树的分支层次，用来表示数据之间的一对多关系。‌‌ 树形结构看起来像倒挂的树，根节点在上方，叶子节点在下方，由节点和边组成，每个非根节点有且仅有一个父节点，但是可以有若干个子节点。

3.图形结构

图形结构的各个节点可以像图像一样进行任意组合，其可以有多个前驱节点和后继节点，是一种多对多的数据结构关系。

4.集合结构

集合结构是一种松散的数据结构关系，其各个数据之间松散无固定连接关系。

按照物理结构可以分为顺序结构和离散结构，顺序结构的数据存储在一片连续的存储空间中，离散结构存储在各个离散的空间中，各个空间通过指针与其他空间进行链接。

顺序结构无需空间保存其他空间的地址，其空间使用相对较小，但是在实际工程中，通常难以申请一片连续的内存空间，链式结构则完美地解决了这个问题。

数据结构通常还被分为线性结构与非线性结构两类，线性结构主要包括数组、链表、栈、队列等，非线性结构包含树、堆、散列表、图等。数组。

数据的访问形式有随机访问和顺序访问，随机访问能力是指在同等时间内访问数据的能力

2.算法

算法是计算或解决问题的步骤，算法具有有穷性、确定性、可行性、输入项、输出项的特征。

其中有穷性表示程序执行必须在有限次数内完成，每一次必须在有限时间内完成；确定性表示每一条语句都必须有准确性解释，不允许出现二义性；可行性表示程序中的每一个复杂语句都可以拆分为基本指令，且每条基本指令必须能够在有限时间内完成；输入项与输出项则表示算法的输入参数/条件以及算法的输出结果，二者均可以是一个或多个。

程序=数据结构+算法，衡量数据结构与算法选择是否合理通常采用时间复杂度与空间复杂度两个指标进行。

时间复杂度是算法程序的语句执行次数，一般用大写的O来表示，通过估算程序的运行次数得到多项式，保留其中影响最大的一项，并去除系数。

int main(){
    for(int i = 0; i < n; i++){        //其中int i = 0执行1次，i < n执行n次，i++执行n次
        printf("hello world\n");     //执行n次
    }
    return 0;
}

对于上述程序，T=3n+1，影响最大项为3n，舍去系数后，时间复杂度为O(n)