java算法:抽象数据类型ADT
开发有关系数据和处理这些数据的方法的抽象数据模型是用计算机解决问题的过程中必不可少的步骤。
使用抽象数据类型,可以很好的把任何具体的数据结构表示与算法分开,利于研究算法。
抽象数据类型是一种智能通过接口访问的数据类型(值与值上的操作所构成的集合),我们把使用ADT的程序称为客户程序,把指定数据类型的程序称为实现。
抽象数据类型与其他数据类型的主要区别是:对于抽象数据类型,客户程序只能通过接口中提供的操作来访问数据值。接口把所有的数据表示和操作方法的实现完全与客户程序隔离。在Java中,一般不能直接访问数据,而是通过方法访问的。
例1:点的类实现
- 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(Pointp){
-
doubledx=x-p.x;
-
doubledy=y-p.y;
-
returnMath.sqrt(dx*dx+dy*dy);
- }
-
publicStringtoString(){
-
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:点类(替换实现)
- publicclassPoint2{
-
privatedoubler,theta;
-
-
privatestaticPoint2p2;
-
-
publicstaticPoint2getInstance(){
-
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(Point2p){
-
doubledx=x()-p.x();
-
doubledy=y()-p.y();
-
returnMath.sqrt(dx*dx+dy*dy);
- }
-
publicStringtoString(){
-
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接口
- publicinterfaceIPoint{
-
doublex();
-
doubley();
-
doubler();
-
doubletheta();
-
doubledistance(Pointp);
-
publicStringtoString();
- }
public interface IPoint {
double x();
double y();
double r();
double theta();
double distance(Point p);
public String toString();
}
ADT是作为支持模块化编程的一种有效机制。模块化编程是现代大型软件系统的一种组织方法。ADT提供了灵活的修改,ADT接口明确定义了程序访问的方法。
分享到:
相关推荐
在像Java这样的面向对象的语言中,抽象数据类型及其实现共同构成一个类。 与ADT相关的每个操作都由成员,功能或方法实现。 定义数据项所需空间的变量称为数据成员。 对象是类的实例,即在计算机程序执行期间创建并...
抽象数据风格的按字母排序算法用的是快速排序算法,代码位于SA\src\adtstyle\impl.AlphabetizerImpl.java,调用返回风格用的是插入排序算法,代码位于SA\src\invretstyle\Alphabetizer.java,管道过滤器风格用的是堆...
3.1 抽象数据类型 3.2 表ADT 3.2.1 表的简单数组实现 3.2.2 简单链表 3.3 JavaCollectionsAPI中的表 3.3.1 Collection接口 3.3.2 Iterator接口 3.3.3 List接口、ArrayList类和LinkedList类 3.3.4 例:remove方法对...
表、栈和队列3.1 抽象数据类型3.2 表ADT3.2.1 表的简单数组实现3.2.2 简单链表3.3 JavaCollectionsAPI中的表3.3.1 Collection接口3.3.2 Iterator接口3.3.3 List接口、ArrayList类和LinkedList类3.3.4 例:remove...
表、栈和队列3.1 抽象数据类型3.2 表ADT3.2.1 表的简单数组实现3.2.2 简单链表3.3 JavaCollectionsAPI中的表3.3.1 Collection接口3.3.2 Iterator接口3.3.3 List接口、ArrayList类和LinkedList类3.3.4 例:remove...
表、栈和队列3.1 抽象数据类型3.2 表ADT3.2.1 表的简单数组实现3.2.2 简单链表3.3 JavaCollectionsAPI中的表3.3.1 Collection接口3.3.2 Iterator接口3.3.3 List接口、ArrayList类和LinkedList类3.3.4 例:remove...
第8章 抽象数据类型 …… 第9章 效率与ADT 第10章 线性结构 第11章 符号表 第Ⅳ部分 递归数据 第12章 递归链表 第13章 树 第14章 表达式树 第15章 集合 第16章 图 第17章 展望Java
小结 练习 参考文献 笫3章 表、栈和队列 3.1 抽象数据类型(ADT) 3.2 表ADT 3.2.1 表的简单数组实现 3.2.2 链表 3.2.3 程序设计细节 3.2.4 双链表 3.2.5 循环链表 3.2.6 例子 3.2.7 链表的游标实现 ...
3.1 抽象数据类型 3.2 表adt 3.2.1 表的简单数组实现 3.2.2 简单链表 3.3 javacollectionsapi中的表 3.3.1 collection接口 3.3.2 iterator接口 3.3.3 list接口、arraylist类和linkedlist类 3.3.4...
3.1 抽象数据类型 3.2 表adt 3.2.1 表的简单数组实现 3.2.2 简单链表 3.3 javacollectionsapi中的表 3.3.1 collection接口 3.3.2 iterator接口 3.3.3 list接口、arraylist类和linkedlist类 3.3.4...
Java单链表源码分析编程课程 (HW) 编程 I:CSCI 220 + 220 实验室(CofC:2018 ...列表抽象数据类型 (ADT) 实现使用数组作为基本数据结构的有序单链表的实现 列出 ADT 个性化和算法分析 通过添加回文检测器/去除器,
1.4 抽象数据类型 12 1.4.1 设计ADT 14 1.4.2 涉及其他ADT的ADT 17 1.5 ADT包 18 1.5.1 确定行为 18 1.5.2 指定数据和操作 19 1.5.3 ADT的模板接口 22 1.5.4 使用ADT包 24 C++片段1 C++类 29 C1.1 待解决的...
1)为了实现上述程序功能,需要定义单链表的抽象数据类型: ADT LinkList { 数据对象:D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0} 数据关系:R={,ai+1>|ai,ai+1 ∈D} 基本操作: (1)insert 初始化状态:...
介绍该存储库由抽象数据类型,常用算法和LeetCode练习的基础组成。选择排序插入排序合并排序快速排序堆排序计数排序桶分类基数排序 搜索二元搜寻树遍历深度优先搜索广度优先搜索Dijkstra算法普里姆算法拓扑排序
对其中的基本原理有必要掌握抽象数据类型及其作为面向对象编程的数据结构的实现。在选择和分析各种ADT实现中使用面向对象的原理。顺序和链接的存储表示形式:列表,堆栈,队列和表。非线性数据结构:树和图。递归,...
2.16 数据类型和数据结构是二种不一样的东西 69 2.17 为什么需要变量这些东东 69 2.18 面向类型化的设计和面向无类型泛化的设计-OO不是银弹 70 第3章 语言之争 71 3.1 学编程之初,语言之争 71 3.2 语言与应用与人(1...
3.4 对引用数据类型的操作 65 3.4.1 字符串操作 65 3.4.2 数组操作 67 3.4.3 NIO 操作 68 3.4.4 访问域 69 3.4.5 调用方法 71 3.4.6 域和方法描述符 72 3.5 异常处理 75 3.5.1 捕获异常 75 3.5.2 抛出异常 ...