数据结构实验4:链表的基本操作

目录

一、实验目的

二、实验原理

1. 节点

2. 指针

3.链表的类型

3.1 单向链表

3.2 双向链表

 3.3 单向循环链表

 3.4 双向循环链表

 4. 单链表的插入

4.1 头插法

4.2 尾插法

4.3 在指定位置插入元素

5. 单链表的删除

5.1 删除指定数值的节点

5.2 删除指定位置的节点

6. 单链表的查找

6.1 按照值域查找

6.2 按照位置查找

7. 链表的遍历

三、实验内容

问题描述

代码

截图


一、实验目的

1、 熟练掌握链表结构体的实现。

2、 熟练掌握链表的存储结构上实现基本操 作:查找、插入和删除算法

二、实验原理

链表(Linked List)是一种基本的数据结构,它用于存储和组织数据元素。链表中的元素被称为节点(Node),每个节点包含两部分:数据域和指针域。

1. 节点

每个节点包含两个部分:数据域和指针域。

  • 数据域(Data Field): 存储节点的数据元素。这可以是任何数据类型,例如整数、字符、对象等。

  • 指针域(Pointer Field): 存储指向下一个节点的引用(地址)。对于双向链表,可能还有指向前一个节点的引用。

2. 指针

链表的节点通过指针相互连接。指针存储了节点的地址,使得可以按顺序遍历链表。

3.链表的类型

3.1 单向链表

每个节点只有一个指针,指向下一个节点。

最后一个节点指向空节点(NULL)。

struct ListNode {
    int data;// 数据域,存储节点的数据 
    struct  ListNode* next;// 指针域,指向下一个节点的地址
};

对于头节点的定义

struct LinkedList {
    struct ListNode* head;
};

3.2 双向链表

每个节点有两个指针,一个指向前一个节点,另一个指向下一个节点。 

第一个节点的prev指向NULL,最后一个节点的next指向NULL

struct ListNode {  
    int data;// 数据域,存储节点的数据
    struct ListNode* next;// 指针域,指向下一个节点的地址
    struct ListNode* prev;// 指针域,指向前一个节点的地址
};

对于头节点的定义

struct DoublyLinkedList {
    struct ListNode* head;
};

 3.3 单向循环链表

尾节点的指针指向头节点,形成一个闭环。

struct ListNode {
    int data;// 数据域,存储节点的数据 
    struct ListNode* next;// 指针域,指向下一个节点的地址
};

对于头节点的定义

struct CircularLinkedList {
    struct ListNode* head;
};

 3.4 双向循环链表

带头结点的循环双向链表在链表尾部连接到头结点,同时每个节点都有一个指向前一个节点的指针。

struct ListNode {
    int data;// 数据域,存储节点的数据
    struct ListNode* next;// 指针域,指向下一个节点的地址
    struct ListNode* prev;// 指针域,指向前一个节点的地址
};

对于头节点的定义

struct CircularDoublyLinkedList {
    struct ListNode* head;
};

 4. 单链表的插入

4.1 头插法

头插法是一种在单链表中插入节点的方法,它将新节点插入到链表的头部,成为新的头结点。

  1. 创建一个新的节点。
  2. 将新节点的 next 指针指向当前链表的头结点。
  3. 更新链表的头结点,使其指向新节点。

struct ListNode* insertAtBeginning(struct ListNode* head, int elem) {
    //创建新节点
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    if (newNode == NULL) {
        cout << "内存分配失败" << endl;
        return;
    }
    newNode->data = elem;//赋值
    newNode->next = head;//newNode的指针指向head
    head = newNode;//newNode成为新的头节点
    return head;
}

 示例

依次插入4 3 2 1

int main() {
    //初始化单链表
    struct ListNode* head = NULL;
    for (int i = 4; i > 0; i--) {
        head = insertAtBeginning(head, i);
    }
    for (int i = 0; i < 4; i++) {
        cout << head->data << " ";
        head = head->next;
    }
    return 0;
}

结果为

正好与输入顺序相反,这就是头插法的特色

4.2 尾插法

 尾插法是一种在单链表中插入节点的方法,它将新节点插入到链表的尾部。相对于头插法,尾插法需要遍历整个链表找到尾节点,然后在尾节点之后插入新节点。

  1. 创建一个新的节点。
  2. 若链表为空,将新节点设置为头结点。
  3. 若链表不为空,遍历链表找到尾节点。
  4. 将尾节点的 next 指针指向新节点。
struct ListNode* insertAtEnd(struct ListNode* head, int elem) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    if (newNode == NULL) {
        cout << "内存分配失败" << endl;
        return head;
    }
    //设置新节点的数据和指针
    newNode->data = elem;
    newNode->next = NULL;

    //查找尾节点
    if (head == NULL) {//如果该链表为空链表,头节点指向该新节点
        head = newNode;
    }
    else {
        struct ListNode* tail = head;//定义尾节点
        while (tail->next != NULL) {//找到尾节点
            tail = tail->next;
        }
        tail->next = newNode;//尾节点的指针指向新节点
    }
    return head;
}

示例

依次插入4 3 2 1

int main() {
    //初始化单链表
    struct ListNode* head = NULL;
    for (int i = 4; i > 0; i--) {
        head = insertAtEnd(head, i);
    }
    for (int i = 0; i < 4; i++) {
        cout << head->data << " ";
        head = head->next;
    }
    return 0;
}

结果为

结果与输入顺序相同,看似更好,但是时间复杂度较高(while循环)。

4.3 在指定位置插入元素

struct ListNode* insertAtEnd_index(struct ListNode* head, int elem,int index) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    if (newNode == NULL) {
        cout << "内存分配失败" << endl;
        return head;
    }
    //设置新节点的数据和指针
    newNode->data = elem;
    newNode->next = NULL;
    struct ListNode* current = head;
    struct ListNode* prev = NULL;
    //index是否合法
    if (index == 1) {//插入的节点为头节点
        head = newNode;
        newNode->next = current->next;
        return;
    }
    while (current != NULL && index!=1) {
        prev = current;
        current = current->next;
        index--;
    }
    if (current == NULL) {//遍历到末尾
        if (index != 0) {
            cout << "索引越界" << endl;
        }
        else {//prev后插入
            prev->next = newNode;
        }
    }
    else {//中间插入
        prev->next = newNode;
        newNode->next = current;
    }
    return head;
}

5. 单链表的删除

5.1 删除指定数值的节点

删除链表中所有数值域与指定数值相同的节点。

struct ListNode* deleteNodeWithValue(struct ListNode* head, int target) {
    struct ListNode* current = head;
    struct ListNode* prev = NULL;//prev只有刚开始等于NULL的时候才发挥作用,其余时候没用
    // 遍历链表删除所有匹配的节点
    while (current != NULL) {
        if (current->data == target) {//如果符合条件
            if (prev == NULL) {// 如果目标节点是头结点
                head = current->next;
                free(current);
                current = head;
            }
            else {
                prev->next = current->next;
                free(current);
                current = prev->next;
            }
        }
        else {//不符合条件,直接右移
            prev = current;
            current = current->next;
        }
    }
    return head;
}

示例,尾插法插入1 2  1 3

再删除1

int main() {
    //初始化单链表
    struct ListNode* head = NULL;
    head = insertAtEnd(head, 1);
    head = insertAtEnd(head, 2);
    head = insertAtEnd(head, 1);
    head = insertAtEnd(head, 3);
    head = deleteNodeWithValue(head, 1);
    for (int i = 0; i < 2; i++) {
        cout << head->data << " ";
        head = head->next;
    }
    return 0;
}

结果为

5.2 删除指定位置的节点

若指定位置无节点,会特殊处理

struct ListNode* deleteNodeAtPosition(struct ListNode* head, int index) {
    if (index < 1) {
        cout << "输入无效" << endl;
        return head;
    }
    struct ListNode* current = head;
    struct ListNode* prev = NULL;
    while (index != 1 && current!=NULL) {
        index--;
        prev = current;
        current = current->next;
    }
    if (current == NULL) {//越界
        cout << "访问越界" << endl;
        return head;
    }
    if (index == 1) {
        if (current == head) {//删除的节点是头节点
            head = current->next;
            free(current);
        }
        else {
            current = current->next;
            prev->next = current;
        }
    }
    return head;
}

示例,尾插法插入1 2  1 3

再删除第一个节点

int main() {
    //初始化单链表
    struct ListNode* head = NULL;
    head = insertAtEnd(head, 1);
    head = insertAtEnd(head, 2);
    head = insertAtEnd(head, 1);
    head = insertAtEnd(head, 3);
    head = deleteNodeAtPosition(head, 1);
    for (int i = 0; i < 3; i++) {
        cout << head->data << " ";
        head = head->next;
    }
    return 0;
}

结果为

2 1 3

6. 单链表的查找

在链表中查找元素的操作通常包括遍历链表,逐一比较节点的值,直到找到匹配的元素或者到达链表的末尾。

6.1 按照值域查找

void search_target(struct ListNode* head,int target) {
    struct ListNode* current = head;
    int count = 1;
    while (current != NULL) {
        if (current->data == target) {
            cout << "在第"<<count<<"个位置" << endl;
            return;
        }
        count++;
        current=current->next;
    }
    cout << "不存在" << endl;
}

依次插入1 2 1 3

查找1 4

int main() {
    //初始化单链表
    struct ListNode* head = NULL;
    head = insertAtEnd(head, 1);
    head = insertAtEnd(head, 2);
    head = insertAtEnd(head, 1);
    head = insertAtEnd(head, 3);
    search_target(head, 1);
    search_target(head, 4);
    return 0;
}

结果为

1在第一个位置

4不存在

6.2 按照位置查找

void search_index(struct ListNode* head, int index) {
    if (index < 1) {
        cout << "输入无效" << endl;
        return;
    }
    struct ListNode* current = head;
    while (index != 1 && current != NULL) {
        index--;
        current = current->next;
    }
    if (current == NULL) {//越界
        cout << "访问越界" << endl;
        return;
    }
    cout << current->data;
}

依次插入1 2 1 3

查找1 4

int main(){
    struct ListNode* head = NULL;
    head = insertAtEnd(head, 1);
    head = insertAtEnd(head, 2);
    head = insertAtEnd(head, 1);
    head = insertAtEnd(head, 3);
    search_index(head, 1);
    search_index(head, 4);
    return 0;
}

结果为

1

3

7. 链表的遍历

从头节点遍历

void traversal(struct ListNode* head) {
    struct ListNode* current = head;
    while (current != NULL) {
        cout << current->data<<" ";
        current = current->next;
    }
    cout << endl;
}

三、实验内容

问题描述

1、 初始化单链表 h;

2、 依次采用头插法插入元素-1,21,13,24,8;

3、 输出单链表 h;

4、 输出单链表 h 长度;

5、 判断单链表 h 是否为空;

6、 输出单链表 h 的第 3 个元素;

7、 输出元素 24 的位置;

8、 在 h 的第 4 个元素前插入元素 0;

9、 输出单链表 h;

10、 删除 h 的第 5 个元素;

11、 输出单链表 h

代码

#include<iostream>
using namespace std;

struct ListNode {
    int data;// 数据域,存储节点的数据 
    struct ListNode* next;// 指针域,指向下一个节点的地址
};

struct LinkedList {
    struct ListNode* head;
};

struct ListNode* insertAtBeginning(struct ListNode* head, int elem) {
    //创建新节点
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    if (newNode == NULL) {
        cout << "内存分配失败" << endl;
        return head;
    }
    newNode->data = elem;//赋值
    newNode->next = head;//newNode的指针指向head

    head = newNode;//newNode成为新的头节点
    return head;
}

struct ListNode* insertAtEnd(struct ListNode* head, int elem) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    if (newNode == NULL) {
        cout << "内存分配失败" << endl;
        return head;
    }
    //设置新节点的数据和指针
    newNode->data = elem;
    newNode->next = NULL;

    //查找尾节点
    if (head == NULL) {//如果该链表为空链表,头节点指向该新节点
        head = newNode;
    }
    else {
        struct ListNode* tail = head;//定义尾节点
        while (tail->next != NULL) {//找到尾节点
            tail = tail->next;
        }
        tail->next = newNode;//尾节点的指针指向新节点
    }
    return head;
}
struct ListNode* insertAtEnd_index(struct ListNode* head, int elem,int index) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    if (newNode == NULL) {
        cout << "内存分配失败" << endl;
        return head;
    }
    //设置新节点的数据和指针
    newNode->data = elem;
    newNode->next = NULL;
    struct ListNode* current = head;
    struct ListNode* prev = NULL;
    //index是否合法
    if (index == 1) {//插入的节点为头节点
        head = newNode;
        newNode->next = current->next;
        return head;
    }
    while (current != NULL && index!=1) {
        prev = current;
        current = current->next;
        index--;
    }
    if (current == NULL) {//遍历到末尾
        if (index != 0) {
            cout << "索引越界" << endl;
        }
        else {//prev后插入
            prev->next = newNode;
        }
    }
    else {//中间插入
        prev->next = newNode;
        newNode->next = current;
    }
    return head;
}

struct ListNode* deleteNodeWithValue(struct ListNode* head, int target) {
    struct ListNode* current = head;
    struct ListNode* prev = NULL;//prev只有刚开始等于NULL的时候才发挥作用,其余时候没用,prev的next指向current
    // 遍历链表删除所有匹配的节点
    while (current != NULL) {
        if (current->data == target) {//如果符合条件
            if (prev == NULL) {// 如果目标节点是头结点
                head = current->next;
                free(current);
                current = head;
            }
            else {
                prev->next = current->next;
                free(current);
                current = prev->next;
            }
        }
        else {//不符合条件,直接右移
            prev = current;
            current = current->next;
        }
    }
    return head;
}

struct ListNode* deleteNodeAtPosition(struct ListNode* head, int index) {
    if (index < 1) {
        cout << "输入无效" << endl;
        return head;
    }
    struct ListNode* current = head;
    struct ListNode* prev = NULL;
    while (index != 1 && current!=NULL) {
        index--;
        prev = current;
        current = current->next;
    }
    if (current == NULL) {//越界
        cout << "访问越界" << endl;
        return head;
    }
    if (index == 1) {
        if (current == head) {//删除的节点是头节点
            head = current->next;
            free(current);
        }
        else {
            current = current->next;
            prev->next = current;
        }
    }
    return head;
}

void search_target(struct ListNode* head,int target) {
    struct ListNode* current = head;
    int count = 1;
    while (current != NULL) {
        if (current->data == target) {
            cout << "在第"<<count<<"个位置" << endl;
            return;
        }
        count++;
        current=current->next;
    }
    cout << "不存在" << endl;
}

void search_index(struct ListNode* head, int index) {
    if (index < 1) {
        cout << "输入无效" << endl;
        return;
    }
    struct ListNode* current = head;
    while (index != 1 && current != NULL) {
        index--;
        current = current->next;
    }
    if (current == NULL) {//越界
        cout << "访问越界" << endl;
        return;
    }
    cout << current->data<<endl;
}

void traversal(struct ListNode* head) {
    struct ListNode* current = head;
    while (current != NULL) {
        cout << current->data<<" ";
        current = current->next;
    }
    cout << endl;
}


int main() {
    //初始化单链表
    struct ListNode* head = NULL;
    head = insertAtEnd(head, -1);
    head = insertAtEnd(head, 21);
    head = insertAtEnd(head, 13);
    head = insertAtEnd(head, 24);
    head = insertAtEnd(head, 8);
    cout << "单链表h为:";
    traversal(head);
    if (head == NULL) {
        cout << "单链表为空"<<endl;
    }
    else {
        cout << "不为空" << endl;
    }
    cout << "单链表的第三个元素为:";
    search_index(head, 3);
    cout << "24";
    search_target(head, 24);
    insertAtEnd_index(head, 0, 4);
    cout << "单链表h为:";
    traversal(head);
    deleteNodeAtPosition(head, 5);
    cout << "单链表h为:";
    traversal(head);
    return 0;
}

截图

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/308401.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

软件测试|Python Selenium 库安装使用指南

简介 Selenium 是一个用于自动化浏览器操作的强大工具&#xff0c;它可以模拟用户在浏览器中的行为&#xff0c;例如点击、填写表单、导航等。在本指南中&#xff0c;我们将详细介绍如何安装和使用 Python 的 Selenium 库。 安装 Selenium 库 使用以下命令可以通过 pip 安装…

Matlab 分段函数(piecewise)

语法 pw piecewise(cond1,val1,cond2,val2,...) pw piecewise(cond1,val1,cond2,val2,...,otherwiseVal)描述 pw piecewise(cond1,val1,cond2,val2,...) 返回分段表达式或函数pw&#xff0c;当cond1为True时&#xff0c;其值为val1&#xff0c;当cond2为True时&#xff0…

优化CentOS 7.6的HTTP隧道代理网络性能

在CentOS 7.6上&#xff0c;通过HTTP隧道代理优化网络性能是一项复杂且细致的任务。首先&#xff0c;我们要了解HTTP隧道代理的工作原理&#xff1a;通过建立一个安全的隧道&#xff0c;HTTP隧道代理允许用户绕过某些网络限制&#xff0c;提高数据传输的速度和安全性。然而&…

PyCharm 设置新建Python文件时自动在文章开头添加固定注释的方法

在实际项目开发时&#xff0c;为了让编写的每个代码文件易读、易于维护或方便协同开发时&#xff0c;我们都会在每一个代码文件的开头做一些注释&#xff0c;如作者&#xff0c;文档编写时间&#xff0c;文档的功能说明等。 利用PyCharm 编辑器&#xff0c;我们只需设置相关设…

MS-DETR论文解读

文章目录 前言一、摘要二、引言三、贡献四、MS-DETR模型方法1、模型整体结构解读2、模型改善结构解读3、一对多监督原理 五、实验结果1、实验比较2、论文链接 总结 前言 今天&#xff0c;偶然看到MS-DETR论文&#xff0c;以为又有什么高逼格论文诞生了。于是&#xff0c;我想查…

12.1SPI驱动框架

SPI硬件基础 总线拓扑结构 引脚含义 DO(MOSI)&#xff1a;Master Output, Slave Input&#xff0c; SPI主控用来发出数据&#xff0c;SPI从设备用来接收数据 DI(MISO) &#xff1a;Master Input, Slave Output&#xff0c; SPI主控用来发出数据&#xff0c;SPI从设备用来接收…

IPv6路由协议---IPv6动态路由(OSPFv3-4)

OSPFv3的链路状态通告LSA类型 链路状态通告是OSPFv3进行路由计算的关键依据,链路状态通告包含链路状态类型、链路状态ID、通告路由器三元组唯一地标识了一个LSA。 OSPFv3的LSA头仍然保持20字节,但是内容变化了。在LSA头中,OSPFv2的LS age、Advertising Router、LS Sequence…

Java中输入和输出处理(三)二进制篇

叮咚&#xff01;加油&#xff01;马上学完 读写二进制文件Data DataInputStream类 FilFeInputStream的子类 与FileInputStream类结合使用读取二进制文件 DataOutputStream类 FileOutputStream的子类 与FileOutputStream类结合使用写二进制文件 读写二进制代码 package 面…

DAPP和APP的区别在哪?

随着科技的飞速发展&#xff0c;我们每天都在与各种应用程序打交道。然而&#xff0c;你是否真正了解DAPP和APP之间的区别呢&#xff1f;本文将为你揭示这两者的核心差异&#xff0c;让你在自媒体平台上脱颖而出。 一、定义与起源 APP&#xff0c;即应用程序&#xff0c;通常指…

使用KubeSphere轻松部署Bookinfo应用

Bookinfo 应用 这个示例部署了一个用于演示多种 Istio 特性的应用&#xff0c;该应用由四个单独的微服务构成。 如安装了 Istio&#xff0c;说明已安装 Bookinfo。 这个应用模仿在线书店的一个分类&#xff0c;显示一本书的信息。 页面上会显示一本书的描述&#xff0c;书籍…

C/C++ 位段

目录 什么是位段&#xff1f; 位段的内存分配 位段的跨平台问题 什么是位段&#xff1f; 位段的声明与结构是类似的&#xff0c;但是有两个不同&#xff1a; 位段的成员必须是 int、unsigned int 或signed int 等整型家族。位段的成员名后边有一个冒号和一个数字 这是一个…

深度学习笔记(二)——Tensorflow环境的安装

本篇文章只做基本的流程概述&#xff0c;不阐述具体每个软件的详细安装流程&#xff0c;具体的流程网上教程已经非常丰富。主要是给出完整的安装流程&#xff0c;以供参考 环境很重要 一个好的算法环境往往能够帮助开发者事半功倍&#xff0c;入门学习的时候往往搭建好环境就已…

【ELISA检测】酶联免疫吸附实验概述-卡梅德生物

酶联免疫吸附实验&#xff08;Enzyme linked immunosorbent assay&#xff0c;ELISA&#xff09;是将抗原或抗体结合在固相载体表面&#xff0c;利用抗原抗体的特异性结合以及抗体或者抗原上标记的酶催化特定底物发生显色反应&#xff0c;实现目标物检测的免疫分析方法&#xf…

24/1/10 qt work

1. 完善对话框&#xff0c;点击登录对话框&#xff0c;如果账号和密码匹配&#xff0c;则弹出信息对话框&#xff0c;给出提示”登录成功“&#xff0c;提供一个Ok按钮&#xff0c;用户点击Ok后&#xff0c;关闭登录界面&#xff0c;跳转到其他界面 如果账号和密码不匹配&…

11 个 Python全栈开发工具集

前言 以下是专注于全栈开发不同方面的 Python 库;有些专注于 Web 应用程序开发&#xff0c;有些专注于后端&#xff0c;而另一些则两者兼而有之。 1. Taipy Taipy 是一个开源的 Python 库&#xff0c;用于构建生产就绪的应用程序前端和后端。 它旨在加快应用程序开发&#xf…

Appium + ios环境搭建过程Mac

前提&#xff1a; 已经搭建好NodeJavaPythonAppium...环境 见下面的文章&#xff1a; ok的话按照下面的步骤搭建IOs的自动化 1. 安装Xcode 官方下载 (Downloads and Resources - Xcode - Apple Developer 1)AppStore 下载安装最新版本 2. 依赖工具 工具名描述libimobile…

Springboot的配置文件详解:从入门到精通,解读配置文件的奇妙世界

目录 1、前言 2、介绍 2.1 Springboot配置文件的作用 2.2 Springboot支持的配置文件类型 2.3 Springboot配置文件的加载顺序 3、YAML配置文件 3.1 YAML基本语法介绍 3.2 YAML中的基本数据类型 3.3 YAML中的复合数据类型 3.4 YAML中的配置属性 3.5 YAML中的多环境配置…

从0开始学Git指令(2)

从0开始学Git指令 因为网上的git文章优劣难评&#xff0c;大部分没有实操展示&#xff0c;所以打算自己从头整理一份完整的git实战教程&#xff0c;希望对大家能够起到帮助&#xff01; 工作区&#xff08;Working Directory&#xff09; 就是你在电脑里能看到的目录&#x…

还不会python 实现常用的数据编码和对称加密?看这篇文章就够啦~

相信很多使用 python 的小伙伴在工作中都遇到过&#xff0c;对数据进行相关编码或加密的需求&#xff0c;今天这篇文章主要给大家介绍对于一些常用的数据编码和数据加密的方式&#xff0c;如何使用 python 去实现。话不多说&#xff0c;接下来直接进入主题&#xff1a; 前言 1…

Windows VSCode 使用Python

一、vscode中安装python 二、下载python.exe&#xff08;即vscode中需要的python解释器&#xff09; 下载地址&#xff1a;https://www.python.org/downloads/ 三、安装第三方代码规范工具 参考网址&#xff1a;https://www.python.org/downloads/ 工具介绍 flake8 &#xf…