一、什么是链表
链表是动态存储分配的数据结构。链表的每个结点都是一个结构体变量，包含数据域（存放数据本身）和指针域（存放下一个结点）的地址;
结构体可以定义为以下方式：
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模板就讲到这里，其中有很多的模板函数在我们去实现代码的时候会有很大的帮助，尤其是一些常用的函数，上面我列举的函数都比较常用，需要熟练掌握;
