1. Python技术站首页
  2. other

C语言实现数据结构和双向链表操作

• other

下面是详细讲解 "C语言实现数据结构和双向链表操作" 的完整攻略。

什么是数据结构？

数据结构是计算机中存储、组织和管理数据的方式。数据结构可以分为线性结构和非线性结构两种。其中，线性结构包括数组、链表、栈、队列等，非线性结构包括树、图等。

什么是链表？

链表是一种动态的数据结构，它由许多个结点组成。每个结点包含两个部分：数据域和指针域。数据域存储数据，指针域则存储指向下一个结点（单向链表）或上一个结点（双向链表）的指针。其中，第一个结点称为头结点，最后一个结点称为尾结点。

双向链表的实现

以下是双向链表的结构体实现：

typedef struct Node{
    int data;
    struct Node *prev;  // 指向前一个结点的指针
    struct Node *next;  // 指向下一个结点的指针
}Node, *LinkList;

其中，prev指向前驱结点，next指向后继结点。

以下是创建双向链表的函数：

/**
 * 创建双向链表
 */
LinkList create(){
    Node *head = (Node*) malloc(sizeof(Node));  // 创建头结点
    head->prev = NULL;
    head->next = NULL;

    Node *tail = head;  // 记录尾结点位置

    int n;
    printf("请输入双向链表的长度:\n");
    scanf("%d",&n);  // 输入结点个数

    for (int i = 0; i < n; i++){
        Node *node = (Node*) malloc(sizeof(Node));  // 创建一个新结点
        printf("请输入第%d个结点的数据:\n",i+1);
        scanf("%d",&node->data);  // 输入结点数据

        node->prev = tail;  // 设置前驱指针
        node->next = NULL;  // 设置后继指针
        tail->next = node;  // 将新结点插到尾部
        tail = node;  // 更新尾结点位置
    }
    return head;
}

该函数会先创建一个头结点，然后根据输入的结点个数，依次创建新的结点。在创建新结点时，我们需要将该结点的前驱指针指向链表的尾结点，将尾结点的后继指针指向该结点，最后更新尾结点位置。

以下是双向链表的遍历函数：

/**
 * 遍历双向链表
 */
void traverse(LinkList L){
    Node *p = L->next;  // 从头结点的后继结点开始遍历
    while (p != NULL){
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

遍历时，我们从头结点的后继结点开始遍历，直到遍历到尾结点为止。

以下是双向链表的插入函数：

/**
 * 双向链表中插入新结点
 */
void insert(LinkList L,int pos,int data){
    Node *node = (Node*) malloc(sizeof(Node));  // 创建新结点
    node->data = data;

    Node *p = L->next;
    int i = 1;
    while (p != NULL && i < pos){
        p = p->next;
        i++;
    }
    if (p == NULL){
        printf("插入的位置非法！\n");
        return;
    }
    node->prev = p->prev;  // 插入新结点
    node->next = p;
    p->prev->next = node;
    p->prev = node;
}

插入时，我们需要定位到插入位置上一个结点的位置，然后将插入结点的前驱指针指向该结点的前驱结点，将插入结点的后继指针指向该结点，将该结点的前驱结点的后继指针指向插入结点，将该结点的前驱指针指向插入结点。

以下是双向链表的删除函数：

/**
 * 双向链表中删除指定结点
 */
void remove_node(LinkList L,int pos){
    Node *p = L->next;
    int i = 1;
    while (p != NULL && i < pos){
        p = p->next;
        i++;
    }
    if (p == NULL){
        printf("删除的位置非法！\n");
        return;
    }
    p->prev->next = p->next;
    if (p->next != NULL){
        p->next->prev = p->prev;
    }
    free(p);
}

删除时，我们同样需要定位到删除结点的位置，然后将删除结点的前驱结点的后继指针指向删除结点的后继结点，将删除结点的后继结点的前驱指针指向删除结点的前驱结点，最后释放删除结点占用的内存空间。

示例1

假设我们要创建一个包含10个结点的双向链表，并对该双向链表进行遍历、插入和删除操作，具体代码如下：

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

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

/**
 * 创建双向链表
 */
LinkList create(){
    Node *head = (Node*) malloc(sizeof(Node));  // 创建头结点
    head->prev = NULL;
    head->next = NULL;

    Node *tail = head;  // 记录尾结点位置

    int n;
    printf("请输入双向链表的长度:\n");
    scanf("%d",&n);

    for (int i = 0; i < n; i++){
        Node *node = (Node*) malloc(sizeof(Node));  // 创建一个新结点
        printf("请输入第%d个结点的数据:\n",i+1);
        scanf("%d",&node->data);

        node->prev = tail;  // 设置前驱指针
        node->next = NULL;  // 设置后继指针
        tail->next = node;  // 将新结点插到尾部
        tail = node;  // 更新尾结点位置
    }
    return head;
}

/**
 * 遍历双向链表
 */
void traverse(LinkList L){
    Node *p = L->next;
    while (p != NULL){
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

/**
 * 双向链表中插入新结点
 */
void insert(LinkList L,int pos,int data){
    Node *node = (Node*) malloc(sizeof(Node));  // 创建新结点
    node->data = data;

    Node *p = L->next;
    int i = 1;
    while (p != NULL && i < pos){
        p = p->next;
        i++;
    }
    if (p == NULL){
        printf("插入的位置非法！\n");
        return;
    }
    node->prev = p->prev;  // 插入新结点
    node->next = p;
    p->prev->next = node;
    p->prev = node;
}

/**
 * 双向链表中删除指定结点
 */
void remove_node(LinkList L,int pos){
    Node *p = L->next;
    int i = 1;
    while (p != NULL && i < pos){
        p = p->next;
        i++;
    }
    if (p == NULL){
        printf("删除的位置非法！\n");
        return;
    }
    p->prev->next = p->next;
    if (p->next != NULL){
        p->next->prev = p->prev;
    }
    free(p);
}

int main(){
    LinkList L = create();  // 创建双向链表
    traverse(L);  // 遍历双向链表
    insert(L, 3, 99);  // 向双向链表中插入新结点
    traverse(L);  // 遍历插入新结点后的双向链表
    remove_node(L, 5);  // 从双向链表中删除指定结点
    traverse(L);  // 遍历删除指定结点后的双向链表
    return 0;
}

以上代码会首先让用户输入该双向链表的长度，然后依次输入每个结点的数据。创建完成后，打印该双向链表的所有结点。接着，向该链表的第3个位置插入一个新结点（data=99），再打印插入结点后的所有结点。最后，从该链表的第5个位置删除一个结点，并打印删除结点后的所有结点。

示例2

假设我们已经有一个双向链表，其中包含了若干结点，我们想要从该链表中查找某个特定数据的结点并打印出该结点的位置，如果没有找到则打印未找到的提示信息。这个问题可以通过以下代码实现：

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

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

/**
 * 遍历双向链表
 */
void traverse(LinkList L){
    Node *p = L->next;
    while (p != NULL){
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

/**
 * 查找双向链表中特定数据的结点
 */
void find(LinkList L,int data){
    Node *p = L->next;
    int pos = 1;
    while (p != NULL && p->data != data){
        p = p->next;
        pos++;
    }
    if (p == NULL){
        printf("未找到数据为%d的结点！\n",data);
    }
    else{
        printf("数据为%d的结点在链表中的位置是%d。\n",data,pos);
    }
}

int main(){
    LinkList L = (LinkList) malloc(sizeof(Node));  // 创建头结点
    L->prev = NULL;
    L->next = NULL;

    Node *tail = L;  // 记录尾结点位置

    for (int i = 1; i <= 5; i++){
        Node *node = (Node*) malloc(sizeof(Node));  // 创建一个新结点
        node->data = i;

        node->prev = tail;  // 设置前驱指针
        node->next = NULL;  // 设置后继指针
        tail->next = node;  // 将新结点插到尾部
        tail = node;  // 更新尾结点位置
    }
    traverse(L);  // 遍历双向链表
    find(L, 3);  // 查找数据为3的结点
    find(L, 7);  // 查找数据为7的结点
    return 0;
}

以上代码会首先创建一个双向链表，并打印该链表中的所有结点。然后，查找该链表中数据为3和7的结点（其中只有数据为3的结点能被找到）。如果找到了，则打印结点的位置；如果没找到，则打印未找到的提示信息。

总而言之，在使用C语言来实现数据结构和双向链表操作的过程中，我们需要清楚每个方法的实现原理，同时遵守良好的编程规范，例如使用函数、结构体等方式将代码模块化，并进行模块间的相互调用。

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：C语言实现数据结构和双向链表操作 - Python技术站

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

相关文章

  • groovy脚本编写教程

    Groovy脚本编写教程 Groovy是一种基于Java平台的动态编程语言。它可以作为Java的补充语言，不但具有Java的强大功能，还提供了很多Java没有的特性，比如闭包、动态类型、混合编程等。其代码易于阅读、编写和维护，尤其适合需要灵活性和可扩展性的项目。 本教程将介绍Groovy脚本的编写和使用，包括以下几个方面： 安装Groovy 在开始使用Gro…

    其他 2023年3月28日
    00

  • 入驻淘宝开放平台及获取SDK的基本教程

    下面是“入驻淘宝开放平台及获取SDK的基本教程”的完整攻略： 一、入驻淘宝开放平台 1.申请开放平台账号 首先，在浏览器中打开淘宝开放平台官网，进入“开放平台入口”页面。点击“免费注册”按钮，填写相关信息，提交申请。 注：需要使用和淘宝账号不同的邮箱进行注册。 2.创建应用 注册成功后，登录账户，进入“管理中心”页面，点击“创建应用”按钮，根据提示填写应用信…

    other 2023年6月26日
    00

  • TabLayout+ViewPager实现切页的示例代码

    TabLayout+ViewPager实现切页的示例代码攻略 1. 添加依赖库 首先，我们需要在项目的build.gradle文件中添加TabLayout和ViewPager的依赖库。在dependencies块中添加以下代码： implementation ‘com.google.android.material:material:1.4.0’ 2. 创建…

    other 2023年8月25日
    00

  • formdata后台如何接收

    FormData后台如何接收 在前端开发中，我们经常使用FormData对象来提交表单数据。那么在后台，我们应该如何接收这些数据呢？ 什么是FormData 在常规情况下，我们提交表单数据通常会使用URL-encoded格式，即把所有数据都按照一定规则编码后拼接成一个字符串，然后作为QueryString附加到请求URL中。而使用FormData对象则可以更…

    其他 2023年3月28日
    00

  • shx文件怎么打开 .shx格式打开方式解答

    打开和解析 SHX 文件的攻略 SHX 文件是一种用于存储字体和形状数据的文件格式，通常用于CAD软件和GIS应用程序中。下面是打开和解析 SHX 文件的详细攻略。 步骤1：选择合适的软件 要打开 SHX 文件，您需要选择适用于您的操作系统的合适软件。以下是一些常用的软件选项： AutoCAD：AutoCAD是一款广泛使用的CAD软件，可以打开和编辑 SHX…

    other 2023年8月6日
    00

  • vue-cli3+ts+webpack实现多入口多出口功能

    “vue-cli3+ts+webpack实现多入口多出口功能”需要做如下几个步骤： 初始化项目 使用vue-cli3初始化一个vue项目，这个项目作为主项目，用于引入其他模块。 vue create my-project 添加模块 在主项目中，通过npm或yarn安装其他需要接入主项目的模块，例如我们需要接入一个blog模块，通过以下命令安装： npm in…

    other 2023年6月27日
    00

  • golang实现命令行程序的使用帮助功能

    下面是一份 “golang实现命令行程序的使用帮助功能”的完整攻略： 1. 引用第三方库 在golang中，我们可以使用 flag 包来方便的解析命令行参数，并生成帮助信息。 因此，第一步需要引用 flag： import ( "flag" "fmt" "os" ) 2. 定义命令行参数 在代码中定…

    other 2023年6月26日
    00

  • Windows 10Build 10240已开发完成 最后的正式发布版

    Windows 10 Build 10240 完成开发攻略 Windows 10 Build 10240 是 Windows 10 的最终正式发布版。本攻略将详细介绍如何完成该版本的开发过程，并提供两个示例说明。 步骤一：准备开发环境 在开始开发之前，确保你已经准备好以下开发环境： 一台运行 Windows 操作系统的计算机 安装了最新的 Windows 1…

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