[数据结构与算法]7月25日~7月30日 C++与数据结构

C++部分

继承：

本周主要学习了继承和多态的相关知识，这两个知识的理论相对来说理解起来不算很难，主要是在编程实践的过程中这种思想的理解和运用。

继承关系和复合关系的辨析:?继承是“是”的关系，如果B是A的派生类,那么B对象也是一个A对象；而复合关系是“有”的关系，C有成员变量k，k是D的对象；D对象是C对象的固有属性或组成部分。

关于protected类的成员变量的访问，谁可以访问？基类的成员函数，基类的友元函数，派生类的成员函数可以访问当前对象的基类保护成员；总之，protected的访问范围是介于public和private之间的一类成员变量

派生类里边的构造函数只能用初始化列表去初始化基类的私有成员变量

public继承的赋值兼容规则：派生类对象可以赋值给基类对象，派生类对象的地址可以复制给基类指针，派生类对象可以初始化基类引用

多态：

表现形式1：派生类的指针可以赋给基类指针，通过基类指针调用基类和派生类中的同名虚函数时若该指针指向一个基类的对象，那么被调用的是基类的虚函数；反之是派生类的虚函数；

表现形式2：派生类的对象可以赋给基类的引用，通过基类引用调用基类和派生类中的同名虚函数时：若该引用引用的时一个基类的对象那么被调用的是基类的虚函数；反之则是派生类的虚函数。

多态的作用：增强程序的可扩充性，即程序需要修改或增加功能的时候，需要改动和增加代码较少。这一点在郭炜老师课程中的游戏例子以及求某一图形面积并排序输出的例子中体现很多，让我感受到多态在编程使得方便。

虽然多态提供了这样的方便，但在减少代码量的同时却也增加了时间和空间上的开销，比如时间上在调用虚函数的时候需要调用虚函数表，增加了运行时间，同时虚函数表需要额外的存储空间；但是如今机器的成本仍然是要低于人工成本的因此多态仍然是一个很好用的机制。

数据结构:

这周通过做题增加了对线性表的理解，同时理解了求最小子列和的两种算法：二分法和在线处理算法，认识到在实际编程的过程中如果自己写的算法的复杂度为O（N2），这时应该尽量优化算法使之降低到N*logN，这是可以考虑递归和二分来降低问题的规模。

下周继续努力！！！