c++基础知识——STL之链表

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档


前言

在c语言数据结构中链表作为一种很基础但是又重要的结构。在学生管理系统中就用到了链表,而在c++中,链表也是一种重要的存储结构,不过在c++中有很多库函数,可以减少我们的麻烦,下面就给你们介绍一下;


在这里插入图片描述

提示:以下是本篇文章正文内容,下面案例可供参考

一、什么是链表

链表是动态存储分配的数据结构。链表的每个结点都是一个结构体变量,包含数据域(存放数据本身)和指针域(存放下一个结点)的地址;
结构体可以定义为以下方式:
struct Node{
int data;
Node*next;
};

二、链表的分类

顺序链表

由多个结点组成的一条线性的数据结构;

链表结构图

在这里插入图片描述

代码如下(示例):

#include<iostream>
using namespace std;
struct Node
{
	int data;
	Node* next;
};
//创建顺序链表
Node* creatNode(int n)
{
	Node* headnode = new Node;//申请动态空间;
	headnode->next = NULL;
	Node* p = headnode;
	while (n--)
	{
		Node* q = new Node;
		cin >> q->data;
		q->next = p->next;
		p->next = q;
		p = q;//每次把头结点后移,重复上面操作;
	}
	return headnode;
}
//链表的打印;
void printList(Node* headnode)
{
	Node* pmove=headnode->next;
	while (pmove)
	{
		printf("%5d", pmove->data);
		pmove = pmove->next;
	}
}
//调试函数;
int main(void)
{
	int n;
	Node *list;
	cin >> n;
	list = creatNode(n);
	printList(list);
}

在这里插入图片描述

2.逆序链表

其实说白了逆序链表就是先进入的结点向后走,后进的结点在前,然后遍历,就可以得到逆序链表;
在这里插入图片描述

代码如下(示例):

#include<iostream>
#include<assert.h>
using namespace std;
struct Student
{
	int data;
	Student* next;
};
//构建链表;
Student* Init_headnode()
{
	Student* headnode = new Student;
	headnode->next = NULL;
	return headnode;
}
//链表的构建;
void creatList(Student* headnode, int n)
{
	assert(headnode != NULL);
	Student* p = headnode;
	while (n--)
	{
		Student* newnode = new Student;
		cin >> newnode->data;
		newnode->next = p->next;
		p->next = newnode;
	}
}
//打印链表函数
void printList(Student* headnode)
{
	assert(headnode != NULL);
	Student* pmove = headnode->next;
	while (pmove)
	{
		printf("%5d", pmove->data);
		pmove = pmove->next;
	}
}
//调试函数;
int main(void)
{
	Student* headnode= Init_headnode();
	int n;
	cin >> n;
	creatList(headnode, n);
	printList(headnode);
}

在这里插入图片描述
通过这两个例子,我们可以认识到链表,链表的操作还有很多,比如删除特定的值,或者特定位置插入,删除表头,清空链表,判空以及排序等一系列的操作方式,但是如果每个操作都定义一个函数,这样太过麻烦,那我们有没有什么模板来简化这些问题喃?这就是我们今天讲的STL(模板)之链表(list)
在这里插入图片描述

链表的库函数(模板函数)

在这里插入图片描述
在这里插入图片描述
代码演示:

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<list>//包含头文件,引用STL中的list模板
using namespace std;
list<int>createList(int n)//建立顺序链表
{
	list<int>myList;
	int t;
	for (int i = 0; i < n; i++)
	{
		cin >> t;
		myList.push_back(t);//将t连接到链表的尾部;
	}
	return myList;
}
//输出链表;
void prtList(list<int>myList)
{
	list<int>::iterator it;//list<int>::iterator类型迭代器;
	for (it = myList.begin(); it != myList.end(); it++)//注意,在STL模板中,迭代器没有小于号的重载,故只能用it!=myList.end()来结束;
	{
		if (it != myList.begin())
			cout << "  ";
		cout << *it;  //此时it就相当于c语言中的一个结构体指针;
	}
	cout << endl;
}
//比较函数;降序排列;
bool cmp(int a, int b)
{
	return a >= b;
}
//调试函数;
int main(void)
{
	int n;
	cin >> n;
	list<int>myList = createList(n);
	prtList(myList);
	cout << myList.size() << endl;//获取链表的长度;
	myList.push_front(3);//在链表的头部位置加入3;
	myList.push_back(3);//在链表的尾部位置加入3;
	prtList(myList);
	myList.reverse();//链表的逆置;
	prtList(myList);//归并链表;
	myList.merge(myList,cmp);
	myList.sort(cmp);//按照降序排列;
	prtList(myList);
}

链表中的这些函数不用去背,一般在编译器上会有提示,不过要熟练掌握他的格式和用意。这些模板为我们解决一些问题减少了很多时间,方便,所以熟练掌握这些很重要;

STL之list的应用

#include<iostream>
#include<list>
using namespace std;
struct Node
{
	string name;
	int age;
};
//创建链表;
list<Node>creatListQueue(int n)
{
	list<Node>myList;
	Node t;
	for (int i = 0; i < n; i++)
	{
		cin >> t.name >> t.age;
		myList.push_back(t);
	}
	return myList;
}
//打印函数;
void prtList(list<Node>myList)
{
	list<Node>::iterator it;
	for (it = myList.begin(); it != myList.end(); it++)
	{
		if (it != myList.begin())
			cout << "  ";
		cout << it->name << it->age;
	}
	cout << endl;
}
//排序函数;
bool cmp(Node a, Node b)
{
	if (a.age != b.age)
		return a.age > b.age;
	return a.name < b.name;
}
//调试函数;
int main(void)
{
	int n;
	cin >> n;
	list<Node>myList=creatListQueue(n);
	prtList(myList);
    //对链表进行排序;
	myList.sort(cmp);
	prtList(myList);
	myList.reverse();//逆置链表;
	prtList(myList);
	Node t;
	cin >> t.name >> t.age;
	myList.insert(myList.begin(), t);
	prtList(myList);
}

总结

前面我们学习了STL之vector,仔细观察,这些模板之间都有很多相似之处,所以不需要去背这些代码,学会活学活用才最好,本节的list模板就讲到这里,其中有很多的模板函数在我们去实现代码的时候会有很大的帮助,尤其是一些常用的函数,上面我列举的函数都比较常用,需要熟练掌握;


文章标签:

原文连接:https://blog.csdn.net/qq_59931372/article/details/124548333

相关推荐

C/C++牛客网刷题练习之翻转链表篇

【开卷数据结构 】多项式的链表表示

【数据结构】设计循环队列

【每天一道算法题】合并两个排序的链表

前端算法小结 | 链表篇

平衡二叉树(AVL)

C语言关于链表的代码看不懂?一篇文章让你拿捏二级指针并深入理解函数参数列表中传参的多种形式

链表面试常见题

【Java练习题第二期】:用Java实现链表内指定区域的反转

链表面试题(图文详解)

深入yocto-queue源码,60余行代码实现一个链表队列🎉🎉

Python实现约瑟夫生者死者游戏可视化(单向循环链表实现)

六六力扣刷题链表之删除链表的倒数第N个节点

双向链表[js实现] 【6】

【开卷数据结构 】什么是二叉排序树(BST)?

六六力扣刷题链表之两两交换链表中的节点

六六力扣刷题链表之反转链表

数据结构与算法——线性表(链表篇)

数据结构与算法——栈和队列

六六力扣刷题链表之移除链表元素