概念

顺序表是指用一组地址连续的存储单元依次存储线性表的数据元素，也被称为线性表的顺序存储结构或顺序映像。
存储的位置：其在逻辑上相邻的数据元素，在物理次序上也是相邻的存储地址。
顺序表的存储结构体

 #define  MAXSIZE  100   //最大的表长
 #define OVERRFLOW   -1
 #define OK  1
 #define ERROR 0
 typedef struct
 {
               ElemType  *elem;//存储空间基地址
               int   length; //当前表长
 }Sqlist;//顺序表的结构类型Sqlist

初始化顺序表

【算法步骤】

1. 为顺序表分配一个MAXSIZE大的动态空间的数组。
2. 将表长设置为0。

伪码：

status Initlist(Sqlist &L)
{
    L.elem=new ElemType[MAXSIZE];
    if(!L.elem)
    exit(OVERRFLOW);
    L.length=0;
    return OK;
}   

顺序表的取值

【算法步骤】

1. 判断i位置是否合理，若不合理则返回ERROR。
2. 若i值合理，则将第i个数据元素L.elem[i-1]的值赋给参数e，通过e返回第i个数据元素的传值。
   伪码：

status GetElem(Sqlist L,int i,ElemType &e)
{
	if((i<1)||(i>L.length))
		return ERROR;
		e=L.elem[i-1];
		return OK;
}

顺序表的查找

【算法步骤】

1. 从第一个元素起，依次和e比较，若找到与e相同的元素L.elem[i],
   则返回该元素的序号i+1。
2. 若没有找到，查找失败，则返回ERROR。
   伪码：

int LocateElem(Sqlist L,ElemType e)
{
	for(i=0;i<L.length;i++)
	if(L.elem[i]==e)
	return i+1;
	return ERROR;
}

顺序表的插入

【算法步骤】

1. 判断插入的位置是否合理，若不合理则返回ERROR。
2. 判断顺序表是否已满，若满则返回ERROR。
3. 将第i个至第n个位置的元素都向后移一位，空出第i个位置；当i为n+1时不需要移动。
4. 见要插入的元素e放入到第i个位置。
5. 表长加一。
   伪码：

 status ListInsert(Sqlist &L,int i,Elemtype e)
  {
     if((i<1)||(i>L.length))
         return ERROR;
     if(L.length==MAXSIZE)
         return ERROR;
     for(j=L.length;j>=i-1;j--)
         L.elem[j+1]=L.elem[j];
        L.elem[i-1]=e;
        L.length++;
    return OK;
  }

顺序表的删除

【算法步骤】

1. 判断删除位置是否合法，若不合法则返回ERROR。
2. 将第i+1个至第n个元素向前移动一位；当i=n时不需要移动。
3. 表长减一。

伪码：

status ListDelete(Sqlist &L,int i)
{
	if((i<1)||(i>L.length))
	return ERROR;
	for(j=i;j<=L.length-1;j++)
	    L.elem[j-1]=L.elem[j];
	    L.length--;
	    return OK;
}

顺序表的具体实现：

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;

#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status; //Status 是函数返回值类型，其值是函数结果状态代码。

typedef int ElemType; //ElemType 为可定义的数据类型，此设为int类型

#define MAXSIZE 100 //顺序表可能达到的最大长度

typedef struct {
   ElemType *elem; //存储空间的基地址
   int length; //当前长度
} SqList;

Status InitList(SqList &L)   // 顺序表的初始化
{
   //构造一个空的顺序表L
   L.elem = new ElemType[MAXSIZE]; //为顺序表分配一个大小为MAXSIZE的数组空间
   if(!L.elem)
      exit(OVERFLOW); //存储分配失败退出
   L.length = 0; //空表长度为0
   return OK;
}
void DestroyList(SqList &L)
{
   if(L.elem)
      delete []L.elem;     //释放存储空间
}

int ListLength(SqList L)
{
    return L.length;//返回表长

}
bool ListEmpty(SqList L)
{//根据表是否为空输出"Empty"或 "Not empty"
   if(L.length==0) 
   return 1;
   else
   return 0;

}
Status GetElem(SqList L, int i, ElemType & e)   //　顺序表的取值
{
    if(L.length>=i&&i>0)
    {
       e=L.elem[i-1];
       return OK;
    }
    else return ERROR;
}
int LocateElem(SqList L, ElemType e)   // 顺序表的查找
{
   for(int i=0;i<L.length;i++)
   {
      if(e==L.elem[i])
      return (i+1);
   }
   return 0;
}
Status ListInsert(SqList & L, int i, ElemType e)   //顺序表的插入
{
   int j;
   if(L.length+1>=i&&i>0)
   {
      for(j=L.length-1;j>=i-1;j--)
      L.elem[j+1]=L.elem[j];
      L.elem[i-1]=e;
      L.length++;
      return OK;
   }
   else 
   return ERROR;

}
Status ListDelete(SqList & L, int i)   //顺序表的删除
{
   if((i<1)||(i>L.length))//判断i是否合理
      return ERROR;
   	  for(int j=i;j<=L.length-1;j++)//从i开始到L.length都向前移动一位
   	  {
   	  	L.elem[j-1]=L.elem[j];
		 }
      L.length--;//表长减一
      return OK;  

}
void ListPrint(SqList L)
{
   for(int i = 0; i < L.length; i++)
      cout << L.elem[i] << ((i == L.length - 1) ? '\n' : ' ');
}
int main()
{
   int i;
   ElemType e;
   SqList L;
   string op;
   InitList(L);
   while(cin >> op) {
      if(op == "Empty")
         cout << (ListEmpty(L) ? "Empty" : "Not empty") << endl;
      else if(op == "Insert") {
         cin >> i >> e;
         if(ListInsert(L, i, e) == ERROR)
            cout << "Insert failed" << endl;
         else
            ListPrint(L);
      } else if(op == "Length") {
         cout << "List length is " << ListLength(L) << endl;
      } else if(op == "GetElem") {
         cin >> i;
         if(GetElem(L, i, e) == ERROR)
            cout << "Out of index" << endl;
         else
            cout << "The elem at position " << i << " is " <<  e << endl;
      } else if(op == "LocateElem") {
         cin >> e;
         i = LocateElem(L, e);
         if(i == 0)
            cout << e << " is not found in list" << endl;
         else
            cout << e  << " is found at the position " << i << endl;
      } else if(op == "Delete") {
         cin >> i;
         if(ListDelete(L, i) == ERROR)
            cout << "Delete failed" << endl;
         else
            ListPrint(L);
      }
   }
   DestroyList(L);
   return 0;
}