抽象数据类型如何定义

数据结构DataStructure延安大学计算机学院DepartmentofComputerScience,Yan’anUniversity2011内容安排章内容学时章内容学时1序论27图62线性表48动态存储管理略3栈和队列49查找44串210内部排序65数组和广义表411外部排序略6树和二叉树612文件略计算机系列课程之间的联系数据结构课程的地位是介于数学、计算机硬件和计算机软件三者之间的一门核心课程关系对象关系操作数学软件硬件对象关系操作第1章序论1.1计算机基本概念（复习）1.2数据结构基本概念1.3抽象数据类型概念1.4算法效率的度量1.1计算机基本概念（复习）计算机系统＝硬件系统＋软件系统Q1硬件系统由哪几部分组成？Q2微型计算机与其他计算机的区别？Q3内存与外存的不同之处是？Q4计算机内常用到哪些数制？Q5计算机主要技术指标有哪些?硬件概念复习软件概念复习Q1软件系统包含哪些软件？Q2什么是系统软件和应用软件？Q3机器语言、汇编语言、高级语言的区别？Q1：计算机硬件系统由哪几部分组成？答：计算机硬件系统由5部分组成：也可浓缩为3部分：人脑：感受→判断→计算→记忆→反应电脑：输入→控制→运算→存储→输出存储器CPUI/O接口及设备控制器输入运算器存储器输出主机Q2：微型计算机与一般意义上的计算机有什么区别？答：其本质特征是运算器和控制器集成在一块IC芯片上这种CPU简称MPUQ3：内存与外存是一回事吗？能被CPU直接控制（BUS直连）的存储器称为内存；通过I/O接口才能被CPU控制的存储器称为外存。答：不是一回事。它们的区别是：输入运算器存储器控制器输出BUS外存储器CPUQ4：计算机内常用到哪些数制？A.（11011001）BB.（75）DC.（37）OD.（2A）H答案：C2进制(B)8进制(O)10进制(D)16进制(H)例3：下列四种不同进制的无符号数中，最小的数是∶例2：下列数据中，有可能是八进制数的是∶A.238B.764C.396D.789例1：10(B)＝D10(O)＝D10(H)＝D2816Q5：计算机主要技术指标有哪些？——CPU一次能处理的二进制位数，它与数据总线的根数有关，如8位机，16位机、32位机等等——运算器做一次“加”动作的最小可靠时间，如奔4机器主频达1.6G（Hz）——CPU每秒能执行加法指令的次数（MIPS）——bit，Byte，KB，MB，GB，TB练：微机中1K字节表示的二进制位数是：1B=8bit1KB=210B1MB=210KB1GB=210MBA.1000B.8×1000C.1024D.8×1024答案：D字长主频运算速度主存容量Q1：软件系统包含哪些软件？裸机答：包含系统软件和应用软件两大类Q2：什么是系统软件？什么是应用软件？答：系统软件——管理计算机系统各部分，使之高效工作，同时为上层提供服务。应用软件——处于系统软件的上层，帮助计算机用户完成特定领域的工作。系统软件中最重要的是操作系统（OperatingSystem），它是一个大型的、优秀的程序，管理着计算机的全部软、硬件资源，并提供人机交互的界面。Q3：机器语言、汇编语言、高级语言的区别？——用二进制代码直接表示的语言，是计算机唯一能识别、执行的语言——符号化了的机器语言（即用助记符来写程序，靠汇编程序翻译成机器码才能执行）——接近自然英语和数学公式的语言（要通过编译或解释程序翻译成机器码）答：低级语言面向机器，执行速度快，效率高；高级语言面向问题，易理解，易移植。机器语言汇编语言高级语言1.2数据结构基本概念Q1：什么是数据结构？Q2：学习数据结构有什么用？Q3：数据结构涵盖的主要内容？讨论：Q1：什么是数据结构？答:是相互之间存在一种或多种特定关系的数据元素的集合，表示为：（数值或非数值）Data_Structure=（D,S）或：是指同一数据元素类中各元素之间存在的关系。亦可表示为：S＝（D,R），或B=（K,R）元素有限集关系有限集术语：数据、数据元素和数据项数据(data)——所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息）。数据元素(dataelement)——是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。数据项(Dataitem)——构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性等）。三者之间的关系：数据数据元素数据项例：班级通讯录个人记录姓名、年龄……Q2：学习数据结构有什么用？答：计算机内的数值运算依靠方程式，而非数值运算（如表、树、图等）则要依靠数据结构。这是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。程序设计实质＝好算法＋好结构同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。Q3：数据结构涵盖的内容？解释1：什么叫数据的逻辑结构？答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。逻辑结构可细分为4类：集合结构：仅同属一个集合线性结构:一对一（1:1)树结构:一对多（1:n)图结构:多对多(m:n)非线性线性例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。（1）S=(D,R)D={a,b,c,d,e,f}R={(a,e),(b,c),(c,a),(e,f),(f,d)}解：上述表达式可用图形表示为：bcaefd此结构为线性的（2）S=(D,R)D={di|1≤i≤5}R={(di,dj),ij}d1d5d2d4d3该结构是非线性的。解：上述表达式可用图形表示为：解释2：什么叫数据的物理结构？答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：例：复数3.0－2.3i的两种存储方式：顺序、链式、索引、散列－2.303023.00300041503023.003000415－2.3法1：地址内容法2：地址内容2字节解释3：什么是数据的运算？答：在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。最常用的数据运算有5种：插入、删除、修改、查找、排序1.3抽象数据类型概念Q1数据类型与抽象数据类型的区别？Q2抽象数据类型如何定义？Q3抽象数据类型如何表示和实现？讨论：提示：教材中例1-6和例1-7分别给出了抽象数据类型“三元组”的定义、表示和实现，请试阅读。Q1:数据类型与抽象数据类型的区别？数据类型：是一个值的集合和定义在该值上的一组操作的总称。抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）。它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。Q2：抽象数据类型如何定义？抽象数据类型可以用以下的三元组来表示：ADT=（D，S，P）数据对象D上的关系集D上的操作集ADT抽象数据类型名{数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义}ADT抽象数据类型名ADT常用定义格式例：给出自然数(NaturalNumber)的抽象数据类型定义。ADTNatural_Numberisobjects:一个整数的有序子集合，它开始于0，结束于机器能表示的最大整数(MAXINT)functions:对于所有的x,yNatural_Number；TRUE,FALSEBoolean；+,-,,==,=等都是可用的服务。Zero()：NaturalNumber返回0IsZero(x)：Booleanif(x==0)返回TRUEelse返回FALSEAdd(x,y)：NaturalNumberif(x+y=MAXINT)返回x+yelse返回MAXINTSubtract(x,y):NaturalNumberif(xy)返回0else返回x-yEqual(x,y):Booleanif(x==y)返回TRUEelse返回FALSESuccessor(x):NaturalNumberif(x==MAXINT)返回xelse返回x+1endNatural_NumberQ3：抽象数据类型如何表示和实现？抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。注1：它有些类似C语言中的结构（struct)类型，但增加了相关的服务。注2：教材中用的是类C语言（介于伪码和C语言之间）作为描述工具。其描述语法见P10-11。上机时要用具体语言实现，如C或C++等1.4算法效率的度量Q1.什么是算法？如何评判一个算法的好坏？Q2.时间复杂度和空间复杂度如何表示？Q3.计算举例讨论：程序设计实质＝好算法＋好结构答：算法是解决某一特定类型问题的有限运算序列。是一系列输入转换为输出的计算步骤。常用时间复杂度来衡量1.什么是算法？如何评判一个算法的好坏？算法有5个基本特性：算法评价有4个指标：有穷性、确定性、可行性、输入和输出运行时间、占用空间、正确性和简单性常用空间复杂度来衡量时间复杂度T(n)按数量级递增顺序为：注1：O（）为渐近符号。注2：空间复杂度S(n)按数量级递增顺序也与上表类同。复杂度高复杂度低渐进符号（O）的定义：当且仅当存在一个正的常数C，使得对所有的nn0，有f(n)Cg(n)，则f(n)=O(g(n))3n+2=O(n)/*3n+24nforn2*/3n+3=O(n)/*3n+34nforn3*/100n+6=O(n)/*100n+6101nforn10*/10n2+4n+2=O(n2)/*10n2+4n+211n2forn5*/6*2n+n2=O(2n)/*6*2n+n27*2nforn4*/例：例：分析以下程序段的时间复杂度。i=1;①while(i=n)i=i*2;②该算法的运行时间由程序中所有语句的频度（即该语句重复执行的次数）之和构成。解：分析：显然，语句①的频度是1。设语句2的频度是f(n)，则有：nnf)(2即f(n)≤log2n，取最大值f(n)=log2n所以该程序段的时间复杂度T(n)=1+f(n)=1+log2n=O(log2n)算法的时间复杂度是由嵌套最深层语句的频度决定的。作业：1.请在下次课前完成第1章自测卷全部内容；2.复习C语言，重点是结构类型和递归概念3.请试做配套习题集的1.8题和1.12题，另外，在看懂教材例1-6和例1-7的基础上，可试做1.4题。