線性表
線性表是最簡單和最常用的一種數據結構，它是有n個體數據元素（節點）組成的有限序列。其中，數據元素的個數n為表的長度，當n為零時成為空表，非空的線性表通常記為：
（a1，a2，… ，ai-1，ai， ai+1，…，an）
一. 線性表的順序存儲及算法
線性表的順序存儲指的是將線性表的數據元素按其邏輯次序依次存入一組地址連續的存儲單元里，用這種方法存儲的線性表稱為順序表。
1.順序表的結構定義
public class SeqList { /* 初始空間為10 */ private static final int LIST_SIZE = 10; /* 數組data用來存放元素*/ private int[] data; /* 當前表長，實際存儲元素的個數*/ private int length; } 2.插入運算
順序表的插入運算是指在線性表的第i-1個元素和第i個元素之間插入一個新元素。由於順序表邏輯上相鄰的元素在物理結構上也相鄰，其物理存儲關係也要發生相應的變化。除非i=n+1，否則必須將原順序表的第i個元素開始的所有元素分別向後移動1個位置。
/** * 在順序表list中第i個位置之前插入一個新元素node * @param list 順序表* @param i 插入位置* @param node 新元素*/public void insertList(SeqList list, int i, int node) { if (i < 1 || i > list.length + 1) { System.out.println("position error"); return; } if (list.length >= LIST_SIZE) { System.out.println("overflow"); return; } for (int j = list.length - 1; j >= i - 1; j --) { /* 從最後一個元素開始逐一後移*/ list.data[j+1] = list.data[j]; } /* 插入新元素*/ list.data[i-1] = node; /* 表長加1 */ list.length ++; } 3.刪除運算
順序表的刪除運算指的是將表中第i個元素刪除，與插入運算相反，插入是向後移動元素，刪除運算則是向前移動元素。
/** * 在順序表list中刪除第i個元素，並返回被刪除的元素* @param list 順序表* @param i 元素位置* @return node */public int deleteList(SeqList list, int i) { int node = 0; if (i < 0 || i > list.length) { System.out.println("position error"); return node; } node = list.data[i-1]; for (int j = i; j < list.length; j ++) { /* 元素前移*/ list.data[j-1] = list.data[j]; } list.length --; return node;} 4.順序表逆置
先以表長的一半為循環控制次數，將表中最後一個元素同順序順數第一個元素交換，將倒數第二個元素同順數第二個元素交換，以此類推，直至交換完為止。
/** * 順序表逆置* @param list 原始順序表* @return 逆置後的順序表*/public SeqList converts(SeqList list) { int node; int length = list.length/2; for (int i = 0; i < length; i ++) { /* 對稱交換元素*/ int j = list.length - 1 - i; node = list.data[i]; list.data[i] = list.data[j]; list.data[j] = node; } return list; }二. 線性表的鍊式存儲及算法
鍊式存儲結構存儲線性表數據元素的存儲空間可能是連續的，也可能是不連續的，因而鍊錶的節點是不可以隨機存取的，鍊式存粗是最常見的存儲方式之一。
在使用鍊式存儲結構表示每個數據元素時，除了存儲元素本身的信息外，還需要一個存儲指示後繼元素存儲位置的地址，利用這種存儲方式表示的線性表稱為鍊錶。
5.單鍊錶的結構定義
public class LinkList { /* 數據域*/ private char data; /* 後繼元素*/ private LinkList next;} 6.頭插法建表算法
頭插法是從一個空表開始，重複讀入數據，生成新節點，將讀入的數據存放到新節點的數據域中，然後將新節點插入到當前鍊錶的表頭上，直到結束為止。
/** * 頭插法創建表* @param chars 字符數組* @return 單鍊錶*/public LinkList createListF(char[] chars) { LinkList node; LinkList head = null; for (char ch : chars) { /* 申請新節點*/ node = new LinkList(); node.data = ch; /* 指向後繼節點*/ node.next = head; head = node; } /* 返回頭節點*/ return head;} 7.尾插法建表算法
頭插法建表中節點的次序和輸入時的順序相反，若需要和輸入次序一致，則可使用尾插法。
/** * 尾插法建表* @param chars 字符數組* @return 單鍊錶*/public LinkList createListR(char[] chars) { LinkList node; LinkList head = null; LinkList rear = null; for (char ch : chars) { node = new LinkList(); node.data = ch; if (head == null) { /* 新節點為頭節點*/ head = node; } else { /* 上一個節點指向新節點*/ rear.next = node; } /* 表尾指向新的節點*/ rear = node; } /* 返回頭節點*/ return head;}以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持武林網。