線性表的論述（Java版）

1. 基礎知識摘要
- 1.1 線性表的定義：
- 1.2 前驅和后繼：
- 1.3 開始結點和終端結點：
- 1.4 特點：
- 1.5 順序存盤的線性表：
- 1.6 順序表的插入、洗掉和按值查找操作的實作方法及性能 :
- 單鏈表的圖形結構：
- - - 順序表上的插入操作 insert ( i , x )
    - 插入的圖形操作：
    - 插入Java代碼如下：
    - 順序表上的洗掉操作 remove( i )
    - 順序表上的按值查找操作 indexOf ( x )
- 1.7 回圈鏈表
- - 回圈單鏈表：
  - - 回圈單串列存在優點：
    - - 列如，現將兩個帶尾指標回圈串列this和 list 合并為 this，
- 1.8 雙向鏈表
- - 雙向鏈表的圖形結構：
  - 雙向鏈表的插入的圖形結構：

1. 基礎知識摘要

1.1 線性表的定義：

線性表是由n ( n >= 0 )個資料元素構成的有序數列，

下標 i 標識資料元素在線性表中的位序號，n為線性表的表長，當 n=0 時，此線性表時空表，

1.2 前驅和后繼：

a< i -1 >就是a < i >  的前驅，反之則為后繼，

1.3 開始結點和終端結點：

線性表中沒有前驅的資料元素稱為開始結點，沒有后繼的資料元素稱為終端結點，

1.4 特點：

資料元素具有相同的資料型別，
有且只有一個開始結點和終端結點，
除開始結點和終端結點外，其余結點有且只有一個前驅和一個后繼，

1.5 順序存盤的線性表：

順序存盤的線性表稱為順序表，它是用一組地址連續的存盤單元依次存放線性表中的各個資料元素，從而使線性表在邏輯上相鄰的資料元素，在物理存盤位置上也是相鄰的，
順序表的主要優點使存盤密度高，節省存盤空間，且讀取順序表中的資料元素非常便利，
【補充】：
存盤密度：（結點資料本身所占的存盤量）/ （結點結構所占的存盤總量）

1.6 順序表的插入、洗掉和按值查找操作的實作方法及性能 :

單鏈表的圖形結構：

在這里插入圖片描述

順序表上的插入操作 insert ( i , x )

做法：

檢查 i 的合法性，
將插入位置及其之后的所有元素后移一個存盤位置
將 x 插入到第 i 個位置
將表長值加 1

插入的圖形操作：

在這里插入圖片描述

插入Java代碼如下：

  /**
     * 在鏈表中查找恰當的位置，將結點n插入到當前鏈表中，插入后鏈表依然有序
     */
    public void Insert(Node n) {
        Node p = head;
        if (p.next == null) {  //只存在頭結點
            n.next = p.next;
            p.next = n; //插入結點
        } else {
            //假設為data為int型別
            while ((int) p.next.data <= (int) n.data) {
                if (p.next.next != null) {
                    p = p.next;
                } else {
                    n.next = p.next.next;
                    p.next.next = n; //插入結點n
                    break;
                }
            }
        }

    }