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。

相关文章

C#如何调用C++库

C#如何调用C++库

《C#如何调用C++库》：本文主要介绍C#如何调用C++库方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录方法一：使用P/Invoke1. 导出C++函数2. 定义P/Invoke签名3. 调用C++函数方法二：使用C++/CLI作为桥接1. 创建C++/CL
阅读更多...
Java Stream流使用案例深入详解

Java Stream流使用案例深入详解

《JavaStream流使用案例深入详解》：本文主要介绍JavaStream流使用案例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录前言1. Lambda1.1 语法1.2 没参数只有一条语句或者多条语句1.3 一个参数只有一条语句或者多
阅读更多...
MySQL 中的 JSON 查询案例详解

MySQL 中的 JSON 查询案例详解

《MySQL中的JSON查询案例详解》：本文主要介绍MySQL的JSON查询的相关知识,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 的 jsON 路径格式基本结构路径组件详解特殊语法元素实际示例简单路径复杂路径简写操作符注意MySQL 的 J
阅读更多...
Python Transformers库(NLP处理库)案例代码讲解

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模
阅读更多...
C++如何通过Qt反射机制实现数据类序列化

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类，并对数据类进行存储、打印、调试等操作。由于数据类
阅读更多...
Linux下如何使用C++获取硬件信息

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息：读取"/proc/cpuinfo"文件获取磁盘信息：读取"/proc/diskstats"文
阅读更多...
C++使用printf语句实现进制转换的示例代码

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符（formatspecifier）快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指
阅读更多...
C++中初始化二维数组的几种常见方法

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a
阅读更多...
Python中使用正则表达式精准匹配IP地址的案例

Python中使用正则表达式精准匹配IP地址的案例

《Python中使用正则表达式精准匹配IP地址的案例》Python的正则表达式(re模块)是完成这个任务的利器,但你知道怎么写才能准确匹配各种合法的IP地址吗,今天我们就来详细探讨这个问题,感兴趣的朋... 目录为什么需要IP正则表达式？IP地址的基本结构基础正则表达式写法精确匹配0-255的数字验证IP地
阅读更多...
MySQL高级查询之JOIN、子查询、窗口函数实际案例

MySQL高级查询之JOIN、子查询、窗口函数实际案例

《MySQL高级查询之JOIN、子查询、窗口函数实际案例》：本文主要介绍MySQL高级查询之JOIN、子查询、窗口函数实际案例的相关资料,JOIN用于多表关联查询,子查询用于数据筛选和过滤,窗口函... 目录前言1. JOIN（连接查询）1.1 内连接（INNER JOIN）1.2 左连接（LEFT JOI
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2