顺序表定义

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储结构或顺序映像通常被叫做顺序表。顺序表的特点为：以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数。因此，只要确定了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。下面的图很好的显示了这种结构。

?

顺序表的数据元素的插入与删除的结构图：

?

顺序表的存储结构代码：

#define LIST_INIT_SIZE 100 
#define LISTINCREMENT  10
typedef int ElemType;
typedef struct
{
	ElemType *elem;//存储空间基址
	int length;//当前长度
	int listsize;//当前分配的存储容量
}SqList;//定义了一个结构体类型，并命名为

顺序表的基本操作

0基本操作前的准备

#include 
using namespace std;
#include 
#include 
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define LIST_INIT_SIZE 100 
#define LISTINCREMENT  10
typedef int ElemType;
typedef int Status;
typedef struct
{
	ElemType *elem;//存储空间基址
	int length;//当前长度
	int listsize;//当前分配的存储容量
}SqList;//定义了一个结构体类型，并命名为

1构建一个空的顺序表

//1初始化顺序表
Status InitList(SqList &L)
{ 
	L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); 
    if(!L.elem) 
	{
		exit(OVERFLOW); 
	}
    L.length=0; 
    L.listsize=LIST_INIT_SIZE; 
    return OK; 
}

2判断顺序表是否为空

//2判断顺序表是否为空
Status ListEmpty(SqList L)
{
	return L.length==0;
}

3求顺序表的长度

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

4销毁顺序表

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

5清空顺序表

Status ClearList(SqList &L)
{
	L.length=0;
	return OK;
}

6向顺序表插入数据元素

Status ListInsert(SqList &L,int i, ElemType e)
{
	if(i<1||i>L.length+1)
	{
		return ERROR;
	}
	if (L.length>=L.listsize)
	{
		ElemType *newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT )*sizeof(ElemType));
        if(!newbase)
		{
			exit(OVERFLOW);
		}
        L.elem=newbase;
        L.listsize+=LISTINCREMENT;
	}
    ElemType *q=&(L.elem[i-1]);
    ElemType *p;
    for(p=&(L.elem[L.length-1]);p>=q;p--)
    {
      *(p+1)=*p;
    }
    *q=e;  
    ++L.length;
     return OK;}

7返回顺序表中的第i个元素

//7返回顺序表中的第i个元素
Status GetElem(SqList L,int i,ElemType &e)
{
	if(i<1||i>L.length)
	{
		return ERROR;
	}
	e=L.elem[i-1];
	return OK;
}

8删除顺序表的第i个数据元素

//8删除顺序表的第i个数据元素
Status ListDelete(SqList &L,int i,ElemType &e)
{
	if(i<1||i>L.length)
	{
		return ERROR;
	}
	e=L.elem[i-1];
	for(i=0;i