2.3、线性表的链式表示与实现

在线性表的顺序表示与实现中，逻辑关系上相邻的两个元素在物理位置上也相邻。

优点：可以随机存取表中任一元素，他的存储公式可用一个简单、直观公式表示。

缺点：在做插入或者删除时，需要移动大量的元素。

链式存储结构，逻辑上相邻的元素物理位置不一定相邻，因此没有顺序表的缺点，但是没有顺序表随机存取的优点。

为了表示每个元素ai与下一个元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储本身信息外，还需要存储一个指示其直接后继的信息，这两部分信息组成数据元素ai的存储映像，称为结点（node）。

结点包括两个域，存储数据元素信息的域称为数据域，存储直接后继存储位置的域称为指针域。

由于此链表的每个结点中包含一个指针域，故又称为线性链表或者单链表。

/* c2-2.h 线性表的单链表存储结构 */
typedef struct LNode
{
ElemType data;
struct LNode *next;
};
typedef struct LNode *LinkList; /* 另一种定义LinkList的方法 */

假设L是LinkList型变量，则L为单链表的头指针，他指向表中的第一个结点。

有时我们在单链表的第一个节点之前附设一个结点，称之为头结点。头结点的数据域可以不存放任何信息，也可以存储如线性表的长度等的附加信息，头结点的指针域存储指向第一个结点的指针（即第一个元素结点的存储位置）。

在单链表中，取得第i个数据元素必须从头指针出发寻找，因此单链表是非随机存取的存储结构。

status GetElem_L(LinkList L, int i, ElemType &e) {

//L为带头结点的单链表的头指针

//当第i个元素存在时，其值赋给e并返回OK,否则返回ERROR

p=L->next;j=1; //初始化，p指向第一个结点，j为计数器

while(p&&j<i){

p=p->next; ++j;

}

if (!p || j>i) reurn ERROR; //第i个元素不存在

e = p->data; //取第i个元素

return OK;

}

在 单链表中若要插入元素x,首先要生成一个数据域为x的结点，然后再插入在单链表中。