精华内容
下载资源
问答
  • 抽象数据类型

    2021-03-28 22:51:59
    抽象数据类型1. 抽象数据类型 1. 抽象数据类型 抽象数据类型(Abstract data type,ADT)是带有一组操作的一些对象的集合。抽象数据类型是数学的抽象;在ADT的定义中没有地方提到关于这组操作是如何实现的具体解释。...

    1. 抽象数据类型

      抽象数据类型(Abstract data type,ADT)是带有一组操作的一些对象的集合。抽象数据类型是数学的抽象;在ADT的定义中没有地方提到关于这组操作是如何实现的具体解释。诸如线性表、集合、图以及它们各自的操作一起形成的这些对象都可以被看作是抽象数据类型,这就像整数、实数、布尔数都是数据类型一样。整数、实数、布尔数各自都有与之相关的操作,而抽象数据类型也是如此。对于集合ADT,可以有像添加(add)、删除(remove)以及包含(contain)这样一些操作。当然,也可以只要两种操作并(union)和查找(find),这两种操作又在集合上定义了一种不同的ADT。

    2. STL

      在C++语言的库中包含公共数据结构的实现。C++的这部分内容就是众所周知的标准模板库(Standard Template Library, STL)。一般来说,这些数据结合称为集合或容器。

    3. Java Collection API

      在类库中,Java语言包含有一些普通数据结构的实现。Java语言的这一部分通常叫做 Collection API 。

    3.1 Collection 接口

      Collection API 位于 java.util 包中。集合的概念在Collection接口中得到抽象,它存储一组类型相同的对象。

    3.2 Iterator 接口

    展开全文
  • 一、抽象数据类型描述: 线性表的抽象数据Java接口描述如下: public interface IList { public void clear();//将线性表置成空表 public boolean isEmpty();//判断线性表是否为空表 public int length();//返回...

    一、抽象数据类型描述:

    线性表的抽象数据Java接口描述如下:

    public interface IList {
    	public void clear();//将线性表置成空表
    	public boolean isEmpty();//判断线性表是否为空表
    	public int length();//返回线性表的长度                                                                                                     
    	public Object get(int i) throws Exception;//读取并返回线性表中第i个数据元素
    	public void insert(int i,Object x) throws Exception;//插入x作为第i个元素
    	public void remove(int i) throws Exception; //删除第i个元素
    	public int indexOf(Object x);//返回元素x首次出现的位序号
    	public void display();//输出线性表中各个数据元素的值
    }
    

    二、线性表的顺序存储:

    可以使用数组来描述线性表的顺序存储结构。在程序设计语言中数组是一种构造数据类型。数组存储具有相同数据类型的元素集合,刷组的存储单元个数成为数组长度,每个存储单元的地址是连续的,每个元素连续存储。数组通过下标识别元素,元素的小标是其存储单元序号奥,表示元素在数组中的位置。一维数组使用一个下标为一确定一个元素,的、二维数组使用两个下表唯一确定一个元素。
    下面是顺序表类的Java语言描述:

    private Object[] listItem;//顺序表存储空间
    	private int curLen;//顺序表当前长度
    	private int maxSize;
    	
    	//构造一个存储空间为maxsize的顺序表
    	public SqList(int maxsize) {
    		curLen=0;
    		maxSize=maxsize;
    		listItem=new Object[maxSize];
    	}
    	//顺序表置为空表
    	public void clear() {
    		curLen=0;
    	}
    	//判断顺序表是否为空表,若空,返回true,否则,返回false
    	public boolean isEmpty() {
    		return curLen==0;
    	}
    	//返会顺序表的长度
    	public int length() {
    		return curLen;
    	}
    	//读取并返回第i个数据元素
    	public Object get(int i) throws Exception {
    		if(i<0||i>curLen-1)
    			throw new Exception("第"+i+"个数据元素不存在");
    		return listItem[i];
    	}
    	//插入x作为第i个元素
    	public void insert(int i, Object x) throws Exception{
    		if(curLen==maxSize)//判断顺序表的存储空间是否已满
    			throw new Exception("顺序表满");
    		if(i<0||i>curLen)//判断参数的值是否满足
    			throw new Exception("插入位置非法");
    for(int j=curLen;j>i;j--)//将插入位置及其之后的所有的数据元素后移一个存储位置
    	listItem[j]=listItem[j-1];
    
    listItem[i]=x;//在位置处插入新的数据元素
    curLen++;//表长加1
    
    	}
    	//删除第i个元素
    	public void remove(int i) throws Exception{
    		if(i<0||i>curLen-1)
    			throw new Exception("删除位置非法");
    		for(int j=i;i<curLen-1;i++)
    			listItem[j]=listItem[j+1];
    		curLen--;
    
    	}
    	//返回元素x首次出现的位序号
    	public int indexOf(Object x) {
    		for(int i=0;i<=curLen-1;i++)
    		{
    			if(listItem[i].equals(x))
    				return i;
    		}
    		return -1;
    	
    	}
    	//输出顺序表中的元素
    	public void display() {
    		for(int i=0;i<curLen-1;i++)
    			System.out.print(listItem[i]+" ");
    	}
    	public static void main(String[] args) throws Exception {
    		// TODO Auto-generated method stub
    		SqList L=new SqList(26);
    		for(int i=0;i<26;i++){
    			L.insert(i,'a'+i);
    		}
    		System.out.println("请输入需要查询元素的位序号:");
    		int i=new Scanner(System.in).nextInt();
    		if(i>0&&i<25){
    		System.out.println("第"+i+"个元素的直接前驱为:"+L.get(i-1));
    		System.out.println("第"+i+"个元素的直接后继为:"+L.get(i+1));
    		}
    		else if(i==0){
    		System.out.println("第"+i+"个元素的直接前驱不存在");
    		System.out.println("第"+i+"个元素的直接后继为:"+L.get(i+1));
    		}
    		else{
    		System.out.println("第"+i+"个元素的直接后继不存在");
    		System.out.println("第"+i+"个元素的直接前驱为:"+L.get(i-1));
    		}
    	}
    
    展开全文
  • 抽象数据类型抽象数据类型是描述数据结构的一种理论工具。在介绍抽象数据类型之前我们先介绍一下数据类型的基本概念。数据类型(data type)是一组性质相同的数据元素的集合以及加在这个集合上的一组操作。例如Java ...

    抽象数据类型

    抽象数据类型是描述数据结构的一种理论工具。在介绍抽象数据类型之前我们先介绍一

    下数据类型的基本概念。

    数据类型(data type)是一组性质相同的数据元素的集合以及加在这个集合上的一组操

    作。例如Java 语言中就有许多不同的数据类型,包括数值型的数据类型、字符串、布尔型

    等数据类型。以Java 中的int 型为例,int 型的数据元素的集合是[-2147483648,2147483647]

    间的整数,定义在其上的操作有加、减、乘、除四则运算,还有模运算等。

    定义数据类型的作用一个是隐藏计算机硬件及其特性和差别,使硬件对于用户而言是透

    明的,即用户可以不关心数据类型是怎么实现的而可以使用它。定义数据类型的另一个作用

    是,用户能够使用数据类型定义的操作,方便的实现问题的求解。例如,用户可以使用Java

    定义在int 型的加法操作完成两个整数的加法运算,而不用关心两个整数的加法在计算机中

    到底是如何实现的。这样不但加快了用户解决问题的速度,也使得用户可以在更高的层面上

    考虑问题。

    与机器语言、汇编语言相比,高级语言的出现大大地简便了程序设计。但是要将解答问

    题的步骤从非形式的自然语言表达到形式化的高级语言表达,仍然是一个复杂的过程,仍然

    要做很多繁杂琐碎的事情,因而仍然需要抽象。

    对于一个明确的问题,要解答这个问题,总是先选用该问题的一个数据模型。接着,弄清

    该问题所选用的数据模型在已知条件下的初始状态和要求的结果状态,以及隐含着的两个状

    态之间的关系。然后探索从数据模型的已知初始状态出发到达要求的结果状态所必需的运算

    步骤。

    我们在探索运算步骤时,首先应该考虑顶层的运算步骤,然后再考虑底层的运算步骤。

    所谓顶层的运算步骤是指定义在数据模型级上的运算步骤,或叫宏观运算。它们组成解答问

    题步骤的主干部分。其中涉及的数据是数据模型中的一个变量,暂时不关心它的数据结构;

    涉及的运算以数据模型中的数据变量作为运算对象,或作为运算结果,或二者兼而为之,简

    称为定义在数据模型上的运算。由于暂时不关心变量的数据结构,这些运算都带有抽象性质,

    不含运算的细节。所谓底层的运算步骤是指顶层抽象的运算的具体实现。它们依赖于数据模

    型的结构,依赖于数据模型结构的具体表示。因此,底层的运算步骤包括两部分:一是数据

    模型的具体表示;二是定义在该数据模型上的运算的具体实现。我们可以把它们理解为微观

    运算。于是,底层运算是顶层运算的细化,底层运算为顶层运算服务。为了将顶层算法与底

    层算法隔开,使二者在设计时不会互相牵制、互相影响,必须对二者的接口进行一次抽象。

    让底层只通过这个接口为顶层服务,顶层也只通过这个接口调用底层的运算。这个接口就是

    抽象数据类型。

    抽象数据类型(abstract data type, 简称ADT)由一种数据模型和在该数据模型上的一

    组操作组成。

    抽象数据类型包括定义和实现两个方面,其中定义是独立于实现的。抽象数据类型的定

    义仅取决于它的逻辑特性,而与其在计算机内部的实现无关,即无论它的内部结构如何变化,

    只要它的逻辑特性不变,都不会影响到它的使用。其内部的变化(抽象数据类型实现的变化)

    只是可能会对外部在使用它解决问题时的效率上产生影响,因此我们的一个重要任务就是如

    何简单、高效地实现抽象数据类型。很明显,对于不同的运算组,为使组中所有运算的效率

    都尽可能地高,其相应的数据模型具体表示的选择将是不同的。在这个意义下,数据模型的

    具体表示又依赖于数据模型上定义的那些运算。特别是,当不同运算的效率互相制约时,还

    必须事先将所有的运算的相应使用频度排序,让所选择的数据模型的具体表示优先保证使用

    频度较高的运算有较高的效率。

    我们应该看到,抽象数据类型的概念并不是全新的概念。抽象数据类型和数据类型在实

    质上是一个概念,只不过是对数据类型的进一步抽象,不仅限于各种不同的计算机处理器中

    已经实现的数据类型,还包括为解决更为复杂的问题而由用户自定义的复杂数据类型。例如

    高级语言都有的“整数”类型就是一种抽象数据类型,只不过高级语言中的整型引进实现了,

    并且实现的细节可能不同而已。我们没有意识到抽象数据类型的概念已经孕育在基本数据类

    型的概念之中,是因为我们已经习惯于在程序设计中使用基本数据类型和相关的运算,没有

    进一步深究而已。

    抽象数据类型一方面使得使用它的人可以只关心它的逻辑特征,不需要了解它的实现方

    式。另一方面可以使我们更容易描述现实世界,使得我们可以在更高的层面上来考虑问题。

    例如可以使用树来描述行政区划,使用图来描述通信网络。

    根据抽象数据类型的概念,对抽象数据类型进行定义就是约定抽象数据类型的名字,同

    时,约定在该类型上定义的一组运算的各个运算的名字,明确各个运算分别要 有多少个参

    数,这些参数的含义和顺序,以及运算的功能。一旦定义清楚,人们在使用时就可以像引用

    基本数据类型那样,十分简便地引用抽象数据类型;同时,抽象数据类型的实现就有了设计

    的依据和目标。抽象数据类型的使用和实现都与抽象数据类型的定义打交道,这样使用与实

    现没有直接的联系。因此,只要严格按照定义,抽象数据类型的使用和实现就可以互相独立,

    互不影响,实现对它们的隔离,达到抽象的目的。

    为此抽象数据类型可以使用一个三元组来表示:

    ADT = (D, S, P)

    其中D 是数据对象,S 是D 上的关系集,P 是加在D 上的一组操作。

    在定义抽象数据类型时,我们使用以下格式:

    ADT 抽象数据类型名{

    数据对象:

    数据关系:

    基本操作:

    }

    展开全文
  • java算法:抽象数据类型ADT开发有关系数据和处理这些数据的方法的抽象数据模型是用计算机解决问题的过程中必不可少的步骤。使用抽象数据类型,可以很好的把任何具体的数据结构表示与算法分开,利于研究算法。抽象...

    java算法:抽象数据类型ADT

    开发有关系数据和处理这些数据的方法的抽象数据模型是用计算机解决问题的过程中必不可少的步骤。

    使用抽象数据类型,可以很好的把任何具体的数据结构表示与算法分开,利于研究算法。

    抽象数据类型是一种智能通过接口访问的数据类型(值与值上的操作所构成的集合),我们把使用ADT的程序称为客户程序,把指定数据类型的程序称为实现。

    抽象数据类型与其他数据类型的主要区别是:对于抽象数据类型,客户程序只能通过接口中提供的操作来访问数据值。接口把所有的数据表示和操作方法的实现完全与客户程序隔离。在Java中,一般不能直接访问数据,而是通过方法访问的。

    例1:点的类实现

    Java代码 icon_copy.gif

    publicclassPoint{

    privatedoublex,y;

    Point(){

    x = Math.random();

    y = Math.random();

    }

    Point(doublex,doubley){

    this.x = x;

    this.y = y;

    }

    doublex(){

    returnx;

    }

    doubley(){

    returny;

    }

    doubler(){

    returnMath.sqrt(x * x + y * y);

    }

    doubletheta(){

    returnMath.atan2(y , x);

    }

    doubledistance(Point p){

    doubledx = x - p.x;

    doubledy = y - p.y;

    returnMath.sqrt(dx * dx + dy * dy);

    }

    publicString toString(){

    return"("+ x +" , "+ y +")";

    }

    }

    public class Point{

    private double x,y;

    Point(){

    x = Math.random();

    y = Math.random();

    }

    Point(double x, double y){

    this.x = x;

    this.y = y;

    }

    double x(){

    return x;

    }

    double y(){

    return y;

    }

    double r(){

    return Math.sqrt(x * x + y * y);

    }

    double theta(){

    return Math.atan2(y , x);

    }

    double distance(Point p){

    double dx = x - p.x;

    double dy = y - p.y;

    return Math.sqrt(dx * dx + dy * dy);

    }

    public String toString(){

    return "(" + x + " , " + y + ")";

    }

    }

    定义ADT的根本原因:通过使客户不能直接访问数据表示,可以随意地对数据表示进行修改!在这种情况下,使用极坐标来表示点,但客户程序可以不管点是如何实现的而执行相同的运算。

    例2:点类(替换实现)

    Java代码 icon_copy.gif

    publicclassPoint2{

    privatedoubler,theta;

    privatestaticPoint2 p2;

    publicstaticPoint2 getInstance(){

    doublex = Math.random() *100;

    doubley = Math.random() *100;

    p2 =newPoint2(x,y);

    returnp2;

    }

    publicPoint2(doublex,doubley){

    this.r = Math.sqrt(x * x + y * y);

    this.theta = Math.atan2(y , x);

    }

    publicdoublex(){

    returnr * Math.cos(theta);

    }

    publicdoubley(){

    returnr * Math.sin(theta);

    }

    publicdoubler(){

    returnr;

    }

    publicdoubletheta(){

    returntheta;

    }

    publicdoubledistance(Point2 p){

    doubledx = x() - p.x();

    doubledy = y() - p.y();

    returnMath.sqrt(dx * dx + dy * dy);

    }

    publicString toString(){

    return"("+ x() +" , "+ y() +")";

    }

    }

    public class Point2{

    private double r,theta;

    private static Point2 p2;

    public static Point2 getInstance(){

    double x = Math.random() * 100;

    double y = Math.random() * 100;

    p2 = new Point2(x,y);

    return p2;

    }

    public Point2(double x, double y){

    this.r = Math.sqrt(x * x + y * y);

    this.theta = Math.atan2(y , x);

    }

    public double x(){

    return r * Math.cos(theta);

    }

    public double y(){

    return r * Math.sin(theta);

    }

    public double r(){

    return r;

    }

    public double theta(){

    return theta;

    }

    public double distance(Point2 p){

    double dx = x() - p.x();

    double dy = y() - p.y();

    return Math.sqrt(dx * dx + dy * dy);

    }

    public String toString(){

    return "(" + x() + " , " + y() + ")";

    }

    }

    使用ADT,精确提供返回客户感兴趣的数据方法。而且在实现方法更灵活。

    例3:点的ADT接口

    Java代码 icon_copy.gif

    publicinterfaceIPoint {

    doublex();

    doubley();

    doubler();

    doubletheta();

    doubledistance(Point p);

    publicString toString();

    }

    public interface IPoint {

    double x();

    double y();

    double r();

    double theta();

    double distance(Point p);

    public String toString();

    }

    ADT是作为支持模块化编程的一种有效机制。模块化编程是现代大型软件系统的一种组织方法。ADT提供了灵活的修改,ADT接口明确定义了程序访问的方法。

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 26,259
精华内容 10,503
关键字:

抽象数据类型