【聲明】

歡迎轉載，但請保留文章原始出處→_→

生命壹號：http://m.survivalescaperooms.com/smyhvae/

文章來源：http://m.survivalescaperooms.com/smyhvae/p/4758808.html

聯系方式：smyhvae@163.com

【正文】

本節內容：

• 線性結構
• 線性表抽象數據類型
• 順序表
• 順序表應用

一、線性結構：

如果一個數據元素序列滿足：

（1）除第一個和最后一個數據元素外，每個數據元素只有一個前驅數據元素和一個后繼數據元素；

（2）第一個數據元素沒有前驅數據元素；

（3）最后一個數據元素沒有后繼數據元素。

則稱這樣的數據結構為線性結構。

二、線性表抽象數據類型：

1、線性表抽象數據類型的概念：

線性表抽象數據類型主要包括兩個方面：既數據集合和該數據集合上的操作集合。

數據集合：

　　可以表示為a0,a1,a2,...an-1,每個數據元素的數據類型可以是任意的類型。

操作集合包括如下：

1.求元素個數

2.插入

3.刪除

4.查找

5.判斷是否為空

2、設計線性表抽象數據類型的Java接口：

代碼如下：

//線性表接口public interface List {    //獲得線性表長度    public int size();    //判斷線性表是否為空    public boolean isEmpty();    //插入元素    public void insert(int index,Object obj) throws Exception;    //刪除元素    public void delete(int index) throws Exception;    //獲取指定位置的元素    public Object get(int index) throws Exception;}

然后我們讓子類去實現這個接口就行了。

三、順序表：（在物理存儲結構上連續，大小固定）

1、順序表的概念：

計算機有兩種基本的存儲結構（物理存儲結構）：順序結構、離散結構。使用順序結構實現的線性表稱為順序表。如下圖所示：

Java內存中，棧內存和堆內存占了很大一部分空間：棧內存的存儲是順序結構，堆內存的存儲是離散結構。

2、設計順序表類：

我們在上面第二段的List接口基礎之上，設計一個順序表：

（1）List.java:（線性表，和上面的第二段中代碼一樣）

//線性表接口public interface List {    //獲得線性表長度    public int size();    //判斷線性表是否為空    public boolean isEmpty();    //插入元素    public void insert(int index, Object obj) throws Exception;    //刪除元素    public void delete(int index) throws Exception;    //獲取指定位置的元素    public Object get(int index) throws Exception;}

（2）SequenceList.java:（核心代碼）

 1 public class SequenceList implements List { 2  3     //默認的順序表的最大長度 4     final int defaultSize = 10; 5     //最大長度 6     int maxSize; 7     //當前長度 8     int size; 9     //對象數組10     Object[] listArray;11 12 13     public SequenceList() {14         init(defaultSize);15     }16 17     public SequenceList(int size) {18         init(size);19     }20 21     //順序表的初始化方法22     PRivate void init(int size) {23         maxSize = size;24         this.size = 0;25         listArray = new Object[size];26     }27 28     @Override29     public void delete(int index) throws Exception {30         // TODO Auto-generated method stub31         if (isEmpty()) {32             throw new Exception("順序表為空，無法刪除！");33         }34         if (index < 0 || index > size - 1) {35             throw new Exception("參數錯誤！");36         }37         //移動元素38         for (int j = index; j < size - 1; j++) {39             listArray[j] = listArray[j + 1];40         }41         size--;42     }43 44     @Override45     public Object get(int index) throws Exception {46         // TODO Auto-generated method stub47         if (index < 0 || index >= size) {48             throw new Exception("參數錯誤！");49         }50         return listArray[index];51     }52 53     @Override54     public void insert(int index, Object obj) throws Exception {55         // TODO Auto-generated method stub56         //如果當前線性表已滿，那就不允許插入數據57         if (size == maxSize) {58             throw new Exception("順序表已滿，無法插入！");59         }60         //插入位置編號是否合法61         if (index < 0 || index > size) {62             throw new Exception("參數錯誤！");63         }64         //移動元素65         for (int j = size - 1; j >= index; j--) {66             listArray[j + 1] = listArray[j];67         }68 69         listArray[index] = obj;  //不管當前線性表的size是否為零，這句話都能正常執行，即都能正常插入70         size++;71 72     }73 74     @Override75     public boolean isEmpty() {76         // TODO Auto-generated method stub77         return size == 0;78     }79 80     @Override81     public int size() {82         // TODO Auto-generated method stub83         return size;84     }85 }

我們來看一下第54行的插入操作insert()方法：如果需要在index位置插入一個數據，那么index后面的元素就要整體往后移動一位。這里面需要特別注意的是：

插入操作：移動元素時，要從后往前操作，不能從前往后操作，不然元素會被覆蓋的。

刪除元素：移動元素時，要從前往后操作。

（3）測試類：

public class Test {    public static void main(String[] args) {        SequenceList list = new SequenceList(20);        try {            list.insert(0, 100);            list.insert(0, 50);            list.insert(1, 20);            for (int i = 0; i < list.size; i++) {                System.out.println("第" + i + "個數為" + list.get(i));            }        } catch (Exception e) {            e.printStackTrace();        }    }}

我們要注意插入的規則是什么，不然會覺得這個順序表打印輸出的順序很奇怪。

運行效果：

3、順序表效率分析：

• 順序表插入和刪除一個元素的時間復雜度為O(n)。
• 順序表支持隨機訪問，順序表讀取一個元素的時間復雜度為O(1)。因為我們是可以通過下標直接訪問的，所以時間復雜度是固定的，和問題規模無關。

4、順序表的優缺點：

• 順序表的優點是：支持隨機訪問；空間利用率高（連續分配，不存在空間浪費）。
• 順序表的缺點是：大小固定（一開始就要固定順序表的最大長度）；插入和刪除元素需要移動大量的數據。

5、順序表的應用：

設計一個順序表，可以保存100個學生的資料，保存以下三個學生的資料，并打印輸出。

代碼實現：

(1)List.java:

　　和上面的代碼保持不變

(2)SequenceList.java:

　　和上面的代碼保持不變

(3)Students.java:學生類

//學生類public class Students {    private String id;// 學號    private String name;// 姓名    private String gender;// 性別    private int age;// 年齡    public Students() {    }    public Students(String sid, String name, String gender, int age) {        this.id = sid;        this.name = name;        this.gender = gender;        this.age = age;    }    public String getId() {        return id;    }    public void setId(String id) {        this.id = id;    }    public String getName() {        return name;    }    public void setName(String name) {        this.name = name;    }    public String getGender() {        return gender;    }    public void setGender(String gender) {        this.gender = gender;    }    public int getAge() {        return age;    }    public void setAge(int age) {        this.age = age;    }    public String toString() {        return "學號：" + this.getId() + " 姓名：" + this.getName() + " 性別：" + this.getGender() + " 年齡:" + this.getAge();    }}

(4)Test.java:

 1 public class Test { 2  3     /** 4      * @param args 5      */ 6     public static void main(String[] args) { 7         // TODO Auto-generated method stub 8         SequenceList list = new SequenceList(100); 9 10         try {11             list.insert(list.size, new Students("S0001", "張三", "男", 18)); //第一個參數list.size代表的是：我每次都是在順序表的最后一個位置（當前線性表的長度的位置）進行插入操作。這一行里，size是等于012             list.insert(list.size, new Students("S0002", "李四", "男", 19));13             list.insert(list.size, new Students("S0003", "王五", "女", 21));14 15             for (int i = 0; i < list.size; i++) {16                 System.out.println(list.get(i));17             }18 19         } catch (Exception ex) {20             ex.printStackTrace();21         }22     }23 24 }

注意第11行的注釋：第一個參數list.size代表的是：我每次都是在順序表的最后一個位置（當前線性表的長度的位置）進行插入操作；這樣的話，遍歷時才是按照張三、李四、王五的順序進行輸出的。

運行效果：