数据结构介绍

《数据结构介绍》由会员分享，可在线阅读，更多相关《数据结构介绍（31页珍藏版）》请在金锄头文库上搜索。

1、数据结构,第 三 章,第一讲 数据结构概述,1.1 什么是数据结构程序=数据结构+算法,书目文件,举例说明:,例2 人机对奕问题,数据结构定义:,是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科.,1.2 基本概念和术语 数据（data)所有能输入到计算机中去的描述客观事物的符号 数据元素（data element）数据的基本单位，也称节点（node）或记录（record） 数据项（data item）有独立含义的数据最小单位，也称域(field) 数据结构（data structure)数据元素和数据元素关系的集合,书目文件,1.数据的存储（物理）结构:

2、 数据的逻辑结构在计算机存储器中的具体实现。,2.数据的逻辑结构只抽象反映数据元素的逻辑关系.,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储,h,数据的逻辑结构,一、算法的概念算法是由一套规则组成的一个过程，算法是对某一特定问题的求解步骤的一种描述。算法应当具备以下几个方面的特点：,1.3 算法及其描述,瑞士计算机科学家N沃思教授提出了程序定义的著名公式： 程序=数据结构+算法,1、一个算法必须保证执行有限步之后结束； 2、算法的每一个步骤必须具有确切的定义； 3、应对算法给出初始量； 4、算法具有一个或多个输出； 5、算法的每一步都必须是计算机能进行的

3、有效操作。,二、算法的描述方法算法是考虑实现某一个问题求解的框架流程，而程序设计则是根据这一求解的框架流程进行语言细化实现这一问题求解的具体过程。常用描述算法的工具有：,1、自然语言：使用人们日常进行交流的语言。 如：从a,b中找出一个大的数给max。 从键盘输入两个数给a和b； 如果a比b大，则把a的值传给max，否则把b的值传给max； 输出max的值。,2、专用工具：借助于有关图形工具或代码符号来描述。常用的工具有流程图、N-S图等。,如用N-S图来描述从a和b中找大数的问题。,3、程序设计语言：算法最终要用程序设计语言来描述，计算机才能保存、翻译和执行。如用C语言来描述从a和b中找大数

4、的问题。常用的算法有：迭代法、枚举法、递归法、递推法等。,选择算法描述语言的准则:（1）该语言应该具有描述数据结构和算法的基本功能；（2）该语言应该尽可能地简捷，以便于掌握、理解；（3）使用该语言描述的算法应该能够比较容易地转换成任何一种程序设计语言。,“类C”描述语言是通过对C语言进行精心筛选保留的一个核心子集，并为了便于描述，又做了若干扩展修改，从而增强了语言的描述功能。,1. 预定义常量及类型#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1数据元素被约定为常量类型，用户需要根据具体情况，

5、自行定义该数据类型。,2.算法描述可以使用函数形式：函数类型 函数名（函数参数表）语句序列；为了简化函数的书写，提高算法描述的清晰度，我们规定除函数参数表中的参数需要说明数据类型外，函数中使用的局部变量可以不做变量说明，必要时给出相应的注释即可。另外，在书写算法时，应该养成对重点语句段落添加注解的良好习惯。,3. 在算法描述中可以使用的赋值语句形式有：简单赋值 变量名 = 表达式；串联赋值 变量名1 = . = 变量名n = 表达式；成组赋值 （变量名1，.，变量名n）=（表达 1，.，表达式n）；结构赋值 结构名1 = 结构名2；结构名 =（值1，值2，.，值n）；条件赋值 变量名 = 条件

6、表达式 ? 表达式1：表达式2；交换赋值 变量名1 变量名2；,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 case 条件1：语句序列1；break；case 条件2：语句序列2；break；.case 条件n：语句序列n；break；default：语句序列n+1；,5. 在算法

7、描述中可以使用的循环结构语句形式有：for循环语句 for （表达式1；循环条件表达式；表达式2） 语句；while循环语句 while （循环条件表达式） 语句；do-while循环语句 do 语句序列； while （循环条件表达式）；6. 在描述算法中可以使用的结束语句形式有：函数结束语句 return 表达式；return;case或循环结束语句 break;异常结束语句 exit；,7. 在算法描述中可以使用的输入输出语句形式有：输入语句 scanf( 格式串，变量名1，.，变量名n)；输出语句 printf( 格式串，表达式1，.，表达式n);8. 在算法描述中可以使用的扩展函数有

8、：求最大值 max（表达式1，.，表达式n）；这个函数返回参数表中n个表达式计算结果中的最大值。求最小值 min（表达式1，.，表达式n）；这个函数返回参数表中n个表达式计算结果中的最小值。,算法的评价标准 (1) 正确性：要求算法能够正确地执行预先规定的功能，并达到所期望的性能要求。 (2) 可读性：为了便于理解、测试和修改算法，算法应该具有良好的可读性。 (3) 健壮性：算法中拥有对输入数据、打开文件、读取文件记录、分配内存空间等操作的结果检测，并通过与用户对话的形式做出相应的处理选择。 (4) 时间与空间效率：算法的时间与空间效率是指将算法变换为程序后，该程序在计算机上运行时所花费的时间

9、及所占据空间的度量。,三. 算法的评价(补充了解),时间复杂度：基本操作重复执行的次数的阶数 T(n)=o(f(n).,例1：NXN矩阵相乘 for(i=1;i=n;i+) / n+1for(j=1;j=n;j+) /n(n+1) cij=0; /n*nfor(k=1;k=n;k+) / n*n(n+1)cij=cij+aik*bkj; /.n*n*n,1.算法时间效率：用依据该算法编制的程序在计算机上执行所消耗的时间来度量.,当T(n)为多项式时,可只取其最高次幂项,且它的系数也可略去不写。一般地，对于足够大的n，常用的时间复杂性存在以下顺序： O(1) O(logn) O(n) O(n*l

10、ogn) O(n2) O(n3)O(2n)O(3n)O(n!) 其中,O(1)为常数数量级,即算法的时间复杂性与输入规模n无关。,算法的运行时间往往还与具体输入的数据有关,通常用以下两种方法来确定一个算法的运算时间：,1. 平均时间复杂性：研究同样的n值时各种可能的输入，取它们运算时间的平均值。2. 最坏时间复杂性：研究各种输入中运算最慢的一种情况下的运算时间。,算法空间效率的分析：一个算法的空间效率是指在算法的执行过程中，所占据的辅助空间数量。辅助空间就是除算法代码本身和输入输出数据所占据的空间外，算法临时开辟的存储空间单元。在设计算法时，应该注意空间效率。,空间效率分析举例：,Q：某程序中

11、已经定义了三个变量x、y、z，现需要把y中的原有数据放到x中，z中的原有数据放到y中，x中的原有数据放到z中。设计一组语句完成该操作。,正确写法t = x ;x = y ;y = z ;z = t ;,注意：我们在写程序时必须兼顾时间效率和空间效率。,小 结,本章介绍了贯穿全书的基本概念和基本思想 程序数据结构算法 数据结构 逻辑结构 物理结构 数据运算 算法 算法的复杂性分析,习题与练习,一、名词解释 数据 数据项 数据元素 数据结构 数据逻辑结构 数据物理结构 算法 算法的时间复杂性二、简答 1. 算法分析的目的是什么？ 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;,返回,