一、前言
线性表的顺序存储结构特点是：逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中的任何一个元素。
缺点：在作插入删除操作时，需要移动大量元素。
二、链式存储结构
概念：它不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具有的弱点，但同时也失去顺序表可随机存取的优点。
三、线性链表
存储空间可以连续也可以不连续。为了表示ai和ai+1的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。它的节点包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链。n个节点链接成一个链表，即为线性表：
（a1,a2,…..,an）
又因为链表的每个节点中只包含一个指针域，故又称为线性链表或单链表。
用线性链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的。换句话说，指针为数据元素之间的逻辑关系的映像，则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻，因此这种存储结构为非顺序映像或者链式映像。
四、定义
|
1
2
3
4
5
6
7
8
9
|
typedef
struct
LNode
{
ElemType data;
struct
LNode *next;
} LNode *LinkList;
|
有时候我们在单链表的第一个结点之前附设一个结点，称之为头结点。头结点的数据域不存储任何信息，也可以附加如线性表的长度等类的附加信息，头结点的指针域存储指向第一个结点的指针
在单链表中，取得第i个数据元素必须从头指针出发寻找，因此单链表是非随机存取的存储结构。
取得第i个元素
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
Status GetElem_L(LinkList L,
int
i,ElemType &e)
{
//L为带头结点的单链表的头指针
//当第i个元素存在时，其值赋给e并返回ok，否则返回error
p = L->next;
//初始化，p指向第一个结点
j=1;
//初始化计数器
while
(p && j<i)
{
p = p->next;
++j;
}
if
(!p || j>i)
//第i个元素不存在
{
return
ERROR;
}
e = p->data;
//取得第i个元素
return
OK;
}
//GetElem_L
|
五、元素的插入和删除
例如要插入的元素为x,假设s为指向结点x的指针，则指针修改为
s->next = p->next;p->next = s;
若要删除元素，则需要
p->next = p->next->next;
六、静态链表
用数组描述的链表起名叫静态链表。
七、循环链表
它是另一种形式的链式存储结构。特点是表中最后一个结点的指针指向头结点，整个链表形成一个环。
八、双向链表
