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

数据结构 链表（上）

2022-12-04 129
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
本文涉及的产品
传统型负载均衡 CLB，每月750个小时 15LCU
推荐场景：
搭建高可用的微信/支付宝小程序服务
应用型负载均衡 ALB，每月750个小时 15LCU
网络型负载均衡 NLB，每月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
目录
相关文章
糜终
|
27天前
|
缓存
数据结构之 - 链表数据结构详解: 从基础到实现
数据结构之 - 链表数据结构详解: 从基础到实现
糜终
61 6
糜终
|
27天前
|
存储 算法 搜索推荐
探索常见数据结构：数组、链表、栈、队列、树和图
探索常见数据结构：数组、链表、栈、队列、树和图
糜终
84 64
肾透侧视攻城狮
|
23小时前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解（9）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
11 2
肾透侧视攻城狮
|
1天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构之单双链表按位、值查找；[前后]插入；删除指定节点；求表长、静态链表等代码及具体思路详解步骤；举例说明、注意点及常见报错问题所对应的解决方法
肾透侧视攻城狮
7 2
小强在此
|
21天前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
小强在此
23 7
GuGuStudy
|
21天前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密（附带练习唔）pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密（附带练习唔）pro
GuGuStudy
20 3
java冯坚持
|
20天前
|
算法 Java
数据结构与算法学习五：双链表的增、删、改、查
双链表的增、删、改、查操作及其Java实现，并通过实例演示了双向链表的优势和应用。
java冯坚持
14 0
数据结构与算法学习五：双链表的增、删、改、查
努力学习的小廉
|
24天前
【数据结构】——双向链表详细理解和实现
【数据结构】——双向链表详细理解和实现
努力学习的小廉
27 2
椰椰椰耶
|
24天前
|
存储 Java
【数据结构】链表
【数据结构】链表
椰椰椰耶
15 1
徐霞客320
|
25天前
|
存储 缓存
数据结构3——双向链表
数据结构3——双向链表
徐霞客320
90 1

热门文章

最新文章

  • 1
    数据结构复习笔记(6)
  • 2
    Hadoop-No.13之数据源系统以及数据结构
  • 3
    数据结构~在页面上渲染树型结构
  • 4
    我花了一夜用数据结构给女朋友写个H5走迷宫游戏
  • 5
    基于OHCI的USB主机 —— OHCI（自定义数据结构）
  • 6
    数据结构学习笔记【持续更新】
  • 7
    基于OHCI的USB主机 —— UFI数据结构2
  • 8
    R语言学习笔记（一）数据结构
  • 9
    算法导论第十四章 数据结构的扩张
  • 10
    初学python数据结构-切片
  • 1
    【数据结构】深入浅出理解链表中二级指针的应用
    99
  • 2
    线性表，双向链表，静态链表，循环链表(约瑟夫环)（上）
    74
  • 3
    【链表】还不会用C++实现链表？一文教会你各种链表的实现
    256
  • 4
    【C/C++ 链表结构】探索链表迭代器：C++实现的深入分析与优化策略
    129
  • 5
    链表的实现（文末附完整代码）
    48
  • 6
    C++链表解析：从基础原理到高级应用，全面掌握链表的使用
    510
  • 7
    【数据结构算法（二）】链表总结
    45
  • 8
    《剑指offer》——合并两个排序的链表
    50
  • 9
    《剑指offer》——从尾到头打印链表
    44
  • 10
    【移除链表元素】LeetCode第203题讲解
    50

    • 相关课程

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

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月