讲解（上）在线视频

刚才，我们讲了线性表的逻辑结构

现在，我们再来看线性表的物理结构

第一种物理结构——以顺序方式实现的线性表

称为顺序表

在这里有一个图，画出了以顺序方式存储的线性表

在内存当中的结构

n个元素

大家看到，占据着连续的存储单元

这时候，就称为顺序表

如果我们要找ai这个元素

它的地址，也就是Location(ai)，它的地址

应该等于它的前驱地址

加上每个元素所占的字节数

在左边的图当中

我们并没有清晰地画出，每个元素到底占多少个字节

因为，这个d取决于你要表达的应用

每个元素的类型不同

它占的字节数可能不同

如果继续向前推

可以用a1的地址来表示

ai的地址

因为，ai这个元素和a1这个元素

它们之间相隔了

i-1个元素

所以，ai的地址就是a1的地址

加上i-1乘上d，这个公式

就是著名的随机存取公式

随机存取的本质

就是：在一段连续的存储空间当中

找任何一个元素

它的位置，应该是在单位时间内找到的

因为，找任何一个元素ai的地址

实际上，CPU是做一个加法

一个首地址加上一个偏移量

无论给出来的偏移量是多少

CPU执行这个加法的时间是一样

我个人认为

随机存取的这个随机

翻译地不太确切

Random

我认为翻译成任意，比较合适一点

任意存取

就是：找一段连续的内存当中，任何一个元素

任意一个元素，所耗费的时间是一样的

就是首地址加上一个偏移量

我们在学C语言的时候，曾经学过一个等价的写法

ai这个元素

它的地址，实际上是等价于a+i的

我们知道，C语言的数组名代表着：数组所占连续存储空间的首地址

也就是a

ai这个元素，它的地址就是：首地址

加上一个偏移量

因为，C语言的数组下标从0开始

而刚才描述一个线性表的时候

第一个元素，是a1开始的；第n个元素，下标是n

所以，这里是i-1。在C语言里面，下标是从0开始的

所以，ai和a0这两个元素之间，实际上相隔了i个元素。有的同学可能会奇怪

为什么没有在i后面

再乘上每个元素所占的字节数呢

这是因为，C语言是一门高级语言

高级语言通常不关心

一个占了若干字节的数据

在内存当中的非首字节

比如，一个整型

假设是16位的，它占2个字节

我们在描述这个整型的地址的时候

描述的都是它所占2个字节的

第1个字节的地址

我们不会关心它的第2个字节

如果是汇编这样的语言

可能会关心它的高字节

但是，在高级语言当中，不会关心

除了首字节之外的其他字节

接下来，我们就要开始写代码了

用类C的代码，来描述出顺序表

首先，我们定义了一个宏

名字叫LIST_INIT_SIZE，从宏名可以看出

它代表着顺序表的初始容量

我们把它定义成100

紧接着，我们又定义了一个LIST_INCREMENT，线性表的增量

主要是用于：当线性表的空间不够的时候

要为线性表追加内存

我们一次追加多少呢

我们一次追加10个元素

所占用的字节

紧接着，我们定义了一个类型

我们给int型起了一个别名，叫ElemType，类似于这种代码

后面，我们会遇到很多次

这样做的目的，主要是为了让后面的代码显得更通用

我们定义了一个类型叫元素类型

只不过，为了能够让它是合法的代码

我们必须为一个已存在的类型

比如int，起一个新的名字

ElemType

这里，为了简单起见

我们就认为，线性表当中的元素都是整型

紧接着，我们定义了一个结构体

这个结构体是没有名字的

struct关键字

后面没有名字

它有3个成员

第1个成员，是指向ElemType类型的指针

大家注意到

elem这个成员

它是一个指针

elem的类型

我们刚才已经定义过了

elem代表的就是：连续存储空间的首地址

有了首地址

我们还必须告诉编译器

这一段连续的存储空间有多长

所以，有第3个成员，叫size，它代表的是线性表的容量

注意

容量跟长度是有区别的

容量是表示线性表能够存放的最多的元素个数

我们为线性表

假设分配了这么多的容量

那在某一个时刻，这一段内存当中

哪些位置才是属于线性表的呢

尽管在图上，我们可以用白色和灰色背景来标识

有些元素

比如灰色的，是不属于线性表的

但是，在内存当中

在任何时刻，内存都是有值的

你怎么知道一个线性表当中

从首地址开始

到哪个地方，才是属于线性表的元素呢

于是，我们还需要第2个成员length，来标识

线性表到底有多少个元素，也就是表长

然后，我们用typedef

给这样一个无名的结构体起了一个别名

叫SqList

这里的Sq

就是Sequential的意思

顺序表

我们来看几个表达式

第一个表达式，SqList L

我们声明了一个SqList类型的变量L

大家注意到，这里的L，已经是结构体类型了

千万不要在SqList的左边

再加上struct关键字

因为，刚才我们用typedef定义别名的时候

实际上就是给一个结构体定义的别名

L这个结构体，它的elem成员表示

连续存储空间的首地址

elem[0]，大家看到，我们这里把首地址当作一个数组名来用

这是C语言的特性之一

其实数组名就是一个地址

你定义的指针elem，实际上也可以当做数组名来用

既然下标是0

说明取的就是第1个元素

也就是a1

L.length，代表的是表长

也就是线性表

有多少个元素

L.elem[L.length - 1]，表长减1

肯定是最后一个元素

an的下标

这个表达式，代表的是an这个元素

L.size，代表的是线性表的容量

再次强调

这个size，表示的是：线性表能够存放的最多的元素个数

现在，我们来看第一个算法实现：初始化

在内存当中

我们要为L分配内存

然后，给L的各个成员赋以合适的初值

因为，L从无到有

所以，前面加了引用参数

我们现在使用C语言的malloc库函数

这个malloc

m代表的是memory

后面是allocate

内存分配函数

这是C语言的一个动态内存

分配API。它的参数是你想分配多少字节的内存

注意，这个单位是字节

我们刚才定义了一个宏，叫做

LIST_INIT_SIZE，就是第一次创建线性表的时候

我们定义的是100，我们为线性表分配100个元素所占的内存

那每一个元素占多少字节呢

我们用sizeof这个运算符取出来，sizeof的参数

是

元素类型——刚才定义的ElemType，线性表的容量乘以每个元素占的字节数

最后，我们再强制转换一下。这个强制转换，代表malloc分配的连续的存储空间

将来只能存放ElemType类型的数据，不能存放别的类型数据

malloc的返回值——如果成功，是你分配的这一段连续存储空间

它的首地址

也就是第一个元素所占的地址

我们将这个地址赋给L的elem成员

因为，elem成员代表的就是连续存储空间的首地址

当然

为了算法的健壮性

有可能指定的容量太大了

那么，malloc失败，也就是：没有足够的内存分配给你的线性表

这时候，malloc返回的实际上是0

也就是NULL

需要注意

C语言中，大写的NULL，并不是一个关键字

而是一个宏

如果大家打开

stdio这个头文件

你会发现，这个宏，它的值实际上是0

而C语言用0表示假，那么，非0就是真

那 !L.elem，就等价于L.elem==0，或者说==NULL，等于空

也就是，malloc返回0

我们要执行这个if语句

这时候，内存不够

我们直接就退出，exit是结束程序运行，参数是退出状态码，这个状态码

一般不会用到

正常情况下

这个if是不会成立的

也就是成功

分配了内存

这时候，我们将length定成0，表示是一个空表

然后将size

修改成LIST_INIT_SIZE

因为，初始大小就是LIST_INIT_SIZE