目錄

順序表的順序存儲結構

1.數組

2.順序表

順序表的聲明，存儲操作以及效率分析

1.泛型類

2.順序表的插入操作

3. 順序表的刪除操作?

?4.順序表查詢操作

5.順序表的應用

線性表的鏈式存儲結構?

單鏈表的基本操作

---

?

順序表的順序存儲結構

數組是實現順序存儲結構的基礎

1.數組

程序設計語言中，數組（Array）具有相同數據類型，是一個構造數據類型。

一維數組占用一塊內存空間，每個存儲單元的地址是連續的，數據的存儲單位個數稱為數組容量。設數組變量為a，第i個元素（存儲單元）為a[i],其中序號i稱為下標，一維數組使用一個下標唯一確定一個元素。

如果數據存儲結構存取任何一個元素的時間復雜度是O(1)，則稱其為隨機存儲結構。因此，數組是隨機存儲結構。

數組一旦占用一片存儲空間，其地址和容量就是確定的，不能更改。因此，數組只能進行賦值，取值兩種操作，不能進行插入和刪除操作。當數組容量不夠時，不能就地擴容。

2.順序表

線性表的順序存儲結構稱為順序表，它使用一維數組一次存放線性表的數據，且順序表的性質和數組是一樣的，因為順序表的底層就是用數組來實現的。

順序表的表現特點：

1. 隨機訪問，可以在O(1)時間內找到第i個元素
2. 存儲密度高，每個節點只存儲數據元素
3. 擴展容量不方便（即便采用動態分配的方式實現，擴展長度的時間復雜度也比較高）
4. 插入和刪除操作不方便，需要移動大量元素

順序表的聲明，存儲操作以及效率分析

1.泛型類

聲明SeqList<T>為泛型類，類型形式參數稱為泛型，T表示順序表數據元素的數據類型。

JAVA語言約定。泛型<T>的實際參數必須是類，不能是int，char等基本數據類型。如果需要表示基本數據類型，也必須采用基本數據類型的包裝類，如Integer，Character等等。

2.順序表的插入操作

public class SequentialList{private int[] array;//用于順序表的數組private int size;//順序表的實際長度public SequentialList(int capacity){array =new int[capacity];size=0;}//插入操作public boolean insert(int index,int element){//檢查索引是否合法if (index<0||index>size){System.out.println("插入的位置不合法");return false;}//如果數組已滿，則無法插入if (size==array.length){System.out.println("順序表已滿，無法插入");return false;}//從插入位置開始，所有的元素向后移動一位for (int i =size;i>index;i--){array[i]=array[i-1];}//插入元素array[index]=element;//更新順序表的長度size++;return true;}public void printList(){for (int i = 0; i < size; i++) {System.out.println(array[i]+" ");}System.out.println();}public static void main(String[] args) {SequentialList list =new SequentialList(10);list.insert(0, 3); // 在索引0處插入元素3list.insert(1, 7); // 在索引1處插入元素7list.insert(2, 1); // 在索引2處插入元素1list.insert(3, 4); // 在索引3處插入元素4list.printList(); // 打印順序表}}

3. 順序表的刪除操作?

?對順序表進行插入和刪除操作時，算法所花費的時間主要用于移動元素。若插入或刪除在最前面，則需要移動n個元素；若插入或刪除元素在最后，則移動元素為0。設插入x作為第i個元素的概率為p，插入一個元素的平均移動到次數為O（n）。

?4.順序表查詢操作

根據查找條件，對順序表進行查找操作，采用順序查找算法，在查找過程中，需要將key與順序表順序表元素逐個比較是否相等。而比較對象對象相等規則有原數所屬的T類的equals（Object）方法實現。

   public int search(T key){for(int i =0;i<this.n;i++){if (key.equals(this.element[i])){return i;}}return -1;}

順序查找的比較次數取決于元素位置。時間復雜度也為O（n）。

靜態順序表的特性：

1. 固定大小：靜態順序表在創建時分配固定數量的內存空間，這個大小在定義后不能改變。

2. 內存分配：內存在編譯時分配，因此內存使用是靜態的，不會隨程序運行而改變。

3. 空間浪費：如果實際存儲的元素少于分配的空間，會造成內存浪費。

4. 無需移動元素：插入和刪除操作不需要移動大量元素，因為有足夠的空間來容納新元素或釋放空間。

5. 簡單實現：由于內存空間固定，實現起來相對簡單。

?順序表利用元素的物理存儲次序反映線性表元素的邏輯次序，不需要額外空間來表達元素之間的關系。

插入和刪除操作效率都很低。每插入或刪除一個元素，元素移動量大，平均移動順序表一半的元素。

順序表（也稱為數組）支持通過索引直接訪問元素，這種情況下查找的時間復雜度是 O(1)。這意味著無論數組有多大，訪問任何元素的時間都是恒定的，因為數組元素在內存中是連續存儲的，可以通過簡單的地址計算直接定位到元素。

如果你不知道元素的索引，而需要通過元素的值來查找它的位置，那么通常需要進行線性查找，這兩種情況的時間復雜度為?O(n) 。

5.順序表的應用

求解Josephus環的問題。

?

Josephus問題是一個著名的數學問題，以公元1世紀的猶太歷史學家約瑟夫斯（Flavius Josephus）的名字命名。據說，在羅馬占領期間，約瑟夫斯和他的39個同胞猶太士兵被羅馬軍隊包圍在一座山洞中，他們決定寧死不屈，并通過抽簽決定自殺的順序，每殺一個人，就按事先規定的順序數到下一人，直到所有人都死去。約瑟夫斯和另外一個人是最后兩個幸存者，他們決定不自殺，而是向羅馬軍隊投降。

這個問題可以形式化為：n個人圍成一圈，從第一個人開始，每數到第m個人，就將其處決，然后從下一個人重新開始數。這個過程一直進行，直到所有人都被處決。問題是，給定n和m，如何找到最后被處決的人的初始位置？

?

?

import java.util.ArrayList;public class Josephus {//n個人，n>0;從start開始技術，0<=start<n,每次數到distance的人出環，0<distance<npublic Josephus(int n ,int start,int distance){if (n<=0||start<0||start>=n||distance<=0||distance>=n)throw new IllegalArgumentException("n="+n+",start="+start+",distance="+distance+"");//創建順序表實例，元素類型是字符串，構造方法參數指定順序表容量，省略時取默認值ArrayList<String> list =new ArrayList<>();for (int i =0;i<n;i++){list.add((char)('A'+i)+"");}System.out.println(list.toString());while(n>1){//循環，每次計算刪除一個元素start =(start+distance-1)%n;//輸出刪除的start位置對象和順序表中的剩余元素，兩者均為Ｏ（ｎ）System.out.println("刪除"+list.remove(start).toString()+","+list.toString());n--;}System.out.println("被赦免的人是"+list.get(0));}public static void main(String[] args) {new Josephus(5,1,3);}
}

運行結果：?

[A, B, C, D, E]
刪除D,[A, B, C, E]
刪除B,[A, C, E]
刪除A,[C, E]
刪除C,[E]
E

線性表的鏈式存儲結構?

線性表采用的是鏈式存儲結構，別名單鏈表，用于儲存邏輯關系為“一對一”的數據。與順序表不同，鏈表不限制數據的物理存儲狀態，換句話說，使用鏈表存儲的數據結構，其物理存儲位置是隨機的，因此必須采用指針變量記載前驅或后續元素的存儲地址，存儲數據元素之間的線性關系。

?物理存儲結構：在物理層面上，單鏈表的節點不需要在內存中連續存儲。每個節點可以獨立地存儲在內存的任何位置，通過指針指向下一個節點，從而在邏輯上形成一個線性序列。這意味著，盡管節點在內存中是分散的，但它們通過指針連接起來，形成了一個完整的鏈表。

例如：

?

存儲一個數據元素的存儲單元稱為節點（node）。結點結構如下，至少包含兩個部分。

結點（數據域，地址域）   //數據域存儲數據元素，地址域（也稱為鏈）存儲前驅或后續元素地址

每個結點只有一個地址域的線性鏈表稱為單鏈表，空鏈表的頭指針head為null；一個單鏈表最后一個節點的地址域為null

一個完整的鏈表需要由以下幾個部分組成：

1.頭指針：一個普通的指針，它的特點是永遠指向鏈表第一個結點的位置。很明顯，頭指針用于指明鏈表的位置，便于后期找到鏈表并使用表中的數據。

2.節點：鏈表中的節點細分為頭節點，首元節和其他節點

A.頭節點：其實就是一個不存任何數據的空節點，通常作為鏈表的第一個節點，對于鏈表來說，頭節點不是必須的，它的作用只是方便解決某些實際問題

B.首元節點：只是堆鏈表的第一個存有數據節點的一個稱謂，沒有實際含義。

C.其他節點：鏈表中其他的節點

?

單鏈表的基本操作

1.單鏈表的插入操作

在單鏈表中插入一個節點，根據不同的插入位置，分一下幾種情況

1. 在頭節點前插入
2. 在尾部插入
3. 在某個特定的位置插入

過程分析：

單鏈表第 i 個數據插入結點的算法思路：

? ? 1）聲明一指針 p 指向鏈表頭結點，初始化 j 從1開始

? ? 2）當 j<i 時，就遍歷鏈表，讓 p 的指針向后移動，不斷指向下一結點，j 累加 1

? ? 3）若到鏈表末尾為空，則說明第 i 個結點不存在

? ? 4）否則查找成功，在系統中生成一個空節點s

? ? 5）將數據元素 e 賦值給 s->data

? ? 6）單鏈表的插入標準語句 s->next=p->next; p->next=s;

? ? 7）返回成功

public class test3  {private Node head;//頭節點//節點內部類private class Node{int data;Node next;Node(int data){this.data =data;this.next=null;}}//在鏈表的頭部插入新的節點public void insertAtHead(int data){Node newNode =new Node(data);//創建一個新的節點newNodenewNode.next=head;//建立的新的節點Node指向head節點的鏈，即插入newNode節點在head節點的前head=newNode;//使head指向newNode節點，則p節點成為第0個節點}//到鏈表的尾部插入新的節點public void insertAtTail(int data){Node newNode=new Node(data);//創建一個新的節點if(head==null){//檢查頭節點是否為空head=newNode;//如果鏈表為空，這行代碼講新節點賦值給頭節點head}else{Node current =head;//這個用來輔助遍歷鏈表while(current.next!=null){//直到current指向鏈表的最后一個節點current=current.next;//不斷指向鏈表中下一個節點}current.next=newNode;//當循環結束時，newNode連接到鏈表的結尾}}//在指定的位置插入新的節點public void insertAtPosition(int position,int data){if (position==0){insertAtHead(data);return;}Node newNode =new Node(data);Node current=head;for (int i =0;i<position-1&&current!=null;i++){current=current.next;}if (current==null){//如果current為null，說明指定的插入位置超出了鏈表當前長度System.out.println("position"+position+"is out of bounds");return;}newNode.next =current.next;current.next=newNode;}}

疑問：為什么在單鏈表數據讀取的時候，聲明的指針p指向鏈表的第一個節點，而在單鏈表插入的時候，聲明的指針p指向鏈表第一個節點，而在單鏈表插入時候，聲明的指針p指向鏈表的頭節點。

分析：

1. 單鏈表讀取的時候，是從頭開始查找的，如果找到直接讀取數據返回，顯然這個跟頭節點沒什么關系，直接從第一個節點開始即可。
2. 單鏈表插入的時候，查找到節點的情況下，是需要將p的后續節點改成s的后續節點，再將節點s變成p的后續節點。聲明p指針指向鏈表頭節點，p的后續節點就是第一節點，p的后續節點就是第一節點，就相當于從第一節點前插入，這顯然符合要求。
3. 如果聲明的指針p指向第一個節點，那通過這個插入語句后，就相當于插入了第二個節點前，顯然不符合要求。

2.刪除單鏈表

刪除單鏈表中的指定節點，通過改變節點的next域，就可以改變節點之間的連接關系，不需要移動元素。

刪除節點的算法思路：

? ? 1）聲明一指針 p 指向鏈表頭結點，初始化 j 從1開始

? ? 2）當 j < i 時，就遍歷鏈表，讓 p 的指針向后移動，不斷指向下一個結點，j 累加1

? ? 3）若到鏈表末尾 p 為空，則說明第 i 個結點不存在

? ? 4）否則查找成功，將欲刪除的結點 ?p->next 賦值給 q

? ? 5） 單鏈表的刪除標準語句 p->next = q->next

? ? 6） 將 q 結點中的數據賦值給 e, 作為返回

? ? 7） 釋放 q 結點

? ? 8） 返回成功

    // 刪除特定值的節點public void delete(int val) {if (head == null) {return;}if (head.val == val) {head = head.next;} else {ListNode curr = head;while (curr.next != null && curr.next.val != val) {curr = curr.next;}if (curr.next != null) {如果循環結束后，curr.next 不為 null，
說明找到了一個值等于 val 的節點。
這時，將 curr.next 更新為 curr.next.next
這樣就將值等于 val 的節點從鏈表中刪除了。curr.next = curr.next.next;}}}

3.查找倒數第k個元素

class LinkedList{ListNode head;//鏈表的頭節點//查找倒數第k個元素public ListNode findKthFromEndUsingTwoPasses(ListNode head,int k ){//第一次遍歷，計算鏈表的長度int length =0;ListNode current =head;while(current!=null){length++;current=current.next;}//如果k大于鏈表長度，則不存在倒數第k個元素if (k>length){throw new IllegalArgumentException("k的值大于鏈表長度");}//第二次遍歷，找到第length-k個節點int index =0;current =head;while(current!=null&&index<length-k){current=current.next;index++;}return current;//返回倒數第j個節點}//打印鏈表節點的值public void printList(ListNode head){ListNode current =head;while(current!=null){System.out.print(current.val+"->");current=current.next;}System.out.println("null");}public static void main(String[] args) {LinkedList linkedList = new LinkedList();linkedList.head = new ListNode(1);linkedList.head.next = new ListNode(2);linkedList.head.next.next = new ListNode(3);linkedList.head.next.next.next = new ListNode(4);linkedList.head.next.next.next.next = new ListNode(5);System.out.println("Original List:");linkedList.printList(linkedList.head);int k = 2; // 假設我們要找倒數第2個元素ListNode kthNode = linkedList.findKthFromEndUsingTwoPasses(linkedList.head, k);if (kthNode != null) {System.out.println("The " + k + "th node from the end has value: " + kthNode.val);} else {System.out.println("The " + k + "th node from the end does not exist.");}}
}

4.單鏈表反轉

思路分析：

對于這個問題，我們選擇迭代的方法，因為他不需要額外的存儲空間，并且時間復雜度為O（n）,其中n是鏈表的長度。

我們使用三個指針，prev初始化為null，以為你它將指向新鏈表的最后一個節點。即原鏈表的第一個節點，用于遍歷鏈表，next用于臨時存儲current的下一個節點。

1. 首先我們將current.next保存到next，因為下一步我們需要移動current
2. 然后，將current.next指向prev,這是反轉鏈表的關鍵，它改變了節點的指向，使其指向前一個節點而不是后一個節點。
3. 接著，將prev和current向前移動一位，prev變為當前的current，current變為next。?

class LinkedList{ListNode head;//鏈表的頭節點//反轉單鏈表public void reverse(){ListNode prev =null;//初始化prev為null,它將指向反轉后的前一個節點ListNode current= head;//用于遍歷當前節點ListNode next =null;//用于存儲下一個節點while (current!=null){next=current.next;//在改變current的next之前，先保存下一個節點current.next=prev;//反轉current節點的next指向prev，這是反轉的關鍵步驟prev=current;  //將prev前移一位，現在prev指向currentcurrent=next;//將current前移一位，現在都current指向next}head=prev;//完成反轉后，prev指向原鏈表的最后一個節點，即新鏈表的頭節點}//打印鏈表public void printList(){ListNode current =head;//頭節點開始遍歷while(current!=null){System.out.println(current.val+"->");current=current.next;}System.out.println("null");}
}

總結：

1.單鏈表不是隨機存儲結構

雖然訪問單鏈表第0個節點的時間是O（1）;但是要訪問第i個節點，必須從head開始沿著鏈的方向查找，遍歷部分單鏈表，進行i次都p=p.next操作，時間復雜度為O（n），所以單鏈表不是隨機存儲，

從整個算法來說，我們很容易推導出：它們的時間復雜度都是O（n）。如果在我們不知道第i個節點的指針位置 ，單鏈表數據結構在插入和刪除操作上，與線性表的存儲結構是沒有太大優勢的。但如果，我們希望從i個位置，插入10個節點，對于存儲結構，意味著，每一次插入都需要移動n-i個節點。每次都是O（n），而單鏈表，我們只需要在第一次時，找到第i個位置的指針，此時為O（n），接下來只是簡單得通過賦值移動指針，時間復雜度都是O（1）。對于插入和刪除數據越頻繁的操作，單鏈表的優勢越明顯。

插入或者刪除后驅節點的時間是O(1)，但是前驅節點或者刪除自己的時間是O（n）

如果front指向單鏈表中的一個節點，那么插入或者刪除后續節點的時間為O（1）。

如果p指向單鏈表的一個節點，要在p節點前插入一個節點或者刪除p節點自己，必須修改p的前驅節點的next域。因此需要再次遍歷單鏈表，找到p前驅節點front，轉換為插入或者刪除front的后續節點。

下面來做一道題來鍛煉一下吧：

題目是使用單鏈表實現素數線性表

public class PrimeLinkedList {ListNode head;public boolean isPrime(int num){if (num<1){return false;}for (int i =2;i*i<=num;i++){if (num%i==0){return false;}}return true;}public void insertPrime(int num){if (!isPrime(num)){System.out.println(num+"不是素數");return;}ListNode newNode =new ListNode(num);if (head==null){head=newNode;}else{ListNode current=head;current =head;while(current.next!=null){current=current.next;}//這段代碼遍歷鏈表到最后一個節點，然后將新的節點連接到鏈表的末尾current.next=newNode;}}public void printList() {ListNode current = head;while (current != null) {System.out.print(current.val + " ");current = current.next;}System.out.println();}
}class Main {public static void main(String[] args) {PrimeLinkedList primeList = new PrimeLinkedList();// 假設我們想插入以下數字int[] numbers = {2, 3, 4, 5, 6, 7, 11, 13, 17, 19, 23};for (int number : numbers) {primeList.insertPrime(number);}primeList.printList();}
}

?

?