前言
你可以把數組想象成是把數據碼成一排進行存放,在強語言中數據的類型是確認的,而在弱語言中數據的類型是不確認的,但是也有方法可以進行確認。js 中的數組是有侷限性的。
還是那句老話:光看文章能夠掌握兩成,動手敲代碼、動腦思考、畫圖才可以掌握八成。源碼倉庫
不要完美主義。掌握好“度”。
太過於追求完美會把自己逼的太緊,會產生各種焦慮的心態,最後甚至會懷疑自己,溫故而知新,不要停止不前,掌握好這個度,不存在你把那些你認為完全掌握了,然後就成了某一個領域的專家,相反一旦你產生很濃厚的厭惡感,那麼就意味著你即將會放棄或者已經選擇了放棄,雖然你之前想把它做到 100 分,但是由於你的放棄讓它變為 0 分。
學習本著自己的目標去。不要在學的過程中偏離了自己的目標。要分清主次。
難的東西,你可以慢慢的回頭看一看。那樣才會更加的柳暗花明,更能提升自己的收穫。
先簡單認識一下數組
相像一下,把一個一個的數據近挨著排成一排。在數組中有一個很重要的概念叫做索引,也就是數組元素的編號,編號從 0 開始的,所以最後一個元素的索引為數組的長度-1 即 n-1,可以通過數組名[索引]
來訪問數組中的元素。
'use strict';
// 輸出
console.log('Array');
// 定義數組
let arr = new Array(10);
for (var i = 0; i < arr.length; i++) {
arr[i] = i;
}
// 定義數組
let scores = new Array(100, 99, 98);
// 遍歷輸出
for (var i = 0; i < scores.length; i++) {
console.log(scores[i]);
}
// 修改數組中某個元素
scores[1] = 60;
// foreach 遍歷數組
for (let index in scores) {
console.log(scores[index]);
}
索引
數組的索引可以有語意也可以沒有語意。如 scores[2]
代表一個班級中第三個學生。 還有數組的最大優點是快速查詢,如 scores[2]
。 數組最好應用於“索引有語意”的情況。如果索引沒有語意的話,那麼使用別的數據結構那會是一個更好的選擇。
數組也可以處理“索引沒有語意”的情況。在索引有語意的情況下使用數組非常簡單,直接就可以查到相應的數據。在索引沒有語義的情況下使用數組,那麼就會產生很多新的問題。因為這個時候數組只是一個待存放那些要考察的數據的空間,例如你開闢了 8 個元素的空間,但是你只考察 2 個元素,此時就有問題了,剩下的空間都沒有元素,可能訪問剩下的空間就是非法的,因為從用戶的角度上來看是沒有那麼多元素的,只有兩個元素。
計算機處理的問題有千千萬萬個
有很多場景即使能給索引定義出來語意,但是它有可能不適用於數組。比如身份證號可以設計為一個數組,用來存儲相應的工資情況,如果想索引到不同的人,那麼使用身份證號就是一個很好的方式,但是身份證號不能作為一個數組的索引,因為這個身份證號太大了。
如果想要使用身份證號作為一個數組的索引,那麼開闢的空間會非常的大,例如arr[110103198512112312]
,對於一般的計算機來說開闢這樣的一塊兒空間,是非常不值當的,甚至是不可能的,而且大部分空間都是浪費的,比如你就想考察 100 個人的工資情況,你卻開闢了 1000 兆倍的空間。
封裝自己的專屬數組
先將原本 js 中的數組封裝到一個類中,從而封裝一個屬於自己的數組,這個類就叫做 MyArray,在這個類中封裝一個 js 的數組,這個數組叫做 data,對這個數組進行增刪改插等等的功能。
階段一:將數組封裝成自己的數組
實現思路
數據結構的本質也是存儲數據,之後再進行高效的對這些數據進行操作,只不過你設計的數據結構會把這些數據存儲在內存中,所以針對這些數據結構的所添加的操作在大的類別的劃分上,也是增刪改查。
針對不同的數據結構,對應的增刪改查的方式是截然不同的,甚至某些數據結構會忽略掉增刪改查中的某一個操作,但是增刪改查可以作為研究某一個數據結構的相應的脈絡。
數組本身是靜態的,必須在創建的時候指定他的大小,可以把這個容量叫做 capacity,也就是數組空間最多可以裝多少個元素,數組空間最多可以裝多少個元素與數組中實際裝多少個元素是沒有關係的,因為這是兩回事兒。
數組中實際能夠裝多少個元素可以叫做 size,通過它來控制,在初始化的時候,數組中一個元素都沒有,所以 size 為 0,這個 size 相當於數組中第一個沒有盛放元素的相應索引,增加數組元素和刪除數組元素的時候就要維護這個 size。
代碼實現
(class: MyArray)
class MyArray {
// 構造函數,傳入數組的容量capacity構造Array 默認數組的容量capacity=10
constructor(capacity = 10) {
this.data = new Array(10);
this.size = 0;
}
// 獲取數組中的元素實際個數
getSize() {
return this.size;
}
// 獲取數組的容量
getCapacity() {
return this.data.length;
}
// 判斷數組是否為空
isEmpty() {
return this.size === 0;
}
}
階段二:對自己的數組進行添加操作
實現思路
向數組添加元素最簡單的形式就是在數組的末尾添加一個元素,size 這個變量其實就是指向數組中的末尾,添加完元素之後其實也需要維護這個 size,因為數組中的元素多了一個,所以要讓它加加。
如果是給元素進行插入的操作那麼要先判數組的容量是否已經裝滿了,然後再判斷索引是否小於 0 或者大於 size,都沒有問題了,就可以根據索引來進行插入了,插入的原理就是那個索引位置及其後的元素,全都都往後移動一位,所以循環是從後往前的,最後讓該索引處的舊元素被新元素覆蓋,但舊元素並沒消失,而是位置往後移動了一位,最後要記得維護 size。
向數組中添加元素可以複用向數組中插入元素的方法,因為插入元素的方法也是在給數組添加元素,並且插入元素的方法可以在任何位置插入新元素,那麼就可以擴展兩個方法,一個插入到數組最前面(插入到索引為 0 的位置),一個是插入到數組最後面(插入到索引為 數組最後一個元素的索引+1 的位置)。
給數組添加元素的時候如果元素為數字(添加時可排序可不排序),那麼每一次添加操作時可以給數組中的元素進行排序,排序方式是按照從小到大來進行排序。先判斷添加的這個元素大於數組中哪一個元素,然後將那個元素及其後面的所有元素往後移一位,最後將添加的這個元素插入到那個元素後面。先要對數組中的容量進行判斷,如果超過了就不添加,並且報錯,每次添加之前要判斷一下插入的位置,它後面還有沒有元素或者這個數組是否為空。記住每次添加操作都要維護 size 這個變量。
代碼實現
(class: MyArray)
class MyArray {
// 構造函數,傳入數組的容量capacity構造Array 默認數組的容量capacity=10
constructor(capacity = 10) {
this.data = new Array(10);
this.size = 0;
}
// 獲取數組中的元素實際個數
getSize() {
return this.size;
}
// 獲取數組的容量
getCapacity() {
return this.data.length;
}
// 判斷數組是否為空
isEmpty() {
return this.size === 0;
}
// 在指定索引處插入元素
insert(index, element) {
// 先判斷數組是否已滿
if (this.size == this.getCapacity()) {
throw new Error('add error. Array is full.');
}
// 然後判斷索引是否符合要求
if (index < 0 || index > size) {
throw new Error('insert error. require index < 0 or index > size');
}
// 最後 將指定索引處騰出來
// 從指定索引處開始,所有數組元素全部往後移動一位
// 從後往前移動
for (let i = size - 1; i >= index; i--) {
this.data[i + 1] = this.data[i];
}
// 在指定索引處插入元素
this.data[index] = element;
// 維護一下size
size++;
}
// 擴展 在數組最前面插入一個元素
unshift(element) {
insert(0, element);
}
// 擴展 在數組最後面插入一個元素
push(element) {
insert(size, element);
}
// 其實在數組中添加元素 就相當於在數組最後面插入一個元素
add(element) {
if (this.size == getCapacity()) {
throw new Error('add error. Array is full.');
}
// size其實指向的是 當前數組最後一個元素的 後一個位置的索引。
this.data[size] = element;
// 維護size
size++;
}
}
階段三:對自己的數組進行查詢和修改操作
實現思路
如果你要覆蓋父類中的方法,有一個通用的規範,加備註 如 // @Override: 方法名 日期-開發人員
。
獲取自定義數組中指定索引位置的元素首先要判斷索引是否小於 0 或者大於等於 實際元素的個數,都沒有問題時,就可以返回索引位置的元素了。用戶沒有辦法去訪問那些沒有使用的數組空間。
修改自動數組中指定索引位置的元素和獲取是一樣的,要先判斷,只能設置已有存在的元素索引位置的元素,用戶沒有辦法去修改那些沒有使用的數組空間。
代碼實現
(class: MyArray
class MyArray {
// 構造函數,傳入數組的容量capacity構造Array 默認數組的容量capacity=10
constructor(capacity = 10) {
this.data = new Array(capacity);
this.size = 0;
}
// 獲取數組中的元素實際個數
getSize() {
return this.size;
}
// 獲取數組的容量
getCapacity() {
return this.data.length;
}
// 判斷數組是否為空
isEmpty() {
return this.size === 0;
}
// 在指定索引處插入元素
insert(index, element) {
// 先判斷數組是否已滿
if (this.size == this.getCapacity()) {
throw new Error('add error. Array is full.');
}
// 然後判斷索引是否符合要求
if (index < 0 || index > this.size) {
throw new Error('insert error. require index < 0 or index > size');
}
// 最後 將指定索引處騰出來
// 從指定索引處開始,所有數組元素全部往後移動一位
// 從後往前移動
for (let i = this.size - 1; i >= index; i--) {
this.data[i + 1] = this.data[i];
}
// 在指定索引處插入元素
this.data[index] = element;
// 維護一下size
this.size++;
}
// 擴展 在數組最前面插入一個元素
unshift(element) {
this.insert(0, element);
}
// 擴展 在數組最後面插入一個元素
push(element) {
this.insert(this.size, element);
}
// 其實在數組中添加元素 就相當於在數組最後面插入一個元素
add(element) {
if (this.size == this.getCapacity()) {
throw new Error('add error. Array is full.');
}
// size其實指向的是 當前數組最後一個元素的 後一個位置的索引。
this.data[this.size] = element;
// 維護size
this.size++;
}
// get
get(index) {
// 不能訪問沒有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size');
}
return this.data[index];
}
// set
set(index, newElement) {
// 不能修改沒有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('set error. index < 0 or index >= size');
}
this.data[index] = newElement;
}
// @Override toString 2018-10-17-jwl
toString() {
let arrInfo = `Array: size = ${this.getSize()},capacity = ${this.getCapacity()},\n`;
arrInfo += `data = [`;
for (var i = 0; i < this.size - 1; i++) {
arrInfo += `${this.data[i]}, `;
}
arrInfo += `${this.data[this.size - 1]}`;
arrInfo += `]`;
// 在頁面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}
class: Main)
class Main {
constructor() {
let ma = new MyArray(20);
for (let i = 1; i <= 10; i++) {
ma.add(i);
}
console.log(ma.toString());
ma.insert(1, 200);
console.log(ma.toString());
ma.unshift(-1);
console.log(ma.toString());
ma.push(9999);
console.log(ma.toString());
ma.set(5, 8888);
console.log(ma.get(5));
this.show(ma.get(5));
}
// 將內容顯示在頁面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
}
window.onload = function() {
// 執行主函數
new Main();
};
階段四:對自己的數組進行包含、查找、和刪除操作
實現思路
繼續對自定義的數組增加新功能包含、搜索、刪除這三個功能。
包含:判斷數組中 是否存在這個元素,不存在返回 false。
搜索:根據這個元素來進行 索引的獲取,找不到返回 非法索引 -1。
刪除:首先要判斷索引的合法性,其次這個操作與插入的操作其實原理類似,只不過是一個反向的過程,指定索引位置的元素其後面的元素的位置全部往前一位,循環時 初始索引為 指定的這個索引,從前往後的不斷向前移動,這樣被刪除的元素就被覆蓋了,覆蓋之前要保存一下指定索引的元素的值,這個值要作為返回值來進行返回,然後讓 size 減減,因為覆蓋掉這個元素,由於數組訪問會有索引合法性的判斷一定要小於 size,於是用戶是訪問不到 size 位置的元素了,所以 size 位置的元素可以不用去處理它,但你也可以手動的將這個元素值設置為默認值。
有了指定索引刪除某個元素並返回被刪除的這個元素的操作那麼就可以擴展出兩個方法,和使用插入方法來進行擴展的那兩個方法類似,分別是 刪除第一個元素和刪除最後一個元素,並且返回被刪除的元素,刪除數組元素時會判斷數組索引的合法性,如果數組為空,那麼合法性驗證就無法通過。
根據元素來刪除數組中的某個元素首先通過 包含 的那個方法來判斷這個元素是否存在,如果元素不存在那就不進行刪除操作,也可以報一個異常,如果元素存在,那就根據 搜索 的那個方法來獲取這個元素的索引,最後根據 獲取到合法索引 來進行元素的刪除。其實你可以使用通過 搜索 的那個方法直接返回元素的索引,如果索引合法你就直接刪除,如果索引不合法那就不刪除然後也可以報一個異常。
可以對那些方法進行擴展如 刪除數組中所有的指定元素,如 找到數組中所有的指定元素的索引。關於自定義的數組已經實現了很多功能,在js中沒有這些侷限性。比如 js的數組存放的數據類型可以是任意的數據類型,但在強類型語言中默認是不可以的。還有在強類型語言中數組的容量是一開始就固定好的,超出就會報異常。
代碼實現
(class: MyArray)
class MyArray {
// 構造函數,傳入數組的容量capacity構造Array 默認數組的容量capacity=10
constructor(capacity = 10) {
this.data = new Array(capacity);
this.size = 0;
}
// 獲取數組中的元素實際個數
getSize() {
return this.size;
}
// 獲取數組的容量
getCapacity() {
return this.data.length;
}
// 判斷數組是否為空
isEmpty() {
return this.size === 0;
}
// 在指定索引處插入元素
insert(index, element) {
// 先判斷數組是否已滿
if (this.size == this.getCapacity()) {
throw new Error('add error. Array is full.');
}
// 然後判斷索引是否符合要求
if (index < 0 || index > this.size) {
throw new Error(
'insert error. require index < 0 or index > size.'
);
}
// 最後 將指定索引處騰出來
// 從指定索引處開始,所有數組元素全部往後移動一位
// 從後往前移動
for (let i = this.size - 1; i >= index; i--) {
this.data[i + 1] = this.data[i];
}
// 在指定索引處插入元素
this.data[index] = element;
// 維護一下size
this.size++;
}
// 擴展 在數組最前面插入一個元素
unshift(element) {
this.insert(0, element);
}
// 擴展 在數組最後面插入一個元素
push(element) {
this.insert(this.size, element);
}
// 其實在數組中添加元素 就相當於在數組最後面插入一個元素
add(element) {
if (this.size == this.getCapacity()) {
throw new Error('add error. Array is full.');
}
// size其實指向的是 當前數組最後一個元素的 後一個位置的索引。
this.data[this.size] = element;
// 維護size
this.size++;
}
// get
get(index) {
// 不能訪問沒有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size.');
}
return this.data[index];
}
// set
set(index, newElement) {
// 不能修改沒有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('set error. index < 0 or index >= size.');
}
this.data[index] = newElement;
}
// contain
contain(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return true;
}
}
return false;
}
// find
find(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return i;
}
}
return -1;
}
// findAll
findAll(element) {
// 創建一個自定義數組來存取這些 元素的索引
let myarray = new MyArray(this.size);
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
myarray.push(i);
}
}
// 返回這個自定義數組
return myarray;
}
// 刪除指定索引處的元素
remove(index) {
// 索引合法性驗證
if (index < 0 || index >= this.size) {
throw new Error('remove error. index < 0 or index >= size.');
}
// 暫存即將要被刪除的元素
let element = this.data[index];
// 後面的元素覆蓋前面的元素
for (let i = index; i < this.size - 1; i++) {
this.data[i] = this.data[i + 1];
}
this.data[this.size - 1] = undefined;
this.size--;
return element;
}
// 擴展:刪除數組中第一個元素
shift() {
return this.remove(0);
}
// 擴展: 刪除數組中最後一個元素
pop() {
return this.remove(this.size - 1);
}
// 擴展: 根據元素來進行刪除
removeElement(element) {
let index = this.find(element);
if (index !== -1) {
this.remove(index);
}
}
// 擴展: 根據元素來刪除所有元素
removeAllElement(element) {
let index = this.find(element);
while (index != -1) {
this.remove(index);
index = this.find(element);
}
// let indexArray = this.findAll(element);
// let cur, index = 0;
// for (var i = 0; i < indexArray.getSize(); i++) {
// // 每刪除一個元素 原數組中就少一個元素,
// // 索引數組中的索引值是按照大小順序排列的,
// // 所以 這個cur記錄的是 原數組元素索引的偏移量
// // 只有這樣才能夠正確的刪除元素。
// index = indexArray.get(i) - cur++;
// this.remove(index);
// }
}
// @Override toString 2018-10-17-jwl
toString() {
let arrInfo = `Array: size = ${this.getSize()},capacity = ${this.getCapacity()},\n`;
arrInfo += `data = [`;
for (var i = 0; i < this.size - 1; i++) {
arrInfo += `${this.data[i]}, `;
}
arrInfo += `${this.data[this.size - 1]}`;
arrInfo += `]`;
// 在頁面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}
class: Main)
class Main {
constructor() {
let ma = new MyArray(20);
for (let i = 1; i <= 10; i++) {
ma.add(i);
}
/*
* Array: size = 10,capacity = 20
* [1,2,3,4,5,6,7,8,9,10]
*/
console.log(ma.toString());
/*
* Array: size = 11,capacity = 20
* [1,200,2,3,4,5,6,7,8,9,10]
*/
ma.insert(1, 200);
console.log(ma.toString());
/*
* Array: size = 12,capacity = 20
* [-1,1,200,2,3,4,5,6,7,8,9,10]
*/
ma.unshift(-1);
console.log(ma.toString());
/*
* Array: size = 13,capacity = 20
* [-1,1,200,2,3,4,5,6,7,8,9,10,9999]
*/
ma.push(9999);
console.log(ma.toString());
/*
* 8888
*/
ma.set(5, 8888);
console.log(ma.get(5));
this.show(ma.get(5));
/*
* Array: size = 13,capacity = 20
* [-1,1,200,2,3,8888,5,6,7,8,9,10,9999]
* true
* 6
*/
console.log(ma.toString());
this.show(ma.contain(5));
this.show(ma.find(5));
/*
* Array: size = 12,capacity = 20
* [-1,1,200,2,3,8888,6,7,8,9,10,9999]
*/
ma.remove(ma.find(5));
console.log(ma.toString());
/*
* -1
* 9999
* Array: size = 10,capacity = 20
* [1,200,2,3,8888,6,7,8,9,10]
*/
this.show(ma.shift());
this.show(ma.pop());
console.log(ma.toString());
/*
* Array: size = 9,capacity = 20
* [1,200,2,3,6,7,8,9,10]
*/
ma.removeElement(8888);
console.log(ma.toString());
/*
* Array: size = 3,capacity = 20
* [9,10,11]
* Array: size = 12,capacity = 20
* [1,200,2,3,6,7,8,9,10,123456,123456,123456]
*/
ma.add(123456);
ma.add(123456);
ma.add(123456);
this.show(ma.findAll(123456));
console.log(ma.toString());
/*
* Array: size = 9,capacity = 20
* [1,200,2,3,6,7,8,9,10]
*/
ma.removeAllElement(123456);
console.log(ma.toString());
}
// 將內容顯示在頁面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
}
window.onload = function() {
// 執行主函數
new Main();
};
階段五:讓自己的數組成為動態數組
實現思路
自定義數組的侷限性還有容量為固定的大小,因為內部還是使用的 js 的靜態數組,靜態數組的容量從定義開始就是固定的,如果一開始就把容量開的太大了,那麼就會浪費很多的空間,如果容量開的太小了,那就可能存放的空間不夠用。
使用一種解決方案,讓自定義數據的容量可伸縮讓自定義數組變成一個動態的數組,當自定義數組中的空間已經滿了,那就創建一個新的數組,這個數組的容量定義為原來的容量的兩倍,然後將舊數組中的元素全部放到新數組中,以循環的方式放入新數組中。
讓新數組替代掉舊數組,當size == capcity
時創建新數組,容量翻倍,當size == capcity / 2
時創建新數組,容量縮小一倍,最終都會讓新數組替代掉舊數組。使用這種方式會讓整體性能上很有優勢。在 js 的動態數組中選擇是擴容倍數是 1.5,然後無論是 1.5 還是 2 或者 3 都是可以的,只不過是一個參數的選擇,你可以根據使用場景來進行擴容。
自定義數組的這些操作及性能需要分析,也就是要進行一個時間複雜度的分析。後面會進行相關的分析。
代碼實現
(class: MyArray)
class MyArray {
// 構造函數,傳入數組的容量capacity構造Array 默認數組的容量capacity=10
constructor(capacity = 10) {
this.data = new Array(capacity);
this.size = 0;
}
// 獲取數組中的元素實際個數
getSize() {
return this.size;
}
// 獲取數組的容量
getCapacity() {
return this.data.length;
}
// 判斷數組是否為空
isEmpty() {
return this.size === 0;
}
// 給數組擴容
resize(capacity) {
let newArray = new Array(capacity);
for (var i = 0; i < this.size; i++) {
newArray[i] = this.data[i];
}
// let index = this.size - 1;
// while (index > -1) {
// newArray[index] = this.data[index];
// index --;
// }
this.data = newArray;
}
// 在指定索引處插入元素
insert(index, element) {
// 先判斷數組是否已滿
if (this.size == this.getCapacity()) {
// throw new Error("add error. Array is full.");
this.resize(this.size * 2);
}
// 然後判斷索引是否符合要求
if (index < 0 || index > this.size) {
throw new Error(
'insert error. require index < 0 or index > size.'
);
}
// 最後 將指定索引處騰出來
// 從指定索引處開始,所有數組元素全部往後移動一位
// 從後往前移動
for (let i = this.size - 1; i >= index; i--) {
this.data[i + 1] = this.data[i];
}
// 在指定索引處插入元素
this.data[index] = element;
// 維護一下size
this.size++;
}
// 擴展 在數組最前面插入一個元素
unshift(element) {
this.insert(0, element);
}
// 擴展 在數組最後面插入一個元素
push(element) {
this.insert(this.size, element);
}
// 其實在數組中添加元素 就相當於在數組最後面插入一個元素
add(element) {
if (this.size == this.getCapacity()) {
// throw new Error("add error. Array is full.");
this.resize(this.size * 2);
}
// size其實指向的是 當前數組最後一個元素的 後一個位置的索引。
this.data[this.size] = element;
// 維護size
this.size++;
}
// get
get(index) {
// 不能訪問沒有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size.');
}
return this.data[index];
}
// set
set(index, newElement) {
// 不能修改沒有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('set error. index < 0 or index >= size.');
}
this.data[index] = newElement;
}
// contain
contain(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return true;
}
}
return false;
}
// find
find(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return i;
}
}
return -1;
}
// findAll
findAll(element) {
// 創建一個自定義數組來存取這些 元素的索引
let myarray = new MyArray(this.size);
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
myarray.push(i);
}
}
// 返回這個自定義數組
return myarray;
}
// 刪除指定索引處的元素
remove(index) {
// 索引合法性驗證
if (index < 0 || index >= this.size) {
throw new Error('remove error. index < 0 or index >= size.');
}
// 暫存即將要被刪除的元素
let element = this.data[index];
// 後面的元素覆蓋前面的元素
for (let i = index; i < this.size - 1; i++) {
this.data[i] = this.data[i + 1];
}
this.size--;
this.data[this.size] = null;
// 如果size 為容量的一半時 就可以縮容了
// 防止 size 為 0 時 data.length 為1 那麼縮容時也為 0
if (
Math.floor(this.getCapacity() / 2) === this.size &&
Math.floor(this.getCapacity() / 2) !== 0
) {
// 縮容一半
this.resize(Math.floor(this.getCapacity() / 2));
}
return element;
}
// 擴展:刪除數組中第一個元素
shift() {
return this.remove(0);
}
// 擴展: 刪除數組中最後一個元素
pop() {
return this.remove(this.size - 1);
}
// 擴展: 根據元素來進行刪除
removeElement(element) {
let index = this.find(element);
if (index !== -1) {
this.remove(index);
}
}
// 擴展: 根據元素來刪除所有元素
removeAllElement(element) {
let index = this.find(element);
while (index != -1) {
this.remove(index);
index = this.find(element);
}
// let indexArray = this.findAll(element);
// let cur, index = 0;
// for (var i = 0; i < indexArray.getSize(); i++) {
// // 每刪除一個元素 原數組中就少一個元素,
// // 索引數組中的索引值是按照大小順序排列的,
// // 所以 這個cur記錄的是 原數組元素索引的偏移量
// // 只有這樣才能夠正確的刪除元素。
// index = indexArray.get(i) - cur++;
// this.remove(index);
// }
}
// @Override toString 2018-10-17-jwl
toString() {
let arrInfo = `Array: size = ${this.getSize()},capacity = ${this.getCapacity()},\n`;
arrInfo += `data = [`;
for (var i = 0; i < this.size - 1; i++) {
arrInfo += `${this.data[i]}, `;
}
if (!this.isEmpty()) {
arrInfo += `${this.data[this.size - 1]}`;
}
arrInfo += `]`;
// 在頁面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}
class: Main)
class Main {
constructor() {
this.alterLine('MyArray Area');
let ma = new MyArray();
for (let i = 1; i <= 10; i++) {
ma.add(i);
}
/*
* Array: size = 10,capacity = 20
* [1,2,3,4,5,6,7,8,9,10]
*/
console.log(ma.toString());
/*
* Array: size = 11,capacity = 20
* [1,2,3,4,5,6,7,8,99999,9,10]
*/
ma.insert(8, 9999);
console.log(ma.toString());
/*
* Array: size = 10,capacity = 20
* [1,2,3,4,5,6,7,8,9,10]
*/
ma.remove(8);
console.log(ma.toString());
/*
* Array: size = 11,capacity = 20
* [1,2,3,4,5,6,7,8,9,10,9999]
*/
ma.push(9999);
console.log(ma.toString());
}
// 將內容顯示在頁面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割線
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
window.onload = function() {
// 執行主函數
new Main();
};
關於時間複雜度的介紹
在算法和數據結構領域有一個非常重要的內容,使用複雜度分析的方式來查看代碼相應的性能好不好,時間複雜度分析是一個理論化的領域,如果非要非常嚴謹的去研究它,那就會涉及到很多數學方面的內容以及很多新概念,所以只需要對時間複雜度有一個簡單的認識即可。
常見的算法的時間複雜度有O(1)、O(n)、O(lgn)、O(nlogn)、O(n^2)
等等.這個大 O 簡單的來說描述的是算法的運行時間和輸入數據之間的關係。如最簡單的求和,使用 for 循環來進行求和他的時間複雜度就是 O(n)
,這個 n 表示的是求和 for 循環遍歷的次數,這個算法運行的時間和 for 循環遍歷的次數成線性關係,算法和 n 呈線性關係就是O(n)
。
為什麼要用大 O,為什麼要叫做O(n)
?
因為忽略掉了很多的常數,實際時間用線性方程來表示:T = c1*n + c2
,其中的 c1 表示循環遍歷的每一次的時間,遍歷的次數就為 n,c2 表示遍歷之前和之後的代碼執行時間,也就是其它地方的代碼執行消耗的時間如 你要初始化一個變量 sum,如果你寫的是一個方法,你要返回最終結果 sum。
function calcSum(nums) {
let sum = 0;
for (let num of nums) {
sum += num;
}
return sum;
}
如果在具體分析算法的時候把 c1 和 c2 也都具體的分析出來,其實那樣沒有什麼必要,並且在有些情況下也不可能做到,例如不同的語言實現,執行的時間是不等的,因為轉換為機器碼後的指令數也是不一樣的,就算指令都一樣,還有不同系統 cpu 執行的操作也是不一樣的,很難判斷出來 c1 是幾條指令、c2 又是幾條指令,正因為如此所以在分析時間複雜度的時候,是一定要忽略掉這些常數的。
忽略掉這些常數之後,算法一:T = 2*n + 2
、算法二:T = 2000*n + 10000
,他們的時候複雜度都是 O(n)
,換句話來說他們都是線性時間的算法,這些算法消耗的時間和輸入數據的規模是成一個線性關係。
如果有一個算法三:T = 1*n*n + 0
不要認為這個 1 很小、0 也很小,但是它依然是一個O(n^2)
級別的一個算法,也就是說這個算法消耗的時間和這個數據的規模成一個平方關係的,O(n^2)
要比O(n)
性能差很多,因為前者是 N 的平方級別的,雖然第二個算法的常數 2000 和 10000 特別的大,而第三個算法的常數 1 和 0 特別的小,的確如此,假設這個 n 為 10,那麼第三個算法消耗的時間會比第二個算法消耗的時間要長,但是那並不能證明第三個算法比第二個算法性能就要差。因為這個本來就要分具體情況,常數會影響到執行的時間,但是計算時間複雜度就是要忽略掉常數的,因為你實際使用沒有辦法控制所有常數。
這個 O 其實表示的一個漸進的時間複雜度
這個漸進 描述的是當 n 趨近於無窮大的時候,例如第二個算法與第三個算法中的 n 為 3000,那麼很明顯第三個算法肯定要比第二個算法執行時間長,當這個 n 比 3000 還要大的時候,那麼O(n^2)
要比O(n)
的執行時間差的越來越大,所以當 n 越大,一個低階算法的性能就越能體現出來,也就是 n 越大就越能看出來O(n^2)
要比O(n)
快。
在實際使用時可能會用到高階算法 當 n 比較小的時候有可能因為他的常數比較低,反而可能會快於一個低階算法,例如 高階的排序算法 歸併排序、快速排序,這些高階排序法都可以對於比較小的數組轉而使用插入排序這種方式,可以很好的進行優化,通常這種優化能獲得百分之 10 到百分之 15 性能提升,它的眼裡實際上是插入排序算法的常數要比歸併排序、快速排序算法的常數小一些,這樣低階的算法執行時間要比高階的算法執行時間要快一些。
大 O 描述的是一個算法或者操作的一個漸進式的時間複雜度,也就是在說這個算法操作所消耗的時間和輸入數據的規模之間的關係由於大 O 描述的是 n 趨近於無窮大的情況下這個算法的時間複雜度,所以當出現這種算法時T = 2*n*n + 300n + 10
,他的時間複雜度還是O(n^2)
,如果這個算法的時間和 n 成 2 次方關係的話,相應這個算法的時間和 n 成 1 次方的關係會被忽略掉,因為在這種情況下 低階項會被忽略掉,因為當 n 趨近於無窮的時候 低階項起到的作用太小了,所以當 n 無窮大的時候低階項的大小是可以忽略不計的,所以T = 2*n*n + 300n + 10
的時間複雜度還是O(n^2)
。
分析自己的專屬數組的時間複雜度
增:O(n)
刪:O(n)
改:已知索引 O(1),未知索引 O(n)
查找:已知索引 O(1),未知索引 O(n)
其它:未知索引的刪除,需要先查後刪:O(n^2) 未知索引的刪除全部,需要先遍歷再查再刪:O(n^3) 未置索引的查找全部,需要先遍歷:O(n)
綜上分析結果,在使用數組的時候,索引要具有一定語意,這樣就可以直接通過索引來進行操作,如果索引沒有語意,那麼修改和查找會讓性能大幅度降低。
增和刪如果只對最後一個元素進行操作,那麼時間複雜度就為O(1)
,但是動態數組要有 resize 伸縮容量的功能,所以增和刪的時間複雜度依然是O(n)
。
一旦要 resize 了,就需要把整個元素全都複製一遍複製給一片新的空間,雖然說 resize 好像是一個性能很差的操作,但是實際上並不是這樣的,完全使用最壞情況的時間複雜度來分析 resize 是不合理的,應該使用均攤時間複雜度分析來分析 resize,其實 resize 所消耗的性能在整體上沒有那麼的糟糕。
添加操作:時間複雜度為 O(n)
push(e)
:向數組末尾添加一個元素非常簡單,只是簡單的給data[size]
賦值,所以它的時間複雜度為 O(1)
`O(1)的時間複雜度表示這個操作所消耗的時間與 數據的規模是沒有關係的,在分析數組的時間複雜度的時候,那個時間複雜度與這個數組有多少個元素有關係,由於你要遍歷數組中每一個元素,那麼這個時間複雜度就為
O(n)(操作 n 個元素),push 都能在常數時間內完成,所以他的時間複雜度就為
O(1)`(操作 1 個元素)。
unshift(e)
:向數組頭部添加一個元素需要把數組中的元素都往後移動一個位置,所以這涉及到遍歷數組中每一個元素,那麼這個時間複雜度就為O(n)
(操作 n 個元素),雖然最後也有O(1)
(操作 1 個元素)的操作 ,但是在有O(n)
情況時,更低階項O(1)
會被忽略掉。
insert(index, e)
:在 index 索引這個位置插入一個元素當 index 為 0 的時候就和unshift(e)
一樣要向後移動 n 個元素,當 index 為 size(數組中實際元素個數)的時候就和push(e)
一樣只是簡單的給data[size]
賦值,由於這個 index 可以取 0 到 size 中任何一個值,有那麼多種可能性,那麼就可以進行假設在具體操作的時候取到每一個值的概率都是一樣的,在這種情況下進行操作時它所消耗的時間的期望,有些情況 index 會小一些,那麼向後移動位置的元素會多一些,有些情況 index 會大一些,那麼向後移動位置的元素會少一些,平均而言這個算法的時間複雜度為O(n/2)
,但是這個 2 是一個常數,需要忽略常數,所以忽略常數後這個算法的時間複雜度為O(n)
所以最好的情況下時間複雜就為O(1)
,最壞的情況下時間複雜度就為O(n)
,中等的情況下時間複雜度就為O(n/2)
。
添加操作綜合來看是一個O(n)
級別的算法push(e)
:O(1)
,unshift(e)
:O(n)
,insert(index, e)
:O(n/2)=O(n)
。嚴格計算就需要一些概率論上的知識,所以在算法複雜度分析上,通常關注的是某個算法時間複雜度的最壞情況、最糟糕的情況,也會有一些特例,但是在現實生活中你不能按照最好的情況去解決問題。例如 你去上班,公司距離你家的位置最快只需要 5 分鐘,然後你每次去上班只留五分鐘的時間從家裡出來到公司去,你這樣做就是很高概率的讓每次上班都會遲到。例如 在考試時,考試最好的情況是考滿分,然後你每次都考試都以為自己能考滿分的蒙題而不去準備,你這樣做的就是很高概率的讓每次考試都會不及格。在大多數情況下去考慮最好的情況是沒有多大意義的,在算法分析的領域通常會比較嚴格一些去考察最壞的情況。
在添加操作時,自定義的動態數組容量已滿就會進行 resize 操作,這個 resize 操作顯然是O(n)
,因為要給新數組重新賦值一遍。
刪除操作:時間複雜度為 O(n)
removeLast()
:在數組末尾刪除一個元素給末尾的數組元素設置默認值,然後size--
,所以它的時間複雜度為 O(1)
`O(1)`的時間複雜度表示這個操作所消耗的時間與 數據的規模是沒有關係的,他每次只是操作一個數組元素。
removeFirst()
:在數組頭部刪除一個元素需要把數組中的元素都往前移動一個位置,所以這涉及到遍歷數組中每一個元素,那麼這個時間複雜度就為O(n)
(操作 n 個元素),雖然最後也有O(1)
(操作 1 個元素)的操作 ,給末尾的數組元素設置默認值,然後size--
,但是在有O(n)
情況時,更低階項O(1)
會被忽略掉。
remove(index)
:刪除指定索引位置處的元素並返回所以最好的情況下時間複雜就為O(1)
,最壞的情況下時間複雜度就為O(n)
,中等的情況下時間複雜度就為O(n/2)
,忽略常數後這個算法的時間複雜度為O(n)
。
刪除操作綜合來看是一個O(n)
級別的算法removeLast()
:O(1)
,removeFirst()
:O(n)
,remove(index)
:O(n/2)=O(n)
。
在刪除操作時,自定義的動態數組中實際元素個數為其容量的一半時,就會進行 resize 操作,這個 resize 操作顯然是O(n)
,以為因為要給新數組重新賦值一遍。
修改操作:時間複雜度為 O(1)
set(index, e)
:指定索引修改一個元素的值簡單的賦值操作,時間複雜度為O(1)
。數組最大的優勢就是支持隨機訪問,訪問到對應索引的值後就可以修改對應索引的值了,性能超級好。
查詢操作:時間複雜度為 O(n)
get(index)
:指定索引查找一個元素的值簡單的獲取操作,時間複雜度為O(1)
。數組最大的優勢就是支持隨機訪問,只要知道我要訪問的索引是那個數字,就能夠一下子訪問到對應索引的值,性能超級好。
contains(e)
:指定元素來查找,判斷元素是否存在複雜的獲取操作,時間複雜度為O(n)
。需要遍歷整個數組從而找到相同的元素,這個元素在數組中可能找的到也可能找不到,所以最好的情況下時間複雜就為O(1)
,第一個,最壞的情況下時間複雜度就為O(n)
,最後一個或者沒找到,中等的情況下時間複雜度就為O(n/2)
,在中間,忽略常數後這個算法的時間複雜度為O(n)
,分析算法要關注最壞的情況。
find(e)
:指定元素來查找,返回該元素對應的索引複雜的獲取操作,時間複雜度為O(n)
。需要遍歷整個數組從而找到相同的元素,這個元素在數組中可能找的到也可能找不到,所以最好的情況下時間複雜就為O(1)
,第一個,最壞的情況下時間複雜度就為O(n)
,最後一個或者沒找到,中等的情況下時間複雜度就為O(n/2)
,在中間,忽略常數後這個算法的時間複雜度為O(n)
,分析算法要關注最壞的情況。
擴展操作
removeElement(e)
:根據指定元素來進行刪除第一相同的元素首先要進行遍歷操作,然後找到指定元素的索引,最後根據索引來進行刪除操作,刪除操作中又會進行元素位置移動於是就有兩輪循環了,所以時間複雜度為O(n^2)
。
removeAll(e)
::根據指定元素來進行刪除所有相同的元素首先要進行遍歷操作,找到一個元素後就刪除這個元素,會複用到removeElement(e)
,於是有三輪循環了,所以這個操作是O(n^3)
。
findAll(e)
:根據指定元素來進行查找,找到所有的元素首先要進行遍歷操作,找到一個元素後就將元素的索引存起來,所以這個操作是一輪循環,時間複雜度為O(n)
。
總結:均攤複雜度和防止複雜度的震盪
resize 的複雜度分析
不可能每次執行 push 操作的時候都會觸發 resize假如數組有十個空間,你執行 push 操作操作之後,只有第十次才會觸發 resize,並且數組的容量會翻一倍,隨著你添加的越多,數組的容量會呈現倍數增長,那麼觸碰 resize 的概率就越小了,根本不可能每次添加元素就觸發 resize,所以使用最壞的情況去分析 resize 是非常不合理的。
假設當前的 capacity = 10,並且每次添加操作都使用 push那麼在觸發 resize 的時候,一共進行了 11 次 push 操作其實一共進行了 21 次基本賦值的操作(10+10+1),11 添加操作和十次轉移數組元素的操作,因為 resize 裡面會將原數組中的元素賦值給新數組,所以平均每次 push 操作,就約等於進行了 2 次的基本賦值操作。
那可以繼續假設 capacity = n,n+1 次 push 觸發 resize,總共進行了 2n+1 次基本賦值操作,這樣一來平均來講 每次 push 操作,都在進行 2 次的基本賦值操作。
相當於就是將 resize 的時間平攤給了 n+1 次 push 操作從而得到一個結論,平均每次 push 操作,都會進行 2 次基本操作,那麼 push 的時間複雜度不會因為 resize 而變為O(n)
級別的,這就意味著 這樣的均攤計算,addLast 時間複雜度其實是O(1)
級別的,而且他和當前數組中有多少個元素完全沒有關係的,所以在這個例子裡,這樣的均攤計算比計算最壞情況要更有意義,這樣計算複雜度就叫均攤複雜度,也就是說 push 的均攤複雜度為O(1)
。
均攤複雜度(amortized time complexity)
均攤複雜度在很多書中並不會進行介紹,但是在實際工程中這樣的一個思想是很有意義的,一個相對比較耗時的操作,如果能夠保證它不會每次都觸發,那麼這個相對比較耗時的操作相應的時間是可以分攤到其它的操作中來,其實這樣一來,removeLast 操作,它的均攤複雜度是為O(1)
的,雖然它的最壞複雜度是O(n)
級別的,但是它的均攤複雜度也是為O(1)
級別的。
複雜度震盪
同時去看 push 和 removeLast 操作時:如 capacity = n,然後數組容量已經滿了,這時候使用 push 操作,這時候數組就要進行擴容,那麼就會耗費O(n)
的時間,這時候又去使用 removeLast 操作,這時候數組又要進行縮容,那麼又會耗費O(n)
的時間,就這樣一直的 addLast、removeLast,那麼操作都是在耗費O(n)
的時間,這種情況每次都會耗費O(n)
的複雜度這就是複雜度的震盪,明明在均攤的時候是一個O(1)
的級別,但是在一些特殊的情況下猛的一下竄到了O(n)
的級別,從而產生了這個震盪。
這個震盪發生的原因是:removeLast 時 resize 過於激進(Eager),當元素的個數變為容量的二分之一的時候,立馬就讓數組進行縮容,此時整個數組中的元素是滿的,元素的個數和容量是相等的,然後使用一下 push 操作時就又需要擴容了。
解決方案:Lazy當 removeLast 時進行 resize 不急著進行縮容,而是等 size 為當前容量的四分之一時再進行縮容,縮容的大小為原來容量的一半,這樣一來就算立馬進行 push 操作也不會立馬進行擴容操作,也就是將原來的策略改成了只有當size == capcity / 4
時,才將 capacity 減半,原來是size == capcity / 2
時,才將 capacity 減半,通過這樣的策略就防止了複雜度的震盪。要防止容量為 4 時,size 又為 1 時,data.length / 2 為 0
,那樣縮容的容量就為 0 了,這樣一來你任何操作都可能會報異常了。
這種方式其實是非常有意思的方式,在算法的領域有的時候懶一些反而讓算法最終的整體性能更加好,所以有時候是在更懶的時候其實是在改善算法性能,雖然說算法更懶,但是不代表代碼更容易編寫,也不代表代碼量更少,有時候讓算法更懶,其實代碼量會更加的大。
數組背後其實數組這種數據結構背後還有很多東西值得探究,不要小看數組,設計一個數據結構整體上就要看它怎麼具體的存儲數據,在這個具體的存儲的基礎上怎樣進行數據的增刪改查。
代碼示例
(class: MyArray)
class MyArray {
// 構造函數,傳入數組的容量capacity構造Array 默認數組的容量capacity=10
constructor(capacity = 10) {
this.data = new Array(capacity);
this.size = 0;
}
// 獲取數組中的元素實際個數
getSize() {
return this.size;
}
// 獲取數組的容量
getCapacity() {
return this.data.length;
}
// 判斷數組是否為空
isEmpty() {
return this.size === 0;
}
// 給數組擴容
resize(capacity) {
let newArray = new Array(capacity);
for (var i = 0; i < this.size; i++) {
newArray[i] = this.data[i];
}
// let index = this.size - 1;
// while (index > -1) {
// newArray[index] = this.data[index];
// index --;
// }
this.data = newArray;
}
// 在指定索引處插入元素
insert(index, element) {
// 先判斷數組是否已滿
if (this.size == this.getCapacity()) {
// throw new Error("add error. Array is full.");
this.resize(this.size * 2);
}
// 然後判斷索引是否符合要求
if (index < 0 || index > this.size) {
throw new Error(
'insert error. require index < 0 or index > size.'
);
}
// 最後 將指定索引處騰出來
// 從指定索引處開始,所有數組元素全部往後移動一位
// 從後往前移動
for (let i = this.size - 1; i >= index; i--) {
this.data[i + 1] = this.data[i];
}
// 在指定索引處插入元素
this.data[index] = element;
// 維護一下size
this.size++;
}
// 擴展 在數組最前面插入一個元素
unshift(element) {
this.insert(0, element);
}
// 擴展 在數組最後面插入一個元素
push(element) {
this.insert(this.size, element);
}
// 其實在數組中添加元素 就相當於在數組最後面插入一個元素
add(element) {
if (this.size == this.getCapacity()) {
// throw new Error("add error. Array is full.");
this.resize(this.size * 2);
}
// size其實指向的是 當前數組最後一個元素的 後一個位置的索引。
this.data[this.size] = element;
// 維護size
this.size++;
}
// get
get(index) {
// 不能訪問沒有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size.');
}
return this.data[index];
}
// set
set(index, newElement) {
// 不能修改沒有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('set error. index < 0 or index >= size.');
}
this.data[index] = newElement;
}
// contain
contain(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return true;
}
}
return false;
}
// find
find(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return i;
}
}
return -1;
}
// findAll
findAll(element) {
// 創建一個自定義數組來存取這些 元素的索引
let myarray = new MyArray(this.size);
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
myarray.push(i);
}
}
// 返回這個自定義數組
return myarray;
}
// 刪除指定索引處的元素
remove(index) {
// 索引合法性驗證
if (index < 0 || index >= this.size) {
throw new Error('remove error. index < 0 or index >= size.');
}
// 暫存即將要被刪除的元素
let element = this.data[index];
// 後面的元素覆蓋前面的元素
for (let i = index; i < this.size - 1; i++) {
this.data[i] = this.data[i + 1];
}
this.size--;
this.data[this.size] = null;
// 如果size 為容量的一半時 就可以縮容了
// 防止 size 為 0 時 data.length 為1 那麼縮容時也為 0
if (
Math.floor(this.getCapacity() / 2) === this.size &&
Math.floor(this.getCapacity() / 2) !== 0
) {
// 縮容一半
this.resize(Math.floor(this.getCapacity() / 2));
}
return element;
}
// 擴展:刪除數組中第一個元素
shift() {
return this.remove(0);
}
// 擴展: 刪除數組中最後一個元素
pop() {
return this.remove(this.size - 1);
}
// 擴展: 根據元素來進行刪除
removeElement(element) {
let index = this.find(element);
if (index !== -1) {
this.remove(index);
}
}
// 擴展: 根據元素來刪除所有元素
removeAllElement(element) {
let index = this.find(element);
while (index != -1) {
this.remove(index);
index = this.find(element);
}
// let indexArray = this.findAll(element);
// let cur, index = 0;
// for (var i = 0; i < indexArray.getSize(); i++) {
// // 每刪除一個元素 原數組中就少一個元素,
// // 索引數組中的索引值是按照大小順序排列的,
// // 所以 這個cur記錄的是 原數組元素索引的偏移量
// // 只有這樣才能夠正確的刪除元素。
// index = indexArray.get(i) - cur++;
// this.remove(index);
// }
}
// @Override toString 2018-10-17-jwl
toString() {
let arrInfo = `Array: size = ${this.getSize()},capacity = ${this.getCapacity()},\n`;
arrInfo += `data = [`;
for (var i = 0; i < this.size - 1; i++) {
arrInfo += `${this.data[i]}, `;
}
if (!this.isEmpty()) {
arrInfo += `${this.data[this.size - 1]}`;
}
arrInfo += `]`;
// 在頁面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}
(class: Main)
class Main {
constructor() {
this.alterLine('MyArray Area');
let ma = new MyArray();
for (let i = 1; i <= 10; i++) {
ma.add(i);
}
/*
* Array: size = 10,capacity = 20
* [1,2,3,4,5,6,7,8,9,10]
*/
console.log(ma.toString());
/*
* Array: size = 11,capacity = 20
* [1,2,3,4,5,6,7,8,99999,9,10]
*/
ma.insert(8, 9999);
console.log(ma.toString());
/*
* Array: size = 10,capacity = 20
* [1,2,3,4,5,6,7,8,9,10]
*/
ma.remove(8);
console.log(ma.toString());
/*
* Array: size = 11,capacity = 20
* [1,2,3,4,5,6,7,8,9,10,9999]
*/
ma.push(9999);
console.log(ma.toString());
for (let i = 1; i <= 11; i++) {
ma.remove(0);
}
/*
* Array: size = 6,capacity = 10
* [1,7,8,9,10,9999]
*/
console.log(ma.toString());
}
// 將內容顯示在頁面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割線
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
window.onload = function() {
// 執行主函數
new Main();
};