数据结构与算法：快速理解数据结构
- 算法
- 2024-05-31
- 481热度
- 0评论
什么是数据结构？
数据结构是指数据在计算机系统中的组织和存储方式。数据是能够带给我们信息的数值、文字、图像、视频、符号等内容，数据按照一定的结构组织在一起称为数据的逻辑结构，数据的逻辑结构以何种方式存储到物理空间称为数据的存储结构，数据的逻辑结构和存储结构统称为数据结构。
为了更好地理解数据结构，下面我们来看几个例子。
案例1
使用计算机管理学生信息问题。学生信息包括学号、姓名、籍贯、年龄、年级、班级等数据字段，计算机要能够存储这些数据，并能对这些数据进行增加、删除、修改和查询操作。在计算机中如何组织和存储这些数据呢？既能方便操作，又能节省存储空间，最简单的方式就是将学生信息设计为表结构（见图1-1），每一个学生的信息为表中的一条记录，记录中的单个数据项为学生的数据字段，学生的学号和姓名为关键数据字段。用户可以通过学号或姓名查找某一学生的信息，也可以添加、删除或修改学生的信息。这些操作都是针对表的操作，从而将计算机管理学生信息问题转化为表和对表的增、删、改、查运算。
图 1-1学生信息表
案例2
使用计算机辅助决策贷款申请问题。用于贷款申请辅助决策主要判断申请者的Age（年龄）、HasJob（是否有工作）、OwnHouse（是否有房产）、CreditRating（信贷评级）。Age可能的取值为：young、middle、old；OwnHouse和HasJob可能的取值为：true和false；CreditRating可能的取值为fair、good、excellent。决策过程从Age开始，根据申请者的年龄构成三个不同的决策分支，每个决策分支可以分别根据HasJob、OwnHouse、CreditRating的值进行后续决策，直至决策完成，这样就构成了一棵决策树，从而将计算机辅助决策贷款申请问题转换为决策树模型，以及对决策树模型的查询操作。
图 1-2贷款申请辅助决策树模型
以图1-2贷款申请辅助决策树模型为例，决策程序首先判断申请者的年龄，根据年龄值选择不同的分支，若年龄值为young，再判断申请者是否有工作：若HasJob值为Fasle，再判断申请者是否有住房，若有住房申请通过，否则申请失败；若HasJob值为True，则申请通过。
案例3
使用计算机解决推销员最短行程问题。推销员需要访问某地区的所有城镇推销商品，最后回到出发点，计算机如何安排推销员的推广路线使总行程最小。若用顶点表示城镇，边表示连接两城镇的路，边上的权重表示距离，于是推销员问题就转化为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题（见图1-3）。
图 1-3某地区城镇加权连通图
图1-3中顶点v1、v2、v3表示三个城镇，顶点之间的边线表示连通城镇之间的交通，边线的权重表示距离。可以判断经过每个顶点至少一次的最短闭通路为：
(V1,V2,v1,V3)
即V1到V2，V2返回到V1，再由V1到V3，边线的权重和为4。
前面的三个案例，程序处理的不再是纯数值数据，而是表、树、图结构化的数据，数据结构就是研究类似表、树、图这样的结构化数据在计算机的存储和运算。
数据结构与计算机的发展
世界上第一个程序员是英国著名诗人拜伦的女儿阿达·洛芙莱斯，阿达有非常好的数学天赋，她在翻译数学家费德里科·路易吉关于巴贝奇分析机的《分析机概论》论文时，对论文进行了详尽的注释，并预想到这台机器不仅能执行计算，还能执行运算，可以被运用到音乐、制图和科学研究中。为此它专门设计了一个可以在分析机上运行的程序，用于计算出有理数数列——伯努利数，分析机是最早的计算机模型，它主要用于数值运算。
图灵机是英国数学家图灵提出的一个可用于计算的模型，模型由一个控制器、一个读写头和一条无限长的纸带组成。纸带上有用于计算的数字或符号，控制器控制读写头在纸带上移动并读取或修改纸带上的数字或符号。发出读写命令的控制器内部有一个有限状态转换表, 状态转换表根据当前状态及从纸带读取的内容来确定下一个状态并控制读写头的移动，状态转换循环往复，直至完成计算。控制器内部的有限状态转换表可以理解为编写的程序，图灵机已经可以处理符号并能够对程序流程进行控制。
世界上第一台通用计算机埃尼阿克在1946年2月的美国宾夕法尼亚大学研制成功，是图灵机的完全再现。埃尼阿克用存储器来存储程序指令和数据，并通过运算器执行程序指令和运算，并使用二进制替代十进制计数，降低了运算电路的复杂度，埃尼阿克是现代计算机的模型，现代计算机一直采用埃尼阿克的计算机结构。
现代计算机的应用领域已不再局限于科学计算，更多地应用于控制、管理等非数值处理领域，计算机处理的数据也由数值发展到字符、表格、图形、图像、视频、声音等具有一定结构的数据，运行在计算机上的程序需要对这些非数值数据进行存储和运算，由此诞生了数据结构技术。
1968年唐纳德•克努思教授在《计算机程序设计艺术》一书中，首次提出了算法及数据结构的概念。70年代初，数据结构作为一门独立的课程开始进入大学课堂，采用的教学语言有Pascal、Java、C、C++等编程语言。
《数据结构》在计算机科学中是一门综合性的专业基础课，它主要研究非数值性程序设计中数据的物理存储和逻辑结构，以及它们之间的关系和运算。它是一般程序设计的基础，也是操作系统、编译程序、数据库系统及其它大型应用程序的设计基础。
数据结构与算法的关系
数据结构是算法的基础。算法的执行离不开数据结构，不同的数据结构具有不同的特性和适用场景，因此选择合适的数据结构是解决问题的关键。例如：在解决排序问题时，如果数据量较小，可以使用简单的插入排序算法；如果数据量较大，则可能需要使用更高效的排序算法，如归并排序或快速排序等。
对于特定的数据结构，可以通过算法优化来提高其执行效率和性能。例如，在二叉搜索树中插入节点时，通过保持树的平衡可以避免树成为“倾斜”的状态，从而保持二叉搜索树的查找、插入和删除操作的效率。
因此数据结构和算法是相互依存的关系，选择合适的数据结构和算法是解决问题的关键。
算法及其评估方法
算法是计算机程序对一个问题求解步骤的描述，是求解问题的方法，它是计算机指令的有限序列。用计算机程序求解一个问题，可以有多种算法，每一种算法都可以达到解决问题的目的，但花费的成本和时间却不尽相同，从节约成本和时间的角度考虑，还需要对算法进行评估，为求解的问题找到合适的算法。
下表是某校的学生信息表：
假设学生信息表为n条记录，要求设计一个算法：应用学号查找对应的学生信息，即给出一个学号，算法要返回与学号对应的学生信息。
比较简单的查找方法是顺序查找，查找过程为：从学生信息表的第一条记录开始，比较记录的学号字段，若相等，则查找成功，否则顺序比较下一条记录，直至全部记录比较完成，若没有查找到对应的记录，则查找失败。
顺序查找法最好的情况是第一条记录就符合查找要求，查找算法仅执行一次就可以了；最坏的情况是最后一条记录符合查找要求，查找算法需要执行n次。顺序查找算法的平均执行次数为(n+1)/2次。
我们观察到学生信息表的记录是按照学号大小排序，在这种情况下，可以使用更好的查找算法。假设记录数量n为100，学号为80，查找过程如下：
折半查找过程
（1）当前有100条记录，从中间第50条记录开始查找，查找学号大于记录学号，排除第前50条记录；
（2）当前剩余后50条记录，从中间第75条记录开始查找，查找学号大于记录学号，排除第前25条记录；
（3）当前剩余后25条记录，从中间第88条记录开始查找，查找学号小于记录学号，排除第88~100条记录；
（4）当前剩余76~87条记录，从中间第82条记录开始查找，查找学号小于记录学号，排除第82~88条记录；
（5）当前剩余76~81条记录，从中间第78条开始查找，查找学号大于记录序号，排除第76~78条记录；
（6）当前剩余79~81条记录，从中间第80条记录开始查找，查找学号等于记录学号，查找成功。
从查找过程可以看出，该算法仅需要6次就可以查找到对应学号的记录，顺序查找算法则需要80次才能查找到对应学号的记录。上述算法为二分查找算法，也称为折半查找，使用该算法的前提是待查找的数据必须有序排列。
对有序排列的数据来说，使用二分查找最多需要n的对数次，顺序查找则需要n次，二分查找要优于顺序查找。
那么，如何评估一个算法呢？评估一个算法，可以通过算法在执行过程中所消耗的时间、算法在执行过程中所占资源的大小、算法的易理解性和易实现性进行综合评估。从多个候选算法中找出运行时间短、资源占用少、易理解、易实现的算法。然而，现实情况却不尽人意。往往是，一个看起来很简便的算法，其运行时间要比一个形式上复杂的算法慢的多；而一个运行时间较短的算法往往占用较多的资源。我们主要讨论算法的时间特性，并给出算法在时间复杂度上的度量指标。
一个算法在执行过程中所消耗的时间主要取决于数据输入的时间、计算机指令执行时间、语句重复执行的次数。其中数据输入时间依赖于输入设备的性能，计算机指令执行时间依赖于计算机性能。因此，习惯上将算法语句重复执行的次数作为算法的时间量度。
例如：
void one () {
int x = 0; // 执行一次
x = x+1; // 执行一次
}
C语言的one()函数有两条语句，每条语句各执行一次，函数共执行两次语句。
void two() {
int i= 0,x=0,n=100; // 执行一次
for( i = 0; i<n;i++ )
x = x + 1; //执行n次
}
C语言的two()函数内包含一个for循环，循环体内的x = x + 1语句将执行n次，two()函数执行n+1次。
为了方便评估算法的执行效率，一般从算法中选取一种对于所研究的问题（或算法模型）来说是基本运算的操作，以其重复执行的次数作为评价算法时间，多数情况下计算算法最深层循环内语句的执行次数。
void three() {
int i,j,x=0,n=100;
for(i = 0;i < n;i++)
{
for(j = 0;j < n;j++)
x = x + 1;
}
}
three()函数包含n次的for嵌套循环，在第二层循环执行x=x+1语句，因此执行次数为n*n次，即n^2次。
我们把算法中语句的执行次数称为语句频度或时间频度记为T(n)，T(n)即为算法通用的时间量度。其中n为问题规模（大小）的量度，如数组的长度、矩阵的阶、图中的顶点数等等，T为n的函数，表示算法的时间复杂度。当问题规模n不断变化时，时间频度T(n)也会不断变化，我们需要评估当n不断变化时，时间频度T(n)的变化规律。
我们还是以学生信息表查找算法为例，查找算法分为顺序查找和二分查找，假设查询一条记录需要1毫秒的时间，记录数量为100，最坏情况下（评估算法一般都按最坏情况进行评估）顺序查找需要耗费100毫秒的时间，二分查找需要耗费7毫秒的时间（以2为底100的对数大约为7）。若是记录数量为10000，顺序查找需要耗费10000毫秒，二分查找则需要耗费14毫秒的时间（以2为底10000的对数大约为14）。
从上面的例子可以看出，随着记录数量的增加，二分查找需要的额外时间并不多，而顺序查找需要的额外时间却很多。因此随着记录数量的增长，二分查找的速度比顺序查找的速度快得多，现在需要一个函数来确定这个快慢程度。若有某个辅助函数f(n)，当n趋向于无穷大时，如果T(n)/ f(n)的极限为不等于零的常数，则认为T(n)与f(n)是同量级的函数，记作：
T(n) =O(f(n))
O(f(n))称为算法的渐进时间复杂度，简称时间复杂度。其中f(n)通常取执行次数中最高次方或最大指数部分的项。例如：
常用算法的时间复杂度
顺序查找算法：O(n)
二分查找算法：
冒泡排序算法：O(n^2)
n阶矩阵的乘法运算：O(n^3)
在各种不同的算法中，若算法语句的执行次数为常数，则算法的时间复杂度为O(1)，按数量级递增排列，常见的时间复杂度量有：
常见的时间复杂度量
（1）O(logn)：对数阶，如二分查找算法，算法的时间复杂度随问题规模n呈对数增长；
（2）O(n)：线性阶，如顺序查找算法，算法的时间复杂度随问题规模n呈线性增长；
（3）O(nlogn)：对数阶，如快速排序算法，算法的时间复杂度随问题规模n呈线性对数增长；
（4）O(n^2)：平方阶，如冒泡排序，算法的时间复杂度随问题规模n呈平方增长；
（5）O(n^3)：立方阶，如两个n阶矩阵的乘法运算，算法的时间复杂度随问题规模n呈立方增长；
（6）O(2^n)：指数阶，如n个元素集合的所有子集的算法，算法的时间复杂度随问题规模n呈指数级增长；
下图给出了随着n的变化，不同量级的时间复杂度变化曲线。
图 1-4时间复杂度变化曲线图
评估算法时间复杂度的具体步骤为：（1）找出算法中重复执行次数最多的语句的频度作为度量次数；（2）保留算法的最高次幂，忽略所有低次幂和高次幂的系数；（3）将算法执行次数的数量级放入大Ο记号中。
评估算法时间复杂度的要点是：如果一个算法的执行次数是 T(n)，那么只保留最高次项，同时忽略最高项的系数后得到函数 f(n)，此时算法的时间复杂度就是 O(f(n))。
