美文网首页我用 Linux互联网科技Linux
小朋友学数据结构1:链表

小朋友学数据结构1:链表

作者: 海天一树X | 来源:发表于2019-04-06 10:43 被阅读7次

    链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

    1.png

    一、链表的创建操作

    刚开始,链表为空。咱们需要创建一个头节点。头节点可以用来存储节点数据,也可以不存储节点数据。咱们这里以不存储数据为例。
    (1)创建头节点
    因为头节点不存储数据,所以头节点的数据域可初始化为0或-1,也可以不用初始化,系统会自动分配一个随机数。

    2.png

    (2)插入第一个节点

    3.png

    上面这个图也可以简化表示为:

    4.png

    (3)插入第二个节点
    这里咱们假定不用考虑节点数据域值的大小顺序,直接插到链表的末尾即可。若要按数据域大小排序,插入时加个判断即可。

    5.png

    实现代码:

    #include<stdio.h>
    #include<malloc.h>
    
    typedef int ElementType;        //    定义数据类型,可根据需要进行其他类型定义
    
    // 定义链表结点
    typedef struct ListNode
    {
        ElementType  Element;  //    数据域,存放数据
        ListNode* Next;        //    指向下一个链表节点
    }Node, *PNode;
    
    //    链表创建函数定义
    PNode createList(void)
    {
        // 创建分配一个头节点内存空间,头节点相当于链表的哨兵,不存放数据
        PNode pHead = (PNode)malloc(sizeof(Node));
        if (pHead == NULL)    //    判断是否分配成功
        {
            printf("空间分配失败 \n");
            exit(-1);
        }
    
        PNode pTail = pHead;    //    链表的末尾节点,初始指向头节点
        pTail->Next = NULL;    //    最后一个节点指针置为空
    
        int len ;    //    用于定义链表长度
        int val ;    //    用于存放节点数值
        printf("请输入节点个数:");
        scanf("%d", &len);        //    输入节点个数
    
        for (int i = 0; i < len; i++)
        {
            PNode pNew = (PNode)malloc(sizeof(Node));    //    分配一个新节点
            if (pNew == NULL)
            {
                printf("分配新节点失败\n");
                exit(-1);
            }
    
            printf("请输入第 %d 个节点的数据:", i + 1);
            scanf("%d", &val);    // 输入链表节点的数据
    
            pNew->Element = val;  // 把数据赋值给节点数据域
            pTail->Next = pNew;   // 末尾节点指针指向下一个新节点
            pNew->Next = NULL;    // 新节点指针指向为空
            pTail = pNew;         // 将新节点复制给末尾节点
        }
    
        printf("创建链表成功\n");
    
        return pHead;    //    返回头节点
    }
    
    int main()
    {
        createList();    //创建一个指针,使其指向新创建的链表的头指针
        return 0;
    }
    

    运行结果:

    请输入节点个数:5
    请输入第 1 个节点的数据:10
    请输入第 2 个节点的数据:20
    请输入第 3 个节点的数据:30
    请输入第 4 个节点的数据:40
    请输入第 5 个节点的数据:50
    创建链表成功
    

    二、链表的遍历操作

    实现代码:

    // 定义链表遍历函数
    void traverseList(PNode head) 
    {
        PNode P = head->Next;       // 首节点赋值给临时节点P
        printf("遍历链表的值为:");
        if (P == NULL)
        {
            printf("链表为空");
        }
        
        while (P != NULL)           // 当临时节点P不为尾节点时,输出当前节点值 
        {
            printf("%d ", P->Element);
            P = P->Next;
        }
        
        printf("\n");
    }
    

    三、链表的查询操作

    // 定义链表查询函数
    PNode findNode(PNode head) 
    {
        PNode P = head->next;   // 定义临时指针P指向首节点的地址
        int num = 0;            // 用于记录链表节点位置
        int val = 0;            // 用于存放要查询的值
        printf("请输入要查询的数:");
        scanf("%d", &val);      //    输入要查询的数值
        while (P != NULL && P->Element != val) 
        {
            P = P->Next;
            ++num;
        }
        
        if (P != NULL)
        {
            printf("找到的节点为:%d", num + 1);
        }
        else
        {
            printf("找不到该节点");
        }
        
        printf("\n");
        
        return P;
    }
    

    四、链表的插入操作

    假设要插入到节点p和q之间,则需要执行两步操作:
    (1)s-> next = q,这是让s的next指向q;
    (2)p->next = s,这是让s成为p的下一个结点,此时p的next不再指向q。

    6.png

    上面这个图也可简化表示为:

    7.png

    实现代码:

    // 定义链表插入函数
    // 在链表位置第pos节点前插入包含数据val的节点
    void insertNode(PNode head, int pos, int val)
    {
        int position = 0;
        PNode P = head;    //    定义节点p指向头节点
        //    寻找pos节点的前驱结点
        while (P != NULL&&position<pos - 1)
        {
            P = P->Next;
            ++position;
        }
    
        PNode tmp = (PNode)malloc(sizeof(Node));    //    分配一个临时节点用来存储要插入的数据
        if (tmp == NULL)
        {
            printf("内存分配失败!");
            exit(-1);
        }
    
        //    插入节点
        tmp->Element = val;
        tmp->Next = P->Next;
        P->Next = tmp;
    }
    

    五、链表的删除操作

    (一)删除整个链表

    实现代码:

    // 定义删除整个链表函数
    void deleteList(PNode head) 
    {
        PNode P, tmp;
        P = head->Next;    //定义指针P指向链表要删除的链表List的第一个点节点
        List->Next = NULL;
        while (P != NULL)
        {
            tmp = P->Next;        //临时Tmp指向要删除的节点的下个节点
            free(P);    //释放指针P指向的节点
            P = tmp;    //重新赋值
        }
    
        printf("删除链表成功!\n");
    }
    

    (二)删除链表中的节点

    假如要删掉s节点,则需要做两步操作:
    (1)p->next = s->next,让s的下一个节点即q,变成p的下一个节点;

    8.png

    (2)free(s),把s节点从内存里释放。

    9.png

    实现代码:

    //  定义删除链表元素函数
    //  删除链表中的第pos个节点
    void deleteNode(PNode head, int pos) 
    {
        int position = 0;
        PNode P = head;    // 定义一个指针p指向链表头节点
        // 寻找pos节点位置的前驱节点
        while (P != NULL&&position < pos - 1) 
        {
            P = P->Next;
            ++position;
        }
    
        //    删除节点
        PNode tmp = P->Next;    //    定义临时指针Tmp指向要删除的节点
        P->Next = tmp->Next;    //    使要删除节点的前驱结点指向其后驱节点
        free(tmp);    //    释放删除节点的内存空间,防止内存泄漏
        tmp = NULL;    //    使q指向空指针,防止产生野指针
    }
    

    六、完整代码实现

    #include<stdio.h>
    #include<malloc.h>
    
    typedef int ElementType;    // 定义数据类型,可根据需要进行其他类型定义
                                // 链表节点的定义
    typedef struct ListNode
    {
        ElementType  Element;   // 数据域,存放数据
        ListNode* Next;         // 指向下一个链表节点
    }Node, *PNode;
    
    
    // 函数声明
    PNode createList(void);     // 声明创建链表函数
    void traverseList(PNode head);    // 声明遍历链表函数
    void insertNode(PNode head, int pos, int val);        // 声明链表插入函数
    void deleteList(PNode head);    // 声明删除整个链表函数
    void deleteNode(PNode head, int pos);    // 声明删除链表元素函数
    PNode findNode(PNode head);    // 声明链表查询函数
    
    
    int main()
    {
        PNode head = createList();  // 创建一个指针,使其指向新创建的链表的头指针
        traverseList(head);         // 遍历链表
        findNode(head);             // 链表查询
        insertNode(head, 3, 100);   // 链表插入,在第三个位置插入数值100
        traverseList(head);
        deleteNode(head, 3);        // 删除链表第三个节点
        traverseList(head);
        deleteList(head);        // 删除整个链表
        traverseList(head);
    
        return 0;
    }
    
    //    创建链表函数定义
    PNode createList(void)
    {
        int len ;    //    用于定义链表长度
        int val ;    //    用于存放节点数值
        PNode pHead = (PNode)malloc(sizeof(Node));    //    创建分配一个头节点内存空间
        if (pHead == NULL)    //    判断是否分配成功
        {
            printf("空间分配失败 \n");
            exit(-1);
        }
    
        PNode pTail = pHead;    //    链表的末尾节点,初始指向头节点
        pTail->Next = NULL;    //    最后一个节点指针置为空
        printf("请输入节点个数:");
        scanf("%d", &len);        //    输入节点个数
        for (int i = 0; i < len; i++)
        {
            PNode pNew = (PNode)malloc(sizeof(Node));    //    分配一个新节点
            if (pNew == NULL)
            {
                printf("分配新节点失败\n");
                exit(-1);
            }
    
            printf("请输入第 %d 个节点的数据:", i + 1);
            scanf("%d", &val);    //    输入链表节点的数据
    
            pNew->Element = val;    //    把数据赋值给节点数据域
            pTail->Next = pNew;    //    末尾节点指针指向下一个新节点
            pNew->Next = NULL;        //    新节点指针指向为空
            pTail = pNew;    //    将新节点复制给末尾节点
        }
    
        printf("创建链表成功\n");
    
        return pHead;    //    返回头节点
    }
    
    //    定义链表遍历函数
    void traverseList(PNode head)
    {
        PNode P = head->Next;    //    首节点赋值给临时节点P
        printf("遍历链表的值为:");
        if (P == NULL)
        {
            printf("链表为空");
        }
    
        while (P != NULL)        //当临时节点P不为尾节点时,输出当前节点值
        {
            printf("%d ", P->Element);
            P = P->Next;
        }
    
        printf("\n");
    }
    
    //    定义链表查询函数
    PNode findNode(PNode head)
    {
        PNode P = head->Next;    //    定义临时指针P指向首节点的地址
        int num = 0;    //    用于记录链表节点位置
        int val = 0;    //    用于存放要查询的值
        printf("请输入要查询的数:");
        scanf("%d", &val);    //    输入要查询的数值
        while (P != NULL&&P->Element != val)
        {
            P = P->Next;
            ++num;
        }
    
        if (P != NULL)
        {
            printf("找到的节点为:%d", num + 1);
        }
        else
        {
            printf("找不到该节点");
        }
    
        printf("\n");
    
        return P;
    }
    
    //     定义链表插入函数
    //    在链表位置第pos节点前插入包含数据val的节点
    void insertNode(PNode head, int pos, int val)
    {
        int position = 0;
        PNode P = head;    //    定义节点p指向头节点
                        //    寻找pos节点的前驱结点
        while (P != NULL&&position<pos - 1)
        {
            P = P->Next;
            ++position;
        }
        PNode tmp = (PNode)malloc(sizeof(Node));    //    分配一个临时节点用来存储要插入的数据
        if (tmp == NULL)
        {
            printf("内存分配失败!");
            exit(-1);
        }
    
        //    插入节点
        tmp->Element = val;
        tmp->Next = P->Next;
        P->Next = tmp;
    }
    
    //定义删除整个链表函数
    void deleteList(PNode head)
    {
        PNode P, tmp;
        P = head->Next;    //定义指针P指向链表要删除的链表List的第一个点节点
        head->Next = NULL;
        while (P != NULL)
        {
            tmp = P->Next;        //临时Tmp指向要删除的节点的下个节点
            free(P);    //释放指针P指向的节点
            P = tmp;    //重新赋值
        }
    
        printf("删除链表成功!\n");
    }
    
    //    定义删除链表元素函数
    //    删除链表中的第pos节点
    void deleteNode(PNode head, int pos)
    {
        int position = 0;
        PNode P = head;    //    定义一个指针p指向链表头节点
                        //    寻找pos节点位置的前驱节点
        while (P != NULL&&position < pos - 1)
        {
            P = P->Next;
            ++position;
        }
    
        //    删除节点
        PNode tmp = P->Next;    //    定义临时指针Tmp指向要删除的节点
        P->Next = tmp->Next;    //    使要删除节点的前驱结点指向其后驱节点
        free(tmp);    //    释放删除节点的内存空间,防止内存泄漏
        tmp = NULL;    //    使q指向空指针,防止产生野指针
    }
    

    运行结果:

    请输入节点个数:5
    请输入第 1 个节点的数据:10
    请输入第 2 个节点的数据:20
    请输入第 3 个节点的数据:30
    请输入第 4 个节点的数据:40
    请输入第 5 个节点的数据:50
    创建链表成功
    遍历链表的值为:10 20 30 40 50
    请输入要查询的数:30
    找到的节点为:3
    遍历链表的值为:10 20 100 30 40 50
    遍历链表的值为:10 20 30 40 50
    删除链表成功!
    遍历链表的值为:链表为空
    
    了解少儿编程、信息学竞赛请加微信307591841或QQ群581357582,关注公众号请扫描二维码 qrcode_for_kidscode_258.jpg

    相关文章

      网友评论

        本文标题:小朋友学数据结构1:链表

        本文链接:https://www.haomeiwen.com/subject/hrhsbqtx.html