C++之链表
发布日期:2022-02-06 00:27:06
浏览次数:41
分类:技术文章
本文共 7639 字,大约阅读时间需要 25 分钟。
C++之链表
怎么理解链表?
就是说现在有一个小纸条,上面写着一个抽屉的地址,那个抽屉里面有一些你需要的东西,和一个新的写着地址的小纸条,这个小纸条又指向了一个新抽屉,大体可以这么理解
程序所包含的头文件
#include#include using namespace std;
1. 构建抽屉
既然把装有东西和写有地址的小纸条比作抽屉那么我们不妨先写出抽屉的结构体
struct listpoint{ int data; //这是一个数字,也就是抽屉里存放的东西 listpoint* next; // 这是一个指向新抽屉的指针};
这就是一个简单的结构体
我们可以在抽屉里面放下一个抽屉的指针,自然也可以放上一个抽屉的指针:
struct listpoint{ int data; listpoint* next; listpoint* last;};
我们在抽屉里不仅仅可以放一个数,我们可以往里面放一个收纳盒,例如,在下面的结构体中包含了另一个结构体
struct data{ int number; char name[10]; char sex[10];};struct listpoint{ data* information; listpoint* next; listpoint* last;};//那个叫做information的小收纳盒装着一个人的学号,姓名,性别等信息
2. 创建一个链表
2.1 创建一个基础链表
listpoint* create_normal_list(int n)//链表每一个节点都是指向listpoint结构的指针,所以返回值是listpoint*,其中n是指创建的链表的节点数目{ listpoint* head, *normal, *end; //创建头节点,其他节点,尾节点 head=(listpoint*)malloc(sizeof(listpoint)); //分配内存 head->information=(data*)malloc(sizeof(data)); //分配内存 end=head; //最开始最后一个节点就是头节点,注意因为通过指针可以直接对地址上的东西进行操作,此时end与head指向同一个地址 for(int i=0;iinformation=(data*)malloc(sizeof(data)); cout<<"intput the number:"; cin>>normal->information->number; //往新节点存入数据,注意我们只给后面的节点存入数据 cout<<"input the name:"; //head节点不存数据 cin>>normal->information->name; cout<<"input the sex:"; cin>>normal->information->sex; cout<<"---------------------"< next=normal; //往end后增添新节点 normal->last=end; //新节点的上一个节点就是end end=normal; //让新节点变成end节点 } end->next=NULL; //链表的最后next为空指针 head->last=NULL; //链表的开始last为空指针 return head;}
2.2 创建环状链表
操作与之前一样,只不过最后一个节点的next指向头节点
listpoint* creat_loop_list(int n){ listpoint* head,*normal,*end; head=(listpoint*)malloc(sizeof(listpoint)); head->infomation=(data*)malloc(sizeof(data)); end=head; for(int i=0; iinformation=(data*)malloc(sizeof(data)); cout<<"intput the number:"; cin>>normal->information->number; cout<<"input the name:"; cin>>normal->information->name; cout<<"input the sex:"; cin>>normal->information->sex; cout<<"---------------------"< next=normal; normal->last=end; end=normal; } end->next=head; //环状链表这里与前面基础链表不同 head->last=end; return head;}
3. 修改链表
3.1 修改数据
因为我们通过指针可以直接修改地址储存的信息,所以函数并不需要返回值
void change_point(listpoint* list, int n, data* ifmation){ listpoint* p; p=list; for(int i=0, inext; } p->information=ifmation;}
3.2 删除节点
void delete_point(listpoint* list, int n){ listpoint* p; p=list; for(int i=0, inext; } p->last->next=p->next; p->next->last=p->last; free(p);}
3.3 插入节点
void insert_point(listpoint* list, int n, data* ifmation){ listpoint* p; p=list; for(int i=0; inext; } listpoint* insertpoint; insertpoint=(listpoint*)malloc(sizeof(listpoint)); insertpoint->information=ifmation; insertpoint->last=p; insertpoint->next=p->next; p->next->last=insertpoint; p->next=insertpoint;}
3.4 搜寻节点
listpoint* search_point(listpoint* list, int n){ listpoint* p; p=list; for(int i=0; inext; } return p;}
4. 输出数据
4.1 输出单个节点数据
void output_point(listpoint* point){ cout<<"The number is:"<information->number< information->name< information->sex<
4.2 输出整个链表数据
void output_list(listpoint* point){ listpoint* p; p=point; cout<next)!=NULL) { output_point(p); }}
4.3 输出部分链表m点到n点
dvoid output_list_part(listpoin* list, int m, int n){ int difference=n-m; listpoint* p; p=list; for(int i=0; inext; } for(int i=0; i next; }}
5. 完整代码
#include#include using namespace std;struct data{ int number; char name[10]; char sex[10];};struct listpoint{ data* information; listpoint* next; listpoint* last;};listpoint* creat_normal_list(int n){ listpoint* head, *normal, *end; head=(listpoint*)malloc(sizeof(listpoint)); head->information=(data*)malloc(sizeof(data)); end=head; for(int i=0; i information=(data*)malloc(sizeof(data)); cout<<"input the number :"; cin>>normal->information->number; cout<<"input the name :"; cin>>normal->information->name; cout<<"input the sex :"; cin>>normal->information->sex; cout<<"-----------------------------"< next=normal; normal->last=end; end=normal; } end->next=NULL; head->last=NULL; return head;}void output_point(listpoint* point){ cout<<"The number is :"< information->number<<";"; cout<<"The name is :"< information->name<<";"; cout<<"The sex is :"< information->sex<<";"< next)!=NULL) { output_point(p); }}//**********************************************************int main(){ listpoint* head; head=creat_normal_list(2); output_list(head); return 0;}
6. 运行结果
创建两个节点,输入两节点相应data数据,最后打印出两节点内容:
7. C++中list用法
7.1 list中常用的函数
//list中的构造函数list(); //声明一个空列表list(n); //声明一个有n个元素的列表,每个元素都是由其默认构造函数T()构造出来的list(n,val); //声明一个有n个元素的列表,每个元素都是由其复制构造函数T(val)得来的list(first,last); //声明一个列表,其元素的初始值来源于由区间所指定的序列中的元素push_back(); //使用list成员函数push_back和push_front插入一个元素到list中push_front(); //push_back从list的末端插入,push_front实现从list的首端插入empty(); //利用empty()判断list是否为空clear(); //清空list中所有函数front(); //通过front()可以获得list容器中的头部元素back(); //通过back()可以获得list容器的最后一个元素pop_back(); //通过pop_back()删除最后一个元素pop_front(); //通过pop_front()删除第一个元素assign(); //具体和vector中的操作类似,也是有两种情况l1.assign(n, val); //将l1中的元素变为n个T(val)l1.assign(l2.begin(), l2.end()); //将l2中的从l2.begin()到l2.end()之间的数值赋给l1swap(); //交换两个链表,一个是l1.swap(l2);另外一个swap(l1,l2),都可以完成两个链表的交换reverse(); //通过reverse()完成list逆置merge(); //合并两个链表并使之默认升序(可更改),l1.merge(l2, greater ());调用结束后,l2变成空,l2元素包含原来的l1,l2的元素,并且排好序,升序。
7.2 程序示例一:
#include#include using namespace std;int main(){ list l1; list l2(2, 0); list ::iterator iter; l1.push_back(1); l1.push_back(2); l2.push_back(3); for(iter = l1.begin(); iter != l1.end(); iter++) { cout<<"l1 :"<<*iter<<" "; } cout<
<
运行结果:
7.3 程序示例二:
//结合第5部分代码,我们 #include进行修改#include
#include using namespace std;struct data{ int number; char name[10]; char sex[10];};//**********************************************************int main(){ list l1; for(int i=0; i<2; i++) { data* list_data = (data*)malloc(sizeof(data)); cout<<"Input the number is :"; cin>>list_data->number; cout<<"Input the name is :"; cin>>list_data->name; cout<<"Input the sex is :"; cin>>list_data->sex; cout<<"--------------------------------"<
::iterator iter; for(iter = l1.begin(); iter != l1.end(); iter++ ) { cout<<"The number is : "< number<<";"; cout<<"The name is : "< name<<";"; cout<<"The sex is : "< sex<<";"<
运行结果:
8. 参考链接
https://blog.csdn.net/slandarer/article/details/91863177
https://blog.csdn.net/yas12345678/article/details/52601578
刚开始尝试写代码,如有问题请指出~
转载地址:https://blog.csdn.net/weixin_46181372/article/details/112253257 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
初次前来,多多关照!
[***.217.46.12]2024年03月05日 19时08分35秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
java线程占用CPU_在windows下揪出java程序占用cpu很高的线程并完美解决
2019-04-21
java多态替换switch_使多态性无法解决那些switch / case语句的麻烦
2019-04-21
下列不属于java语言特点的是_下列选项中,不属于Java语言特点的一项是( )。...
2019-04-21
java中小数的乘法_javascript的小数点乘法除法实例
2019-04-21
kappa一致性检验教程_SPSS在线_SPSSAU_Kappa一致性检验
2019-04-21
linux shell mysql备份_linux shell 备份mysql 数据库
2019-04-21
Java双向链表时间复杂度_链表是什么?有多少种链表?时间复杂度是?
2019-04-21
unity3d能和java系统整合吗_Android与Unity3d的整合
2019-04-21
minecraft666java_我的世界的666的世界
2019-04-21
辽宁师范大学java_辽宁师范大学心理学院
2019-04-21
java程序有连接数据库_Java程序连接数据库
2019-04-21
java reduce.mdn_reduce高级用法
2019-04-21
java shape用法_Java PShape.scale方法代码示例
2019-04-21
java字符串三目_java字符串连接运算符和三目运算符
2019-04-21
python 数据挖掘48讲_Python 数据挖掘与机器学习实战(四)
2019-04-21
java 上传图片到图片服务器_java从服务器上传本地图片到图片服务器
2019-04-21
java 堆内存 非堆内存_JVM 堆内存和非堆内存
2019-04-21
Java新手写什么demo_通过入门demo简单了解netty使用方法
2019-04-21