考研論壇
標題: [轉載]數據結構系列教程（一） [打印本頁]
作者: lihjlihj 時間: 2006-10-8 21:17
標題: [轉載]數據結構系列教程（一）
[轉載]數據結構系列教程（一）
數據結構系列教程（一）
接觸不少程序員，都能夠獨立的作一下小型應用系統，和他們交談起來才發現，他們純粹是程序員，對基礎的掌握太差，比喻 java 程序員，就是對 jdk 和各種框架特別的熟悉，能夠熟練的運用其中的各種包、類以及一些組件，確實能做出一下系統來，但是涉及到一些特殊的設計方法來就不行了，對基礎掌握太差，包括現在的很多培訓，都是灌輸這些所謂的實際應用的東西，學好基礎才是最關鍵的東西，學一門語言很快，沒有很好的基礎、清晰的思路只能照葫蘆畫瓢了，為此，筆者結合自己的學習經驗寫了系列教程，主要包括數據結構的全部內容：線性表、樹、圖、數組、集合、矩陣、排序、查找、哈希表，并將 java 的設計思想、方法及一些常見的算法、設計模式貫穿其中，希望能給初學者一個很好的幫助，由于本人水平有限，同時請大家給與批評指正！
第一講 線性表
數據結構包括數據的邏輯結構、儲存結構以及對數據的操作，線性表的含義就是：除了第一個和最后一個數據元素，其他的只有一個前驅元素和一個后繼元素，如下圖：
A--->B--->C--->D
這個就是一個最簡單的線性表的實例，結合定義可以很好的理解的，數據結構中最常見的就是提到抽象數據類型，所謂抽象數據類型就是在基本數據類型支持下用戶新設計的數據類型，通俗的說就是用戶對基本數據類型（整型、浮點型等等）的組合應用成自己的一種新型的數據類型，也就是 java 中接口和抽象類，這么說可能有些不妥，不過這樣最好理解，前面講到數據結構包括對數據的操作，這個設計數據結構的最終目的，下面我們就講講 java 數據結構中的線性表的設計思想。
由于線性表的數據集合可以表示為序列： A1,A2,A3……….An-1, 每個元素的類型都是任意的，對于這個集合的操作可以歸結如下：
(1) 求出當前集合中數據元素個數（ size ） ;
(2) 向當前數據集合任意位置插入新的數據 (insert);
(3) 刪除當前數據集合中的任意數據 (delete);
(4) 獲取當前數據集合中的任意數據 (getData);
(5) 判斷當前數據集合是否為空 ;
，由于存在很多不同形式的線性表結構，對其操作方式當然也不一樣，這樣就要求設計一個大家都能使用的數據類型，由前面的講述大家就可以想到必須要設計一個抽象數據類型，也就是一個接口，這時可能有人問為什么不設計一個抽象類阿？這個問題留個大家思考，可以到論壇發表。 Java 中可以這樣定義這個接口：
public interface List {
/**
* @author 天意
*/
public void insert(int i,Object obj ) throws Exception;// 在任意位置插入數據
public Object delete(int i) throws Exception;// 刪除任意位置的數據
public Object getData(int i) throws Exception;// 獲取任意位置的數據
public int size();// 獲取當前集合的大小
public boolean isEmpty();// 判斷當前集合是否為空
}
，由于所有線性表的操作都是圍繞以上而來的，所以上面的接口就可以通用于所有線性表了，這就告訴大家在設計程序時要做好充分的考慮，強調一個“廣”字。
線性表包括順序表和鏈式表，首先講一下順序表，順序表顧名思義，就是數據元素按一定組合在一起的，邏輯上相鄰的元素在物理儲存上也是相鄰的，如下如示例：
0 1 2 3 4 5 maxSize-1
結合這個圖我們可以想到：首先建立這個表就必須有個初始大小，然后才能對他就行實際操作，插入操作時可能會出現表已滿、插入位置不存在的情況，刪除時可能出現表已空、刪除的元素不存在的情況，獲取時可能出現要求的元素不存在的情況，考慮這些因素就可以設計這個順序表的操作類了 SeqList.java ，具體內容如下：
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(" 參數錯誤 ");
}
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(" 參數錯誤！ ");
}
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(" 參數錯誤！ ");
}
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;
}
}
，以上就可以實現順序表的所有操作了，你可以自己試一下，這里要說明的是，因為順序表中儲存的對象類型可以任意，所以設計時一定要使用 Object 類，當然有時為了限定具體類型你可以重寫這個類然后拋出相應的異常即可，這個順序表的效率分析工作留給大家，大家可以到論壇跟貼，下一講鏈式表！
(注：本文作者,EasyJF開源團隊 天意，轉載請保留作者聲明！)
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 編輯 ]
| 歡迎光臨 考研論壇 (http://www.0313v.com/) |
Powered by Discuz! X3.2 |