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

简介: c++基础知识——STL之链表

一、什么是链表


链表是动态存储分配的数据结构。链表的每个结点都是一个结构体变量,包含数据域(存放数据本身)和指针域(存放下一个结点)的地址;

结构体可以定义为以下方式:

struct Node{

int data;

Node*next;

};


二、链表的分类


顺序链表


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


链表结构图


ea6fce4c13eb387a9e6ca0a52656b518_2dfde0b378d94b79bbbdc1d4091a5078.png


代码如下(示例):


#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);
}


3556c8a231ed216dae6d441e0753048a_d3c258d0072d45638042fc677b0e04e0.png


2.逆序链表


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


c60c7dd465776f47dc5062b03aec3ea0_5b44405543364af6aa2b1d091dcefc64.png


代码如下(示例):


#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);
}


f2fe0560dc6c05c4fdc0d1b660bd9c30_5f4e71f959db4363bf7741e4f973269f.png


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


eaafd8a8da823f63d9399702006d75e0_f924e9d5f53449b9bee0d998864490d2.png


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


8392f41ea58f8b32dde799a74c0c32d3_ad0edab43bed4cb88e560510de0c61d3.png


b7b3af7773062ac17397bede814b4031_5073809d18fc4c84b3125b3956ae4ed8.png


代码演示:


#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模板就讲到这里,其中有很多的模板函数在我们去实现代码的时候会有很大的帮助,尤其是一些常用的函数,上面我列举的函数都比较常用,需要熟练掌握;

相关文章
|
20小时前
|
存储 编译器 C++
C++:STL - string
C++:STL - string
7 1
|
3天前
|
存储 算法 C++
C++ STL精通之旅:向量、集合与映射等容器详解
C++ STL精通之旅:向量、集合与映射等容器详解
62 0
|
5天前
|
存储 前端开发 C++
【C++入门到精通】C++入门 —— 容器适配器、stack和queue(STL)
在C++中​​std::stack​​​是一个模板类,它是基于容器的适配器,用于实现堆栈数据结构。堆栈是一种后进先出(LIFO)的数据结构,类似于现实生活中的一叠盘子。
16 4
|
15天前
|
Java C++ Python
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-456 求链表各节点的平均值(C++解法)
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-456 求链表各节点的平均值(C++解法)
20 0
|
15天前
|
存储 定位技术 C++
C++ STL容器与常用库函数
C++ STL容器与常用库函数
58 0
C++ STL容器与常用库函数
|
15天前
|
机器学习/深度学习 C++
C/C++基础知识——数组、循环
C/C++基础知识——数组、循环
30 0
C/C++基础知识——数组、循环
|
19天前
|
存储 算法 C++
开心档之 C++ STL 教程
开心档之 C++ STL 教程
|
20天前
|
存储 算法 搜索推荐
【编码狂想】探索C++ STL:提升编程效率的强大工具集
【编码狂想】探索C++ STL:提升编程效率的强大工具集
12 0
|
20天前
|
存储 算法 C++
【C++】STL的基本用法
【C++】STL的基本用法
21 0
|
20天前
|
存储 算法 C++
【数据结构】链表—C/C++实现
【数据结构】链表—C/C++实现
13 1

相关产品

  • 云迁移中心