AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

数据结构 链表（上）

2022-12-04 139
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
本文涉及的产品
应用型负载均衡 ALB，每月750个小时 15LCU
网络型负载均衡 NLB，每月750个小时 15LCU
传统型负载均衡 CLB，每月750个小时 15LCU
简介： 数据结构 链表

1. DS单链表–类实现


题目描述


用C++语言和类实现单链表，含头结点


属性包括：data数据域、next指针域


操作包括：插入、删除、查找


注意：单链表不是数组，所以位置从1开始对应首结点，头结点不放数据


1f3cb51fac164c39a79ba78b16115c12.png


输入


n


第1行先输入n表示有n个数据，接着输入n个数据


第2行输入要插入的位置和新数据


第3行输入要插入的位置和新数据


第4行输入要删除的位置


第5行输入要删除的位置


第6行输入要查找的位置


第7行输入要查找的位置


输出


n


数据之间用空格隔开，


第1行输出创建后的单链表的数据


每成功执行一次操作（插入或删除），输出执行后的单链表数据


每成功执行一次查找，输出查找到的数据


如果执行操作失败（包括插入、删除、查找等失败），输出字符串error，不必输出单链表


输入样例


6 11 22 33 44 55 66

3 777

1 888

1

11

0

5


输出样例


11 22 33 44 55 66

11 22 777 33 44 55 66

888 11 22 777 33 44 55 66

11 22 777 33 44 55 66

error

error

44


参考代码

#include <bits/stdc++.h>
using namespace std;
#define ok 0
#define error -1
//链表结点类定义
class ListNode {
public:
    int data;
    ListNode *next;
    ListNode() {
        next = NULL;
    }
};
//带头结点的单链表类定义
class LinkList {
public:
    ListNode *head;
    int len;
    //操作定义
    LinkList() {
        head = new ListNode();
        len = 0;
    }
    //链表回收，要逐个结点回收
    ~LinkList() {
        ListNode *p, *q;
        p = head;
        while (p != NULL) {
            q = p;
            p = p->next;
            delete q;
        }
        len = 0;
        head = NULL;
    }
    //返回第i个结点的指针，如果不存在返回NULL
    ListNode *LL_index(int i) {
        if (i < 0 || i > len)
            return NULL;
        int k = 0;
        ListNode *p = head;
        while (p && k < i) {
            p = p->next;
            k++;
        }
        return p;
    }
    //获取第i个元素的数据
    int LL_get(int i) {
        ListNode *p = LL_index(i);
        return p->data;
    }
    //把数值item插入第i个位置
    int LL_insert(int i, int item) {
        if (i <= 0 || i > len + 1)
            return error;
        ListNode *p = LL_index(i - 1);
        ListNode *newNode = new ListNode();
        newNode->data = item;
        newNode->next = p->next;
        p->next = newNode;
        len++;
        return ok;
    }
    //删除第i个结点
    int LL_del(int i) {
        if (i <= 0 || i > len)
            return error;
        ListNode *p = LL_index(i - 1);
        ListNode *q = p->next;
        p->next = q->next;
        delete q;
        return ok;
    }
    //输出单链表的内容
    void LL_display() {
        ListNode *p;
        p = head->next;
        while (p) {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
    }
    //结点交换
    int swap(int pa, int pb) {
        ListNode *pa_point = LL_index(pa);
        ListNode *pb_point = LL_index(pb);
        if (!pa_point || !pb_point)
            return error;
        ListNode *front_pa = LL_index(pa - 1);
        ListNode *front_pb = LL_index(pb - 1);
        ListNode *temp = pa_point->next;
        pa_point->next = pb_point->next;
        pb_point->next = temp;
        front_pa->next = pb_point;
        front_pb->next = pa_point;
        return ok;
    }
    //两个单链表的合并
    int LL_merge(ListNode *La, ListNode *Lb) {
        ListNode *p = head;
        while (La && Lb) {
            if (La->data < Lb->data) {
                ListNode *temp = new ListNode();
                temp->data = La->data;
                temp->next = La->next;
                p->next = temp;
                p = p->next;
                La = La->next;
                len++;
            } else {
                ListNode *temp = new ListNode();
                temp->data = Lb->data;
                temp->next = Lb->next;
                p->next = temp;
                p = p->next;
                Lb = Lb->next;
                len++;
            }
        }
        while (La) {
            ListNode *temp = new ListNode();
            temp->data = La->data;
            temp->next = La->next;
            p->next = temp;
            p = p->next;
            La = La->next;
            len++;
        }
        while (Lb) {
            ListNode *temp = new ListNode();
            temp->data = Lb->data;
            temp->next = Lb->next;
            p->next = temp;
            p = p->next;
            Lb = Lb->next;
            len++;
        }
        return 1;
    }
};
int main() {
    int n;
    cin >> n;
    LinkList ex;
    //输入数据
    for (int i = 0; i < n; i++) {
        int data;
        cin >> data;
        ex.LL_insert(i + 1, data);
    }
    ex.LL_display();
    int index, data;
    //插入
    cin >> index >> data;
    if (ex.LL_insert(index, data) == 0)
        ex.LL_display();
    else
        cout << "error" << endl;
    cin >> index >> data;
    if (ex.LL_insert(index, data) == 0)
        ex.LL_display();
    else
        cout << "error" << endl;
    //删除
    cin >> index;
    if (ex.LL_del(index) == 0)
        ex.LL_display();
    else
        cout << "error" << endl;
    cin >> index;
    if (ex.LL_del(index) == 0)
        ex.LL_display();
    else
        cout << "error" << endl;
    //查找
    cin >> index;
    if (ex.LL_index(index) && ex.LL_index(index) != ex.head)
        cout << ex.LL_get(index) << endl;
    else
        cout << "error" << endl;
    cin >> index;
    if (ex.LL_index(index) && ex.LL_index(index) != ex.head)
        cout << ex.LL_get(index) << endl;
    else
        cout << "error" << endl;
}

2. DS单链表–结点交换


题目描述


用C++实现含头结点的单链表，然后实现单链表的两个结点交换位置。


注意不能简单交换两个结点包含数据，必须通过修改指针来实现两个结点的位置交换


交换函数定义可以参考：


swap（int pa, int pb) //pa和pb表示两个结点在单链表的位置序号


swap (ListNode * p, ListNode * q) //p和q表示指向两个结点的指针


输入


第1行先输入n表示有n个数据，接着输入n个数据


第2行输入要交换的两个结点位置


第3行输入要交换的两个结点位置


输出


第一行输出单链表创建后的所有数据，数据之间用空格隔开


第二行输出执行第1次交换操作后的单链表数据，数据之间用空格隔开


第三行输出执行第2次交换操作后的单链表数据，数据之间用空格隔开


如果发现输入位置不合法，输出字符串error，不必输出单链表


输入样例


5 11 22 33 44 55

1 4

2 6


输出样例


11 22 33 44 55

44 22 33 11 55

error


参考代码

#include <bits/stdc++.h>
using namespace std;
#define ok 0
#define error -1
//链表结点类定义
class ListNode {
public:
    int data;
    ListNode *next;
    ListNode() {
        next = NULL;
    }
};
//带头结点的单链表类定义
class LinkList {
public:
    ListNode *head;
    int len;
    //操作定义
    LinkList() {
        head = new ListNode();
        len = 0;
    }
    //链表回收，要逐个结点回收
    ~LinkList() {
        ListNode *p, *q;
        p = head;
        while (p != NULL) {
            q = p;
            p = p->next;
            delete q;
        }
        len = 0;
        head = NULL;
    }
    //返回第i个结点的指针，如果不存在返回NULL
    ListNode *LL_index(int i) {
        if (i < 0 || i > len)
            return NULL;
        int k = 0;
        ListNode *p = head;
        while (p && k < i) {
            p = p->next;
            k++;
        }
        return p;
    }
    //获取第i个元素的数据
    int LL_get(int i) {
        ListNode *p = LL_index(i);
        return p->data;
    }
    //把数值item插入第i个位置
    int LL_insert(int i, int item) {
        if (i <= 0 || i > len + 1)
            return error;
        ListNode *p = LL_index(i - 1);
        ListNode *newNode = new ListNode();
        newNode->data = item;
        newNode->next = p->next;
        p->next = newNode;
        len++;
        return ok;
    }
    //删除第i个结点
    int LL_del(int i) {
        if (i <= 0 || i > len)
            return error;
        ListNode *p = LL_index(i - 1);
        ListNode *q = p->next;
        p->next = q->next;
        delete q;
        return ok;
    }
    //输出单链表的内容
    void LL_display() {
        ListNode *p;
        p = head->next;
        while (p) {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
    }
    //结点交换
    int swap(int pa, int pb) {
        ListNode *pa_point = LL_index(pa);
        ListNode *pb_point = LL_index(pb);
        if (!pa_point || !pb_point)
            return error;
        ListNode *front_pa = LL_index(pa - 1);
        ListNode *front_pb = LL_index(pb - 1);
        ListNode *temp = pa_point->next;
        pa_point->next = pb_point->next;
        pb_point->next = temp;
        front_pa->next = pb_point;
        front_pb->next = pa_point;
        return ok;
    }
    //两个单链表的合并
    int LL_merge(ListNode *La, ListNode *Lb) {
        ListNode *p = head;
        while (La && Lb) {
            if (La->data < Lb->data) {
                ListNode *temp = new ListNode();
                temp->data = La->data;
                temp->next = La->next;
                p->next = temp;
                p = p->next;
                La = La->next;
                len++;
            } else {
                ListNode *temp = new ListNode();
                temp->data = Lb->data;
                temp->next = Lb->next;
                p->next = temp;
                p = p->next;
                Lb = Lb->next;
                len++;
            }
        }
        while (La) {
            ListNode *temp = new ListNode();
            temp->data = La->data;
            temp->next = La->next;
            p->next = temp;
            p = p->next;
            La = La->next;
            len++;
        }
        while (Lb) {
            ListNode *temp = new ListNode();
            temp->data = Lb->data;
            temp->next = Lb->next;
            p->next = temp;
            p = p->next;
            Lb = Lb->next;
            len++;
        }
        return 1;
    }
};
int main() {
    int n;
    cin >> n;
    LinkList ex;
    //输入数据
    for (int i = 0; i < n; i++) {
        int data;
        cin >> data;
        ex.LL_insert(i + 1, data);
    }
    ex.LL_display();
    int index1, index2;
    cin >> index1 >> index2;
    if (ex.swap(index1, index2) == 0)
        ex.LL_display();
    else
        cout << "error" << endl;
    cin >> index1 >> index2;
    if (ex.swap(index1, index2) == 0)
        ex.LL_display();
    else
        cout << "error" << endl;
}


文章标签：
负载均衡
C++
关键词：
数据结构链表
链表数据结构
相关实践学习
SLB负载均衡实践
本场景通过使用阿里云负载均衡 SLB 以及对负载均衡 SLB 后端服务器 ECS 的权重进行修改，快速解决服务器响应速度慢的问题
负载均衡入门与产品使用指南
负载均衡（Server Load Balancer）是对多台云服务器进行流量分发的负载均衡服务，可以通过流量分发扩展应用系统对外的服务能力，通过消除单点故障提升应用系统的可用性。 本课程主要介绍负载均衡的相关技术以及阿里云负载均衡产品的使用方法。
wstqfqdpnmll4
目录
相关文章
XIAZHI
|
3月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法，并分析时间复杂度，理解链表特点。实验内容包括循环链表应用（约瑟夫回环问题）、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践，加深对链表数据结构的理解和应用能力。
XIAZHI
86 4
Cyan_RA9
|
23天前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表（下）
408考研——《数据结构》算法题基础篇之链表（下）。
Cyan_RA9
83 29
Cyan_RA9
|
23天前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表（上）
408考研——《数据结构》算法题基础篇之链表（上）。
Cyan_RA9
88 25
RossyYan
|
1月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算（头歌实践教学平台习题）【合集】
本内容介绍了单链表的基本运算任务，涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法，并提供了测试说明、通 - **任务描述**：实现单链表的基本运算。 - **相关知识**：包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**：平台会对你编写的代码进行测试，提供测试输入和预期输出。 - **通关代码**：给出了完整的C++代码实现。 - **测试结果**：展示了测试通过后的预期输出结果。 开始你的任务吧，祝你成功！
RossyYan
46 5
三三是该溜子
|
2月前
|
数据库
数据结构中二叉树，哈希表，顺序表，链表的比较补充
二叉搜索树，哈希表，顺序表，链表的特点的比较
三三是该溜子
61 0
数据结构中二叉树，哈希表，顺序表，链表的比较补充
龙大吉
|
3月前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
103 5
ephemerals__
|
3月前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
180 4
肾透侧视攻城狮
|
3月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解（9）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
52 2
肾透侧视攻城狮
|
3月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构之单双链表按位、值查找；[前后]插入；删除指定节点；求表长、静态链表等代码及具体思路详解步骤；举例说明、注意点及常见报错问题所对应的解决方法
肾透侧视攻城狮
72 2
XIAZHI
|
3月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能，支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构，并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示，系统在处理小规模购物车时表现良好，但在大规模购物车操作下可能存在性能瓶颈。
XIAZHI
75 0

热门文章

最新文章

  • 1
    C 408—《数据结构》易错考点200题（含解析）
  • 2
    C 408—《数据结构》算法题基础篇—链表（上）
  • 3
    C 408—《数据结构》算法题基础篇—链表（下）
  • 4
    C 408—《数据结构》图、查找、排序专题考点（含解析）
  • 5
    C 408—《数据结构》算法题基础篇—数组（通俗易懂）
  • 6
    c语言及数据结构实现简单贪吃蛇小游戏
  • 7
    数据结构（C语言）之对归并排序的介绍与理解
  • 8
    ☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
  • 9
    Redis原理—1.Redis数据结构
  • 10
    【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
  • 1
    【C++数据结构——线性表】单链表的基本运算（头歌实践教学平台习题）【合集】
    46
  • 2
    数据结构中二叉树，哈希表，顺序表，链表的比较补充
    61
  • 3
    【C语言】深入浅出：C语言链表的全面解析
    842
  • 4
    在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
    103
  • 5
    数据结构实验之链表
    87
  • 6
    数据结构之购物车系统(链表和栈)
    75
  • 7
    顺序表和链表（2）
    79
  • 8
    【数据结构】双向带头循环链表（c语言）（附源码）
    135
  • 9
    【数据结构】手把手教你单链表（c语言）（附源码）
    180
  • 10
    顺序表和链表（1）
    49

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    阿里云oss简介和如何对接使用