数据结构03顺序表

1 线性表的定义

线性表(List):零个或多个数据元素的有限序列。

  1. 线性表是一个序列。元素之间是有顺序的,若元素存在多个,则第一个元素无前驱,最后一个元素无后继,其他每个元素都有且只有一个前驱和后继。
  2. 线性表强调是有限的,在计算机中处理的对象都是有限的,那种无限的数列,只存在于数学的概念中。

在较复杂的线性表中,一个数据元素可以由若干个数据项组成。

数据结构03顺序表

2 线性表的抽象数据类型

线性表的抽象数据类型定义伪代码如下:

ADT 线性表(List)
DATA
线性表的数据对象集合为{a1,a2,·····,an},每个元素的类型均为DataType。其中,除第一个元素a1外,每一个元素有且只有—个直接前驱元素,除了最后一个元素an外,每—个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
Operation
InitList(*L):初始化操作,建立一个空的线性表L。
ListEmpty(L):若线性表为空,返回为true,否则返回false。
ClearList(*L):将线性表清空。
GetElem(L,i,*e):将线性表L中的第i个位置元素返回给e。
LocateElem(L,e):在线性表L中查找与给定值e相等的元素,如果查找成功,返回该元素在表中序号表示成功;否则返回0表示失败。
ListInsert(*L.i,e):在线性表L中的第i个位置插入新元素e。
ListDelete(*L,i,*e):删除线性表L中第i个位置元素,并用e返回其值。
ListLength(L):返回线性表L的元素个数。
endADT

注意一个很容易混淆的地方:

当传递一个参数给函数的时候,这个参数会不会在函数内被被动决定了使用什么参数形式。

如果需要被改动,则需要传递指向这个参数的指针。

如果不用被改动,可以直接传递这个参数。

3 线性表的顺序存储结构

线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。

顺序存储示意图如下:

数据结构03顺序表

线性表的顺序存储的结构代码:

#define MAXSIZE 20 //存储空间初始分配量
typedef int ElemType; // ElemType类型根据实际情况而定,这里为int
typedef struct{
ElemType data[MAXSIZE]; // 数组,存储数据元素
int length; //线性表当前长度
}SqList;

描述顺序存储结构需要三个属性:

  • 存储空间的起始位置:数组data,它的存储位置就是存储空间的存储位置。
  • 线性表的最大存储容量:数组长度MAXSIZE。
  • 线性表的当前长度:length。

4 顺序存储结构的插入与删除

4.1 获取元素

对于线性表的顺序存储结构来说,如果我们要实现GetElem操作,即将线性表L中的第j个位置元素值返回,只要j的数值在数组下标范围内,就是把数组第j-1下标的值返回即可。

#define OK 1
#define ERROE 0
typedef int Status; // Status是函数的类型,其值是函数结果状态代码,如OK等
/* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L) */
/* 操作结果:用e返回L中第i个数据元素的值,注意i是指位置,第1个位置的数组是从0开始 */
Status GetElem(SqList L,int i,ElemType *e)
{
if(L.length==0 || i<1 || i>L.length)
return ERROR;
*e=L.data[i-1];

return OK;
}

4.2 插入操作

插入算法的思路:

  1. 如果插入位置不合理,抛出异常。
  2. 如果线性表长度大于等于数组长度,则抛出异常或动态增加容量。
  3. 从最后一个元素开始向前遍历到第i个位置,分别将它们都向后移动一个位置。
  4. 将要插入元素填入位置i处。
  5. 表长加一。

实现代码如下:

/* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L), */
/* 操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1 */
Status ListInsert(SqList *L,int i,ElemType e){
int k;
if (L->==MAXSIZE){ // 顺序线性表已经满
return ERROR;
}
if (i<1 || i>L->length+1){ // 当i比第一位置小或者比最后一位置后一位置还要大时
return ERROR;
}
if (i <= L-> length){ // 若插入数据位置不在表尾
for (K = L->length -1; k>= i-1 ; k--){ // 将要插入位置之后的数据元素向后移动一位
L->data[k+1] = L->data[k];
}
}
L->data[i-1] = e; // 将新元素插入
L->length++; // 表长加一

return OK;
}

4.3 删除操作

删除算法的思路:

  1. 如果删除位置不合理,抛出异常。
  2. 取出删除元素。
  3. 从删除元素位置开始遍历到最后一个元素位置,分别将它们都向前移动一个位置。
  4. 表长减一。

实现代码如下:

/* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L) */
/* 操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1 */
Status ListDelete(SqList *L,int i,ElemType *e)
{
int k;
if (L->length==0) { /* 线性表为空 */
return ERROR;
}

if (i<1 || i>L->length){ /* 删除位置不正确 */
return ERROR;
}

*e=L->data[i-1];
if (i<L->length){ /* 如果删除不是最后位置 */
for(k=i;k<L->length;k++){ /* 将删除位置后继元素前移 */
L->data[k-1]=L->data[k];
}
}
L->length--; // 表长减一
return OK;
}

5 顺序存储结构的优缺点

优点:

  • 随机存取,快速地通过首地址和元素符号可在数据结构03顺序表的时间内找到指定的元素。
  • 存储密度高,每个结点只存储数据元素。
  • 逻辑上相邻的元素物理上也相邻,插入和删除操作需要移动大量元素。
  • 当线性表长度变化较大时,难以确定存储空间的容量。
  • 易造成存储空间的“碎片”。
发表评论

相关文章