C语言链表与单链表详解

C语言链表与单链表详解

什么是链表

链表是由一系列节点组成的线性结构,每个节点由两个部分组成:数据域和指针域。数据域用来存储节点的数据,指针域用来指向下一个节点的地址,也就是说每个节点保存了下一个节点的地址信息。由此构成的链式结构被称为链表。

链表相对于数组来说,其大小可以动态调整,插入和删除元素操作更加高效。

单链表

单链表是链表的一种,每个节点中只包含一个指针,指向下一个节点的地址。链表的头节点不包含数据,只包含指向第一个节点的指针。

单链表结构体定义

在C语言中,可以如下定义单链表结构体:

typedef struct node {
    int data;           // 数据域
    struct node *next;  // 指针域
} Node, *LinkList;

其中,Node表示一个节点,LinkList代表一个指向链表头节点的指针。

单链表的创建

单链表的创建需要一个头节点和一系列数据,可以使用一个循环来依次添加节点,最后返回头节点指针。

LinkList createList() {
    Node *head, *tail, *p;
    int data;
    head = tail = (Node*)malloc(sizeof(Node));
    tail->next = NULL;
    printf("请输入数据,输入-1结束:\n");
    scanf("%d", &data);
    while (data != -1) {
        p = (Node*)malloc(sizeof(Node));
        p->data = data;
        tail->next = p;
        tail = p;
        scanf("%d", &data);
    }
    tail->next = NULL;
    return head;
}

在该函数中,首先定义头节点和尾节点,然后按顺序添加节点,直到输入-1停止。最后返回头节点指针。

单链表的遍历

单链表的遍历可以使用一个指针从头节点开始挨个访问每个节点。

void traverseList(LinkList list) {
    Node* p = list->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

该函数首先将指针指向第一个节点,若节点存在,则输出数据域,并将指针指向下一个节点,循环直到最后一个节点。

单链表的插入

单链表的插入需要指定插入位置,可以使用一个指针找到待插入位置,然后插入新节点。

void insertNode(LinkList list, int data, int pos) {
    Node* p = list;  // 创建指针指向第一个节点
    Node* q = NULL;  // 创建指针指向待插入位置前面的节点
    Node* new = NULL;  // 创建新节点
    int i = 1;
    while (p != NULL && i < pos) {  // 找到待插入位置的前一个节点
        p = p->next;
        i++;
    }
    if (p == NULL || i > pos) {  // 位置不合法,退出插入。
        printf("位置不合法\n");
        return;
    }
    q = p->next;  // 待插入位置前一个节点
    new = (Node*)malloc(sizeof(Node));  // 创建新节点
    new->data = data;  // 写入数据域
    new->next = q;  // 连接到后面的节点
    p->next = new;  // 连接到前面的节点
}

该函数首先根据输入的位置找到待插入位置和前一个节点,然后创建新节点,并将它插入到链表中。

单链表的删除

单链表的删除同样需要指定删除位置,可以使用一个指针找到待删除位置,然后删除该节点。

void deleteNode(LinkList list, int pos) {
    Node* p = list;  // 创建指针指向第一个节点
    Node* q = NULL;  // 创建指针指向待删除位置前面的节点
    int i = 1;
    while (p != NULL && i < pos) {  // 找到待删除位置的前一个节点
        p = p->next;
        i++;
    }
    if (p == NULL || i > pos || p->next == NULL) {  // 位置不合法,退出删除。
        printf("位置不合法\n");
        return;
    }
    q = p->next;  
    p->next = q->next;  
    free(q);  // 释放掉待删除节点的内存空间
}

该函数同样根据输入的位置找到待删除位置和前一个节点,然后删除该节点。

单链表的示例

下面是一个完整的单链表的示例,包含了创建、遍历、插入和删除操作。

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

typedef struct node {
    int data;           
    struct node *next;  
} Node, *LinkList;

LinkList createList() {
    Node *head, *tail, *p;
    int data;
    head = tail = (Node*)malloc(sizeof(Node));
    tail->next = NULL;
    printf("请输入数据,输入-1结束:\n");
    scanf("%d", &data);
    while (data != -1) {
        p = (Node*)malloc(sizeof(Node));
        p->data = data;
        tail->next = p;
        tail = p;
        scanf("%d", &data);
    }
    tail->next = NULL;
    return head;
}

void traverseList(LinkList list) {
    Node* p = list->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

void insertNode(LinkList list, int data, int pos) {
    Node* p = list;  
    Node* q = NULL;  
    Node* new = NULL;  
    int i = 1;
    while (p != NULL && i < pos) {  
        p = p->next;
        i++;
    }
    if (p == NULL || i > pos) {  
        printf("位置不合法\n");
        return;
    }
    q = p->next;  
    new = (Node*)malloc(sizeof(Node));  
    new->data = data;  
    new->next = q;  
    p->next = new;  
}

void deleteNode(LinkList list, int pos) {
    Node* p = list;  
    Node* q = NULL;  
    int i = 1;
    while (p != NULL && i < pos) {  
        p = p->next;
        i++;
    }
    if (p == NULL || i > pos || p->next == NULL) {  
        printf("位置不合法\n");
        return;
    }
    q = p->next;  
    p->next = q->next;  
    free(q);  
}

int main() {
    LinkList list = createList();
    printf("原始链表:\n");
    traverseList(list);
    printf("插入节点前:\n");
    insertNode(list, 99, 3);
    traverseList(list);
    printf("删除节点后:\n");
    deleteNode(list, 2);
    traverseList(list);
    return 0;
}

运行结果:

请输入数据,输入-1结束:
1 2 3 4 5 -1
原始链表:
1 2 3 4 5 
插入节点前:
1 2 99 3 4 5 
删除节点后:
1 3 4 5 

双向链表

双向链表是相对于单向链表而言的另一种链表结构,每个节点中包含两个指针,分别指向前一个节点和后一个节点。双向链表的优点是在单向链表的基础上增加了向前访问的功能,但其缺点是节点中需要保存更多指针,占用的空间更大。

双向链表的创建、遍历、插入和删除和单向链表类似,只需要修改部分代码即可。

总结

链表是一种重要的数据结构,在算法和程序设计中被广泛使用。本文介绍了链表的基本概念,并通过单向链表为例讲解了链表的创建、遍历、插入和删除操作。读者可以通过修改代码实现双向链表和其他版本的链表。

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

(0)
上一篇 2023年6月27日
下一篇 2023年6月27日

相关文章

  • 华为mate30pro如何开启开发人员选项?华为mate30pro开发者选项开启教程

    华为Mate 30 Pro 如何开启开发人员选项? 华为Mate30 Pro是一款非常优秀的智能手机,它有着强大的硬件配置以及丰富的软件功能。如果你是一名开发者或者想要进行一些特殊的操作,那么你需要开启华为Mate 30 Pro的开发人员选项。 以下是华为Mate 30 Pro开启开发人员选项的步骤: 打开手机的“设置”应用程序 滚动到底部并点击“关于手机”…

    other 2023年6月26日
    00
  • zeromq rpc原型

    下面是 ZeroMQ RPC 原型的完整攻略,包括定义、使用方法和两个示例说明。 ZeroMQ RPC 原型的定义 ZeroMQ RPC 原型是一种基于 ZeroMQ 的远程过程调用(RPC)框架,它可以帮助开发人员快速构建分布式应用程序。ZeroMQ RPC 原型使用 ZeroMQ 的套接字进行通信,支持多种消息传输模式,如请求-响应、发布-订阅、推送-拉…

    other 2023年5月5日
    00
  • Android 滚动时间选择的示例代码

    Sure! Here is a detailed guide on implementing a time picker with scrolling functionality in Android, along with two example explanations: Step 1: Add Dependencies To begin, make s…

    other 2023年9月6日
    00
  • XMind思维导图怎么设置主题优先级?

    XMind思维导图设置主题优先级攻略 1. 确定主题优先级的重要性 在进行主题优先级设置之前,首先需要明确主题优先级对你的思维导图的重要性。不同的主题可能具有不同的重要性,因此根据你的需求和目标来决定主题优先级的设置。 2. 使用主题优先级符号 使用XMind思维导图软件提供的主题优先级符号来设置主题的优先级。主题优先级符号可以使用不同的图标或颜色来表示主题…

    other 2023年6月28日
    00
  • python利用后缀表达式实现计算器功能

    Python利用后缀表达式实现计算器功能攻略 后缀表达式(也称为逆波兰表达式)是一种将运算符放在操作数之后的表示方法。利用后缀表达式可以实现计算器功能,以下是详细的攻略。 步骤一:将中缀表达式转换为后缀表达式 创建一个空栈和一个空列表,用于存储运算符和后缀表达式。 从左到右遍历中缀表达式的每个字符。 如果遇到操作数(数字),将其添加到后缀表达式列表中。 如果…

    other 2023年8月5日
    00
  • 深入NAS协议系列: 召唤SMB2 OpLock/Lease

    深入NAS协议系列: 召唤SMB2 OpLock/Lease SMB2是一种高性能、可靠的网络文件共享协议,被广泛运用于Windows-based操作系统中。而OpLock和Lease是SMB2协议在文件访问方面的两个关键特性。本文将深入解读这两个概念,帮助读者深入了解SMB2协议在文件共享方面的工作原理。 SMB2协议简介 SMB2协议是一种客户端/服务器…

    其他 2023年3月28日
    00
  • 利用PHP和百度ai实现文本以及图片的审核

    利用PHP和百度AI实现文本以及图片的审核 在很多网站应用中,我们可能需要对用户上传的文本和图片进行审核,以保证其内容不含有不良信息,不违反法律法规,同时也保护其他用户的利益。本文将介绍如何利用PHP和百度AI实现文本和图片审核的功能。 百度AI平台介绍 百度AI(Baidu AI)平台是由百度推出的人工智能开发平台,涵盖了图像识别、语音识别、自然语言处理等…

    其他 2023年3月28日
    00
  • idea中如何使用git进行版本回退详解

    使用Git进行版本回退的详细攻略 Git是一个强大的版本控制系统,可以帮助我们管理代码的版本。在Git中,我们可以使用git reset命令来进行版本回退。下面是使用Git进行版本回退的详细攻略。 步骤一:查看提交历史 首先,我们需要查看当前仓库的提交历史,以确定要回退到哪个版本。可以使用以下命令查看提交历史: git log 这将显示所有的提交记录,包括提…

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