1、线性表的逻辑结构
线性结构是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基
本特点是线性表中的数据元素是有序且是有限的。在这种结构中：
① 存在一个唯一的被称为“第一个”的数据元素；
② 存在一个唯一的被称为“最后一个”的数据元素；
③ 除第一个元素外，每个元素均有唯一一个直接前驱；
④ 除最后一个元素外，每个元素均有唯一一个直接后继。
例如： 线性序列 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 语言)环境下：数组具有随机存取的特性，因此，借助数组来描述顺序
表。除了用数组来存储线性表的元素之外，顺序表还应该有表示线性表的长度属性，所以用
结构类型来定义顺序表类型。
#define MAXSIZE 100 //数组最大长度
typedef struct { //定义线性表结构体
int data[MAXSIZE]; //线性表存储元素的数组
int length; //记录线性表的长度
} *SqList; //线性表的名称
顺序表小结。
1、单链表的定义
链式存储：用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表
简称线性链表。
为了正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其直接后
继结点的地址(或位置)，称为指针(pointer)或链(link)，这两部分组成了链表中的结点结构，
链表是通过每个结点的指针域将线性表的 n 个结点按其逻辑次序链接在一起的。每一个结只
包含一个指针域的链表，称为单链表。
存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散
分布在内存中的任意位置上的。链表中结点的逻辑顺序和物理顺序不一定相同。
操作方便，总是在链表的第一个结点之前附设一个头结点(头指针)head 指向第一个。
2、双向链表
双向链表(Double Linked List) :指的是构成链表的每个结点中设立两个指针域：一个指向
其直接前趋的指针域 prior，一个指向其直接后继的指针域 next。这样形成的链表中有两个
方向不同的链，故称为双向链表。将头结点和尾结点链接起来也能构成循环链表，并称之为
双向循环链表。
双向链表的结点的类型定义如下。其结点形式如图所示，带头结点的双向链表的形式如
图所示。
就是用数组来实现链式存储结构，目的是方便在不设指针类型的高级程序设计语言中使
用链式结构。实现原理：
1、使用结构体数组，结构体有指针域 cur 和数据域 data
2、一个数组分量表示一个节点，用 cur 代替指针指示节点在数组中
这章没有结束，请点击下一页继续阅读！