溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
線性表
線性表是最簡單和最常用的一種數據結構，它是有n個體數據元素（節點）組成的有限序列。其中，數據元素的個數n為表的長度，當n為零時成為空表，非空的線性表通常記為：
（a1，a2，… ，ai-1，ai， ai+1，…，an）
一. 線性表的順序存儲及算法
線性表的順序存儲指的是將線性表的數據元素按其邏輯次序依次存入一組地址連續的存儲單元里，用這種方法存儲的線性表稱為順序表。
1.順序表的結構定義
public class SeqList {
/* 初始空間為10 */
private static final int LIST_SIZE = 10;
/* 數組data用來存放元素 */
private int[] data;
/* 當前表長，實際存儲元素的個數 */
private int length;
}
2.插入運算
順序表的插入運算是指在線性表的第i-1個元素和第i個元素之間插入一個新元素。由于順序表邏輯上相鄰的元素在物理結構上也相鄰，其物理存儲關系也要發生相應的變化。除非i=n+1，否則必須將原順序表的第i個元素開始的所有元素分別向后移動1個位置。
/**
* 在順序表list中第i個位置之前插入一個新元素node
* @param list 順序表
* @param i 插入位置
* @param node 新元素
*/
public void insertList(SeqList list, int i, int node) {
if (i < 1 || i > list.length + 1) {
System.out.println("position error");
return;
}
if (list.length >= LIST_SIZE) {
System.out.println("overflow");
return;
}
for (int j = list.length - 1; j >= i - 1; j --) {
/* 從最后一個元素開始逐一后移 */
list.data[j+1] = list.data[j];
}
/* 插入新元素 */
list.data[i-1] = node;
/* 表長加1 */
list.length ++;
}
3.刪除運算
順序表的刪除運算指的是將表中第i個元素刪除，與插入運算相反，插入是向后移動元素，刪除運算則是向前移動元素。
/**
* 在順序表list中刪除第i個元素，并返回被刪除的元素
* @param list 順序表
* @param i 元素位置
* @return node
*/
public int deleteList(SeqList list, int i) {
int node = 0;
if (i < 0 || i > list.length) {
System.out.println("position error");
return node;
}
node = list.data[i-1];
for (int j = i; j < list.length; j ++) {
/* 元素前移 */
list.data[j-1] = list.data[j];
}
list.length --;
return node;
}
4.順序表逆置
先以表長的一半為循環控制次數，將表中最后一個元素同順序順數第一個元素交換，將倒數第二個元素同順數第二個元素交換，以此類推，直至交換完為止。
/**
* 順序表逆置
* @param list 原始順序表
* @return 逆置后的順序表
*/
public SeqList converts(SeqList list) {
int node;
int length = list.length/2;
for (int i = 0; i < length; i ++) {
/* 對稱交換元素 */
int j = list.length - 1 - i;
node = list.data[i];
list.data[i] = list.data[j];
list.data[j] = node;
}
return list;
}
二. 線性表的鏈式存儲及算法
鏈式存儲結構存儲線性表數據元素的存儲空間可能是連續的，也可能是不連續的，因而鏈表的節點是不可以隨機存取的，鏈式存粗是最常見的存儲方式之一。
在使用鏈式存儲結構表示每個數據元素時，除了存儲元素本身的信息外，還需要一個存儲指示后繼元素存儲位置的地址，利用這種存儲方式表示的線性表稱為鏈表。
5.單鏈表的結構定義
public class LinkList {
/* 數據域 */
private char data;
/* 后繼元素 */
private LinkList next;
}
6.頭插法建表算法
頭插法是從一個空表開始，重復讀入數據，生成新節點，將讀入的數據存放到新節點的數據域中，然后將新節點插入到當前鏈表的表頭上，直到結束為止。
/**
* 頭插法創建表
* @param chars 字符數組
* @return 單鏈表
*/
public LinkList createListF(char[] chars) {
LinkList node;
LinkList head = null;
for (char ch : chars) {
/* 申請新節點 */
node = new LinkList();
node.data = ch;
/* 指向后繼節點 */
node.next = head;
head = node;
}
/* 返回頭節點 */
return head;
}
7.尾插法建表算法
頭插法建表中節點的次序和輸入時的順序相反，若需要和輸入次序一致，則可使用尾插法。
/**
* 尾插法建表
* @param chars 字符數組
* @return 單鏈表
*/
public LinkList createListR(char[] chars) {
LinkList node;
LinkList head = null;
LinkList rear = null;
for (char ch : chars) {
node = new LinkList();
node.data = ch;
if (head == null) {
/* 新節點為頭節點 */
head = node;
} else {
/* 上一個節點指向新節點 */
rear.next = node;
}
/* 表尾指向新的節點 */
rear = node;
}
/* 返回頭節點 */
return head;
}
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
