【文档说明】数据结构与算法基础课件.pptx，共(38)页，3.627 MB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-7194.html

以下为本文档部分文字说明：

数据结构2020.2第1章数据结构与算法基础为什么要学数据结构如何学好数据结构数据结构的概念算法和算法分析习题0102030405目录本章要点掌握数据结构的学习方法掌握数据结构基本概念掌握算法时间复杂度的分析

方法基本准备，初识数据与结构1.1数据结构=数据+结构人们常说的大数据时代与信息时代，究竟什么是数据，什么是信息呢？数据:数字、文字、图片、声音、视频都是数据信息：是对数据进行操作和分析之后得出的产物。数据结构：

数据的容器，装载数据达到最终的目的。1.1初识数据与结构数据结构的概念1.21.2数据结构的概念数据：一切可以被计算机所识别的文字符号图像音视频等都属于数据因此数据是一个相当庞大、抽象和笼统的概念。数据元素:是有一定意义数据的基本单位，作为整体处

理的单位。数据项:是数据的最小标识单位。一个记录可称为一个数据元素，一个字段就是一个数据项。数据对象:是具有相同性质的数据元素的集合，是数据的子集。数据结构:相互之间存在一种或多种特定关系的数据元素的集合。【例1-1】这

个表中的数据元素是学生记录,每个数据元素由四个数据项(即学号、姓别、性别和C语言)组成。1.2数据结构的概念1.2数据结构的概念数据结构的物理结构与逻辑结构物理结构:是数据元素在计算机中的表示和实现。(实现层)逻辑结构:是对数据元素之间的逻辑关

系的描述。属于用户视图，是面向问题的，反映数据内部的构成方式。(抽象层)1.2.1数据的物理结构物理结构(存储结构)是数据在计算机内部的存储实现，分为顺序存储和链式存储两种。顺序存储结构：数据元素按某种顺序依此存放在计算机存储器的连续存储单元中，其存储的地址由起始地址

和元素所占的存储空间来决定链式存储结构:把数据元素存放在任意的存储单元里，这组存储单元可连续的，也可不连续的，因此需要用一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置1.2.1数据的物理结构—顺序存储S是起始地址，H是每个元素所占的空间则第i个

元素的存储地址为:Loc(i)=Loc(1)+(i-1)*H=S+(i-1)*H1.2.1数据的物理结构—顺序存储顺序存储结构的主要特点:•结点中只有自身数据域。因此存储密度大，利用率高。•可以通过计算确定数据结构中第i个元素的位置，可以(直接)随机存取。•插入和删除操作会引起大量的元素移

动。•必须存储在一片地址连续的存储单元中。1.2.1数据的物理结构—链式存储把逻辑上相邻的元素存放在物理上不相邻的存储单元中。主要特点：•有表示连接信息的指针域。因此存储密度小，利用率低。•逻辑上相邻的结点在物理上不一定邻接。•插入和删除操作灵活方

便;只要修改指针域的值即可。•可以存储在不连续的存储单元中。1.2.2数据的逻辑结构数据的逻辑结构是数据元素之间关系的描述，可看作是从具体问题抽象出来的数学模型。与数据的存储无关，是独立于计算机的。通常逻辑结构

有四类：集合结构:数据元素间的关系是“属于同一个集合”。集合是元素关系极为松散的一种结构。线性结构:该结构的数据元素之间存在着一对一的关系。1.2.2数据的逻辑结构树型结构:该结构的数据元素之间存在着一对

多的关系。图形结构:该结构的数据元素之间存在着多对多的关系，也称作网状结构。1.2.2数据的逻辑结构-举例说明线性数据结构树型数据结构图形数据结构1.2.3数据结构数据结构=数据+数据的物理结构+数据的逻辑

结构1.2.3数据类型与抽象数据类型数据类型是编程中对不同种类数据的一种分类与定义。常见的数据类型有整型，浮点型，字符型，布尔型等抽象数据类型是用基本数据类型来描述事物的各个属性，再把所有属性当做一个整体来看待。数据结构

的运算插入、删除、更新、检索、排序加工型操作:操作改变了存储结构的值。引用型操作:操作只是查询或求得结点的值。为什么学习数据结构1.31.3为什么要学习数据结构数据结构是计算机科学与技术专业的专业基础课，是十分重要的核心课程。所有的计算机系统软件和应用软件

都要用到各种类型的数据结构。要想有效地使用计算机、充分发挥计算机的性能，还必须学习和掌握好数据结构的有关知识。如何学好数据结构1.41.4如何学好数据结构(1)要求掌握基本的C语言知识，掌握模块化程序设

计的基本思想，能够利用C语言熟练编写一些简单的程序。(2)在学习时，首先要掌握各种基本的数据结构，并对各种数据结构的逻辑结构和物理结构有足够的认识。(3)对基于各种数据结构的常见的操作及其算法要重点掌握，并要了解评价某个具体算法优劣的方法。(4)多思考、多做练习题、多上机实践。算法与算法分析

基础1.51.5算法和算法分析基础数据结构+算法=编程算法是描述解决问题的方法。在计算机中表现指令的有限序列。其中每一条指令表示一个或多个操作1.5.1算法特性(1)有穷性：一个算法必须在有穷步之后结束，即有限时间内完成。如计算

机需要30年的时间才能结束，算法的意义就不大。(2)确定性：算法的每一步必须有确切的定义，无二义性。相同的输入仅有唯一的输出结果。(3)可行性：算法中的每一步都可实现，即每一步都是经过有限次数执行得以实现。(4)输入：一个算法具有零个或多个输入，可以没有输入。(5)输出：一

个算法具有一个或多个输出，至少有一个输出。1.5.1算法特性要设计一个好的算法通常要考虑以下的要求：(1)正确性：算法的执行结果应当满足预先规定的功能和性能要求。(2)可读性：一个算法应当思路清晰、层次分明、简单明了、易读易懂。(3)健壮性(鲁棒性)：当输

入不合法数据时，应能作适当处理，不至引起严重后果，陷入死机。(4)高效率和低存储量：有效使用存储空间和有较高的时间效率。【例1-5】求n个数的最大值。分析健壮性main(){intmax=0,x;for(inti=1;i<=n;i++){scanf(“%d”,

&x);if(x>max)max=x;}printf(“%d”,max);}提示：本程序无语法错误，当输入全为正数时，结果正确；当输入全为负数时，求得的最大值为0，结果不正确。既要输入正确的数据，也要输入错误的数

据进行健壮性测试。1.5.2算法性能分析与度量评价一个算法主要看这个算法所占用机器资源的多少，而这些资源中时间代价与空间代价是两个主要的方面，通常是以算法执行所需的机器时间和所占用的存储空间来判断一个算法的优劣。好的算法具备时间效率高和存储量低的特点。对同一问题，有多个算法

，执行时间短的效率高，存储量是指执行过程需要的最少存储量。1.5.2算法性能分析与度量（1）关于算法执行时间一个算法的执行时间大致上等于其所有语句执行时间的总和语句的执行时间是指该语句的执行次数和执行一次所需时间的乘积。两个算法的第一条、最后一条语句是一样的，

中间部分是要关注的，把循环当作一个整体，忽略头尾循环判断的次数，这两个算法的差别就是1与n的区别。1.5.2算法性能分析与度量（2）时间复杂度（TimeComplexity）对于算法分析，我们关心的是算法中语句总的执行次数T（n）是关于问题规模n的函数。T（n）随n的变化

情况并确定T（n）的数量级。常用“大O表示法”表示：T(n)=O(f(n))。它表示随着问题的规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。函

数的渐近增长：两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n>N时，总有f(n)>g(n)，称f(n)的增长渐近快于g(n)。如C算法、D算法与E算法。1.5.2算法性能分析与度量当n=1,2时，C算法不如D算法。但当n>2时，C算法优于D算法。随n的增加，算法C比D越来越好。

于是我们可以说，当输入数据n，只要超过某一数值N时，这个函数就总是大于另一函数，我们称函数是渐近增长的。当n>2时，即N=3时，算法D与E的渐近增长是相同的。都记为O（n2）。推导大O阶的方法1）程序运行时间中的常数用1代替。如运行3次，记O(1),运行100次，

也记为O(1)。2）在大O()函数中运行次数只取最高阶项，并且最高阶项的常数为1。如5n2记O(n2)。一般情况下，随n的增大，T（n）的增长较慢的算法为最优的算法。按大O阶推导方法：A算法f(n)=3,常数项3次用1代替，记O(1)。B算法f(n)=2n+

3，常数项3次用1代替，2n的系数2也改为1，记O（n）C算法f(n)=C(3n+5)，记为O（n）。D算法f(n)=(2n2)，记为O(n2)。E算法f(n)=(2n2+3n+5),记为O(n2)。按最高项，其余忽略不计。1.5.2算法性能分析与度量【例1-6】在下列三段程序段

中，给出原操作x=x+1的时间复杂度分析。（1）x=x+1；程序执行1次，其时间复杂度为O(1)称为常量阶；（2）for(i=1;i<=n;i++)//执行2n+2次x=x+1;//执行n次程序共执行3n+2,取最高项，去掉该项的系数，T(n)=O(n)，称为线性阶；（3）

for(i=1;i<=n;i++)//执行2n+2次for(j=1;j<=n;j++)//执行n(2n+2)次x=x+1;//执行n2次,程序共执行3n2+4n+2,只取最高项，去掉该项的系数，T(n)=O(n2),称为平方

阶。常见的时间复杂度：O(1)＜O(log2n)＜O(n)＜O(n2)＜O(n3)＜O(2n)1.5.2算法性能分析与度量（3）算法的空间复杂度•空间复杂度是指程序运行从开始到结束所需的存储量。•算法的存储空间需求，类

似于算法的时间复杂度，为算法所需存储空间的量度，记做：S(n)=O(f(n))其中n为问题的规模。•一个程序在机器上执行时，除了需要寄存本身所用的指令，常数，变量和输入数据以外，还需要一些对数据进行操作的辅助存储空间。其中对于输入数据所占的具

体存储量只取决于问题本身，与算法无关。•若算法执行时所需要的辅助空间相对于输入数据量而言是个常数，则称这个算法为原地工作，辅助空间为O(1)。•算法的执行时间的耗费和所序的存储空间的耗费两者是矛盾的，难以兼得。即算法执行时间上的节省一定是以增加空间存储为代价的，反之亦然。

•常常以算法执行时间做为算法优劣的主要衡量指标。1.5.2算法性能分析与度量1.5.2算法的大致分类本书涵盖的算法大致可以被分为蛮力算法、分治算法、减治算法、变治算法以及动态规划算法等几大类。•蛮力法(BruteForce):直接解决问题的方法，不讲

究任何策略，基于问题的描述对结果进行枚举或暴力破解，因此也被称为穷举算法或枚举算法。蛮力法属于最容易应用的算法，因为其直接且没有策略，所以简单，但是通常来讲时间复杂度较高，效率低下。蛮力法的典型算法例如蛮力模式匹配算法等。•分治法(DivideandConqu

er):将复杂问题分解的方法，也就是俗称的分而治之。将一个复杂的问题分解成两个甚至更多的相同或相似的子问题，使得解决复杂问题的目标变成解决多个简单的子问题。原来复杂问题的解就是多个子问题的解的合集。分治法是很多高效算法的基础。分治法的典型算法例如快速排序算法、归并排序算法等。•减治法

(DecreaseandConquer):将大问题缩小规模最终变为小问题的方法。通过算法中每一步对问题规模的缩小，使得一个较大较复杂的问题最终变为较小的小问题，对最后的最小问题求解，便是最终大问题的解。减治法的典型算法例如二分查找

、插入排序、拓扑排序等。•变治法(TransferandConquer):变化问题求解的方法。基于变换的思想，把复杂问题变成简单的更容易求解的问题，也就是俗称的变而治之。典型的变治算法例如堆排序等。•动态规划(Dyn

amicProgramming):将问题分解称为不同的状态，后一个状态的最优解由前一个状态的最优解得到。典型的动态规划算法有弗洛伊德算法等。1.5.2算法的大致分类作业习题1.6