数据结构_2.2、顺序表插入删除查找

1、线性表的顺序存储表示定义：

线性表：是具有相同数据类型的n （n≥0）个数据元素的有限序列

顺序表：用顺序存储的方式实现线性表

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

ElemType ：就是你的顺序表中存放的数据元素类型

2、顺序表的存储结构

2.1、顺序表的实现——静态分配

给各个数据元素分配连续的存储空间，大小为 MaxSize*sizeof(ElemType)

#include <stdio.h>
#define MaxSize 10 //定义最大长度typedef struct {int data[MaxSize]; //用静态的“数组”存放数据元素int length; //顺序表的当前长度
} SqList;// 初始化顺序表
void InitList(SqList &L) {L.length = 0; // 顺序表初始化长度为0
}int main(){SqList L; //声明一个顺序表InitList(L); //初始化顺序表//尝试 “违规 ” 打印整个 data 数组
//	printf("data[%d]=%d\n", L.data);for(int i=0;i<MaxSize;i++)printf("data[%d]=%d\n", i, L.data[i]);return 0;
}

2.2、顺序表的实现——动态分配

#include <stdio.h>
#include <stdlib.h>
#define MaxSize 10 //定义最大长度typedef struct {int *data; //指示动态分配数组的指针int length;//顺序表的当前长度int MaxSize; //顺序表的最大容量
} SqList;void InitList(SqList &L){
//用 malloc 函数申请一片连续的存储空间
L.data=(int *)malloc(InitSize*sizeof(int));
L.length=0;
L.MaxSize=InitSize;
}//增加动态数组的长度
void IncreaseSize(SqList &L,int len){int *p=L.data;L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));for(int i=0; i<L.length; i++){L.data[i]=p[i];//顺序表最大长度增加 len,时间开销大}L.MaxSize=L.MaxSize+len;free(p);//释放原来的内存空间}int main(){SqList L; //声明一个顺序表InitList(L); //初始化顺序表IncreaseSize(L,5);free(L.data);return 0;
}

3、顺序表中基本操作的实现

3.1、初始化

• 顺序表的初始化操作就是构造一个空的顺序表。
• 为顺序表L动态分配一个预定义大小的数组空间，使 elem 指向这段空间的基地址。

• 将表的当前长度设为0。
• 动态分配线性表的存储区域可以更有效地利用系统的资源 ， 当不需要该线性表时 ， 可以使用 销毁操作及时释放占用的存储空间。

【算法描述】

//构造一个空的顺序表L
Status Initlist(SqList &L){L.elem=new Elemrype [MAXSIZE];//为顺序表分配一个大小为 MAXSI2E的数组空间if(!L.elem)exit(OVERFLON);//存储分配失败退出L.length=0;//空表长度为 0return OK;
}

3.2、取值

• 取值操作是根据指定的位置序号i, 获取顺序表中第i个数据元素的值。
• 由于顺序存储结构具有随机存取的特点 ， 可以直接通过数组下标定位得到，elem[-1]单元存储第i个数据元素。
• 顺序表取值算法的时间复杂度为0(1)。

Status GetElem(SqList L,int i, ElemType &e）
{if {i<ll li>L.length) return ERROR; //判断i值是否合理，若不合理， 返回 ERRORe=L.elem[i-1]; //elem[i-1] 单元存储第i个数据元素return OK;
}i

3.3、查找

• 查找操作是根据指定的元素值e, 查找顺序表中第1个与e相等的元素。若查找成功，则返回该元素在表中的位置序号；若查找失败，则返回0。

• 从第一个元素起，依次和 e相比较，若找到与 e相等的元素 L.elem[i], 则查找成功，返回该元素的序号 i+1。

• 若查遍整个顺序表都没有找到，则查找失败， 返回0。

• 顺序表按值查找算法的平均时间复杂度为 O(n)。

int LocateELem(SqList L,ElemType e){//在顺序表工中查找值为e的数据元素，返回其序号for(i=0; i<L.length; i++)if(L.elem[i]==e)return i+l;  //查找成功，返回序号 i+1
return 0;            //查找失败，返回 0}

3.4、插入

顺序表的插入算法步骤:

顺序表插入算法的平均时间复杂度为 O(n)

Status Listinsert(SqList &L, int i, ElemType e)
{//在顺序表 L 中第 i 个位置之前插入新的元素 e, i值的合法范围是 1<=i<=L.length+lif ((i < l) || (i > L.length + l)) return ERROR;                       //i值不合法if (L.length == MAXSIZE) return ERROR;                       //当前存储空间已满for (j = L.length - 1; j >= i - 1; j--)L.elem[j + l] = L.elem[j];              //插入位置及之后的元素后移L.elem[i - l] = e;                          //将新元素e放入第l个位置++L.length;                                 //表长加1return OK;}

3.5、删除

顺序表的删除算法步骤

• 判断删除位置 i 是否合法（合法值为 1 ≤ i ≤n), 若不合法则返回 ERROR。

• 将第 i个至第n个的元素依次向前移动一个位置 (i = n时无需移动）

• 表长减 1

• 顺序表删除算法的平均时间复杂度为O(n)。

Status ListDelete(SqList &l int i)
{//在顺序表工中删除第i个元素，i.值的合法范闱是1≤i≤L.length
if((i<1)|l(i>L.length)) //i值不合法return ERROR;
for(j=i;j<-L.length-l;j++)L.elem[j-1]=L.elem[j];//被删除元素之后的元素前移
--L.length;//表长减 1
return OK;
}