資料結構--線性表

基本概念

線性表：有n(n>=0)個相同資料類型資料元素組成的線性結構。其實作方法見圖。

線性結構：除了第一個和最後一個資料元素，其餘各元素隻有一個前驅元素和後繼元素，第一個資料元素隻有一個後繼元素，最後一個資料元素隻有一個前驅元素。其分類見圖。

順序存儲結構：資料元素存儲在一塊連續的位址空間中，資料元素間的邏輯關系表現在連續的位址空間上，邏輯上相鄰的資料元素在實體上也相鄰。

鍊式存儲結構：存儲資料元素的空間并不連續，資料元素間的邏輯關系用指針來實作，邏輯上相鄰的資料元素在實體上不一定相鄰。

順序表：采用順序存儲結構的線性表。

連結清單：采用鍊式存儲結構的線性表。可分為：單連結清單、單循環連結清單、雙向循環連結清單。

說下第二張圖中的 堆棧和隊列：

1. 堆棧：是一種特殊的線性表，它隻允許線上性表的表頭進行删除和插入操作。
2. 隊列：也是一種特殊的線性表，它隻允許線上性表的表頭進行删除操作，而在表尾進行插入操作。

看到這裡也許有人會問，既然堆棧和隊列都是線性表，那為什麼在第二張圖把堆棧、隊列和線性表放在一個級别裡呢？這個就不要去糾結這個問題哈。線性表可以采用順序表、仿真連結清單和連結清單來實作，那麼堆棧和隊列當然也可以采用順序表、仿真連結清單和連結清單來實作。是以堆棧和隊列是與資料的存儲結構無關的資料結構。

下面說下順序表、仿真連結清單和連結清單的差別：

其實就是各自儲存資料元素間關系的方法不一樣。

1. 順序表：資料元素的關系表現在連續的位址空間上；
2. 仿真連結清單：通過儲存資料元素在數組中存放的下标來儲存資料元素間的關系；
3. 連結清單：通過儲存資料元素在記憶體中的存放位址（或者引用）來儲存資料元素間的關系。

頭結點：不存放資料元素的第一個結點；

頭指針：指向頭結點的指針。

帶頭結點與不帶頭結點的差別：

1. 帶頭結點：插入第一結點和非第一個結點時，其操作都一樣的；
2. 不帶頭結點：當插入第一個結點時，需要單獨考慮哈。删除結點時，兩者的差別與插入結點時類似。

代碼實作

結點類：

public class Node{
	private Object data;
	private Node next;
	
	//如果new時，采用 new Node(null)，則得到一個沒有存儲資料的結點，即：頭結點。
	public Node(Object data){
		this.data = data;
	}
	
	public void setData(Object data){
		this.data = data;
	}
	
	public void setNext(Next next){
		this.next = next;
	}
	
	public Object getData(){
		return this.data;
	}
	
	public Node getNext(){
		return this.next;
	}
}           

帶頭結點的單連結清單類：

public class HeadLinkList{
	private Node head;
	private int currentSize;
	
	public HeadList(){
		head = new Node(null);    //構造一個未存放資料的頭結點。
		currentSize = 1;
	}
	
	//傳回下标為 i 的那個結點的指針
	public Node index(int i){    //結點編号從0開始，頭結點下标為0；
		if(i>=0 && i< currentSize ){
			Node temp = head;
			for(int j = 0 ; j < i;j++){
				temp = temp.getNext();
			}
			return temp;
		}else{
			throw new Exception("下标超界！");
		}
	}
	
	//插入結點，使其成為第 i 個結點。
	public void insertNode(Node node,int i){  
		Node temp = index(i-1);
		node.setNext(temp.getNext());
		temp.setNext(node);
		currentSize++;
	}

	//删除編号為 i 的結點
	public void deleteNode(int i){
		Node temp = index(i-1);
		temp.setNext(temp.getNext().getNext());
	}
	
	//getter setter
}           

不帶頭結點的單連結清單類：

public class NoHeadLinkList{
	private Node head;
	private int currentSize;
	
	public HeadList(){
		head = null;
		currentSize = 0;
	}
	
	//傳回下标為 i 的那個結點的指針
	public Node index(int i){    //結點編号從0開始；
		if(i>=0 && i< currentSize ){
			Node temp = head;
			for(int j = 0 ; j < i;j++){
				temp = temp.getNext();
			}
			return temp;
		}else{
			throw new Exception("下标超界！");
		}
	}
	
	//插入結點，使其成為第 i 個結點。
	public void insertNode(Node node,int i){
		if(head == null){
			head = node;
			currentSize++;
		}else{
			Node temp = index(i-1);
			node.setNext(temp.getNext());
			temp.setNext(node);
			currentSize++;
		}
	}

	//删除編号為 i 的結點
	public void deleteNode(int i){
		if(i == 0){
			Node temp = index(0);
			head = temp.getNext();
			temp.setNext(null);
		}else{
			Node temp = index(i-1);
			temp.setNext(temp.getNext().getNext());
		}
	}
	
	//getter setter
}           

比較HeadLinkList和NoHeadLinkList這兩個類，可以發現他們在構造函數、删除結點、插入結點函數有點不一樣，其餘是一樣的。

持續更新中。。。。。