单链表的定义、初始化、建立、插入、删除

单链表的定义

//单链表的定义,数据类型重命名
typedef struct LNode{
    int data;
    struct LNode * next;
}LNode,*LinkList;
//LNode *L与LinkList L表示的意思相同，都是生命一个指向单链表首结点的指针，是等价的
//一般LNode *强调这是一个结点，LinkList强调这是一个单链表

初始化带头结点的单链表

//初始化一个空的单链表——带头结点
bool InitList(LinkList &L){
    L=(LNode *)malloc(sizeof(LNode)*1);//分配一个头结点，不存数据，只是为了方便操作
    if(L==NULL)//内存不足，分配失败
        return false;
    L->next=NULL;//置空，表示还没有任何结点的单链表，避免脏数据
    return true;
}

初始化不带头结点的单链表

//初始化一个空的单链表——不带头结点
bool InitList(LinkList &L){
    L=NULL;//置空，表示还没有任何结点的单链表，避免脏数据
    //由此，判断头指针是否为空->判断单链表是否为空
    return true;
}
//注意不带头结点的单链表处理数据结点的代码逻辑与带头结点的处理逻辑不同
//对空表和非空表的处理逻辑也不同

按位插入元素（带头结点）

//按位插入元素——带头结点
bool ListInsert(LinkList &L,int i,int e){
    //判断插入位置合法性
    if(i<1)
        return false;
    if(p==NULL)
        return false;
    LNode *p;
    p=L;
    int j=0;//这里是0，表示当前p指向的是第0个结点，即头结点。
    //寻找第i个数据元素的前一个数据元素
    while(p!=NULL&&j-1){//p==NULL说明此时插入位置不合法，第i-1个元素不存在
        p=p->next;
        j++;
    }
    //申请一个结点存放要插入的数据e
    LNode *s=(LNode *)malloc(sizeof(LNode)*1);
    s->data=e;
    //插入
    s->next=p->next;
    p->next=s;
    return true;
}

按位插入元素——不带头结点

//按位插入元素——不带头结点
//因为不存在”第0个“结点，要注意i=1的情况
bool ListInsert(LinkList &L,int i,int e){
    if(i<1||p==NULL)
        return false;
    if(i=1){
        //不用借助标记LNode *p；
        LNode *s=(LNode *)malloc(sizeof(LNode)*1);
        s->data=e;
        s->next=L;//注意不带头结点，L指向第一个数据元素
        return true;
    }
    LNode *p=L;
    LNode *s=(LNode *)malloc(sizeof(LNode)*1);
        s->data=e;
    //寻找第i-1个数据元素
    int j=1;//注意这里是1，表示当前p指向的是第一个结点
    while(p!=NULL&&j-1)
    {
        p=p->next;
        j++;
    }
    s->next=p->next;
    p->next=s;
    return true;
}

在指定结点p之后插入元素e

//在指定结点p之后插入元素e
bool InsertNextNode(LNode * p,int e){
    //判断p的合法性
    if(p==NULL)
        return false;
    LNode *s=(LNode *)malloc(sizeof(LNode)*1);
    if(s==NULL)
        return false;//分配内存失败
    s->data=e;
    s->next=p->next;
    p->next=s;
    retur true;
}

在指定结点p之前插入元素e

//在指定结点p之前插入元素e
//我们在p之后插入元素e，再将两个结点交换即可，从而在O(1)时间复杂度下解决问题
bool InsertPriorNode(LNode * p,int e){
    if(p==NULL)
        return false;
    LNode *s=(LNode *)malloc(sizeof(LNode)*1);
    s->next=p->next;
    p->next=s;
    s->data=p->data;
    p->data=e;
    return true;
}
//法二
bool InsertPriorNode(LNode * p,LNode *s){
    if(p==NULL||s==NULL)
        return false;
    s->next=p->next;
    int temp=p->data;//申请中间变量保存结点的数据部分。
    p->data=s->data;
    s->data=temp;
    return true;
 
}

按位序删除结点（带头结点）

//按位序删除——带头结点
//要删除的元素结点设为q，q的前一个结点为p；
bool ListDelete(LinkList &L,int i,&e)
{
    if(i<1)//结点位序从1开始
        return false;
    int j=0;//j指向当前第0个结点，即头结点
    LNode * p=L;
    //找到第i-1个数据元素
    while(P!=NULL&&j-1){
        p=p->next;
        j++;
    }
    if(p==NULL)//遍历到第i-1个元素发现，前驱结点p不存在
        return false;
    if(p->next=NULL)//要删除的结点q不存在。
        return false;
    LNode *q=p->next;
    e=q->data;
    p->next=q->next;
    free(q);
    return true;
}

按位序删除结点（不带头结点）

//按位序删除——不带头结点
//要删除的元素结点设为q，q的前一个结点为p；
bool ListDelete(LinkList &L,int i,&e)
{
    if(i<1)//结点位序从1开始
        return false;
    int j=1;//j指向当前第1个结点，没有头结点，与带头结点的单链表的不同
    LNode * p=L;
    //找到第i-1个数据元素
    while(P!=NULL&&j-1){
        p=p->next;
        j++;
    }
    if(p==NULL)//遍历到第i-1个元素发现，前驱结点p不存在
        return false;
    if(p->next=NULL)//要删除的结点q不存在。
        return false;
    LNode *q=p->next;
    e=q->data;
    p->next=q->next;
    free(q);
    return true;
}

删除指定结点

//指定结点删除,将要删除的结点和其后面的一个结点交换，删除后面的结点即可
//这个方法，如果删除的正好是最后一个结点，没有后继结点交换时，要特殊处理，不方便
bool DeleteNode(LNode *p){
    //判断合法性
    //要删除的结点不存在
    if(p==NULL)
        return false;
    //p是尾结点
    if(p->next==NULL){
        //找到p的前一个结点q并q->next=NULL
        //申请标记指针r
        LNode * r=L;
        while(r->next!=p)
            r=r->next;
        q->next=NULL;
        free(p);
        return true;
    }
    else{
        //申请指针指向p的后一个结点
    LNode *q=p->next;
    p->data=q->data;
    p->next=q->next;
    free(q);
    return true;
    }
}

单链表按位查找（带头结点）返回结点

//单链表按位查找——带头结点
//返回第i个结点 位序
LNode * GetElem(LinkList L,int i){
    if(i<1)
        return NULL;//注意返回值
    //申请指针扫描链表
    LNode *p;
    p=L;
    int j=0;//j是头结点的位置
    while(p!=NULL&&j//保证遍历到第i个元素时，p指向的结点存在
        p=p->next;
        j++;
    }
    //找到第i个元素了
    return p;//遍历到第i个元素时，p指向的结点不存在的话，返回为NULL
}

单链表按位查找（不带头结点）返回结点

//单链表按位查找——不带头结点
//返回第i个结点 位序
LNode * GetElem(LinkList L,int i){
    if(i<1)
        return NULL;//注意返回值
    LNode *p;
    p=L;
    int j=1;//j是第一个结点结点的位置，和带头结点的单链表的区别
    while(p!=NULL&&j
        p=p->next;
        j++;
    }
    return p;
}

单链表按值查找（带头结点）返回结点

//单链表按值查找——带头结点
//返回结点
LNode * LocateElem(LinkList L,int e){
    //指针扫描单链表
    LNode * p=L->next;//带头结点
    //单链表不是空表
    while(p->data!=e&&p!=NULL){
        p=p->next;
    }
    return p;
}

单链表按值查找（不带头结点）返回结点

//单链表按值查找——不带头结点
//返回结点
LNode * LocateElem(LinkList L,int e){
    //指针扫描单链表
    LNode * p=L;//不带头结点
    //单链表不是空表
    while(p->data!=e&&p!=NULL){
        p=p->next;
    }
    return p;
}

尾插法建立单链表（带头结点）

//尾插法建立单链表——带头结点
LNode * List_TailiInsert(LinkList &L){
    int x;//插入的元素类型为整形
    //建立头结点,初始化空表
    L=(LinkList)malloc(sizeof(LNode)*1);
    //申请新结点
    LNode *r;
    r=L;//r为表尾指针，作为标记
    scanf("输入链表元素x= %d",&x);
    while(x!=9999){
        //申请结点加入链表；
        LNode *p=(LNode *)malloc(sizeof(LNode)*1);
        p->data=x;
        p->next=r->next;
        r-next=s;
        r=s;//r作为表尾指针向后挪
        scanf("输链表元素x= %d",&x);
    }
    r->next=NULL;
    return L;
}

尾插法建立单链表（不带头结点）

//尾插法建立单链表——不带头结点
LNode * List_TailiInsert(LinkList &L){
    int x;//插入的元素类型为整形
    //不用建立头结点
    //申请新结点
    LNode *r;
    r=L;//r为表尾指针，作为标记
    scanf("输入链表元素x= %d",&x);
    while(x!=9999){//如果输入9999代表单链表建立结束
        //申请结点加入链表；
        LNode *p=(LNode *)malloc(sizeof(LNode)*1);
        p->data=x;
        p->next=r->next;
        r-next=s;
        r=s;//r作为表尾指针向后挪
        scanf("输链表元素x= %d",&x);
    }
    r->next=NULL;
    return L;
}

尾插法建立单链表的后插思路

bool LinkInsert(LinkList &L,int i,int e){
    if(i<1)
        return false;
    LNode *p//表示当前扫描到的结点
    int j=0//有头结点，无头结点的时候j=1
    p=L;
    while(P!=NULL&&j-1){
        p=p->next;
        j++;
    }
    if(p==NULL)//i值不合法，找到位置i时，指针p超过表长了
        return false;
    LNode *s=(LNode *)malloc(sizeof(LNode)*1);
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}

头插法建立单链表（带头结点）

//头插法建立单链表——带头结点
//带头结点的单链表——对头结点的尾插操作(逆向建立单链表)
LNode * List_HeadInsert(LinkList &L){
    int x;//插入元素类型为整形
    //建立头结点
    LNode * L=(LNode *)malloc (sizeof(LNode)*1);
    L->next=NULL;//初始化为空链表，是一个习惯，防止脏数据
    scanf("输入元素x= ",&x);
    //开始循环输入元素值
    while(x!=9999){
        //申请新结点
        LNode *s=(LNode *)malloc(sizeof(LNode));
        s->data=x;
        s->next=L->next;
        L->next=s;
        //继续输入元素
        scanf("输入元素x= ",&x);
    }
    return L;
}

头插法建立单链表（不带头结点）

//头插法建立单链表——不带头结点
LNode * List_HeadInsert(LinkList &L){
    int x;//插入元素类型为整形
    //建立头结点
    //LNode * L=(LNode *)malloc (sizeof(LNode)*1);
    //L->next=NULL;//初始化为空链表，是一个习惯，防止脏数据
    scanf("输入元素x= ",&x);
    //开始循环输入元素值
    while(x!=9999){
        //申请新结点
        LNode *s=(LNode *)malloc(sizeof(LNode));
        s->data=x;
        s->next=L->next;
        L->next=s;
        //继续输入元素
        scanf("输入元素x= ",&x);
    }
    return L;
}

加油！