单链表的基本操作

注：本文转自https://blog.csdn.net/weixin_45924251/article/details/106055264

已经作者本人授权转载

单项链表的一些基础使用方法包括：

创造单链表，其中含有两种创造方法：头插法和尾插法
输出单链表
在单链表中查找某个节点
在单链表中插入新的节点
在链表中删除一个节点或者多个某个内容相同的节点
对单链表进行排序
创造一个有序的单链表
主函数中的引用
那么接下来我们逐个解析：
大前提是用结构体作为节点，结构体中包含节点的内容和指向下一个节点的地址

typedef struct node
{
    int date;
    struct node *next;
}Lnode,*Linked;

1.创造单链表的两种方法：头插法的尾插法。

头插法：顾名思义就是将从第二个节点开始的到最后的节点依次插入到第一个节点的前方，头插头插当然要查到前面去，那么顺序输入则倒序输出。

尾插法：顾名思义就是从第二个节点开始到最后的节点依次插入到第一个节点后方，尾插尾插当然要从插到尾部去，那么顺序输入则顺序输出。

Linked get_linkedlist(int n)
{
    Linked H,p;
    int x,k=0;
    H=(Lnode*)malloc(sizeof(Lnode));
    H->next=NULL;
    while(k<n)
    {
        p=(Lnode*)malloc(sizeof(Lnode));
        scanf("%d",&x);
        p->date=x;
        p->next=H->next;
        H->next=p;
        k++;
    }
    return H;
}

尾插法：顾名思义就是从第二个节点开始到最后的节点依次插入到第一个节点后方，尾插尾插当然要从插到尾部去，那么顺序输入则顺序输出。

Linked get_linkedlist(int n)
{
    Linked H,r,p;
    int x,k=0;
    H=(Lnode*)malloc(sizeof(Lnode));
    H->next=NULL;
    r=H;
    while(k<n)
    {
        p=(Lnode*)malloc(sizeof(Lnode));
        scanf("%d",&x);
        p->date=x;
        r->next=p;
        r=p;
        k++;
    }
    r->next=NULL;
    return H
}

2 .链表的输出：

void Out(Linked H)
{
    Lnode *p;
    p=H->next;
    while(p)
    {
        printf("%d",p->date);
        p=p->next;
    }
}

3.在链表中查找一个节点：遍历整个链表，找到就标记并退出

int Find(Linked H,int goal)
{
    Lnode *p;
    int flag,k;
    flag=0;k=1;
    p=H->next;
    while(p)
    {
        if(p->date==goal){flag=1;break;}
        k++;
        p=p->next;
    }
    if(!flag)return 0;
    else return k;
    //这里的goal可以不是int型的，可以是一个链表的节点
}

4.链表的插入：插入的时候需要找到介于这个值得前和后，即前驱和后驱

Linked Insert(Linked H,int goal)
{
    Lnode *p,*pre,*tmp;
    pre=H;
    p=H->next;
    while(p&&p->date<goal)//这样可以避免要插入的数在最后的一个情况
    {
        pre=p;
        p=p->next;
    }
    tmp=(Lnode*)malloc(sizeof(Lnode));
    tmp->date=goal;
    pre->next=tmp;
    tmp->next=p;
    return H;
}

5.在链表中删除一个节点或者多个某个内容相同的节点：首先找到与要求相同的节点，再移动指针即可，相同的要删除一个节点和要插入一个节点相同，要找到要删除的节点的前驱和后驱。

Linked disapper(Linked H,int x)
{
    Lnode *p,*pre;
    pre=H;
    p=H->next;
    while(p)
    {
        if(p->date==x)
        {
            pre->next=p->next;
            free(p);
            p=pre->next;
        }
        else
        {
            pre=p;
            p=p->next;
        }
    }
    return H;
}

6.对链表进行排序：这里介绍冒泡排序，其中冒泡排序和用二级指针对字符串排序是不相同的，在这里直接做值的交换而不是交换指针，对于指针的写法需要注意一下，和数组相比仍然没有改变的是还是做了n*n次运算，仍然是双重循环。

Linked bouble(Linked H,int n)
{
    Lnode *p1,*p2,*q;
    q=NULL;
    p1=H->next;
    while(p1->next)
    {
        p2=H->next;
        while(p2->next!=q)
        {
            if(p2->date>p2->next->date)
            {
                int tmp;
                tmp=p2->date;
                p2->date=p2->next->date;
                p2->next->date=tmp;
            }
            p2=p2->next;
        }
        p1=p1->next;
    }
    return H;
}

7.创建一个有序的单链表就有两种思路了，可以先用一种链表创建方法创建一个链表，然后再进行排序，也可以一边创建节点，一边插入，这里我们讨论后一种，一边创建节点，一边插入。

void Insert(Linked H,Linked tmp)
{
    Lnode *pre,*p;
    pre=H;
    p=H->next;
    while(p&&p->date>tmp->date)
    {
        pre=p;
        p=p->next;
    }
    pre->next=tmp;
    tmp->next=p;
}
Linked get_linkedlist(int n)
{

    Linked H,p;
    H=(Lnode*)malloc(sizeof(Lnode));
    int x,k=0;
    while(k<n)
    {
        p=(Lnode*)malloc(sizeof(Lnode));
        scanf("%d",&p->date);
        Insert(H,p);
        k++;
    }
    return H;
}

8.在主函数的引用：

int main()
{
    Linked H;
    int n;
    H=(Lnode*)malloc(sizeof(Lnode));
    scanf("%d",&n);
    H=get_linkedlist(n);
    Out(H);
    return 0;
}

版权声明：本文为CSDN博主「凯撒袁六兽」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_45924251/article/details/106055264