链式存储的基本实现

1.3线性表的链式存储结构(单链表)

  用一组地址任意的存储来存放线性表中的元素。

  以元素（数据元素的映象）+指针（指示后继元素存储位置）=结点（表示数据元素或数据元素的映象）

  以“结点的序列”表示线性表
          ————称作链表

  以线性表中第一个数据元素a~1~的存储地址作为线性表中的地址，称作线性表的头指针。
  有时为了操作方便，在第一个结点之前需加一个“头结点”，以指向头结点的指针为链表的头指针。

单链表的C语言实现：

typedef struct LNode{
    ElemType data;//数据域
    struct LNode *next;//指针域
}LNode, *LinkList;

LinkList L;//L为单链表的头指针;

单链表操作实现的基本实现：

• GetElem(L, i, e) //取第i个数据元素
• ListInsert(&L, i, e) //插入数据元素
• ListDelete(&L, i, e) //删除数据元素
• ClearList(&L) //重新置为一个空表
• CreateList(&L, n) //生成含$n$个数据元素的链表

找第1个数据元素，必须先找到第$i-1$个数据元素。因此，查找第i个数据元素的基本操作是==移动指针，比较j和i==。令指针p始终指向线性表中第j个数据元素。