资源简介

(共43张PPT)
第1章 数据结构与算法概述
数据结构的概念
逻辑结构与物理结构
算法的概念
数据结构的概念
逻辑结构与物理结构
算法的概念
1.2
1.3
1.1
点击查看本小节知识架构
点击查看本小节知识架构
点击查看本小节知识架构
学习目标
了解
了解
了解
了解数据结构的概念与专业术语
1
2
了解数据的逻辑结构与物理结构
3
掌握算法的概念与特性
数据结构是计算机专业的一门基础课，其主要研究程序设计中的操作对象及它们之间的关系。算法指的是解决问题的策略，只要有符合一定规范的输入，在有限时间内就能获得所要求的输出。虽然数据结构与算法属于不同的研究课题，但优秀的程序设计离不开二者的相辅相成。因此，本章将主要介绍数据结构与算法的基本概念，包括数据结构的基本术语、数据的结构分类以及算法的各种特性。
1.1 数据结构与算法
1.1.1
数据
返回目录
1.1.2
数据元素与数据项
1.1.3
数据对象
1.1.4
数据结构
1.1.1 数据
数据（Data）在计算机科学中是指计算机操作的对象，是输入到计算机中被计算机程序处理的符号集合。例如，一个读取终端输入的程序，其操作的对象可能是字符串，那么字符串就是计算机程序处理的数据。数据不仅可以是整型、字符型等数值类型，也可以是音频、图片、视频等非数值类型。
综上所述，数据的本质就是符号，且这些符号都满足以下特定的需求。
（1）可以输入到计算机中。
（2）可以被计算机程序处理。
其中数值类型的数据可以被执行数值计算，而非数值类型的数据可以被执行非数值的处理，例如，音频、图片、视频等资源在计算中都是被编码转换为字符数据来处理的。
1.1.2 数据元素与数据项
数据元素（Data Element）是组成数据的基本单位。数据的基本单位是一种抽象的概念，并没有具体的数值化标准。例如，可以将公司看作一个数据元素，也可以将员工视为一个数据元素。
数据元素由数据项组成，并且数据项是数据不可分割的最小单位。例如，将公司看作一个数据元素，则行政部、人事部、财务部都可以视为该元素的数据项，也可以将董事长、经理、总监作为该元素的数据项。
1.1.3 数据对象
数据对象（Data Object）指的是具有相同性质的数据元素的集合，是数据的子集。相同性质指的是数据项的数量与类型的相同。例如，每一个人都有姓名、年龄、性别、出生地址这些数据项。
在实际开发应用中，处理相同性质的数据元素时，默认将数据对象简称为数据。也就是说，“数据”在数据结构这一课题中代指数据对象，即具有相同性质的多个数据元素。
1.1.4 数据结构
结构（Structure）通常指的是数据元素之间的特定关系。因此，数据结构（Data Structure）通常指的是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构主要研究的是数据的逻辑结构与数据的物理（存储）结构以及它们之间的相互关系。其目的是对这种结构设计相应的算法，确保经过运算后得到的新结构仍保持原来的结构类型。
1.2 逻辑结构与物理结构
1.2.1
逻辑结构
返回目录
1.2.2
物理结构
1.2 逻辑结构与物理结构
数据结构可分为逻辑结构与物理结构。数据的逻辑结构是对数据元素之间逻辑关系的描述，而数据的物理结构是指数据元素及其关系在计算机内存中的表示。
逻辑结构与物理结构是与数据结构密切相关的两个概念，同一种逻辑结构可以对应不同的物理结构。算法的设计取决于数据的逻辑结构，算法的实现依赖于指定的物理结构。
1.2.1 逻辑结构
按照数据元素之间存在的逻辑关系的不同数学特性，通常可以将逻辑结构分为4种类型。
1.线性结构
线性结构中的数据元素之间是一对一的关系，即数据元素存在依次排列的先后次序关系，且只有一个起始数据元素和一个终止数据元素，如图所示。
生活中的城市公交路线类似于上述结构，其站点就是数据元素，每一条公交线路都有一个起点和终点，中间各站都按先后次序排列。
1.2.1 逻辑结构
2.树形结构
树形结构中的数据元素之间存在一对多的关系，即层次关系或分支关系。这种结构只有一个起始数据元素（称为树根），其他数据元素称为树叶，如图所示。
一个公司的组织架构类似于上述结构，树根为公司，公司的下一层对应各部门，各部门下有各种分组。因此，公司架构可被抽象成树形结构来进行数据管理，如图所示。
1.2.1 逻辑结构
3.图形结构
图形结构中的数据元素之间存在多对多的网络关系，即数据元素之间相互连接成网状，如图所示。
生活中常用的交通路线图类似于上述结构，每一个地点都是一个数据元素，公路是地点之间的关系。一个地点可能与多个地点有公路，地点之间通过公路连接成网状，如图所示。
1.2.1 逻辑结构
4.集合结构
集合结构中的数据元素除了同属一个集合外，没有其他关系，各个元素是“平等”的，该结构类似于数学中的集合，如图所示。
1.2.2 物理结构
物理结构即存储结构，主要指的是数据的逻辑结构在实际的计算机内存中存储的形式。通常数据的物理结构有以下4种类型。
1.顺序存储
顺序存储指的是将相邻的数据元素存放在计算机地址连续的存储单元中，如图所示。
1.2.2 物理结构
在C语言程序中，数组采用的就是典型的顺序存储。当程序中定义一个含有5个整型元素的数组时，操作系统就会在内存中申请一块连续且大小为20字节的区域存放这个数组。数组中的元素依次存放在这块连续的区域中，每个元素占4个字节。
2.链式存储
链式存储不同于顺序存储，在顺序存储中，逻辑上相邻的数据元素在内存中也是相邻的，而链式存储中，逻辑上相邻的数据元素在内存中不一定相邻。简单地说，链式存储中的数据元素可以存储在内存的任意位置。如图所示，C语言程序通过指针指向地址的方式来连接不同存储位置上的数据元素。
1.2.2 物理结构
生活中的飞机航班路线就可以理解为链式结构。假设飞机从北京飞往广州，且需要经停长沙，那么北京、长沙、广州可认为是在逻辑上相邻的元素，航班路线就是三者的逻辑关系，但是这三座城市在地理位置上是不相邻的。
3.索引存储
索引存储指的是在存储数据元素的同时建立索引列表，存储元素之间的关系。这是一种为了加速检索而创建的存储结构。例如，一所大学在安排学生宿舍时，一定不能按照学生的学号依次分配宿舍，学号并不考虑性别，也就是说不可能采用顺序存储；其次，也不能是链式存储，因为学号只是学生的一个标识，没有其他意义。因此，为学生分配宿舍可采用索引存储，即建立一个索引列表记录学号与宿舍关系，根据索引列表即可找到与学号对应的宿舍。
4.散列存储
散列存储指的是根据数据元素的关键字直接计算出该数据元素的存储位置。其基本的设计思想是以数据元素的关键字K为自变量，通过一个确定的函数关系f（称为散列函数），计算出对应的函数值f(K)，将这个值解释为数据元素的存储地址，最后将数据元素存入f(K)所指的存储位置上。查找时只需根据要查找的关键字用同样的函数计算地址，然后到相应的地址提取要查找的数据元素。
1.3 算法的概念
1.3.1
算法的描述
返回目录
1.3.2
算法的特性
1.3.3
算法的设计要求
1.3.4
算法效率的度量方法
1.3 算法的概念
1.3.5
算法的时间复杂度
返回目录
1.3.6
算法的空间复杂度
1.3 算法的概念
算法是解决问题的方法，该术语最早出现在公元825年由波斯数学家阿勒 花刺子密所写的《印度数字算术》中。
1.3.1 算法的描述
算法可以用自然语言、数学语言、约定的符号语言或计算机程序语言来描述。例如，“从3个整数中选出最大的1个整数输出”这一问题，可采用以下3种方法来描述。
1.自然语言描述
（1）输入3个整数a、b、c。
（2）先从前两个整数a、b中选出较大的一个整数，设为x。
（3）从x、c中选出较大的整数，设为y。
（4）输出y的值。
使用自然语言描述算法通俗易懂，但算法整体的数据流向不够清晰。
1.3.1 算法的描述
2.符号语言描述
描述算法的符号语言有很多种类型，其中比较有特点的是程序流程图，如图所示。
程序流程图描述算法比较清晰，而且容易转换为计算机语言。
1.3.1 算法的描述
3.计算机程序语言描述
计算机程序语言有很多，本次使用C语言，如例所示。
用计算机程序语言描述算法对描述者的要求较高，需要描述者在理解算法工作原理的前提下，具备计算机语言的编程能力。但这种描述可以直接输入计算机，便于验证其正确性。
1.3.2 算法的特性
算法有5个基本的特性：输入、输出、有穷性、确定性、可行性。
1.输入
一个算法可以有多个或没有输入，具体的输入量取决于算法中的数据对象。有些算法的输入需要在执行过程中进行，有些算法则将输入嵌入到算法之中，如例所示。
从例中可以看出，变量i在函数内部自加并完成运算，无须用户输入。没有输入量的算法，其输出结果一般是固定的。
1.3.2 算法的特性
2.输出
一个算法必须有一个或多个输出，这些输出是算法对输入进行运算后的结果。如果一个算法没有输出，则算法没有任何意义。
3.有穷性
有穷性指的是算法在执行有限次数的操作后自动停止，不会出现无限循环的情况，且每次操作都可以在有限时间内完成。简单地说，算法运行一定有结束的时刻。
1.3.2 算法的特性
在例中，代码第8行的循环语句添加了分号，成为一个独立的语句。当输入的n值大于0时，此语句将无限循环，因为i的值一直为0。
例就是典型的错误算法，程序不能在有限时间内结束，而是进入死循环状态。将第8行的分号去掉，则第8行与第9行代码变成一个完整的语句，实现在有限次循环中叠加，算法具备了有穷性。
4.确定性
确定性指的是算法的每次操作都具有确定的含义，不会出现二义性。算法在一定条件下，应只有一条执行路径，相同的输入在任何时刻执行都应该导向相同的结果。
5.可行性
可行性指的是算法中描述的操作都可以通过将已经实现的基本运算执行有限次来实现。简单地说，算法可以转换为程序上机运行，并可以输出正确的结果。
1.3.3 算法的设计要求
同一个问题可以有很多种算法。判断一个算法是否为最优算法，可以从以下4个方面分析。
1.正确性
算法的正确性指的是算法能正确反映问题的需求，经得起一切可输入数据的测试。算法的正确性包括以下4个层次。
（1）算法程序无语法错误。
（2）算法程序对于合法的输入数据能够产生满足要求的输出结果。
（3）算法程序对于非法的输入数据能够产生满足规格的说明。
（4）算法程序对于极端的输入数据能够产生满足要求的输出结果。
1.3.3 算法的设计要求
例的算法程序看似没有错误，但是当用户输入的数据为0或负数时，该算法都无法产生满足需求的结果。
1.3.3 算法的设计要求
2.可读性
可读性指的是算法的设计应该尽可能简单，便于阅读、理解。
3.健壮性
健壮性指的是算法可以对不合法的输入数据做出处理，而不是产生异常或极端的结果。
4.高效率
高效率指的是算法的执行时间要尽量短，对存储空间的使用要尽可能少。在满足前3个要求的前提下，高效率是体现算法优异的重要指标。
1.3.4 算法效率的度量方法
由1.3.3节可知，高效率算法应该具备运行时间短和存储量低的特点。接下来介绍如何对算法效率进行测试。
1.事后统计法
事后统计法指的是通过设计好的测试程序和数据，对不同算法程序的运行时间进行比较，从而确定算法效率的高低。
通常情况下，不采用事后统计法进行算法效率测试，其原因如下。
（1）解决问题的算法有很多，为了测试某算法效率的高低，需要尽可能多地编写算法程序与之进行比较测试，而设计编写算法程序需要大量的时间和精力。
（2）程序运行时间受计算机硬件等环境因素影响，有时会掩盖算法本身的优劣。例如，八核处理器明显比单核处理器处理程序的速度要快。
（3）算法测试数据设计困难，效率高的算法在测试数据规模小时表现不明显。
1.3.4 算法效率的度量方法
2.事前分析法
事前分析法指的是设计算法程序之前，根据统计方法对算法进行估算。一个好的算法所消耗的时间，应该是算法中每条语句执行的时间之和；每条语句的执行时间是该语句的执行次数与该语句执行一次所需时间的乘积。
接下来对比两个求和的示例，讨论算法的优劣。
1.3.4 算法效率的度量方法
例通过循环累加计算从1到100的和，在不讨论语句执行一次所需时间的情况下（只讨论语句执行次数），可见示例核心部分的语句总共执行了 2×n+5 次。
例1-6实现与例1-5相同的需求，其核心部分的语句总共执行了3次。
1.3.4 算法效率的度量方法
由上述示例可以看出，在相同硬件环境下，例1-6所示的算法程序明显优于例1-5。变量n的值越大，例1-5所示的算法程序劣势越明显。
在上述两个示例的基础上再进行进一步讨论，如例所示。
在例中，外部循环的循环次数为n，内部循环的循环次数也为n，因此循环内部的x++语句将执行 n 2 次。显然，随着n值的增加，例1-7的执行次数明显高于例1-5和例1-6。
1.3.5 算法的时间复杂度
在1.3.4节中的例1-5、例1-6、例1-7中，变量n称为问题规模，算法中语句的执行次数称为时间频度，记为T(n)。例1-5和例1-7中，当n不断变化时，时间频度T(n)也会不断变化。
如果有某个辅助函数f(n)，并且存在一个正常数c使得 f(n)×c≥T(n)恒成立，则记作 T(n)=O(f(n))。通常将 O(f(n))称为算法的渐进时间复杂度，简称时间复杂度。使用O( )计算时间复杂度的记法称为大O记法。一般情况下，随着n的增大，T(n)增长最慢的算法为最优算法。
利用上述时间复杂度的公式，分别计算例1-5、例1-6、例1-7中算法的时间复杂度，具体分析如下。（辅助函数 f(n)获取执行次数，正常数c视为单次执行时间，可以忽略。）
（1）例1-5的算法时间为 2×n+5，则 f(n)=2n+5。当问题规模n变为无穷大时，该算法的执行时间可估算为n，使用大O记法表示时间复杂度为 O(n)。
（2）例1-6的算法时间为3，则 f(n)=3。此值相较于无穷大的n值可忽略不计，因此使用大O记法表示时间复杂度为 O(1)。（ O(1)表示执行次数或时间是一个常数，不随着n的变化而变化）
（3）例1-7的算法时间为 3×n 2 +3×n+3，则 f(n)=3(n 2 +n+1)。当问题规模n变为无穷大时，该算法的执行时间可估算为 n 2 ，使用大O记法表示时间复杂度为 O(n 2 )。
1.3.4 算法的度量方法
通常情况下，将 O(1)、O(n)、O(n 2 )分别称为常数阶、线性阶、平方阶。除此之外，还有对数阶、指数阶等其他阶。
1.常数阶
例中的算法时间为3，根据上述时间复杂度计算方法可知，该算法的时间复杂度没有最高阶项，就是一个常数。使用平面直角坐标系表示常数阶，如图所示。
2.线性阶
例中的算法时间为 2n+5，根据上述时间复杂度计算方法可知，随着问题规模n变大，时间复杂度成线性增长。使用平面直角坐标系表示线性阶，如图所示。
1.3.4 算法的度量方法
3.平方阶
例中的算法执行时间为 3(n 2 +n+1)，根据上述时间复杂度计算方法可知，随着问题规模n变大，时间复杂度线性增长变快。使用平面直角坐标系表示平方阶，如图所示。
1.3.4 算法的度量方法
常见的时间复杂度如表所示。
常见的时间复杂度所对应的时间从短到长依次为：
1.3.6 算法的空间复杂度
了解算法的空间复杂度之前，需要先理解算法存储量的概念。算法的存储量指的是算法执行过程中所需的最大存储空间，其主要包括3个部分：输入/输出数据所占空间、程序代码所占空间、程序运行临时占用空间。
1.输入/输出数据所占空间
算法的输入/输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不会随着算法的不同而改变，因此在算法比较时不予考虑。
2.程序代码所占空间
算法的程序代码所占用的存储空间与程序的长度成正比，要压缩这部分存储空间，就必须编写出较短的程序。程序代码本身所占空间对不同算法来说不会有数量级的差别。
1.3.6 算法的空间复杂度
3.程序运行临时占用空间
根据程序在运行过程中临时占用存储空间的不同，可以将算法分为两类。
（1）原地算法：只占用较小的临时空间，且占有量不会随着问题规模n的改变而改变。
（2）非原地算法：占用临时空间的大小与问题规模n有关，n越大占用的临时空间越大。
通过计算算法存储量可以得到算法的空间复杂度，算法空间复杂度的计算公式记作 S(n)=O(f(n))，其中，n为问题的规模，f(n)为关于n所占存储空间的函数。随着问题规模n的增大，算法存储量的增长率与 f(n)的增长率相同。
1.3.6 算法的空间复杂度
根据上述概念，使用示例进行具体分析，如例所示。
例现的功能为从1到n的数值累加。其中，变量s、i所占用的空间不会随着n的变化而发生改变，因此空间复杂度与n无关，该算法的空间复杂度记作 S(n)=O(1)。
本章小结
本章以概念为主，重点介绍了数据的概念、数据的逻辑结构与物理结构以及算法的概念。其中，数据的逻辑结构与物理结构以及二者之间的关系，是数据结构研究的核心内容。读者需要对数据结构与算法建立初步的认识，重点要理解逻辑结构与物理结构的设计思想，为后续的程序设计奠定良好的基础。

展开更多......

收起↑