线性表的顺序存储结构定义

是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中。

插入操作

指在表的第i (1≤i≤n+1)个位置，插入一个新元素e，使长度为n的线性表 (a1，…，ai-1，ai，…，an) 变成长度为n+1的线性表（a1，…,ai-1，e，ai，…，an）。

删除操作

指将表的第i(1≤i≤n)个元素删去，使长度为n的线性表 (a1，…,ai-1，ai，ai+1，…，an)，变成长度为n-1的线性表(a1，…,ai-1， ai+1，…，an)。

编制C/C++程序，利用顺序存储方式实现下列功能：从键盘输入数据建立一个线性表（整数），并输出该线性表；然后根据屏幕提示，进行数据的插入或删除等操作，并在插入或删除数据后输出线性表。

#include <iostream>
using namespace std;

#define MAXSIZE 1000        //根据需要设置为线性表可能达到的最大长度
typedef int ElemType;        //数组元素的类型为ElemType，将ElemType定义为int类型

//顺序表的建立：定义了一个名为SqList的结构体
typedef struct
{
    ElemType *data;        //存储空间的基地址
    int length;            //顺序表的当前长度（实际已经存入的元素个数）
}SqList; 

//顺序表的初始化
void InitList(SqList &L) 
{
    L.data = new ElemType[MAXSIZE];        //构造一个新的顺序表L，并为之分配大小为MAXSIZE的空间
    if (L.data == NULL)
    {
        cout << "存储空间分配失败！\n";
        exit(0);        //存储空间分配失败退出
    }
    L.length = 0;
    cout << "顺序表初始化完成！\n";
}

//通过顺序表读入值的方式，创建顺序表
void Create(SqList &L, int n) 
{
    ElemType e;
    for (int i = 0; i < n; i++) 
    {
        cin >> e;
        L.data[i] = e;
        L.length++;
    }
}

//顺序表插入值
/*在指定位置插入InsList(&L,i,e);                                *
 *要求在表的第i个位置，插入一个值为e的新元素。*/
void Insert(SqList &L, int i, ElemType e)
{
    if ((i < 1) || (i > L.length + 1))
    {
        cout << "插入地址不合法！\n";
        exit(0);
    }
    if (L.length == MAXSIZE)
    {
        cout << "存储空间已满！\n";
        exit(0);
    }
    for (int j = L.length - 1; j >= i - 1; j--)
    {
        L.data[j + 1] = L.data[j];
    }        //以上是从后比较的方法，可以边比较边移动
    L.data[i - 1] = e;
    ++L.length;
}
/*删除数据元素Delete(&L,i)
将顺序表的第i个元素删去*/
void Delete(SqList &L, int i)
{
    if ((i < 1) || (i > L.length))
    {
        cout << "删除地址不合法！\n";
        exit(0);
    }
    for (int j = i; j <= L.length - 1; j++)
    {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
}
/*遍历并输出顺序表Print(L);
按照顺序表中元素的顺序依次输出每个元素的值*/
void Print(SqList L)
{
    if (L.length == 0)
    {
        cout << "线性表长度为0\n";
        exit(0);
    }
    for (int k = 0; k < L.length; k++)
    {
        if (k == L.length - 1)
        {
            cout << L.data[k];
        }
        else
        {
            cout << L.data[k] << ' ';
        }
    }
 }
/*清空顺序表ClearList(L);
清空顺序表：即表示将顺序表设置为长度为0的空表*/
void ClearList(SqList &L)
{
    L.length = 0;
}
/*判断顺序表是否存满IsListEmpty(L)
判断顺序表是都为空：如果空返回1，否则返回0*/
int IsListEmpty(SqList L)
{
    if (L.length == 0)
        return 1;
    else
        return 0;
}
/*求顺序表的长度ListLength(L)
要求返回线性表L的长度*/
int ListLength(SqList L)
{
    return L.length;
}
/*按序号查找GetData(L,I,e)
要求查找线性表L中第i个数据元素*/
void GetData(SqList L, int i, ElemType &e)
{
    if ((i < 1) || (i > L.length))
    {
        cout << "删除地址不合法！\n";
        exit(0);
    }
    e = L.data[i - 1];
}
/*按值查找Locate(L,e)
要求查找线性表中与给定值e相等的数据元素，
若在表L中找到与e相等的元素，则返回该元素在顺序表中的序号；
若找不到，则返回一个“空序号“，如'0'                                        */
int Locate(SqList L, ElemType e)
{
    int i = 1;
    while ((i <= L.length) && (L.data[i - 1] != e))
        i++;
    if (i <= L.length)        //找到，返回位序i+1
        return i;
    else
        return 0;        //未找到，返回位序0
}
int main()
{
    int n, i;
    ElemType e;
    cout << "请输入线性表的整数个数n：";
    cin >> n;
    SqList L;        //给线性表分配内存空间
    InitList(L);        //顺序表的初始化
    cout << "请输入线性表的各个元素：";
    Create(L, n);        //通过顺序表读入值的方式，创建顺序表
    cout << "原线性表如下：\n";
    Print(L);        //输出顺序表
    cout << "\n请输入要插入的元素及其所要插入的位置：";
    cin >> e >> i;
    Insert(L, i, e);
    cout << "插入之后的数组：\n";
    Print(L);
    cout << "\n请输入要删除的元素的位置：";
    cin >> i;
    Delete(L, i);
    cout << "删除之后的数组：\n";
    Print(L);
    cout << "\n请输入要查找的位置：";
    cin >> i;
    GetData(L, i, e);
    cout << "该值是：" << e;
    cout << "\n请输入要查找的值：";
    cin >> e;
    i = Locate(L, e);
    cout << "该值所在的位置是：" << i;
    system("pause");
    return 0;
}