《数据结构与算法分析》课件第1章-绪论

第一章绪论数据结构概述算法分析程序设计关键技术

《数据结构与算法分析》是计算机程序设计的重要理论基础。学会分析计算机加工数据的结构特性，初步掌握基本算法的设计及分析技术，同时也是对复杂程序设计的训练。什么是数据结构数据结构的引入【例1】计算机管理图书目录问题。书名作者登录号分类号出版日期定价(元)Java语言李晓等9700001873.8792

991977/3/2643.5UNIX系统张昊9600012973.874

1261996/9/1923.5………………程序要处理各种数据，故需考虑数据之间的关系，将其组织、存储在计算机中，并以此为基础实现所要求的程序功能。书目信息组织存放在表中，完成相关查找运算。什么是数据结构【例2】工厂组织管理问题。组织机构抽象成树结构，以表示各数据之间的关系。什么是数据结构数据结构的研究范围

数据间的结构关系及表示

数据在计算机内的存储

数据处理的方法和技巧数据处理算法的性能分析数据结构的基本概念数据(data)描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。例，利用数值分析方法解代数方程组的程序处理的对象是整数和实数；文字处理程序的对象是字符。数据元素(data

element)数据的基本单位，即数据集合中的一个个体。可由若干数据项(dataitem)组成。数据项是数据的最小单位。数据对象(data

object)具有相同特性的数据元素的集合，是数据的一个子集。例：

N={0,±1,±2,…}数据结构的基本概念数据结构(data

structure)按某种逻辑关系组织起来的一批数据，应用计算机语言，按一定的存储表示方式把他们存储在计算机的存储器中，并在这些数据上定义了一个运算的集合。数据元素的集合D上关系的集合数据元素间的逻辑关系——逻辑结构数据元素及其关系在计算机存储器内的表示——存储结构

对数据施加的操作——数据的运算二元组：Data-Structure=(D,R)数据结构的基本概念【例3】

学生成绩管理系统。——线性表学生成绩表学号姓名数学物理英语01001赵89788101002钱677881……01099孙67817801100李918992逻辑关系：除开始和终端结点，每个结点只有一个直接前趋和直接后继。运算：查找、插入、删除、修改等。

存储：顺序和非顺序存储。数据结构的基本概念【例4】人机对弈问题。——树数据结构的基本概念【例5】多叉路口交通灯管理问题。(C和E为单行道)——图数据结构的基本概念数据的逻辑结构线性结构

有且仅有一个开始结点和一个终端结点，且所有结点都只有一个直接前趋和一个直接后继。如线性表。

非线性结构一个结点可能有多个直接前趋和直接后继。如树和图。数据结构的基本概念数据的存储结构

顺序存储

逻辑相邻的结点，其在内存的物理位置也相邻。

链接存储

结点存储在任意存储单元中，其邻接关系由指针表示。ABCDEF顺序存储链接存储数据结构的基本概念

索引存储

除存储数据信息，还需建立索引表。索引存储关键字地址53…………34……2921索引表学生数据表学号姓名性别籍贯29

张祺女陕西42

王军男山东38

江丽女北京34周强男北京21

刘晓飞男陕西53王江平男浙江30

陈娟女陕西数据结构的基本概念

散列存储以关键字项key为自变量，函数值f(key)为存放位置建立存储表。如数据集合：S={and,begin,do,end,for,go,if,then,year,zero}散列函数:f(key)=key[0]-'a'散列表:charHT[26][8];andbegindoendzeroyear...0123...2425

散列存储数据结构的基本概念抽象数据类型(ADT)将数据类型和数据类型上的运算捆在一起封装。目的将算法顶层设计与底层设计隔开，降低设计复杂性，提高模块复用程度，使程序有较高可靠性和较好的可维护性。ADT抽象数据类型名{数据对象：{数据对象的定义}数据关系：{数据元素间关系的定义}操作集合：{基本操作的定义}}ADT抽象数据类型名定义形式数据结构与程序设计数据结构+算法=程序数据是程序处理的对象根据目标系统的性能要求，合理设计数据的组织方式算法效率在很大程度上依赖于数据的组织数据结构

数据的运算

数据之间的逻辑关系

数据的组织及存储数据结构与程序设计【例6】电话号码查询问题。查找的效率取决于数据的组织和存储分析：方法一：信息随机存储线性结构姓名电话号码李丽7100791赵平8200504李小东8222031……——顺序查找数据结构与程序设计【例6】电话号码查询问题。查找的效率取决于数据的组织和存储方法二：建立索引表分析：姓王虹…地址李王赵…姓名电话号码李丽7100791王霞8209302……赵剑…索引结构——索引查找算法的性质及评价算法的性质由若干条指令组成的有限序列，满足以下性质：

可行性

有穷性

确定性

输入性

输出性算法的评价如何评价算法？衡量算法优劣的标准：正确性(correctness)

健壮性(robustness)

可读性(readability)效率与低存储量算法的效率分析算法（效率）的分析

预测算法所需的资源，如计算时间(CPU消耗)、内存空间(RAM消耗)等算法复杂度的衡量算法的优劣是由算法的复杂性决定的。资源（时间，空间）↑算法复杂度↑

时间复杂性

空间复杂性算法执行所耗费的时间度量算法所耗费的存储空间算法的效率分析影响算法复杂度的因素算法复杂性

C=F（I，N，A）I

—输入的数据。例如：若数据有序，则时间消耗可能会减少。N—数据的规模，即问题规模。A—算法本身。如何分析呢？

最坏情况：任意输入规模的最大运行时间。

平均情况：任意输入规模的平均运行时间。

最佳情况：通常最佳情况很少出现。算法的效率分析——时间复杂度若用n表示算法问题规模的量度，则算法的基本操作重复执行次数是n的函数f(n)。频度当n→∞时，f(n)的数量级（阶）称为算法的渐近时间复杂度，简称为时间复杂度，记为T(n)=O(f(n))

O的数学定义:

设f(N)和g(N)是定义在正数集上的正函数。如果存在常数C和自然数N0

，使得当N≥N0时，有f(N)≤C×g(N)，则称函数f(N)当N充分大时有上界，且g(N)是它的一个上界，记为f(N)=O(g(N))。f(N)的阶不高于g(N)的阶。算法中基本操作重复执行的次数。【例7】已知n阶方阵A和B，求乘积C=A×B。算法各语句频度之和为：for(i=0;i<n;i++)

for(j=0;j<n;j++){

c[i][j]=0;

for(k=0;k<n;k++)

c[i][j]=c[i][j]+a[i][k]*b[k][j];

}

//n＋1次

//n(n＋1)次

//n2次

//n2(n＋1)次

//n3次

T(n)=2n3＋3n2＋2n＋1T(n)=O(n3)当n→∞时limT(n)/n3=lim(2n3＋3n2＋2n＋1)/n3=2n→∞n→∞算法的效率分析——时间复杂度说明

通常可通过判定算法中重复执行次数最多的语句来估算时间复杂度。如：

常见的时间复杂度，按数量级递增排列：O(1),O(log2n),O(n),O(nlog2n),O(n2),O(n3),…O(nk),O(2n)

对于较复杂算法，可将其分割成易估算的几部分，再用求"和"原则得到整个算法的时间复杂度。如：则T(n)=O(1)—常数阶temp=i;i=j;j

=temp;若T1(n)=O(f(n))，T2(n)=O(g(n))则：T(n)=T1(n)＋T2(n)=O(max(f(n),g(n)))算法的效率分析——时间复杂度算法的效率分析——空间复杂度渐进空间复杂度(SpaceComplexity)是对算法所耗费的存储空间的度量，它也是问题规模n的函数，简称为空间复杂度。

算法的输入输出数据所占存储空间由要解决的问题决定的，它不随本算法的不同而改变。

算法在运行过程中临时占用的存储空间随算法策略而异。

存储算法本身所占存储空间与算法书写的长短成正比。设计算法时，需根据问题的具体需求在时间复杂度和空间复杂度之间进行权衡。程序设计的关键技术程序设计的环节明确需求设计编码测试

明确需求分析问题，明确“做什么”，谁使用程序，使用该程序的具体目的，程序的功能

设计程序结构设计、模块设计、数据结构与算法设计、用户界面设计

编码为每个模块设计编写程序，应有必要的文档

测试对程序的复审，是软件质量保证的关键步骤结构设计方法程序结构设计先设计第一层(即顶层)，逐层细分，逐步求精，直到整个问题可用程序设计语言明确地描述出来为止。特点：先整体后局部，先抽象后具体。自底向上先底层再顶层，由表及里、由浅入深地解决问题。特点：主要用于修改、优化或扩充一个程序。自顶向下结构设计任务程序结构设计(1)将程序划分成模块(2)决定各个模块的功能(3)决定模块间的调用关系(4)决定模块间的界面模块分解，即将较大的软件系统分解成若干较小的具有特定功能的模块，并确定软件系统中模块的层次结构。

模块划分“功能独立”，以降低开发、测试、维护的代价

模块优劣的评价因素：信息隐蔽发生变化的因素包含在某个模块内部，使其它模块与此因素无关。内聚模块内各成分之间相关联程度的度量。耦合模块之间依赖程度的度量。影响其强度的因素：（1）一个模块对另一个模块的调用（2）一个模块向另一个模块传递的数据量（3）一个模块施加到另一个模块的控制的多少（4）模块之间接口的复杂程度程序结构设计

模块接口及调用关系的确定程序结构设计

模块设计输入到输出的映射建模数据结构和算法设计

良好的编程风格命名名称简洁，具有一定的说明性注释简洁地说明程序的突出特征，帮助读者理解程序程序外观一致、统一的块对齐方式适当的缩进和空白使用简洁、清晰的表达式程序结构设计

排错与测试排错有利于减少排错时间的因素：好的设计、好的风格、边界条件测试、代码中的断言和合理性检查、防御性程序设计、设计良好的界面、限制全局数据结构以及检查工具等。充分利用系统调试工具积极寻找错误线索（1）寻找熟悉的模式（2）检查最近的改动（3）取得堆栈轨迹（4）认真阅读代码程序结构设计测试测试代码的边界情况根据软件开发各阶段的规格说明和程序的内部结构而精心设计一批测试用例（即输入数据及预期的输出结果），并利用这些测试用例运行程序，以发现程序错误的过程。测试前置条件和后置条件以递增方式做测试合理设计测试用例：等价分类法、边界值分析法、错误猜测法、因果图法、逻辑覆盖法

程序性