数据结构-课件1

第第 三三 章章第一讲第一讲 数据结构概述数据结构概述1.1 1.1 什么是数据结构什么是数据结构 程序程序=数据结构数据结构+算法算法登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件线性表举例说明举例说明:例例2 2 人机对奕问题人机对奕问题树.数据结构定义数据结构定义:是一门研究是一门研究非数值计算非数值计算的程序设计问题中的程序设计问题中计算机的计算机的操作对象操作对象以及它们之间的以及它们之间的关系关系和和操作操作等等的学科等等的学科.1.2 1.2 基本概念和术语基本概念和术语数据（数据（data)data)所有能输入到计算机中去的所有能输入到计算机中去的描述客观事描述客观事物的符号物的符号数据元素（数据元素（data elementdata element）数据的数据的基本单位基本单位，也称节，也称节点（点（nodenode）或记录（）或记录（recordrecord）数据项（数据项（data itemdata item）有独立含义的数据有独立含义的数据最小单位最小单位，也称域也称域(field)field)数据结构（数据结构（data structure)data structure)数据元素和数据元素关数据元素和数据元素关系的集合系的集合书目文件 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：检索、排序、插入、删除、修改等数据的运算：检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面：数据结构的三个方面：1.数据的存储（物理）结构数据的存储（物理）结构:数据的逻辑结构在数据的逻辑结构在计算机计算机存储器中的具体实现。存储器中的具体实现。存储结构分为：存储结构分为：顺序顺序存储结构存储结构借助元素在存储器中的借助元素在存储器中的相对位置相对位置来表示来表示 数据元素间的逻辑关系数据元素间的逻辑关系.链式链式存储结构存储结构借助指示元素存储地址的借助指示元素存储地址的指针指针表示数据表示数据 元素间的逻辑关系元素间的逻辑关系.2.2.数据的逻辑结构数据的逻辑结构只抽象反映数据元素的只抽象反映数据元素的逻辑逻辑关系关系.元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容Loc(元素元素i)=Lo+（i-1)*m顺序存储顺序存储1536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 41345h存储地址存储地址 存储内容存储内容 指针指针 13451345 元素元素1 1 14001400 13461346 元素元素4 4 .14001400 元素元素2 2 15361536 .15361536 元素元素3 3 13461346 链式存储链式存储 h根据数据元素间逻辑关系的基本特性，有三种基本根据数据元素间逻辑关系的基本特性，有三种基本数据结构数据结构.线性结构线性结构一个对一个，如线性表、栈、队列一个对一个，如线性表、栈、队列;树形结构树形结构一个对多个，如树一个对多个，如树;图状结构图状结构多个对多个，如图多个对多个，如图;数据的逻辑结构数据的逻辑结构一、算法的概念一、算法的概念 算法是由一套规则组成的一个过程，算法是对某一特算法是由一套规则组成的一个过程，算法是对某一特定问题的求解步骤的一种描述。算法应当具备以下几个方定问题的求解步骤的一种描述。算法应当具备以下几个方面的特点：面的特点：1.3 1.3 算法及其描述算法及其描述 瑞士计算机科学家瑞士计算机科学家N N沃思教授提出了程序定义的著名沃思教授提出了程序定义的著名公式：公式：程序程序=数据结构数据结构+算法算法1 1、一个算法必须保证执行有限步之后结束；、一个算法必须保证执行有限步之后结束；2 2、算法的每一个步骤必须具有确切的定义；、算法的每一个步骤必须具有确切的定义；3 3、应对算法给出初始量；、应对算法给出初始量；4 4、算法具有一个或多个输出；、算法具有一个或多个输出；5 5、算法的每一步都必须是计算机能进行的有效操作、算法的每一步都必须是计算机能进行的有效操作。二、算法的描述方法二、算法的描述方法 算法是考虑实现某一个问题求解的框架流程，而程序算法是考虑实现某一个问题求解的框架流程，而程序设计则是根据这一求解的框架流程进行语言细化实现这一设计则是根据这一求解的框架流程进行语言细化实现这一问题求解的具体过程。常用描述算法的工具有：问题求解的具体过程。常用描述算法的工具有：1、自然语言：自然语言：使用人们日常进行交流的语言。使用人们日常进行交流的语言。如：从如：从a,ba,b中找出一个大的数给中找出一个大的数给maxmax。从键盘输入两个数给从键盘输入两个数给a a和和b b；如果如果a a比比b b大，则把大，则把a a的值传给的值传给maxmax，否则把否则把b b的值传给的值传给maxmax；输出输出maxmax的值。的值。2、专用工具：专用工具：借借助助于于有有关关图图形形工工具具或或代代码码符符号号来来描描述述。常常用用的的工工具具有有流程图、流程图、N-SN-S图等。图等。如用如用N-SN-S图来描述从图来描述从a a和和b b中找大数的问题。中找大数的问题。输入a和b abmaxa maxb输出max3 3、程序设计语言：程序设计语言：算算法法最最终终要要用用程程序序设设计计语语言言来来描描述述，计计算算机机才才能能保保存存、翻译和执行。如用翻译和执行。如用C C语言来描述从语言来描述从a a和和b b中找大数的问题。中找大数的问题。常用的算法有：迭代法、枚举法、递归法、递推法等。常用的算法有：迭代法、枚举法、递归法、递推法等。scanf(“%d,%d”,&a,&b);if(ab)max=a;else max=b;printf(“%d,%d”,a,b);选择算法描述语言的准则选择算法描述语言的准则:（1 1）该语言应该具有描述数据结构和算法的基本功能；）该语言应该具有描述数据结构和算法的基本功能；（2 2）该语言应该尽可能地简捷，以便于掌握、理解；）该语言应该尽可能地简捷，以便于掌握、理解；（3 3）使用该语言描述的算法应该能够比较容易地转换成任）使用该语言描述的算法应该能够比较容易地转换成任何一种程序设计语言。何一种程序设计语言。“类类C C”描述语言是通过对描述语言是通过对C C语言进行精心筛选保留的一个语言进行精心筛选保留的一个核心子集，并为了便于描述，又做了若干扩展修改，从而核心子集，并为了便于描述，又做了若干扩展修改，从而增强了语言的描述功能。增强了语言的描述功能。1.1.预定义常量及类型预定义常量及类型#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1 数据元素被约定为常量类型，用户需要根据具体情数据元素被约定为常量类型，用户需要根据具体情况，自行定义该数据类型。况，自行定义该数据类型。2.2.算法描述可以使用函数形式：算法描述可以使用函数形式：函数类型函数类型 函数名（函数参数表）函数名（函数参数表）语句序列；语句序列；为了简化函数的书写，提高算法描述的清晰度，我为了简化函数的书写，提高算法描述的清晰度，我们规定除函数参数表中的参数需要说明数据类型外，函们规定除函数参数表中的参数需要说明数据类型外，函数中使用的局部变量可以不做变量说明，必要时给出相数中使用的局部变量可以不做变量说明，必要时给出相应的注释即可。另外，在书写算法时，应该养成对重点应的注释即可。另外，在书写算法时，应该养成对重点语句段落添加注解的良好习惯。语句段落添加注解的良好习惯。3.3.在算法描述中可以使用的赋值语句形式有：在算法描述中可以使用的赋值语句形式有：简单赋值简单赋值 变量名变量名 =表达式；表达式；串联赋值串联赋值 变量名变量名1=.=1=.=变量名变量名n=n=表达式；表达式；成组赋值成组赋值 （变量名（变量名1 1，.，变量名，变量名n n）=（表达（表达 1 1，.，表达式表达式n n）；）；结构赋值结构赋值 结构名结构名1=1=结构名结构名2 2；结构名结构名 =（值（值1 1，值，值2 2，.，值，值n n）；）；条件赋值条件赋值 变量名变量名 =条件表达式条件表达式?表达式表达式1 1：表达式：表达式2 2；交换赋值交换赋值 变量名变量名1 1 变量名变量名2 2；4.4.在在算算法法描描述述中中可可以以使使用用的的选选择择结结构构语语句形式有：句形式有：条件语句条件语句1 if（表达式）（表达式）语句；语句；条件语句条件语句2 if（表达式）（表达式）语句；语句；else 语句语句；开关语句开关语句1 switch（表达式）（表达式）case 值值1：语句序列：语句序列1；break；case 值值2：语句序列：语句序列2；break；.case 值值n：语句序列：语句序列n；break；default：语句序列：语句序列n+1；开关语句开关语句2 switch 2 switch case case 条件条件1 1：语句序列语句序列1 1；breakbreak；case case 条件条件2 2：语句序列语句序列2 2；breakbreak；.case case 条件条件n n：语句序列语句序列n n；breakbreak；defaultdefault：语句序列：语句序列n+1n+1；5.在算法描述中可以使用的循环结构语句形式有：在算法描述中可以使用的循环结构语句形式有：for循环语句循环语句 for（表达式（表达式1；循环条件表达式；表；循环条件表达式；表达式达式2）语句；语句；while循环语句循环语句 while（循环条件表达式）（循环条件表达式）语句；语句；do-while循环语句循环语句 do 语句序列；语句序列；while（循环条件表达式）；（循环条件表达式）；6.在描述算法中可以使用的结束语句形式有：在描述算法中可以使用的结束语句形式有：函数结束语句函数结束语句 return 表达式；表达式；return;case或循环结束语句或循环结束语句 break;异常结束语句异常结束语句 exit；7.在算法描述中可以使用的输入输出语句形式有：在算法描述中可以使用的输入输出语句形式有：输入语句输入语句 scanf(格式串格式串，变量名，变量名1，.，变量名，变量名n)；输出语句输出语句 printf(格式串格式串，表达式，表达式1，.，表达式，表达式n);8.在算法描述中可以使用的扩展函数有：在算法描述中可以使用的扩展函数有：求最大值求最大值 max（表达式（表达式1，.，表达式，表达式n）；）；这个这个函数返回参数表中函数返回参数表中n个表达式计算结果中的最大值。个表达式计算结果中的最大值。求最小值求最小值 min（表达式（表达式1，.，表达式，表达式n）；）；这个这个函数返回参数表中函数返回参数表中n个表达式计算结果中的最小值。个表达式计算结果中的最小值。算法的评价标准算法的评价标准(1)(1)正确性：正确性：要求算法能够正确地执行预先规定的功能，要求算法能够正确地执行预先规定的功能，并达到所期望的性能要求。并达到所期望的性能要求。(2)(2)可读性：可读性：为了便于理解、测试和修改算法，算法应该为了便于理解、测试和修改算法，算法应该具有良好的可读性。具有良好的可读性。(3)(3)健壮性：健壮性：算法中拥有对输入数据、打开文件、读取文算法中拥有对输入数据、打开文件、读取文件记录、分配内存空间等操作的结果检测，并通过与用件记录、分配内存空间等操作的结果检测，并通过与用户对话的形式做出相应的处理选择。户对话的形式做出相应的处理选择。(4)(4)时间与空间效率：时间与空间效率：算法的时间与空间效率是指将算法算法的时间与空间效率是指将算法变换为程序后，该程序在计算机上运行时所花费的时间变换为程序后，该程序在计算机上运行时所花费的时间及所占据空间的度量。及所占据空间的度量。三三.算法的评价算法的评价(补充了解补充了解)时间复杂度：时间复杂度：基本操作重复执行的次数的基本操作重复执行的次数的阶数阶数 T(n)=o(f(n).例例1：NXN矩阵相乘矩阵相乘 for(i=1;i=n;i+)/.n+1 for(j=1;j=n;j+)/n(n+1)cij=0;/n*n for(k=1;k=n;k+)/.n*n(n+1)cij=cij+aik*bkj;/.n*n*n 1.1.算法时间效率：算法时间效率：用依据该算法编制的程序在用依据该算法编制的程序在计算机上执行所消耗的时间来度量计算机上执行所消耗的时间来度量.当当T(n)T(n)为多项式时为多项式时,可只取其最高次幂项可只取其最高次幂项,且它的系数也可略去不写。且它的系数也可略去不写。一般地，对于足够大的一般地，对于足够大的n n，常用的时间复，常用的时间复杂性存在以下顺序：杂性存在以下顺序：O(1)O(logn)O(n)O(n*lognO(1)O(logn)O(n)O(n*logn)O(nO(n2 2)O(n)O(n3 3)O(2O(2n n)O(3)O(3n n)O(n!)O(n!)其中其中,O(1),O(1)为常数数量级为常数数量级,即算法的即算法的时间复杂性与输入规模时间复杂性与输入规模n n无关。无关。算法的运行时间往往还与具体输入的数据有关算法的运行时间往往还与具体输入的数据有关,通常通常用以下两种方法来确定一个算法的运算时间：用以下两种方法来确定一个算法的运算时间：1.1.平均时间复杂性：平均时间复杂性：研究同样的研究同样的n n值时各种可能的输值时各种可能的输入，取它们运算时间的平均值。入，取它们运算时间的平均值。2.2.最坏时间复杂性：最坏时间复杂性：研究各种输入中运算最慢的一研究各种输入中运算最慢的一种情况下的运算时间。种情况下的运算时间。算法算法空间效率的分析：空间效率的分析：一个算法的空间效率是指在算法的执行过程中，一个算法的空间效率是指在算法的执行过程中，所占据的辅助空间数量。所占据的辅助空间数量。辅助空间就是除算法代码本身和输入输出数据辅助空间就是除算法代码本身和输入输出数据所占据的空间外，算法临时开辟的存储空间单所占据的空间外，算法临时开辟的存储空间单元。元。在设计算法时，应该注意空间效率。在设计算法时，应该注意空间效率。空间效率分析举例：Q：某程序中已经定义了三个变量：某程序中已经定义了三个变量x、y、z，现需要把，现需要把y中的原有数据放到中的原有数据放到x中，中，z中的原有数据放到中的原有数据放到y中，中，x中的中的原有数据放到原有数据放到z中。设计一组语句完成该操作。中。设计一组语句完成该操作。xyz#t#正确写法正确写法 t=x;x=y;y=z;z=t;注意：我们在写程序时必须兼顾时间效率和空间效率。小小 结结本章介绍了贯穿全书的基本概念和基本思想本章介绍了贯穿全书的基本概念和基本思想程序数据结构算法程序数据结构算法数据结构数据结构逻辑结构逻辑结构物理结构物理结构数据运算数据运算算法算法算法的复杂性分析算法的复杂性分析 习题与练习习题与练习一、名词解释一、名词解释 数据数据 数据项数据项 数据元素数据元素 数据结构数据结构 数据逻辑结构数据逻辑结构 数据物理结构数据物理结构 算法算法 算法的时间复杂性算法的时间复杂性二、简答二、简答 1.1.算法分析的目的是什么？算法分析的目的是什么？2.2.什么是算法的最坏和平均时间复杂性？什么是算法的最坏和平均时间复杂性？三、分析下列算法的时间复杂性三、分析下列算法的时间复杂性:1sum=0;for(i=1;i=n;i+)sum=sum+i;2i=1;while(i=n)i=i*10;3sum=0;for(i=0;in;i+)for(j=0;jn;j+)sum=sum+Arrayij;返回