单链表

1、特点：任意存储，顺序存取

2、结构体定义和预定义

#include<stdio.h>
#include<stdlib.h>//malloc函数

#define ElemType int
#define Status int
#define ERROR 0
#define OK 1

typedef struct Lnode
{
   ElemType data;
   struct Lnode *next;
}Lnode,*Linklist;

3、初始化（本来头节点的初始化也放置在构建链表的函数中，但是一直段错误，所以吧头结点的初始化放在了主函数内）

void Create_L(Linklist L,int n)//头插法 还有一种尾插法，都可以简单实现
{
    int i;
    Linklist p;
    for(i = n;i>0;--i){//一开始需要定义节点个数
        p = (Linklist)malloc(sizeof(Lnode));
        printf("please input integer:");
        scanf("%d",&p->data);
        p->next = L->next;//头插法；
        L->next = p;
// q = L;q->next = p; q = p;尾插法 
    }
}

　4、获取单链表的第i个元素

//find获取第i个元素
Status GetElem_L(Linklist L,int i,ElemType *e)
{
    Linklist p;
    int j;
    p = L->next;//注意啊，单链表的操作，一般都会先赋值头节点，而不是直接拿头结点进行操作
    j = 1;
    while(p&&j<i)
    {
        p = p->next;//找到j的位置
        j++;
    }
    if(!p||j>i)
    {
        return ERROR;
    }
    *e = p->data;
    return OK;
}

　5、在i的位置插入元素e

//在i位置插入元素e
Status ListInsert_L(Linklist L,int i,ElemType e)
{
    Linklist p,s;
    p = L;
    int j = 0;
    while(p&&j<i-1)//找到插如位置的前一个节点
    {
        p = p->next;
        j++;
    }
    if(!p||j>i-1)
    {
        return ERROR;
    }
    s = (Linklist)malloc(sizeof(Lnode));//为新节点申请空间，把节点放进单链表中
    s->data = e;
    s->next = p->next;
    p->next = s; 
    return OK;
}

　　6、删除节点i并且保存其元素

//删除位置i的元素并且保存
Status ListDelete_L(Linklist L,int i,ElemType *e)
{
    Linklist p;
    Linklist q;
    int j = 0;
    p = L;
    while(p&&j<i-1)//找到删除节点的前一个
    {
        p = p->next;
        j++;
    }
    if(!p||j>i-1)
    {
        return ERROR;
    }
    q = p->next;
    *e = q->data;
    p->next = q->next;
    free(q);//释放删除节点的空间
    return OK;
}

　　7、两个单链表的操作，ab有序，c也有序

void MergeList_L(Linklist a,Linklist b,Linklist c)
{
    Linklist pa,pb,pc;
    pa = a->next;//有头结点
    pb = b->next;
    pc = c = a;
    while(pa&&pb)
    {
        if(pa->data <= pb->data)
        {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
        else
        {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    while(pa)
    {
        pc->next = pa;
        pc = pa;
        pa = pa->next;
    }
    while(pb)
    {
        pc->next = pb;
        pc = pb;
        pb = pb->next;
    }
    free(b);//a作为c的相应头结点，所以只释放了b
}

8、主函数

int main()
{
    Linklist La = (Linklist)malloc(sizeof(Lnode));
    La->next = NULL;;
    int n;
    int i = 2;
    ElemType e;
    printf("please input num:");
    scanf("%d",&n);
    Create_L(La,n);
    Output(La);

    GetElem_L(La,n,&e);
    printf("%d\n",e);

    ListInsert_L(La,i,e);
    Output(La);

    ListDelete_L(La,i,&e);
    printf("%d\n",e);
    Output(La);


    free(La);
    return 0;

}

　　9、输出函数

void Output(Linklist L)
{
    Linklist p = L->next;
    while(p)
    {
        printf("%4d",p->data);
        p = p->next; 
    }
    printf("\n");
}