基本概念和术语
基本概念
区别和详细解释
1、数据(Data)：描述客观事物属性的数、字符及所有能被输入到计算机中并被计算机程序识别和处理的符号的集合。
数据不仅包括整形、实型等数值类型，还包括字符及声音、图像、视频等非数值类型。 数据必须具备两个前提：
（1）可以输入到计算机中；
（2）能被计算机程序处理。对于整型、实型等数值类型，可以进行数值计算；而对于字符数据类型，就需要非数值的处理；而声音、图像、视频等可以通过编码的手段变成字符数据来处理。
2、数据对象(Data Object)：具有相同性质的数据元素的集合。数据对象是数据的一个子集。
什么叫性质相同呢？是指数据元素具有相同数量和类型的数据项，比如人 这个例子，都有姓名、生日、性别等相同的数据项。 既然数据对象是数据的子集，在实际应用中，处理的数据元素通常具有相同性质，在不产生混淆的情况下，我们将数据对象简称为数据。
3、数据元素(Data element)：数据的基本单位，也称结点(node)或记录(record)。
比如 畜类 牛、马、羊、鸡、猪、狗等动物当然就是畜类的数据元素。
4、数据项(Data item)：构成数据元素的不可分割、有独立含义的最小单位，也称域(field)。
一个数据元素由若干个数据项组成。
5、数据结构(Data Structure)：相互之间存在一种或多种特定关系的数据元素的集合。
数据元素都不是孤立存在的，它们之间存在某种关系，这些数据元素之间的关系称为结构(structure)。
数据结构三要素
逻辑结构（数据元素之间的关系）+数据结构（数据结构在计算机中的表示）+数据的运算（运算的定义和实现）。
PS:通常需要用（数据对象、数据关系、基本操作集）这样的三元组来定义数据结构
逻辑结构、数据结构的区分方法
逻辑结构与数据结构的区分判定方法：当一个结构(如数组、链表、树、图)，在逻辑结构中只有一种定义，而在存储结构中却有两种或多种定义，那么这个结构就属于逻辑结构；相反，当此结构在原有基础上加上了某种限定词(如二叉树->线索二叉树)，使得其在存储结构中只有一种定义，那么这个结构就称为数据结构。
举例1：栈属于什么结构？
分析：栈在逻辑结构中只能属于线性结构，而在存储结构中它可以使用顺序存储（数组），也可以使用链式存储（链表），所以说栈是一种逻辑结构。
举例2：线索二叉树属于什么结构？
分析：首先因为二叉树既可以顺序存储又可链式存储，故可以得到二叉树是一种逻辑结构。但是线索二叉树是二叉树加上限定词线索后的链表结构（不能用顺序存储），也就是说，线索二叉树在计算机内部的只有一种存储结构，所以线索二叉树是数据结构。
逻辑结构和数据结构的区别点在于：数据的逻辑结构是独立于在计算机中的存储结构的，数据的存储方式有多种不同的选择。例如栈是一种逻辑结构，它可以用顺序存储也可以用链式存储；而数据结构是既可以描述逻辑结构又可以描述存储结构和数据运算，必须包含这三种元素。所以像顺序表、哈希表、单链表都是数据结构。
算法和算法分析
程序 = 数据结构 + 算法
算法（algorithm） 是为了解决某类问题而规定的一个有限长的操作序列。
算法的五个特性：
- 有穷性：指算法在执行完有限步骤之后，自动结束而不会出现死循环，并且每个步骤都在可接受时间内完成。
- 确定性：算法的每一步骤都具有正确的含义，不会出现二义性。
- 可行性：算法的每一步都是可行的，也就是说，每一步都能通过执行有限次数完成。
- 输入：一个算法有零个或多个输入。
- 输出：一个算法有一个或多个输出。
算法设计的要求：
- 正确性：没有歧义，能正确反映问题需求、能够得到问题的正确答案。
- 可读性：便于阅读、理解和交流。
- 健壮性：当输入数据不合法时，也能做出相关处理，而不至于出现莫名其妙的结果。
- 高效性和低存储量需求：时间高效、空间高效。
衡量算法效率的度量方法分为时间复杂度和空间复杂度。
时间和空间复杂度
时间复杂度：在进行算法分析时，语句总的执行次数T（n）是关于问题规模n的函数，进而分析T（n）随n的变化情况并确定T（n）的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T（n）= O（f（n））。它表示随问题规模的增大，算法执行时间的增长率和f（n）的增长率相同，称为算法的渐进复杂度，简称为时间复杂度。其中f（n）是问题规模n的某个函数。这样用大写 O（） 来体现算法时间复杂度的记法，我们称为大O记法。
推导大O阶的方法
- *用常数1取代运行时间中的所有加法常数。*
- *在修改后的运行次数函数中，只保留最高阶项。*
- *如果最高阶项存在且不是1，则去除与这个项目相乘的常数。*
- *最后得到的结果就是大O阶。*
算法的空间复杂度：通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S（n）= O（f（n）），其中，n为问题规模，f（n）为语句关于n所占存储空间的函数。
存储和存取
存取结构：随机存取和顺序存取
随机存取
随机存取（直接存取,Random Access）指的是当存储器中的数据被读取或写入时，所需要的时间与该数据所在的物理地址无关。
随机存取的微观现实例子就是编程语言中的数组。
随机存取的宏观现实例子就是我们的随机存取存储器(RAM:Random Access Memory)，通俗的说也就是我们电脑的内存条。因为RAM利用电容存储电荷的原理保存信息，所以RAM可以高速存取，且与物理地址无关。
顺序存取
顺序存取(Sequential Access)是一种按记录的逻辑顺序进行读、写操作的存取方法，所需要的时间与该数据所在的物理地址有关。顺序存取表现为:在存取第N个数据时，必须先访问前（N-1）个数据。
顺序存取的微观现实例子就是数据结构中的链表。
顺序存取的现实例子就是我们的录音磁带、光盘、机械硬盘里面的磁盘。磁带、光盘、磁盘上的数据分别存储在不同扇区、不同磁道上，磁盘的读写磁头通过切换不同扇区和磁道来读取物理地址不连续的数据时，该过程中要经过不同扇区和不同磁道上的无关数据，磁盘的读写磁头在切换不同扇区和磁道所需时间也不同，故为顺序存取。
顺序存储
顺序存储是把逻辑上相邻的数据元素存储在物理位置上相邻的存储单元中，数据元素之间的逻辑关系由存储单元的邻接关系来体现。
顺序存储的主要优点：
- 节省存储空间。因为分配给数据的存储单元全用存放数据元素（不考虑c/c++语言中数组需指定大小的情况），数据元素之间的逻辑关系没有占用额外的存储空间。
- 可实现对数据元素的随机存取(直接存取)。即每一个数据元素对应一个元素下标，由该元素下标可以直接计算出来数据元素的物理存储地址。
顺序存储的主要缺点：
不便于数据修改。对数据元素的插入、删除运算时，可能要移动一系列的数据元素。
产生磁盘碎片。因为顺序存储只能使用相邻的一整块存储单元，因此会产生较多的磁盘碎片。
顺序存储的典型实例就是编程语言中的数组。例如，使用顺序表存储集合 {1,2,3,4,5}，数据最终的存储状态如下图所示：
数组中的所有元素存储在一个连续性的内存块中，并通过数组的首地址和元素下标来访问。因此一个数组就是由1个数组首地址和N个数组元素构成，数组不需要像链表一样，链表的每个节点必须存储下一个结点的物理地址，在存储同样多的数据下，数组比链表节省空间。
数组可通过数组的首地址和元素下标来直接存取数组中的没每一个元素，而不需要像链表一样，在存取第N个链表结点的数据时，必须先访问前（N-1）个链表结点。
但对数组的数据元素的插入、删除运算时，可能要移动一系列的数据元素，特别的麻烦，因此顺序存储结构的数组不便于修改。
随机存储
在计算机中用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。它不要求逻辑上相邻的元素在物理位置上也相邻，而是借助指示元素存储地址的指针来表示元素之间的逻辑关系。
随机存储的主要优点：
- 不会产生磁盘碎片。因为随机存储不要求逻辑上相邻的元素在物理位置上也相邻，而是借助指示元素存储地址的指针来表示元素之间的逻辑关系，因此不会产生磁盘碎片。
- 数据修改方便。对数据元素的插入、删除运算时，随机存储不必移动结点，只要改变结点中的指针。
随机存储的主要缺点：
占用空间大。随机存储的每个结点都由数据域和指针域组成，所以相同空间内假设全存满，顺序存储比随机存储可存更多数据。
查找结点时链式存储要比顺序存储慢，且只能实现顺序存取。
随机存储——链式存储
链式存储是随机存储最典型的代表，因此链式存储的定义、优点和缺点就是2.2随机存储中的定义、优点和缺点。
随机存储——索引存储
除建立存储结点信息外，还建立附加的索引表来标识结点的地址，索引表由若干索引项组成，索引项的一般形式是(关键字，地址)。
索引存储的主要优点：检索速度快。
索引存储的主要缺点：增加了附加的索引表,会占用较多的存储空间。
随机存储——散列存储
散列存储，又称Hash存储，是一种将数据元素的存储位置与关键码之间建立确定对应关系的查找技术，即根据元素的关键字直接计算出该元素的存储地址。
散列存储的主要优点：检索、增加和删除节点的操作更快。
散列存储的主要缺点：若散列函数不好，则可能出现元素存储单元的冲突。
电脑磁盘碎片的定义、产生原理和清理原因
文件碎片的定义
电脑碎片即磁盘碎片，磁盘碎片应称为文件碎片。文件碎片是由于文件被分散保存到整个磁盘的不同地方，而不是连续地保存在磁盘连续的簇中而形成的。
文件碎片产生的原因
百度百科中对文件碎片产生列出了以下三大原因：
当应用程序所需的物理内存不足时，一般操作系统会在硬盘中产生磁盘临时交换文件，用该文件所占用的硬盘空间虚拟成内存。虚拟内存通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上。虚拟内存管理程序会对硬盘频繁读写，产生大量的碎片，这是产生硬盘碎片的主要原因。
还有一种情况就是当中间的一个扇区内容被删除后，新写入一个较小的文件，这样在这个文件两边就会出现一些空间，这时候再写入一个文件，两段空间的任意一部分都不能容纳该文件，这时候就需要将文件分割成两个部分，碎片再次产生了。
最常见的就是下载电影之类的大文件，这期间大家一般都会处理一下其它事情，而下载下来的电影文件被迫分割成若干个碎片存储于硬盘中。因此下载是产生碎片的一个重要源头。还有就是经常删除、添加文件，这时候如果文件空间不够大，就会产生大量的文件碎片，随着文件的删改频繁，这种情况会日益严重。
文件碎片产生的原因：
清理文件碎片的原因(为什么要清理文件碎片?)
知道了文件碎片的产生原因之后，我们还有必要了解一下程序运行时磁盘的读写动作。一般运行一个程序时，磁盘驱动器的磁头所做的工作是先搜索该程序运行必需的文件，然后读取数据，最后做读后处理——将数据传送至磁盘高速缓存(Cache)和内存中。搜索时间在硬盘性能指标中被称为平均寻道时间（Average seek time），单位为毫秒（ms），当下主流硬盘的平均寻道时间小于9.5ms。如果能将应用程序的相关文件放在磁盘的连续空间内，磁头搜索的时间将会减少很多。读取时也是如此，磁盘读取位于磁头下方扇区的数据所需时间仅为将磁头移到另一地点再读取相同数据所需时间的五分之一。读盘时，系统先检查数据是否在高速缓存中，如果有则直接读取；如果没有则访问磁盘，也就是读盘。当需要多次读取同一份数据时，Cache的作用很大，但对于第一次读取某个文件，Cache就无能为力了。于是搜索时间和读取时间在很大程度上影响着程序执行的效率。
而磁盘碎片整理是将电脑使用中产生的碎片和冗杂的文件重新整理，让碎片文件融为一体，从而减少了磁盘的寻道时间，因此整体上使得电脑的运行速度得以提升。
机械硬盘/固态硬盘都需要清理文件碎片吗？
先说结论：机械硬盘需要清理文件碎片，固态硬盘不需要清理文件碎片。
机械硬盘需要清理文件碎片的原因已经在上述的四、清理文件碎片的原因(为什么要清理文件碎片?)解释了，因为磁盘碎片整理是将电脑使用中产生的碎片和冗杂的文件重新整理，让碎片文件融为一体，从而减少了磁盘的寻道时间，因此整体上使得电脑的运行速度得以提升。
而为什么说固态硬盘不需要磁盘碎片整理呢？
固态硬盘的擦写次数是有限的。闪存完全擦写一次叫做1次P/E，25nm的固态硬盘寿命约是3000次P/E。碎片整理会大大减少固态硬盘的使用寿命。其实，固态硬盘的垃圾回收机制就已经是一种很好的“磁盘整理”，再多的整理完全没必要。Windows的“磁盘整理”功能是机械硬盘时代的产物，并不适用于固态硬盘。
固态硬盘电荷寻道耗时几乎为0。固态硬盘不用磁头，又因为固态硬盘的存储单元是基于闪存颗粒的电子存储，所以寻道时间几乎为0。持续写入的速度非常惊人，大部分固态硬盘读写速度在500MB/s。
固态硬盘具有TRIM功能。这一功能充当了SSD的军师，它会发出指令让系统告诉固态硬盘哪些数据块不再使用了，否则SSD控制器不知道可以回收这些闲置的数据块。从某种意义上来说，这个功能已经是承担了磁盘碎片整理的工作了。