三、(2)顺序表

顺序表:

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;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+1)		        //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）

顺序表的优缺点:

优点:

• 无须为表示中元素之间的逻辑关系而增加额外的存储空间。
• 可以快速的存取表中任一位置的元素。

缺点：

• 插入和删除操作需要后移大量数据元素。
• 当线性表长度未知时，难以确定存储空间的容量。
• 若存储空间开的大，会造成大量的空闲空间。