第二周线性表的顺序表示和实现.pdfVIP

1.线性表的定义和特点

1.1线性表是具有相同特性的数据元素的一个有限序列。

1.2线性表的例子

同一线性表中的元素必定具有相同特性，数据元素间的关系是线性关系.

1.3线性表的逻辑特征

线性表是一种典型的线性结构

逻辑特征：

2.案例引入

【案例2.1】

一元多项式的运算：实现两个多项式加、减、乘运算

【案例2.2】：稀疏多项式的运算

mapkeyvalue

建立一个容器，值代表次方，值代表常数项。

重点：

顺序存储结构存在问题：

•存储空间分配不灵活；

•运算的空间复杂度高。

采用链式存储结构

3.线性表的类型定义

ADT

•抽象数据类型线性表的定义如下：

3.1线性表的基本操作

InitList(L)DestoryList(L)ClearList(L)ListEmpty(L)ListLength(L)GetElem(L,i,e)

LocateElem(L,e,compare())PriorElem(L,cur_e,pre_e)NextElem(L,cur_e,next_e)

ListInsert(L,i,e)ListDelete(L,i,e)ListTraverse(L,visited())

4.线性表的顺序表示和实现1

线性表的顺序表示又称为顺序存储结构或顺序映像

4.1顺序存储定义：

把逻辑上相邻的数据元素存储在物理上相邻的存储单元上的存储结构。

1a1

线性表的第个数据元素的存储位置，称作线性表的起始位置或基地址。

线性表顺序存储结构占用一片连续的存储空间。知道某个元素的存储位置就可以计算其他

元素的存储位置。

顺序表中元素存储位置的计算

重点：

线性表顺序存储结构的图示：

顺序表的特点：以物理位置相邻表示逻辑关系。任一元素均可随机存取。（优点）

4.2顺序表的顺序存储表示：

用一变量表示顺序表的长度属性

4.3多项式的顺序存储结构类型定义：

4.4线性表的顺序存储表示：

顺序表示意图

4.4.1补充：操作算法中用到的预定义常量和类型

4.4.2顺序表的基本操作的实现：

4.5顺序表上的查找操作

按值查找

•Le

在线性表查找和指定值相同的数据元素的位置；

•在表的一端开始，逐个进行记录的关键字和给定值的比较。找到，返回该元素的位置

0

序号，未找到，返回。

顺序表的查找算法分析：

n

对含有个记录的表，查找成功时：

Pi指得是第i个记录被查找的概率。

Ci指得是找到第个记录需比较的次数。i

4.6顺序表的插入

4.6.1顺序表的插入算法分析

算法时间主要耗费在移动元素的操作上

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

4.7顺序表的删除

算法时间主要耗费在移动元素的操作上

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

5.顺序表小结

5.1顺序表(线性表的顺序存储结构)的特点

5.2顺序表的优缺点