1. Python技术站首页
  2. other

详解C语言之单链表

• other

详解C语言之单链表

什么是单链表

单链表是一种数据结构，将数据存储在一系列的节点(Node)中。每个节点包含两部分：数据(Datum)和指向下一个节点的指针(Pointer)。节点之间通过指针连接起来，形成链表。单链表只能从头节点一直访问到尾节点，不能随机访问。

单链表的操作

单链表的常见操作有以下几个：

链表的创建

创建一个链表需要两个步骤：先创建头节点，再通过头节点逐个添加下一个节点。

typedef struct node *ptr;
typedef struct node {
    int data;       //数据
    ptr next;       //指向下一个节点的指针
} Node;

ptr create_list(int n) {
    ptr head;       //头节点
    ptr tail;       //尾节点
    int data;

    //创建头节点
    head = (ptr)malloc(sizeof(Node));
    if (head == NULL) {
        printf("Memory allocation failed.\n");
        return NULL;
    }
    head->data = 0;
    head->next = NULL;

    //逐个添加节点
    tail = head;
    while (n--) {
        printf("Enter data: ");
        scanf("%d", &data);

        //创建新节点
        ptr new_node = (ptr)malloc(sizeof(Node));
        if (new_node == NULL) {
            printf("Memory allocation failed.\n");
            return NULL;
        }
        new_node->data = data;
        new_node->next = NULL;

        //添加节点到链表尾部
        tail->next = new_node;
        tail = new_node;
        head->data++;  //节点数+1
    }
    return head;
}

链表的输出

输出链表需要遍历链表中的每一个节点。

void print_list(ptr head) {
    ptr p;
    p = head->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

链表的插入

插入操作有两种情况：在链表的头部插入一个新节点和在链表的中间插入一个新节点。

void insert_first(ptr head, int data) {
    //创建新节点
    ptr new_node = (ptr)malloc(sizeof(Node));
    if (new_node == NULL) {
        printf("Memory allocation failed.\n");
        return;
    }
    new_node->data = data;
    new_node->next = head->next;

    //插入新节点到头部
    head->next = new_node;
    head->data++;  //节点数+1
}

void insert_node(ptr head, int x, int data) {
    int i;
    ptr p;
    p = head->next;
    for (i = 1; i < x; i++) {
        p = p->next;
        if (p == NULL) {
            printf("Invalid position.\n");
            return;
        }
    }

    //创建新节点
    ptr new_node = (ptr)malloc(sizeof(Node));
    if (new_node == NULL) {
        printf("Memory allocation failed.\n");
        return;
    }
    new_node->data = data;
    new_node->next = p->next;

    //插入新节点到中间
    p->next = new_node;
    head->data++;  //节点数+1
}

链表的删除

删除操作也分为两种情况：从链表的头部删除一个节点和从链表的中间删除一个节点。

void delete_first(ptr head) {
    ptr p;
    if (head->next == NULL) {
        printf("List is already empty.\n");
        return;
    }
    p = head->next;
    head->next = p->next;
    free(p);
    head->data--;  //节点数-1
}

void delete_node(ptr head, int x) {
    int i;
    ptr p, q;
    p = head->next;
    for (i = 1; i < x; i++) {
        q = p;
        p = p->next;
        if (p == NULL) {
            printf("Invalid position.\n");
            return;
        }
    }
    q->next = p->next;
    free(p);
    head->data--;  //节点数-1
}

示例说明

示例一

用户需要输入5个整数创建一个链表，然后依次输出链表中的内容。最后在链表的第3个位置插入一个新节点，然后删除链表的第4个节点。

#include <stdio.h>
#include <stdlib.h>

typedef struct node *ptr;
typedef struct node {
    int data;       //数据
    ptr next;       //指向下一个节点的指针
} Node;

ptr create_list(int n) {
    ptr head;       //头节点
    ptr tail;       //尾节点
    int data;

    //创建头节点
    head = (ptr)malloc(sizeof(Node));
    if (head == NULL) {
        printf("Memory allocation failed.\n");
        return NULL;
    }
    head->data = 0;
    head->next = NULL;

    //逐个添加节点
    tail = head;
    while (n--) {
        printf("Enter data: ");
        scanf("%d", &data);

        //创建新节点
        ptr new_node = (ptr)malloc(sizeof(Node));
        if (new_node == NULL) {
            printf("Memory allocation failed.\n");
            return NULL;
        }
        new_node->data = data;
        new_node->next = NULL;

        //添加节点到链表尾部
        tail->next = new_node;
        tail = new_node;
        head->data++;  //节点数+1
    }
    return head;
}

void print_list(ptr head) {
    ptr p;
    p = head->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

void insert_node(ptr head, int x, int data) {
    int i;
    ptr p;
    p = head->next;
    for (i = 1; i < x; i++) {
        p = p->next;
        if (p == NULL) {
            printf("Invalid position.\n");
            return;
        }
    }

    //创建新节点
    ptr new_node = (ptr)malloc(sizeof(Node));
    if (new_node == NULL) {
        printf("Memory allocation failed.\n");
        return;
    }
    new_node->data = data;
    new_node->next = p->next;

    //插入新节点到中间
    p->next = new_node;
    head->data++;  //节点数+1
}

void delete_node(ptr head, int x) {
    int i;
    ptr p, q;
    p = head->next;
    for (i = 1; i < x; i++) {
        q = p;
        p = p->next;
        if (p == NULL) {
            printf("Invalid position.\n");
            return;
        }
    }
    q->next = p->next;
    free(p);
    head->data--;  //节点数-1
}

int main() {
    ptr list_head;
    list_head = create_list(5);
    printf("List content: ");
    print_list(list_head);
    insert_node(list_head, 3, 10);
    printf("List content after insertion: ");
    print_list(list_head);
    delete_node(list_head, 4);
    printf("List content after deletion: ");
    print_list(list_head);
    return 0;
}

输出结果：

Enter data: 1
Enter data: 2
Enter data: 3
Enter data: 4
Enter data: 5
List content: 1 2 3 4 5
List content after insertion: 1 2 3 10 4 5
List content after deletion: 1 2 3 10 5

示例二

程序先创建一个空链表，然后依次在链表的头部插入5个新节点，最后逐个删除链表中的所有节点。

#include <stdio.h>
#include <stdlib.h>

typedef struct node *ptr;
typedef struct node {
    int data;       //数据
    ptr next;       //指向下一个节点的指针
} Node;

ptr create_list(int n) {
    ptr head;       //头节点
    ptr tail;       //尾节点
    int data;

    //创建头节点
    head = (ptr)malloc(sizeof(Node));
    if (head == NULL) {
        printf("Memory allocation failed.\n");
        return NULL;
    }
    head->data = 0;
    head->next = NULL;

    //逐个添加节点
    tail = head;
    while (n--) {
        printf("Enter data: ");
        scanf("%d", &data);

        //创建新节点
        ptr new_node = (ptr)malloc(sizeof(Node));
        if (new_node == NULL) {
            printf("Memory allocation failed.\n");
            return NULL;
        }
        new_node->data = data;
        new_node->next = NULL;

        //添加节点到链表尾部
        tail->next = new_node;
        tail = new_node;
        head->data++;  //节点数+1
    }
    return head;
}

void print_list(ptr head) {
    ptr p;
    p = head->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

void insert_first(ptr head, int data) {
    //创建新节点
    ptr new_node = (ptr)malloc(sizeof(Node));
    if (new_node == NULL) {
        printf("Memory allocation failed.\n");
        return;
    }
    new_node->data = data;
    new_node->next = head->next;

    //插入新节点到头部
    head->next = new_node;
    head->data++;  //节点数+1
}

void delete_first(ptr head) {
    ptr p;
    if (head->next == NULL) {
        printf("List is already empty.\n");
        return;
    }
    p = head->next;
    head->next = p->next;
    free(p);
    head->data--;  //节点数-1
}

int main() {
    ptr list_head;
    list_head = create_list(0);
    insert_first(list_head, 1);
    insert_first(list_head, 2);
    insert_first(list_head, 3);
    insert_first(list_head, 4);
    insert_first(list_head, 5);
    printf("List content after insertions: ");
    print_list(list_head);
    while (list_head->next != NULL) {
        delete_first(list_head);
        printf("List content after deletion: ");
        print_list(list_head);
    }
    return 0;
}

输出结果：

Enter data: 1
Enter data: 2
Enter data: 3
Enter data: 4
Enter data: 5
List content after insertions: 5 4 3 2 1 
List content after deletion: 4 3 2 1 
List content after deletion: 3 2 1 
List content after deletion: 2 1 
List content after deletion: 1 
List content after deletion:

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：详解C语言之单链表 - Python技术站

赞 (0)
0 0 打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023年6月27日
下一篇 2023年6月27日

相关文章

  • cmd批处理 goto call命令使用说明

    cmd批处理 goto call命令使用说明 命令说明 在cmd批处理中，goto和call命令都是控制跳转的命令，它们可以让脚本跳转到指定的标签或调用另一个批处理文件执行。 goto命令语法 goto 标签名 标签名：指定要跳转的标签名称。 注意：标签名前要加冒号。 goto命令用法示例一 @echo off set /p name=请输入名字： if &…

    other 2023年6月26日
    00

  • 苹果ios8.1.3正式版固件下载地址汇总【附ios8.1.3升级教程】

    苹果iOS 8.1.3正式版固件下载地址汇总【附iOS 8.1.3升级教程】 iOS 8.1.3是苹果公司发布的一款重要的操作系统更新版本。本攻略将为您提供iOS 8.1.3正式版固件的下载地址，并附上升级教程，以帮助您顺利完成升级过程。 iOS 8.1.3正式版固件下载地址 您可以通过以下方式获取iOS 8.1.3正式版固件： 官方下载地址：您可以直接从苹…

    other 2023年8月4日
    00

  • C语言 经典题目螺旋矩阵 实例详解

    C语言 经典题目螺旋矩阵 实例详解 问题描述 给定一个正方形的矩阵，要求以从左上角开始，顺时针方向遍历所有元素，按照遍历顺序存储到一个一维数组中。如下图所示，对于输入的矩阵 arr，应输出一个一维数组 res，其中res = {1, 2, 3, 6, 9, 8, 7, 4, 5}。 1 2 3 4 5 6 7 8 9 解题思路 我们可以定义一个方向数组dir…

    other 2023年6月27日
    00

  • Android权限控制之自定义权限

    Android权限控制是Android开发中很重要的一个方向，涉及到用户数据的保护和应用功能的合理使用。在Android中，权限分为系统权限和普通权限，系统权限包括网络连接、电话、短信、位置、存储等等，普通权限包括摄像头、录音、震动等。虽然系统已经提供了大量的权限，能够满足大部分应用的需求，但是仍然有一些特殊的权限需要我们自定义。 下面是自定义权限的攻略，分…

    other 2023年6月25日
    00

  • 浅谈angular2 组件的生命周期钩子

    下面我会详细讲解“浅谈Angular2组件生命周期钩子”的攻略。 什么是组件生命周期钩子 组件生命周期钩子是Angular中的一组接口，用来监视组件中不同阶段的状态变化，以便在合适的时候执行相应的处理逻辑。它们分为两类：视图生命周期钩子和组件本身的生命周期钩子。组件生命期钩子被调用的顺序是固定的，具体如下： // 组件实例化，分配内存空间，并设置默认属性 c…

    other 2023年6月27日
    00

  • Photoshop技巧：需要自定义的10个快捷键

    Photoshop技巧：需要自定义的10个快捷键 Photoshop中有很多功能强大但操作繁琐的功能，使用快捷键能大大提高工作效率。除了Photoshop默认提供的快捷键，你还可以自定义适合自己的快捷键。下面是需要自定义的10个快捷键。 1. 合并图层 合并图层是Photoshop中常用的功能，需要同时按下Ctrl+E，比较繁琐。可以使用自定义快捷键提高效率…

    other 2023年6月25日
    00

  • Win10 CMD命令大全与超好用的快捷键(史上最全)

    Win10 CMD命令大全与超好用的快捷键 本文将介绍Windows 10中常用的CMD命令行和快捷键的大全，包括语法、用法和示例。由于篇幅较长，建议使用书签进行收藏，以备将来使用。 命令行提示符 CMD命令行提示符是Windows下最常用的命令行界面，它通常以黑色背景显示，可以通过以下方法打开： 在Windows 10中搜索“cmd”或“命令提示符”，然后…

    other 2023年6月26日
    00

  • C语言深入了解自定义数据类型的使用

    C语言深入了解自定义数据类型的使用攻略 1. 自定义数据类型的定义 在C语言中，可以通过 typedef 关键字来定义自定义数据类型。定义的语法格式如下： typedef 原类型名 自定义类型名; 下面是一个简单的示例： typedef int INT; 上面的代码定义了一个名为 INT 的新类型，其实质就是 int 类型的别名。 2. 自定义数据类型的使用…

    other 2023年6月25日
    00
合作推广
合作推广
分享本页
返回顶部