1、第一章 绪论1.3 算法和算法的描述1.1 什么是数据结构 1.2 基本概念和术语1.1 什么是数据结构 当今计算机应用的特点：l计算机应用领域从科学计算到非数值计算,更多地是需要对其进行组织、管理和检索; l所处理的数据量大且具有一定的关系.下面举几个非数值计算的例子线性表例1 学生档案管理系统 学 生 基本 情 况学 号姓 名性 别出 生 年 月.99070101李 军男80 12.99070102王 颜 霞女81 2.99070103孙 涛男80 9.99070104单 晓 宏男81 3. 假设一个学生档案管理系统应包含如下表所示的学生信息特点： l每个学生的信息占据一行，所有学生的信息
2、按学号顺序依次排列构成一张表格； l表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构； l对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。例2 人机对奕问题树.例3 制定教学计划图 计算机专业学生的必修课程课程编号课程名称需要的先导课程编号C 1程序设计基础无C 2离散数学C 1C 3数据结构C 1 ，C 2C 4汇编语言C 1C 5算法分析与设计C 3 ，C 4C 6计算机组成原理C 1 1C 7编译原理C 5 ，C 3C 8操作系统C 3 ，C 6C 9高等数学无C 1 0线性代数C 9C 1 1普通物理
3、C 9C 1 2数值分析C 9 ，C 1 0 ，C 1 在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表所示：c1c9c4c2c12c10c11c5c3c6c7c8课程先后关系的图形描形式：特点： 课程之间的先后关系用图结构描述； 通过实施创建图结构，按要求将图结构中的顶点进行线性排序。 结论 计算机的操作对象的关系复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理，我们将此称为非数值性处理。要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些数据
4、之间的关系，在计算机中的存储方式以及各个操作的具体实现。数据结构的研究内容为：数据结构的研究内容为： 研究非数值计算的程序设计问题中计算机的研究非数值计算的程序设计问题中计算机的操作操作对象对象以及它们之间的以及它们之间的关系和操作关系和操作等的学科等的学科。 能够分析研究计算机加工的对象的特性，获得其逻辑结构，根据需求，选择合适存贮结构及其相应的算法； 学习一些常用的算法； 复杂程序设计的训练过程，要求编写的程序结构清楚和正确易读； 初步掌握算法的时间分析和空间分析技术。1.2 基本概念和术语一、基本概念一、基本概念二、数据类型二、数据类型三、抽象数据类型三、抽象数据类型 学生基本情况学 号
5、姓 名性 别出生年月.99070101李 军男8012.99070102王颜霞女812.99070103孙 涛男809.99070104单晓宏男813.数据:所有能被输入到计算机中，且能被计算机处理的符号的集合。不仅包括数字、字符串，还包括图形、图像、声音、动画、视频等数据形式。数据元素:数据的基本单位，也称结点（node）或记录（record） 。数据项:是数据结构中讨论的最小最小单位。一个数据元素可由若干数据项组成。数据元素数据项一、基本概念一、基本概念三者之间的关系：数据 数据元素 数据项例：学生表 个人记录 学号、姓名4. 数据对象：是性质相同的数据元素的集合，是数据的一个子集。u整数
6、数据对象 N = 0, 1, 2, u学生数据对象 学生记录的集合5、数据结构（Data Structure）是相互之间存在一种或多种特定关系的数据元素的集合。数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。6 逻辑结构 数据结构中所说的数据结构中所说的“关系关系”实际上是指数据元素之间的实际上是指数据元素之间的逻辑关系，又称此为逻辑结构。逻辑关系，又称此为逻辑结构。集合数据元素间除“同属于一个集合”外，无其它关系线性结构 一对一的关系， 如线性表、栈、队列树型结构 一对多的关系，如树图状结构或网状结构 多对多的关系，如图。数据之间的关系分为四类：7.存储结构（物理
7、结构） ：数据在计算机中的存储表示。链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系。 (可以占用不连续的存储单元）分为两种：顺序存储结构：借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系。(占用连续的存储单元）head990180990290990375NULLa 0 1 2 3 4 5 6 7 8 9顺序存储结构链式存储结构l逻辑结构和存储结构都相同逻辑结构和存储结构都相同, , 但运算不同但运算不同, , 则数则数据结构不同据结构不同. . 例如例如, , 栈与队列栈与队列l对于一种数据结构对于一种数据结构, , 常见的运算常见的运算u 插入插入u 删除删除u 修
8、改修改u 查找查找u 排序排序数据的运算数据的运算 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：插入、删除、修改、查找、排序数据的运算：插入、删除、修改、查找、排序 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表 栈、队列栈、队列 串、数组串、数组树形结构树形结构图形结构图形结构逻辑结构逻辑结构唯一唯一存储结构存储结构不唯一不唯一运算的实现运算的实现依赖于依赖于存储结构存储结构二、数据类型二、数据类型数据类型数据类型 是一个值的集合和定义在此集合上的一组操作的总是一个值的集合和定义在此集合上的一组操作的总称。称。 在程序设计
9、语言中，每一个数据都属于某种数据类型。类在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。可以认为，数据类型是在程序设计中已经实现进行的运算。可以认为，数据类型是在程序设计中已经实现了的数据结构。了的数据结构。C语言语言：基本数据类型：基本数据类型： char int float double void构造数据类型：构造数据类型：数组、结构体、共用体、文件数组、结构体、共用体、文件 三、抽象数据类型三、抽象数据类型 (Abstract Data Type 简称简称ADT) 是指一
10、个数学模型以及定义在此数学是指一个数学模型以及定义在此数学模型上的一组操作。模型上的一组操作。 抽象数据类型实际上就是对该数据结构的抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组及在此结构上的一组操作操作。ADT 有两个重要特征:数据抽象数据抽象 用ADT描述程序处理的实体时，强调的是其本质的特征本质的特征、其所能完成的功能其所能完成的功能以及它和外部用户的接口外部用户的接口（即外界使用它的方外界使用它的方法法）。数据封装数据封装 将实体的外部特性和其内部实现外部特性和其内部实现细节分离细节分离，并且对外部用户
11、隐藏对外部用户隐藏其内部实其内部实现细节。现细节。抽象数据类型抽象数据类型可以用以下的三元组来表示：可以用以下的三元组来表示： ADT = （D，S，P） 数据对象数据对象 D上的关系集上的关系集 D上的操作集上的操作集 ADTADT抽象数据类型名抽象数据类型名 数据数据对象对象： 数据数据关系关系： 基本基本操作操作 ： ADT ADT抽象数据类型抽象数据类型名名ADT常用常用定义定义格式格式抽象数据类型的描述方法抽象数据类型的描述方法例如，例如，抽象数据类型复数复数的定义： 数据对象：数据对象： De1,e2e1,e2RealSet 数据关系：数据关系： R1 | e1是复数的实数部分 |
12、 e2 是复数的虚数部分 ADT Complex 基本操作：基本操作：AssignComplex( &Z, v1, v2 )操作结果：构造复数 Z,其实部和虚部 分别被赋以参数 v1 和 v2 的值。DestroyComplex( &Z)操作结果：复数Z被销毁。 GetReal( Z, &realPart )初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。GetImag( Z, &ImagPart )初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。Add( z1,z2, &sum )初始条件：z1, z2是复数。操作结果：用sum返回两个复数z1,
13、z2 的和值。 ADT Complex假设:z1和z2是上述定义的复数则 Add(z1, z2, z3) 操作的结果z3 = z1 + z2即为用户企求的结果抽象数据类型的表示与实现抽象数据类型的表示与实现抽象数据类型可以通过抽象数据类型可以通过固有的固有的数据类型（如整数据类型（如整型、实型、字符型等）来表示和实现。型、实型、字符型等）来表示和实现。教材中用的是教材中用的是类类C C语言（介于伪码和语言（介于伪码和C C语言之间）语言之间）作为描述工具作为描述工具但上机时要用具体语言实现，如但上机时要用具体语言实现，如C C或或C+C+等等例如，对前面定义的复数。typedef struct
14、 float realpart； float imagpart；complex；/ -存储结构的定义存储结构的定义/ -基本操作的实现基本操作的实现void add( complex z1, complex z2, complex &sum ) / 以 sum 返回两个复数 z1, z2 的和 sum.realpart = z1.realpart + z2.realpart; sum.imagpart = z1.imagpart + z2.imagpart; 其它省略 1.3 1.3 算法和算法的衡量算法和算法的衡量一、算法一、算法二、算法设计的原则二、算法设计的原则三、算法效率的衡量方法和准
15、则三、算法效率的衡量方法和准则四、算法的描述四、算法的描述算法是对特定问题求解步骤的一种描述，是指令的有限序列。一、算法一、算法计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、插入、删除等等。设计算法的基本过程通过对问题进行详细地分析，抽象出相应的数学模型；确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法；选用某种语言将算法转换成程序；调试并运行这些程序。例如：复数运算的实现一个算法必须满足以下五五个重要特性特性：1有穷性: 一个算法必须总是在执行有穷步之后结束， 且每一步都在有穷时间内完成。2
16、确定性：算法的每一步必须是确切定义的， 不能产生二义性 3可行性：算法是能够实现的.即算法描述的操作都是可以 通过已经实现的基本运算执行有限次来实现的。4有输入：一个算法有零个或多个输入 5有输出：一个算法有零个或多个输出 二、算法设计的原则二、算法设计的原则设计算法时，通常应考虑达到以下目标：1正确性正确性: :2. . 可读性可读性: :3健壮性健壮性: :4高效率与低存储量需求高效率与低存储量需求效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。标准：通常对于精心选择的典型、苛刻而带有刁难性的几组输入数据程序能够得出满足规格说明要求的结果。算法应易于阅读和理解，以
17、便于调试和修改。算法应具有容错处理。当输入数据非法时，算法能做出适当的反应和进行特殊处理，而不是产年莫名其妙的输出结果。三、算法效率的衡量方法和准则三、算法效率的衡量方法和准则通常有两种两种衡量算法效率的方法: 事后统计法：事后统计法：事前分析估算法事前分析估算法1.1.事后统计：事后统计：利用计算机内的计时功能，不同算法利用计算机内的计时功能，不同算法的程序可以用一组或多组相同的统计数据区分的程序可以用一组或多组相同的统计数据区分 缺点：缺点：必须先运行依据算法编制的程序必须先运行依据算法编制的程序所得时间统计量依赖于硬件、软件等环境因素所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身
18、的优劣，掩盖算法本身的优劣 2.2.事前分析估计：事前分析估计：一个高级语言程序在计算机上运行所消耗的时间取一个高级语言程序在计算机上运行所消耗的时间取决于：决于： 依据的算法选用何种策略依据的算法选用何种策略 问题的规模问题的规模 程序语言程序语言 编译程序产生机器代码质量编译程序产生机器代码质量 机器执行指令速度机器执行指令速度 同一个算法用不同的语言、不同的编译程序、在不同同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行，效率均不同，的计算机上运行，效率均不同，使用使用绝对时绝对时间单位间单位衡量算法效率不合适衡量算法效率不合适算法算法 = = 控制结构控制结构 + + 基本
19、操作基本操作 算法的执行时间算法的执行时间 =基本操作基本操作(i)(i)的执行次数的执行次数基本操作基本操作(i)(i)的执行时间的执行时间算法的执行时间算法的执行时间 与与 基本操作执行次数之和基本操作执行次数之和 成正比成正比 如何估算算法的时间复杂度？如何估算算法的时间复杂度？ 从算法中选取一种对于所研究的问题来说是 基本操作基本操作 的原操作，以该基本操作 在算法中重复执行的次数在算法中重复执行的次数 作为算法运行时间的衡量准则。算法中算法中基本操作基本操作（循环）（循环）重复执行的次数是问题规模重复执行的次数是问题规模n n的的某个函数某个函数f(n),f(n),它是一个算法运行时
20、间的相对量度它是一个算法运行时间的相对量度, ,算法算法的时间量度记作：的时间量度记作： T(n)=T(n)=O(f(n)(f(n) 时间复杂度的渐进表示法时间复杂度的渐进表示法它表示随着问题规模它表示随着问题规模 n n 的增长，算法执行时间的增长率的增长，算法执行时间的增长率和和 f(n) f(n) 的增长率相同的增长率相同，T(n) T(n) 称作算法的称作算法的( (渐近渐近) )时间复时间复杂度。杂度。例1：+x;s=0;1O(1)for(i=1;i=n;+i)+x;s+=x;nO(n)for(j=1;j=n;+j)for(k=1;k=n;+k)+x;s+=x;n*nO(n2)例2：
21、例3：频度时间复杂度程序时间复杂度的计算：例4：void 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;/语句的频度语句的频度: 重复执行的次数：重复执行的次数：n3; /for /mult基本操作: 乘法乘法操作时间复杂度: O(n3)T( n ) = O ( n 3)即：矩阵乘法的运算量和问题的规模即：矩阵乘法的运算量和问题的规模n的立方是同一个的立方是同一
22、个量级量级x = 0; y = 0;for ( int k = 0; k n; k + ) x +;for ( int i = 0; i n; i+ ) for ( int j = 0; j n; j+ ) y +;T1(n) = O(1)T2(n) = O(n)T3(n) = O(n2)T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2)例5： void exam ( float x , int m, int n ) float sum ; for ( int i = 0; i m; i+ ) /x中各行数据累加 sumi = 0.0
23、; for ( int j = 0; j n; j+ ) sumi += xij; /关键操作关键操作 for ( i = 0; i m; i+ ) /打印各行数据和 cout i “ : ” sum i endl; /关键操作关键操作 渐进时间复杂度为 O(max (m*n, m)算法的时间复杂度是由算法的时间复杂度是由嵌套最深层嵌套最深层语句的频度决定的语句的频度决定的例6：for( i=1; i=n; i+) for (j=1; j=i; j+) for (k=1; k=j; k+)x=x+1;niniijniijjkiij1111112)1(16)2)(1(2)1(6)12)(1(21
24、21112nnnnnnnniinini语句频度语句频度 =例7：例例8：分析以下程序段的时间复杂度分析以下程序段的时间复杂度i=1; while(i=n) i=i*2; nnf)(2即即f(n)log2n，取最大值取最大值f(n)=log2n所以该程序段的时间复杂度所以该程序段的时间复杂度T(n) =O( log2n)【例例9】顺序查找，在数组顺序查找，在数组ai中查找值等于中查找值等于e的的元素，返回其所在位置。元素，返回其所在位置。 for (i=0;i n;i+) if (ai=e) return i+1; return 0;有的情况下，算法中基本操作重复执行的次数还有的情况下，算法中基
25、本操作重复执行的次数还随问题的随问题的输入数据集输入数据集不同而不同不同而不同最好情况：最好情况：1 1次次 最坏情况：最坏情况：n n平均时间复杂度为平均时间复杂度为:O(n):O(n)复杂度高复杂度高复杂度低复杂度低指数时间的关系为：指数时间的关系为： O(2n)O(n!)O(nn) 当当n n取得很大时，指数时间取得很大时，指数时间算法和多项式时间算法在算法和多项式时间算法在所需时间上非常悬殊所需时间上非常悬殊n 空间复杂度:算法所需存储空间的度量，记作: S(n)=O(g(n) 其中n为问题的规模(或大小)n算法要占据的空间算法本身要占据的空间输入数据所占空间算法要使用的辅助空间若输入
26、数据所占空间和算法无关，则只需要分析除输入和程序之外的辅助变量辅助变量所占额外空间额外空间。渐进空间复杂度渐进空间复杂度 一个算法可以用自然语言、数字语言或约定的符号来描述，也可以用计算机高级程序语言来描述，如Pascal语言、C语言或伪代码等。本书选用C语言作为描述算法的工具。四、算法的描述四、算法的描述 1预定义常量和类型：简单说明C语言的语法结构：typedef int ElemType;typedef struct LnodeElemType data;struct Lnode *next;Lnode,*LinkList;/函数结果状态代码#define OK 1 #define ER
27、ROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 / Status是函数返回值类型，其值是函数结果状态代码。 typedef int Status; 函数类型函数类型 函数名函数名( (参数表参数表) / /算法说明算法说明 语句组语句组 /* *函数名函数名* */ /2函数的形式简单赋值：变量名=表达式，它表示将表达式的值赋给左边的变量； 变量+，它表示变量加1后赋值给变量； 变量-，它表示变量减1后赋值给变量；3赋值语句成组赋值：1.（, ，,）= （，,）；2.下标1下标2=下标1下标2串联赋值：变量1=变量2=变量3=变量k= 表达式；条
28、件赋值：变量名=条件表达式？表达式1：表达式2；交换赋值：变量1变量2，表示变量1和变量2互换；情况语句: switch （表达式） case 值1；语句组1；break； case 值2；语句组2；break； case 值n；语句组n； break； default：语句组；break； 4条件选择语句if （表达式） 语句；if （表达式）语句1；else 语句2； for语句 for（表达式1；表达式2；表达式3） 循环体语句；5循环语句 while语句while （条件表达式） 循环体语句； do-while语句do 循环体语句 while（条件表达式）输入语句：用函数scanf实现
29、，当数据为字符时，用getchar函数实现。输出语句：用printf函数实现，当要输出字符数据时，用putchar函数实现。6输入、输出语句（1）return表达式或return：用于函数结束。（2）break语句：可用在循环语句或case语句中结束循环过程或跳出情况语句。（3）exit语句：表示出现异常情况时，控制退出语句。8注释形式 可用 /*字符串*/ 单行注释 或 /文字序列。7其他一些语句如： max函数，用于求一个或几个表达式中的最大值； min函数，用于求一个或几个表达式中的最小值； abs函数，用于求表达式的绝对值； 9一些基本的函数1.数据、数据结构等基本概念数据、数据结构等基本概念2.对数据结构的两个方面的理解对数据结构的两个方面的理解逻辑结构的四种形式逻辑结构的四种形式线性和非线性结构的逻辑特征线性和非线性结构的逻辑特征存储结构的两种形式存储结构的两种形式本章学习要点本章学习要点3. 掌握计算语句频度和估算算法时间复杂度的方掌握计算语句频度和估算算法时间复杂度的方法。法。
