【数据结构】线性表的顺序表示（顺序表的定义和基本操作）

计算机考研408-数据结构笔记本之——第二章线性表

2.2 线性表的顺序表示（顺序表的定义和基本操作：初始化/插入/删除/查找）

2.2.1 顺序表的定义

1.定义

顺序表是线性表的顺序存储。

所谓顺序存储，就是把逻辑上相邻的元素存储在物理位置上相邻的存储单元中，元素间的关系由存储单元的邻接关系来体现。

2.实现

顺序表中的任意一个数据元素都可以随机存取。通常用数组来描述线性表的顺序存储结构。数组可以是静态分配的，也可以是动态分配的.

注意：线性表中元素位序从1开始，而数组中元素下标从0开始。

假定线性表的元素类型为ElemType

1）静态分配（存储数组空间和内存固定）

静态分配的顺序表存储结构描述为：

2）动态分配（存储数组分配空间大小在运行时动态决定）

3.特点

2.2.2 顺序表的初始化

静态分配：

静态分配在声明一个顺序表时，就已经为其分配了数组空间，因此初始化时只需将顺序表的当前长度设为0。

//静态分配初始化//SqList L；				//声明一个顺序表 void InitSize(SeqList &L){	L.length = 0;			//顺序表初始长度为0 }

动态分配：

动态分配的初始化为顺序表分配一个预定义大小的数组空间，并将顺序表的当前长度设为0.MaxSize指顺序表当前分配的存储空间大小,一旦因为插入元素而空间不足,就再进行分配.

//动态分配初始化//SqList L；				//声明一个顺序表 void InitSize(SeqList &L){L.data = (ElemType *)malloc(sizeof(ElemType)*Initsize);		//分配存储空间 L.length = 0;			//顺序表初始长度为0L.MaxSzie = InitSize;	//初始存储容量 }

2.2.2 顺序表的插入(O(n))

在顺序表L的第i个位置插入新元素e: ListInsert(&L,i,e);

若i不合法(不在1 <= i <= L.length + 1范围内),返回False,插入失败;

若i合法,将第i个元素及其后的元素均往后移动一位,腾出的空位置插入新元素e,顺序表长度+1,插入成功,返回True.

bool ListInsert(SqList &L, int i, int e)
{if(i < 1 || i > L.length+1) return false; 	//判断i的范围是否有效 if(L.length >= MaxSzie) return false;		//存储空间若满了不能插入 for(int j = L.length; j >= i; j--)L.data[j] = L.data[j-1];				//将第i个及其之后元素均后移一位 L.data[i-1] = e;							//插入元素e L.length++;									//表长度+1 return true;
}

时间复杂度分析:

2.2.2 顺序表的删除(O(n))

删除顺序表L中第i个位置的元素,用引用变量e返回被删除元素的值: ListDelete(&L,i,e);

若i不合法(不在1 <= i <= L.length 范围内),返回False;

若i合法,将第i个元素(要删除的元素)的值赋给e,并将第i+1个元素及其后的元素均往前移动一位,表长减1,返回True.

bool ListDelte(SqList &L, int i, int &e)  //注意e要加引用符 
{if(i < 1 || i > L.length) return false; 	//判断i的范围是否有效 e = L.data[i-1];							//将被删除元素的值赋给e for(int j = i; j < L.length; j++)L.data[j-1] = L.data[j];				//将第i个元素后面的元素均前移一位 L.length--;									//表长度-1 return true;
}

时间复杂度分析

2.2.2 顺序表的查找(O(n)或O(1))

分按位查找和按值查找(顺序查找)两种.

按位查找(O(1)):直接根据数组下标访问元素,获取表L中第i个位置的元素的值.GetElem(L,i);

ElemType GetElem(SqList L, int i)
{return L.data[i-1]; 
}

按值查找(顺序查找)(O(n)):在顺序表L中查找第一个元素值 = e的元素,并返回其位序: LocateElem(&L,e);