? 作者：小胡_不糊涂
?? 作者主頁：小胡_不糊涂的個人主頁
?? 收錄專欄：淺談數(shù)據(jù)結(jié)構(gòu)
?? 持續(xù)更文，關(guān)注博主少走彎路，謝謝大家支持 ??
1. 線性表
線性表（linear list） 是n個具有相同特性的數(shù)據(jù)元素的有限序列。 它是一種在實際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見的線性表：順序表、鏈表、棧、隊列…
線性表在邏輯上是線性結(jié)構(gòu)，也就說是連續(xù)的一條直線。但是在物理結(jié)構(gòu)上并不一定是連續(xù)的，線性表在物理上存儲時，通常以數(shù)組和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲。
2. 順序表
順序表 是用一段物理地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲。在數(shù)組上完成數(shù)據(jù)的增刪查改。
2.1 接口的實現(xiàn)
實現(xiàn)順序表的插入、刪除、修改、查找工作：
import java.util.Arrays;
public class MyArrayList {
public int[] elem ;//定義一個數(shù)組
public int usedSize;//0，用來記錄元素個數(shù)
//順序表的 默認(rèn)大小
public static final int DEFAULT_SIZE = 10;
public MyArrayList() {
this.elem = new int[DEFAULT_SIZE];
}
public MyArrayList(int capacity) {
this.elem = new int[capacity];
}
//順序表尾部插入元素
public void add(int data) {
checkCapacity();
this.elem[this.usedSize] = data;
this.usedSize++;
}
//判斷順序表是否為空
public boolean isFull() {
/*if(usedSize == elem.length) {
return true;
}
return false;*/
return usedSize == elem.length;
}
//指定pos位置添加元素data
public void add(int pos, int data) {
try {
checkPosOnAdd(pos);
}catch (PosIllegality e) {
e.printStackTrace();
}
checkCapacity();
//1、從最后一個有效的數(shù)據(jù)開始往后移動 //2、當(dāng)i < pos 就結(jié)束
for (int i = usedSize-1; i >= pos; i--) {
elem[i+1] = elem[i];
}
//3、存放元素到pos 位置
elem[pos] = data;
//4、usedSize++;
usedSize++;
}
//檢查插入位置pos的合法性
private void checkPosOnAdd(int pos) throws PosIllegality{
if(pos < 0 || pos > usedSize) {
System.out.println("不符合法！");
throw new PosIllegality("插入元素下標(biāo)異常: "+pos);
}
}
private void checkCapacity() {
if(isFull()) {
//擴容
elem = Arrays.copyOf(elem,elem.length*2);
}
}
//判定是否包含某一元素
public boolean contains(int toFind) {
if(isEmpty()) {
return false;
}
for (int i = 0; i < usedSize; i++) {
//如果是查找引用數(shù)據(jù)類型 一定記住 重寫方法
if(elem[i] == toFind) {
return true;
}
}
return false;
}
//判斷線性表是否為空
public boolean isEmpty() {
return usedSize == 0;
}
//查找某個元素對應(yīng)位置
public int indexOf(int toFind) {
if(isEmpty()) {
return -1;
}
for (int i = 0; i < usedSize; i++) {
//如果是查找引用數(shù)據(jù)類型 一定記住 重寫方法
if(elem[i] == toFind) {
return i;
}
}
return -1;
}
//獲取pos位置元素
public int get(int pos) throws MyArrayListEmpty{
checkPosOnGetAndSet(pos);
if(isEmpty()) {
throw new MyArrayListEmpty("獲取指定下標(biāo)元素時" +
"順序表為空！");
}
return elem[pos];
}
private void checkPosOnGetAndSet(int pos) throws PosIllegality{
if(pos < 0 || pos >= usedSize) {
System.out.println("不符合法！");
throw new PosIllegality("獲取指定下標(biāo)的元素異常: "+pos);
}
}
//給pos位置設(shè)為元素value
public void set(int pos, int value) {
checkPosOnGetAndSet(pos);
elem[pos] = value;
}
//刪除第一次出現(xiàn)的這個數(shù)字
public void remove(int toRemove) {
int index = indexOf(toRemove);//獲取元素下標(biāo)
if(index == -1) {
System.out.println("沒有這個數(shù)字！");
return;
}
for(int i = index; i < usedSize-1;i++) {
elem[i] = elem[i+1];
}
usedSize--;
}
//獲取順序表長度
public int size() {
return this.usedSize;
}
//清空順序表
public void clear() {
this.usedSize = 0;
}
//打印順序表中元素
public void display() {
for (int i = 0; i < this.usedSize; i++) {
System.out.print(this.elem[i]+" ");
}
System.out.println();
}
}
測試類：
public class TestMAL{
public static void main(String[] arg) {
MyArrayList arr = new MyArrayList();
arr.add(1);
arr.add(2);
arr.add(3);
arr.add(4);
arr.add(5);
arr.display();
System.out.println("-------");
arr.add(1);
arr.display();
System.out.println("-------");
arr.add(6,2);
arr.display();
System.out.println("-------");
System.out.println(arr.indexOf(3));
arr.display();
System.out.println("-------");
arr.get(9);
}
}
3. ArrayList簡介
在集合框架中，ArrayList是一個普通的類，實現(xiàn)了List接口，具體框架圖如下：
【說明】
- ArrayList是以泛型方式實現(xiàn)的，使用時必須要先實例化
- ArrayList實現(xiàn)了RandomAccess接口，表明ArrayList支持隨機訪問
- ArrayList實現(xiàn)了Cloneable接口，表明ArrayList是可以clone的
- ArrayList實現(xiàn)了Serializable接口，表明ArrayList是支持序列化的
- 和Vector不同，ArrayList不是線程安全的，在單線程下可以使用，在多線程中可以選擇Vector或者CopyOnWriteArrayList
- ArrayList底層是一段連續(xù)的空間，并且可以動態(tài)擴容，是一個動態(tài)類型的順序表
4. ArrayList使用
4.1 ArrayList構(gòu)造
| 方法 | 解釋 |
|---|---|
| ArrayList() | 無參構(gòu)造 |
| ArrayList(Collection<? extends E> c) | 利用其他 Collection 構(gòu)建 ArrayList |
| ArrayList(int initialCapacity) | 指定順序表初始容量 |
ArrayList的創(chuàng)建：
public static void main(String[] arg){
// ArrayList創(chuàng)建，推薦寫法
// 構(gòu)造一個空的列表
List<Integer> list1 = new ArrayList<>();
// 構(gòu)造一個具有10個容量的列表
List<Integer> list2 = new ArrayList<>(10);
list2.add(1);
list2.add(2);
list2.add(3);
// list2.add("hello"); // 編譯失敗，List<Integer>已經(jīng)限定了，list2中只能存儲整形元素
// list3構(gòu)造好之后，與list中的元素一致
ArrayList<Integer> list3 = new ArrayList<>(list2);
// 避免省略類型，否則：任意類型的元素都可以存放，使用時將是一場災(zāi)難
List list4 = new ArrayList();
list4.add("111");
list4.add(100);
System.out.println(list4);//[111,100]
}
4.2 ArrayList常見操作
| 方法 | 解釋 |
|---|---|
| boolean add(E e) | 尾插 e |
| void add(int index, E element) | 將 e 插入到 index 位置 |
| boolean addAll(Collection<? extends E> c) | 尾插 c 中的元素 |
| E remove(int index) | 刪除 index 位置元素 |
| boolean remove(Object o) | 刪除遇到的第一個 o |
| E get(int index) | 獲取下標(biāo) index 位置元素 |
| E set(int index, E element) | 將下標(biāo) index 位置元素設(shè)置為 element |
| void clear() | 清空 |
| boolean contains(Object o) | 判斷 o 是否在線性表中 |
| int indexOf(Object o) | 返回第一個 o 所在下標(biāo) |
| int lastIndexOf(Object o) | 返回最后一個 o 的下標(biāo) |
| List subList(int fromIndex, int toIndex) | 截取部分 list |
ArrayList操作方法的使用：文章來源：http://www.zghlxwxcb.cn/news/detail-725566.html
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("JavaSE");
list.add("JavaWeb");
list.add("JavaEE");
list.add("JVM");
list.add("測試課程");
System.out.println(list);
// 獲取list中有效元素個數(shù)
System.out.println(list.size());
// 獲取和設(shè)置index位置上的元素，注意index必須介于[0, size)間
System.out.println(list.get(1));
list.set(1, "JavaWEB");
System.out.println(list.get(1));
// 在list的index位置插入指定元素，index及后續(xù)的元素統(tǒng)一往后搬移一個位置
list.add(1, "Java數(shù)據(jù)結(jié)構(gòu)");
System.out.println(list);
// 刪除指定元素，找到了就刪除，該元素之后的元素統(tǒng)一往前搬移一個位置
list.remove("JVM");
System.out.println(list);
// 刪除list中index位置上的元素，注意index不要超過list中有效元素個數(shù),否則會拋出下標(biāo)越界異常
list.remove(list.size()-1);
System.out.println(list);
// 檢測list中是否包含指定元素，包含返回true，否則返回false
if(list.contains("測試課程")){
list.add("測試課程");
}
// 查找指定元素第一次出現(xiàn)的位置：indexOf從前往后找，lastIndexOf從后往前找
list.add("JavaSE");
System.out.println(list.indexOf("JavaSE"));
System.out.println(list.lastIndexOf("JavaSE"));
// 使用list中[0, 4)之間的元素構(gòu)成一個新的SubList返回,但是和ArrayList共用一個elementData數(shù)組
List<String> ret = list.subList(0, 4);
System.out.println(ret);
list.clear();
System.out.println(list.size());
}
4.3 ArrayList的遍歷
ArrayList 可以使用三方方式遍歷：for循環(huán)+下標(biāo)、foreach、使用迭代器文章來源地址http://www.zghlxwxcb.cn/news/detail-725566.html
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
// 使用下標(biāo)+for遍歷
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i) + " ");
}
System.out.println();
// 借助foreach遍歷
for (Integer integer : list) {
System.out.print(integer + " ");
}
System.out.println();
//使用迭代器
Iterator<Integer> it = list.listIterator();
while(it.hasNext()){
System.out.print(it.next() + " ");
}
System.out.println();
}
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】線性表與順序表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
