Experiment 2: write a program and verify that the linear table sequence represents all operations

This blog is from teacher YanWeiMin's book 《 data structure 》, I see there is an experiment two today , I wrote it immediately , And share it in the blog , Code from Clion The compiler is fully executable . The complete title is as follows ：

Topic reproduction

Write a main program to design and verify all the operations represented by the linear table sequence
( At least algorithm 2.3、2.4、2.5), And design an algorithm to delete all values greater than min And less than max The elements of .

Topic analysis

1. 2.3 Is the insertion of a linear table
2. 2.4 Is the deletion of a linear table
3. 2.5 Is a linear table lookup
4. I designed a delete function （ Two methods are given ）

2.3 Linear table insertion

Linear table insertion , It's the process of moving back , We just write according to the book .

Status ListInsert_Sq(SqList &L,int i,ElementType e){
    
    if(i<1 || i>L.length+1) {
    
        return ERROR;

    }

    if(L.length >= L.listsize){
    
        ElementType * newbase = (ElementType *) realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElementType));
        if(!newbase) exit(OVERFLOW);
        L.elem = newbase;
        L.listsize += LISTINCREMENT;
    }
    ElementType *q = &(L.elem[i-1]);
    for(ElementType *p = &(L.elem[L.length-1]);p>=q;--p){
    
        *(p+1) = *p;
    }
    *q = e;
    ++L.length;
    return OK;
}

From the back to the front , That's it .

2.3 Linear table deletion

Delete from front to back

Status ListDelete_Sq(SqList &L,int i,ElementType &e){
    
    if((i<1)|| (i>L.length)) return ERROR;
    int* p = &(L.elem[i-1]);
    e = *p;
    int* q = L.elem + L.length - 1;
    for(++p;p<=q;++p)*(p-1)=*p;
    --L.length;
    return OK;
}

2.5 Linear table lookup

Find this value directly . Let's go through it from beginning to end .

Status compare(ElementType a,ElementType b){
    
    return a==b?0:1;
}
int LocateElem_Sq(SqList L,ElementType e,Status (*compare)(ElementType,ElementType)){
    
    int i = 1;
    int* p  = L.elem;


    while(i<=L.length && !(*compare)(*p++,e)){
    
        ++i;

    }
    if(i<=L.length) return i;
    else return 0;
}

2.6 Design your own functions Delete range

For this topic, I first use the common O(n^2) Complexity is calculated , Then we trade space for time O(n) The complexity of , So these two algorithms are given one by one . I think the second kind is easier to understand .

Status Delete_minToMax(SqList &L,ElementType min,ElementType max){
    
    while(1){
    
        int flag = true;
        int i;
        for(i =0;i<L.length;i++){
    
            if(L.elem[i]>min && L.elem[i]<max){
    
                flag = false;
                break;
            }
        }
        for(int j= i+1;j<L.length;j++){
    
            L.elem[j-1] = L.elem[j];
        }

        if(flag) break;
        else L.length--;
    }
    return TRUE;
}

Status Delete_minToMax2(SqList &L,ElementType min,ElementType max){
    
    SqList L_cp;
    InitList_Sq(L_cp);
    for(int i=0;i<L.length;i++){
    
        if(L.elem[i]>min && L.elem[i]<max) continue;
        L_cp.elem[L_cp.length++] = L.elem[i];
    }
    L.length = 0;
    for(int i=0;i<L_cp.length;i++){
    
        L.elem[L.length++] = L_cp.elem[i];
    }
    return TRUE;
}

2.7 summary

The topic as a whole is not difficult , Mainly some small details need to be handled separately , such as L.length When to delete and subtract . These are all planned in advance , Only in this way can we do problems quickly .

Complete code

#include<iostream>
#define ERROR -1
#define OVERFLOW -1
#define TRUE 1
#define OK 1
#define LISTINCREMENT 10
#define LIST_INIT_SIZE 100
typedef int Status;
typedef int ElementType;
using namespace std;
typedef struct{
    
    ElementType *elem;
    int listsize;
    int length = 0;
}SqList;

//2.3
Status ListInsert_Sq(SqList &L,int i,ElementType e){
    
    if(i<1 || i>L.length+1) {
    
        return ERROR;

    }

    if(L.length >= L.listsize){
    
        ElementType * newbase = (ElementType *) realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElementType));
        if(!newbase) exit(OVERFLOW);
        L.elem = newbase;
        L.listsize += LISTINCREMENT;
    }
    ElementType *q = &(L.elem[i-1]);
    for(ElementType *p = &(L.elem[L.length-1]);p>=q;--p){
    
        *(p+1) = *p;
    }
    *q = e;
    ++L.length;
    return OK;
}


Status ListDelete_Sq(SqList &L,int i,ElementType &e){
    
    if((i<1)|| (i>L.length)) return ERROR;
    int* p = &(L.elem[i-1]);
    e = *p;
    int* q = L.elem + L.length - 1;
    for(++p;p<=q;++p)*(p-1)=*p;
    --L.length;
    return OK;
}
Status compare(ElementType a,ElementType b){
    
    return a==b?0:1;
}
int LocateElem_Sq(SqList L,ElementType e,Status (*compare)(ElementType,ElementType)){
    
    int i = 1;
    int* p  = L.elem;


    while(i<=L.length && !(*compare)(*p++,e)){
    
        ++i;

    }
    if(i<=L.length) return i;
    else return 0;
}

Status InitList_Sq(SqList &L){
    
    L.elem = (ElementType *)malloc(LIST_INIT_SIZE*sizeof(ElementType));
    if(!L.elem) exit(OVERFLOW);
    L.length = 0;
    L.listsize = LIST_INIT_SIZE;
    return OK;
}

// And design an algorithm to delete all values greater than min And less than max The elements of .

/*Status Delete_minToMax(SqList &L,ElementType min,ElementType max){ while(1){ int flag = true; int i; for(i =0;i<L.length;i++){ if(L.elem[i]>min && L.elem[i]<max){ flag = false; break; } } for(int j= i+1;j<L.length;j++){ L.elem[j-1] = L.elem[j]; } if(flag) break; else L.length--; } return TRUE; }*/

Status Delete_minToMax2(SqList &L,ElementType min,ElementType max){
    
    SqList L_cp;
    InitList_Sq(L_cp);
    for(int i=0;i<L.length;i++){
    
        if(L.elem[i]>min && L.elem[i]<max) continue;
        L_cp.elem[L_cp.length++] = L.elem[i];
    }
    L.length = 0;
    for(int i=0;i<L_cp.length;i++){
    
        L.elem[L.length++] = L_cp.elem[i];
    }
    return TRUE;
}
int main(){
    


    //test1:
    SqList  L;

    int flag  = InitList_Sq(L);
    flag = ListInsert_Sq(L,1,1);
    flag = ListInsert_Sq(L,1,2);
    flag = ListInsert_Sq(L,1,3);
    flag = ListInsert_Sq(L,1,4);
    flag = ListInsert_Sq(L,1,5);
    flag = ListInsert_Sq(L,1,6);
    cout << "test1:" << endl;
    for(int i=0;i<L.length;i++){
    
        cout << L.elem[i] << " ";
    }
    cout << endl;

    //test2:
    int x;

    flag = ListDelete_Sq(L,2,x);
    cout << "test2:";
    cout << endl << "Delete Element:" << x << endl;

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

    //test3: find == 4
    cout << endl << "test3: find4:" << endl;
    int pos;
    pos = LocateElem_Sq(L,4,compare);
    cout << L.elem[pos] << endl;


    //test4:delete 2 - 5
    cout << "test4:" << endl <<"(2,5)Delete before:" << endl;
    for(int i=0;i<L.length;i++){
    
        cout << L.elem[i] << " ";
    }
    cout << endl << "after Deleted :" << endl;
    /*flag = Delete_minToMax(L,2,5);*/
    flag = Delete_minToMax2(L,2,5);
    for(int i=0;i<L.length;i++){
    
        cout << L.elem[i] << " ";
    }
    return 0;
}