复习C++&笔记

类与对象

  • 1、静态成员函数没有this指针,静态成员变量可以通过classname::或object.调用,声明非常量静态成员时,需要在类中加static前缀但不能定义或初始化,在类外定义和初始化但不能再加static前缀(不方便编译器判断这是全局静态变量或属于某一个类)。
  • 2、类中函数参数表后加const则函数不能修改类的数据成员。
  • 3、友元函数都在类外定义,不能加上classname::前缀。友元函数没有this指针,可以访问类中的所有数据成员。
  • 4、this指针只在成员函数里有定义,创建一个对象后不能直接取得this指针的位置。
  • 5、构造函数可以有参数,析构函数没有参数,他们都没有返回值。
  • 6、struct和class和union都可以用来定义对象,但struct默认全部公有,class默认全部私有。union不支持继承,默认全部成员公有,union实际只能存放一个成员变量,但可以作为其中包含的任意一种变量被使用,union所占的内存空间也由其中占空间最大的类型决定,union也可以拥有成员函数(union一般用的比较少,仅供了解)。

虚函数与虚继承

  • 7、类的虚继承指继承的方式,虚基类是相对于继承的类来说的(而不是基类的属性)。虚基类解决了多继承中父类存在多个共同基类实例的问题(非虚继承的情况下,如B、C继承A,D继承B、C,则D型对象继承了B-A和C-A两个不同的基类),从而共享A的数据成员。
  • 8、当继承关系满足:基类A-基类B(虚继承基类A)-派生类C。派生类的构造函数的执行顺序:基类A、基类B、对象成员、派生类。通常在多继承中会出现多个基类B虚继承基类A,基类A的构造函数首先被调用,基类B不调用A类的构造函数。
  • 9、虚函数用法
#include <iostream>
using namespace std;
//一个计算几何体周长体积的程序
class Circle{
public://我差点没写?私有构造函数海星
    Circle(double radiu){
        radius=radiu;
    }
    virtual double area(){
        return 3.14*radius*radius;
    };
    virtual double volume(){
        return 0;
    };
protected://这里声明为protected,如果是private,重载的虚函数不能使用这些数据成员
    double radius;
};

class Sphere:public Circle{//这里一定要声明public,否则默认private,基类指针访问不了子类的继承的数据成员
public:
    Sphere(double radius):Circle(radius){
        
    }
    double volume(){
        return 100+4/3.0*3.14*radius*radius*radius;
    }
    double area(){
        return 200+4*3.14*radius*radius;
    }
};
class Column:public Circle{
public:
    Column(double radius, double heigh):Circle(radius),height(heigh){
        
    }
    double volume(){
        return 300+3.14*radius*radius*height;
    }
    double area(){
        return 400+3.14*radius*radius*2+2*3.14*radius*height;
    }
private:
    double height;
};

int main(){
    Sphere ball(1);
    cout<<ball.area()<<endl<<ball.volume()<<endl;
    Column col(1,1);
    cout<<col.area()<<endl<<col.volume()<<endl;
    Circle* ptr;//多态通过基类指针的移动实现
    ptr=&ball;
    cout<<ptr->area()<<endl<<ptr->volume()<<endl;
    ptr=&col;
    cout<<ptr->area()<<endl<<ptr->volume()<<endl;
    return 0;
}
#include <iostream>
using namespace std;

class teacher{
public:
    teacher(double pe){
        peroids=pe;
    }
    virtual int total(){
        return 0;
    }
protected:
    int peroids;
};

class pro:public teacher{
public:
    pro(double pe):teacher(pe){
        
    }
    int total(){
        return 5000+50*peroids;
    }
};

class proAssistant:public teacher{
public:
    proAssistant(double pe):teacher(pe){
        
    }
    int total(){
        return 3000+30*peroids;
    }
};

class lecture:public teacher{
public:
    lecture(double pe):teacher(pe){}
    int total(){
        return 2000+20*peroids;
    }
};

int main(){
    teacher* ptr;
    pro a(10);
    proAssistant b(10);
    lecture c(10);
    ptr=&a;
    cout<<ptr->total()<<endl;
    ptr=&b;
    cout<<ptr->total()<<endl;
    ptr=&c;
    cout<<ptr->total()<<endl;
    return 0;
}

流对象

  • 10、常见的文件打开模式:ios::in 打开并读取, ios::out 打开以写入, ios::trunc 覆盖模式, ios::ate 读文件指针位于文件末尾。如果需要创建新文件,可以用out,也可以用in、out、app的组合。文件打开模式组合较多,详情见相关网站。
  • 11、关于流的方向:in和out是相对于与流操作的对象来说的,比如cin>>a,cin将键盘输入传给a,也就是a的in(输入);cout<<a时a的内容传给cout进而传给显示器,a的内容out(输出)了;文件对象同上,in模式文件对象fs使用>>运算符,将fs的内容传给右边的对象。运算符总能表示流的方向。

为什么C++短整型溢出了还可以比较!

复习C++的时候,看到一段通过比较两个short变量之和与2^15大小来判定是否溢出的代码,惊到我了,两个short相加都超过short取值范围了,还能和最大取值范围比较???

虽然很不服,还是打开了编辑器,想(毫无头绪地)验证一下这是怎么一回事。

C++获取变量类型

其实我只知道typeof,而我不知道的是,这东西并不能向用户输出变量类型?它整个作用都在编译阶段

通过Google+Stack overflow的神奇组合,typeid().name()方法浮出水面,是的,第一个括号里填表达式。

验证程序

输出结果

s=short  i==integer 

结论

原来两个short型变量相加得到了int型变量?C++是强类型语言,这种转换最好说明一下吧。

补充

两个short相加无论是否溢出,加起来都作为int型变量。

快速排序算法(C++)介绍和简易实现

快速排序算法,即一种递归地讲数组按一定大小标准分成两组,小的一组在前,大的一组排在后的算法。

有关快速排序算法的文章和图解,网络上已经很多了,但阅读理解起来可能稍有困难,接下来我们将看到更容易理解的快速排序算法。

示例:以数组的首位作为基准(pivot),将小于ta的数置于ta的左边,大于ta的数在右边,左边只有1个元素,排序完成,而右边有4个数,那么把这4个数作为新的要排序的(抽象的)数组,重复上面的过程,最终基准所在的(抽象的)数组只有基准一个元素(如下图第二排的“2”),排序完成。

快速排序算法示例

快速排序的复杂度

快排过程中需要移动元素的位置,很大程度上决定了时间复杂度。如果一个数组由大到小排列,而选取首位(最大数)为基准,则每一个元素都需要移动,而每一次移动的过程:对n个元素,考虑一般情况,分割一次数组(即小的排左边的过程)比较和交换元素的次数和n有关(虽然有的时候不用交换,但一定会比较);而快排有一颗递归树,在数字比较随机,树比较均匀的情况下,树的高度近似logn,而树的每一层都有n个元素参与partition(数组分割成抽象数组后,多个抽象数组partition,因为partition的复杂度与n的一次方相关,在估测复杂度时,可以认为每一层都有n个元素参与一次partition),随机情况的复杂度即为n*logn。

最坏情况这棵树只沿着一颗子树延伸,树的高度为n,每一层仍有n个元素参与partition,复杂度为n*n。看一下数字从大到小排列的情况,例如100到1,首次partition会进行99次比较,最后一次partition进行1次比较,并且递归也会进行99次,从等差数列的公式也可以看出来它与n的平方相关。

复杂度的数学证明:

图片来自:https://blog.csdn.net/matrix_laboratory/article/details/9342415

快速排序的代码(便于理解过程的版本,partition时移动数据,复杂度高)

#include <iostream>
using namespace std;

void QuickSort(int arr[],int start,int end){//递归的时候,start和end都相对于整个arr
    if(start>=end){return;}
    int temp=start;//保留start初始值
    int pivot=arr[start];//以数组或分割后的抽象数组的第一个元素作为基准(pivot)
    for(int i=start+1;i<=end;i++){//遍历arr[start]右边的元素
        if(arr[i]<pivot){//当arr[i]比基准小
            arr[start]=arr[i];//小的元素放到基准所在的位置
            for(int j=i;j>start;j--){//遍历arr[start]到arr[i],全体右移(arr[start]已经放了新的元素)
                arr[j]=arr[j-1];//右移
            }
            arr[++start]=pivot;//由于start和i项交换,start+1项的值需要修正,完成交换后基准右移,所以start也要++
        }
    }//完成了一次左右分组(排序)
    
    QuickSort(arr, temp, start-1);//对0号到start-1号元素排序,共有start个元素
    QuickSort(arr, start+1, end);//对右边的元素排序
}

int main(int argc, const char * argv[]) {
    int arr[]={3,4,2,7,5,8,6,1};//8个元素组成的的乱序数组
    QuickSort(arr,0,7);//8个元素即0号到7号
    for(int i=0;i<8;i++){
        cout<<arr[i]<<endl;
    }
    
    return 0;
}

快速排序的代码(普通版本)

#include <iostream>
using namespace std;

int Partition(int arr[],int &start,int &end){
    int pos=start;//(pos-start)用来记录小于等于arr[start](基准)的数的个数,arr[start+1]到arr[pos]都小于基准
    for(int i=start+1;i<=end;i++){//遍历基准以后的元素
        if(arr[i]<arr[start]){//当某一项小于基准
            if(arr[i]!=arr[++pos]){//如果任何一个大于基准的数后面所有元素中都没有小于x基准的数(即基准后的元素,前一部分全部小于基准,后一部分全部大于基准),则arr[i]==arr[pos],不需要交换;否则需要交换
                swap(arr[i], arr[pos]);
            }
        }
    }
    swap(arr[start], arr[pos]);//基准的位置开始没有移动,现在把基准的位置交换到小于基准的抽象数组的最右端,实现对数组的分割
    return pos;
}

void QuickSort(int arr[],int start,int end){//递归的时候,start和end都相对于整个arr
    if(start>=end){return;}//对应多种情况,pos可能等于start,pos-1为负,这种情况没有数小于基准,也不需要排序,对应start==end+1;pos等于start+1时,只有一个数比基准小,并且已经z位于基准左边,也不需要排序,对应start==end
    int pos=Partition(arr, start, end);//对数组或抽象数组按基准排列,基准左边的数小于基准,右边大于基准
    QuickSort(arr, start, pos-1);//对0号到start-1号元素排序,共有start个元素
    QuickSort(arr, pos+1, end);//对右边的元素排序
}

int main(int argc, const char * argv[]) {
    int arr[]={3,4,2,7,5,8,6,1};//8个元素组成的的乱序数组
    QuickSort(arr,0,7);//8个元素即0号到7号
    for(int i=0;i<8;i++){
        cout<<arr[i]<<endl;
    }
    return 0;
}

两个指针的快速排序&&Partition的优化

待补充

参考资料:

1.《算法导论》第7章:快速排序

2.快速排序的时间复杂度nlogn是如何推导的??

我的博客即将同步至腾讯云+社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=1q1xzkj9mydbq

C++使用非常量静态成员(non-const static data member)

误区一:将非常量静态成员放到private里
非常量静态成员的错误使用方法
静态成员只跟类有关,是所有对象共有的属性,如果在类中初始化则意味着每个对象都初始化一次,这样就需要非静态成员了。非常量静态成员函数不可以在类中初始化,一定要在类外把类名作为命名空间而初始化,但放在private里又只能在类里初始化,这种操作是无法实现的。但C++支持在类里定义非常量静态成员函数,如”static double average(){…};”。 误区二:在函数体内对非常量静态成员变量初始化。(xcode有提示)正确的方法是将初始化语句放到函数体外定义(在类中只有声明),然后在函数内以class::member的方式调用。
非常量静态成员的错误使用方法
综上,非常量静态成员变量需要在类的public中声明,在函数体外类外定义,以classname::member的方式使用。

参考资料:声明、定义、初始化、赋值的区别