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

lihjlihj

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

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

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

第一講   線性表

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

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

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

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

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

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

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

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

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

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

  

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();// 獲取當(dāng)前集合的大小

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

}

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

線性表包括順序表和鏈?zhǔn)奖恚紫戎v一下順序表，順序表顧名思義，就是數(shù)據(jù)元素按一定組合在一起的，邏輯上相鄰的元素在物理儲(chǔ)存上也是相鄰的，如下如示例：

A0

A1

A2

A3

A4

A5

……

0       1          2         3        4         5                 maxSize-1

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

  

public class SeqList implements List {

  

       /**

        * @author 天意

        */

       final int defaultSize=10;// 默認(rèn)為 10 個(gè)，你可以自己隨便改

       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 對(duì)象

     if(size==maxsize){

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

     }

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

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

     }

     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ù)錯(cuò)誤！ ");

              }

              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ù)錯(cuò)誤！ ");

              }

              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;

       }

  

}

，以上就可以實(shí)現(xiàn)順序表的所有操作了，你可以自己試一下，這里要說明的是，因?yàn)轫樞虮碇袃?chǔ)存的對(duì)象類型可以任意，所以設(shè)計(jì)時(shí)一定要使用 Object 類，當(dāng)然有時(shí)為了限定具體類型你可以重寫這個(gè)類然后拋出相應(yīng)的異常即可，這個(gè)順序表的效率分析工作留給大家，大家可以到論壇跟貼，下一講鏈?zhǔn)奖?/font>！

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

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


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

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