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++使用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
阅读更多...
C++ vector的常见用法超详细讲解

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》：本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve
阅读更多...
如何高效移除C++关联容器中的元素

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元
阅读更多...
Python获取C++中返回的char*字段的两种思路

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串，目前我找到两种解决问题的思路，具体实现如下：
阅读更多...
C++ Sort函数使用场景分析

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序
阅读更多...
Java调用C++动态库超详细步骤讲解(附源码)

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,：本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步：动态库生成（vs2017+qt5.12.10）第二步：Java调用C++
阅读更多...
C/C++错误信息处理的常见方法及函数

C/C++错误信息处理的常见方法及函数

《C/C++错误信息处理的常见方法及函数》C/C++是两种广泛使用的编程语言,特别是在系统编程、嵌入式开发以及高性能计算领域,：本文主要介绍C/C++错误信息处理的常见方法及函数,文中通过代码介绍... 目录前言1. errno 和 perror()示例：2. strerror()示例：3. perror(
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2