第一章  绪论

鉴于本人懒得不得了，忘得贼快的体质，已近6月终于决定重新梳理一遍知识框架抽打自己。希望明年看到此贴，我能留下心满意足的眼泪

1.1数据结构的基本概念

 

1.1.1基本概念和术语

1. 数据：数据是信息的载体， 是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。（人类的认知转换为计算机能够识别和处理）
2. 数据元素：数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。（数据项：小猫的年龄毛色耳朵嘴等，数据元素：这只小猫）
3. 数据项：数据项是数据不可分割的最小单元。
4. 数据对象：性质相同的数据元素的集合，是数据的子集。性质：指数据元素具有相同数量和类型的数据项（一群蓝猫）
5. 数据类型：数据类型是一个值的集合和定义在此集合上的一组操作的总称。（节约内存因地制宜）
   1 ）原子类型。其值不可再分的数据类型。（int,float,double）
   2 ）结构类型。其值可以再分解为若干成分（分量）的数据类型。（自定义的结构体，类）
   3 ）抽象数据类型。一个数学模型以及定义在模型上的一组操作。通常是对数据的抽象，定义了数据的取值范围以及对数据操作的集合。（实现与操作分离，从而实现封装）下图源自：大话数据结构

   

    

6. 数据结构：相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中， 数据元素都不是孤立存在的，它们之间存在某种关系，这种数据元素相互之间的关系称为结构（ Structure ）。逻辑结构、存储结构和数据运算。

     数据的逻辑结构和存储结构是密不可分的两个方面， 一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。

1.1.2数据结构三要素

1. 数据的逻辑结构：数据对象之间的相互关系（下图来源王道书）

   

   1. 集合结构。集合中数据元素除了属于一个集合外没有其他关系。
   2. 线性结构。一对一的关系
   3. 树形结构。一对多的关系
   4. 图状结构或网状结构。多对多的关系
2. 数据的存储结构：数据结构在计算机中的存储形式（又称映像），也称物理结构。它包括数据元素的表示和关系的表示。如何将数据元素存储到存储器，数据的存储结构主要有顺序存储、连式存储、索引存储、散列存储。
   1. 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。优点：可以实现随机存取，每个元素占用最少的存储空间： 缺点：只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。
   2. 链式存储：不要求逻辑上相邻物理地址也相邻。存储关系不能反映逻辑关系，需要一个指针存放数据元素的地址，通过地址找到关联的数据元素。优点：不会出现碎片化情况，充分利用存储单元；缺点：每个元素存储指针占用额外空间，只能实现顺序存取。（上传下达，无法越级）
   3. 索引存储：在存储元素信息的同时， 还建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）。优点：检索速度快；缺点：附加的索引表额外占用存储空间。另外，增加和删除数据时也要修改索引表， 因而会花费较多的时间。
   4. 散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希（ Hash ）存储。优点：检索、增加和删除结点的操作都很快； 缺点：若散列函数不好， 则可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。
3. 数据的运算：包括运算的定义和实现。（定义：指出运算的功能即逻辑结构；运算：指出运算具体操作步骤即存储结构）

 

 

1.2算法和算法评价

1.2.1算法的基本概念

1. 算法：解决特定问题的求解步骤的描述，在计算机中是指令的有限序列，没条指令表示一个或多个操作（武功秘籍智慧的套路）
2. 算法特性：                                                                                                                                                                                1 ）有穷性。执行有穷步之后结束，且每一步都可在有穷时间内完成。
   2 ）确定性。算法每条指令必须有确切的含义， 对于相同的输入只能得出相同的输出。（类似函数）
   3 ）可行性。算法中描述的操作者可以通过已经实现的基本运算执行有限次来实现。                                                              4 ）输入。一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
   5 ）输出。一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

1.2.2算法的效率的度量

存在一个整数N，当n>N时，任意f(n)>g(n)，则f(n)的增长大于g(n)

1. 时间复杂度：一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n)它是该算法问题规模n 的函数,时间复杂度主要分析T(n)的数量级。                                                                                                                     1)加法规则                                                                                                                                                                                                                                                             2)乘法规则                                                                                                                                                                                                                                                                   3)常见渐进复杂度                                                                                                                                                                                                                                                           
2. 空间复杂度：算法的空间复杂度S(n）定义为该算法所耗费的存储空间，它是问题规模n 的函数。一个程序在执行时除需要存储空间来存放本身所用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和l存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身，和算法无关，则只需分析除输入和程序之外的额外空间。算法原地工作是指算法所需的辅助空间为常量， 即0(1 ） 。