1.1.1数据类型与数据结构
[]数据（data）
数据是计算机程序的处理对象，它可以是任何能输入到计算机的符号集合（数据是以多种形式呈现的信息），例如描述客观事实数量特征的数值数据以及名称特性的字符数据。
[]数据元素（data element）
数据的基本单位是数据元素，它是表示一个事物的一组数据，有时又称为数据结点，通常作为一个整体进行考量和处理。
[]数据项（date item/field）
一个数据元素可能分为若干成分，构成数据元素的某个成分称做数据元素的数据项。数据项是数据元素的基本组成单位，有时又称为数据域（data field）。数据项是数据结构中讨论的最小单位。
例如：描述一个学生的数据元素，由多个域构成，其中每个域称为一个数据项
姓名 学号 班号 性别 出生日期(年 月 日)
(其中学号称为原子项，年月日称之为组合项)
注：在用高级程序语言编写编写的程序中，必须对程序中出现的每个变量，常量或表达式明确，说明他们所属的数据类型。
[]数据类型(data type)
数据类型是一个“值”的集合和定义在此集合的“一组操作”的总称。它定义了数据的性质、取值范围以及对数据所能进行的各种操作。
注：从这个意义上可称“整数”是一个抽象数据类型。
1.高级程序设计语言提供了一些基本数据类型，这些基本数据类型在数据处理程序中应用得最为频繁。
2.自定义数据类型不能满足程序设计中所有需求，这时可以利用基本类型设计出各种复杂的数据类型，称为自定义数据类型。自定义数据类型，要声明一个“值”的集合和定义在此集合的“一组操作”。
3.为了描述更广泛的数据实体，数据结构和算法描述中更多地使用抽象数据类型：概念意义上的类型和这个类型上的逻辑操作集合。最终演变为在常规数据类型支持下的用户新设计的高层次数据类型，简称ADT（abstract data type）。ADT是指一个数据模型以及定义在该模型上的一组操作。（抽象数据类型有两个重要特征：“数据抽象”和“数据封装”）
抽象数据类型的描述方法
ADT=（D,S,P）
其中：D是数据对象；S是D上的关系集；P是对D的基本操作集。
（数据对象是个特定的数据子集，用来表示实体的特性）
ADT 抽象数据类型名称
{数据对象:<数据对象的定义>
数据关系:<数据关系的定义>
基本操作:<
基本操作名(参数表)
初始条件:<初始条件描述>
操作结果:<操作结果描述>
>}ADT 抽象数据类型名称
[]数据结构
对于一个数据（元素）的集合来说，如果在数据元素之间存在一种或多种特定的关系，则称为数据结构。
数据结构可以看成是关于数据集合的数据类型，是一种特殊的抽象数据类型ADT。
数据结构是关于数据集合的抽象数据类型，它关注三个方面的内容：数据元素的特性，数据元素之间的关系以及由这些数据元素组成的数据结合所允许进行的操作。
数据结构是一个三元组Data_structures=(D,S,P)其中，D是数据元素的有限集，S是D上关系的有限集，P是数据集合所允许进行的操作。
[]数据结构的两个方面
1.逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合的若干关系来表示。侧重于数据集合的抽象特性。
2.物理结构是数据结构在计算机中的表示和实现，故又称“存储结构”，数据的存储结构依赖于计算机，它是逻辑结构在计算机中的体现。
1.1.2数据的逻辑结构
数据的逻辑结构侧重于数据集合的抽象特性，它描述几何中数据元素之间的逻辑关系，按照数据集合中数据元素之间存在的不同特性的逻辑关系，数据结构可以分为三种基本类型：
1.线性结构：每个数据元素只有一个前驱数据元素和一个后继数据元素，逻辑上的顺序关系。数组是最基本的，具有线性结构的集合，其它常用的线性结构有线性表，栈，队列等。
2.树结构：每个数据元素只有一个前驱数据元素，可以有零个或若干个后继数据元素，层次关系。
3.图结构：每个数据元素可有零个或若干个前驱数据元素，零个或若干个后继数据元素，网状关系。
图示法表示数据的逻辑结构
圆圈表示一个数据元素（数据节点），圆圈中的字符或数字表示数据元素的标记或数据元素的值，连线表示数据元素间的逻辑关系。
1.1.3数据的存储结构
数据集合在计算机中的存储表示方式称为数据的存储结构，也称为物理结构。
数据的逻辑结构独立于计算机，而存储结构则依赖于计算机。
有两种基本的存储结构：
1.顺序储存结构
顺序存储结构将数据集合的元素存储在一块地址连续的内存空间中，并且逻辑上相邻的元素在物理上也相邻。
顺序存储结构中只包含元素本身的信息，典型的数据结构是数组。
注：当不需要频繁插入和删除时，可以采用顺序存储结构，此时占用的存储空间少。
2.链式储存结构
链式存储结构使用称为链接点的扩展类型储存各个数据元素，结点由数据元素域和指向其他节点的指针域组成，链式储存结构使用指针把相互关联的结点链接起来，逻辑上相邻的数据元素在物理上不一定相邻，数据间的逻辑关系表现在结点的链接关系上。
注：当插入和删除操作很频繁时，需要采用链式存储结构。此时虽然占用的存储空间较多，但操作的时间效率高，这种方案以储存空间为代价取代了较高的时间效率。
1.1.4数据的操作
对数据结构对象进行的某种处理称作数据的操作。
每种特定的逻辑结构都有一个自身的操作集合，不同的逻辑结构有不同的操作。
数据的操作一般是根据数据的逻辑结构定义的，但操作的具体规则则与数据的存储结构有关。
1.2.1算法
算法是对特定问题求解过程的一种描述，是解决该问题的一个确定的，有限长的操作序列。
一个算法必须满足以下五个重要特性：确定性，可行性，有穷性，有输入，有输出。
（有输入：算法有零个或多个输入数据，有的输入量需要在算法执行过程中输入，而有的算法表面上没有输入，实际上输入已被镶入算法之中）
计算模型：指算法实现技术的模型。
具有两方面的特性：
1.使用通用单处理器在同一时间执行一条指令，并且指令的执行的指令是确定的，程序以指令一条接一条的执行的方式实现算法。
2.随机存储机模型，处理器可以随机访问存储器。
算法的描述方式：文字，流程图，高级程序设计语言，类似于高级程序设计语言的伪码。
无论用哪种描述形式，都要体现出的是算法是由语义明确的操作步骤组成的有限操作序列。
算法与数据结构的关系
数据的逻辑结构，存储结构以及对数据所进行的操作，三者是相互依存的。
在研究一种数据结构时，总是离不开研究对这种数据结构所能进行的各种操作，因为这些操作从不同角度体现了这种数据结构的某种性质，只有通过研究这些操作的算法，才能更清楚地理解这种数据结构的性质。
反之，每种算法都是建立在特定的数据结构上的。数据结构和算法之间存在着本质的联系，失去了一方，另一方就没有意义。
1.不同的逻辑结构需采用不同的算法。
2.同样的逻辑结构，因为存储结构的不同，而采用不同的算法。
3.同样的逻辑结构和存储结构，因为要解决问题的要求不同，而采用不同的算法
1.2.2算法设计的要求
1.正确性
2.可读性
算法的可读性主要体现在两方面：一是被描述算法中的类名、对象名、方法名等的命名要见名知意；二是要有足够多的清晰注释。
3.健壮性
当输入的数据非法时，算法应当恰当地做出反应或进行相应处理，而不是产生莫名其妙的输出结果。错误或异常处理：处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。
4.高时间效率
算法的执行时间应满足问题的需求，执行时间短的算法称为高时间效率的算法。
5.高空间效率
算法在执行时一般要求额外的内存空间，内存要求低的算法称为高空间效率的算法。
注：当算法的高时间效率和高空间效率矛盾时，在很多时候首先考虑算法的时间效率目标。
1.2.3算法效率分析
1.算法的时间复杂度
算法的执行时间等于所有语句执行时间的总和，它取决于控制结构和原操作两者的综合效果。通常选取一种对所研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间度量。
算法重复执行原操作的次数是算法所处理的数据个数n的函数f(n)，其渐进特性称为该算法的时间复杂度。
2.算法的空间复杂度
算法的执行除了需要储存空间来寄存本身所用指令，变量和输入数据外，也需要一些对数据进行操作的工作单元和储存一些为实现算法所需的辅助空间。与算法的时间复杂度概念类似，算法在执行时所需辅助内存空间大小与待处理的数据量之间的关系称为算法的空间复杂度，也用O(f(n))的形式表示。
如冒泡排序算法的空间复杂度为O(1)；
归并排序算法的空间复杂度为O(n)。
这是我自己上个学期整理的笔记。
整理不易，如果对你有所帮助的话，欢迎点赞+转发。
最后附上我的公众号，目前是关于文学方面的（主要是诗歌） ，里面有一些资源无偿分享，感兴趣的朋友可以关注一下。
网友评论