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++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快
阅读更多...
VSCode中C/C++编码乱码问题的两种解决方法

VSCode中C/C++编码乱码问题的两种解决方法

《VSCode中C/C++编码乱码问题的两种解决方法》在中国地区,Windows系统中的cmd和PowerShell默认编码是GBK,但VSCode默认使用UTF-8编码,这种编码不一致会导致在VSC... 目录问题方法一：通过 Code Runner 插件调整编码配置步骤方法二：在 PowerShell
阅读更多...
C/C++随机数生成的五种方法

C/C++随机数生成的五种方法

《C/C++随机数生成的五种方法》C++作为一种古老的编程语言,其随机数生成的方法已经经历了多次的变革,早期的C++版本使用的是rand()函数和RAND_MAX常量,这种方法虽然简单,但并不总是提供... 目录C/C++ 随机数生成方法1. 使用 rand() 和 srand()2. 使用 <random
阅读更多...
MySQL中实现多表查询的操作方法(配sql+实操图+案例巩固 通俗易懂版)

MySQL中实现多表查询的操作方法(配sql+实操图+案例巩固 通俗易懂版)

《MySQL中实现多表查询的操作方法(配sql+实操图+案例巩固通俗易懂版)》本文主要讲解了MySQL中的多表查询,包括子查询、笛卡尔积、自连接、多表查询的实现方法以及多列子查询等,通过实际例子和操... 目录复合查询1. 回顾查询基本操作group by 分组having1. 显示部门号为10的部门名，员
阅读更多...
Win32下C++实现快速获取硬盘分区信息

Win32下C++实现快速获取硬盘分区信息

《Win32下C++实现快速获取硬盘分区信息》这篇文章主要为大家详细介绍了Win32下C++如何实现快速获取硬盘分区信息,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 实现代码CDiskDriveUtils.h#pragma once #include <wtypesbase
阅读更多...
C++ Primer 标准库vector示例详解

C++ Primer 标准库vector示例详解

《C++Primer标准库vector示例详解》该文章主要介绍了C++标准库中的vector类型,包括其定义、初始化、成员函数以及常见操作,文章详细解释了如何使用vector来存储和操作对象集合,... 目录3.3标准库Vector定义和初始化vector对象通列表初始化vector对象创建指定数量的元素值
阅读更多...
C++实现回文串判断的两种高效方法

C++实现回文串判断的两种高效方法

《C++实现回文串判断的两种高效方法》文章介绍了两种判断回文串的方法：解法一通过创建新字符串来处理,解法二在原字符串上直接筛选判断,两种方法都使用了双指针法,文中通过代码示例讲解的非常详细,需要的朋友... 目录一、问题描述示例二、解法一：将字母数字连接到新的 string思路代码实现代码解释复杂度分析三、
阅读更多...
Python爬虫selenium验证之中文识别点选+图片验证码案例(最新推荐)

Python爬虫selenium验证之中文识别点选+图片验证码案例(最新推荐)

《Python爬虫selenium验证之中文识别点选+图片验证码案例(最新推荐)》本文介绍了如何使用Python和Selenium结合ddddocr库实现图片验证码的识别和点击功能,感兴趣的朋友一起看... 目录1.获取图片2.目标识别3.背景坐标识别3.1 ddddocr3.2 打码平台4.坐标点击5.图
阅读更多...
C++一个数组赋值给另一个数组方式

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法：使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::
阅读更多...
C++使用栈实现括号匹配的代码详解

C++使用栈实现括号匹配的代码详解

《C++使用栈实现括号匹配的代码详解》在编程中,括号匹配是一个常见问题,尤其是在处理数学表达式、编译器解析等任务时,栈是一种非常适合处理此类问题的数据结构,能够精确地管理括号的匹配问题,本文将通过C+... 目录引言问题描述代码讲解代码解析栈的状态表示测试总结引言在编程中，括号匹配是一个常见问题，尤其是在
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2