[轉(zhuǎn)載]數(shù)據(jù)結(jié)構(gòu)系列教程（一）

lihjlihj

[轉(zhuǎn)載]數(shù)據(jù)結(jié)構(gòu)系列教程（一）

數(shù)據(jù)結(jié)構(gòu)系列教程（一）

　　接觸不少程序員，都能夠獨立的作一下小型應(yīng)用系統(tǒng)，和他們交談起來才發(fā)現(xiàn)，他們純粹是程序員，對基礎(chǔ)的掌握太差，比喻 java 程序員，就是對 jdk 和各種框架特別的熟悉，能夠熟練的運用其中的各種包、類以及一些組件，確實能做出一下系統(tǒng)來，但是涉及到一些特殊的設(shè)計方法來就不行了，對基礎(chǔ)掌握太差，包括現(xiàn)在的很多培訓(xùn)，都是灌輸這些所謂的實際應(yīng)用的東西，學(xué)好基礎(chǔ)才是最關(guān)鍵的東西，學(xué)一門語言很快，沒有很好的基礎(chǔ)、清晰的思路只能照葫蘆畫瓢了，為此，筆者結(jié)合自己的學(xué)習(xí)經(jīng)驗寫了系列教程，主要包括數(shù)據(jù)結(jié)構(gòu)的全部內(nèi)容：線性表、樹、圖、數(shù)組、集合、矩陣、排序、查找、哈希表，并將 java 的設(shè)計思想、方法及一些常見的算法、設(shè)計模式貫穿其中，希望能給初學(xué)者一個很好的幫助，由于本人水平有限，同時請大家給與批評指正！

第一講   線性表

   數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、儲存結(jié)構(gòu)以及對數(shù)據(jù)的操作，線性表的含義就是：除了第一個和最后一個數(shù)據(jù)元素，其他的只有一個前驅(qū)元素和一個后繼元素，如下圖：

   A--->B--->C--->D

這個就是一個最簡單的線性表的實例，結(jié)合定義可以很好的理解的，數(shù)據(jù)結(jié)構(gòu)中最常見的就是提到抽象數(shù)據(jù)類型，所謂抽象數(shù)據(jù)類型就是在基本數(shù)據(jù)類型支持下用戶新設(shè)計的數(shù)據(jù)類型，通俗的說就是用戶對基本數(shù)據(jù)類型（整型、浮點型等等）的組合應(yīng)用成自己的一種新型的數(shù)據(jù)類型，也就是 java 中接口和抽象類，這么說可能有些不妥，不過這樣最好理解，前面講到數(shù)據(jù)結(jié)構(gòu)包括對數(shù)據(jù)的操作，這個設(shè)計數(shù)據(jù)結(jié)構(gòu)的最終目的，下面我們就講講 java 數(shù)據(jù)結(jié)構(gòu)中的線性表的設(shè)計思想。

由于線性表的數(shù)據(jù)集合可以表示為序列： A1,A2,A3……….An-1, 每個元素的類型都是任意的，對于這個集合的操作可以歸結(jié)如下：

(1) 求出當前集合中數(shù)據(jù)元素個數(shù)（ size ） ;

(2) 向當前數(shù)據(jù)集合任意位置插入新的數(shù)據(jù) (insert);

(3) 刪除當前數(shù)據(jù)集合中的任意數(shù)據(jù) (delete);

(4) 獲取當前數(shù)據(jù)集合中的任意數(shù)據(jù) (getData);

(5) 判斷當前數(shù)據(jù)集合是否為空 ;

，由于存在很多不同形式的線性表結(jié)構(gòu)，對其操作方式當然也不一樣，這樣就要求設(shè)計一個大家都能使用的數(shù)據(jù)類型，由前面的講述大家就可以想到必須要設(shè)計一個抽象數(shù)據(jù)類型，也就是一個接口，這時可能有人問為什么不設(shè)計一個抽象類阿？這個問題留個大家思考，可以到論壇發(fā)表。 Java 中可以這樣定義這個接口：

  

public interface List {

/**

  * @author 天意

  */

       public void insert(int i,Object obj ) throws Exception;// 在任意位置插入數(shù)據(jù)

       public Object delete(int i) throws Exception;// 刪除任意位置的數(shù)據(jù)

       public Object getData(int i) throws Exception;// 獲取任意位置的數(shù)據(jù)

       public int size();// 獲取當前集合的大小

       public boolean isEmpty();// 判斷當前集合是否為空

}

，由于所有線性表的操作都是圍繞以上而來的，所以上面的接口就可以通用于所有線性表了，這就告訴大家在設(shè)計程序時要做好充分的考慮，強調(diào)一個“廣”字。

線性表包括順序表和鏈式表，首先講一下順序表，順序表顧名思義，就是數(shù)據(jù)元素按一定組合在一起的，邏輯上相鄰的元素在物理儲存上也是相鄰的，如下如示例：

A0

A1

A2

A3

A4

A5

……

0       1          2         3        4         5                 maxSize-1

結(jié)合這個圖我們可以想到：首先建立這個表就必須有個初始大小，然后才能對他就行實際操作，插入操作時可能會出現(xiàn)表已滿、插入位置不存在的情況，刪除時可能出現(xiàn)表已空、刪除的元素不存在的情況，獲取時可能出現(xiàn)要求的元素不存在的情況，考慮這些因素就可以設(shè)計這個順序表的操作類了 SeqList.java ，具體內(nèi)容如下：

  

public class SeqList implements List {

  

       /**

        * @author 天意

        */

       final int defaultSize=10;// 默認為 10 個，你可以自己隨便改

       int maxsize;

       int size;

       Object[] listArray;

       public SeqList(){

              initiate(defaultSize);

       }

       public SeqList(int size){

              initiate(size);

       }

       private void initiate(int sz) {

              // 初始化

              maxsize=sz;

              size=0;

              listArray=new Object[sz];

       }

       public void insert(int i, Object obj) throws Exception {

              // 在 i 位置插入 obj 對象

     if(size==maxsize){

            throw new Exception(" 順序表無法插入 ");

     }

     if (i<0||i>size){

            throw new Exception(" 參數(shù)錯誤 ");

     }

     for(int j=size;j>i;j--)

            listArray[j]=listArray[j-1];

         listArray=obj;

         size++;

       }

  

       public Object delete(int i) throws Exception {

              // 刪除 i 位置的元素

              if (size==0){

                     throw new Exception(" 順序表已空無法刪除！ ");

              }

              if(i<0||i>size-1){

                     throw new Exception(" 參數(shù)錯誤！ ");

              }

              Object it=listArray;

              for(int j=i;j<size-1;j++)

                     listArray[j]=listArray[j+1];

              size--;

              return it;

       }

  

       public Object getData(int i) throws Exception {

              // 獲取 i 位置的元素并返回

              if(i<0||i>=size){

                     throw new Exception(" 參數(shù)錯誤！ ");

              }

              return listArray;

              }

  

       public int size() {

              // 獲得大小

              return size;

       }

  

       public boolean isEmpty() {

              // 判斷是否為空

              return size==0;

       }

       public int MoreDataDelete(SeqList L,Object x)throws Exception{

              int i;

              int tag=0;

              for( i=0;i<L.size;i++){

                     if(x.equals(L.getData(i))){

                            L.delete(i);

                            i--;

                            tag=1;

                     }

                     

              }

              return tag;

       }

  

}

，以上就可以實現(xiàn)順序表的所有操作了，你可以自己試一下，這里要說明的是，因為順序表中儲存的對象類型可以任意，所以設(shè)計時一定要使用 Object 類，當然有時為了限定具體類型你可以重寫這個類然后拋出相應(yīng)的異常即可，這個順序表的效率分析工作留給大家，大家可以到論壇跟貼，下一講鏈式表！

(注：本文作者,EasyJF開源團隊　天意，轉(zhuǎn)載請保留作者聲明！)

posted on 2006-08-15 14:57 簡易java框架 閱讀(3497) 評論(18)  編輯 收藏 收藏至365Key


原文地址:http://www.blogjava.net/easyjf/archive/2006/08/15/63680.aspx

[ 本帖最后由 lihjlihj 于 2006-10-8 21:30 編輯 ]