2.2 线性表的顺序表示和实现在线视频

同学们大家好

我是云南大学信息学院教师孔兵

今天我们讨论线性表的顺序表示和实现

前面我们提到

顺序映象是描述元素之间关系的一种方法

特点是借助数据元素

在存储器中的相对位置描述数据元素之间的关系

线性表的顺序表示

就是采用顺序映象的办法实现线性表的存储

下面我们看一下具体的做法

把线性表的数据元素按逻辑顺序

依次存放在一组地址连续的存储单元里

这个连续的存储单元一般是一个数组

用这种方法存储的线性表

我们简称为顺序表

在这样的存储方式下

我们是通过数据元素

在数组位置上的相邻来暗示数据元素之间的逻辑关系

如图中所示，例如ai和ai+1

它们存储在数组相邻的

下标连续的两个存储单元中

通过这样的位置相邻暗示，ai是ai+1的前驱

对称的 ai+1是ai的后继

其它元素之间前驱和后继的关系也是如此表示

下面我们看一下具体的实现方式

我们采用动态分配存储空间的方式实现顺序表的存储

类似的定义方式前面课程中讨论过

首先定义两个常量

一个是线性表中当前存储元素的个数

一个是线性表的容量

用Typedef给这个结构体起了个类型名sqlist

基于这样存储结构的定义

下面看一下基本操作的实现

首先看一下线性表的初始化

从上面存储结构的定义可以看出

结构体本身并没有可用的存储空间

线性表需要的存储空间需要动态分配

因此，线性表初始化的主要的工作

工作为线性表分配存储空间

初始化操作中主要的一个语句

就是利用malloc函数申请空间

函数的参数是以字节数给出需要分配空间的大小

这里用每个元素需要的字节数

sizeof(Elemtype)乘上线性表初始容量作为参数

意思是分配可以存100个数据元素的空间

作为线性表初始的存储空间

函数调用成功，返回分配空间的起始地址

我们把这个地址进行强制类型转换赋值给L.elem指针

也就是说用L.elem指向分配空间的起始地址

可以参考图示，这个指针我们后面经常当做数组名来使用

如果函数调用失败，会返回空指针

那么就退出操作

分配成功的话，L.length被赋值零

现在线性表中还没有数据元素

L.listsize被赋值为线性表初始大小

这是目前线性表的容量

到这就完成了线性表的初始化

为一个线性表分配好了存储空间

可以使用它来存储我们的线性表了

下面我们看一下在顺序表中插入操作的实现

线性表插入操作中涉及到三个参数

一个是插入对象线性表L, 一个是插入的位置i

一个是需要插入的元素e. 前面我们强调过

这里插入位置I指的是线性表序列当中的第i个位置

也就是应该插到序列中第ai-1之后，ai之前

这实际上是指明，e是ai-1的后继，是ai的前驱

所以e应该放在序列中这个位置

下面我们通过图示看看插入的具体实现

从图中可以看出看ai所存位置的下标是i-1

要通过存储位置暗示e是ai-1的后继

是ai的前驱

需要把ai到an这段线性表统统后移一个位置

这里我们用一个循环实现这段线性表的后移

用指针q指向i-1

指针p指向线性表最后一个元素

每次循环做一个元素的后移，从最后一个元素开始

首先通过*p赋值给*（p+1）把an后移一个位置

随后--p,让p指向an-1个元素

下次循环就把an-1后移

一直到p等于q的时候

后移ai，完成这段线性表的后移

通过这样的移动下标i-1这个位置就空出来了

后面需要做的工作就很简单了

把需要插入的元素e存到i-1这个位置

就完成了线性表的插入

从插入后的情况来看。e在a1-1之后

表示它是a1-1的后继，在ai之前，表示它是ai的前驱

数据元素之间的逻辑关系确实在存储结构上被正确的表达

下面我们看一下线性表插入操作的具体实现代码

插入操作的代码可以分为三块

黄色这一块就是一个语句

这个语句是对插入位置合法性的一个判断

合法的插入位置是线性表逻辑序列中的1到L.length+1这些位置

如果插入位置小于1

或是插入位置大于L.length+1的话

那么说明插入的位置非法，直接return error

绿色这块是处理当线性表容量满了，要插入元素的情况

如果线性表不满，这个语句是不执行的

这块中的主要工作就是通过realloc函数

申请一块快更大的空间

从realloc的第2个参数可以看出

新空间的大小是在原来容量L.listsize的基础上增加一个增量

这个增量前面定义过

如果申请成功，重置指针L.elem和容量L.listsize

最后蓝色这一块是具体的插入操作过程

首先用指针q指向要插入的位置i-1

然后通过一个for循环实现把ai到an这段线性表后移一个位置

前面结合图形已经讨论过

后移完成以后，q所指的就是插入位置i-1

通过赋值语句*q赋值e就可以完成e的插入

插入一个元素后，线性表中元素个数增加了1

要做一个++L.lenght

下面我们分析一下插入算法的时间复杂度

我们注意到插入算法的主要时间

是花费在循环进行元素的后移

而后移的次数，是和插入的位置有关

设线性表中有n个元素

最坏情况是插入位置i等于1的情况

元素需要移动的次数是n次

最好情况是插入位置i等于n+1，元素不需要移动

在这个问题中，为了更准确的分析算法的时间复杂度

可以进行算法平均时间复杂度的分析

由于插入可能在表中任何位置上进行

可能的插入位置有n+1

令Eis表示移动节点的期望值

我们注意到在第i个位置上插入一个元素

移动次数是n-i+1

基于此我们可以列出Eis的计算公式

考察每个插入位置i，设在位置i插入元素的概率是pi

在第i个位置上插入元素的移动次数是n-i+1

二者相乘，把n+1个位置相乘的积连加就是Eis

不失一般性，假设在任意位置插入的概率是相等的

经过计算，Eis等于2分之n

从结果可以看出，平均移动次数是表长的一半

那么，当表长n比较大的时候

算法的效率可以说是比较低的

虽然Eis中n的系数较小

就数量级而言，它仍然是线性界的

因此算法的平均时间复杂度仍然是线性阶的

同学们，这一节就到这

下节课再见