1、包含

那么在很多時(shí)候我們?cè)跀?shù)據(jù)結(jié)構(gòu)中存儲(chǔ)了一些元素，我們需要查找在這些元素中是否包含某個(gè)元素，那么在這種情況下的我們就需要設(shè)置一個(gè)方法返回的是一個(gè)bool型的變量。我們來看看，在我們的這個(gè)數(shù)組中是否存在某一個(gè)元素e，對(duì)于這個(gè)方法來說實(shí)現(xiàn)起來就非常的簡(jiǎn)單，我們只需要從0到size整個(gè)遍歷一遍我們當(dāng)前數(shù)組中所有的元素，在這里要注意這里是小于size，而不是小于capacity容量。如果一但發(fā)現(xiàn)了data[i] == e我們要查找的這個(gè)元素，不用說了我們就返回true，說明這個(gè)數(shù)據(jù)中包含有這個(gè)元素e。循環(huán)結(jié)束之后還沒有找到這個(gè)元素e的話，我們直接返回false就好了，非常容易。

// 是否包含某個(gè)元素
bool AMGArray::contains(int e) {
    for ( int i = 0; i < size; i++ ) {
        if ( data[i] != e ) {
            continue;
        }
        return true;
    }
    return false;
}

2、搜索

在有的時(shí)候我們可能不僅僅想查看是包含這個(gè)元素e，還是不包含這個(gè)元素e，而且想去看一下如果存在這個(gè)元素e的話，這個(gè)元素一對(duì)應(yīng)的索引是多少。相應(yīng)我們就可以設(shè)置一個(gè)方法，這個(gè)方法的命名為find進(jìn)行這個(gè)尋找，對(duì)于這個(gè)尋找的結(jié)果我返回的是一個(gè)int 型對(duì)應(yīng)的就是索引，在這里同學(xué)們要注意有可能找不到這個(gè)元素，如果找不到這個(gè)元素了我們返回一個(gè)特殊的無效的索引，通常的這個(gè)特殊的無效索引定義成是-1。我們想象一下，由于合法的索引一定是大于等于零的，所以如果我返回一個(gè)-1他一定是一個(gè)非法的索引，此時(shí)就表示在我們的這個(gè)數(shù)據(jù)中沒有找到這個(gè)元素e。相應(yīng)的這個(gè)邏輯也非常簡(jiǎn)單，整體呢其實(shí)和contains的這個(gè)邏輯完全一樣，只不過在data[i] == e找到了這個(gè)元素e的時(shí)候，我們返回的是這個(gè)索引。那么循環(huán)結(jié)束我們?nèi)绻€沒有找到這個(gè)元素的話，我們返回的是-1。

// 查找數(shù)組中元素所在的索引，如果不存在元素e，則返回-1
int AMGArray::find(int e) {
    for ( int i = 0; i < size; i++ ) {
        if ( data[i] != e ) {
            continue;
        }
        return i;
    }
    return -1;
}

3、怎么刪除

這樣我們就又完成了兩個(gè)新的方法，一個(gè)是contains，另一個(gè)是find，最后我們來看一下如何從數(shù)組中刪除元素，在這里頭呢我們主要來看一下，如果我們指定了某一個(gè)索引。比如說現(xiàn)在我們的這個(gè)數(shù)組中有六十六、七十七、八十八、九十九、一百這樣的五個(gè)元素，現(xiàn)在我想刪除索引為1的元素。也就是現(xiàn)在我想刪除掉這個(gè)77的話，應(yīng)該怎么做呢？那么回憶一下，之前我們?cè)诮o數(shù)組插入一個(gè)元素的時(shí)候，那么插入這個(gè)位置以及它之后的所有的元素都要向右移給新插入的這個(gè)元素騰位置。那么相應(yīng)的這個(gè)刪除的過程呢其實(shí)就是一個(gè)反向的過程，我們要?jiǎng)h除的這個(gè)索引之后的所有的元素都向左移，這樣一來那就相當(dāng)于把這個(gè)待刪除索引位置的元素給擠跑了。那么具體是怎么操作的呢？可以想象一下我們要?jiǎng)h除索引為1的元素，那么我們就從索引為二的元素開始，將索引為2的這個(gè)元素移動(dòng)到索引為1的這個(gè)元素中。不過這里回一下我們?cè)僦vinsert的這個(gè)添加操作的時(shí)候，當(dāng)時(shí)說的也是移動(dòng)，可是我們實(shí)際代碼的實(shí)現(xiàn)呢就是一次賦值，那么我們?cè)谶@個(gè)刪除的過程中也是這樣的的。其實(shí)就是讓這個(gè)data[1] = data[2]，也就是其實(shí)我們做的是這樣的一件事情?？梢钥船F(xiàn)在77沒了變成了88，不過索引2這個(gè)位置它的元素依然是88，那么這個(gè)循環(huán)繼續(xù)。下面呀我們要做的就是要索引2這個(gè)位置的元素等于索引3這個(gè)位置的元素，所以99被賦值到了這個(gè)data[2]的位置。那么相應(yīng)的下面100就會(huì)賦值到這個(gè)data[3]的位置，那么再下面如果還有元素的話我們就要把data[5]的元素賦值到data[4]這個(gè)位置中來。但是呢data[5]已經(jīng)沒有元素了,所以此時(shí)我們這個(gè)刪除任務(wù)已經(jīng)結(jié)束了。77已經(jīng)從這個(gè)數(shù)組中刪除了，不過刪除以后同學(xué)們千萬不要忘記了我們要維護(hù)一下這個(gè)size，此時(shí)我們整個(gè)數(shù)組都少了一個(gè)元素，所以這個(gè)size要進(jìn)行一次減減。那么在這種情況下注意，我之前說過這個(gè)size，它既表示我們數(shù)組中有多少個(gè)元素，同時(shí)它也指向了第一個(gè)沒有元素的位置，也就是如果我們?cè)傧蛘麄€(gè)數(shù)組的末尾添加1個(gè)元素的話，我們應(yīng)該添加到data[size]這個(gè)位置。但是我現(xiàn)在這樣做，刪除了指定的元素之后，data[size]還指向了一個(gè)100，這樣有沒有什么問題呢？可以想象一下，其實(shí)這樣是完全沒有問題的，因?yàn)閷?duì)于我們的用戶訪問我們的數(shù)組來說，他如果想使用某一個(gè)索引拿到某一個(gè)元素，會(huì)判斷這個(gè)索引的合法性。那么對(duì)這個(gè)索引呢合法性來說，它必須大于等于零并且小于size的。也就是說對(duì)用戶來說他永遠(yuǎn)看不到data[size]的值是多少，所以在這里呢我們根本不用費(fèi)心去管size減減之后，這個(gè)size還指向了100，這個(gè)100會(huì)不會(huì)對(duì)我們產(chǎn)生什么影響，其實(shí)是任何影響都沒有的。

刪除元素

4、代碼實(shí)現(xiàn)刪除

下面我們就來具體的編程實(shí)現(xiàn)一下從數(shù)據(jù)中刪除元素。我們的這個(gè)數(shù)組類中再添加1個(gè)新的算法，那么這個(gè)方法remove(int index)傳入的是一個(gè)index索引，那么在這里可能注意到了對(duì)于這個(gè)remove函數(shù)，我設(shè)置了一個(gè)返回值int。這是因?yàn)橥ǔ碇v，對(duì)于刪除元素這個(gè)功能來說，都會(huì)把我刪除的那個(gè)元素是什么給返回回來，以留給用戶備用用。那么在我們之前ppt的例子中如果我想刪除索引為1相應(yīng)的這個(gè)元素的話。執(zhí)行完remove這個(gè)操作之后，我們?cè)谶@個(gè)數(shù)組中就已經(jīng)不在有77這個(gè)元素了，但是77這個(gè)元素會(huì)被我們的這個(gè)remove函數(shù)返回回來。

// 刪除某個(gè)位置上的元素
int AMGArray::remove(int index) {
    if ( index < 0 || index >= size ) {
        cout << "remove Index 不合法 " << index << endl;
        return -1;
    }
    // 從index位置開始往后賦值
    for (int i = index; i < size - 1; i++) {
        data[i] = data[i + 1];
    }
    int res = data[index];
    data[size - 1] = 0;  // 游蕩元素
    size--;
    return res;
}

那么具體在邏輯上也非常簡(jiǎn)單，首先依然要判斷一下這個(gè)index相應(yīng)的合法性。如果這個(gè)index小于零或者大于等于size的話，這個(gè)index就是非法的，我們投出一個(gè)異常，否則的話，后面我們做的事情就是之前ppt中所講的這個(gè)過程。有一點(diǎn)區(qū)別就是我們首先要把我們帶刪除的這個(gè)元素存起來，這就是正確刪除元素后返回的值。那么之后我們?cè)賮磉M(jìn)行我們整個(gè)這個(gè)刪除了邏輯，這個(gè)刪除的邏輯跟著我們之前ppt所講解的就是一次循環(huán)，對(duì)于index之后的每一個(gè)元素都讓他向前挪一個(gè)位置，這個(gè)過程其實(shí)就將我們的data[index]這個(gè)位置的元素給擠出去了。那么之后大家不要忘記了維護(hù)一下size這個(gè)變量，減減就可以了。這樣我們就完成了整個(gè)兒從數(shù)組中刪除某一個(gè)索引位置的元素這樣的功能，依然是和我們之前的insert一樣，我們完成了這個(gè)remove。

5、其它的刪除

我們就可以再為用戶創(chuàng)建一些快捷的方法，比如說，我們就可以創(chuàng)建一個(gè)removeFirst(intindex)的方法，那么對(duì)于這個(gè)方法，只需要調(diào)用我們的remove(0)就好了，這個(gè)函數(shù)是從數(shù)組中刪除掉的一個(gè)元素。我們也可以創(chuàng)建一個(gè)叫做removeLast(int index)這樣的一個(gè)方法，我們只需要調(diào)用remove(size-1)，也就是刪除數(shù)組中最后一個(gè)元素所。要運(yùn)行這兩個(gè)方法我們就要保證我們的數(shù)組不能為空，因?yàn)槲覐臄?shù)組中既不能刪除第一個(gè)元素，也不能刪除最后一個(gè)元素，因?yàn)橐粋€(gè)空數(shù)組沒有元素。不過其實(shí)我們?cè)谶@兩個(gè)方法中不需要進(jìn)行這樣的判斷，是因?yàn)槲覀冊(cè)谡{(diào)用remove的時(shí)候我們把這個(gè)0和size-1傳進(jìn)去了，在remove中，會(huì)對(duì)index的合法性進(jìn)行一個(gè)判斷。想像一下，如果我們數(shù)組為空的話，那么remvoe(0)進(jìn)行運(yùn)行，此時(shí)我們的size等于0，會(huì)拋出異常。那么相應(yīng)的如果我們r(jià)emoveLast的話，如果我數(shù)組為空傳進(jìn)去的也在此相當(dāng)于是0 - 1等于-1，所以拋出異常。那么我們復(fù)用了remove這個(gè)方法非常方便的完成了，這樣兩個(gè)快捷的刪除操作。

// 刪除尾部元素
int AMGArray::removeLast() {
    return remove(size - 1);
}

// 刪除第一個(gè)元素
int AMGArray::removeFirst() {
    return remove(0);
}

最后對(duì)于我們的數(shù)組中我們還想涉及這樣的一個(gè)接口，咱們這個(gè)方法叫做removeElement(inte)，就是有的時(shí)候我們可能不是要?jiǎng)h除某一個(gè)指定位置的元素，而是想看一下我們的數(shù)組中是否有某個(gè)元素，如果有這個(gè)元素的話，就把他刪除。那么這個(gè)方法其實(shí)也非常容易的可以組合我們之前寫的邏輯來完成。首先我們要做的事情就是進(jìn)行一下fined操作，尋找一下e這個(gè)元素的在我們數(shù)組中是否存在，如果存在的話，可以想象一下這個(gè)索引就不等于-1。所以我的這個(gè)索引如果不等于-1的話，要做的就是直接把這個(gè)位置的元素給刪除就好了，那么這個(gè)方法做的事情就是從數(shù)組中刪除元素e。在這里可能會(huì)為什么這個(gè)removeElement我不返回刪除的元素呢？因?yàn)橛脩粼谡{(diào)這個(gè)函數(shù)的時(shí)候，就已經(jīng)知道自己要?jiǎng)h除的是哪一個(gè)元素了，我們就不需要再把這個(gè)e返回給用戶了。對(duì)于這個(gè)方法來說，有很多設(shè)計(jì)上的考量，我們可以進(jìn)行一定的增強(qiáng)，比如說現(xiàn)在我設(shè)計(jì)了這個(gè)方法他的語意，就是如果在我們的這個(gè)數(shù)組中有這個(gè)e的話就刪除，如果沒有這個(gè)e，那就什么都不需要干，那么可能有一些同學(xué)希望用戶在調(diào)用完這個(gè)removeElement之后，知道是不是從數(shù)組中真的刪掉了某個(gè)元素e。那么為了完成這個(gè)需求呢我們就可以返回給用戶一個(gè)布爾值，對(duì)于這個(gè)邏輯呢有興趣的可以修改一下。另外一點(diǎn)值得注意的就是空，對(duì)于我們現(xiàn)在的這個(gè)數(shù)組來說，是允許存放重復(fù)的元素的。那么在這種情況下，我們當(dāng)前的這個(gè)removeElement其實(shí)只刪除了一個(gè)e，在做完這個(gè)動(dòng)作之后并不能保證我們整個(gè)數(shù)組中不在存在元素一了。那么這本身呢也是我設(shè)計(jì)這個(gè)方法的初衷。換句話說我設(shè)計(jì)的這個(gè)方法，就是如果數(shù)組中存在元素e的話那么只刪除1個(gè)，如果你想設(shè)計(jì)一個(gè)方法刪除掉數(shù)組中所有的元素e的話，那么我建議呢可以再新設(shè)計(jì)一個(gè)方法叫做removeAllElement。

// 從數(shù)組中刪除元素e
void AMGArray::removeElement(int e) {
    int index = find(e);
    if ( -1 == index ) {
        return;
    }
    remove(index);
}

6、總結(jié)

其實(shí)對(duì)于我們的fined的函數(shù)也是有同樣的問題的，我們完全可以設(shè)計(jì)一個(gè)叫做finedAll這樣的一個(gè)函數(shù)，來找到我們數(shù)組中所有的元素e所在的索引。那么其實(shí)都已經(jīng)是設(shè)計(jì)上的問題了，不在是我們這個(gè)數(shù)據(jù)結(jié)構(gòu)中的上的問題了，所以你如果有興趣的話可以繼續(xù)完善我們整個(gè)的數(shù)組類。

現(xiàn)在我們的數(shù)組類還有諸多的局限性，我們?cè)诤罄m(xù)會(huì)解決這些局限性。

刪除