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。

相关文章

PostgreSQL的扩展dict_int应用案例解析

PostgreSQL的扩展dict_int应用案例解析

《PostgreSQL的扩展dict_int应用案例解析》dict_int扩展为PostgreSQL提供了专业的整数文本处理能力,特别适合需要精确处理数字内容的搜索场景,本文给大家介绍PostgreS... 目录PostgreSQL的扩展dict_int一、扩展概述二、核心功能三、安装与启用四、字典配置方法
阅读更多...
Python中re模块结合正则表达式的实际应用案例

Python中re模块结合正则表达式的实际应用案例

《Python中re模块结合正则表达式的实际应用案例》Python中的re模块是用于处理正则表达式的强大工具,正则表达式是一种用来匹配字符串的模式,它可以在文本中搜索和匹配特定的字符串模式,这篇文章主... 目录前言re模块常用函数一、查看文本中是否包含 A 或 B 字符串二、替换多个关键词为统一格式三、提
阅读更多...
从入门到精通C++11 ＜chrono＞ 库特性

从入门到精通C++11 ＜chrono＞ 库特性

《从入门到精通C++11＜chrono＞库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段（Durat
阅读更多...
C++20管道运算符的实现示例

C++20管道运算符的实现示例

《C++20管道运算符的实现示例》本文简要介绍C++20管道运算符的使用与实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录标准库的管道运算符使用自己实现类似的管道运算符我们不打算介绍太多，因为它实际属于c++20最为重要的
阅读更多...
Visual Studio 2022 编译C++20代码的图文步骤

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性：
阅读更多...
c++中的set容器介绍及操作大全

c++中的set容器介绍及操作大全

《c++中的set容器介绍及操作大全》：本文主要介绍c++中的set容器介绍及操作大全,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录​​一、核心特性​​️ ​​二、基本操作​​​​1. 初始化与赋值​​​​2. 增删查操作​​​​3. 遍历方
阅读更多...
解析C++11 static_assert及与Boost库的关联从入门到精通

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识：传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决
阅读更多...
C++11委托构造函数和继承构造函数的实现

C++11委托构造函数和继承构造函数的实现

《C++11委托构造函数和继承构造函数的实现》C++引入了委托构造函数和继承构造函数这两个重要的特性,本文主要介绍了C++11委托构造函数和继承构造函数的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、委托构造函数1.1 委托构造函数的定义与作用1.2 委托构造函数的语法1.3 委托构造函
阅读更多...
C++11作用域枚举(Scoped Enums)的实现示例

C++11作用域枚举(Scoped Enums)的实现示例

《C++11作用域枚举(ScopedEnums)的实现示例》枚举类型是一种非常实用的工具,C++11标准引入了作用域枚举,也称为强类型枚举,本文主要介绍了C++11作用域枚举(ScopedEnums... 目录一、引言二、传统枚举类型的局限性2.1 命名空间污染2.2 整型提升问题2.3 类型转换问题三、C
阅读更多...
Python get()函数用法案例详解

Python get()函数用法案例详解

《Pythonget()函数用法案例详解》在Python中,get()是字典（dict）类型的内置方法,用于安全地获取字典中指定键对应的值,它的核心作用是避免因访问不存在的键而引发KeyError错... 目录简介基本语法一、用法二、案例：安全访问未知键三、案例：配置参数默认值简介python是一种高级编
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2