---

概述

单链表是链式存储的线性表，单链表为线性表中的每一个数据单元开辟一块空间，每块空间在物理位置上并不连续，每块空间中都有一个指针域用来存储下一块空间的位置，这样每一块空间在逻辑上便有了联系（逻辑上线性相连，每一块空间里都有下一个空间的地址）。

如下图所示：

 

整理一下：

 

 

 

头结点（head）的相关问题

每一个单链表都有一个头指针，头指针始终指向单链表的第一个空间，若有头结点则指向头结点，没有头结点指向第一个结点。

通常情况下，单链表都有一个头结点，这个结点并不存储数据（数据域实际可以使用，但通常不使用），但其指针域指向第一个结点所在的位置。

使用头结点之后，链表非空与空的两种情况下，无须进行特殊情况处理，因为头指针必定不为空。

在不实使用头结点的情况下，链表为空表时，头指针L为NULL。

单链表结点结构体的定义

typedef struct  LNode
{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

 

data是数据域，用来存储数据的。

next是指针域，用来存放下一个空间的地址，next是一个结构体指针类型的变量，只能存放LNode类型结构体的地址。

LinkList是结构体LNode类型的指针。

每一个结点占用一块空间，每一块空间物理上不连续，每一个结点使用next指针域指向下一结点的位置。

图片：

 

 

单链表的创建

1.头插法建立单链表

 

 

LinkList CreatList1(LinkList  &L){
    LNode *s;int x;
    L = (LinkList)malloc(sizeof(LNode));
    L -> next = NULL;
    scanf("%d",&x);
    while(x != 9999){
        s = (Node*)malloc(sizeof(No...