資料結構與算法-數組

數組

• 數組
• • 數組定義
  • 表現形式
  • 數組的随機通路
  • • 數組下标為什麼從0開始？
  • 優缺點
  • ArrayList和數組
  • 堆棧記憶體
  • 數組實作CRUD

數組

• 是有序的元素序列。若将有限個類型相同的變量的集合命名，那麼這個名稱為數組名。組成數組的各個變量也稱為數組的分量，也稱數組元素。
• 區分數組的各個元素的數組編号為下标；
• 數組是在程式設計中，為了處理友善， 把具有相同類型的若幹元素按無序的形式組織起來的一種形式。這些無序排列的同類資料元素的集合稱為數組。
• 線性表

數組定義

• 數組是相同資料類型的元素的集合
• 各元素的存儲是有先後順序的，在記憶體中按照先後順序存放在一起；
• 數組元素用整個數組的名字和它自己在數組中的順序位置來表示。例如，a[0]表示名字為a的數組中的第一個元素，a[1]代表數組a的第二個元素，以此類推。

表現形式

• 一維數組

int a[],String a[]
           

• 多元數組

int a[][],int[][][];
           

數組的随機通路

數組是連續的記憶體空間和相同類型的資料。正是因為這兩個限制，它才有了一個非常重要的特性：随機通路。但有利就有弊，這兩個限制也讓數組的很多操作變得非常低效，比如要想在數組中删除、插入一個資料，為了保證連續性，就需要做大量的資料搬移工作。

是以、使用者可以直接根據數組下标通路數組元素

數組下标為什麼從0開始？

int a[]=new int[3];
           

假如到記憶體中申請空間：10001,10005,10009。

a[0]=>10001==>10001+0 * 4;

a[1]=>10005==>10001+1 * 4;

a[2]=>10009==>10001+2 * 4;

如果我們不從0開始

a[1] = 10001+(1-1) * 4

a[2] = 10001+(2-1) * 4

a[3] = 10001+(3-1) * 4

在CPU裡，一個相減運算倒沒什麼，但是這個運算被大量使用，就會耗費時間。是以數組下标應該從0開始；

二位數組arr[m][n]的尋址是怎麼樣的？

int arr[][]=new arr[m][n];
           

位址=數組的起始位址+m * n * typeSize+ n*typeSize;

優缺點

優點：随機通路

缺點：

1. 删除、删除需要涉及到元素移動、資料量大很麻煩；
2. 可能會有越界問題

ArrayList和數組

本質是一樣的，都是數組。

• ArrayList是JDK封裝了。不需要管擴容等操作。
• 數組的話就要你全部操作。

兩者之間應該如何選用？

• 不知道資料大小的肯定選ArrayList。
• 如果你知道資料的大小而且你又非常關注性能那就用數組。

數組最需要注意的就是越界：尤其是在開始和結束。測試的時候也一樣注意頭和尾。

堆棧記憶體

Java分為堆棧兩種記憶體。

什麼是堆記憶體？

• 存放new建立的對象和數組。

什麼是棧記憶體？

• 引用變量

堆棧的差別

• 棧的速度要快
• 棧記憶體的資料可以共享，主要存一些基本資料類型。

數組實作CRUD

package algorithm.array;

public class ArrayTest {
	
	private int size;		//數組的長度
	private int data[];
	private int index;		//目前已經存的資料大小
	
	public ArrayTest(int size){		//數組的初始化過程
		this.size = size;
		data = new int[size];		//配置設定的記憶體空間{0,0,0,0,0}
		index = 0;
	}
	
	public void print(){
		System.out.println("index:" + index);
		for(int i = 0 ; i < index ; i++){
			System.out.print(data[i] + " ");
		}
		System.out.println();
	}
	
	public void insert(int loc,int n){		//時間複雜度 O(n);
		if(index ++ < size){
			for(int i = size - 1; i > loc ; i --){	//為什麼不能寫size 0~size-1 如果loc是0 O(n),O(1)=>O(n)
				data[i] = data[i - 1];	//把資料往後移一個
			}
			data[loc] = n;
		}
		//擴容 會把size/2； 
	}
	public void delete(int loc){	//O(n)
		for(int i = loc ; i < size ; i++){
			if(i != size - 1){		//怕越界是以加一個判斷
				data[i] = data[i + 1];
			}else{
				data[i] = 0;			//預設為0 就是沒存資料的
			}
		}
		index -- ;
	}
	
	public void update(int loc,int n){//O(1)
		data[loc] = n;
	}
	
	public int get(int loc){		//O(1)
		return data[loc];
	}
	
	
	public static void main(String[] args) {
		//ArrayList
	}
}

           

其實這就類似ArrayList的底層實作；