线性表的应用2（删除顺序表中的元素）

一时失言乱红尘 2022-07-26 01:26 133阅读 0赞

一、写一算法，从顺序表中删除自第i个元素开始的k个元素。 （按照下标删除）

方法：循环控制删除即可

代码实现：

#include <iostream>
    #include <cstdio>
    #include <cstdlib>
    
    #define OVERFLOW -2
    #define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
    #define LISTINCREMENT 10  //线性表存储空间的分配增量
    
    using namespace std;
    
    typedef int ElemType;
    
    typedef struct
    {
        ElemType *elem; //存储空间基址
        int length; //当前长度
        int listsize; //当前分配的存储容量（以sizeof（ElemType）为单位）
    } SeqList;
    
    int InitList(SeqList &L)
    {
        L.elem=(ElemType *)calloc(LIST_INIT_SIZE,sizeof(ElemType));
        if(!L.elem) exit(OVERFLOW);
        L.length=0;
        L.listsize=LIST_INIT_SIZE;
        return 1;
    }
    
    int ListInsert(SeqList &L, int i,ElemType e)
    {
        ElemType *newbase,*p,*q;
        if(i<1||i>L.length+1) return 0;
        if(L.length>=L.listsize)
        {
    
            newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
            if(!newbase) exit(OVERFLOW);
            L.elem=newbase;
            L.listsize+=LISTINCREMENT;
        }
        q=&(L.elem[i-1]);
        for(p=&(L.elem[L.length-1]); p>=q; --q)
        {
            *(p+1)=*p;
        }
        *q=e;
        ++L.length;
        return 1;
    }
    
    int ListDelet(SeqList &L,int i,ElemType &e)
    {
        ElemType *p,*q;
        if((i<1)||(i>L.length))
            return 0;
        p=&(L.elem[i-1]);
        e=*p;
        q=L.elem+L.length-1;
        for(++p; p<=q; ++p)
            *(p-1)=*p;
        --L.length;
        return 1;
    }
    
    void Output(SeqList &L)
    {
        for(int i=0; i<L.length; i++)
        {
            printf("%d ",L.elem[i]);
        }
        printf("\n");
    }
    
    int main()
    {
        SeqList L;
        int flag,n,n1,k,e;
        while(scanf("%d",&n)!=EOF)
        {
            flag=InitList(L);
            if(flag==1)
            {
                for(int i=0; i<n; i++)
                {
                    scanf("%d",&e);
                    flag=ListInsert(L,i+1,e);
                    if(flag==0)
                    {
                        cout<<"Inser Fail"<<endl;
                    }
                }
                cout<<"The List is:"<<endl;
                Output(L);
                scanf("%d%d",&n1,&k);
                for(int i=1;i<=k;i++)
                {
                    flag=ListDelet(L,n1,e);
                    if(flag==0)
                    {
                        cout<<"Delete Fail"<<endl;
                        break;
                    }
                }
                Output(L);
                if(flag==1)
                {
                    cout<<"Delete sucessfully"<<endl;
                }
            }
            else
            {
                cout<<"Can not do it!"<<endl;
            }
        }
        return 0;
    }

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

方法：一边遍历，一边按照元素删除

代码实现：

#include <iostream>
    #include <cstdio>
    #include <cstdlib>
    
    #define OVERFLOW -2
    #define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
    #define LISTINCREMENT 10  //线性表存储空间的分配增量
    
    using namespace std;
    
    typedef int ElemType;
    
    typedef struct
    {
        ElemType *elem; //存储空间基址
        int length; //当前长度
        int listsize; //当前分配的存储容量（以sizeof（ElemType）为单位）
    } SeqList;
    
    int InitList(SeqList &L)
    {
        L.elem=(ElemType *)calloc(LIST_INIT_SIZE,sizeof(ElemType));
        if(!L.elem) exit(OVERFLOW);
        L.length=0;
        L.listsize=LIST_INIT_SIZE;
        return 1;
    }
    
    int ListInsert(SeqList &L, int i,ElemType e)
    {
        ElemType *newbase,*p,*q;
        if(i<1||i>L.length+1) return 0;
        if(L.length>=L.listsize)
        {
    
            newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
            if(!newbase) exit(OVERFLOW);
            L.elem=newbase;
            L.listsize+=LISTINCREMENT;
        }
        q=&(L.elem[i-1]);
        for(p=&(L.elem[L.length-1]); p>=q; --q)
        {
            *(p+1)=*p;
        }
        *q=e;
        ++L.length;
        return 1;
    }
    
    int ListDelet(SeqList &L,int i,ElemType &e)
    {
        ElemType *p,*q;
        if((i<1)||(i>L.length))
            return 0;
        p=&(L.elem[i-1]);
        e=*p;
        q=L.elem+L.length-1;
        for(++p; p<=q; ++p)
            *(p-1)=*p;
        --L.length;
        return 1;
    }
    
    void Output(SeqList &L)
    {
        for(int i=0; i<L.length; i++)
        {
            printf("%d ",L.elem[i]);
        }
        printf("\n");
    }
    
    int main()
    {
        SeqList L;
        int flag,n,n1,k,e;
        while(scanf("%d",&n)!=EOF)
        {
            flag=InitList(L);
            if(flag==1)
            {
                for(int i=0; i<n; i++)
                {
                    scanf("%d",&e);
                    flag=ListInsert(L,i+1,e);
                    if(flag==0)
                    {
                        cout<<"Inser Fail"<<endl;
                    }
                }
                cout<<"The List is:"<<endl;
                Output(L);
                scanf("%d",&k);
                for(int i=0; i<n; i++)
                {
                    if(L.elem[i]==k)
                    {
                        flag=ListDelet(L,i+1,e);  //第i个元素的下标是i+1
                        i--;
                        if(flag==0)
                        {
                            cout<<"Delete Fail"<<endl;
                            break;
                        }
                    }
                }
                Output(L);
                if(flag==1)
                {
                    cout<<"Delete sucessfully"<<endl;
                }
            }
            else
            {
                cout<<"Can not do it!"<<endl;
            }
        }
        return 0;
    }