2.1线性表的类型定义在线视频

同学们，大家好，我是云南大学信息学院教师孔兵

今天我们开始数据结构第2章的学习

第一节，我们首先讨论线性表的类型定义

线性表是n个数据元素的有限序列

且表中数据元素属同一数据对象

在前面例子当中，提到图书馆的书籍排列成了一个线性表

线性结构最重要的特征就是，它是一个系列

既然是一个序列，就有一些特点

存在唯一的一个被称为第1个的数据元素

也就是排在序列，最开始的这个元素

存在唯一一个被称为最后一个的数据元素

就是排在序列最尾部的这个元素

除了第1个元素之外

序列中每个数据元素均只有一个前驱

除了最后一个元素之外

序列中每个数据元素均只有一个后继

就是前面提到的一个前驱一个后继

线性表的描述前面提到过

在逻辑结构这个层面上来说

线性表可以描述为一个a1a2到 a n的序列

或者图示，顶点表示数据元素

通过箭头来描述前驱和后继的关系

也可以通过形式化的描述

用一个集合描述数据元素

用另外一个有序对的集合描述数据元素之间的关系

这些我们前面都讨论过

线性表的长度是指线性表中数据元素的个数

当n等于0的时候，一个线性表被称为空表

抽象数据类型线性表的定义分为三个部分

首先定义数据对象D，这是线性表中所包含的元素

有a1到an n个元素

随后，用有序对的集合描述数据元素之间的关系

从定义可以看出，i从2开始一直到n

它定义了a1的后继是a2, a2的后继是a3.

以此类推，直到an-1的后继是an.

通过这样方式

定义了线性表的序列

前面两者构成了线性表的数据结构

第3部分定义了在数据结构上的基本操作

教材上的介绍了很多基本操作

这里呢我们给出5个

包括初始化、线性表判空、求线性表长度

取线性表中一个元素和线性表的插入五个操作

我们以插入操作为例，介绍一下基本操作的定义方式

我们要强调的是，基本操作是定义在逻辑结构上的

插入操作包含3个参数

第1个参数指明作为插入对象的线性表L

第2个参数i给出的是插入的逻辑位置

线性表是一个序列，这里的i指的是序列中的第i个位置

从图上可以看出，其含义就是把数据元素

插入到序列中ai这个元素的位置

第3个参数e给出要插入的数据元素

完成插入以后，线性表长度增1，e变成了

ai-1的后继，ai的前驱

e占据了原来序列中的第i个位置

把原位置的ai挤朝后一个位置

取线性表中一个元素的操作与此类似

第2个参数i也是给出要取

元素在序列中的逻辑位置

取中的元素用引用e带回

对基本操作的定义方式，我们总结一下

基本操作的意义是定义在逻辑结构上的

如上面介绍的插入操作

操作的含义都是逻辑结构的序列上定义的

在逻辑结构，序列的第i个位置插入元素

第1章中，我们介绍过

线性表有两种存储实现方式

一种是顺序映象，利用一个数组实现线性表的存储

一种是非顺序映象，借助指针

用链表实现线性表的存储

我们可以注意到

线性表不同的存储方式下

基本操作的实现方式是不一样的。

以插入操作为例

如果用一个数组实现线性表的存储

实现插入操作时需要把ai到an

这段的元素依次后移一个位置

再把e插入到原来ai存储的位置

而在链式结构当中，实现同样的操作

可能需要申请一个节点，存储e

然后通过指针的重新赋值来实现插入

从插入操作的讨论可以看出

基本操作的具体实现，和存储结构有关

不同的存储结构实现方式是不一样的

基本操作可以理解为抽象数据类型对外部程序的接口

当其它程序使用到线性表的时候

可以通过反复调用基本操作实现自己更复杂的功能

从这儿也可以看出定义抽象数据类型的好处

其它程序只需要按照线性表的逻辑含义

通过调用基本操作，就可以使用它

而不必关心线性表具体实现的方法

下面我们通过一个例子看一看

如何通过调用基本操作实现更复杂的功能

这个例子是有序表的合并

假定两个线性表是有序的，例如LA和LB

我们想把这两个有序表合并为一个新的有序的线性表LC

LC初始为一个空表

解决问题的步骤，大致分两步

第1步，首先比较LA和LB中的第1个元素

示例中分别是3和2. 2相对较小

我们就把2插入到LC中

随后，取LB中下一个元素6和LA中的3继续进行比较

比较以后，3较小，把3插入到LC中

继续取LA中下一个元素5和LB中的6”

继续进行比较

就这样反复进行两两比较

直到某个序列中的元素被全部送入LC中为止

当一个系列处理完以后，就可以进行第2步了

把未处理完的序列中的元素依次插入到LC中

不用比较了

下面我们看看有序表的合并算法

合并算法中有三个参数

分别是要合并的有序表la和lb.

以及合并以后的所产生的线性表Lc

整个算法可以分为三块

黄色这一块是为后面的比较做准备

首先调用初始化操作，对LC做初始化

可理解为对LC置空，为后面的插入做准备

随后，把i和j赋值1.

分别指明两个序列中的第1个元素

这是首先参与比较的两个元素

K 赋值0，表示LC中元素的个数

初始的时候lc是空的，没有元素

所以其长度等于0.

随后调用基本操作分别求la和lb的长度

结果赋值la-len和lb-len两个变量

绿色这一块是两两比较

当i小于la-len，同时j小于lb-len

这样的条件下，也就是说两个系列都没有处理完

我们进行元素的两两比较

用取元素的操作

从la中，第i个位置取出元素，用ai带回

同样，从序列lb中取出第j个位置的元素

用bj带回

从i和j的初始初始值看

首先比较的是两个序列的第1个元素。

随后进行两个元素的比较

如果ai小于等于bj，我们调用插入操作

把ai插入到LC中

注意插入位置的实参++k

K是lc中已有元素的个数

那么新插入的元素在LC中的位置

应该是现有元素个数的下一个位置

所以，我们先对k做自加

计算插入的位置，再把它作为参数传递给插入函数

因为在这儿是把从la序列中第i个位置取到的元素ai插入到LC

所以做++i，为下一次两两比较做准备

Else后的情况和这类似

只不过插入的是lb中的元素

如果满足循环条件，继续两两比较

当循环条件不满足的时候

一定有某一个序列已经被全部取完

那么两两比较的循环就结束了

蓝色部分这段代码主要是把未取完序列的元素依次插入到LC中

第1个循环处理的是，La中的元素没有取完的情况

当i小于等于la-len的时候，表示la系列没有处理完

首先也是调用取元素这个基本操作

从la中，把第i个位置的元素取出,用ai带回

这里要注意一下i++

这是先把i作为实参传递给形参

作为本次取元素的位置

随后再做自加

为取下一个元素做好准备

插入操作的情况和上面类似

就不再讨论了

第2个循环处理

Lb中的元素没有取完的情况

处理的方式类似

从有序表的合并算法来看

这是一个相对复杂的程序

它通过调用基本操作，实现了合并的功能

这个程序在调用基本操作的时候

并不考虑基本操作的具体实现方式

只是利用这些接口来使用线性表

关于线性表的定义以及基本操作的情况

我们就讨论到这儿

同学们

下一节课再见