1. Python技术站首页
  2. other

详解C语言之单链表

• other
yizhihongxing

详解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日

相关文章

  • Java重写与重载之间的区别

    下面是“Java重写与重载之间的区别”的详细讲解攻略。 一、概述 Java中的方法支持两种不同的机制，即重写和重载。虽然这两种机制旨在实现方法的多态性，但它们的实现方式不同。因此必须理解它们之间的区别，才能正确使用它们。 二、方法的重载（Overloading） 方法重载是指在一个类中定义多个相同名称但参数列表不同的方法。在Java中，方法的参数列表不仅包括…

    other 2023年6月27日
    00

  • jquery插件lazyload.js延迟加载图片的使用方法

    下面是详细的jQuery插件lazyload.js延迟加载图片的使用方法攻略。 简介 lazyload.js是一款轻量级的jQuery插件，可以帮助网站实现图片的延迟加载，减少网站的加载时间。该插件使用非常简单，只需引入js文件并初始化即可。 安装 使用lazyload.js需要在HTML页面中引入jQuery库和lazyload.js文件，具体代码如下： …

    other 2023年6月25日
    00

  • synchronized优化

    synchronized优化 Java中的synchronized关键字是用来控制线程访问共享资源的并发机制。然而，如果不恰当地使用它，就很容易导致线程死锁、性能下降等问题。因此，针对synchronized的优化是非常重要的。 以下是几种优化synchronized的方法： 减小同步代码块的粒度 synchronized（锁定）操作是需要一定的系统开销的。…

    其他 2023年3月29日
    00

  • Go语言利用接口实现链表插入功能详解

    Go语言利用接口实现链表插入功能详解 简介 本篇攻略将会介绍如何使用Go语言的接口来实现链表的插入功能。链表是一种常用的数据结构，可以方便地在其中插入和删除元素。通过实现链表的插入功能，我们可以更全面地理解接口在Go语言中的应用。 链表结构体 在实现链表之前，我们需要定义一个链表的结构体。该结构体包含两个字段，一个是链表的元素值，另一个是后继指针。 type…

    other 2023年6月27日
    00

  • vue cli4.0项目引入typescript的方法

    第一步：安装Vue CLI 和 Typescript 首先，你需要安装 Vue CLI 和 Typescript。运行如下命令： npm install -g @vue/cli npm install -g typescript 第二步：创建 Typescript 项目 使用 Vue CLI 创建一个新的项目，并选择手动配置，勾选需要的特性。运行如下命令： …

    other 2023年6月27日
    00

  • c#chart控件教程

    C# Chart控件教程 介绍 C# Chart控件是.NET Framework中的一个可视化控件，可以用于绘制各种类型的图表，如折线图、柱状图、饼图等。在数据分析和可视化方面，Chart控件是一个非常强大的工具，使用它可以快速直观地展现数据结论。 本篇教程将为你带来Chart控件的基本使用方法，从创建控件到绘制图表，一步步指导你实现各种图表的绘制。 创建…

    其他 2023年3月28日
    00

  • 阿里路由框架ARouter 源码解析之Compiler

    阿里路由框架ARouter 源码解析之Compiler ARouter是一款阿里巴巴开源的Android路由框架，它提供了一种方便快捷的方式来实现组件之间的通信和页面跳转。在ARouter的源码中，Compiler模块起着重要的作用，它负责将注解处理器生成的代码编译成可执行的代码。下面是Compiler模块的详细解析。 1. Compiler模块的作用 Co…

    other 2023年10月13日
    00

  • 计算机怎么查内网和外网的ip？本机ip(外网、内网)查询方法介绍

    计算机怎么查内网和外网的IP？ 在计算机网络中，每个设备都有一个唯一的IP地址，用于在网络中进行通信。IP地址可以分为内网IP和外网IP。内网IP是在局域网中使用的地址，而外网IP是用于在互联网上进行通信的地址。下面是查找内网和外网IP的方法介绍： 查找内网IP Windows系统： 打开命令提示符（CMD）或PowerShell。 输入ipconfig命令…

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