抽象数据类型如何表示和实现

课程内容：–计算机软件的基础知识———数据结构课时安排：–数据结构——32学时–上机——8学时教材：–实用数据结构与算法设计庄晋林等参考书：–数据结构严蔚敏清华目录1.1数据结构的发展史及地位1.2数据结构的定义1.3数据类型1.4算法及算法分析数据结构:是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数学硬件软件数据结构数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。1.2数据结构的定义1、线性表示例例1书目自动检索系统001高等数学樊映川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书S02……………………书目文件按书名按作者名按分类号高等数学001，003……理论力学002，……..线性代数004，………………..樊映川001,…华罗庚002,….栾汝书004,….…….…….L002,…S001,003,…………索引表线性表例2人机对奕问题树……..……..…...…...…...…...什么是数据结构？答:(见教材P6)是相互之间存在一种或多种特定关系的数据元素的集合，表示为：（数值或非数值）Data_Structure=（D,S）或：是指同一数据元素类中各元素之间存在的关系。亦可表示为：S＝（D,R）或B=（K,R）元素有限集关系有限集1.2.2基本概念及术语1、数据(data)—所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息）。2、数据元素(dataelement)—是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。数据项(dataitem)——构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性等）。术语：数据、数据元素、数据项、数据对象三者之间的关系：数据数据元素数据项例：班级通讯录个人记录姓名、年龄……4、数据结构(datastructure)◎数据结构有逻辑结构和物理结构之分。◎物理结构是一种逻辑结构在存储器中的存储方式，存储方式有顺序、链接、索引、散列等多种，所以一种逻辑结构可以采用多种物理结构存储。◎通常所说的数据结构就是指逻辑结构。3、数据对象(dataobject)——性质相同的数据元素的集合,是数据的一个子集。什么叫数据的逻辑结构？答：指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。逻辑结构可细分为4类：集合结构：仅同属一个集合线性结构:一对一（1:1)树结构:一对多（1:n)图结构:多对多(m:n)非线性线性什么叫数据的物理结构？答：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：顺序、链式、索引、散列元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储1536元素21400元素11346元素3∧元素41345h存储地址存储内容指针1345元素114001346元素4∧…….……..…….1400元素21536…….……..…….1536元素31346链式存储h什么是数据的运算？答：在数据的逻辑结构上定义的操作算法。在数据的存储结构上实现。最常用的数据运算有5种：插入、删除、修改、查找、排序1.3数据类型1数据类型与抽象数据类型的区别？2抽象数据类型如何定义？3抽象数据类型如何表示和实现？讨论：1、数据类型与抽象数据类型的区别？数据类型：是一个值的集合和定义在该值上的一组操作的总称。抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。2、抽象数据类型如何定义？抽象数据类型可以用以下的三元组来表示：ADT=（D，S，P）数据对象D上的关系集D上的操作集ADT抽象数据类型名{数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义}ADT抽象数据类型名ADT常用定义格式3、抽象数据类型如何表示和实现？抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。注1：它有些类似C语言中的结构（struct)类型，但增加了相关的服务。注2：教材中用的是类C语言（介于伪码和C语言之间）作为描述工具。但上机时要用具体语言实现，如C或C++等1.4算法和算法分析1.什么是算法？如何评判一个算法的好坏？2.时间复杂度和空间复杂度如何表示？3.计算举例讨论：程序设计实质＝好算法＋好结构答：算法是解决某一特定类型问题的有限运算序列。是一系列输入转换为输出的计算步骤。常用时间复杂度来衡量1.什么是算法？如何评判一个算法的好坏？算法有5个基本特性：算法评价有5个指标：有穷性、确定性、可行性、输入和输出运行时间、占用空间、正确性、健壮性和可读性常用空间复杂度来衡量例：分析以下程序段的时间复杂度。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)算法的时间复杂度是由嵌套最深层语句的频度决定的。3、空间复杂性（SpaceComplexity）◎算法运行中占用空间包括算法本身占用，输入输出数据占用和运行中的临时占用。◎同一个问题，算法不同，运行中的临时空间不同，即空间复杂性不同。◎C只考虑在运行中为局部变量分配的存贮空间的大小，一般也以数量级表示。时间复杂度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*/例：