数据结构 第一章 绪论

概念

数据data：是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素(data element:是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据对象(data object)：是性质相同的数据元素的集合，是数据的一个子集。

数据结构(data structure)又称逻辑结构，是相互之间存在一种或多种特定关系的数据元素的集合。通常有以下四类基本结构：集合、线性结构、树形结构、图状结构或网状结构。

存储结构（物理结构）：是数据结构在计算机中的表示（又称映像）。

数据类型(data type)：是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型(Abstract Data Type)（ADP表示）：是指一个数学模型以及定义在该模型上的一组操作，可细分为：原子类型、固定聚合类型、可变聚合类型。

• • 由用户定义，从问题抽象出数据类型（逻辑结构）
  • 还包括定义在数据模型上的一组抽象运算（相关操作）
  • 不考虑计算机内的具体存储结构与运算的具体实现算法

抽象数据类型的形式定义 可用DSP三元组表示

• • D是数据对象
  • S是D上的关系集
  • P是对D的基本操作集

**一个抽象数据类型的定义格式**
ADP 抽象数据类型名{
	数据对象:<数据对象的定义>
	数据关系:<数据关系的定义>
	基本操作:<基本操作的定义>
}ADP 抽象数据类型名

其中数据对象和数据关系的定义用伪代码描述

基本操作的定义格式为：
- 基本操作名
- 初始条件：<初始条件描述>
- 操作结果：<操作结果描述>

基本操作者定义格式说明:
参数表：  赋值参数 只为操作提供输入值
		引用参数以&打头，除可提供输入值，还将返回操作结果
初始条件：描述操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回		 相应出错信息。若初始条件为空，则省略之。
操作结果：说明操作正常完成之后，数据结构的变化状况和应返回的结果

抽象数据类型的表示和实现

• 抽象数据类型可以通过固有的数据类型（如整型，实型，字符型等）来表示和实现
  • 即利用处理器已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作

算法和算法分析

程序与算法

• 程序＝数据结构+算法
• 数据结构通过算法来实现操作
• 算法根据数据结构设计程序

算法的特性（确定，有穷，可行，输入，输出）

1.有穷性：算法在执行有限步骤之后，自动结束而不会出现无限循环，并且每一个步骤都在可接受的时间范围内完成。

2.确定性：算法的每一个步骤都有确定的含义，不会出现二义性(不会有歧义)。

3.可行性：算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现。

4.输入：一个算法有零个或多个输入。当用函数描述算法时，输入往往是通过形参表示的，在它们被调用时，从主调函数获得输入值。

5.输出：一个算法有一个或多个输出，它们是算法进行信息加工后得到的结果，无输出的算法没有任何意义。当用函数描述算法时，输出多用返回值或引用类型的形参表示。

算法的设计要求

好的算法应该具有正确性、可读性、健壮性、时间效率高和存储量低的特征

1.正确性(Correctness)：能正确的反映问题的需求，能得到正确的答案。

分以下四个层次：

a.算法程序没有语法错误；

b.算法程序对n组输入产生正确的结果；

c.算法程序对典型、苛刻、有刁难性的几组输入可以产生正确的结果；

d.算法程序对所有输入产生正确的结果；

但我们不可能逐一的验证所有的输入，因此算法的正确性在大多数情况下都不可能用程序证明，而是用数学方法证明。所以一般情况下我们把层次3作为算法是否正确的标准。

2.可读性(Readability)：算法，首先应便于人们理解和相互交流，其次才是机器可执行性。可读性强的算法有助于人们对算法的理解，而难懂的算法易于隐藏错误，且难于调试和修改。

3.健壮性(Robustness)：当输入的数据非法时，好的算法能适当地做出正确反应或进行相应处理，而不会产生一些莫名其妙的输出结果。【健壮性又叫又名鲁棒性即使用棒子粗鲁地对待他也可以执行类似于Java预料到可能出现的异常并对其进行捕获处理】处理出错的方法，不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。

4.(高效性)时间效率高和存储量低

算法分析

算法分析的目的是看算法实际是否可行，并在同一问题存在多个算法时可进行性能上的比较，以便从中挑选出比较优的算法。

(时间效率)运行时间的长短和(空间效率)占用内存空间的大小是衡量算法好坏的重要因素

衡量算法时间效率的方法主要有两类：事后统计法和事前分析估算法

• 事前分析法 指一个算法在计算机上运行所耗费的时间大致可以等于计算机执行一种简单的操作(如赋值，比较，移动等)所需要的时间与算法中进行简单操作次数的乘积。一条语句的重复执行次数称作语句频度(Frequency Count)。语句的执行要由源程序经编译程序翻译成目标代码，目标代码经装配再执行，因此语句执行一次实际所需的具体时间是与机器的软、硬件环境（如机器速度、编译程序质量等）密切相关的。设每条语句执行一次所需的时间均是单位时间，则一个算法的执行时间可用该算法中所有语句频度之和来度量。所谓的算法分析并非精确统计算法实际执行所需时间，而是针对算法中语句的执行次数做出估计，从中得到算法执行时间的信息。

• 事后分析法 需要先将算法实现然后测算其时间和空间开销。这种方法的缺陷很显然，一是必须把算法转换成可执行的程序，如果编辑出来发现它根本是很糟的算法，不是竹篮打水一场空吗？二是时空开销的测算结果依赖于计算机的软硬件等环境因素，这容易掩盖算法本身的优劣。三是算法的测试数据设计困难，并且程序的运行时间往往还与测试数据的规模有很大关系，效率高的算法在小的测试数据面前往往得不到体现。比如10个数字的排序，不管用什么算法，差异几乎是零。而如果有一百万个随机数字排序，那不同算法的差异就非常大了。那么我们为了比较算法，到底用多少数据来测试，这是很难判断的问题。所以我们通常采用事前分析估算法。

求两个n阶矩阵的乘机算法

【i从1~n首先判断条件是否成立，条件满足执行循环体并i++，i=n+1判断条件是否成立条件不满足，退出循环，判断n+1次循环体执行了n次】

渐进时间复杂度

对于稍微复杂一些的算法，计算出算法中所有语句的频度通常是比较困难的。通常，算法的执行时间是随问题规模增长而增长的，因此对算法的评价通常只需考虑其随问题规模增长的趋势。

这种情况下，我们只需要考虑当问题规模充分大时，算法中基本语句的执行次数在渐近意义下的阶。

基本语句：执行次数最多；对算法运行时间贡献最大；嵌套最深的语句。

分析算法时间复杂度的基本方法

1.找出语句频度最大的那条语句作为基本语句；

2.计算基本语句的频度，得到问题规模n的某一个函数；

3.取其数量级用O表示

忽略所有低次幂项和最高次幂的系数，这样可以简化算法分析，也体现出了增长率的含义。

常数阶

实际上，如果算法的执行时间不随问题规模n的增加而增长，算法中语句频度就是某个常数。即使这个常数再大，算法的时间复杂度都是O(1)。

线性阶

给小灰一个长度为10cm的面包，小灰每三分钟吃掉1cm，那么他吃掉整个面包要多久？

答案自然是3*10=30min

如果面包的长度为n cm呢？

此时吃掉整个面包需要3*n即3n分钟。

如果用一个函数来表达吃掉整个面包所需要的时间可以记作T(n)=3n(n表示面包的长度即处理的数据的规模)

对数阶

给小灰一个长度为16cm的面包，小灰小灰每5min吃掉面包剩余长度的一半，第1min吃掉8cm，第2min吃掉4cm，第三min吃掉2cm…那么小灰把面包吃得只剩下1cm，需要多少天呢？

这个问题翻译一下，就是数字16不断地除以2，除几次以后的结果等于1？这里要涉及到数学当中的对数，以2位底，16的对数，可以简写为log216。(下文对函数的底数全部省略)

因此，把面包吃得只剩下1寸，需要 5* log₂16=5*4=20 min

如果面包的长度为n cm呢？

此时吃掉整个面包需要5* log n分钟记作T(n)=5*log n

即f(n)≤log₂n，取最大值f(n)=log₂n

所以该程序段的时间复杂度T(n)=O(log₂n)

也可以给n几个具体的值找规律

平方阶

由于当i=0时内循环执行n次，当i=1时内循环执行n-1次，…，当i=n-1时内循环执行1次总执行次数

n+(n-1)++(n-2)+…+1=n(n+1)/2

时间复杂度是O(n^2)

立方阶

**最好、最坏和平均时间复杂度 **

有的情况算法的基本操作重复执行的次数还随问题输入的数据集不同而不同

最好的情况a0=e执行1次

最坏数组中没有e/an-1=e执行n次

而对于一个算法来说，需要考虑各种可能出现的情况，以及每一种情况出现的概率，一般情况下，可假设待查找的元素在数组中所有位置上出现的可能性均相同。类似于数学中求期望值。计算每一种情况执行次数与概率的乘积在求和。

最坏时间复杂度是指在最坏情况下算法的的复杂度；

最好时间复杂度是指在最好情况下算法的的复杂度；

平均时间复杂度是指算法在所有可能情况下，按照输入实例以等概率出现时，算法计算量的加权平均值。

通常考虑最坏和平均但有时平均比较难计算只考虑最坏时间复杂度，最坏情况运行时间是一种保证，那就是运行时间不会再坏了。

**计算公式 **

如果时间复杂度是平方阶最好降低到对数阶实在不行平方阶也可以接受，立方阶也尚可。

算法的空间复杂度：算法要占据的空间

算法本身要占据的空间：输入/输出、指令、常数、变量等。

算法要使用的辅助空间。

若输入数据所占据的空间只取决于问题本身和算法无关，这样只需分析该算法在实现时所需的辅助单元即可，若算法执行时所需的辅助单元相对于输入数据量而言是个常数，则称此算法为原地施工，空间复杂度为O(1)

时间与空间的取舍

人们之所以花大力气去评估算法的时间复杂度和空间复杂度，其根本原因是计算机的运算速度和空间资源是有限的。就如一个大财主，基本不必为日常的花销而伤脑筋，而一个没有多少积蓄的普通人则不得不为日常的花销精打细算。对于计算机系统来说也是如此，虽然目前计算机的CPU处理速度不断飙升，内存和硬盘空间也越来越大，但是面对庞大而复杂的数据和业务，我们仍要精打细算，选择最有效的利用方式。

举个例子说，要判断某年是不是闰年，你可能会花一点心思来写一个算法，每给一个年份，就可以通过这个算法计算得到是否闰年的结果。

另外一种方法是，事先建立一个有2050个元素的数组，然后把所有的年份按下标的数字对应，如果是闰年，则此数组元素的值是1，如果不是元素的值则为0。这样，所谓的判断某一年是否为闰年就变成了查找这个数组某一个元素的值的问题。

第一种方法相比起第二种来说很明显非常节省空间，但每一次查询都需要经过一系列的计算才能知道是否为闰年。第二种方法虽然需要在内存里存储2050个元素的数组，但是每次查询只需要一次索引判断即可。

这就是通过一笔空间上的开销来换取计算时间开销的小技巧。到底哪一种方法好？其实还是要看你用在什么地方。但在绝大多数情况下，时间复杂度更重要一些，我们宁愿多分配一些内存空间也要提升程序的执行速度。