数据结构（Chapter Two -03）—线性表的链式表示

在这一部分（数据结构(Chapter Two -01)—线性表及顺序表-CSDN博客）里面，我们知道线性表包括顺序表和链表结构。前面写了顺序表的基本操作，那这部分就写一写线性表叭！

链表特点：不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理地址上也相邻。

优点：插入和删除不需要移动元素（顺序表的缺点是需要移动）

缺点：不可以随机存取。需要额外的存放地址的指针域，浪费空间。

我们可以发现顺序表和链表的缺点和优点似乎恰好相反。来一个单链表结点的结构：

?我们可以看到指针域是存放下一个结点的地址的，每一个结点（除第一个）的读取都需要靠前一个结点读取，这就导致了缺点（不能随机读取）。

头指针：可用于标识一个单链表，如单链表L，头指针为NULL时表示一个空表。

头结点：为了操作上面的方便，通常会为单链表附加一个头结点。头结点数据域可以不设置任何信息，也可以记录表长等信息。

头结点和头指针的区别：不管带不带头结点，头指针都始终指向链表的第一个结点，而头结点是带头结点的链表中的第一个结点，结点内通常不存储信息。

举个栗子，下图为带了头结点的单链表：

引入头结点两个优点：

1、由于第一个数据结点的位置被存放头结点的指针域中，因此在链表的第一个位置上的操作和在表的其他位置上的操作一致，无需特殊处理。

2、无论链表是否为空，其头指针都指向头结点的非空指针（空表中头结点的指针域为空，但是可以存在）。

注意了：空表可以存在头结点（不存在的时候就是NULL），但是空表长度为0，因此线性表长度是不包括头结点的。

由以上我们可以写出单链表的结点描述，代码如下：

typedef struct LNode{    //定义单链表结点类型
    ElemType data;      //数据域
    struct LNode* next; //指针域
}LNode,*LinkList;
//头插法构建单链表
LinkList List_HeadInsert(LinkList &L){//逆向建立单链表
    LNode *s;
    int x;                           
    L = (LinkList) malloc(sizeof(LNode));//创建头结点，L指向的那片区域是头结点
    L->next = NULL;                   //初始为空链表
    scanf("%d",&x);                   //输入结点的值
    while(x!=9999){                   //输入9999表示结束
        s=(LNode*)malloc(sizeof(LNode));//创建新结点
        s->data=x;
        s->next=L->next;
        L->next=s;                   //将新结点插入表中，L为头指针
        scanf("%d",&x);
    }
    return L;
}
//尾插法构建单链表
LinkList List_TailInsert(LinkList &L){//正向建立单链表
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LNode *s,*r =L;                   //r表示尾指针
    scanf("%d",&x);                   //输入结点的值
    while(x!=9999){                   //输入9999表示结束
        s=(LNode*)malloc(sizeof(LNode));
        s->data =x;
        r->next =s;
        r=s;                           //r指向新的表尾结点
        scanf("%d",&x);
    }
    r->next = NULL;                    //尾结点指针设置为空
    return L;
}

其中头插法和尾插法的区别：插入的位置不同，头插法每一次都是在头结点的下一个插入，尾插法就是每一次插入的是链表的末端。