第310章 有毛病！（1 / 2）

1、线性表的逻辑结构

线性结构是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基

本特点是线性表中的数据元素是有序且是有限的。在这种结构中：

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

2存在一个唯一的被称为“最后一个”的数据元素；

3除第一个元素外，每个元素均有唯一一个直接前驱；

4除最后一个元素外，每个元素均有唯一一个直接后继。

例如：线性序列a1，a2，…an线性表：是由n(n≧0)个数据元素(结点)a1，a2，…an组成的有限序列。该序列中的

所有结点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。

当n=0时，称为空表。

当n＞0时，将非空的线性表记作：(a1，a2，…an)

a1称为线性表的第一个(首)结点，an称为线性表的最后一个(尾)结点。

a1，a2，…ai-1都是ai(2≦i≦n)的前驱，其中ai-1是ai的直接前驱;

ai+1，ai+2，…an都是ai(1≦i≦n-1)的后继，其中ai+1。

2、顺序表

顺序存储：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这

种方法存储的线性表简称顺序表。

有非空的线性表：(a1，a2，…an)。顺序存储如图所示。

顺序存储的线性表的特点：

◆线性表的逻辑顺序与物理顺序一致;

◆数据元素之间的关系是以元素在计算机内

“物理位置相邻”来体现。设有非空的线性表：(a1，

a2，…an)。顺序存储如图所示。

设线性表的每个元素需占用l个存储单元，以所

占的第一个单元的存储地址作为数据元素的存储位

置。则线性表中第i+1个数据元素的存储位置Loc(ai+1)

和第i个数据元素的存储位置Loc(ai)之间满足下列关

系：Loc(ai+1)=Loc(ai)+l

线性表的第i个数据元素ai的存储位置为：数组具有随机存取的特性

Loc(ai)=Loc(a0)+(i)*l

在高级语言(如c语言)环境下：数组具有随机存取的特性，因此，借助数组来描述顺序

表。除了用数组来存储线性表的元素之外，顺序表还应该有表示线性表的长度属性，所以用

结构类型来定义顺序表类型。

#defeAxSIZE100\/\/数组最大长度

typedefstruct{\/\/定义线性表结构体

tdata[AxSIZE];\/\/线性表存储元素的数组

ih;\/\/记录线性表的长度

}*SqList;\/\/线性表的名称

顺序表小结。

1、单链表的定义

链式存储：用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表

简称线性链表。

为了正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其直接后

继结点的地址(或位置)，称为指针(poter)或链(lk)，这两部分组成了链表中的结点结构，

链表是通过每个结点的指针域将线性表的n个结点按其逻辑次序链接在一起的。每一个结只

包含一个指针域的链表，称为单链表。

存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散

分布在内存中的任意位置上的。链表中结点的逻辑顺序和物理顺序不一定相同。

操作方便，总是在链表的第一个结点之前附设一个头结点(头指针)head指向第一个。

2、双向链表

双向链表(doubleLkedList):指的是构成链表的每个结点中设立两个指针域：一个指向

其直接前趋的指针域prior，一个指向其直接后继的指针域。这样形成的链表中有两个