C++数据结构——链表（各式链表与案例）

2024-04-17 04:38
文章标签 c++ 链表 数据结构 案例 各式

本文主要是介绍C++数据结构——链表（各式链表与案例），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一：单链表

#include<iostream>
using namespace std;enum error_code{success, underflow, range_error
};struct node{int data;node* next;
};class list{public:list();~list();int length()const; // 获得链表长度 error_code get_element(const int i, int& x)const; // 按序号取元素 node* locate(const int x)const; // 按值查找响应结点 error_code insert(const int i, const int x); // 插入结点 error_code delete_element(const int i); // 删除结点error_code display(); // 显示链表所有元素  node* get_head(); // 读取链表表头指针的函数void create_R(); // 表尾插入法建表void create_H(); // 表头插入法建表 private:int count;node* head;
};list::list(){count = 0;head = new node;head->next = NULL;
}list::~list(){for(int i = 1; i <= count; i++) delete_element(i);
}int list::length()const{node* p = head->next;int n = 0;while(p != NULL){n++;p = p->next;}return n;// 或者直接 return count; 
} error_code list::get_element(const int i, int& x)const{node* p = new node;p = head->next;int j = 1;while(p != NULL && j != i){p = p->next;j++;}if(p == NULL) return range_error;x = p->data;return success;
}node* list::locate(const int x)const{node* p = new node;p = head->next;while(p != NULL){if(p->data == x) return p;elsep = p->next;}return NULL;
}error_code list::insert(const int i, const int x){if(i < 1 || i > count + 1) return range_error;node* p = new node;p = head; // 此时不能指向 head->next， 如果在第一个结点插入，那样会直接在while里死循环 int j = 0;while(j != i - 1 && p != NULL) // 搜索i-1结点 (p != NULL 的必要性？？){p = p->next;j++;}node* s = new node;s->data = x;s->next = p->next;p->next = s;count++;return success;
} error_code list::delete_element(const int i){if(i < 1 || i > count) return range_error; node* p = new node;p = head;int j = 0;while(j != i - 1 && p != NULL){ // 搜索i-1结点 p = p->next;j++;}node* u = new node;u = p->next; // 指向待删除结点p->next = u->next; // 绕过待删除结点delete u;count--;return success; 
}error_code list::display(){if(length() == 0) return underflow;node* s = new node;s = head->next;while(s != NULL){cout << s->data << "  ";s = s->next;}cout << endl;return success;
}node* list::get_head(){return head;
}void list::create_R(){int x;cin >> x;node* rear = head; // 设置尾指针while(x != -1) // 设置结束符 {node* s = new node;s->data = x;rear->next = s;rear = s;rear->next = NULL;count++;cin >> x;}
} void list::create_H(){int x;cin >> x;while(x != -1) // 设置结束符{node* s = new node;s->data = x;s->next = head->next;head->next = s;count++;cin >> x;}
}bool ReferenceError(error_code a)
{if(a == underflow){cout << "underflow!!" << endl;return false;}if(a == range_error){cout << "range_error!!" << endl;return false;}return true;
}int main()
{list L;int d;L.create_H(); // 初始化链表 ReferenceError(L.display()); // 展示链表内容 cout << L.length() << endl; // 获得链表长度 ReferenceError(L.get_element(3, d)); // 按照索引获得值 cout << d << endl;ReferenceError(L.delete_element(3)); // 删除结点 ReferenceError(L.insert(1, 0)); // 插入结点 ReferenceError(L.display());return 0;
}

二：单循环链表

将单链表的表尾结点中的后继指针改为指向表头结点，就构成了单循环链表，而且单循环链表可以不带头结点，改为单循环链表后，搜索函数就需要改变，否则会进入死循环。

带头结点的单循环链表：

#include<iostream>
using namespace std;enum error_code{success, underflow, range_error
};struct node{int data;node* next;
};class list{public:list();~list();int length()const;error_code get_element(const int i, int& x)const; node* locate(const int x)const; error_code insert(const int i, const int x); error_code delete_element(const int i);error_code display(); node* get_head();void create_R();void create_H();private:int count;node* head;
};list::list(){count = 0;head = new node;head->next = head;
}list::~list(){for(int i = 1; i <= count; i++) delete_element(i);
}int list::length()const{return count; 
} error_code list::get_element(const int i, int& x)const{if(i < 1) return range_error;node* p = new node;p = head->next;int j = 1;while(j != i){p = p->next;j++;}x = p->data;return success;
}node* list::locate(const int x)const{node* p = new node;p = head->next;while(p != head){if(p->data == x) return p;elsep = p->next;}return NULL;
}error_code list::insert(const int i, const int x){if(i < 1 || i > count + 1) return range_error;node* p = new node;p = head; int j = 0;while(j != i - 1){p = p->next;j++;}node* s = new node;s->data = x;s->next = p->next;p->next = s;count++;return success;
} error_code list::delete_element(const int i){if(i < 1 || i > count) return range_error;if(count == 0) return underflow; node* p = new node;p = head;int j = 0;while(j != i - 1){p = p->next;j++;}node* u = new node;u = p->next;p->next = u->next;delete u;count--;return success; 
}error_code list::display(){if(count == 0) return underflow;node* s = new node;s = head->next;while(s != head){cout << s->data << "  ";s = s->next;}cout << endl;return success;
}node* list::get_head(){return head;
}void list::create_R(){int x;cin >> x;node* rear = head;while(x != -1){node* s = new node;s->data = x;rear->next = s;rear = s;rear->next = head;count++;cin >> x;}
} void list::create_H(){int x;cin >> x;while(x != -1){node* s = new node;s->data = x;s->next = head->next;head->next = s;count++;cin >> x;}
}bool ReferenceError(error_code a)
{if(a == underflow){cout << "underflow!!" << endl;return false;}if(a == range_error){cout << "range_error!!" << endl;return false;}return true;
}int main()
{list L;int d;L.create_R(); // 初始化 ReferenceError(L.display()); // 展示链表 cout << L.length() << endl; // 获得链表长度ReferenceError(L.get_element(10, d)); // 按照索引取值cout << d << endl; ReferenceError(L.insert(1, 0)); // 插入值 ReferenceError(L.delete_element(6)); // 删除值ReferenceError(L.display()); return 0;
}

三：链表案例

  • 案例一：设计算法判断链表L中的元素是否是递增的，若递增，返回true，否则返回false
  • 案例二：复制链表A中的内容到B表
  • 案例三：已知递增有序列表A、B分别表示一个集合，设计算法实现A∩B，要求求解结果以相同方式存储。
#include<iostream>
using namespace std;enum error_code{success, underflow, range_error
};struct node{int data;node* next;
};class list{public:list();~list();int length()const;error_code get_element(const int i, int& x)const; node* locate(const int x)const; error_code insert(const int i, const int x); error_code delete_element(const int i);error_code display(); node* get_head();void create_R();void create_H();private:int count;node* head;
};list::list(){count = 0;head = new node;head->next = NULL;
}list::~list(){for(int i = 1; i <= count; i++) delete_element(i);
}int list::length()const{return count; 
} error_code list::get_element(const int i, int& x)const{node* p = new node;p = head->next;int j = 1;while(p != NULL && j != i){p = p->next;j++;}if(p == NULL) return range_error;x = p->data;return success;
}node* list::locate(const int x)const{node* p = new node;p = head->next;while(p != NULL){if(p->data == x) return p;elsep = p->next;}return NULL;
}error_code list::insert(const int i, const int x){if(i < 1 || i > count + 1) return range_error;node* p = new node;p = head; int j = 0;while(j != i - 1 && p != NULL){p = p->next;j++;}node* s = new node;s->data = x;s->next = p->next;p->next = s;count++;return success;
} error_code list::delete_element(const int i){if(i < 1 || i > count) return range_error; node* p = new node;p = head;int j = 0;while(j != i - 1 && p != NULL){p = p->next;j++;}node* u = new node;u = p->next;p->next = u->next;delete u;count--;return success; 
}error_code list::display(){if(length() == 0) return underflow;node* s = new node;s = head->next;while(s != NULL){cout << s->data << "  ";s = s->next;}cout << endl;return success;
}node* list::get_head(){return head;
}void list::create_R(){int x;cin >> x;node* rear = head;while(x != -1){node* s = new node;s->data = x;rear->next = s;rear = s;rear->next = NULL;count++;cin >> x;}
} void list::create_H(){int x;cin >> x;while(x != -1){node* s = new node;s->data = x;s->next = head->next;head->next = s;count++;cin >> x;}
}bool ReferenceError(error_code a)
{if(a == underflow){cout << "underflow!!" << endl;return false;}if(a == range_error){cout << "range_error!!" << endl;return false;}return true;
}// 判断是否递增
void isAdd()
{cout << "判断递增" << endl;// 初始化题目条件 list L;int d1, d2, i;L.create_R();ReferenceError(L.display());int length = L.length(); // 避免多次计算长度浪费性能 // 开始操作for(i = 1; i < length; i++){ReferenceError(L.get_element(i, d1));ReferenceError(L.get_element(i + 1, d2));if(d1 > d2){cout << "不是递增的！！" << endl;break;	    	}}if(i == length)cout << "是递增的！！" << endl;
}// 复制链表
void copy()
{cout << "复制链表" << endl;// 初始化题目条件 list La, Lb;int ia, ib, d;La.create_R();ReferenceError(La.display());// 开始操作ia = La.length();for(ib = 1; ib <= ia; ib++){ReferenceError(La.get_element(ib, d));ReferenceError(Lb.insert(ib, d));}ReferenceError(Lb.display());
}// 实现 A ∩B 
void intersection()
{cout << "实现交集" << endl;//初始化题目条件list La, Lb, Lc;int ia = 1, ib = 1, ic = 1; int x, y;La.create_R();Lb.create_R();ReferenceError(La.display());ReferenceError(Lb.display());// 开始操作int l1 = La.length();int l2 = Lb.length();while(ia <= l1 && ib <= l2){ReferenceError(La.get_element(ia, x));ReferenceError(Lb.get_element(ib, y));if(x == y){ReferenceError(Lc.insert(ic, x));ic++;ia++;ib++;}if(x > y){ReferenceError(Lc.insert(ic, y));ic++;ib++;}if(x < y){ReferenceError(Lc.insert(ic, x));ic++;ia++;}		}while(ia <= l1){ReferenceError(La.get_element(ia, x));ReferenceError(Lc.insert(ic, x));ic++;ia++;}while(ib <= l2){ReferenceError(Lb.get_element(ib, y));ReferenceError(Lc.insert(ic, y));ic++;ib++;}ReferenceError(Lc.display());
}int main()
{// 判断是否递增isAdd();// 复制链表copy();// 实现 A ∩B intersection();return 0;
}

更多内容大家可以前往我的个人博客浏览：eyes++的个人空间

这篇关于C++数据结构——链表（各式链表与案例）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/910804。

相关文章

Hadoop企业开发案例调优场景

Hadoop企业开发案例调优场景

需求 （1）需求：从1G数据中，统计每个单词出现次数。服务器3台，每台配置4G内存，4核CPU，4线程。 （2）需求分析： 1G / 128m = 8个MapTask；1个ReduceTask；1个mrAppMaster 平均每个节点运行10个 / 3台 ≈ 3个任务（4    3    3） HDFS参数调优 （1）修改：hadoop-env.sh export HDFS_NAMENOD
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
性能分析之MySQL索引实战案例

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题，本文将一起从代码层去分析为什么没有建立索引？ 开源ERP项目地址：https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置
阅读更多...
深入探索协同过滤：从原理到推荐模块案例

深入探索协同过滤：从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤（UserCF）2. 基于物品的协同过滤（ItemCF）3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代，推荐系统成为连接用户与内容的桥梁。本文聚焦于
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
06 C++Lambda表达式

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获：包含零个或者多个捕获符的逗号分隔列表 模板形参：用于泛型lambda提供个模板形参的名
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2