单链表的创建、单链表的删除、单链表的插入（数据结构）

比眉伴天荒 2023-07-15 04:58 4阅读 0赞

### 1.创建一个超级简单的单链表 ###

#include <stdio.h>
    /*
    
    *csdn学院
    
    *目的：让代码见证成长(作为一个初学的菜鸟，如
    
    *大家有发现错误，欢迎指正！)
    
    *运行软件：CodeBlocks
    
    *作者:小臣小仁
    
    *完成日期:2020年3月15日
    
    */
    struct student
    {
        int num;//学号
        float score;//得分
        struct student *next;//指向下一个指针的结构体
    };
    int main()
    {
        struct student a,b,c,*p,*head;
        //给结构体赋值
        a.num=1001;
        a.score = 86;
    
        b.num=1002;
        b.score = 88;
    
        c.num = 1003;
        c.score = 98;
        //连接链表
        head = &a;
        a.next = &b;
        b.next = &c;
        c.next = NULL;
        //输出链表
        p = head;
        do
        {
            printf("%d %.2f\n",p->num,p->score);
            p = p->next;
        }while(p != NULL);
        return 0;
    }

运行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9jaGVueGlhb3Jlbg_size_16_color_FFFFFF_t_70][]

### 2、单链表的创建(尾插法) ###

#include <stdio.h>
    #include <stdlib.h>
    /*
    
    *csdn学院
    
    *目的：让代码见证成长(作为一个初学的菜鸟，如
    
    *大家有发现错误，欢迎指正！)
    
    *运行软件：CodeBlocks
    
    *作者:小臣小仁
    
    *完成日期:2020年3月18日
    
    */
    typedef struct NODE//创建结构体数组
    {
        int data;//存放数值
        struct NODE *next;//指向下一个结点
    }Node;
    /*功能：遍历链表，输出保存在data里面的内容*/
    void traverse(Node *Head)//遍历链表
    {
        Node *p = Head;//*p指针为运动的指针，指向头结点
        while(p != NULL)
        {
            printf("%-5d",p->data);//输出*p遍历到的结点值
            p = p->next;//*p继续指向下一个结点
        }
        printf("\n");
        return;
    }
    /*
    功能：将手动申请的空间释放释放
    */
    void Free_List(Node *Head)//释放链表
    {
        Node *pointer = NULL;//将替换头结点的指针先设为空
        while(Head != NULL)
        {
            pointer = Head->next;//指向链表下一个结点
            free(Head);//释放头结点
            Head = pointer;//将刚才*pointer指向的下一个节点设为头指针
        }
        return;
    }
    /*
    用尾插法建立一个单链表
    */
    void *createLinkList(int n)//创造链表
    {
        //将头指针Head，尾指针Last，指向申请空间的Pointer设为空，预防程序出错时指向随机的位置
        Node *pointer = NULL,*Last = NULL,*Head = NULL;
        int i=0;
        int d;//输入的数值存放的变量
        while(i<n)
        {
            pointer = (Node *)malloc(sizeof(Node));//动态申请空间
            printf("输入存入第%d个数据值:",i+1);
            scanf("%d",&d);
            pointer->data = d;//存入数值
            pointer->next = NULL;//指向下一个结点为空
            if(Head == NULL)//当头结点为空时，将头结点指向所申请的第一个结点
                Head = pointer;//头指针指向第一个结点
            else//当不为空时链表进行链表尾插入
                Last->next = pointer;
            Last = pointer;//将尾指针指移向尾部
            i++;
        }
        return Head;
    }
    int main()
    {
        Node *head;
        head=createLinkList(5);//创建单链表结点数为5个
        traverse(head);//遍历链表，输出存储数值
        Free_List(head);//释放链表
        return 0;
    }

输出结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9jaGVueGlhb3Jlbg_size_16_color_FFFFFF_t_70 1][]

### 3、单链表的插入 ###

#include <stdio.h>
    #include <stdlib.h>
    /*
    
    *csdn学院
    
    *目的：让代码见证成长(作为一个初学的菜鸟，如
    
    *大家有发现错误，欢迎指正！)
    
    *运行软件：CodeBlocks
    
    *作者:小臣小仁
    
    *完成日期:2020年3月15日
    
    */
    typedef struct NODE
    {
        int data;//存放数据
        struct NODE *next;//指向下一个节点
    }Node;
    
    /*功能：遍历链表，输出保存在data里面的内容*/
    void traverse(Node *h)
    {
        Node *p = h;//指向头指针
        while(p != NULL)
        {
            printf("%-5d",p->data);//输出data中保存的数据
            p = p->next;//p指向下一个节点的地址
        }
        printf("\n");
        return;
    }
    /*
    功能:将待插入的数插入链表
    */
    Node *insertNode(Node *h,int b)
    {
        Node *p,*q1,*q2;//这里p为存放插入的数据结构体，q1为
        q1 = h;//指向头结点
        p = (Node *)malloc(sizeof(Node));//开辟空间，生成新结点
        p->data = b;//保存插入的数值b
        if(h == NULL)//如果链表为空，p作为头结点
        {
            h = p;
            h->next = NULL;//链表指向空
        }
        else if(h->data > p->data)//当插入元素小于头结点元素，p作为头结点
        {
            h = p;//头结点赋值为p
            p->next = q1;//p指向的下一个节点为原来的头结点
        }
        else
        {
            while(q1!=NULL && p->data>q1->data)//当插入元素值大于头结点，往后找到合适位置
            {
                q2 = q1;//q2记录q1的值
                q1 = q1->next;//q1指向下一个结点
            }
            p->next = q2->next;//插入操作，p指向当前p的下一个节点
            q2->next = p;//q2的下一个节点变为p
        }
        return h;
    }
    /*
    功能：将手动申请的空间释放释放
    */
    void Free_List(Node *Head)
    {
        Node *pointer = NULL;
        if(Head != NULL)
        {
            pointer = Head;//指向头指针
            Head = Head->next;//头指针指向下一个节点
            free(pointer);//释放pointer指向的空间
        }
        return;
    }
    int main()
    {
        int b[6] = {34,56,43,67,32,98};//将这组数组插入链表，呈升序
        Node *head= NULL;//创建一个头结点
        int i = 0;
        while(i<6)
        {
            head = insertNode(head,b[i]);//将这组数组呈升序插入链表，返回头指针
            i++;
        }
        traverse(head);//遍历链表
        Free_List(head);//释放链表
        return 0;
    }

运行结果：

![20200315154720628.png][]

### 4、单链表的删除 ###

#include <stdio.h>
    #include <stdlib.h>
    /*
    
    *csdn学院
    
    *目的：让代码见证成长(作为一个初学的菜鸟，如
    
    *大家有发现错误，欢迎指正！)
    
    *运行软件：CodeBlocks
    
    *作者:小臣小仁
    
    *完成日期:2020年3月15日
    
    */
    /*结构体*/
    typedef struct NODE
    {
        int data;//每个结点的数据项
        struct NODE *next;//指向下一个节点
    }Node;
    /*遍历链表*/
    void traverse(Node *Head)
    {
        Node *pointer = Head;//移动指针*pointer指向头结点
        while(pointer != NULL)//*pointer不为空的情况下
        {
            printf("%-5d",pointer->data);//输出指针指向的数据项
            pointer=pointer->next;//指向链表的下一个节点
        }
        printf("\n");
        return;
    }
    /*释放链表*/
    void Free_List(Node *Head)
    {
        Node *pointer = NULL;//移动指针*pointer指向头结点
        while(Head != NULL)//当头指针不为空，循环执行
        {
            pointer = Head->next;//*pointer指向下一个节点
            free(Head);//释放头结点
            Head = pointer;//将指向下一个结点的*pointer的结点设为头结点
        }
        printf("链表已销毁\n");
        return;
    }
    /*插入链表*/
    Node *insertNode(Node *Head,int b)
    {
        Node *q1,*q2,*p;//设置*q1，*q2为可移动的替换指针，*p指向动态分配内存的指针
        q1 = Head;//指向头结点
        p = (Node *)malloc(sizeof(Node));//动态分配空间
        p->data = b;//将数组元素值赋值给指针
        if(Head == NULL)//没有头结点设为头结点
        {
            Head = p;//头结点指向*p
            p->next = NULL;//*p指向下一个结点为空
        }
        else if(Head->data > p->data)//数值比头结点数值小设为头结点
        {
            Head = p;//头结点指向*p
            p->next = q1;//*p的下一个结点指向*q1
        }
        else//数值大于头结点存储的数值
        {
            while(q1!=NULL && q1->data<=p->data)当*q1指针不为空且*q的数据值小于等于*p指向的数据值
            {
                q2=q1;//将指针*q2存*q1地址
                q1=q1->next;//q1指向链表下一个地址
            }
            p->next=q2->next;//将待插入链表指向待插入位置的下一关结点
            q2->next=p;//指针*q2下一关结点指向*p
        }
        return Head;
    }
    Node *deleteNode(Node *Head,int b)
    {
        Node *q = NULL,*p = Head;
        if(Head == NULL)//链表为空
        {
            printf("链表为空，删除失败\n");
        }
        else//链表不为空
        {
            while(p->data != b && p->next != NULL)//循环直到查找到要删除的位置
            {
                q = p;//*q指针存放*P地址
                p = p->next;//p继续往下查找
            }
            if(p->data == b)//找到待删除位置
            {
                if(p==Head)//如果为头结点
                {
                    Head = p->next;//头结点指向下一个结点
                }
                else//不是头结点
                {
                    q->next = p->next;//将要删除的上一个节点直接指向待删除的下一关结点
                }
                free(p);//释放代表将删除的结点*p
            }
            else
            {
                printf("%d 没有查找到，删除失败。\n",b);
            }
    
        }
        return Head;
    }
    int main()
    {
        int b[6]={23,34,55,29,78,15};//待插入的数组
        Node *Head=NULL;// 头结点指针
        int i;
        for(i=0;i<6;i++)
            Head = insertNode(Head,b[i]);//插入链表
        traverse(Head);//遍历链表
        Head = deleteNode(Head,29);//删除链表
        traverse(Head);//遍历链表
        Free_List(Head);//释放链表
        return 0;
    }

输出结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9jaGVueGlhb3Jlbg_size_16_color_FFFFFF_t_70 2][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9jaGVueGlhb3Jlbg_size_16_color_FFFFFF_t_70]: /images/20230528/6a20a61ddc094d04be146fa526fa3690.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9jaGVueGlhb3Jlbg_size_16_color_FFFFFF_t_70 1]: /images/20230528/5e5be2b3813e491bbfc086c238a785b3.png
[20200315154720628.png]: /images/20230528/66f73f674af14f61a189163c4abb5dc6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW9jaGVueGlhb3Jlbg_size_16_color_FFFFFF_t_70 2]: /images/20230528/bee0c02ec0e64db6b0aa041dcad5270e.png