内容简介

本书是Ford和Topp两位教授于1996看出版的名著Data Structures with C++的第2版，在全球范围内已经有数以万计的学生从中受益。作者将C++语言作为算法描述语言，应用包含规范化的数据结构的标准模板库，集中讲述了数组、向量、表、关联树容器，以及集合、映射、堆、哈希表和图等数据结构及其算法，重点讨论了如何高效地存储大型数据集合，涵盖了数据库结构初级和高级教程撮新内容。书中各章章前提出学习目标，章后附有丰富的练习题、答案以及书面练习和上机编程练习，指导读者迅速、全面地掌握核心知识点和编程技巧。本书可作为计算机及相关专业数据结构课程的核心教材，对于广大研发人员，也是一本数据结构与面向对象技术完整结合的全新技术参考用书。

作者简介

[英] 福特，陈君 等 著

目录

第一章 数据结构入门
第二章 对象设计技术
第三章 算法概述
第四章 向量容器
第五章 指针和动态内存
第六章 表容器和迭代器
第七章 栈
第八章 队列和优先级队列
第九章 链表
第十章 二叉树
第十一章 关联容器
第十二章 高级关联结构
第十三章 继承和抽象类
第十四章 堆、2进制文件和位组
第十五章 递归算法
第十六章 图

感悟与笔记

一、vector常见用法详解

1. vector翻译为向量，但是这里翻译成变长数组的叫法更好理解。
2. 如果typename是一个STL容器，定义的时候要记得在>>符号之间加上空格，因为在C++11之前标准的编译器会把他当成位移操作。vector<vector > name;
3. vector Arrayname[arrySize]和vector<vector > name不一样，其中定义为数组的即第一个中每个都是一个vector容器，一维长度已经固定为arrySize的大小。
4. vector元素访问有两种方式，一种是通过下标，还有一种是通过迭代器，通过下标访问和普通数组是一样的操作，重点是通过迭代器访问，vector::iterator it;可以把迭代器理解成像指针一样的东西，通过*it可以访问vector里面的内容。在C++11中特别是在for循环中可以写成auto it
5. v[i]和*(v.begin()+i)是等价的
6. 左闭右开记住这个思想
7. 迭代器中还实现了两种自加操作：++it和it++（自减同理）迭代器支持it < v.end()因此循环条件一般使用it != v.end()
8. 在常用STL容器中，只有vector和string中才允许使用v.begin()+i这种迭代器上加数字的写法。
9. 迭代器：vector<typename>::iterator it;

常用函数：

1. push_back()就是在vector后添加一个元素，时间复杂度为O(1)
2. pop_back()就是在vector末尾删除一个元素，时间复杂度为O(1)
3. size()用来获得vector中元素的个数，时间复杂度为O(1)，size返回的是unsigned类型，这一点对所有的STL都是一样的。
4. clear()用来清空vector中所有的元素
5. insert(it, x)用来向vector的任意迭代器it处插入一个元素x，时间复杂度为O(N)
6. erase()有两种用法删除单个元素，删除一个区间内的所有元素，时间复杂度均为O(N)，erase(it)删除迭代器为it位置处的元素；erase(first, last)例如erase(v.begin(), v.begin()+i),左闭右开。

常见用法：

1. 存储数据本身可以作为数组使用
2. 用邻接表存储图

二、set的常见用法详解

1. set翻译为集合，是一个内部自动有序且不含重复元素的容器。
2. set容器的元素只能通过迭代器（iterator）访问。
3. set内的元素自动递增排序，且自动去除了重复元素。
4. 迭代器：set::iterator it;

常见函数用法：

1. insert(x)可以将x插入set容器中，并自动递增排序和去重，时间复杂度O(logN)。
2. find(value)返回set中对应值为value的迭代器。时间复杂度同上。
3. erase()有两种用法，删除单个元素；删除一个区间的所有元素。删除单个元素有两种方法：（1）st.erase(it),it为所需删除元素的迭代器，时间复杂度为1，结合find()函数使用(2)st.erase(value),value为所需删除元素的值，时间复杂度为O(logN);然后是删除区间元素st.erase(first, last)记住这里都是迭代器。
4. size()用来获得set内元素的个数，时间复杂度为1
5. clear()用来清空set中的所有元素，时间复杂度为O(N)。

常见用途：

1. 主要作用是存储自动去重和升序。
2. 如果需要处理不唯一的则需使用multiset，C++11中还加了unorder_set，以散列代替set内部的红黑树，可以实现只去重不排序的需求。

三、string的常见用法详解

1. 在C语言中，一般是使用字符串数组来表示字符串的即char str[]，但是C++直接引入string数据类型。
2. string str；
3. string可以如同字符串数组一样通过下标来访问；也可以通过迭代器来访问。
4. 如果要读入或输出整个字符串只能够使用cin或cout，如果强行使用printf输出，可以使用c_str()函数将string强制转化为字符串数组，解决这个问题，printf("%s", str.c_str())；
5. string迭代器不像其他容器那样需要参数，string::iterator it;
6. 同vector一样可以进行数字操作迭代器

常见函数:

1. 可以直接进行拼接操作 str += str2；
2. compare operator ，可以直接进行比较，是按照字典序来的
3. length()/size(), length()返回string的长度，时间复杂度为1
4. insert()有多种方法，时间复杂度为O(n)，（1）insert(pos, string),pos是下标号，string是要插入的str，（2）insert(it, it2, it3),it是原字符要插入的位置，是迭代器，it2，it3是为待插入字符串的首尾迭代器。
5. erase(),有两种用法，删除单个元素、删除一个区间内的所有元素，时间复杂度均为O(N)，str.erase(it),it为要删除的迭代器，str.erase(first, last),区间迭代器。str.erase(pos, length),删除位置开始处，length接下来需要删除的长度。
6. clear(),清空所有元素，时间复杂度为1.
7. substr()提取字符串中子串, substr(pos, len)pos为位置，len为长度。
8. string::npos是一个常数，其本身值为-1，可以作为find函数失配的返回值。
9. find()返回出现的位置，str.find(str2), str.find(str2, pos),pos是指定开始查找位置。
10. replace(), str.replace(pos, len, str2),把str从pos号位置开始，长度为len的子串替换为str2.

四、map的常见用法详解

1. map翻译为映射，也是常用的STL容器。因为map可以将任何基本类型映射到任何基本类型。
2. map<typename1, typename2> mp;如果是字符串映射到整数，必须使用string而不能使用char数组。
3. 访问方式，使用下标访问，也就是键值。也可以使用迭代器访问，和其他迭代器访问方式一样。
4. map可以使用it->first来访问键值，使用it->second来访问值。
5. map会以键值从小到大的顺序自动排序，因为map内部也是使用红黑树实现的。

常见函数：

1. find(key)返回键值为key的映射的迭代器
2. erase(),也有两种用法，单个和区间，mp.erase(it/key)注意是迭代器或是键值即可，区间都是迭代器。
3. size(),用来返回map中的对数。
4. clear(),清空所有元素。

常见用途

1. 需要建立字符与整数之间的联系
2. 判断大整数或其他类型是否存在，当bool类型使用
3. 字符串和字符串之间的映射也有可能会遇到。

五、queue的常见用法详解

1. queue翻译为队列，在STL中主要实现了一个先进先出的的容器
2. queue内元素访问，因为队列本身是一种先进先出的数据结构，因此只能通过front()来访问队首元素，通过back()来访问队尾元素，通过push()来将元素压入队列。

常见函数：

1. push(x), 将元素x压入队列，时间复杂度为1.
2. front()、back()分别用于访问队首和队尾元素。
3. pop(),让队首元素出列。
4. empty()检查队列是否为空，如果为空返回true，否则返回false
5. size()返回queue内元素的个数

主要用途：

1. 当实现广度优先搜索时，可以不用自己动手实现一个队列。
2. 在使用front()back()时，必须先使用empty()判断队列是否为空，否则会出现错误。

六、priority_queue的常见用法详解

1. priority_queue又称优先队列，由名字可知队首元素是当前队列中优先级最高的那一个，底层使用堆来进行实现。可以在任何时候使用push()加入元素，会自动调整使得队首优先级最高。
2. 优先队列元素访问，和队列不一样，没有front()和back()函数，只能通过top()函数来访问队首元素。

常见函数：

1. push()
2. top()
3. pop()
4. empty()
5. size()

会员免费下载

链接：https://pan.baidu.com/s/1W8TY1hn_KDpznT5QUhcbsw

提取码： ****** 查看

￥69/年 开通VIP会员

成为本站VIP会员即可无限下载。 请先点击百度网盘，看资源是否还在，不在请点击链接通知站长补资源。

资源标签点击标签可查看对应分类的资源

C++

资源推荐

免费 图解数据结构：使用Java

C++ 程序设计语言：第4部分 标准库（原书第4版）

C++编程思想（两卷合订本）

CSS世界

JavaScript DOM编程艺术（第2版）

C++ Primer Plus（第6版） 中文版

Vue.js快速入门

Java编程思想（第4版） [thinking in java]