第2周线性表（上）第2讲-线性表的顺序存储结构.pdf

《第2周线性表（上）第2讲-线性表的顺序存储结构.pdf》由会员分享，可在线阅读，更多相关《第2周线性表（上）第2讲-线性表的顺序存储结构.pdf（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、线性表的顺序存储结构：把线性表中的所有元素按照顺序存储线性表的顺序存储结构：把线性表中的所有元素按照顺序存储 方法进行存储。方法进行存储。 线性表线性表 (a1, a2, , ai, an) 直接映射直接映射 a1a2 ai an n MaxSize- -101i- -1n- -1 datalength 顺序表顺序表 逻辑结构逻辑结构 存储结构存储结构 其中其中data成员存放元素，成员存放元素，length成员存放线性表的实际长度成员存放线性表的实际长度。 顺序顺序表类型定义表类型定义： 说明：说明：注意注意逻辑位序逻辑位序和和物理位序物理位序相差相差1。 这里，假设这里，假设ElemTyp

2、e为为char类型类型 1、建立、建立顺序表顺序表 a0.n- -1 顺序表顺序表L 整体创建顺序表整体创建顺序表。 传递顺序传递顺序 表指针表指针 顺序表顺序表 ？L1010 顺序表指针的含义顺序表指针的含义 顺序表的空间顺序表的空间 顺序表顺序表 L SqList *L; L=(SqList *)malloc(sizeof(SqList); 1010 通过顺序表指针通过顺序表指针 L操作顺序表操作顺序表 算法参数说明算法参数说明 顺序表指针引用顺序表指针引用 void CreateList(SqList *&L,ElemType a,int n) 引用参数：将执行结果回传给实参引用参数：将

3、执行结果回传给实参 （1）初始化线性表初始化线性表InitList(L) 2、顺序、顺序表基本运算算法表基本运算算法 该运算的结果是构造一个空的线性表该运算的结果是构造一个空的线性表L。实际上只需将。实际上只需将length 成员设置为成员设置为0即可。即可。 （2）销毁线性表）销毁线性表DestroyList(L) L free(L)释放释放L所指向的所指向的空间空间 顺序表顺序表 该运算的结果是释放线性表该运算的结果是释放线性表L占用的内存空间。占用的内存空间。 （3）判定是否为空表）判定是否为空表ListEmpty(L) 该运算返回一个值表示该运算返回一个值表示L是否为空表。若是否为空表

4、。若L为空表，则返回为空表，则返回 true，否则返回，否则返回false。 （4）求线性表的长度）求线性表的长度ListLength(L) 该运算返回顺序表该运算返回顺序表L的长度。实际上只需返回的长度。实际上只需返回length成员的值即可。成员的值即可。 （5）输出线性表输出线性表DispList(L) 该运算当线性表该运算当线性表L不为空时不为空时,顺序显示顺序显示L中各元素的值。中各元素的值。 （6）求某个数据元素值）求某个数据元素值GetElem(L,i,e) 体现顺序表的体现顺序表的随机存取特性随机存取特性 本算法的时间复杂度为本算法的时间复杂度为O(1)。 该运算返回该运算返回

5、L中第中第 i（1iListLength(L)）个元素的值，存放在）个元素的值，存放在e中。中。 （7）按元素值查找）按元素值查找LocateElem(L,e) 该运算顺序查找第该运算顺序查找第1个值域与个值域与e相等的元素的逻辑位序。若这相等的元素的逻辑位序。若这 样的元素不存在，则返回值为样的元素不存在，则返回值为0。 （8）插入数据元素插入数据元素ListInsert(L,i,e) 该运算在顺序表该运算在顺序表L的第的第i（1iListLength(L)+1）个位置）个位置 上插入新的元素上插入新的元素e。 01 i- -1n- -1ni a1a2aiai+1an e i+1 插入完成插

6、入完成 length n n+1 插入算法如下：插入算法如下： 对于本算法来说，元素移动的次数不仅与表长对于本算法来说，元素移动的次数不仅与表长L- -length=n有关，有关， 而且与插入位置而且与插入位置i有关有关： 算法算法最好时间复杂度为最好时间复杂度为O(1)算法算法最坏时间复杂度为最坏时间复杂度为O(n) 当当i=1时，移动次数为时，移动次数为n，达到最大值。，达到最大值。 当当i=n+1时，移动次数为时，移动次数为0； a1a2aiai+1an 在线性表在线性表L中共有中共有n+1个可以插入元素的地方个可以插入元素的地方 此时需要将此时需要将aian的元素均后移一个位置，共移动

7、的元素均后移一个位置，共移动n- -i+1个元素。个元素。 因此插入算法的平均时间复杂度为因此插入算法的平均时间复杂度为O(n)。 在插入元素在插入元素ai时，若为等概率情况，则时，若为等概率情况，则pi = 1 1 n 所以在长度为所以在长度为n的线性表中插入一个元素时所需移动元素的的线性表中插入一个元素时所需移动元素的 平均次数为：平均次数为： 2 )1( 1 1 )1( 1 1 1 1 n in n inp n i n i i 平均情况分析：平均情况分析： （9）删除数据元素删除数据元素ListDelete(L,i,e) 该该运算删除顺序表运算删除顺序表L的第的第i（1iListLeng

8、th(L)）个）个元素元素。 01 i- -1n- -1i a1a2ai+1anai e n- -2 an- -1 length nn- -1 删除完成删除完成 删除算法如下：删除算法如下： 对于本算法来说，元素移动的次数也与表长对于本算法来说，元素移动的次数也与表长n和删除元素的位和删除元素的位 置置i有关有关： 当当i=n时，移动次数为时，移动次数为0； 当当i=1时，移动次数为时，移动次数为n- -1。 删除算法最好时间复杂度为删除算法最好时间复杂度为O(1)删除算法最坏时间复杂度为删除算法最坏时间复杂度为O(n) a1a2aiai+1an n 1 在删除元素在删除元素ai时，若为等概率情况，则时，若为等概率情况，则pi = 在线性表在线性表L中共有中共有n个可以删除元素的地方个可以删除元素的地方 此时需要将此时需要将ai+1an的元素均前移一个位置，共移动的元素均前移一个位置，共移动n- -(i+1)+1=n- -i 个元素。个元素。 n i n i i n in n inp 11 2 1 )( 1 )( 所以在长度为所以在长度为n的线性表中删除一个元素时所需移动元素的平的线性表中删除一个元素时所需移动元素的平 均次数为：均次数为： 因此删除算法的平均时间复杂度为因此删除算法的平均时间复杂度为O(n)。 平均情况分析：平均情况分析： 本讲完本讲完