《重庆科创职业学院数据结构课件第一章绪言第二讲》由会员分享，可在线阅读，更多相关《重庆科创职业学院数据结构课件第一章绪言第二讲（30页珍藏版）》请在金锄头文库上搜索。
1、重庆科创职业学院数据类型数据类型在用高级程序语言编写的程序中，必须对程序中出现的每个变在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。量、常量或表达式，明确说明它们所属的数据类型。例如，例如，C语言中提供的基本数据类型有语言中提供的基本数据类型有:整型整型、实型（浮点型）、字符型、实型（浮点型）、字符型、枚举型、枚举型注：注：不同类型的变量，其所能取的值的范围不同，所能进行的操作不同类型的变量，其所能取的值的范围不同，所能进行的操作也不同。也不同。重庆科创职业学院数据类型数据类型定义：定义：一组一组值的集合值的集合和定义在这个集合上的一组和定
2、义在这个集合上的一组操作操作的总称。的总称。例例如如：整整数数类类型型（int），值值的的范范围围是是-32768，32767，主主要要运运算算有有+、-、*、/、%（取模运算）等。（取模运算）等。从从硬硬件件看看，实实现现涉涉及及到到“字字”，“字字节节”，“位位”，“位位的的运运算算”等。等。从从用用户户看看，只只需需了了解解整整数数运运算算的的数数学学特特性性，而而不不必必了了解解内内部部结结构构如何变化如何变化 。重庆科创职业学院抽象数据类型（抽象数据类型（ADT）定义：定义：一个一个数学模型数学模型以及定义在该模型上的一组以及定义在该模型上的一组操作操作。例：线性表的抽象数据类型。例
3、：线性表的抽象数据类型。数学模型是：在数据元素的集合中数学模型是：在数据元素的集合中,除第一个和最后一个元素外，除第一个和最后一个元素外，每个元素有唯一的前趋和后继。可以有的操作如插入、删除等。每个元素有唯一的前趋和后继。可以有的操作如插入、删除等。重庆科创职业学院抽象数据类型分类：抽象数据类型分类：原子类型、原子类型、固定聚合类型、固定聚合类型、可变聚合类型可变聚合类型抽象数据类型表示法：抽象数据类型表示法：1、三元组表示：（、三元组表示：（D，S，P）其中其中D是数据对象，是数据对象，S是是D上的关系集，上的关系集，P是对是对D的基本操作集。的基本操作集。2、书中的定义格式：、书中的定义格
4、式：ADT抽象数据类型名抽象数据类型名数据对象：数据对象：数据关系：数据关系：基本操作：基本操作：ADT抽象数据类型名抽象数据类型名重庆科创职业学院例：线性表的表示例：线性表的表示名称名称线性表线性表数据数据对象对象D=ai|ai(-ElemSet,i=1,2,.,n,n=0任意数据元素的集合任意数据元素的集合数据数据关系关系R1=|ai-1,ai(-D,i=2,.,n除第一个和最后一个外，除第一个和最后一个外，每个元素有唯一的直接前每个元素有唯一的直接前趋和唯一的直接后继趋和唯一的直接后继基本基本操作操作ListInsert(&L,i,e)L为线性表，为线性表，i为位置，为位置，e为为数据元
5、素。数据元素。ListDelete(&L,i,e).重庆科创职业学院类类C语言语法语言语法 预定义预定义常量和类型常量和类型#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefinStatus;/Status是函数的类型，其值是函数结果状是函数的类型，其值是函数结果状态代码。态代码。数据结构数据结构的存储结构的存储结构typedefElemTypefirst;基本操作基本操作的算法的算法函数类型函数类型函数名（函数参数表）函数名（函数参数表）/算法说明算法说明语句序
6、列语句序列/函数名函数名重庆科创职业学院赋值赋值语句语句简单赋值：简单赋值： 变量名变量名=表达式；表达式；串联赋值：串联赋值： 变量名变量名1=变量名变量名2=.=变量名变量名k=表达式；表达式；成组赋值成组赋值:（变量名（变量名1，.,变量名变量名k）=（表达式（表达式1，.,表达式表达式k);结构名结构名=（值（值1，.，值，值k);变量名变量名=表达式；表达式；变量名变量名起始下标起始下标.终止下标终止下标=变量名变量名起始起始下标下标.终止下标终止下标；交换赋值：交换赋值： 变量名变量名变量名；变量名；条件赋值：条件赋值：变量名变量名=条件表达式？表达式？表达式条件表达式？表达式？表
7、达式T：表：表达式达式F重庆科创职业学院选择语句选择语句1、if（表达式）（表达式）语句；语句；2、if（表达式）（表达式）语句；语句；else语句；语句；3、switch(表达式）表达式）case值值1：语句序列：语句序列1；break;.case值值n：语句序列：语句序列n；break;default:语句序列语句序列n+1；break;4、switchcase条件条件1：语句序列：语句序列1；break;.case条件条件n：语句序列：语句序列n；break;default:语句序列语句序列n+1；break;重庆科创职业学院循环语句循环语句for（赋初值表达式；条件；修改表达式序列）语
8、句；（赋初值表达式；条件；修改表达式序列）语句；while（条件）语句；（条件）语句；do语句序列语句序列while（条件）；（条件）；结束语句结束语句return表达式表达式；return;/函数结束语句函数结束语句break;/case结束语句结束语句exit(异常代码异常代码);/异常结束语句异常结束语句输入输出输入输出scanf（格式串格式串，变量，变量1，.,变量变量n）；）；注释注释/文字序列文字序列基本函数基本函数max（表达式（表达式1，.，表达式，表达式n）min,abs,floor,ceil,eof,eoln逻辑运算逻辑运算 &与运算；与运算；|或运算或运算重庆科创职业学院
9、1.3算法和算法分析算法和算法分析1.算法算法定义：对特定问题求解步骤的一种描述。定义：对特定问题求解步骤的一种描述。（通俗点说，就是计算机解题的过程。（通俗点说，就是计算机解题的过程。 ）2、算法的五大特性、算法的五大特性(1)有穷性有穷性：a、操作步骤有穷，、操作步骤有穷，b、每步执行时间有穷、每步执行时间有穷(2)确定性确定性：无二义性，对于相同的输入执行相同的路径无二义性，对于相同的输入执行相同的路径(3)输入：输入：0至多个输入至多个输入(4)输出：输出：1至多个输出至多个输出(5)有效性有效性(可行性可行性)：（用于描述算法的操作都是足够基本的）所有操作都可通（用于描述算法的操作都
10、是足够基本的）所有操作都可通过已经实现的基本运算执行有限次来实现的。过已经实现的基本运算执行有限次来实现的。 重庆科创职业学院问：程序一定是算法，对不对？问：程序一定是算法，对不对？如操作系统，只要系统不遭破坏，它就永远不会停止，即使没如操作系统，只要系统不遭破坏，它就永远不会停止，即使没有作业要处理，仍处于一个等待循环中，等待新作业的进入。有作业要处理，仍处于一个等待循环中，等待新作业的进入。因此操作系统程序不是一个算法。因此操作系统程序不是一个算法。重庆科创职业学院算法与数据结构关系举例算法与数据结构关系举例例例1：编写程序查询某城市某人的电话号码：编写程序查询某城市某人的电话号码建立一张
11、登记表，存放建立一张登记表，存放2个数据项：个数据项：姓名姓名+Tel好的算法取决于这张表的结构及存储方式：好的算法取决于这张表的结构及存储方式：v将表中结点按照姓名顺序存储在计算机中，依次查找，可能遍历将表中结点按照姓名顺序存储在计算机中，依次查找，可能遍历整个表都找不到。整个表都找不到。v建立一张姓氏索引表：姓建立一张姓氏索引表：姓+表中的起始地址表中的起始地址,则不需查找其他姓氏，则不需查找其他姓氏，查找效率得到提高。查找效率得到提高。重庆科创职业学院 例例2:设计一个考试日程安排设计一个考试日程安排表，使在尽可能短的时间内表，使在尽可能短的时间内安排完考试，要求同一个学安排完考试，要求
12、同一个学生选修的几门课程不能安排生选修的几门课程不能安排在同一个时间内。在同一个时间内。姓名选修1 选修2 选修3ABECDCEFDFABF解决问题的关键步骤是解决问题的关键步骤是先选取合适的数据结构表示问先选取合适的数据结构表示问题题，才能写出有效的算法。，才能写出有效的算法。重庆科创职业学院3.算法设计的要求算法设计的要求（1）正确性（对算法是否）正确性（对算法是否“正确正确”的理解可以有以下四个层次的理解可以有以下四个层次：a程序中不含语法错误；程序中不含语法错误；b程序对于几组输入数据能够得出满足要求的结果；程序对于几组输入数据能够得出满足要求的结果；c程序对于精心选择的、典型、苛刻且
13、带有刁难性的几组输入数据能程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；够得出满足要求的结果；d程序对于一切合法的输入数据都能得出满足要求的结果；程序对于一切合法的输入数据都能得出满足要求的结果；（2）可读性（易于）可读性（易于人的理解）理解）（3）健壮性（出错提示）健壮性（出错提示）（4）高效率与低存储量需求）高效率与低存储量需求重庆科创职业学院4.算法的分析算法的分析算法性能的评价算法性能的评价1)、度量算法执行时间的两种方法、度量算法执行时间的两种方法 a a、事后统计法、事后统计法b b、事前分析估算法、事前分析估算法2)、评价标准：评价标准：a、算法
14、所需的计算时间、算法所需的计算时间b、算法所需的存储空间、算法所需的存储空间(不利于较大范围内的算法比较。不利于较大范围内的算法比较。)（此方法取决于（此方法取决于:算法本身选用的策略、问题的规模算法本身选用的策略、问题的规模、书写程、书写程序的语言序的语言、编译产生的机器代码质量、编译产生的机器代码质量）重庆科创职业学院5.时间复杂度时间复杂度(1)语句频度语句频度所谓某语句的频度，是指在一个算法中所谓某语句的频度，是指在一个算法中该条该条语句重复执行的次数。语句重复执行的次数。(2)算法的执行时间算法的执行时间所有语句的执行次数之和所有语句的执行次数之和重庆科创职业学院（1）引例）引例:请
15、指出下列语句中请指出下列语句中+x的频度的频度（a）+x;s=0；+x执行的次数执行的次数1（b）for(i=1;i=n;+i)+x;s+=x;+x执行的次数执行的次数n（c）for(j=1;j=n;+j)for(k=1;k=n;+k)+x;s+=x;+x执行的次数执行的次数n2重庆科创职业学院算法的执行时间算法的执行时间 基本操作执行的次数基本操作执行的次数基本操作执行的时间基本操作执行的时间即即: :算法的算法的执行时间执行时间与与基本操作基本操作执行次数之和成正比执行次数之和成正比重庆科创职业学院(3)算法的渐近时间复杂度算法的渐近时间复杂度算法的时间度量依据算法中算法的时间度量依据算法
16、中最大语句频度最大语句频度来估算，来估算，它是问题规模它是问题规模n的某个函数的某个函数f(n)。算法的时间量度记作：。算法的时间量度记作：T(n)=O(f(n)它表示随着问题规模它表示随着问题规模n的增大，算法执行时间的增长率和的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称的增长率相同，称作算法的渐近时间复杂度，简称时时间复杂度。间复杂度。重庆科创职业学院注意：注意：基本操作的执行次数不确定时，以平均时基本操作的执行次数不确定时，以平均时间复杂度或最坏情况下时间复杂度计算。间复杂度或最坏情况下时间复杂度计算。重庆科创职业学院例：写出以下各语句执行次数例：写
17、出以下各语句执行次数(1)for(i=1;i=n;+i)(2)(2)for(j=1;j=n;+j) (3)(3)ci,j=0;(4)for(k=1;k=n;+k)(5)(5)ci,j+=ai,k*bk,j; n(n+1)n+1n2n2(n+1)n3总时间消耗：总时间消耗：T(n)=2n3+3n2+2n+1时间复杂度：时间复杂度：O(n3)重庆科创职业学院(1)x91；y100；while（y0）if（x100）xx-10；y-；elsex时间复杂度：时间复杂度：O(1)重庆科创职业学院注注:若算法中语句执行次数为一个常数，则时间复若算法中语句执行次数为一个常数，则时间复杂度为杂度为O(1)。时
18、间频度不同，但时间复杂度有可能相同。时间频度不同，但时间复杂度有可能相同。如：如：T(n)=n2+3n+4与与T(n)=4n2+2n+1它们的频度不它们的频度不同，但时间复杂度相同，都为同，但时间复杂度相同，都为O(n2)。重庆科创职业学院按数量级递增排列，常见的时间复杂度有：按数量级递增排列，常见的时间复杂度有：常数阶常数阶O(1),对数阶对数阶O(log2n),线性阶线性阶O(n),线性对数阶线性对数阶O(nlog2n),平方阶平方阶O(n2)，立方阶，立方阶O(n3),.，k次方阶次方阶O(nk),指数阶指数阶O(2n)。随着问题规模。随着问题规模n的不断增的不断增大，上述时间复杂度不断
19、增大，算法的执行效率越低。大，上述时间复杂度不断增大，算法的执行效率越低。重庆科创职业学院上述的时间复杂度的优劣次序如下上述的时间复杂度的优劣次序如下(n16)：O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n)膨胀率的关系如图所示。膨胀率的关系如图所示。 重庆科创职业学院例例1、将将整数序列重新排列成自小至大有序的整数序列。整数序列重新排列成自小至大有序的整数序列。for(i=0;in-1;+i)j=i;for(k=i+1;kn;+k)if(ak1&change;-i)change=FALSE;for(j=0;jaj+1)w=aj;aj=aj+1;aj+1=w;
20、change=TRUE基本操作基本操作:赋值操作、赋值操作、时间复杂度时间复杂度:O(n2)重庆科创职业学院算法的空间复杂度定义为算法的空间复杂度定义为: :表示随着问题规模表示随着问题规模n的增大，算法运行所需存储量的增长率的增大，算法运行所需存储量的增长率与与g(n)的增长率相同。的增长率相同。S(n)=O(g(n)6.空间复杂度空间复杂度重庆科创职业学院算法的存储量包括算法的存储量包括:1输入数据所占空间输入数据所占空间2程序本身所占空间程序本身所占空间3辅助变量所占空间辅助变量所占空间注意：注意：若输入数据所占空间只取决于问题本身，和算法无关，则只若输入数据所占空间只取决于问题本身，和
21、算法无关，则只需要分析需要分析除输入和程序之外的辅助变量所占额外空间除输入和程序之外的辅助变量所占额外空间。若所需额外空间相对于输入数据量来说是常数，则称此算法若所需额外空间相对于输入数据量来说是常数，则称此算法为为原地工作原地工作。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。重庆科创职业学院作业作业1简简述述下下列列术术语语：数数据据、结结点点、逻逻辑辑结结构构、存存储储结结构构、数数据据处处理理、数数据据结结构和数据类型。构和数据类型。2试试根根据据以以下下信信息息：校校友友姓姓名名、性性别别、出出生生年年月月、毕毕业业时时间间、所所学学专专业业、现现在在工工作作单单位位、职职称称、职职务务、电电话话等等，为为校校友友录录构构造造一一种种适适当当的的数数据据结结构（作图示意），并定义必要的运算和用文字叙述相应的算法思想。构（作图示意），并定义必要的运算和用文字叙述相应的算法思想。3什么是算法？算法的主要特点是什么？什么是算法？算法的主要特点是什么？4如何评价一个算法？如何评价一个算法？
