《数据结构第一章概论.ppt》由会员分享，可在线阅读，更多相关《数据结构第一章概论.ppt（51页珍藏版）》请在三一办公上搜索。
1、数据结构 第一章 概论,重庆一中 葛静,本章的主要内容,问题一：数据结构讨论的范畴问题二：基本概念问题三：算法及其度量,问题一：数据结构讨论的范畴,尼克劳斯沃斯(Niklaus Wirth)：生于瑞士，求学美洲，立业瑞士。苏黎世联邦理工学院教授，Pascal系列语言之父，世界闻名的计算机科学家。Algorithm+Data Structures=Programs 算法+数据结构=程序程序：为计算机处理问题编制的一组指令集。算法：处理问题的策略。数据结构：问题的数学模型。,数值计算的程序设计问题,全球天气预报 环流模式方程（数学模型）进行大量的数值运算，这是计算数学要讨论的问题。,非数值计算的程
2、序问题,例1：求n个数中的最大值算法？：两两比较数据结构？：n 的范围？如果n达到1012，如何表示这个整数？,非数值计算的程序问题,例2：人机对弈算法？：对弈的规则和策略数据结构？：棋盘、棋子怎么表示？,非数值计算的程序问题,例3：足协数据库管理算法？：需要管理哪些项目？用户的界面？条例、规则等等。数据结构？：各种各样的表格和数据库。,综合各种程序设计的问题，抽出其具体的物理含义，就可得到几类数学模型：,1、和数值计算相关的数学模型，如线性代数方程、非线性代数方程和常微分方程等，他们的数值解问题就是计算数学要解决的问题。2、非数值计算问题，其数学模型的表示和求解就是数据结构要研究的内容。,概
3、括的说：,数据结构要研究的就是：非数值型计算的程序设计问题中描述现实世界实体的数学模型 和 在计算机中表示的方法 以及 这些数学模型进行的操作如何在计算机中实现。,问题二：基本概念,数据：是计算机要处理的信息集合，是信息的某种特定的符号表示形式。其含义随着计算机的发展不断扩大。数据元素：是数据中的一个“个体”，是数据结构中讨论的基本单位。但不是最小单位。如：学生（数据元素）姓名、性别、出生日期（年月日）、入学日期、班级数据项才是数据结构中要讨论的最小单位。,数据结构：带结构的数据元素的集合。,结构：就是数据元素之间存在的约束关系。例1：一个含有12位数的十进制整数可以用三个4位的十进制整数表示
4、。1548，4913，7875a1(1548),a2(4913),a3(7875)在a1,a2,a3之间存在次序关系,4973,7875,1548 1548,4913,7875 a2 a3 a1 a1 a2 a3,数据结构：带结构的数据元素的集合。,例2：2行3列的二维数组a1,a2,a3,a4,a5,a6行的次序关系：row=,列的次序关系：col=,a1 a3 a4 a1 a2 a3 a2 a6 a5 a4 a5 a6,数据结构：带结构的数据元素的集合。,例3：一位数组a1,a2,a3,a4,a5,a6，这6个数据元素还可以存在单纯的次序关系i=1,2,3,4,5所以：相同的数据元素，不同
5、的约束关系，构成了不同的数据结构。,例3 人机对奕问题,多叉路口交通灯管理问题,数据的逻辑结构,数据在逻辑上的联系，叫做数据的逻辑结构。,数据的逻辑结构只抽象反映数据元素的逻辑关系数据的存储（物理）结构数据的逻辑结构在计算机存储器中的实现,数据逻辑结构的定义,定义为一个二元组：Data_structures=(D,S)其中：D是数据元素的有限集，S是D上关系的有限集。如：线性结构：数据对象：A=ai1=0,aielemtype 其中n为线性表的表长，n=0时线性表为空表。数据关系：R=rR=1=i=n-1,数据的物理结构（存储结构）,数据的在计算机上的存储表示称作数据的物理结构或存储结构。数据
6、元素的映像方法：用二进制位（bit）的位串表示数据元素。（321）10=（101000001）2 A=(001000001)2,数据的物理结构（存储结构）,关系集合的映像方法：所有关系都可用一个有序对的集合来表示。,有序对看成是关系的一个基本单位，讨论关系的映像，只要讨论这个有序对的映像方法即可。,映像方法：,顺序映像：以存储位置的相邻表示后继关系。链式印象：存储位置无固定关系，用附加信息（指针）来表示后继关系。,数据类型,数据类型是一个值的集合和定义在这个集合上的一组操作的总称。如pascal中的integer类型，数据范围-32768,32767操作：+-*div mod数据类型分为：简单
7、型和结构类型（构造类型）,结构类型,比如：数组，数组的值可以分割，它是某个结构的值，因此这个值集是一个数据结构。所以数据类型也可以看成是一个数据结构和定义在这个数据结构上的一组操作的总称。从这个概念出发抽象数据类型（ADT Abstract Data Type）是指一个数学模型以及定义在这个数学模型上的一组操作。,例如：抽象数据类型复数的定义,ADT complex数据对象：D=e1,e2e1,e2real数据关系：R=e1是复数的实部，e2是复数的虚部基本操作：Initcomplex(z,v1,v2)操作结果：构造复数z，其实部和虚部分别赋以参数v1,v2的值。,Destroycomplex
8、(z)操作结果：复数z被销毁Getreal(z,x)初始条件：复数已存在操作结果：用x返回复数z的实部值Getimag(z,y)初始条件：复数已存在操作结果：用y返回z的虚部值Add(z1,z2,sum)初始条件：z1,z2是复数操作结果：用sum返回两个复数的和值。,抽象数据类型的描述方法,(D,S,P)三元组表示：D是数据对象S是D上的关系集P是对D的基本操作,抽象数据类型的表示和实现：,通过固有数据类型，即高级编程语言中已经实现的数据类型，来实现。,问题三：算法及算法的衡量,算法：是为了解决某类问题而规定的一个有限长的操作序列。算法的五个重要特性：1、有穷性 2、确定性 3、可行性4、有
9、输入 5、有输出,算法的特性,1、有穷性：对任意一组合法输入值，在执行有穷步骤之后，一定能结束，即能在有限时间内完成。其含义有二：其一：描述算法的指令条数有限。其二：每一步的执行时间是有限的，非数学意义上的有限，而应理解为合理。,算法的特性,确定性：每种情况下执行的操作，在算法中都有确切的规定，使算法的执行者或者阅读者能够明确其含义及如何执行，并且在任何条件下，算法都只有与之对应的一条路径。可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次来实现之。如：将a,b的最大公约数赋值给c（）增加x的值（）交换a,b 两个变量的值（）,算法的特性,有输入：输入的形式多样，有
10、的输入嵌在算法中，有的可通过终端输入。必须保证算法有可以加工的对象。如：求100以内的素数For i:=2 to 100 do 有输出：信息加工的结果。,算法设计（评价）的原则,1、正确性：程序不含语法错误 程序对于几组输入数据能够得到满足要求的结果。对于精心选择的、典型的、苛刻且带有刁难性的几组输入数据都能得出满足要求的结果。程序对于一切合法的输入数据都能得出满足要求的结果。（相当难）,算法设计（评价）的原则,2、可读性 算法主要是为了人的阅读与交流，其次才是为了计算机执行，因此算法应该易于人的理解；另一方面，晦涩难懂的程序易于隐藏较多的错误而难以调试。例如：多人合作设计大型软件系统设计 程
11、序设计 编程,算法设计（评价）的原则,3、健壮性（对应着正确性）当输入数据非法时，算法应当恰当地作出反映或进行相应的处理，而不是产生莫名其妙的输出结果，并且，不应该中断程序的执行，而应是返回一个表示错误或错误性质的值。4、高效率与低存储量的需求。效率：算法执行的时间存储量：算法执行过程中最大的存储空间。二者均与问题的规模有关。,算法效率的衡量方法和准则,1、事后统计法：算法程序运行时间缺点：（1）必须执行程序（2）其他因素掩盖算法本质2、事前分析估算法,和算法执行时间相关的因素：,算法选用的策略。问题的规模。编写程序的语言。编译程序产生的机器代码的质量。计算机执行指令的速度。第3、4、5条均与
12、硬件及软件有关，一般不考虑。一个特定算法的“运行工作量”的大小，只依赖于问题的规模n，或者说，它是问题规模n的函数。,我们要关系的是：随着n的增长，算法执行时间的增长与n的关系。T(n)=O(f(n)T(n)就是算法的渐近时间复杂度，T(n)增大的趋势与f(n)相同。,如何估算？,算法=控制结构*原操作（固有数据类型的操作）算法的执行时间=（原操作执行的次数原操作执行的时间）从算法中选取起决定作用的基本操作叫原操作，以该基本操作在算法中重复执行的次数为算法运行时间的衡量准则。,例1：for i:=1 to n do for j:=1 to n do begin ci,j:=0;for k:=1
13、 to n do ci,j:=ci,j+ai,k*bk,j;end;控制结构：3重循环基本操作：乘法时间复杂度：O(n3),例2：for i:=1 to n-1 do begin j:=i;for k:=i+1 to n do if aki then swap(aj,ai);end;基本操作：比较。比较次数：(n-1)+(n-2)+1=n(n-1)/2=(n2-n)/2与n2成正比。故时间复杂度O(n2)。,例3：t:=true;i:=n-1;while(i=1)and(t)do begin t:=false;for j:=1 to i do if ajaj+1 then begin swap
14、(aj,aj+1);t:=true;end;dec(i);end;该算法与输入有关，最好情况O(n-1)，最坏O(n2),算法的存储空间需求,算法的空间复杂度 S(n)=O(g(n)表示随着n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。算法的存储量包括：程序本身所占空间。（细微差别，可不考虑）输入数据所占得空间。辅助变量所占空间。一般情况下，所需存储量依赖于特定的输入，通常按最坏情况考虑。,如何学习数据结构,了解常见的抽象数据类型对每种ADT，了解常见的逻辑结构设计逻辑结构是最难的！对给定的逻辑结构，自己设计物理结构物理结构一般只是数组和链结构数组可以随机访问（设计下标计算公式）
15、经典例子：哈希表，二叉堆，并查集，线段树链结构应该根据元素间关系（链接）进行“移动”经典例子：伸展树，二项堆，跳跃表*特殊算法需要自己归纳出ADT并设计逻辑结构PQ树，后缀树,1.算法的计算量的大小称为计算的(B)A效率 B.复杂性 C.现实性 D.难度2.算法的时间复杂度取决于（C）A.问题的规模 B.待处理数据的初态 C.A和B3.计算机算法指的是（C），它必须具备（B）这三个特性。(1)A.计算方法 B.排序方法 C.解决问题的步骤序列 D.调度方法(2)A可执行性、可移植性、可扩充性 B.可执行性、确定性、有穷性 C.确定性、有穷性、稳定性 D.易读性、稳定性、安全性,4一个算法应该是
16、（B）。A程序 B问题求解步骤的描述 C要满足五个基本特性 DA和C.5.下面关于算法说法正确的是（D）A算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性 D.以上几个都是错误的,6.下面说法错误的是（C）(1)算法原地工作的含义是指不需要任何额外的辅助空间(2)在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法(3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界(4)同一个算法，实现语言的级别越高，执行效率就越低 A(1)B.(1),(2)C.(1),(4)D.(3),7从逻辑上可以把数
17、据结构分为(C)两大类。A动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构8在下面的程序段中，对x的赋值语句的频度为(C)FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1;A O(2n)BO(n)CO(n2)DO(log2n),1.数据元素是数据的最小单位。(F)2.记录是数据处理的最小单位。(F)3.数据的逻辑结构是指数据的各数据项之间的逻辑关系；(F)4算法的优劣与算法描述语言无关，但与所用计算机有关。(F)5健壮的算法不会因非法的输入数据而出现莫名其妙的状态。(T)6算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。(F),7程序一定是算法。(F)8.在顺序存储结构中，有时也存储数据结构中元素之间的关系。(F)9.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(F)11.数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构.(F),本章学习要点,1、基本概念，术语名词等。2、算法的5个基本特征及4个评价原则。3、掌握语句频度（即执行次数）、算法时间复杂度的分析。作业：请完成书上的课后练习,
