线性表的顺序存储表示（顺序表实现）
----------顺序表的存储结构----------
#demine MAXSIZE 100 //顺序表可能达到的最大长度
typedef struct{
ElemType *elem; //存储空间的基地址，此时的ElemType由用户根据需要自己定义，可以是int，char，float也可以是结构体，如一下类似于图书的存储结构
int length; //当前长度
}SqList;
#define MAXSIZE 100 //图书表可能达到的最大长度
typedef struct
{
char num[20]; //图书编号
char name[50]; //图书名字
float price; //图书价格
}BOOK;
typedef struct
{
BOOK *elem; //存储空间的基地址
ine length; //图书表中当前图书个数
}SqList; //当前图书表中的顺序存储结构类型为SqList
在上述定义完之后，可以通过变量定义语句
SqList L;
将L定义为SqList类型的变量，便可以通过利用L.elem[i-1]访问表中位置序号为i图书记录。
只要确定了存储线性表的起始位置，线性表中的任一数据元素都可以随机存取，所以说线性表中的顺序存储结构是一种随机存取的存储结构
----------顺序表的基本操作的实现----------
①顺序表的初始化
顺序表的初始化就是构造一个空的顺序表
Status InitList(SqList &L)
{
L.elem=new ElemeType[MAXSIZE]; //为顺序表分配一个大小为MAXSIZE的数组空间
if(!L.elem) exit(ERROR); //存储失败则退出
L.length=0; //空表长度为零
return OK;
}
②顺序表的取值
取值的操作是根据指定的位置序号i,获取顺序表中第i个数据元素的值。
由于顺序表的存储结构具有随机存储的特点，可以通过数组下标定位得到，elem[i-1]单元存储第i个元素
Status GetElem(SqList &L,int i,ElemType &e)
{
if(i<1 || i>L.length) return ERROR; //判断i值是否合理
e=L.elem[i-1]; //elem[i-1]用来存储第i个数据
return OK;
}
显然顺序表的时间复杂度为O(1)
③顺序表的查找
查找操作是根据指定的e值，查找第一个与e值相等的元素。若查找成功，则返回该元素在表中的位置序号。若查找失败则返回零。
结构体变量之间可以直接赋值我想大家都知道了。但结构体变量之间可以做比较吗？答案肯定是不行的，因为比较符号只作用于基本数据类型。故只能对其成员变量进行比较，而不能对结构体进行整体比较。
e不为结构体的时候
Status LocateElem(SqList &L,ElemType e)
{
for(i=0;i<L.length;i++)
if(L.elem[i]==e) return i+1; //查找成功返回序号i+1
return 0;
}
e为结构体的时候
按序号查找
Status LocateElem(SqList &L,ElemType &e)
{
for(i=0;i<L.length;i++)
if(L.elem[i].num==e.num)
{
e=L.elem[i]; //将符合条件的数据元素赋值给e
return i+1; //查找成功返回序号i+1
}
return 0;
按姓名查找
Status LocateElem(SqList &L,ElemType &e)
{
for(i=0;i<L.length;i++)
if(!strcmp(L.elem[i].name,e.name))
{
e=L.elem[i]; //将符合条件的数据元素赋值给e
return 1; //查找成功返回序号1
}
return 0;
在查找过程中，最好的结果是指查找一个元素就出现与其相等的值，最坏的结果是查找n个元素时才找到与其结果相同的值，平均下来是(n+1)/2
时间复杂度一般不看系数，且取指数最大的值
故此操作的算法复杂度为O(n)
④顺序表的插入
Status ListInsert(SqList &L,int i,ElemType &e)
{
if((i<1)||(i>L.length+1)) return ERROR;
if(L.length==MAXSIZE) return ERROR;
for(j=L.length-1;j>=i-1;j--) //插入位置及以后的元素右移
L.elem[j+1]=L.elem[j];
L.elem[i-1]=e; //将插入元素e放在第i个位置
++L.length; //线性表长度加一
return OK; //插入成功
}
在此操作中最好的结果是把元素插入到表尾，则此时不需要移动元素，最坏的结果是把元素插入到表头，则此时需要移动n个元素。平均下来是(n+0)/2,即n/2.
则此操作的时间复杂度为O(n)
⑤顺序表的删除
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;
}
此操作如果是删除的表中第1个元素，则需要移动n-1个元素，如果删除的是最后一个元素，则不需要移动元素。平均下来是(n-1)/2
故此操作的时间复杂度为O(n)
