5分钟理解数据结构、算法、编程语言三者的计算思维（附教程分享
我们使用的计算机绝大多数都是冯·诺依曼体系，其理论基础就是”存储程序“概念。数据和操作数据的指令都需要先存储到地址线性表示的内存单元中。数据的一般操作有”增、查、删、改、遍历“等，数据存储需要”存得进、取得出”，需要考虑时间和空间效率，所以要“存数值、存联系”，数据的存储不仅需要保存数据本身，还需要考虑保存数据本身的逻辑关系。
程序要处理的数据有数值类或非数值类两种类型。数值类处理的是纯数值性的信息，如科学和工程计算。数值类数据的关系一般用数学公式或方程来描述。而非数值类问题的数据及数据间的相应关系一般无法用数学公式或方程来描述，如排序问题、检索问题，需要另外设计数据的描述方法和相应的算法来处理。
所以，用计算机解决实际问题，需要对解决的问题进行分析，提炼出问题的两个要素：信息和功能。（数据描述和数据处理的步骤描述，也就是数据结构和算法）。
分析问题中的已知信息，提炼数据和数据之间的联系（数据的逻辑结构），选用合适的存储方式（数据的存储结构）将逻辑结构（数据元素和逻辑关系）存到计算机中，然后在存储结构之上按照自顶向下逐步细化的方法给出算法。这就是程序设计思维的一般过程。
上图中，程序设计将算法”翻译“成相应命令语句及处理形成代码。
一般来说，一个逻辑数据结构可能有多种存储结构，在不同的存储结构之上，数据处理的效率不尽相同。许多时候，确定数据结构后，算法就容易找到了。有些时候事情也会反过来，我们根据特定的算法来选择数据结构与之适应。
程序设计中信息的抽象是用标识符、常量、变量、数组和结构体等描述和记录信息及信息间的关系。
下表是一般编程的解题步骤与从软件工程角度看这些步骤的对应关系。
程序解题软件工程具体工作建模型需求分析阶段提取问题要完成的功能；分析问题的数据对象，找出数据对象之间的关系设计设计阶段数据结构设计、软件的结构设计、算法设计编程编码阶段编写程序代码验证测试软件测试与调试
1 数据类型与抽象数据类型
计算机对数据的处理，就如同工厂对“物料”的处理一样，物料如同数据，工艺如同算法。一般来说，按照“存储程序”概念，数据需要保存到“一格一格”的内存单元中，根据数据种类、数量的多少、数据元素的复杂程度，对应的数据结构和复杂度也会有所区别。如果数据量少，数据元素联系简单，则用简单的基本数据类型如变量、数组即可描述需要处理的数据，用简单的一些表达式即可描述算法。如果数据量大，数据元素联系复杂（普通数学方程无法描述），则需要定义或选择复杂的数据结构（抽象数据类型），如栈、树、图等，以及复杂的算法。
1.1 数据类型（data type)是一组性质相同的值的集合和定义在集合上的一级操作的总称。
1.2 抽象数据类型（Abstract Data Type，ADT）指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算，而不考虑计算机的具体存储结构和运算的具体实现算法。抽象数据类型中的数据对象和数据运算的声明与数据对象的表示和数据运算的实现相互分离。
一个具体问题的抽象数据类型的定义通常采用简洁、严谨的文字描述，一般包括数据对象（即数据元素的集合）、数据元素关系和基本运算三方面的内容。其基本格式可描述如下：
ADT 抽象数据类型名
{
数据对象Data
数据关系Relation
基本运算Operation
}
(Data和Relation一般可以用结构体或类数据成员定义，Operation一般可以用函数（数据结构算法）或类成员函数定义。)
如，线性表的抽象数据类型：
ADT 抽象数据类型名
{
数据对象：任意数据元素的集合
数据关系：除第一个和最后一个外，每个元素都有唯一的直接前驱和唯一的直接后继
基本运算：
ListInsert(&L,i,e); //元素的插入
ListDelete(&L,i,e); //元素的删除
...
}ADT list
2 数据元素及联系（逻辑结构）
现实世界是复杂的，抽象后的数据也有线性、非线性、集合的逻辑关系，而计算机内部的存储单元地址只是线性关系，所以数据元素逻辑关系与实际存储的映射会形成不同的数据结构和算法，会有不同的时间和空间效率。
数据结构的含义包括三个方面－数据的逻辑结构、数据的存储结构以及数据的运算（如增、查、删、改）。数据的逻辑结构体现在数据的联系，数据的存储是数据在计算机中的体现。
3 数据存储（存储结构）
3.1 顺序存储结构 Sequential storage strcture
是采用一组连续的存储单元存放所有的数据元素，也就是说，所有数据元素在存储器中占有一整块存储空间，而且两个逻辑上相邻的元素在存储器中的存储位置也相邻。因此，数据元素之间的逻辑关系由存储单元地址间的关系隐含表示，即顺序存储结构将数据的逻辑结构直接映射到存储结构。
顺序存储结构的主要优点是存储效率高，因为分配给数据的存储单元全用于存放数据元素，元素之间的逻辑关系没有占用额外的存储空间；另外，在采用这种存储方法时可实现对元素的随机存储，即每个元素对应一个逻辑序号，由该序号可以直接计算出对应元素的存储地址，从而获取元素值。顺序存储结构的主要缺点是不便于数据修改，对元素的插入或删除操作可能需要移动一系列的元素。
3.2 链式存储结构 Linked storage structure
在链式存储结构中，每个逻辑元素用一个内存结点存储，每个结点是单独分配的，所有的结点地址不一定是连续的，所以无须占用一整块存储空间。为了表示元素之间的逻辑关系，给每个结点附加指针域，用于存放相邻结点的存储地址，也就是通过指针域将所有结点链接起来，这就是链式存储结构名称的由来。
3.3 顺序存储与链式存储二者优、缺点对比
顺序存储结构链式存储结构存储效率存储效率高，因为分配给数据的存储单元全用于存放数据元素，元素之间的逻辑关系没有占用额外的存储空间；存储空间的利用率低，因为分配给元素的存储单元有一部分被用来存储结点之间的逻辑关系；访问元素可实现对元素的随机存取，即每个元素对应一个逻辑序号，由该序号可以直接计算出对应元素的存储地址，从而获取元素值。由于逻辑上相邻的元素在存储空间中不一定相邻，所以不能对元素进行随机存取。插入和删除不便于数据修改，对元素的插入或删除操作可能需要移动一系列的元素。便于数据修改，在对元素进行插入和删除操作时仅需修改相应结点的指针域，不必移动结点。
3.4 索引存储结构 Indexed storage structure
索引存储结构是指在存储数据元素信息的同时还建立附加的索引表。存储所有数据元素信息的表称为主数据表，其中每个数据元素有一个关键字和对应的存储地址。索引表中的每一项称为索引项，索引项的一般形式为“关键字，地址”，其中“关键字”唯一标识一个元素，“地址”对应该关键字的元素在主数据表中的存储地址。通常，索引表中的所有索引项是按关键字有序排列的。
在按关键字查找时，首先在索引表中利用关键字的有序性快速查找到该关键字的地址，然后通过该地址在主数据表中找到对应的元素。
索引存储结构的优点是查找效率高。缺点是需要建立索引表，从而增加了空间开销。
3.5 哈希（或散列）存储结构 Hashed storage structure
哈希存储结构的基本思想是根据元素的关键字通过哈希（或散列）函数直接算出一个值，并将这个值作为该元素的存储地址。
哈希存储结构的优点是查找速度快，只要给出待查元素的关键字就可立即计算出该元素的存储地址。与前3种存储方法不同的是，哈希存储方法只存储元素的数据，不存储元素之间的逻辑关系。哈希存储结构一般只适合要求对数据能够进行快速查找和插入的场合。
4 数据运算（增、查、删、改）
数据运算是指对数据实施的操作。每种数据结构都有一组相应的运算，最常用的运算有检索、插入、删除、更新和排序等。数据运算最终需要在对应的存储结构上用算法实现，所以数据运算分为运算定义和运算实现两个层面。
5 数据结构具体类型
5.1 线性表包括顺序表和链表两种类型。
5.2 栈：操作都在表的一端(栈顶，top)进行，按先入(插入)后出(删除)的方式管理的线性表；栈相对于线性表来说，不需要考虑数组的下标增减等细节，而直接使用对栈的Push和Pop操作。如回退操作、递归调用、函数调用等可以方便地用到这种受限的线性表结构。
5.3 队列：一端插入(队尾)一端删除(队头)的线性表。
假设有20台包装好的电视机，放到一个房间，房间有一个位置都标有编号。看现实世界中的存储（如何操作可以能存能取）
顺序表找一个连续的四周开放的空间，一台一台按顺序放好；链表不考虑连续的空间，有一台的位置就放一台，但每一台的位置放一张卡片，标明下一台的放置位置；栈20台叠起来放；或者放到一个三端封闭的空间，只有一端可以存、取操作；队列找一个两边封闭的空间，一端放，一端取；
5.4 树结构：反映一种层次的纵向关系，如计算机文件系统的目录结构。其存储的数据逻辑关系是每一个结点都有1个或0个双亲（parent）结点，n个或0个子（child）结点。树结构的基本操作包括：构造、插入、删除、遍历、深度、查找等。堆通常是一个可以被看做一棵树（完全二叉树）的数组对象。
5.5 广义表：包含子结构的线性结构，是线性表的推广，但是一种非线性结构类型。
5.6 图结构：数据结构中的图不是几何平面中的图的概念，而是拓扑意义上的图。通常平面几何或立体几何研究的对象是点、线、面之间的位置关系以及它们的度量性质。拓扑学研究几何图形在连续变形下保持不变的性质。如地铁线路图就是应用了拓扑学的原理。通常在平面几何中，把平面上的一个图形搬到另一个图形上，如果完全重合，那么这两个图形叫做全等形。但在拓扑学中，无论图的大小或者形状怎么变化，只要其中点和线的数量不变，它们就是等价图。
图是一种比线性表和树形结构更为复杂的非线性数据结构，图对结点的前驱和后继个数不加限制，各数据元素之间的关系可以是任意的，描述的是“多对多”的关系。在数据结构中，考虑的是图在计算机中的存储和操作。
图是由顶点和边构成，除了要存储结点的信息，还要存储边的信息。另外，图有无向图、有序图、加权图等、
面向对象偏向结构——在数据结构的基础上加入自我实现的算法 而函数式编程则是偏向函数（算法）——函数也是对象，就是函数的数据化，让算法也可以自由组合。
6 算法
在分析处理的问题、确定的需要的数据结构、完成了数据的存储之后，接下来的事情就是对数据的加工处理了，对问题求解进行精确描述，也就是算法。
不同的问题有不同的解决方法，同一个问题也可能会有多种算法可供选择。
算法有5个特征。
- 有穷性：一个算法必须保证在执行有限步骤后结束，而不是无限的；
- 确定性：算法中每一条指令必须有明确的含义，而不能是含糊不清有歧义的；
- 可行性：每一个操作步骤必须在有限的时间内完成；
- 输入：一个算法可以有多个输入，也可以没有输入；
- 输出：一个算法可以有一个或多个输出，没有输出的算法是没有意义的。
算法的实现由函数完成。算法设计的一般步骤是：
- 设定算法初始条件；
- 确定算法的结束条件；
- 按问题的普遍规律，给出算法处理的流程；
- 考虑临界点或特殊点的处理；
- 考虑异常情况。
常用算法：递推法、递归法、穷举法、贪心算法、分治法、动态规划法、迭代法、分支界限法。
算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法，厄米变形模型，随机森林算法。
7 数据处理（数据结构和算法）综述
实际问题中数据的处理，一是根据问题中的信息，抽象出信息中的数据与联系，并根据问题的功能要求及数据量的大小，选用合适的存储结构；二是根据功能要求划分模块分别处理；三是测试和调试
如，求一个数的阶乘n!
5.1 问题分析：可以先选择一个数值不太大，又不是特殊点的值，如n=5来设计算法的实现。
5.2 测试样例设计：
情形测试数据预期结果问题的一般情形n>1按照n!一般定义得出的值临界点或特殊点n=0，n=1按照n!边界定义得出的值异常情况n<=给出错误或提示信息
5.3 函数接口及功能描述：
5.4 代码实现
double factorial(int n)
{
int i;
double t=1;
if(n<0) return (-1);
for(i=1;i<=n;i++)
{
t=t*i;
}
return(t);
}
5.5 测试结果
万物皆数，是说一切事物都可以编码，都可以用符号或数字表示出来，符号或数字的种类只要两个或两个以上，然后有适当数量的位数，即可表示万物。另外，不仅可以用编码描述事物为数据，数据元素的关系（线性或非线性）亦可用编码进行描述，这种数据元素和数据元素之间联系的描述或编码也就是数据的逻辑结构。数据的逻辑结构需要保存到计算机编址（线性）的存储单元中，这就是数据逻辑结构与存储结构的映射。我们知道，如果是非线性的逻辑结构与线性的逻辑结构的映射，解决起来会稍显复杂，但非线性的逻辑结构都可用复杂度更高的顺序存储或链式存储加以解决。数据的静态存储不是目的，对数据元素有如“增、查、删、改”等的运算并能保持原有的映射才能对数据进行进一步的利用，或者说构造了一种新的抽象数据类型，加上编程语言定义的基本数据类型，是对事物进行数据描述的基本手段。上述所有的一切，皆是数据结构的范畴。
有了数据结构，对需要解决的问题便可以在数据结构的基础上构造数据结构的输入方式、构造表达式、函数、构造数据输出方式，形成详细、明确的步骤，这就是所谓的算法。
当然，一些特殊的问题，有时会先考虑算法，然后构造数据结构。复杂的问题，初期的方案更是在数据结构与算法的相互的选择取舍中不得优化。有了数据结构、算法，选择合适的编程语言进行描述，便可完成代码的编写，通过调试，到最后产生符合解决问题的应用或工具。总之，数据结构和算法以及与之匹配的编程语言便构成了编程的核心。
柠檬为大家准备了一些学习教程，希望可以帮助到大家。
