【数据结构/线性表】线性表的顺序表示和实现

1.称顺序存储结构的线性表为顺序表

2.线性表的顺序存储结构是一种随机存取的存储结构

3.通常用数组来描述数据结构中的顺序存储结构

4.逻辑结构与存储结构一致

5.访问每个元素所花时间相等

顺序表数据结构

数组形式

//顺序表数据结构
typedef struct
{
	ElemType data[MaxSize];//顺序表元素
	int length;            //顺序表当前长度
}SqList;                   //顺序表的结构类型为SqList

指针形式

//顺序表数据结构
typedef struct
{
	ElemType *elem;        //存储空间的基地址
	int length;            //顺序表当前长度
}SqList;                   //顺序表的结构类型为SqList

顺序表初始化

数组形式

//初始化顺序表函数，构造一个空的顺序表 
Status InitList(SqList &L)
{
	memset(L.data, 0, sizeof(L));//初始化数据为0
	L.length = 0;                //初始化长度为0
	return 0;
}

指针形式

Status InitList(SqList &L)
{
	L.elem=new int[MAXSIZE];
	if(!L.elem) exit(OVERFLOW);
	L,length=0;
	return OK;
}

销毁顺序表

void DestoryList(SqList &L)
{
	if(L.elem) delete[] L.elem;
}

顺序表的取值

指针形式
时间复杂度：O(1)

Status GetElem(SqList L,int i,int &e)
{
	if((i<1)||(i>L.length)) return ERROR;
	e=L.elem[i-1];//将第i个元素赋值给e
	return OK; 
} 

顺序表的查找

指针形式
时间复杂度：O(n)
查找失败返回0

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

顺序表的插入

插在第i个节点之前，需要移动n-i+1次元素

时间复杂度：O(n)

Status ListInsert(SqList &L,int i,int e)
{	
	if((i<1)||(i>L.length+1)) return ERROR;//i值不合法 
	if(L.length==MAXSIZE) return ERROR;//存储空间已满 
	for(j=length-1;j>=i-1;j--)
	{
		L.elem[j+1]=L.elem[j];
	}
	L.elem[i-1]=e;//将新元素放入第i个位置
	++L.length; 
	return OK;
}

顺序表的删除

删除第i个节点，需要移动n-i次元素

时间复杂度：O(n)
空间复杂度：O(1)

Status ListDelete(SqList &L,int i)
{
	if((i<1)||(i>L.length)) return ERROR;//i值不合法 
	for(j=i;j<=L.length-1;j++)
	{
		L.elem[j-1]=L.elem[j];
	}
	--L.length;
	return OK;
}

顺序表的倒置

//倒置函数 将原顺序表直接倒置
void Reverse(SqList &L)
{
	if (L.length)
	for (int i = 0; i<L.length - 1 - i; i++)
	{
		int t = L.data[i];
		L.data[i] = L.data[L.length - 1 - i];
		L.data[L.length - 1 - i] = t;
	}
}

清空顺序表

void ClearList(SqList &L)
{
	L.length = 0;
}

优点和缺点

优点：

随机存取表中任何一个元素，其存储位置可用一个简单直观的公式来表示

缺点：

1.做插入或者删除操作，需要移动大量元素

2.数组长度有相对固定的静态特性，当表中数据元素个数较多而且变化较大时，操作过程相对复杂，必然导致存储空间的浪费。