1.3 面向对象的数据结构表示
1.3.1 Java面向对象基础
1. 类的声明与实例化
Java语言是面向对象的程序设计语言，类和对象是面向对象的核心。Java语言提供了创建类和创建对象的语法支持。定义类的简单语法如下。
[修饰符] class 类名
{
零个到多个构造器定义
零个到多个成员变量
零个到多个成员方法
}
在上面的语法格式中，修饰符可以是public、final、abstract，或者完全省略这三个修饰符，类名必须是一个合法的标识符。
例如，圆是大家都熟悉的一种几何图形，半径是圆的一个属性，它的值决定了圆的大小，下面我们就来定义一个表示圆的类。
public class Circle
{
private double radius；
public Circle(double r) //构造器
{
radius=r;
}
}
在Java中，自定义一个类的实质是自定义一种数据类型。因此，必须将类实例化之后才能引用类中的成员变量和成员方法。所谓“实例化”就是使用类声明一个变量并通过new操作符以及构造器完成各成员变量的初始化。
例如，要得到一个半径为2.5的圆，则可以使用下面代码进行实例化。
Circle c= new Circle(2.5);
其中，变量c本质是一个Circle型的变量，是一个半径为2.5的圆对象。该对象就是通过操作符new并且调用构造器Circle(2.5)完成半径radius的初始化之后得到的。
2. 类的成员的定义与使用
类是数据以及数据的操作的封装体。类的成员详细描述了类的数据信息（成员变量）以及针对这些数据信息的操作方法（成员方法）。Java是完全面向对象的，方法（在C语言中称为函数）不能独立存在，所有的方法都必须定义在类之中。
例如，上面定义的Circle类缺乏任何操作方法。为了计算圆的周长，则必须修改其定义，添加相应的方法，代码如下。
//Circle.java
public class Circle {
private double radius;
public Circle(double r){
radius=r;
}
public double getPerimeter ( ){ //计算圆的周长
return Math.PI*radius*2;
}
}
类的成员在类的内部允许直接引用，例如在上面代码中为了计算圆的周长直接引用了成员变量radius。但是，请注意，在类的外部引用类的成员通常必须使用对象名来引用，格式为：“对象.成员名”。
例如，
public class Test1{
public static void main(String[] args) {
Circle c = new Circle(2.5);
System.out.println(c.getPerimeter ( ));
}
}
3. 抽象类
在Java中，类的成员方法用来完成类的成员变量的运算处理，因此通常拥有明确的可执行的语句代码，例如Circle类的getPrimeter()方法拥有“return Math.PI*radius*2; ”语句。但是，当类表达的是抽象概念（例如几种图形）时，其运算处理往往也是抽象的，此时只能定义方法的格式，而无法写出语句代码。
例如，针对几何图形Shape类及其周长计算，可使用以下代码进行描述。
public abstract class Shape {
public abstract double getPerimeter ( );
}
在Java中，抽象类及其抽象成员方法必须使用abstract来修饰。抽象方法不能有方法体。抽象类不能被实例化，无法使用new关键字来创建Shape类型的对象，但是抽象类可以作为父类被其他类继承。
例如，使用抽象类Shape定义Circle类的代码如下：
public class Circle extends Shape{
private double radius;
public Circle(double r){
radius = r;
}
public double getPerimeter( ) //重写Shape类计算周长的抽象方法
{
return Math.PI*radius*2;
}
}
可见，抽象类的子类必须实现抽象类的抽象成员方法。
同样，三角形类Triangle的定义代码如下。
public class Triangle extends Shape{
private double a;
private double b;
private double c;
public Triangle(double a,double b,double c)
{
this.a=a;
this.b=b;
this.c=c;
}
public double getPerimeter( ) //重写Shape类计算周长的抽象方法
{ return a+b+c; }
}
//test2.java
public class Test2 {
public static void main(String[] args) {
Shape s1=new Triangle(3,4,5);
Shape s2=new Circle(3.5);
System.out.println(s1.getPerimeter());
System.out.println(s2.getPerimeter());
}
}
在上面main( )方法中定义了两个Shape型的变量s1和s2，它们分别指向Triangle对象和Circle对象。由于Shape类定义了getPerimeter()方法，所以可以直接使用s1和s2变量调用getPerimeter()方法，无需强制类型转换为其子类型。
4. 泛型类
顾名思义，泛型就是一种包含了要运算处理的数据的类型尚不明确而临时使用类型参数（如K）来表示的一种自定义数据类型。
例如，映射Map类就是典型的泛型类，代码如下：
public class Map<K, V>{ //指定类型参数
K k; //使用类型参数定义成员变量
V v;
public void set(K key, V value){ //使用类型参数定义成员方法
k=key;
v= value;
}
public V get(){
return v;
}
}
其中，Map类包含了两个类型参数K和V，K表示键的类型，V表示值的类型，Map类实现由键向值的映射和转换。
注意，泛型类在使用时必须明确指定各类型参数对应的实际数据类型，Java编译器在编译代码时将根据所指定的实际数据类型自动替换对应的类型参数。
例如：
Map< String, String > a = new Map< String, String >();
a.set("China","中国");
System.out.println(a.get());
Map<Integer, String > b = new Map<Integer, String >();
b.set(21,"10101");
System.out.println(a.get());
上面代码的第一行构造了一个键/值均为String类型的对象a，可实现英文单词“China”向中文词汇“中国”的转换。第4行构造了一个键为Integer型、值为String型的对象b，可实现十进数21向二进制10101的转换。
1.3.2 面向对象的抽象数据类型
数据结构研究的是数据对象内部各数据元素之间逻辑关系问题，它不关心数据的具体类型，因此数据结构本身就是一种抽象概念。为了弄清楚针对特定数据结构计算机能进行何种操作，就必须把数据结构中的数据对象、数据关系和基本操作看作一个整体进行定义，从而得到抽象数据类型（Abstract Data Type）。
在传统的数据结构教材中，抽象数据类型通常表示为｛D，S，P｝集合。
ADT抽象数据类型名
{
数据对象D：<数据对象的定义>
数据关系S：<数据关系的定义>
基本操作P：<基本操作的定义>
} ADT抽象数据类型名
其中，数据对象D的定义是在已有数据类型的基础之上对新的数据对象的定义，以明确其数据元素组成；数据关系S的定义描述了数据元素之间的逻辑结构；基本操作P的定义包括操作名称、参数列表、初始条件和操作结果四部分内容的定义和描述。数据对象和数据关系的定义可采用数据符号或自然语言进行描述。基本操作的定义格式为：
<操作名称>([参数列表]); //前提条件与操作结果描述
例如，一个集合的抽象数据类型可定义如下：
ADT Set
{
数据元素：ai∈同一数据对象，i=1，2，...，n（n≥0）
逻辑结构：<ai,ai-1>| i=1，2，...，n（n≥0）,a1无前驱，an无后继
基本操作：InitSet( ); //建立一个空的集合
Length( ); //求集合的长度
Insert( i,x); //向集合中插入一个新元素x
Delete( i); //删除集合中的第i个元素
...... //设计者可以根据实际需要添加必要的操作
}ADT Set
正如前文中的Circle类是对所有圆的抽象，Shape类是对所有几何图形的抽象一样，Java面向对象思想的抽象性与数据结构中的抽象数据类型的抽象性在目标上是相同的。因此，我们也可以使用Java的抽象类、泛型类或接口来表示数据结构中的抽象数据类型，从而实现面向对象的抽象数据类型表示。
用Java泛型类表示的抽象数据类型的格式如下。
//数据关系的定义
[访问修改符] class抽象数据类型名<类型参数列表>
{
[访问修改符] 数据类型 数据对象; //数据对象的定义
[访问修改符] 返回值类型 基本操作1(参数列表){
//基本操作1的定义
}
//其他基本操作
}
例如，一个字典的抽象数据类型可定义如下：
//数据关系的定义：词典是若干个原文词汇及对应的译文词汇所构成的集合
public class Dictionary<K,V> {
//数据对象的定义：词典由原文词汇表和译文词汇表组成
public K[] keys;
public V[] values;
public int n;
//基本操作：词典提供初始化、添加新词、删除词条、翻译等操作
public Dictionary (int max){
//初始化操作的定义
}
public void append (K k, V v){
//添加新词的定义
}
public boolean delete (K k){
//删除词条的定义
}
public V translate(K k){
//翻译操作的定义
}
//其他操作定义
}
1.3.3 使用Java语言描述数据结构的优势
1. 使用Java描述数据结构更加简单
Java语言是一种完全面向对象的程序设计语言，支持使用对象、类、继承、封装、消息等基本概念来进行程序设计。在Java中，使用类时必须先声明变量名（也称对象名），然后实例化，再引用类的成员。其中，实例化的本质是为对象分配足够的内存空间，以保存各数据成员的值。对象名代表对象的引用，可理解为对象所拥有的内存空间的首地址。因此，Java语言不使用指针就可以描述数据结构的前驱后继关系。
Java提供了自动的垃圾回收机制，在实现复杂的数据结构运算处理时程序员不必为内存管理而担忧。因此Java语言使用时简单、方便。
2. Java的泛型机制更加适合数据结构的抽象表示
Java的泛型类定义了一个代码模板，专门针对暂时不确定的数据类型进行抽象描述和定义。因此，相对抽象数据类型的传统表示方法，Java的泛型类将更加直观和方便。
例如，在不使用泛型机制描述集合时，必须指定集合元素的数据类型，代码如下。
public class Set {
private final int MaxSize=20;
private int[ ] elements;
private int length;
public Set( ) { //建立一个空的集合
length=0;
elements =new int [MaxSize];
}
public int Length( ) { //求集合的长度
return length;
}
public boolean Insert(int x) { //向集合中插入一个新元素x
......//具体实现此处省略
}
public boolean Delete( i) { //删除集合中的第i个元素
......// 具体实现此处省略
}
}
上述代码定义了一个整数集合。但在实际应用中集合的数据元素可以是整数，也可以是字符、浮点数或者更复杂的数据。若不借助泛型机制，此时必须反复书写相似的代码，以定义各种集合。此时，工作量将成倍地增加。同时，相似的代码在编辑时极易出错。若使用泛型机制，则只需引入一个类型参数T来表示集合元素的数据类型即可完成泛型集合的定义，之后就可以该泛型集合来创建各种类型的集合对象。代码如下所示。
public class Set<T> { private final int MaxSize =20; private T[ ] elements; private int length; public Set( ) { //建立一个空的集合 length=0; elements =(T[])new Object [MaxSize]; //不能实例化一个泛型对象，所以先实例化一个Object数组，再强制转换类型 } public int Length( ) { //求集合的长度 return length; } public boolean Insert(T x) { //向集合中插入一个新元素x ......//具体实现此处省略 } public boolean Delete(int i) { //删除集合中的第i个元素 ......//具体实现此处省略 } }
其中，突出显示的是需要重点关注的代码，其中T仅仅是一个合法的标识符，在使用Set时必须用实际的数据类型来替换T。
例如：
Set< Integer > a= new Set< Integer >;
编译器在遇到Set< Integer >时会自动用Integer替换原代码中的T，即集合中的数据元素最终为Integer类型。
以此类推，也可以把T绑定为charcter或者其他任意类型。
【注意】Java泛型类在描述抽象数据类型时更加直观和方便，因此本书在后文将主要使用泛型类来定义各种数据结构。
3. java.util提供多种数据结构，可以加速应用系统开发
在java.util包中，Java提供了多种数据结构，包括ArrayList、Hashtable、LinkedList、Map、Queue、Set、Stack、TreeSet、Vector等，这些数据结构在Java程序中可直接使用，而不需要用户自己编程实现，这样可大大加快应用系统的开发速度。
例如：
java.util.Stack s=new java.util.Stack(); //创建堆栈对象s
s.push("中国"); //将数据压入对象
s.push("四川");
while(!s.empty()) //测试堆栈是否为空
System.out.print(s.pop()+" "); //将数据从堆栈中弹出
System.out.println();
堆栈操作的基本规则是“先进后出”，因此上述代码最终输出结果为“四川 中国”。
看到这里，有读者会说“既然Java已经实现了各种数据结构，我们为什么还要学习数据结构呢？”是的，Java API确实提供了多种数据结构，但这些数据结构往往只满足通用的功能需求，在实际应用中通常需要自定义数据结构，以提供特殊数据运算处理。此外，数据结构这门课是提升编程能力的最给力的课程，因此作为刚涉足程序设计的在校学生来说，除了要了解各种数据结构的概念之外，最重要的是要理解各种数据结构的操作算法并提高实际编程能力。