线性表算法设计题（九）

题目

已知长度为n的线性表A采用顺序存储结构，请写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法可删除线性表中所有值为item的数据元素。

算法思想

用k记录顺序表A中不等于item的元素个数，k初始为0.可以采用类似建立顺序表的思想，从前向后遍历顺序表，查找值不为item的元素，如果找到，则利用原表的空间记录值不为item的元素，同时是k增1。遍历结束后，顺序表中前k个元素即为值不为item的元素，最后将顺序表的长度置为k。

完整代码

#include <iostream>
using namespace std;

//已知长度为n的线性表A采用顺序存储结构，请写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法可删除线性表中所有值为item的数据元素。

#define MAXSIZE 100
typedef int ElemType;
typedef struct{ 
    ElemType *elem;                 //存储空间的基地址 
    int length;                     //当前长度 
}SqList;                            //顺序表的结构类型为SqList 
 
//创建
void CreateList(SqList &L)
{
    int i;
    L.elem = new ElemType[MAXSIZE];
    if(! L.elem){
        cout << "ERROR！" << endl;
    }
    cout << "请输入线性表的长度:" << endl; 
    cin >> L.length;
    cout << "请依次输入表中元素：" << endl;
    for(i = 0; i < L.length; i ++){
        cin >> L.elem[i];
    }
    //cout<<"创建完成！"<<endl;
}
 
void DeleteItem(SqList &A, ElemType item){
    //删除顺序表A中所有值为item的元素 
    int k = 0;                               //k记录值不等于item的元素个数 
    for(int i = 0; i < A.length; i ++){      //从前向后扫描顺序表 
        if(A.elem[i] != item){               //查找值不为item的元素 
            A.elem[k] = A.elem[i];           //利用原表的空间记录值不为item的元素 
            k ++;                            //不等于item的元素增1 
        }
    }
    A.length = k;                            //顺序表A的长度等于k 
}


//输出表
void display(SqList L)
{
    int i;
    cout << '[';
    for(i = 0; i <L.length; i ++){
        if(i == L.length-1){
            cout << L.elem[i];
        }
        else{
            cout << L.elem[i] << ',';
        }
    }
    cout << ']' << endl;
}

int main(){
    SqList L;
    int item;
 
    CreateList(L);
    cout << "当前线性表为：" << endl;
    display(L);
 
    cout << "请输入需要删除的item值：" << endl;
    cin >> item;
 
    DeleteItem(L,item);
 
    cout << "选择删除后线性表为：" << endl;
    display(L);

    return 0;
}

结果显示

TIM图片20191027195144.png