如需转载，请根据 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 许可，附上本文作者及链接。
本文作者： 执笔成念
作者昵称： zbcn
本文链接： https://1363653611.github.io/zbcn.github.io/2020/02/20/al_00%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95%E6%A6%82%E8%BF%B0/
数据结构
概述
- 主要任务是通过分析数据对象的结构特征,包括逻辑结构与数据对象之间的关系,然后把逻辑结构表示成计算机计算机可实现的物理结构,从而便于计算处理.
概念术语
- 数据(data) 是能被计算机处理的符号或者符号集合,含义广泛,可理解为”原材料”.如字符,图片,音视频.
- 数据元素(data element) 是数据的基本单位.eg:一张学生统计表
- 数据项(data item): 数据元素的最小单位. eg:一张学生统计表,里面有:编号,姓名,性别,籍贯
- 数据对象(data object) : 是性质相同的数据元素的集合,是数据的一个子集.eg:正整数N={1，2，3，····}。
- 数据结构(data structure):是数据的组织形式,数据元素之间存在一种或者多种特定关系的数据元素集合的组织形式.
- 数据类型(data type): 是按照数据值的不同进行划分的可操作性.
数据的逻辑结构
逻辑结构(logic structure) 是指数据中数据元素之间的相互关系. 数据元素之间存在不同的逻辑关系构成了一下4中结构类型.
- 集合结构: 集合的数据元素没有其他关系,仅仅是将他们统一收纳在一个称作为”集合”的容器中.
- 线性结构: 线性的数据元素结构关系是一对一的,并且是一种先后的次序. eg:就像a-b-c-d-e-f-g·····被一根线穿连起来
- 树性结构:树形的数据元素结构是一对多的. eg:像公司的部门级别，董事长-CEO\CTO-技术部\人事部\市场部…..。
- 图结构:图数据元素的关系是多对多的. eg:常见的各大城市的铁路图，一个城市有很多线路连接不同城市(北京地铁)
数据的存储（物理）结构
存储结构(storage structure)也称作物理结构(physical structure),是指数据的逻辑结构在在计算机中的存储形式. 数据的存储结构一般可以反映数据元素之间的逻辑关系,分为顺序存储结构和链式存储结构.
- 顺序存储结构: 是把数据元素放置在一组存储地址连续的存储单元里.其数据的逻辑关系和物理关系是一致的.
- 链式存储结构: 把数据元素放置在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的.数据元素的存储关系并不能影响其逻辑关系,需要借助指针来表示元素之间的逻辑关系.
总结: 数据的逻辑结构和物理(存储)结构是密切相关的,任何一个算法的设计都取决于选定的数据的逻辑结构.而算法的实现依赖于数据的存储结构.
抽象数据类型
抽象数据类型(abstract data type): 是描述具有某种逻辑关系的数据类型,并对在数学模型上进行的一组操作. 抽象数据类型描述的是一组逻辑上的特性, 与计算机内部表示无关. 计算机中的整数数据类型是一个抽象数据类型. 不同的处理器可能的实现方式不同,但其逻辑特性相同的,即 加.减.乘.除 等运算是一致的. “抽象”的意思是数据类型的数学抽象特性而不是指它们的实现方法。抽象数据类型体现了程序设计中的问题分解,抽象,信息隐藏等特性. 可以把现实中的大问题分解成多个规模小而且容易解决的小问题.然后建立起一个能被计算机处理的数据,并把每个功能模块的实现细节作为一个独立的单元，从而使具体实现过程隐藏起来。就类似建一栋房子，分成若干个小任务，如地皮规划、图纸设计、施工、装修等，整个过程与抽象数据类型中的问题分解类似。而搬砖人不需要了解图纸设计如何，设计图纸人员不需要了解施工的地基、砌墙的具体细节，装修工人不用关系图纸和搬砖过程，这就是抽象类型中的信息隐藏。
抽象数据类型的概念可能让我们不容易理解. 例如线性表的抽象数类型的描述对象集合:线性表的数据对象集合为{a1,a2,a3,····,an},每个元素的类型均为DataType。其中，除了第一个元素a1外，每一个元素有且只有一个直接前驱元素；除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的。
算法
算法(algorithm) 解决特定问题求解步骤的描述，在计算机中表现为有限的操作序列。在数据类型建立起来之后，就要对这些数据类型进行操作，建立起运算的集合即程序。运算的建立、方法好坏直接决定着计算机程序原型效率的高低。
数据结构和算法的关系
两者既有联系又有区别. 联系: 程序=算法+数据结构 数据结构是算法实现的基础,算法总是要依赖于某种数据结构来实现的. 算法的操作对象是数据结构. 区别是数据结构关注的是数据的逻辑结构和存储结构,有一基本操作. 而算法更加关注的是在数据结构的基础上解决实际问题. 算法是编程思想，数据结构则是这些思想的基础。
算法的5 大特性
- 有穷性: 是指算法在执行有限的步骤之后，自动结束而不是出现无限循环，并且每一个步骤在可接受的时间内完成。
- 确定性: 是指算法的每个执行步骤在一定条件下只有一条执行路径,也就是相同的输入只能有一个唯一的输出结果.
- 可行性: 算法的每个步骤都必须可行,能够通过有限的执行次数完成.
- 输入: 算法具有零个或者多个输入
- 输出: 是指算法至少有一个或多个输出。
时间复杂度
在进行算法分析时,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!)
空间复杂度
空间复杂度(space complexity) ,作为算法需存储空间的量度,记做S(n) = O (f(n)). 其中，n为问题的规模；f（n）为语句关于n的所占存储空间的函数。
一般情况下，一个程序在机器上运行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需要存储对数据操作的存储单位。若输入数据所占空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常量，则称此算法为原地工作，空间复杂度为O(1)。
递归和非递归
在数据结构与算法实践过程中, 递归式一种分而治之,是一种将复杂的问题转换为简单问题的方法. 使用递归编写的程序简单、结构清晰, 程序的正确性很容易证明，不需要理解递归调用的具体细节。
- 函数的递归： 就是函数自己调用自己，即一个函数在调用其他函数的过程中，又出现对自身的调用，这种函数成为递归函数。函数的递归调用就是自己调用自己，可以直接调用自己，也可以间接自己调用自己。其中，在函数中直接调用自己称为函数的直接递归调用；如果函数f1调用了函数f2又再次调用了函数f1，这种调用的方式我们称之为间接递归调用。
