5月安卓手機(jī)好評榜：魅族20 Pro奪冠
性能榜和性價(jià)比榜之后，我們來看最后的安卓手機(jī)好評榜，數(shù)據(jù)來源安兔兔評測，收集時(shí)間2023年5月1日至5月31日，僅限國內(nèi)市場。第一名：魅族20 Pro好評率：97.50%不得不感慨魅族老品牌還
通過前面數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)知識我們知道了數(shù)據(jù)結(jié)構(gòu)的一些概念和重要性，那么本章總結(jié)下線性表相關(guān)的內(nèi)容。當(dāng)然，我用自己的理解分享給大家。
其實(shí)說實(shí)話，可能很多人依然分不清線性表，順序表，和鏈表之間的區(qū)別和聯(lián)系！
在Java中，大家都知道List接口，這就是邏輯結(jié)構(gòu)，它封裝了一個線性關(guān)系的一系列方法，用于表示和維護(hù)線性關(guān)系。而具體的實(shí)現(xiàn)其實(shí)就是跟物理結(jié)構(gòu)相關(guān)的內(nèi)容。比如順序表的內(nèi)容存儲使用數(shù)組的，然后一個get，set，add方法都要基于數(shù)組來完成,而鏈表是基于指針的，基于不同的物理結(jié)構(gòu)要根據(jù)結(jié)構(gòu)的特性維護(hù)數(shù)據(jù)的存儲和線性關(guān)系。
下面用一個圖來淺析物理結(jié)構(gòu)中順利表和鏈表之間的區(qū)別。
對于一個線性表來說，不管它的具體實(shí)現(xiàn)如何，它們的方法函數(shù)名和實(shí)現(xiàn)效果應(yīng)該一致（即使用方法相同、達(dá)成邏輯上的效果相同，差別的是實(shí)現(xiàn)方式可能針對不同的場景效率不同）。線性表的概念與Java的接口/抽象類有一些相似之處。最著名的例子就是List接口的ArrayList和LinkedList，List是一種邏輯上的結(jié)構(gòu)，表示這種結(jié)構(gòu)為線性表，而ArrayList和LinkedList更多的是一種物理結(jié)構(gòu)（數(shù)組和鏈表）。
所以基于面向?qū)ο蟮木幊趟季S，我們可以將線性表寫成一個接口，而具體實(shí)現(xiàn)的順序表和鏈表的類可以實(shí)現(xiàn)這個線性表的方法，以提高程序的可讀性。還有一點(diǎn)非常重要，初學(xué)數(shù)據(jù)結(jié)構(gòu)與算法時(shí)實(shí)現(xiàn)的線性表都是固定類型（例如int），隨著知識的進(jìn)步，我們應(yīng)當(dāng)采用泛型來實(shí)現(xiàn)更合理的方式。至于接口的具體設(shè)計(jì)如下：
public interface ListInterface<T> { void init(int initialSize); // 初始化表 int length(); boolean isEmpty(); // 是否為空 int elemIndex(T t); // 找到編號 T getElem(int index); // 根據(jù)index獲取數(shù)據(jù) void add(int index, T t) ; // 根據(jù)index插入數(shù)據(jù) void delete(int index) ; void add(T t) ; // 尾部插入 void set(int index, T t) ; String toString(); // 轉(zhuǎn)成String輸出}順序表是基于數(shù)組實(shí)現(xiàn)的，所有實(shí)現(xiàn)需要基于數(shù)組特性。對于順序表的結(jié)構(gòu)應(yīng)該有一個存儲數(shù)據(jù)的數(shù)組data和有效使用長度size.
這里為了簡單就不實(shí)現(xiàn)擴(kuò)容、異常處理相關(guān)的操作。
下面著重講解一些初學(xué)者容易混淆的概念和方法實(shí)現(xiàn)。這里把順序表比作一隊(duì)坐在板凳上的人。
(1)從后(最后一個有數(shù)據(jù)位)向前到index依次后移一位，騰出index位置的空間
(2)將待插入數(shù)據(jù)賦值到index位置上，完成插入操作
順序表很長，在靠前的地方如果插入效率比較低(插入時(shí)間復(fù)雜度為O(n))，如果頻繁的插入那么復(fù)雜度挺高的。
同理，刪除原理和插入類似，刪除index位置的操作就是從index開始(index+1)數(shù)據(jù)賦值到index位置，一直到size-1位置，具體可以看這張圖：
這里實(shí)現(xiàn)一個簡單的順序表：
public class SeqList<T> implements ListInterface<T> { private T[] array; private int size; public SeqList() { // 默認(rèn)構(gòu)造函數(shù) init(10); } @Override public void init(int initialSize) { array = (T[]) new Object[initialSize]; size = 0; } @Override public int length() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public int elemIndex(T value) { for (int i = 0; i < size; i++) { if (array[i].equals(value)) { return i; } } return -1; } @Override public T getElem(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index is out of bounds."); } return array[index]; } @Override public void add(int index, T value) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("Index is out of bounds."); } if (size == array.length) { // 如果數(shù)組已滿，擴(kuò)展數(shù)組 resizeArray(); } // 將index之后的元素后移一位 for (int i = size; i > index; i--) { array[i] = array[i - 1]; } array[index] = value; size++; } @Override public void delete(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index is out of bounds."); } // 將index之后的元素前移一位 for (int i = index; i < size - 1; i++) { array[i] = array[i + 1]; } size--; } @Override public void add(T value) { if (size == array.length) { // 如果數(shù)組已滿，擴(kuò)展數(shù)組 resizeArray(); } array[size] = value; size++; } @Override public void set(int index, T value) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index is out of bounds."); } array[index] = value; } @Override public String toString() { StringBuilder sb = new StringBuilder("["); for (int i = 0; i < size; i++) { sb.append(array[i]); if (i < size - 1) { sb.append(", "); } } sb.append("]"); return sb.toString(); } private void resizeArray() { int newCapacity = (int) (array.length * 1.5); T[] newArray = (T[]) new Object[newCapacity]; for (int i = 0; i < size; i++) { newArray[i] = array[i]; } array = newArray; }}在學(xué)習(xí)C/C++時(shí)，鏈表往往讓許多人感到復(fù)雜，其中一個主要原因可能是因?yàn)樯婕暗街羔槨１M管在Java中不直接使用指針，但我們?nèi)匀恍枰斫庵羔樀脑砗蛻?yīng)用。鏈表與順序表（數(shù)組）不同，它的結(jié)構(gòu)就像一條鏈一樣，將節(jié)點(diǎn)鏈接成一個線性結(jié)構(gòu)。在鏈表中，每個節(jié)點(diǎn)都存在于不同的內(nèi)存地址中，指針指向（鏈表存儲）了相鄰節(jié)點(diǎn)的地址，節(jié)點(diǎn)能夠通過這些指針找到下一個的節(jié)點(diǎn)形成一條鏈。
就物理存儲結(jié)構(gòu)而言，地址之間的聯(lián)系是無法更改的，相鄰地址就是相鄰。但在鏈?zhǔn)酱鎯χ校乱粋€地址是由上一個節(jié)點(diǎn)"主動記錄的"，因此可以進(jìn)行更改。這就好比親兄弟從出生就是同姓兄弟，而在我們的成長過程中，最好的朋友可能會因?yàn)殡A段性的變化而有所不同！
舉個例子，就像西天取經(jīng)的唐僧、悟空、八戒、沙和尚。他們本來沒有直接的聯(lián)系，但通過結(jié)拜為師徒兄弟，他們建立了聯(lián)系。如果你問悟空他的師父是誰，他會立刻想到唐僧，因?yàn)樗麄冎g有五指山下的約定。
對于線性表，我們只需要一個data數(shù)組和size就能表示基本信息。而對于鏈表，我們需要一個Node類節(jié)點(diǎn)(head頭節(jié)點(diǎn))，和size分別表示存儲的節(jié)點(diǎn)數(shù)據(jù)和鏈表長度，這個節(jié)點(diǎn)有數(shù)據(jù)域和指針域。數(shù)據(jù)域就是存放真實(shí)的數(shù)據(jù)，而指針域就是存放下一個Node類節(jié)點(diǎn)的指針，其具體結(jié)構(gòu)為：
private static class Node<T> { T data; Node<T> next; Node(T data) { this.data = data; this.next = null; } }有許多人可能會對帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)鏈表的區(qū)別感到困惑，甚至不清楚什么是帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)。我來為大家闡述一下：
帶頭結(jié)點(diǎn)：在帶頭結(jié)點(diǎn)的鏈表中，head指針始終指向一個節(jié)點(diǎn)，這個節(jié)點(diǎn)不存儲有效值，僅僅起到一個標(biāo)識作用（有點(diǎn)像班主任帶著學(xué)生）。
不帶頭結(jié)點(diǎn)：在不帶頭結(jié)點(diǎn)的鏈表中，head指針始終指向第一個有效節(jié)點(diǎn)，這個節(jié)點(diǎn)存儲有效數(shù)值。
那么帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)的鏈表有什么區(qū)別呢？
查找方面：在查找操作上，它們沒有太大區(qū)別，帶頭結(jié)點(diǎn)需要多進(jìn)行一次查找。
插入方面：對于非第0個位置的插入操作，區(qū)別不大，但不帶頭結(jié)點(diǎn)的鏈表在插入第0號位置之后需要重新改變head頭指針的指向。
刪除方面：對于非第0個位置的刪除操作，區(qū)別不大，不帶頭結(jié)點(diǎn)的鏈表在刪除第0號位置之后需要重新改變head頭指針的指向。
總而言之：帶頭結(jié)點(diǎn)通過一個固定的頭可以使鏈表中任意一個節(jié)點(diǎn)都同等的插入、刪除。而不帶頭結(jié)點(diǎn)的鏈表在插入、刪除第0號位置時(shí)候需要特殊處理，最后還要改變head指向。兩者區(qū)別就是插入刪除首位(尤其插入)，個人建議以后在使用鏈表時(shí)候盡量用帶頭結(jié)點(diǎn)的鏈表避免不必要的麻煩。
基本上是個鏈表都是要有頭指針的，那么頭尾指針是個啥呢？
頭指針： 其實(shí)頭指針就是鏈表中head節(jié)點(diǎn)，表示鏈表的頭，稱為為頭指針。
尾指針： 尾指針就是多一個tail節(jié)點(diǎn)的鏈表，尾指針的好處就是進(jìn)行尾插入的時(shí)候可以直接插在尾指針的后面。
但是帶尾指針的單鏈表如果刪除尾的話效率不高，需要枚舉整個鏈表找到tail前面的那個節(jié)點(diǎn)進(jìn)行刪除。
add(int index,T value) 其中index為插入的編號位置，value為插入的數(shù)據(jù)，在帶頭結(jié)點(diǎn)的鏈表中插入那么操作流程為
當(dāng)然，很多時(shí)候鏈表需要插入在尾部，如果頻繁的插入在尾部每次枚舉到尾部的話效率可能比較低，可能會借助一個尾指針去實(shí)現(xiàn)尾部插入。
按照index移除(主要掌握)：delete(int index)
帶頭結(jié)點(diǎn)鏈表的通用方法(刪除尾也一樣)，找到該index的前一個節(jié)點(diǎn)pre，pre.next=pre.next.next
在這里我也實(shí)現(xiàn)一個單鏈表給大家作為參考使用：
public class LinkedList<T> implements ListInterface<T> { private Node<T> head; private int size; public LinkedList() { head = new Node<>(null); // 頭結(jié)點(diǎn)不存儲數(shù)據(jù) size = 0; } @Override public void init(int initialSize) { head.next = null; size = 0; } @Override public int length() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public int elemIndex(T value) { Node<T> current = head.next; int index = 0; while (current != null) { if (current.data.equals(value)) { return index; } current = current.next; index++; } return -1; } @Override public T getElem(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index is out of bounds."); } Node<T> current = head.next; for (int i = 0; i < index; i++) { current = current.next; } return current.data; } @Override public void add(int index, T value) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("Index is out of bounds."); } Node<T> newNode = new Node<>(value); Node<T> pre = head; for (int i = 0; i < index; i++) { pre = pre.next; } newNode.next = pre.next; pre.next = newNode; size++; } @Override public void delete(int index) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index is out of bounds."); } Node<T> pre = head; for (int i = 0; i < index; i++) { pre = pre.next; } pre.next = pre.next.next; size--; } @Override public void add(T value) { add(size, value); // 在末尾添加元素 } @Override public void set(int index, T value) { if (index < 0 || index >= size) { throw new IndexOutOfBoundsException("Index is out of bounds."); } Node<T> current = head.next; for (int i = 0; i < index; i++) { current = current.next; } current.data = value; } @Override public String toString() { StringBuilder sb = new StringBuilder("["); Node<T> current = head.next; while (current != null) { sb.append(current.data); if (current.next != null) { sb.append(", "); } current = current.next; } sb.append("]"); return sb.toString(); } private static class Node<T> { T data; Node<T> next; Node(T data) { this.data = data; this.next = null; } } public static void main(String[] args) { LinkedList<Integer> list = new LinkedList<>(); list.init(10); // 初始化表 list.add(1); list.add(2); list.add(3); list.add(1, 4); // 在索引1處插入值4 list.delete(2); // 刪除索引2處的值 System.out.println(list.toString()); // 打印表的內(nèi)容 }}這里的只是簡單實(shí)現(xiàn)，實(shí)現(xiàn)基本方法。鏈表也只是單鏈表。完善程度還可以優(yōu)化。
單鏈表查詢速度較慢，因?yàn)樗枰獜念^遍歷，如果在尾部插入，可以考慮設(shè)計(jì)帶尾指針的鏈表。而順序表查詢速度雖然快但是插入很費(fèi)時(shí)，實(shí)際應(yīng)用根據(jù)需求選擇！
Java中的Arraylist和LinkedList就是兩種方式的代表，不過LinkedList使用雙向鏈表優(yōu)化，并且JDK也做了大量優(yōu)化。所以大家不用造輪子，可以直接用，但是手寫順序表、單鏈表還是很有學(xué)習(xí)價(jià)值的。
本文鏈接：http://www.www897cc.com/showinfo-26-17177-0.html數(shù)據(jù)結(jié)構(gòu)與算法—線性表
聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。郵件：2376512515@qq.com
上一篇： 如何成為前1%的程序員
Copyright ? 2016-2023 天津谷騏科技有限公司 版權(quán)所有 sitemap.xml
違法及侵權(quán)請聯(lián)系：2376512515@qq.com 津ICP備18001702號
津公網(wǎng)安備 12010102000574號