線性表
線性表是最基本、最簡單、也是最常用的一種資料結構，是n個具有相同特性的資料元素的有限序列（n ≥ 0），
關鍵點
-
資料有限
-
元素之間是有順序
-
若元素存在多個
- 第一個元素無前驅
- 最后一個元素無后繼
- 其他每個元素都有且只有一個前驅和后繼
數學定義
抽象資料型別
線性表的順序存盤結構
線性表的順序儲存指的是用一段地址連續的存盤單元一次存盤線性表的資料元素，
正巧一維陣列就滿足了連續存盤的條件，所以可以用一維陣列實作順序存盤結構，
順序存盤結構需要三個屬性
- 存盤空間 陣列 data
- 最大容量 maxSize
- 當前長度 length
代碼實作
package com.linearlist;
/**
* 線性表順序存盤
*/
public class LinearList {
private int maxSize;
private int length;
private int[] arr;
public LinearList(int maxSize) {
// 初始化傳入一個最大容量
this.maxSize = maxSize;
this.arr = new int[maxSize];
this.length = 0;
}
public boolean isEmpty() {
// 慷訓傳真
return arr == null || length == 0;
}
public boolean isFull() {
return length == maxSize;
}
// 獲取某個元素
public int getElem(int i) {
if (isEmpty()) {
throw new RuntimeException("線性表為空");
}
return arr[i - 1];
}
public void insertElem(int i, int num) {
//在第i個位置插入元素num
if (isFull()) {
System.out.println("擠不下了~兄弟");
return;
}
if (i < 0 || i > maxSize) {
System.out.println("輸入例外");
return;
}
// 從i位置后面的人都要后移，包括i
int j = ++length;
for (; j >= i; j--) {
arr[j] = arr[j - 1];
}
// 騰出位置后，即可插入
arr[j] = num;
}
public int deleteElem(int i) {
//在第i個位置插入元素num
if (isEmpty()) {
throw new RuntimeException("刪完了");
} else if (i < 0 || i > length) {
throw new RuntimeException("輸入例外");
}
int temp = arr[i - 1];
// 從洗掉的位置后一個向前移動
for (int j = i - 1; j < length - 1; j++) {
arr[j] = arr[j + 1];
}
length--;
// deleteElem(4)
// 1 2 3 4
// 0 1 2 3
// 4
return temp;
}
public void list() {
if (isEmpty()) {
System.out.println("無資料");
return;
}
for (int i =0;i<length;i++) {
System.out.print(arr[i] + "\t");
}
}
}
優缺點
優點
- 無須為表中的元素之間的邏輯關系而添加額外的存盤空間
- 可以快速的存取表中的任一位置的元素
缺點
- 插入和洗掉需要移動大量元素
- 當線性表變化大時，難以確定存盤空間的容量
- 造成存盤空間的“碎片”
這里區別一下陣列、線性表、順序表的概念
由上面代碼可以知道，線性表的順序存盤結構需要陣列實作，
陣列就是相同資料型別的元素按一定順序排列的集合，
陣列本質：物理上存盤在一組聯系的地址上，也就是資料結構中的順序存盤物理結構，
線性表中資料元素之間的關系是一對一的關系，即除了第一個和最后一個資料元素之外，其它資料元素都是首尾相接的，
線性表本質：線性表是資料結構中的邏輯結構，
**線性表根據存盤結構的不同可以分為 **
- 順序表，通過陣列實作（順序存盤結構）
- 鏈表，通過鏈式存盤實作
以上代碼實作的就是順序表，加下來學習鏈表
線性表的鏈式存盤結構
特點
用一組任意的存盤單元存盤線性表的資料元素，這組存盤單元可以是連續的，也可以是不連續的，
在順序結構中，每個資料元素只需要存資料元素資訊就可以了，
而鏈式結構中，除了要存資料元素資訊外，還要存盤它的后繼元素的存盤地址，
基本概念
資料域：存盤資料元素資訊
指標域：存盤后繼位置
結點：由資料域和指標域組成
單鏈表：每個結點質保函一個指標域
頭指標：鏈表的第一個結點的存盤位置
頭結點：單鏈表的第一個結點前附加一個結點
頭指標和頭結點的異同:
單鏈表的實作
首先定義一個結點類
HerNode.java
/**
* 定義一個節點
*/
class HeroNode {
public int no;
public String name;
public String nickname;
public HeroNode next;
public HeroNode() {
}
public HeroNode(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
}
再去寫一個單鏈表的類
SingleLinkedList.java
import HeroNode;
public class SingleLinkedList {
// 先初始化一個頭結點，頭結點是尋找鏈表開始，不要動它
private HeroNode head = new HeroNode(0, "", "");
public HeroNode getHead() {
return head;
}
public void setHead(HeroNode head) {
this.head = head;
}
/**
* 頭插法添加新節點
*/
public void addHead(HeroNode heroNode) {
heroNode.next = head.next;
head.next = heroNode;
}
/**
* 尾插法添加新節點
* @param heroNode 新節點
*/
public void add(HeroNode heroNode) {
// 1.首先遍歷到尾結點
HeroNode temp = head;
while (temp.next != null) {
temp = temp.next;
}
// 2.將尾結點的next指向新節點
temp.next = heroNode;
}
/**
* 根據排名插入資料
* @param heroNode 新節點
*/
public void addByOrder(HeroNode heroNode) {
// 1.首先找到新節點的插入位置
HeroNode temp = head;
// 如果找到尾結點還沒有找到合適的位置，則尾插到最后
while (temp.next != null && temp.next.no <= heroNode.no) {
temp = temp.next;
if (temp.no == heroNode.no) {
System.out.println(heroNode.name+"已存在,不可添加");
return;
}
}
// 2.新節點指向后節點
heroNode.next = temp.next;
// 3.原節點指向新節點
temp.next = heroNode;
}
/**
* 根據編號更新節點資料
*/
public void update(HeroNode heroNode) {
// 1.首先找到新節點的插入位置
HeroNode temp = head;
while (temp.next != null && temp.no != heroNode.no) {
temp = temp.next;
}
// 如果跳出回圈還沒有匹配，就是找不到對應的節點
if (temp.no != heroNode.no) {
System.out.println("該編號不存在");
} else {
temp.name = heroNode.name;
temp.nickname = heroNode.nickname;
}
}
/**
* 洗掉節點
*/
public void delete(int no) {
if (head.next == null) {
System.out.println("雙向鏈表為空");
return;
}
// 首先找到洗掉節點的【前一個】節點
HeroNode temp = head;
while (temp.next != null && temp.next.no != no) {
temp = temp.next;
}
// 如果沒沒有遍歷到最后一個節點說明找到了匹配的節點
if (temp.next != null) {
// 跳過匹配節點的鏈接
temp.next = temp.next.next;
} else {
System.out.println(no + "節點不存在");
}
}
/**
* 列印鏈表資訊
*/
public void list() {
if (head.next == null) {
System.out.println("鏈表為空");
return;
}
// 臨時變數遍歷
HeroNode temp = head;
while (temp.next != null) {
temp = temp.next;
System.out.println(temp.toString());
}
}
}
單鏈表和順序存盤結構的優缺點
經驗性結論
- 若線性表頻繁查找，很少插入和洗掉資料 —> 使用順序表，反之用鏈表，
- 當線性表的元素個數比較大時，或者根本不知道有多大時，最好用鏈表，
- 如果事先知道線性表的大概長度，使用順序表
鏈表擴展
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/31060.html
標籤：其他