邓俊辉《数据结构》-向量学习笔记

目录

2021.12.7 星期二

向量

数组与向量

简单理解什么是泛化？

理解什么是接口？

向量的ADT操作接口

有序向量

唯一化-去重

有序向量的二分查找

有序向量的fibonacci查找

有序向量的二分查找（改进）

2021.12.8 星期三

 起泡排序 Bubblesort

改进

 再改进

归并排序 Mergesort

分治策略

二路归并

位图 bitmap

2021.12.20

vector二维数组

初始化

获取长度

赋值

2021.12.7 星期二 向量

在线性结构中，各数据项按照一个线性次序构成一个整体。最基本的线性结构统称为序列，按照逻辑和储存地址的不同分为向量（vector）和列表（list）。逻辑次序-秩（rank）。

数组与向量

在数组中：应该知道什么是前驱、后继、直接前驱、直接后继。

对于向量，向量是数组的一般性推广，使得数组特征更具普遍性。向量是线性数组的抽象和泛化，那么有必要理解一点：

简单理解什么是泛化？

参考文章：https://blog.csdn.net/shrak_12/article/details/110186581

泛化我们在机器学习（深度学习）中能够看到。对某件事情的规律进行的掌握程度，就是泛化能力。做题时如果善于总结做题规律，说明泛化能力好，如果只是一门心思做题没掌握规律，则说明泛化能力差。

泛化与优化：优化（optimization）是调节模型得到最佳性能，而泛化（generalization）是指深度学习得到了模型后，在前所未有的数据上性能的好坏。

理解什么是接口？

参考文章：C++接口的定义与实现_zhanghui962623727的博客-CSDN博客_c++接口

简单的例子：安卓苹果的充电线接到手机上的接口样子是不同的，但是连接电源的接口都是USB接口，当我们想要对不同的设备进行充电的时候，我们不需要在电源上设置各种各样的接口，只需要给个USB接口，使用不同的充电线就行，这样就大概理解了接口的意思。

参考文章中对接口的定义：将内部实现细节封装起来，外部用户用过预留的接口可以使用接口的功能而不需要知晓内部具体细节。

接口的定义：通常在头文件中完成类接口的定义

接口的实现：通常在源文件代码调用来实现接口

向量的ADT操作接口

图片来自C++学习书籍

有序向量 唯一化-去重

低效的方法：从前向后依次比对，发现重复的就删除，为O(n²) 【没有充分利用有序性】

高效的方法：

vectoruniquify(){
rank i=0,j=0; //互异的秩
  while(++j