《矢量数据结构》课件

《矢量数据结构》课程目标理解矢量数据结构掌握矢量的应用掌握矢量的算法掌握矢量的基本概念，属性和操作了解矢量在实际编程中的应用场景，以及学习矢量相关的常用算法，如排序、查如何使用矢量解决问题找、遍历等矢量概述矢量是一种动态数据结构，类似于动态数组，可根据需要动态调整大小它是一种顺序容器，支持随机访问，元素存储在连续的内存位置矢量通常用于存储同类数据的集合，并提供高效的元素访问、插入、删除等操作矢量的核心概念是动态扩展，即在需要时自动扩展容量，以容纳更多元素这种“”动态特性使矢量能够灵活地处理不同数量的数据，而无需事先预知确切的存储空间大小矢量基本属性容量大小元素类型表示矢量可以存储的元素数量表示矢量中当前存储的元素数量表示矢量存储的元素类型，例如整数、浮点数或字符串矢量的声明与初始化声明1指定矢量类型和名称初始化2创建矢量对象并分配内存赋值3将值赋给矢量元素矢量元素的访问下标访问1使用下标运算符访问矢量元素，类似数组访问例如，`[]``vector[index]`迭代器访问2使用迭代器遍历矢量元素，可通过和获`begin``end`取迭代器方法at3使用方法访问指定索引的元素，并进行边界检查，防`at`止越界访问矢量元素的插入与删除插入使用方法可以将元素添加到矢量的末尾`push_back`.删除使用方法可以删除矢量末尾的元素`pop_back`.插入指定位置使用方法可以将元素插入到矢量的指定位置`insert`.删除指定位置使用方法可以删除矢量的指定位置的元素`erase`.矢量容量的扩展动态分配1矢量容量不足时，自动申请新的内存空间内存拷贝2将原有数据复制到新的内存地址释放旧内存3释放不再使用的旧内存区域矢量的遍历循环遍历使用循环语句（如循环或循环）遍历矢量的所有for while元素，依次访问每个元素迭代器使用迭代器来访问矢量中的元素，迭代器提供了一种更便捷的遍历方式范围遍历引入了范围遍历功能，使用自动推断的变量来遍历矢C++11量的所有元素常用的矢量操作添加元素删除元素使用方法在矢量末尾添加新元素使用方法删除矢量末尾的元素，或使用方法push poperase删除特定位置的元素访问元素排序使用下标运算符或方法访问矢量中的元素使用方法对矢量中的元素进行排序[]at sort矢量与指针的关系矢量使用指针来管理内存，提高效指针指向内存地址，方便访问和修改率元素指针链接元素，形成连续的内存空间矢量的内存管理动态分配自动释放12矢量使用动态内存分配，根据矢量在超出作用域时会自动释需要自动扩展其容量，避免了放其占用的内存空间，避免内预先分配固定大小内存带来的存泄漏浪费内存碎片3频繁插入和删除元素会导致内存碎片化，降低内存使用效率可以通过内存压缩或重新分配来解决矢量的异常处理越界访问内存分配失败迭代器失效当访问矢量中不存在的元素时，会抛出当矢量需要扩展容量时，如果内存分配当矢量元素被插入或删除时，迭代器可异常失败，会抛出异常能会失效，导致程序崩溃矢量的拷贝与赋值浅拷贝1仅复制矢量的地址，共享同一块内存空间深拷贝2复制矢量内容到新的内存空间，独立存在赋值操作3使用赋值运算符将一个矢量的内容复制到另一个矢量中=矢量的比较操作相等比较大小比较判断两个矢量是否完全相同比较两个矢量的大小关系矢量的排序算法冒泡排序1逐个比较相邻元素，交换位置插入排序2将元素插入已排序的部分选择排序3每次选择最小元素，并将其放置到正确位置归并排序4将序列递归地分成两半，然后合并排序快速排序5选择一个基准元素，将序列划分为两部分，并递归排序矢量的查找算法线性查找1逐个比较二分查找2有序数组哈希查找3散列函数矢量的应用案例1使用矢量存储地图数据矢量数据能够精确地表示地理要素的形状、位置和属性例如，道路、河流和建筑物可以存储为矢量数据，以便在地图应用程序中进行渲染和分析矢量的应用案例2矢量在游戏开发中扮演着重要的角色例如，在角色动画和场景建模中，矢量可以用于创建平滑的运动轨迹和精确的几何形状矢量还可以用于存储和管理游戏中的各种数据，例如角色属性、游戏地图等矢量的应用案例3矢量在游戏开发中发挥着重要作用例如，在角色动画、游戏地图和场景设计中，矢量数据结构可以有效地存储和管理大量点、线和面的信息，从而实现流畅的图形渲染和动态效果矢量的优缺点分析优点缺点•随机访问•插入删除慢•动态扩展内存占用大••内存连续易于操作•矢量与其他容器的比较数组链表集合123矢量和数组都用于存储固定大小的矢量提供快速随机访问元素，而链集合不存储重复元素，并提供了高元素，但矢量提供了动态大小调整表擅长在中间插入或删除元素选效的搜索和去重功能，与矢量侧重的功能，更灵活择取决于访问模式于顺序访问不同矢量的未来发展趋势性能优化多线程支持不断提升矢量的内存效率和运行利用多核处理器优势，提升矢量速度，以适应日益复杂的应用场操作的并行处理能力，提高程序景执行效率与其他数据结构的结合探索与其他数据结构的协同，如树、图等，以构建更强大的数据模型课程小结回顾要点展望未来我们已经详细学习了矢量数据结构的定义、属性、操作和应用矢量数据结构在软件开发中扮演着重要的角色，在未来，它将与矢量是中的一种重要的数据结构，它可以有效地存储和管理其他数据结构和算法相结合，应用于更复杂的软件系统C++大量数据思考与练习本节课学习了矢量数据结构的基本概念和应用，请同学们思考以下问题•矢量数据结构的优势和劣势是什么？•在实际应用中，如何选择合适的容器类型？•尝试用矢量数据结构实现一些简单的算法，例如排序算法或查找算法知识点回顾矢量数据结构容量与内存管理算法与操作定义、基本属性、声明与初始化、元素访容量扩展、内存分配、异常处理排序、查找、拷贝、比较、遍历问、插入与删除参考文献《数据结构》《》C++Primer Plus严蔚敏、吴伟民编著，清华大学编著，人民邮电Stephen Prata出版社出版社《源码剖析》STL侯捷编著，华章公司答疑交流如有任何问题，请随时提出让我们共同学习，共同进步！。