数据结构
所有复杂的数据结构都是基于数组,链表和树结构去实现 数组(最基本) 链表(最基本)(单向链表,双向链表,单向环状链表,双向环状链表)(使用结构和指针实现链表) 栈(链表和数组都能实现栈) 队列(链表和数组都能实现队列) 树(数据量大,链表的访问时间就长,所以使用树 平均O(logN))(使用结构和指针实现树) 散列表(哈希表,采用结构数组实现) 堆(最大堆或最小堆,可以从顶端取的最大或最小的元素,采用vector或者数组来实现) 图 STL: vector(可扩展的数组)【使用数组实现】 list(双向链表)【使用双向环状链表实现】 queue(单向队列)【使用deque作为基础容器封装实现】 deque(双向队列)【使用二维数组实现】 priority_queue(优先队列)【使用最大(小)堆实现】 set(不重复,排序后的value容器)【使用自顶向下的红黑树实现】 map(不重复,排序后的key,是一个key-value容器)【使用自顶向下的红黑树实现】 vector支持随机访问,而list支持常量时间的删除,deque支持的是随机访问以及首尾元素的删除 stack,queue,priority_queue它们均不是标准的STL容器,却都是以标准STL容器为基础。stack和queue默认是在deque的基础上封装的,priority_queue默认是在vector的基础上封装出来的。stack和queue的基础容器之所以选择deque而不选择vector等容器,是因为deque在删除元素的时候可以释放空间,同时在重新申请空间的时候无需拷贝所有元素。 树结构自底向上插入(删除)的缺点: 那么就需要在红黑树结构体里加上父亲指针,或者使用栈的方式来解决递归向上。 1. 这样就就使得结构体变大了,这样的情况在自底向上实现AVL树时也出现了(我先自底向上实现了AVL树,觉得太繁琐,又自顶向下实现了一遍)。 2. 加上父亲节点之后,编程变得非常的麻烦,特别是旋转操作时,需要非常小心。(在编写自底向上的AVL树时就吃过亏) 树结构自顶向下插入(删除)的改进: 1. 无需添加父亲指针 2. 编码简单