數據結構與算法—線性表詳解
- 2019 年 10 月 3 日
- 筆記
前言
-
通過前面數據結構與算法前導我么知道了數據結構的一些概念和重要性，那麼我們今天總結下線性表相關的內容。當然，我用
自己的理解解分享給大家。 -
其實說實話，可能很多人依然分不清
線性表，順序表，和鏈表之間的區別和聯繫！- 線性表：
邏輯結構， 就是對外暴露數據之間的關係，不關心底層如何實現。 - 順序表、鏈表：
物理結構，他是實現一個結構實際物理地址上的結構。比如順序表就是用數組實現。而鏈表用指針完成主要工作。不同的結構在不同的場景有不同的區別。
- 線性表：
-
對於java來說，大家都知道
List接口類型，這就是邏輯結構，因為他就是封裝了一個線性關係的一系列方法和數據。而具體的實現其實就是跟物理結構相關的內容。比如順序表的內容存儲使用數組的，然後一個get，set，add方法都要基於數組來完成,而鏈表是基於指針的。當我們考慮對象中的數據關係就要考慮指針的屬性。指針的指向和value。
下面用一個圖來淺析線性表的關係。可能有些不太確切，但是其中可以參考，並且後面也會根據這個圖舉例。
線性表基本架構
- 對於一個
線性表來說。不管它的具體實現方法如何，我們應該有的函數名稱和實現效果應該一致。你也可以感覺的到在一些結構的設計。比如List的Arraylist和LinkedList。Map的HashMap和currentHashMap他們的接口api都是相同的，但是底層設計實現肯定是有區別的。 - 所以，基於面向對象的編程思維，我們可以將線性表寫成一個接口，而具體實現的順序表和鏈表可以
繼承這個接口的方法，提高程序的可讀性。 - 還有一點比較重要的，記得初學數據結構與算法時候實現的線性表都是
固定類型(int),隨着知識的進步，我們應當採用泛型來實現更合理。至於接口的具體設計如下：
package LinerList; public interface ListInterface<T> { void Init(int initsize);//初始化表 int length(); boolean isEmpty();//是否為空 int ElemIndex(T t);//找到編號 T getElem(int index) throws Exception;//根據index獲取數據 void add(int index,T t) throws Exception;//根據index插入數據 void delete(int index) throws Exception; void add(T t) throws Exception;//尾部插入 void set(int index,T t) throws Exception; String toString();//轉成String輸出 } 順序表
- 順序表是基於數組實現的，所以一些方法要基於數組的特性。對於順序表應該有的基礎屬性為一個
數組data和一個length. - 還有需要注意的是初始化數組的大小，你可以
固定大小，但是筆者為了可用性如果內存不夠將擴大二倍。當然這樣很可能因為空間使用問題造成很大的浪費。 - 一些基本的額方法就不說了，下面着重講解一些初學者容易混淆的概念和方法實現。這裡把順序表比作一隊坐在板凳上的人。
插入
add(int index,T t)
- 其中index為插入的編號位置，t為插入的數據
- 根據圖片你就很好理解插入操作。當插入一個index時候，他的後面所有元素都要後移一位。你可以看的出插入時候整個操作的臃腫性。所以這也是順序表
性能表現最差的地方,頻繁的插入，刪除。
刪除
- 同理，刪除也是非常佔用資源的。原理和插入類似，不過人走了，
空一個小板凳後面的人需要往前挪。
其他操作
- 其他操作就很簡單了。比如如果按照編號獲取數據
getElem(int index)，你可以直接根據數據坐標返回。a[index]，而其他操作，可以通過遍歷直接操作數組即可。
鏈表
- 我想，表應該是很多人感覺很繞的東西，這個很大原因可能因為
指針。很多人說java沒指針，其實java他也有隱形指針。只不過不能直接用罷了。 - 指針建立的數據關係往往比數組這些要抽象的多。對於指針域，你把他當成一個對象就好了，不過這個對象指向的是
另一個同等級對象。對於這個關係，你可以比作每個person類。每個person類都有老公(老婆),而這個老公老婆也是一個實際對象，可以理解這更像一種邏輯約定關係，而不是硬生生的關係吧。 - 指針你可以考慮成
腦子記憶。上面的順序表我們說它有序因為每個小板凳(數組)有編號，我們可以根據這個來確定位置。而對於鏈表來說，你可以看作成一個站在操場上的一隊人。而他的操作也略有不同，下面針對一些比較特殊和重要的進行歸納。
基本結構
對於線性表，我們只需要一個data數組和length就能表示基本信息。而對於鏈表，我們需要一個node(head頭節點)，和length,當然，這個node也是一個結構體。
class node<T>{ T data;//節點的結果 node next;//下一個連接的節點 public node(){} public node(T data) { this.data=data; } public node(T data, node next) { this.data = data; this.next = next; } } 當然，這個節點有數據域和指針域。數據域就是存放真實的數據，而指針域就是存放下一個node的指針。所以相比順序表，如果用滿數組情況下，鏈表佔用更多的資源，因為它要存放指針佔用資源。
插入
add(int index,T t) 其中index為插入的編號位置，t為插入的數據 加入插入一個節點node，根據index找到插入的前一個節點叫pre。那麼操作流程為
node.next=pre.next如下1的操作，將插入節點後面聯繫起來。此時node.next和pre.next一致。pre.next=node因為我們要插入node，而node鏈可以替代pre自身的next。那麼直接將pre指向node。那麼就相當於原始鏈表插入了一個node。
帶頭節點與不帶頭節點
很多人搞不清什麼是
帶頭節點和不帶頭節點。帶頭節點就是head節點不放數據，第0項從head後面那個開始數。而不帶頭節點的鏈表head放數據，head節點就是第0位。 主要區別：
- 帶頭節點和不帶頭節點的主要區別就在插入刪除首位，尤其是首位插入。帶頭節點找元素需要多遍歷一次因為它的第一個head節點是頭節點，不存數據(
可看作一列火車的火車頭)。而方便的就是帶頭節點在首位插入更簡單。因為插入第0位也是在head的後面。 - 而不帶頭節點的鏈表就需要特殊考慮首位。因為插入第0位其實是插入head的前面。假設有head，插入node。具體操作為：
- node.next=head；(node指向head，node這條鏈成我們想要的鏈)
- head=node；(很多人想不明白，其實這個時候
node才是插入後最長鏈的首位節點，head在他的後面，而在鏈表中head通常表示首位節點，所以head不表示第二個節點，直接"="node節點。這樣head和node都表示操作完成的鏈表。但是對外暴露的只有head。所以head只能指向第一個節點！)
插入尾
- 而在插入尾部的時候，需要注意尾部的
next為null。不能和插入普通位置相比！
刪除
按照index移除：delete(int index)
- 找到該index的節點node。node.next=node.next.nex
按照尾部移除(拓展)：deleteEnd()
- 這個方法我沒有寫，但是我給大家講一下，按照尾部刪除的思想就是：
- 聲明一個node為head。
- 當
node.next！=null時node=node.next指向下一個 - 當
node.next==null時候。說明這個節點時最後一個。你可以node=null。這個這個node的前驅pre的next就是null。這個節點就被刪除了。
頭部刪除(帶頭節點)：
- 帶頭節點的刪除和普通刪除一直。直接
head.next(第1個元素)=head.next.next(第二個元素) - 這樣head.next就直接指向第二個元素了。第一個就被刪除了
頭部刪除(不帶頭節點)
- 我們知道不帶頭節點的
第一個就是存貨真價實的元素的。不帶頭節點刪除也很簡單。直接將head移到第二位就行了。即：head=head.next
其他
- 對於其他操作，主要時結合查找。而單鏈表的查找時
從head開始。然後另一個節點team=head或head.next。然後用這個節點不停的等於它指向的next去查找我們需要的內容即while(循環條件){team=team.next}類似。 - 不同教程和人寫的線性表也不一致，這裡只給出一個樣例學習使用而並不是標準，希望大家審視。
- 在實現上用了帶頭節點的鏈表實現，因為比較方便管理，不需要很多
if else.
代碼實現
順序表
package LinerList; public class seqlist<T> implements ListInterface<T> { private Object[] date;//數組存放數據 private int lenth; public seqlist() {//初始大小默認為10 Init(10); } public void Init(int initsize) {//初始化 this.date=new Object[initsize]; lenth=0; } public int length() { return this.lenth; } public boolean isEmpty() {//是否為空 if(this.lenth==0) return true; return false; } /* * * @param t * 返回相等結果，為-1為false */ public int ElemIndex(T t) { // TODO Auto-generated method stub for(int i=0;i<date.length;i++) { if(date[i].equals(t)) { return i; } } return -1; } /* *獲得第幾個元素 */ public T getElem(int index) throws Exception { // TODO Auto-generated method stub if(index<0||index>lenth-1) throw new Exception("數值越界"); return (T) date[index]; } public void add(T t) throws Exception {//尾部插入 add(lenth,t); } /* *根據編號插入 */ public void add(int index, T t) throws Exception { if(index<0||index>lenth) throw new Exception("數值越界"); if (lenth==date.length)//擴容 { Object newdate[]= new Object[lenth*2]; for(int i=0;i<lenth;i++) { newdate[i]=date[i]; } date=newdate; } for(int i=lenth-1;i>=index;i--)//後面元素後移動 { date[i+1]=date[i]; } date[index]=t;//插入元素 lenth++;//順序表長度+1 } public void delete(int index) throws Exception { if(index<0||index>lenth-1) throw new Exception("數值越界"); for(int i=index;i<lenth;i++)//index之後元素前移動 { date[i]=date[i+1]; } lenth--;//長度-1 } @Override public void set(int index, T t) throws Exception { if(index<0||index>lenth-1) throw new Exception("數值越界"); date[index]=t; } public String toString() { String vaString=""; for(int i=0;i<lenth;i++) { vaString+=date[i].toString()+" "; } return vaString; } }
鏈表
package LinerList; class node<T>{ T data;//節點的結果 node next;//下一個連接的節點 public node(){} public node(T data) { this.data=data; } public node(T data, node next) { this.data = data; this.next = next; } } public class Linkedlist<T> implements ListInterface<T>{ node head; private int length; public Linkedlist() { head=new node(); length=0; } public void Init(int initsize) { head.next=null; } public int length() { return this.length; } public boolean isEmpty() { if(length==0)return true; else return false; } /* * 獲取元素編號 */ public int ElemIndex(T t) { node team=head.next; int index=0; while(team.next!=null) { if(team.data.equals(t)) { return index; } index++; team=team.next; } return -1;//如果找不到 } @Override public T getElem(int index) throws Exception { node team=head.next; if(index<0||index>length-1) { throw new Exception("數值越界"); } for(int i=0;i<index;i++) { team=team.next; } return (T) team.data; } public void add(T t) throws Exception { add(length,t); } //帶頭節點的插入，第一個和最後一個一樣操作 public void add(int index, T value) throws Exception { if(index<0||index>length) { throw new Exception("數值越界"); } node<T> team=head;//team 找到當前位置node for(int i=0;i<index;i++) { team=team.next; } node<T>node =new node(value);//新建一個node node.next=team.next;//指向index前位置的下一個指針 team.next=node;//自己變成index位置 length++; } @Override public void delete(int index) throws Exception { if(index<0||index>length-1) { throw new Exception("數值越界"); } node<T> team=head;//team 找到當前位置node for(int i=0;i<index;i++)//標記team 前一個節點 { team=team.next; } //team.next節點就是我們要刪除的節點 team.next=team.next.next; length--; } @Override public void set(int index, T t) throws Exception { // TODO Auto-generated method stub if(index<0||index>length-1) { throw new Exception("數值越界"); } node<T> team=head;//team 找到當前位置node for(int i=0;i<index;i++) { team=team.next; } team.data=t;//將數值賦值，其他不變 } public String toString() { String va=""; node team=head.next; while(team!=null) { va+=team.data+" "; team=team.next; } return va; } }
測試與結果
package LinerList; public class test { public static void main(String[] args) throws Exception { // TODO Auto-generated method stub System.out.println("線性表測試："); ListInterface<Integer>list=new seqlist<Integer>(); list.add(5); list.add(6); list.add(1,8); list.add(3,996); list.add(7); System.out.println(list.ElemIndex(8)); System.out.println(list.toString()); list.set(2, 222); System.out.println(list.toString()); list.delete(4); System.out.println(list.toString()); System.out.println(list.length()); System.out.println("鏈表測試："); list=new Linkedlist<Integer>(); list.add(5); list.add(6); list.add(1,8); list.add(3,996); list.add(7); System.out.println(list.ElemIndex(8)); System.out.println(list.toString()); list.set(2, 222); System.out.println(list.toString()); list.delete(4); System.out.println(list.toString()); System.out.println(list.length()); } }
輸出:
線性表測試： 1 5 8 6 996 7 5 8 222 996 7 5 8 222 996 4 鏈表測試： 1 5 8 6 996 7 5 222 6 996 7 5 222 6 996 4 總結
- 這裡的只是簡單實現，實現基本方法。鏈表也只是單鏈表。完善程度還可以優化。如果有錯誤還請大佬指正。
- 單鏈表
查詢速度較慢，因為他需要從頭遍歷。如果頻繁操作尾部，可以考慮鏈表中不僅有head在加尾tail節點。而順序表查詢速度雖然快但是插入很費時費力。實際應用根據需求選擇！ - java中的Arraylist和LinkedList就是兩種方式的代表，不過LinkedList使用雙向鏈表優化，並且jdk的api做了大量優化。所以大家
不用造輪子，可以直接用，但是還是很有學習價值的。 - 如果有不理解或者不懂的可以聯繫交流討論。筆者敞開
自家公眾號的大門隨時歡迎受訪！下面還會持續出貨分享！ - 感覺不錯的可以點個贊，關注一波
公眾號(回復數據結構 送精心準備資料一份)：bigsai 
