数据结构第一章概论.ppt

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