零.前言数据结构是阐述计算机存储组织数据的一门学科1.逻辑结构a.集合结构数据元素之间除了“同属于一个集合”的关系外b.线性结构只存在一对一c.树形结构一对多d.图结构多对多2.存储结构a.顺序存储把逻辑上相邻的元素储存在物理上也相邻的储存单元里元素之间的关系由储存单元的邻接关系来提现b.链式存储不要求逻辑上相邻的元素在物理上也相邻借助指示元素储存地址的指针表示元素之间的逻辑关系c.索引存储在储存元素的同时还附加的索引表索引主要负责标记元素的地址。d.散列存储利用散列函数根据元素的关键字直接计算该元素的储存地址。3.定义在数据结构上的运算增插入元素删删除元素改修改元素查查找元素一.数组Vector是一种可变长数组a[i]返回动态数组的第i个元素a.empty()/a.size()/a.resize()/a.push_back()/a.pop_back()/a.begin()返回指向vector头部的迭代器a.end()返回指向vector尾部元素的后一个元素的迭代器指针二.链表双向链表:c.pop_back()c.pop_front()c.push_back()c.push_front()c.size()c.insert(it,elem)三.栈A.定义栈是一种先进后出的数据结构B.算法进栈push算法退栈pop算法C.stacks.empty()若栈为空则返回ture否则返回falses.size返回栈元素的个数s.pop()删除栈顶元素返回voids.push()创建一个值为m的新元素压入栈顶s.top()返回栈顶元素的值但不删除该元素。四.队列1.queueA.定义队是一种先进先出的数据结构B.queueintqq.empty()q.size()q.pop()删除队首元素q.front()q.back()q.top()q.push()在队尾压入一个元素2.dequec.pop_back()删除最后一个数据c.pop_front()删除第一个数据c.push_back()在尾部加入一个数据c.push.front()在首部加入一个数据c.size()返回容器中实际数据的个数c.at(i)五.关联式容器1.set就是我们数学上的集合默认情况下会对元素自动进行升序排序begin()返回set容器中的第一个元素end()返回set容器中的最后一个元素clear()empty()max_size()返回set容器可能包含的元素最大个数size()2.map在实际应用中我们可以使用map容器作为一个有序的映射表可以看做是一个下标是任何类型的数组。对map单次操作的时间复杂度为O(lg).operator[]访问map中的元素若元素不存在将创建一个新元素并将该元素映射到类型为2的初始值上ma.begin()ma.end()ma.size()ma.count(elem)若elem中存在于map中返回1否则0ma.clear()初始化mapma.lower_bound()返回键值大于等于该元素给定元素的第一个位置六.树0.树1结点(node)(2) 根节点(root)(3)度 (degree)(4)深度(depth)1.二叉树[性质1]在二叉树的di第i层上最多有个节点[性质2]深度为k的二叉数至多有-1个节点(k1)[性质3]对任意一棵二叉树如果其叶节点数为度为2的节点数为则一定满足1[性质4]具有n个节点的完全二叉树的深度为floor(1)[性质5]对于一棵n个节点的完全二叉树对任一个结点编号为i)有a.如果i1则结点i根无父节点如果i1则其父结点编号为i/2。//.堆注