线性表的基本应用(二)：顺序表的删除操作

要求：

首先我们需要建立一个顺序存储的、由整数构成的线性表，然后将表中的所有偶数元素删除，并估算操作的时间复杂度。

思路：

常规方法：遍历线性表，若当前元素为偶数，则调用顺序表的删除操作删除，预估操作的时间复杂度为O(n²)。
常规方法的改进：可以在创建顺序表对象时，记录下偶数项的下标，从而免去遍历“找”偶数项的过程，或者干脆将本问题转化成将表中的奇数值复制到另一个顺序表中的操作。

常规方法的代码实现如下：

#include <bits/stdc++.h>
using namespace std;

class SqList
{
public:
    SqList(int cnt);
    bool insertElement(int pos,int num); //pos代表插入到第几个元素之前
    bool deleteElement(int pos); //pos代表删除第几个元素
    void deleteEvenNum(); //删除偶数
    void show();
    ~SqList();
private:
    int * pHead;
    int cnt;
};

SqList::SqList(int cnt)
{
    this->pHead = new int[cnt];
    for (int i = 0; i<cnt; i++)
    {
        printf("请输入线性表的第%d个元素：",i+1);
        scanf("%d",pHead+i);
    }
    this->cnt = cnt;
}

void SqList::show()
{
    if (cnt == 0)
    {
        printf("线性表为空，无法遍历！\n");
        return;
    }
    for (int i = 0; i<cnt; i++)
    {
        printf("%d ",*(pHead+i));
    }
    printf("\n");
}

bool SqList::insertElement(int pos,int num)
{
    if (pos>cnt+1 || pos<1)
    {
        printf("插入的位置非法！\n");
        return false;
    }
    for (int i = cnt-1; i>=pos-1; i--)
    {
        *(pHead+i+1) = *(pHead+i);
    }
    *(pHead+pos-1) = num;
    cnt++;
    return true;
}

bool SqList::deleteElement(int pos)
{
    if (pos>cnt || pos<1)
    {
        printf("删除的位置非法！\n");
        return false;
    }
    for (int i = pos-1; i<cnt; i++)
    {
        *(pHead+i) = *(pHead+i+1);
    }
    cnt--;
    return true;
}

//删除偶数
void SqList::deleteEvenNum()
{
    for (int i = 0; i<cnt; )
    {
        if (*(pHead+i)%2 == 0)
        {
            deleteElement(i+1);
            continue; //注意成功删除元素后，i应该维持原值
        }
        i++;
    }
}

SqList::~SqList()
{
    delete [] pHead;
    pHead = NULL;
}

int main()
{
    SqList sqList(5);
    sqList.show();
    sqList.deleteEvenNum();
    sqList.show();
    return 0;
}

测试结果如下：