顺序表:
1.定义：指用一段地址连续的存储单元依次存储线性表的数据元素。逻辑上相邻的数据元素，其物理次序也是相邻的。
2.地址计算方法：
假设线性表有n个元素，每个元素占k个单元。第一个元素地址为loc（a1），称为基地址。
则第i个元素地址loc（ai）：loc（ai）=loc（a1）+（i-1）*k；
对每个元素进行存入或者取出的时间复杂度都是O（1），这样的存储结构叫做随机存储结构。
3.线性表的顺序存储结构伪代码：
#define MAXSIZE 100 //存储空间初始分配量
typedef int ElemType;//这里的类型定为int
typedef struct{
ElemType *elem;//存储空间的基地址,也可换为date[MAXSIZE]
int length;//线性表当前长度
}SqList;
4.operation:
①.初始化
Status InitList(Sqlist &L)
{
L.elem=new ElemType[MAXSIZE]; //为顺序表分配一个大小为MAXSIZE的数组空间
if(!L.elem) exit(OVERFLOW); //分存储失败则退出
L.length=0; //空表长度为0
return OK;
}
- 为顺序表L分配一个预定义大小为MAXSIZE的数组空间,使elem指向这段空间的基地址
- 将表的当前长度设为0
Status GetElem(Sqlist L,int i,ElemType &e)
{
if(i<1||i>L.length)
return ERROR;
e=L.elem[i-1];
return OK;
}O（1）
- 判断指定的位置序号i值是否合理（1<= i <= L.length），若不合理,返回ERROR。
- 若i值合理，则将第i个数据元素L.elem[i-1]赋给参数e，通过e返回第i个数据元素的传值。
int LocateElem(Sqlist L,ElemType e)
{//在顺序表L中查找值为e的数据元素,返回其序号
for(int i=0;i<L.length;i++)
if(L.elem[i]==e) return i+1; //如查找成功,返回序号i+1
return 0; //查找失败，返回0
} O（n）
Status ListInsert(Sqlist &L,int i,ElemType e)
{
if(i<1||i>L.length+1)
return ERROR; //当i不在范围内,抛出异常
if(L.length==MAXSIZE) //顺序表已满
return ERROR;
for(int j=L.length-1;j>=i-1;j--)
L.elem[j+1]=L.elem[j]; //插入位置及之后元素后移
L.elem[i-1]=e; //将新元素e放入第i个位置
++L.length; //表长加1
return OK;
} O（n）
Status ListDelete(Sqlist &L,int i)
{
//在顺序表L删除第i个元素,i值的合法范围是1<=i<=L.length
if(i<1||i>L.length) //i值不合法
return ERROR;
for(int j=i;j<L.length;j++)
L.elem[j-1]=L.elem[j]; //被删除元素之后的元素前移
L.length--; //表长减1
return OK;
}O（n）
优点:
- 无须为表示中元素之间的逻辑关系而增加额外的存储空间。
- 可以快速的存取表中任一位置的元素。
缺点：
- 插入和删除操作需要后移大量数据元素。
- 当线性表长度未知时，难以确定存储空间的容量。
- 若存储空间开的大，会造成大量的空闲空间。
京公网安备 11010502036488号