顺序表基本操作的实现

一、顺序表的初始化

算法步骤：

（1）为顺序表L动态分配一个预定大小的数组空间，使elem指向这段空间的基地址。

（2）将表的当前长度设为0。

typedef int ElemType;
typedef struct
{
    ElemType *elem;
    int length;
} SqList;
 
//顺序表的初始化
void InitList(SqList &L)
{
    L.elem=new ElemType[MAXSIZE];
    if(!L.elem)
    {
        cout<<"存储分配失败！"<<endl;
    }
    L.length=0;
    cout<<"顺序表初始化成功！"<<endl;
}

二、顺序表的取值

算法步骤：

（1）判断指定序号i的值是否合理（1<=i<=L.length）。

（2）若i值合理，则将第i个元素L.elem[i-1]赋给参数e，通过e返回第i个数据元素的值。

//顺序表的取值
int GetElem(SqList L,int i,ElemType &e)
{
    if(i<1||i>L.length)//判断i值是否合理，若不合理，返回ERROR -1
    {
        cout<<"i值不合法！"<<endl;
        return -1;
    }
    e=L.elem[i-1];//elem[i-1]单元储存第i个数据元素,把第i个元素数据赋值给e
    cout<<"取值成功！"<<endl;
    return e;//通过e返回第i个元素数据
 
}

三、顺序表的查找

算法步骤：

（1）从第一个元素起，依次和e比较，若找到与e相等的元素L.elem[i]，则查找成功，返回该元素的序号i+1。

（2）若查遍整个顺序表都没有找到，则查找失败，返回0。

//顺序表的查找
int LocateElem(SqList L,ElemType e)
{
    //在顺序表L中查找值为e的数据元素，返回其序号
    for(int i=0; i<L.length; i++)
    {
        if(L.elem[i]==e)
        {
            cout<<"查找成功！"<<endl;
            return i+1;
        }
    }
    cout<<"查找失败！"<<endl;
    return 0;
}

四、顺序表的插入

算法步骤：

（1）判断位置i是否合法（1<=i<=n+1），如不合法则返回EREROR。

（2）判断顺序表的存储空间是否已满

（3）将第n个至第i个位置的元素依次后移一位，空出第i个位置。

（4）将要插入的新元素e放入第i个位置。

（5）表长加1。

//顺序表的插入
void ListInsert(SqList &L,int i,ElemType e)
{
    //在顺序表L中第i个位置插入新的元素e
    if((i<1)||(i>L.length+1))//i值的合法范围是1<=i<=L.length+1
    {
        cout<<"ERROR"<<endl;
    }
    if(L.length==MAXSIZE)
    {
        cout<<"ERROR"<<endl;
    }
    for(int j=L.length-1; j>=i-1; j--)
    {
        L.elem[j+1]=L.elem[j];//插入位置及之后的元素后移
        L.elem[i-1]=e;//将元素e放入第i个位置
        ++L.length;//表长加1
    }
    cout<<"插入成功！"<<endl;
 
}

五、顺序表的删除

算法步骤：

（1）判断删除位置i是否合法（1<=i<=n），若不合法则返回ERROR。

（2）将第i+1个至第n个的元素依次向前移动一个位置（i=n时无需移动）。

（3）表长减1。

//元素的删除
void ListDelete(SqList &L,int i)
{
    //在顺序表L中删除第i个元素，i值的合法范围是1<=i<=L.length
    if((i<1)||(i>L.length))
    {
        cout<<"i值不合法"<<endl;
    }
    for(int j=i; j<=L.length-1; j++)
    {
        L.elem[j-1]=L.elem[j];//被删除元素之后的元素前移
    }
    --L.length;//表长减1
    cout<<"删除成功！"<<endl;
}

六、顺序表的输入输出

//输入
void ListInput(SqList &L,int n)
{
    cout<<"请依次输入"<<n<<"个数据"<<endl;
    int e;
    for(int i=1; i<=n; i++)
    {
        cout<<"请输入第"<<i<<"个数据：";
        cin>>e;
        L.elem[i-1]=e;
        ++L.length;
    }
 
}
//输出
void ListOutput(SqList &L)
{
    cout<<"- - - - - -"<<endl;
    for(int i=0; i<L.length; i++)
    {
        cout<<"第"<<i+1<<"个元素的值为："<<L.elem[i]<<endl;
    }
    cout<<"- - - - - -"<<endl;
}

七、完整代码

#include <iostream>
#define MAXSIZE 100
using namespace std;
 
typedef int ElemType;
typedef struct
{
    ElemType *elem;
    int length;
} SqList;
 
//顺序表的初始化
void InitList(SqList &L)
{
    L.elem=new ElemType[MAXSIZE];
    if(!L.elem)
    {
        cout<<"存储分配失败！"<<endl;
    }
    L.length=0;
    cout<<"顺序表初始化成功！"<<endl;
    cout<<"- - - - - -"<<endl;
}
//输入
void ListInput(SqList &L,int n)
{
    cout<<"请依次输入"<<n<<"个数据"<<endl;
    int e;
    for(int i=1; i<=n; i++)
    {
        cout<<"请输入第"<<i<<"个数据：";
        cin>>e;
        L.elem[i-1]=e;
        ++L.length;
    }
 
}
//输出
void ListOutput(SqList &L)
{
    cout<<"- - - - - -"<<endl;
    for(int i=0; i<L.length; i++)
    {
        cout<<"第"<<i+1<<"个元素的值为："<<L.elem[i]<<endl;
    }
    cout<<"- - - - - -"<<endl;
}
//顺序表的取值
int GetElem(SqList L,int i,ElemType &e)
{
    if(i<1||i>L.length)//判断i值是否合理，若不合理，返回ERROR -1
    {
        cout<<"i值不合法！"<<endl;
        return -1;
    }
    e=L.elem[i-1];//elem[i-1]单元储存第i个数据元素,把第i个元素数据赋值给e
    cout<<"取值成功！"<<endl;
    return e;//通过e返回第i个元素数据
 
}
//顺序表的查找
int LocateElem(SqList L,ElemType e)
{
    //在顺序表L中查找值为e的数据元素，返回其序号
    for(int i=0; i<L.length; i++)
    {
        if(L.elem[i]==e)
        {
            cout<<"查找成功！"<<endl;
            return i+1;
        }
    }
    cout<<"查找失败！"<<endl;
    return 0;
}
//顺序表的插入
void ListInsert(SqList &L,int i,ElemType e)
{
    //在顺序表L中第i个位置插入新的元素e
    if((i<1)||(i>L.length+1))//i值的合法范围是1<=i<=L.length+1
    {
        cout<<"ERROR"<<endl;
    }
    if(L.length==MAXSIZE)
    {
        cout<<"ERROR"<<endl;
    }
    for(int j=L.length-1; j>=i-1; j--)
    {
        L.elem[j+1]=L.elem[j];//插入位置及之后的元素后移
        L.elem[i-1]=e;//将元素e放入第i个位置
        ++L.length;//表长加1
    }
    cout<<"插入成功！"<<endl;
 
}
//元素的删除
void ListDelete(SqList &L,int i)
{
    //在顺序表L中删除第i个元素，i值的合法范围是1<=i<=L.length
    if((i<1)||(i>L.length))
    {
        cout<<"i值不合法"<<endl;
    }
    for(int j=i; j<=L.length-1; j++)
    {
        L.elem[j-1]=L.elem[j];//被删除元素之后的元素前移
    }
    --L.length;//表长减1
    cout<<"删除成功！"<<endl;
}
int main()
{
    SqList L;
    InitList(L);
//给顺序表录入元素，并输出
    cout<<"会有人看见吗，哈哈"<<endl;
    cout<<"小兄弟想给顺序表输入多少个数值？";
    int n;
    cin>>n;
    ListInput(L,n);
    ListOutput(L);
 
//插入
//    int i;
//    cout<<"输入插入位置i：";
//    cin>>i;
//    int e;
//    cout<<"输入插入数值e：";
//    cin>>e;
//    ListInsert(L,i,e);
//    ListOutput(L);
 
//取值
//    int i;
//    cout<<"请输入要取元素的序号：";
//    cin>>i;
//    int e=GetElem(L,i,e);
//    cout<<e<<endl;
 
//查找
//    int e;
//    cout<<"请输入要查找元素的值：";
//    cin>>e;
//    int n=LocateElem(L,e);
//    cout<<"元素"<<e<<"在第"<<n<<"个位置"<<endl;
 
//删除
    cout<<"请输入需要删除元素的序号：";
    int i;
    cin>>i;
    ListDelete(L,i);
    ListOutput(L);
 
}