//单链表 来自 王道
//有错误请指出，谢谢

1.单链表结点的定义：

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

2.利用头插法建立链表(逆序)
a.有头结点

    LinkList insert(LinkList &L)
    {
        LNode* s;int x;
        L=(LinkList)malloc(sizeof(LNode));
        L->next=NULL;
        scanf("%d",&x);
        while(x!=9999)
        {
            s=(LNode*)malloc(sizeof(LNode));
            s->data=x;
            s->next=L->next;
            L->next=s;
            scanf("%d",&x);
        }
        return L;
    }

b.没有头结点

    LinkList insert(LinkList L)
    {
        LNode* s;int x;
        scanf("%d",&x);
        while(x!=9999)
        {
            s=(LNode *) malloc(sizeof (LNode));
            s->data=x;
            s->next=L;
            L=s;
            scanf("%d",&x);
        }
        return L;
    }

3. 利用尾插法建立单链表(顺序)

LinkList insert(LinkList &L)
{
    LNode* s,*r;int x;
    L=(LinkList) malloc (sizeof (LNode));
    L->next=null;

    r=L;
    scanf("%d",&x);
    while(x!=9999)
    {
        s=(LNode *)malloc(sizeof (LNode));
        s->data=x;
        r->next=s;
        r=s;
        scanf("%d",&x);
    }
    r->next=null;
    return L;
}

4.按序号查找结点值

LNode * GetElem(LinkList L,int i)
{
    int j=1;
    LNode *p=L->next; //指向第一个结点
    if(i==0) return L;
    if(i<=0) return NULL;
    while(p && j<i)
    {
        p=p->next;
        j++; //不要忘记这句话
    }
    return p;
}

5.按值查找表结点

LNode *LocateElem(LinkList L,ElemType e)
{
    LNode *p=L->next;
    while(p!=NULL && p->data!=e)
    {
        p=p->next;
    }
    return p;
}

6.插入结点操作

插入结点操作将值为x的新节点插入到单链表的第i个位置上。
1.先检查位置的合法性
2.找到第i-1个结点
3.将新节点news插入

LNode *p=GetElem(L,i-1);
if(p!=NULL){
    news->next=p->next;
    p->next=news;
}


对某一个结点进行前插操作：
LNode *p=GetElem(L,i-1);
if(p!=NULL){
    news->next=p->next;
    p->next=news;
    //交换数据域部分
    temp=news->data;
    news->data=p->data;
    p->data=temp;
}

7.删除结点操作

删除链表的第i个结点
LNode p=GetElem(L,i-1);
if(p!=null)
{
    LNode *temp=p->next;
    p->next=temp->next;
    free(temp);
}

扩展：删除结点*p

下面：删除p的操作实际上用删除p的后继结点temp操作来实现
本质就是将后继结点temp的内容(数据域与指针域)赋值到p，再删除后继结点temp
temp=p->next;
p->data=temp->data;
p->next=temp->next;
free(temp);

8.求表长

即计算单链表中数据结点（不含头结点）的个数
因为单链表的长度使不包括 头结点的 ，所以处理 不带头结点和带头结点的操作会有不同。
对于不带头结点的单链表，当表为空时，要单独处理