1、顺序表的定义

将表中元素一个接一个的存入一组连续的存储单元中，这种存储结构是顺序结构，采用顺序存储结构的线性表简称为“ 顺序表”。 顺序表的存储特点是：只要确定了起始位置，表中任一元素的地址都通过下列公式得到：

Loc(ai)=Loc(a1)+(i−1)∗L,1≤i≤n

其中，L是元素占用存储单元的长度。
2、顺序表的基本操作

（1）初始化：建立一个空的顺序表；

（2）新建：新建一个顺序表；

（3）合并顺序表：将两个顺序表合并，并去掉重复元素；

（4）按元素查找：查找顺序表中是否含有指定元素；

（5）按位置查找：查找指定位置的元素；

（6）求顺序表的长度：计算顺序表的元素个数；

（7）指定位置插入：在指定位置插入元素；

（8）删除元素：删除指定位置的元素；

（9）判空：判断是否是空的顺序表；

（10）清空顺序表；

（11）显示：显示当前顺序表的所有数据。
3、C++编程实现类定义顺序表

（1）顺序表的头文件 sequencelist.h
#ifndef SEQUENCELIST_H
#define SEQUENCELIST_H

#define MAXSIZE 20//最大存储容量
typedef int ElemType;

class SqList
{
public:
    SqList();//
    SqList(ElemType elems[],int n);//有参构造器
    ~SqList();//
    bool CreatList();//新建一个顺序表
    bool UnionList(SqList L1,SqList L2);
    int LocateElem(ElemType e);//按元素查找：成功则返回元素的序号（从1开始）,失败则返回0
    int ListLength();//顺序表的长度
    bool GetElem(int i, ElemType& e);//查找第i个位置的元素
    bool ListInsert(int i,ElemType e);//在第i个位置插入元素
    bool ListDelete(int i,ElemType& e);//删除第i个位置的元素
    bool ListEmpty();//判空
    void clearList();//清空顺序表
    void display();//显示当前的顺序表

private:
    ElemType data[MAXSIZE];//下标从0开始，但是对线性表的操作中的下标从1开始：第1个元素其实就是下标为0的元素
    int length;
};

#endif // SEQUENCELIST_H

（2）顺序表的源文件 sequencelist.cpp
#include "sequencelist.h"
#include <iostream>
using namespace std;

SqList::SqList()//初始化
{
    length=0;//
}

SqList::SqList(ElemType elems[],int n)//有参构造器
{
    if(n>MAXSIZE)
    {
        cout<<"传入的顺序表长度超出最大范围，只接收了前"<<MAXSIZE<<"个元素"<<endl;
        length=MAXSIZE;
    }
    else
        length=n;//

    for(int i=0;i<length;i++)
        data[i]=elems[i];
}

SqList::~SqList()
{

}

bool SqList::CreatList()
{

    cout<<"插入多少个元素(0-20)？"<<endl;
    cin>>length;
    if(length<0||length>MAXSIZE)
    {
        length=0;
        return false;
    }
    for(int i=1;i<=length;i++)
    {
//        cout<<"请输入顺序线性表的第"<<i<<"个元素：";
//        cin>>data[i-1];
        data[i-1]=i;
    }
    return true;
}

bool SqList::UnionList(SqList L1,SqList L2)
{
    int i,j;
    for(i=0;i<L1.length;i++)
    {
        data[i]=L1.data[i];
    }

    for(j=0;j<L2.length;j++)
        if(L1.LocateElem(L2.data[j])==0)
        {
            if(i>=MAXSIZE)
                return false;
            data[i]=L2.data[j];
            i++;
        }
    length=i;
    return true;
}

int  SqList::LocateElem(ElemType e)//成功则返回元素的序号（从1开始）,失败则返回0
{
    for(int i=0;i<length;i++)
        if(data[i]==e)
            return i+1;
    return 0;
}

int  SqList::ListLength()
{
    return length;
}

bool SqList::GetElem(int i, ElemType& e)
{
    if(length==0 || i<1|| i>length)
        return false;
    e=data[i-1];
    return true;
}

bool SqList::ListInsert(int i,ElemType e)
{
    if(length==MAXSIZE || i<1|| i>length+1)//线性表满，或者i的范围不在合理范围内时返回错误
        return false;
    if(i<=length)//不在表尾
    {
        //插入位置的后续元素后移一位
        for(int k=length-1;k>=i-1;k--)
            data[k+1]=data[k];// 倒序挪动位置，避免覆盖问题
    }
    data[i-1]=e;//插入元素
    length++;
    return true;
}

bool SqList::ListDelete(int i,ElemType& e)
{
    if(length==0 || i<1|| i>length)//线性表空，或者i的范围不在合理范围内时返回错误
        return false;
    e=data[i-1];//取出元素
    if(i<length)//不在表尾
    {
        //插入位置的后续元素前移一位
        for(int k=i-1;k<length-1;k++)
            data[k]=data[k+1];// 正序挪动位置，避免覆盖问题
    }
    length--;
    return true;
}

bool SqList::ListEmpty()
{
    if (length==0)
        return true;
    return false;
}

void SqList::clearList()
{
    length=0;
}

void SqList::display()
{
    for(int i=0;i<length;i++)
        cout<<data[i]<<"  ";
    cout<<endl;
}

(3)主函数 main.cpp
#include <iostream>
#include "sequencelist.h"
using namespace std;

int main()
{
    SqList list;
    int num;
    ElemType elem;
    bool flag;

    cout<<"            1.顺序表的创建和显示"<<endl;
    if(!list.CreatList())
        cout<<"顺序表创建失败！"<<endl;
    else
        cout<<"顺序表创建成功！    "<<endl;
    //顺序表的显示
    list.display();
    cout<<endl<<endl;

    cout<<"            2.按元素查找"<<endl;
    num=list.LocateElem(3);
    cout<<"3是顺序表的第"<<num<<"个元素"<<endl<<endl<<endl;

    cout<<"            3.按位置查找"<<endl;
    list.GetElem(4,elem);
    cout<<"顺序表的第4个元素是:"<<elem<<endl<<endl<<endl;

    cout<<"            4.顺序表的插入"<<endl;
    if(list.ListInsert(2,10))
        cout<<"插入成功！在第2个位置插入10后：    "<<endl;
    else
        cout<<"插入失败！"<<endl;
    list.display();
    cout<<endl<<endl;

    cout<<"            5.删除元素"<<endl;
    list.ListDelete(5,elem);
    cout<<"删掉第5个元素:"<<elem<<endl;
    cout<<"该表的长度为:"<<list.ListLength()<<endl;
    list.display();
    cout<<endl<<endl;

    cout<<"            6.清空顺序表"<<endl;
    cout<<"清空顺序表前-----";
    if(!list.ListEmpty())
    {
        cout<<"当前顺序表不是空表！"<<endl;
        list.clearList();
        cout<<"清空顺序表后-----";
        if(list.ListEmpty())
            cout<<"当前顺序表是空表！"<<endl;
    }
    cout<<endl<<endl;

    cout<<"            7.合并顺序表"<<endl;
    ElemType elems1[8]={0,1,2,3,4,5,6,7};
    ElemType elems2[9]={5,6,7,8,9,10,11,1,12};

    SqList list1={elems1,8};
    SqList list2={elems2,9};
    SqList list3;
    cout<<"合并前的两个表为："<<endl;
    list1.display();
    list2.display();
    flag=list3.UnionList(list1,list2);
    if(!flag)
        cout<<"合并后，顺序表的长度超过最大范围"<<endl;
    cout<<"该表的长度为:    "<<list3.ListLength()<<endl;
    list3.display();
    return 0;
}

另外，线性表的结构体定义见：

https://blog.csdn.net/qq_38236355/article/details/100160419

顺序表的类定义见：

https://blog.csdn.net/qq_38236355/article/details/100161003

对于顺序存储的长度为N的线性表，删除第一个元素和插入最后一个元素的时间复杂度分别对应为O(N)和O(1)。


若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用顺序表最节省时间。


线性表L=（a1, a2 ,……，an ）用一维数组表示，假定删除线性表中任一元素的概率相同（都为1/n），则删除一个元素平均需要移动元素的个数是(n-1)/2

顺序表是指线性表的顺序表示，指的是用一组地址连续的存储单元依次存储线性表的数据元素。只要确定了顺序表的起始位置，顺序表的任一数据元素都可以随机存取，线性表的顺序存储结构是一种随机存取的存储结构。在这点上与高级程序设计语言中的数组十分相似，因此通常用数组来描述数据结构中的顺序存储结构。接下来是顺序表的12个基本操作和这12个操作在主函数中的检验。
声明：本程序是在VS2015中实现的，在其他编译器中如果有些许差错还请自行手动更改。


一. 头文件和宏定义



//--保存为constant.h--
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
using namespace std;
#define TRUE   1
#define FALSE  0    
#define OK     1
#define ERROR  0
#define INFEASIBLE -1
#define OVERFLOW   -2
typedef  int   Status;
typedef  int ElemType;


二.接下来是12个基本操作 

//—顺序表的动态分配存储结构— 

//保存成header.h



#include"constant.h"
#define LIST_INIT_SIZE 100
#define LISTINCREMENT   10
typedef struct
{
    ElemType  *elem;
    int      length;
    int    listsize;
}SqList;




//1.构造顺序表
Status InitList(SqList &L)
{
    L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if (!L.elem)
        return ERROR;
    L.length = 0;
    L.listsize = LIST_INIT_SIZE;
    return OK;
}



//2.销毁顺序表
Status DestroyList(SqList &L)
{
    if (L.elem)
        free(L.elem);
    if (L.elem == NULL)
        return OK;
    else
        return ERROR;
}




//3.清空顺序表
void ClearList(SqList &L)
{
    L.length = 0;
}



//4.判断顺序表是否空表
Status ListEmpty(SqList L)
{
    if (L.length == 0)
        return ERROR;
    else
        return OK;
}



//5.顺序表求表长
Status ListLength(SqList L)
{
    return L.length;
}



//6.顺序表的取元素
Status GetElem(SqList L)
{
    int i, e;    //取出顺序表中第i个元素e
    cout << "请输入要取的元素的位序:" << endl;
    cin >> i;
    if (i<1 || i>L.length)
        return ERROR;
    else
        e = L.elem[i - 1];
    cout << "要取出的第" << i << "个元素是" << e << endl;
    return OK;
}




//辅助函数
Status compare(int e1, int e2)
{
    if (e1 == e2)
        return OK;
    else
        return ERROR;
}

//7.顺序表的定位
Status LocateElem(SqList L)
{
    int e, i = 1;
    cout << "请输入要定位的元素e" << endl;
    cin >> e;
    while (i <= L.length&&L.elem[i - 1] != e)
    {
        i++;
    }
    if (i > L.length)
        return ERROR;
    else
        cout << "要定位的元素的位序为" << i << endl;
        return i;
}




//8.返回前驱
Status PriorElem(SqList L)
{
    int cur_e, pre_e, i = 1;
    int *p;
    p = L.elem + 1;//将第二个元素的地址赋值给p
    cout << "请输入顺序表中第二到表尾的任何一个数:" << endl;
    cin >> cur_e;
    while(i < L.length && compare(cur_e, L.elem[i - 1]))
    {
        p++;
        i++;
    }
    if (i > L.length)
        return ERROR;
    else
    {
        pre_e = L.elem[i];  //注意i
        cout << "它的前驱元素是" << pre_e << endl;
        return pre_e;//将此元素返回给要调用的函数
    }        
}




//9.返回后继
Status NextElem(SqList L)
{
    int cur_e, next_e, i = 0;//i的初值是第一个元素的位序
    cout << "请输入第一到倒数第二个任意一个元素:" << endl;
    cin >> cur_e;
    int *p = L.elem;//第一个元素的地址赋值给p
    while (i < L.length && !compare(cur_e, L.elem[i]))
    {
        p++;
        i++;
    }
    if (i == L.length)
    {
        return ERROR;
    }
    else
    {
        next_e = *(++p);
        cout << "它的后继元素是" << next_e << endl;
        return next_e;//将此元素返回给主函数
    }
}




//10.插入元素
Status ListInsert(SqList &L)
{
    ElemType *p, *q, *newbase;
    int i, e;//在位置i插入元素e
    cout << "请输入要插入的元素的位置i:" << endl;
    cin >> i;
    cout << "请输入要插入的元素的数值e:" << endl;
    cin >> e;
    if (i<1 || i>L.length)
        return ERROR;
    if(L.length>=L.listsize)
    {
        if (!(newbase = (ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType))))
            exit(0);//分配存储空间失败
        L.elem = newbase;//新基址
        L.listsize += LISTINCREMENT;//增加存储容量
    }
    q = L.elem + i - 1;//q为插入位置
    for (p = L.elem + L.length - 1; p >= q; --p)
    {
        *(p + 1) = *p;//给插入位置之后的元素赋值达到之后元素后移一位的效果
    }
    *q = e;//插入e
    ++L.length;
    return OK;
}



//11.删除元素
Status ListDelete(SqList &L)
{
    int i,e;
    cout << "请输入要删除的元素的位置i:" << endl;
    cin >> i;
    if (i<1 || i>L.length)//i值不合法
        return ERROR;
    ElemType *p, *q;
    p = L.elem + i - 1;//p为被删除元素的位置
    e = *p;            //被删除元素的值赋给e
    cout << "被删除的元素是" << e << endl;
    q = L.elem + L.length - 1;//q是表尾元素的位置
    p = p + 1;
    for ( ; p <= q; p++)
        *(p - 1) = *p;
    L.length--;  //表长减一
    return OK;
}



//12.遍历
Status ListTraverse(SqList L)
{
    ElemType *p = L.elem;
    int i;
    for (i = 1; i <= L.length; i++)
        cout<<*p++<<"  ";
    cout << endl;
    return OK;
}


三.主函数中检验



#include "stdafx.h"
#include "header.h"
int main()
{
    int m,n;
    SqList L;
    InitList(L);
    cout << "……顺序表初始化……" << endl;
    cout << "请输入顺序表的长度n:"<<endl;
    cin >> n;
    for (m = 1; m <= n; m++)
    {
        cout << "请输入第"<<m<<"个元素的值:"<<endl;
        cin >> L.elem[m - 1];
        L.length++;
    }
    cout << "顺序表的长度为" << L.length << endl;
    cout << "顺序表中的元素为:"<<endl;
    ListTraverse(L);
    cout << "…………判断顺序表是否空表…………" << endl;
    if (ListEmpty(L) == 1)
        cout << "顺序表非空" << endl;
    else
        cout << "顺序表为空" << endl;
    cout << "…………顺序表中取元素操作…………" << endl;
    GetElem(L);
    cout << "…………顺序表中元素的定位…………" << endl;
    LocateElem(L);
    cout << "…………顺序表中元素的前驱…………" << endl;
    PriorElem(L);
    cout << "…………顺序表中元素的后继…………" << endl;
    NextElem(L);
    cout << "…………顺序表元素插入测试…………" << endl;
    ListInsert(L);
    cout << "此时顺序表中的元素为:"<<endl;
    ListTraverse(L);
    cout << "…………顺序表元素删除测试…………" << endl;
    ListDelete(L);
    cout << "此时顺序表中的元素为:" << endl;
    ListTraverse(L);
    cout << "恭喜您成功完成顺序表的所有功能！！！！" << endl;
    return 0;
}

顺序表是指线性表的顺序表示，指的是用一组地址连续的存储单元依次存储线性表的数据元素。只要确定了顺序表的起始位置，顺序表的任一数据元素都可以随机存取，线性表的顺序存储结构是一种随机存取的存储结构。在这点上与高级程序设计语言中的数组十分相似，因此通常用数组来描述数据结构中的顺序存储结构。

接下来是顺序表的12个基本操作和这12个操作在主函数中的检验。

 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
#include<stdio.h> 
#define TRUE   1
#define FALSE  0    
#define OK     1
#define ERROR  0
#define INFEASIBLE -1
#define OVERFLOW   -2
typedef  int   Status;
typedef  int ElemType;

#define LIST_INIT_SIZE 100
#define LISTINCREMENT   10
typedef struct
{
    ElemType  *elem;
    int      length;
    int    listsize;
}SqList;

//1.构造顺序表
Status InitList(SqList &L)
{
    L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if (!L.elem)
        return ERROR;
    L.length = 0;
    L.listsize = LIST_INIT_SIZE;
    return OK;
}

//2.销毁顺序表
Status DestroyList(SqList &L)
{
    if (L.elem)
        free(L.elem);
    if (L.elem == NULL)
        return OK;
    else
        return ERROR;
}
//3.清空顺序表
void ClearList(SqList &L)
{
    L.length = 0;
}
//4.判断顺序表是否空表
Status ListEmpty(SqList L)
{
    if (L.length == 0)
        return ERROR;
    else
        return OK;
}
//5.顺序表求表长
Status ListLength(SqList L)
{
    return L.length;
}
//6.顺序表的取元素
Status GetElem(SqList L)
{
    int i, e;    //取出顺序表中第i个元素e
    printf("请输入要取的元素的位序:\n");
    scanf("%d",&i);
    if (i<1 || i>L.length)
        return ERROR;
    else
        e = L.elem[i - 1];
    printf("要取出的第%d个元素是%d\n",i,e);
    return OK;
}
//辅助函数
Status compare(int e1, int e2)
{
    if (e1 == e2)
        return OK;
    else
        return ERROR;
}

//7.顺序表的定位
Status LocateElem(SqList L)
{
    int e, i = 1;
    printf("请输入要定位的元素：\n");
    scanf("%d",&e);
    while (i <= L.length&&L.elem[i - 1] != e)
    {
        i++;
    }
    if (i > L.length)
        return ERROR;
    else
        printf("要定位的元素的位序为%d\n",i);
        return i;
}

//8.返回前驱
Status PriorElem(SqList L)
{
    int cur_e, pre_e, i = 1;
    int *p;
    p = L.elem + 1;//将第二个元素的地址赋值给p
    printf("请输入顺序表中第二到表尾的任何一个数:\n");
    scanf("%d",&cur_e);
    while(i < L.length && compare(cur_e, L.elem[i - 1]))
    {
        p++;
        i++;
    }
    if (i > L.length)
        return ERROR;
    else
    {
        pre_e = L.elem[i];  //注意i
        printf("它的前驱元素是%d\n",pre_e);
        return pre_e;//将此元素返回给要调用的函数
    }        
}
//9.返回后继
Status NextElem(SqList L)
{
    int cur_e, next_e, i = 0;//i的初值是第一个元素的位序
    printf("请输入第一到倒数第二个任意一个元素:\n");
    scanf("%d",&cur_e);
    int *p = L.elem;//第一个元素的地址赋值给p
    while (i < L.length && !compare(cur_e, L.elem[i]))
    {
        p++;
        i++;
    }
    if (i == L.length)
    {
        return ERROR;
    }
    else
    {
        next_e = *(++p);
        printf("它的后继元素是%d\n",next_e);
        return next_e;//将此元素返回给主函数
    }
}
//10.插入元素
Status ListInsert(SqList &L)
{
    ElemType *p, *q, *newbase;
    int i, e;//在位置i插入元素e
    printf("请输入要插入的元素的位置i:\n");
    scanf("%d",&i);
    printf("请输入要插入的元素的数值e:\n");
    scanf("%d",&e);
    if (i<1 || i>L.length)
        return ERROR;
    if(L.length>=L.listsize)
    {
        if (!(newbase = (ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType))))
            exit(0);//分配存储空间失败
        L.elem = newbase;//新基址
        L.listsize += LISTINCREMENT;//增加存储容量
    }
    q = L.elem + i - 1;//q为插入位置
    for (p = L.elem + L.length - 1; p >= q; --p)
    {
        *(p + 1) = *p;//给插入位置之后的元素赋值达到之后元素后移一位的效果
    }
    *q = e;//插入e
    ++L.length;
    return OK;
}
//11.删除元素
Status ListDelete(SqList &L)
{
    int i,e;
    printf("请输入要删除的元素的位置i:\n");
    scanf("%d",&i);
    if (i<1 || i>L.length)//i值不合法
        return ERROR;
    ElemType *p, *q;
    p = L.elem + i - 1;//p为被删除元素的位置
    e = *p;            //被删除元素的值赋给e
    printf("被删除的元素是%d\n",e);
    q = L.elem + L.length - 1;//q是表尾元素的位置
    p = p + 1;
    for ( ; p <= q; p++)
        *(p - 1) = *p;
    L.length--;  //表长减一
    return OK;
}
//12.遍历
Status ListTraverse(SqList L)
{
    ElemType *p = L.elem;
    int i;
    for (i = 1; i <= L.length; i++)
        printf("%d ",*p++);
    printf("\n");
    return OK;
}
int main()
{
    int m,n;
    SqList L;
    InitList(L);
    printf("……顺序表初始化……\n");
    printf("请输入顺序表的长度n:\n");
    scanf("%d",&n);
    for (m = 1; m <= n; m++)
    {
        printf("请输入第%d个元素的值:\n",m);
        scanf("%d",&L.elem[m-1]);
        L.length++;
    }
    printf("顺序表的长度为%d\n",L.length);
    printf("顺序表中的元素为:\n");
    ListTraverse(L);
    printf("…………判断顺序表是否空表…………\n");
    if (ListEmpty(L) == 1)
        printf("顺序表非空\n");
    else
        printf("顺序表为空\n");
    printf("…………顺序表中取元素操作…………\n");
    GetElem(L);
    printf("…………顺序表中元素的定位…………\n");
    LocateElem(L);
    printf("…………顺序表中元素的前驱…………\n");
    PriorElem(L);
    printf("…………顺序表中元素的后继…………\n");
    NextElem(L);
    printf("…………顺序表元素插入测试…………\n");
    ListInsert(L);
    printf("此时顺序表中的元素为:\n");
    ListTraverse(L);
    printf("…………顺序表元素删除测试…………\n");
    ListDelete(L);
    printf("此时顺序表中的元素为:\n");
    ListTraverse(L);
    printf("恭喜您成功完成顺序表的所有功能！！！！\n");
    return 0;
}