1.3 面向?qū)ο蟮臄?shù)據(jù)結(jié)構表示

1.3.1 Java面向?qū)ο蠡A

1. 類的聲明與實例化

Java語言是面向?qū)ο蟮某绦蛟O計語言，類和對象是面向?qū)ο蟮暮诵摹ava語言提供了創(chuàng)建類和創(chuàng)建對象的語法支持。定義類的簡單語法如下。

[修飾符]  class  類名
{
        零個到多個構造器定義
        零個到多個成員變量
        零個到多個成員方法
}

在上面的語法格式中，修飾符可以是public、final、abstract，或者完全省略這三個修飾符，類名必須是一個合法的標識符。

例如，圓是大家都熟悉的一種幾何圖形，半徑是圓的一個屬性，它的值決定了圓的大小，下面我們就來定義一個表示圓的類。

public class Circle
{
        private double radius；
        public Circle(double r)  //構造器
        {
               radius=r;
        }
}

在Java中，自定義一個類的實質(zhì)是自定義一種數(shù)據(jù)類型。因此，必須將類實例化之后才能引用類中的成員變量和成員方法。所謂“實例化”就是使用類聲明一個變量并通過new操作符以及構造器完成各成員變量的初始化。

例如，要得到一個半徑為2.5的圓，則可以使用下面代碼進行實例化。

Circle c= new Circle(2.5);

其中，變量c本質(zhì)是一個Circle型的變量，是一個半徑為2.5的圓對象。該對象就是通過操作符new并且調(diào)用構造器Circle(2.5)完成半徑radius的初始化之后得到的。

2. 類的成員的定義與使用

類是數(shù)據(jù)以及數(shù)據(jù)的操作的封裝體。類的成員詳細描述了類的數(shù)據(jù)信息（成員變量）以及針對這些數(shù)據(jù)信息的操作方法（成員方法）。Java是完全面向?qū)ο蟮?，方法（在C語言中稱為函數(shù)）不能獨立存在，所有的方法都必須定義在類之中。

例如，上面定義的Circle類缺乏任何操作方法。為了計算圓的周長，則必須修改其定義，添加相應的方法，代碼如下。

//Circle.java
public class Circle {
        private double radius;
        public Circle(double r){
                radius=r;               
        }
        public double getPerimeter ( ){          //計算圓的周長
                return Math.PI*radius*2;
        }
}

類的成員在類的內(nèi)部允許直接引用，例如在上面代碼中為了計算圓的周長直接引用了成員變量radius。但是，請注意，在類的外部引用類的成員通常必須使用對象名來引用，格式為：“對象.成員名”。

例如，

public class Test1{        
        public static void main(String[] args) {
                Circle c = new Circle(2.5);
                System.out.println(c.getPerimeter ( ));
        }
}

3. 抽象類

在Java中，類的成員方法用來完成類的成員變量的運算處理，因此通常擁有明確的可執(zhí)行的語句代碼，例如Circle類的getPrimeter()方法擁有“return Math.PI*radius*2; ”語句。但是，當類表達的是抽象概念（例如幾種圖形）時，其運算處理往往也是抽象的，此時只能定義方法的格式，而無法寫出語句代碼。

例如，針對幾何圖形Shape類及其周長計算，可使用以下代碼進行描述。

public abstract class Shape {
        public abstract double getPerimeter ( );
}

在Java中，抽象類及其抽象成員方法必須使用abstract來修飾。抽象方法不能有方法體。抽象類不能被實例化，無法使用new關鍵字來創(chuàng)建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;
        }
}

可見，抽象類的子類必須實現(xiàn)抽象類的抽象成員方法。

同樣，三角形類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變量調(diào)用getPerimeter()方法，無需強制類型轉(zhuǎn)換為其子類型。

4. 泛型類

顧名思義，泛型就是一種包含了要運算處理的數(shù)據(jù)的類型尚不明確而臨時使用類型參數(shù)（如K）來表示的一種自定義數(shù)據(jù)類型。

例如，映射Map類就是典型的泛型類，代碼如下：

public class Map<K, V>{               //指定類型參數(shù)
   K k;                               //使用類型參數(shù)定義成員變量
   V v;
   public void set(K key, V value){     //使用類型參數(shù)定義成員方法
      k=key;
      v= value;
}
   public V get(){
      return v;
}
}

其中，Map類包含了兩個類型參數(shù)K和V，K表示鍵的類型，V表示值的類型，Map類實現(xiàn)由鍵向值的映射和轉(zhuǎn)換。

注意，泛型類在使用時必須明確指定各類型參數(shù)對應的實際數(shù)據(jù)類型，Java編譯器在編譯代碼時將根據(jù)所指定的實際數(shù)據(jù)類型自動替換對應的類型參數(shù)。

例如：

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，可實現(xiàn)英文單詞“China”向中文詞匯“中國”的轉(zhuǎn)換。第4行構造了一個鍵為Integer型、值為String型的對象b，可實現(xiàn)十進數(shù)21向二進制10101的轉(zhuǎn)換。

1.3.2 面向?qū)ο蟮某橄髷?shù)據(jù)類型

數(shù)據(jù)結(jié)構研究的是數(shù)據(jù)對象內(nèi)部各數(shù)據(jù)元素之間邏輯關系問題，它不關心數(shù)據(jù)的具體類型，因此數(shù)據(jù)結(jié)構本身就是一種抽象概念。為了弄清楚針對特定數(shù)據(jù)結(jié)構計算機能進行何種操作，就必須把數(shù)據(jù)結(jié)構中的數(shù)據(jù)對象、數(shù)據(jù)關系和基本操作看作一個整體進行定義，從而得到抽象數(shù)據(jù)類型（Abstract Data Type）。

在傳統(tǒng)的數(shù)據(jù)結(jié)構教材中，抽象數(shù)據(jù)類型通常表示為｛D，S，P｝集合。

ADT抽象數(shù)據(jù)類型名
{
        數(shù)據(jù)對象D：<數(shù)據(jù)對象的定義>
        數(shù)據(jù)關系S：<數(shù)據(jù)關系的定義>
        基本操作P：<基本操作的定義>
} ADT抽象數(shù)據(jù)類型名

其中，數(shù)據(jù)對象D的定義是在已有數(shù)據(jù)類型的基礎之上對新的數(shù)據(jù)對象的定義，以明確其數(shù)據(jù)元素組成；數(shù)據(jù)關系S的定義描述了數(shù)據(jù)元素之間的邏輯結(jié)構；基本操作P的定義包括操作名稱、參數(shù)列表、初始條件和操作結(jié)果四部分內(nèi)容的定義和描述。數(shù)據(jù)對象和數(shù)據(jù)關系的定義可采用數(shù)據(jù)符號或自然語言進行描述?；静僮鞯亩x格式為：

   <操作名稱>([參數(shù)列表]);   //前提條件與操作結(jié)果描述

例如，一個集合的抽象數(shù)據(jù)類型可定義如下：

ADT Set
{
數(shù)據(jù)元素：ai∈同一數(shù)據(jù)對象，i=1，2，...，n（n≥0）
邏輯結(jié)構：<ai,ai-1>| i=1，2，...，n（n≥0）,a1無前驅(qū)，an無后繼
基本操作：InitSet( );        //建立一個空的集合
Length( );              //求集合的長度
Insert( i,x);           //向集合中插入一個新元素x
Delete( i);             //刪除集合中的第i個元素
......                  //設計者可以根據(jù)實際需要添加必要的操作
}ADT Set

正如前文中的Circle類是對所有圓的抽象，Shape類是對所有幾何圖形的抽象一樣，Java面向?qū)ο笏枷氲某橄笮耘c數(shù)據(jù)結(jié)構中的抽象數(shù)據(jù)類型的抽象性在目標上是相同的。因此，我們也可以使用Java的抽象類、泛型類或接口來表示數(shù)據(jù)結(jié)構中的抽象數(shù)據(jù)類型，從而實現(xiàn)面向?qū)ο蟮某橄髷?shù)據(jù)類型表示。

用Java泛型類表示的抽象數(shù)據(jù)類型的格式如下。

//數(shù)據(jù)關系的定義
[訪問修改符] class抽象數(shù)據(jù)類型名<類型參數(shù)列表>
{
        [訪問修改符] 數(shù)據(jù)類型 數(shù)據(jù)對象; //數(shù)據(jù)對象的定義
        [訪問修改符] 返回值類型 基本操作1(參數(shù)列表){
             //基本操作1的定義
        }
        //其他基本操作
}

例如，一個字典的抽象數(shù)據(jù)類型可定義如下：

//數(shù)據(jù)關系的定義：詞典是若干個原文詞匯及對應的譯文詞匯所構成的集合
public class Dictionary<K,V> {
        //數(shù)據(jù)對象的定義：詞典由原文詞匯表和譯文詞匯表組成
        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語言描述數(shù)據(jù)結(jié)構的優(yōu)勢

1. 使用Java描述數(shù)據(jù)結(jié)構更加簡單

Java語言是一種完全面向?qū)ο蟮某绦蛟O計語言，支持使用對象、類、繼承、封裝、消息等基本概念來進行程序設計。在Java中，使用類時必須先聲明變量名（也稱對象名），然后實例化，再引用類的成員。其中，實例化的本質(zhì)是為對象分配足夠的內(nèi)存空間，以保存各數(shù)據(jù)成員的值。對象名代表對象的引用，可理解為對象所擁有的內(nèi)存空間的首地址。因此，Java語言不使用指針就可以描述數(shù)據(jù)結(jié)構的前驅(qū)后繼關系。

Java提供了自動的垃圾回收機制，在實現(xiàn)復雜的數(shù)據(jù)結(jié)構運算處理時程序員不必為內(nèi)存管理而擔憂。因此Java語言使用時簡單、方便。

2. Java的泛型機制更加適合數(shù)據(jù)結(jié)構的抽象表示

Java的泛型類定義了一個代碼模板，專門針對暫時不確定的數(shù)據(jù)類型進行抽象描述和定義。因此，相對抽象數(shù)據(jù)類型的傳統(tǒng)表示方法，Java的泛型類將更加直觀和方便。

例如，在不使用泛型機制描述集合時，必須指定集合元素的數(shù)據(jù)類型，代碼如下。

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
                          ......//具體實現(xiàn)此處省略
        }
        public boolean Delete( i) {    //刪除集合中的第i個元素
                          ......// 具體實現(xiàn)此處省略
        }
}

上述代碼定義了一個整數(shù)集合。但在實際應用中集合的數(shù)據(jù)元素可以是整數(shù)，也可以是字符、浮點數(shù)或者更復雜的數(shù)據(jù)。若不借助泛型機制，此時必須反復書寫相似的代碼，以定義各種集合。此時，工作量將成倍地增加。同時，相似的代碼在編輯時極易出錯。若使用泛型機制，則只需引入一個類型參數(shù)T來表示集合元素的數(shù)據(jù)類型即可完成泛型集合的定義，之后就可以該泛型集合來創(chuàng)建各種類型的集合對象。代碼如下所示。

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數(shù)組，再強制轉(zhuǎn)換類型
        }
        public int Length( ) {   //求集合的長度
                 return length;
        }
        public boolean Insert(T x) {   //向集合中插入一個新元素x
                 ......//具體實現(xiàn)此處省略
        }
        public boolean Delete(int i) {    //刪除集合中的第i個元素 
                 ......//具體實現(xiàn)此處省略
        }
}

其中，突出顯示的是需要重點關注的代碼，其中T僅僅是一個合法的標識符，在使用Set時必須用實際的數(shù)據(jù)類型來替換T。

例如：

   Set< Integer >  a= new Set< Integer >;

編譯器在遇到Set< Integer >時會自動用Integer替換原代碼中的T，即集合中的數(shù)據(jù)元素最終為Integer類型。

以此類推，也可以把T綁定為charcter或者其他任意類型。

【注意】Java泛型類在描述抽象數(shù)據(jù)類型時更加直觀和方便，因此本書在后文將主要使用泛型類來定義各種數(shù)據(jù)結(jié)構。

3. java.util提供多種數(shù)據(jù)結(jié)構，可以加速應用系統(tǒng)開發(fā)

在java.util包中，Java提供了多種數(shù)據(jù)結(jié)構，包括ArrayList、Hashtable、LinkedList、Map、Queue、Set、Stack、TreeSet、Vector等，這些數(shù)據(jù)結(jié)構在Java程序中可直接使用，而不需要用戶自己編程實現(xiàn)，這樣可大大加快應用系統(tǒng)的開發(fā)速度。

例如：

  java.util.Stack s=new java.util.Stack();                 //創(chuàng)建堆棧對象s
  s.push("中國");                                         //將數(shù)據(jù)壓入對象
  s.push("四川");
  while(!s.empty())                                     //測試堆棧是否為空
    System.out.print(s.pop()+" ");              //將數(shù)據(jù)從堆棧中彈出
  System.out.println();

堆棧操作的基本規(guī)則是“先進后出”，因此上述代碼最終輸出結(jié)果為“四川 中國”。

看到這里，有讀者會說“既然Java已經(jīng)實現(xiàn)了各種數(shù)據(jù)結(jié)構，我們?yōu)槭裁催€要學習數(shù)據(jù)結(jié)構呢？”是的，Java API確實提供了多種數(shù)據(jù)結(jié)構，但這些數(shù)據(jù)結(jié)構往往只滿足通用的功能需求，在實際應用中通常需要自定義數(shù)據(jù)結(jié)構，以提供特殊數(shù)據(jù)運算處理。此外，數(shù)據(jù)結(jié)構這門課是提升編程能力的最給力的課程，因此作為剛涉足程序設計的在校學生來說，除了要了解各種數(shù)據(jù)結(jié)構的概念之外，最重要的是要理解各種數(shù)據(jù)結(jié)構的操作算法并提高實際編程能力。