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

提示&＃xff1a;文章写完后&＃xff0c;目录可以自动生成&＃xff0c;如何生成可参考右边的帮助文档

前言

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

提示&＃xff1a;以下是本篇文章正文内容&＃xff0c;下面案例可供参考

一、什么是链表

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

二、链表的分类

顺序链表

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

链表结构图

代码如下&＃xff08;示例&＃xff09;&＃xff1a;

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


2.逆序链表

其实说白了逆序链表就是先进入的结点向后走&＃xff0c;后进的结点在前&＃xff0c;然后遍历&＃xff0c;就可以得到逆序链表;

代码如下&＃xff08;示例&＃xff09;&＃xff1a;

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


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

链表的库函数&＃xff08;模板函数&＃xff09;

代码演示&＃xff1a;

#define _CRT_SECURE_NO_WARNINGS 1
#include
#include//包含头文件&＃xff0c;引用STL中的list模板
using namespace std;
list<int>createList(int n)//建立顺序链表
{list<int>myList;int t;for (int i &＃61; 0; i < n; i&＃43;&＃43;){cin >> t;myList.push_back(t);//将t连接到链表的尾部;}return myList;
}
//输出链表;
void prtList(list<int>myList)
{list<int>::iterator it;//list::iterator类型迭代器;for (it &＃61; myList.begin(); it !&＃61; myList.end(); it&＃43;&＃43;)//注意&＃xff0c;在STL模板中&＃xff0c;迭代器没有小于号的重载&＃xff0c;故只能用it&＃xff01;&＃61;myList.end&＃xff08;&＃xff09;来结束;{if (it !&＃61; myList.begin())cout << " ";cout << *it; //此时it就相当于c语言中的一个结构体指针;}cout << endl;
}
//比较函数;降序排列;
bool cmp(int a, int b)
{return a >&＃61; b;
}
//调试函数;
int main(void)
{int n;cin >> n;list<int>myList &＃61; 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);
}


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

STL之list的应用

#include
#include
using namespace std;
struct Node
{string name;int age;
};
//创建链表;
list<Node>creatListQueue(int n)
{list<Node>myList;Node t;for (int i &＃61; 0; i < n; i&＃43;&＃43;){cin >> t.name >> t.age;myList.push_back(t);}return myList;
}
//打印函数;
void prtList(list<Node>myList)
{list<Node>::iterator it;for (it &＃61; myList.begin(); it !&＃61; myList.end(); it&＃43;&＃43;){if (it !&＃61; myList.begin())cout << " ";cout << it->name << it->age;}cout << endl;
}
//排序函数;
bool cmp(Node a, Node b)
{if (a.age !&＃61; b.age)return a.age > b.age;return a.name < b.name;
}
//调试函数;
int main(void)
{int n;cin >> n;list<Node>myList&＃61;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&＃xff0c;仔细观察&＃xff0c;这些模板之间都有很多相似之处&＃xff0c;所以不需要去背这些代码&＃xff0c;学会活学活用才最好&＃xff0c;本节的list模板就讲到这里&＃xff0c;其中有很多的模板函数在我们去实现代码的时候会有很大的帮助&＃xff0c;尤其是一些常用的函数&＃xff0c;上面我列举的函数都比较常用&＃xff0c;需要熟练掌握;