数据结构介绍

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