链表与STL数据结构总结

"让我写了两个半小时的总结（2023.7.13写于信友队集训营）" 这篇总结涵盖了计算机科学中的基础数据结构和C++中的STL（标准模板库）相关知识。首先，我们关注的是链表这一重要的链式存储结构。 链表是一种非连续存储数据的结构，与顺序存储（如数组）不同。在链表中，每个节点由两部分组成：数据域，用于存储实际的数据，以及指针域，用于存储指向下一个节点的地址。链表有多种类型，包括单向链表、循环链表和双向链表。单链表的建立通常包括定义节点结构，创建头结点和尾结点，然后依次添加新节点。查找、删除和插入操作在单链表中都有特定的步骤，如删除操作需将前一个节点的指针域指向被删除节点的下一个节点。 接下来，讨论了C++的STL，它提供了一系列预定义的数据结构和算法，极大地简化了编程工作。STL包括stack（栈）、queue（队列）、vector（动态数组）、set（集合）和map（映射）。栈遵循先进后出（FILO）原则，常用于后进先出的操作，如函数调用。队列则遵循先进先出（FIFO）原则，常用于模拟“先来的先服务”场景。vector是一种动态数组，可以方便地进行元素的添加和删除。set则是一个自动去重并保持元素排序的集合，而map则是一个键值对的映射结构，允许通过键来高效查找、插入和删除对应的值。 在栈的示例中，展示了如何定义栈、使用push和pop操作以及验证栈序列的代码。队列的定义和常用操作，包括enqueue和dequeue，也有展示。此外，还提到了优先队列，一种可以自定义优先级的队列结构。对于vector，介绍了其定义、初始化、访问元素和使用相关函数的方法。set的使用包括定义、访问（通过迭代器）和一些基本函数，如insert和erase。此外，还提到了使用`auto`关键字来简化类型推断的过程。 这篇总结涵盖了链表的基本概念和操作，以及C++ STL中主要容器的使用，这些都是编程中不可或缺的基础知识。理解并熟练掌握这些内容对于进行高效的程序设计至关重要。