定义结构体

#define MaxSize 10
#define ElemType int
typedef struct {
    ElemType *data;
    int length;
    int size;
}SqList;

初始化

// 初始化顺序表
bool InitList(SqList &L,int s){
    L.data = new ElemType[s];
    if (L.data == NULL){
        return false;
    }
    L.size = s;
    L.length = 0;

    return true;
}

输出顺序表中所以元素

//输出顺序表
void printList(SqList &L){

    for (int i = 0; i < L.length; ++i) {
        cout << L.data[i] << endl;
    }
}

删除顺序表中最小的元素,并返回元素的值,把最后一个元素填充进去

//删除最小元素并返回被删元素的值
bool deleteMin(SqList &L,ElemType &value){
    if (L.length ==0){
        return false;
    }
    value = L.data[0];
    int pos = 0;
    for (int i = 0; i < L.length; ++i) {
        if (L.data[i] < value){
            pos = i;
            value = L.data[i];
        }
    }
    L.data[pos] = L.data[L.length-1];;
    L.length--;
    return true;
}

元素逆置

//元素逆置
bool reverseList(SqList &L){
    if (L.length == 0){
        return false;
    }
    int t;

    for (int i = 0; i < L.length /2; ++i) {
        t = L.data[i];
        L.data[i] = L.data[L.length -1 -i];
        L.data[L.length-1-i] = t;
    }

    return true;

}

除值为x的元素 时间复杂度O(N) 空间复杂度O(1)

//删除值为x的元素 时间复杂度O(N) 空间复杂度O(1)
bool delList_x(SqList &L,int x){
    if (L.length == 0){
        return false;
    }
    int len=0;
    for (int i = 0; i < L.length; ++i) {
        if (L.data[i] != x){
            L.data[len] = L.data[i];
//            if (i!=L.length-1)len++;
            len++;
        }
    }
    L.length = len-1;

    return true;

}

删除S到T区间内的元素,且S<T

bool delListStoT(SqList &L,int s,int t){
    if (L.length == 0 || s >= t) return false;
    int len=0;
    for (int i = 0; i < L.length; ++i) {
        if (L.data[i] <= s || L.data[i] >= t){
            L.data[len] = L.data[i];
            len++;
        }
    }
    L.length = len-1;
    return true;
}

运行测试

int main() {
    SqList  sqList;
    if (InitList(sqList,10)) cout << "初始化成功" << endl;
    else cout << "初始化失败" << endl;
    for (int i=1; i<=9; i++) {
        sqList.data[i-1]=i;
        sqList.length++;
    }
    cout << "InitList ____________" << endl;
    printList(sqList);
    int value;
    deleteMin(sqList,value);
    cout << "deleteMin ____________" << endl;
    cout << value << endl;
    cout << endl;
    printList(sqList);

    reverseList(sqList);
    cout << "reverseList ____________" << endl;
    printList(sqList);

    if (delList_x(sqList,5)){
        cout << "delList_x ____________" << endl;
        printList(sqList);
        cout << endl << sqList.length <<endl;
    }
    if (delListStoT(sqList,3,7)){
        cout << "delListStoT ____________" << endl;
        printList(sqList);
        cout << endl << sqList.length <<endl;
    }

    return 0;
}
Office365 微信公众号
最后修改:2021 年 07 月 21 日 06 : 50 PM
如果您觉得我的文章有帮助,请随意赞赏!