2.2.1 顺序表
顺序表是一种定长的顺序存储结构(向量型的一维数组结构)。其用一段地址连续的存储单元依次存储线性表中的数据元素。
我们将按以下三点描述一个顺序表。
综上我们将使用【一维数组+当前长度】来组成一个顺序表。
特点:线性表元素可以按地址相邻存储在数组的一片连续地址区域中。
缺点:数组的固定长度限制了线性表长度变化不得超过该固定长度。
2.2.2 顺序表上基本操作的实现
(1)初始化*init_SeqList()
//初始化
SeqList* Init_SeqList() {
SeqList* L;
L = (SeqList*)malloc(sizeof(SeqList));
L->last = -1;
return L;
}
顺序表的初始化即构造一个空表,将L设为指针参数,首先动态分配存储空间,然后,将表中 last 指针置为-1,表示表中没有数据元素。
- 因为我们存放的位置是从零开始的,所以我们将last置为-1。
(2)插入运算Insert_SeqList()
在表的第i个位置上插入一个值为 x 的新元素。
int Insert_SeqList(SeqList *L,int i,datatype x)
{ int j;
if (L->last==MAXSIZE-1)
{ printf("表满"); return(-1); } /*表空间已满,不能插入*/
if (i<1 || i>L->last+2) /*检查插入位置的正确性*/
{ printf("位置错");return(0); }
for(j=L->last;j>=i-1;j--)
L->data[j+1]=L->data[j]; /* 结点移动 */
L->data[i-1]=x; /*新元素插入*/
L->last++; /*last仍指向最后元素*/
return (1); /*插入成功,返回*/
}
完成这一运算需通过以下步骤进行:
(1) 将ai~an 顺序向后移动,为新元素让出位置;
(2) 将 x 置入空出的第i个位置;
(3) 修改 last 指针(即修改表长),使之仍指向最后一个元素。
(3)删除运算 Delete_SeqList()
(4)按值查找 Locate_SeqList()
(5)销毁
//销毁
void Destroy_SeqList(SeqList** L) {
if (*L) {
free(*L);
*L = NULL;
}
}
销毁顺序表即释放非空的顺序表的空间,并将其指针置为空(防止误操作)。
- 这里要先释放空间再将指针置空,如果是先将指针置空就无法找到该空间了。
(6)求表长
//求表长
int Length_SeqList(SeqList* L) {
return L->last + 1;
}
(7)判断表列是否为空
//判断是否为空
int isEmpty_SeqList(SeqList* L) {
if (L->last == 0)
return true;
else
return false;
}