计算机软件及应用绪论课件

《计算机软件及应用绪论课件》由会员分享，可在线阅读，更多相关《计算机软件及应用绪论课件（74页珍藏版）》请在金锄头文库上搜索。

1、数据数据结构及构及应用算法教程用算法教程(修修订版版)配套课件配套课件1计算机软件及应用 绪论第第1章章 绪 论 本章将本章将讲讲述数据述数据结结构的各种概念和定构的各种概念和定义义。使用使用类类C C语语言描述数据言描述数据结结构的算法构的算法时时，引入了少量的，引入了少量的C+C+语语言言扩扩展的内容，以有利于算法的表达。展的内容，以有利于算法的表达。算法分析的方法是算法分析的方法是评评估数据估数据结结构及其算法效率的重要构及其算法效率的重要依据，依据，该该方法将方法将贯贯穿全穿全书书的始的始终终。考考虑虑内容的内容的连贯连贯，绪论课绪论课件中含抽象数据件中含抽象数据类类型的介型的介绍绍，

2、有关的运用有关的运用细节细节可参可参见见教科教科书书的第的第1010章。章。讲讲授本章授本章课课程大程大约约需需4 4课时课时。2计算机软件及应用 绪论v 1.1 数据数据结构构讨论的范畴的范畴v 1.2 与数据与数据结构相关的概念构相关的概念v 1.3 算法及其描述和分析算法及其描述和分析3计算机软件及应用 绪论1.1 数据数据结构构讨论的范畴的范畴Niklaus Wirth： Algorithm + Data Structures = Programs 算法算法 +数据数据结构构 = 程序程序程序程序设计:算法算法: 数据数据结构构: 为计算机处理问题编制一组指令集 处理理问题的策略的策略

3、问题的数学模型的数学模型4计算机软件及应用 绪论 结构静力分析构静力分析计算算例如例如: 数数值计算算的程序设计问题 线性代数方程组 环流模式方程(球面坐标系)全球天气全球天气预报5计算机软件及应用 绪论非数非数值计算算的程序的程序设计问题例一例一: 求一组(n个)整数整数中的最大值算法: ?模型：？基本操作是“比比较两个数的大小两个数的大小”取决于整数整数值的范的范围6计算机软件及应用 绪论例二：例二：计算机对弈算法：?模型：?对弈的规则和策略棋盘及棋盘的格局7计算机软件及应用 绪论例三：例三：足协的数据库管理算法：?模型：?需要管理的项目？如何管理？用户界面？各种表格8计算机软件及应用 绪

4、论概括地概括地说： 数据数据结构是一构是一门讨论“描述描述现实世界世界实体的数学模型体的数学模型(非数非数值计算算)及其上的操作在及其上的操作在计算机中如何表示算机中如何表示和和实现”的学科。的学科。9计算机软件及应用 绪论1.2 与数据与数据结构相关的概念构相关的概念一、基本概念和一、基本概念和术语二、数据二、数据结构构三、数据三、数据类型和抽象数据型和抽象数据类型型10计算机软件及应用 绪论一、基本概念和一、基本概念和术语所有能被被输入入到计算机中，且能被计算机处理的符号理的符号的集合。数据数据:是计算机操作的算机操作的对象象的总称。是计算机处理的信息的信息的某种特定的符号表示形式表示形式

5、。11计算机软件及应用 绪论是数据（集合）中的一个“个体个体”数据元素数据元素:是数据结构中讨论的基本基本单位12计算机软件及应用 绪论 数据数据项：是数据结构中讨论的最小最小单位数据元素可以是数据数据元素可以是数据项的集合的集合例如：描述一个运动员的数据元素可以是姓名姓名俱俱乐部名称部名称出生日出生日期期参加日期参加日期职务 业绩称之为组合项年年 月月 日日编号号关键码13计算机软件及应用 绪论二、数据二、数据结构构 数据数据结构构是带“结构构”的数据元素的集合。14计算机软件及应用 绪论 假设用三个三个 4 位的十位的十进制数制数表示一个含 12 位数的十位数的十进制数。制数。3214,6

6、587,9345 a1(3214),a2(6587),a3(9345)则在数据元素a1、a2 和 a3 之间存在着“次序次序”关系关系 a1,a2 、 a2,a3 3214，6587，9345 a1 a2 a3 6587，3214，9345 a2 a1 a3例如例如: 示例一：15计算机软件及应用 绪论 在2行3列的二维数组a1, a2, a3, a4, a5, a6中六个元素之间存在两个关系:行的次序关系行的次序关系:列的次序关系列的次序关系:row = ,col = , a1 a3 a5 a2 a4 a6 a1 a2 a3a4 a5 a6 示例二：16计算机软件及应用 绪论 在一维数组a1

7、, a2, a3, a4, a5, a6 的数据元素之间存在如下的次序关系次序关系:| i=1, 2, 3, 4, 5 或者说，数据数据结构构是相互之相互之间存在着某存在着某种种逻辑关系的数据元素的集合关系的数据元素的集合。可见，不同的“关系关系”构成不同的“结构构” 示例三：17计算机软件及应用 绪论数据的逻辑结构构可归结为以下四四类:线性线性结构树形树形结构图状图状结构集合集合结构18计算机软件及应用 绪论数据数据结构构的形式定的形式定义为:数据结构数据结构是一个二元组Data_Structures = (D, S)其中:D 是数据元素的有限集数据元素的有限集，S 是 D上关系的有限集关系

8、的有限集。19计算机软件及应用 绪论数据的数据的存存储结构构 逻辑结构在存储器中的映象映象“数据元素”的映象 ？“关系”的映象 ？20计算机软件及应用 绪论数据元素的映象方法：数据元素的映象方法：用二进制位(bit)的位串表示数据元素(321)10 = (501)8 = (101000001)2 A = (101)8 = (001000001)221计算机软件及应用 绪论关系关系的映象方法：的映象方法：（表示x, y的方法）顺序映象序映象以相以相对的存的存储位置表示后位置表示后继关系关系例如例如:令 y 的存储位置和 x 的存储位置之间差一个常量 C 而 C 是一个隐含值，整个存整个存储结构中

9、构中只含数据元素本身的信息只含数据元素本身的信息x yC22计算机软件及应用 绪论链式映象式映象以附加信息以附加信息(指指针)表示后表示后继关系关系需要用一个和x 在一起的附加信息附加信息指示y 的存储位置y x23计算机软件及应用 绪论在不同的编程环境中，存储结构可有不同的描述方法。 当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。24计算机软件及应用 绪论例如例如: 以三个带有次序关系的整数表示一个长整数时，可利用C 语言中提供的整数数组类型。 typedef int Long_int 3；定义长整数为:25计算机软件及应用 绪论 在用高级程序语言编写的程序中，

10、必须对程序中出现的每个变量、常量或表达式，明确明确说明明它们所属的数据数据类型型。三、数据三、数据类型和抽象数据型和抽象数据类型型数据数据类型型26计算机软件及应用 绪论例如，C 语言中提供的基本数据基本数据类型型有:整型整型 int浮点型浮点型 float字符型字符型 char逻辑型逻辑型 bool （ C+语言）语言）双精度型双精度型 double实型实型（ C+语言语言）27计算机软件及应用 绪论 数据数据类型型是一个值的集合的集合和定义在此集合上的一一组操作操作的总称。 不同类型的变量，其所能取的值的范的范围不同，所能进行的操作行的操作不同。28计算机软件及应用 绪论抽象数据抽象数据类

11、型型(Abstract Data Type 简称称ADT) 是指一个数学模型以及定是指一个数学模型以及定义在在此数学模型上的一此数学模型上的一组操作。操作。29计算机软件及应用 绪论例如，例如，抽象数据类型复数复数的定义： 数据数据对象：象：De1,e2e1,e2RealSet 数据关系：数据关系：R1 | e1是复数的实数部分 | e2 是复数的虚数部分 ADT Complex 30计算机软件及应用 绪论基本操作：基本操作： AssignComplex( &Z, v1, v2 )操作结果：构造复数Z,其实部和虚部分别被赋以参数v1 和v2 的值。 DestroyComplex( &Z)操作结

12、果：复数Z被销毁。 GetReal( Z, &realPart )初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。31计算机软件及应用 绪论 GetImag( Z, &ImagPart )初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。 Add( z1,z2, &sum )初始条件：z1, z2是复数。操作结果：用sum返回两个复数z1, z2 的和值。 ADT Complex32计算机软件及应用 绪论假设:z1和z2是上述定义的复数则Add(z1, z2, z3) 操作的结果z3 = z1 + z2即为用户需求的复数求和的结果33计算机软件及应用

13、绪论ADT 有两个重要特征:数据抽象数据抽象 用ADT描述程序处理的实体时，强调的是其本本质的特征的特征、其所能完成的功能其所能完成的功能以及它和外部用外部用户的接口的接口（即外界使用它的外界使用它的方法方法）。数据封装数据封装 将实体的外部特性和其内部外部特性和其内部实现细节分离分离，并且对外部用外部用户隐藏藏其内部其内部实现细节。34计算机软件及应用 绪论抽象数据抽象数据类型的形式描述型的形式描述 抽象数据类型可用(D, S, P)三元组表示 其中： D 是数据对象； S 是 D 上的关系集； P 是对 D 的基本操作集。 35计算机软件及应用 绪论ADT 抽象数据抽象数据类型名型名 数据

14、数据对象：象：数据对象的定义 数据关系：数据关系：数据关系的定义 基本操作：基本操作：基本操作的定义 ADT 抽象数据类型名其中基本操作的定义格式为:基本操作名基本操作名(参数表) 初始条件：初始条件：初始条件描述 操作操作结果果：操作结果描述 36计算机软件及应用 绪论赋值参数参数 只为操作提供输入值。引用参数引用参数 以&打头，除可提供输入值外，还将返回操作结果。初始条件初始条件 描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。操作操作结果果 说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略之。37计算机软件及应用 绪

15、论抽象数据抽象数据类型的表示和型的表示和实现 抽象数据类型需要通过固有数据固有数据类型型(高级编程语言中已实现的数据类型)来实现。例如，对以上定义的复数。38计算机软件及应用 绪论typedef struct float realpart； float imagpart；complex；/ -存储结构的定义/ -基本操作的函数原型说明void Assign( complex &Z, float realval, float imagval )；/ 构造复数Z,其实部和虚部分别被赋以参数/ realval 和imagval 的值39计算机软件及应用 绪论float GetReal( cpmple

16、x Z )； / 返回复数Z 的实部值float Getimag( cpmplex Z )； / 返回复数Z 的虚部值void add( complex z1, complex z2, complex &sum )；/ 以 sum 返回两个复数z1, z2 的和40计算机软件及应用 绪论/ -基本操作的实现void add( complex z1, complex z2, complex &sum ) / 以 sum 返回两个复数z1, z2 的和sum.realpart = z1.realpart + z2.realpart; sum.imagpart = z1.imagpart + z2.

17、imagpart; 其它省略 41计算机软件及应用 绪论1.3 算法及其描述和分析算法及其描述和分析一、算法一、算法二、算法的描述二、算法的描述三、算法效率的衡量方法和准三、算法效率的衡量方法和准则四、算法的存四、算法的存储空空间需求需求42计算机软件及应用 绪论 算法算法是为了解决某类问题而规定的一个有限长的操作序列操作序列。一个算法必须满足以下五个重要特性：1有有穷性性 2确定性确定性 3可行性可行性4有有输入入 5有有输出出一、算法一、算法43计算机软件及应用 绪论1. 有有穷性性对于任意一组合法输入值，在执行有有穷步步骤之后一定能结束，即：算法中的每个步骤都能在有限有限时间内完成。2.

18、 确定性确定性 对于每种情况每种情况下所应执行的操作，在算法中都有确切确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且并且在任何条件下，算法都只有一条在任何条件下，算法都只有一条执行路径。行路径。44计算机软件及应用 绪论3. 可行性可行性算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。4. 有有输入入作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。45计算机软件及应用 绪论 5. 有有输出出它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结

19、，这种确定关系即为算法的功能。46计算机软件及应用 绪论 具备上述特征的计算描述，只是具有了算法的基本属性。设计算法时，通常还应考虑满足以下目标： 1.正确性正确性，2.可可读性性， 3.健壮性健壮性 4.高效率与低存高效率与低存储量需求量需求47计算机软件及应用 绪论效率效率和和存存储量量都与都与问题的的规模模有关有关 通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。48计算机软件及应用 绪论二、算法的描述二、算法的描述v 采用类C语言进行描述（不拘泥于某个具体版本的C语言）v 利用了C+对C的部分扩展功能49计算机软件及应用 绪论v 使用

20、引用参数（以&标记），作为函数 输出数据的管道。如：void programXP (BiTree T, int a, int &sum) / sum的初值为0，/ 调用之后，由引用参数sum把算法programXP的/ 计算结果传递给调用者 例如：50计算机软件及应用 绪论再例如：v 简化动态分配空间的描述。如：u 使用C语言的风格描述： T=(BiTNode*)malloc(sizeof(BiTNode);u 本书采用C+语言的风格描述： T= new BiTNode;51计算机软件及应用 绪论三三、算法效率的、算法效率的衡量方法和准衡量方法和准则通常有两种两种衡量算法效率的方法:事后事后统

21、计法法事前分析估算法事前分析估算法缺点：缺点：1. 必须执行程序 2. 其它因素掩盖算法本质52计算机软件及应用 绪论和算法执行时间相关的因素因素：1. 算法算法选用的策略策略2. 问题的的规模模3. 编写程序的语言4. 编译程序产生的机器代码的质量5. 计算机执行指令的速度53计算机软件及应用 绪论 一个特定算法的算法的“运行工作量运行工作量”的大小，只依赖于问题的规模(通常用整数量n表示),或者说,它是是问题规模的函数模的函数。54计算机软件及应用 绪论 假如，随着问题规模 n 的增长，算法算法执行行时间的增的增长率和率和 f(n) 的增的增长率相同率相同，则可记作：T (n) = O(f

22、(n)称称T (n) 为算法的算法的(渐近)时间复复杂度。度。55计算机软件及应用 绪论 如何估算如何估算算法的算法的时间复复杂度？度？56计算机软件及应用 绪论算法算法 = 控制控制结构构 + 原操作原操作（固有数据类型的操作）算法的算法的执行行时间=原操作原操作(i)的的执行次数行次数原操作原操作(i)的的执行行时间 算法的算法的执行行时间与与原操作原操作执行次数之和行次数之和成正比成正比57计算机软件及应用 绪论 从算法中选取一种对于所研究的问题来说是基本操作基本操作 的原操作，以该基本操作在算法中重复在算法中重复执行的次数行的次数作为算法运行时间的衡量准则。58计算机软件及应用 绪论v

23、oid mult(int a, int b, int& c ) / 以二维数组存储矩阵元素，/ c 为a 和b 的乘积 for (i=1; i=n; +i) for (j=1; j=n; +j) ci,j = 0; for (k=1; k=n; +k) ci,j += ai,k*bk,j; /for /mult基本操作: 乘法乘法操作时间复杂度: O(n3)例一两个矩阵相乘59计算机软件及应用 绪论void select_sort(int& a, int n) / 将 a 中整数序列重新排列成 / 自小至大有序的整数序列。 / select_sort基本操作: 比比较(数据元素) 操作操作时间

24、复杂度: O(n2)j = i; / 选择第i 个最小元素for ( k = i+1; k n; +k ) if (ak aj ) j = k;for ( i = 0; i1 & change; -i) / bubble_sort基本操作: 赋值操作时间复杂度: O(n2) change = FALSE; / change 为元素进行交换标志 for (j=0; j aj+1) aj aj+1; change = TRUE ; / 一趟起泡例三例三 起泡排序起泡排序61计算机软件及应用 绪论四、算法的存四、算法的存储空空间需求需求算法的空空间复复杂度定度定义为: 表示随着问题规模 n 的增大,

25、算法运行所需存储量的增长率与 g(n) 的增长率相同。S(n) = O(g(n)62计算机软件及应用 绪论算法的存算法的存储量量包括:1. 输入数据入数据所占空间2. 程序本身程序本身所占空间3. 辅助助变量量所占空间63计算机软件及应用 绪论 若输入数据入数据所占空间只取决于问题 本身，和算法无关和算法无关，则只需要分析除 输入和程序之外的辅助助变量量所占额外外 空空间。 若所需额外空间相对于输入数据量 来说是常数，则称此算法为原地工作原地工作。 若所需存储量依赖于特定的输入，则通常按最坏情况考虑。64计算机软件及应用 绪论本章学本章学习要点要点65计算机软件及应用 绪论1. 熟悉各名熟悉各

26、名词、术语的含的含义，掌握基，掌握基本概念。本概念。2. 理解算法五个特征的确切含理解算法五个特征的确切含义。3. 掌握通掌握通过计算算“原操作原操作”语句的次句的次数来估算算法数来估算算法时间复复杂度的方法。度的方法。66计算机软件及应用 绪论习题解答解答实例例67计算机软件及应用 绪论v 算法算法设计题1-7 对于一维数组A0.n-1 (n1)，设计在时间和空间方面尽可量有效率的算法，将A中的序列循环左移p(0pn)个位置，即将A中的数据从 （A0, A1, ., An-1）转 变成（Ap,Ap+1,. ,An-1,A0,A1,.,Ap-1），并分析所设计算法的时间复杂度和空间复杂度。68

27、计算机软件及应用 绪论 从简到繁，我们按四种思路构思算法，并逐一分析时间和空间方面的效率。具体的算法参见习题的解答实例。 在下面的实例演示中，假设n=12，p=3 69计算机软件及应用 绪论（参考答案之（参考答案之1）A0A11A1A2A3A4A5A6A7A8A9A10A1A2A3A4A5A6A7A8A9A10A11A0A2A3A4A5A6A7A8A9A10A11A0A1A3A4A5A6A7A8A9A10A11A0A1A2 首先设计一个左移1位的函数，然后3次调用该函数，实现数组元素左移3位。70计算机软件及应用 绪论（参考答案之（参考答案之2）A0A11A1A2A3A4A5A6A7A8A9A

28、10A11A3A4A5A6A7A8A9A10A0A1A2A11A3A4A5A6A7A8A9A10A0A1A2 先将A0, A1, A2缓存到辅助空间，其余元素一次性左移3位，再把缓存的那3个元素复制到数组A的尾部。71计算机软件及应用 绪论（参考答案之（参考答案之3）A0A11A1A2A3A4A5A6A7A8A9A10A3A11A1A2A6A4A5A9A7A8A0A10第一趟A3A11A4A2A6A7A5A9A10A8A0A1第二趟A3A2A4A5A6A7A8A9A10A11A0A1第三趟 每一趟，按步距p=3, (循环)左移调换元素，一次定位，共进行3趟。72计算机软件及应用 绪论（参考答案

29、之（参考答案之4）A0A11A1A2A3A4A5A6A7A8A9A10A11A0A10A9A8A7A6A5A4A3A2A1A3A0A4A5A6A7A8A9A10A11A2A1A3A2A4A5A6A7A8A9A10A11A0A1第一次逆置第二次逆置第三次逆置 通过三次逆置数组的元素来实现左移，首先，整体逆置；然后分别对左部的9个元素和右部的3个元素进行逆置。73计算机软件及应用 绪论四个算法的时空分析比较v参考答案之参考答案之1: 时间复杂度O(p*n) 空间复杂度O(1) v参考答案之参考答案之2: 时间复杂度O(n) 空间复杂度O(p) v参考答案之参考答案之3: 时间复杂度O(n) 空间复杂度O(1) v参考答案之参考答案之4: 时间复杂度O(n) 空间复杂度O(1) 74计算机软件及应用 绪论