#include <iostream>
#include <string>
using namespace std;


void merge(int a[],int c[],int first,int mid,int last){
    int i = first;
    int j = mid+1;
    int k = first;
    while(i<=mid && j<=last){
        if(a[i] <= a[j]){
            c[k] = a[i];
            k++;
            i++;
        }
        else{
            c[k] = a[j];
            k++;
            j++;
        }
    }
    while(i<=mid){
        c[k]=a[i];
        k++;
        i++;
    }
    while(j<=last){
        c[k]=a[j];
        k++;
        j++;
    }
for(int i=first;i<=last;i++)a[i]=c[i];
}

void mergeSort(int a[],int c[],int first , int last){
    if(first<last){
    int mid = (first+last)/2;
    mergeSort(a,c,first,mid);
    mergeSort(a,c,mid+1,last);
    merge(a,c,first,mid,last);
}
}

int  main(){
    int a[99] = {5,4,3,2,1};
    int c[99];
    mergeSort(a,c,0,4);
    for(int i = 0 ;i<5;i++){
        cout<<a[i]<<" ";
    }
}

归并排序的思想是分而治之,将数组不断分割,最后将两部分数组合并,通过判断第一部分和第二部分数组当前元素的大小来合并,不断合并直到完成排序。

归并排序是稳定的排序方式,归并排序的比较次数小于快速排序的比较次数,移动次数一般多于快速排序的移动次数,归并排序的时间复杂度为O(nlogn),空间复杂度为O(n)。

有时候scanf(“%c”,&ch)本应该阻塞等待用户输入一个char型数据的,但为什么会跳过呢?
例:在该程序段中,
int year;
    printf("请输入一个年份:\n");
    scanf("%d",&year);
   // setbuf(stdin,NULL);//或者直接用getchar();
    //在键盘输入一字符,显示其类型(数字、大写字母、小写字母、其他)
    char ch;
    printf("请输入一个字符:\n");
    scanf("%c",&ch);
    if(ch>='1'&&ch<='9')
        printf("this is digital\n");
    else if (ch>='A'&&ch<='B')
        printf("this is capital letter\n");
    else if (ch>='a'&&ch<='z')
        printf("this is letter\n");
    else
        printf("other!\n”);

 

会输出:
请输入一个年份:
2000
请输入一个字符:
other!
 
例2:
以下程序段:
while (n<=0)
{
printf(“请输入字符串长度:\n”);
scanf(“%d”,&n);
}
setbuf(stdin,NULL); //<1>
char a[n],b[n];
printf(“输入字符串:\n”);
for (int i=0; i<n; i++)
{
scanf(“%c”,&a[i]);
}
printf(“输出字符串为:\n”);
for (int i=0; i<n; i++)
{
b[i]=a[n-1-i];
printf(“%c”,b[i]);
}
如果将<1>语句去除,会使结果错误
例:
请输入字符串长度:
5
输入字符串:
hello
输出字符串为:
lleh

纠其根源,我们先来了解一下scanf()是怎么接受数据的。

首先,当我们的pc指向scanf这句时,系统并不是等待用户输入,而是判断输入缓冲区有没有符合格式的内容,如果有,则直接读取。

知道了这个,我就应该明白,scanf(“%c”,&ch);不是没有读到数据,而是读到了我们不知道的数据。

那问题又来了,它读到了什么??

好吧,这就要说到行缓存;

我们用scanf()的时候都要按下enter键,那enter键按了之后去哪儿了??

好吧,问题基本应该知道了,enter键也进入了输入缓存区,也就是scanf(“%c”,&ch);

读到了’\n’;

解决办法,很简单,既然缓存区有东西,那我们就清空它呗~~

setbuf(stdin,NULL);//这个windows和linux下都可以
fflush(stdin);//这个只能windows;

 

 

有没有想过,当我们定义一个对象的时候,该对象是定义在堆上还是栈上的呢?

现在,假设你已经清楚什么是堆,什么是栈。

如果需要在堆上创建对象,要么使用C++的new运算符,要么使用C语言的malloc系列函数。这点没有异议。

那么假如有一个类A,语句如下:

A a;

此时,a是在栈上分配的吗?

其实,这行语句的含义是,使对象a具有“自动存储(automatic storage)”的性质。所谓“自动存储”,意思是这个对象的存储位置取决于其声明所在的上下文。

如果这个语句出现在函数内部,那么它就在栈上创建对象。

如果这个语句不是在函数内部,而是作为一个类的成员变量,则取决于这个类的对象是如何分配的。

一般来说,如果你用new来生成的对象都是放在堆中的,而直接定义的局部变量都是放在栈中的,全局和静态的对象是放在数据段的静态存储区中。

那么,该如何定义一个只能在堆/栈上生成对象的类呢?

只能在堆上

方法:将析构函数设置为私有

原因:C++ 是静态绑定语言,编译器管理栈上对象的生命周期,编译器在为类对象分配栈空间时,会先检查类的析构函数的访问性。若析构函数不可访问,则不能在栈上创建对象。

如下所示:

#include <iostream>
using namespace std;

class A{
  public:
    A(){};
  private:
    ~A(){};//将析构函数设为私有
};

int main(){
    A a;//无法通过编译,提示A类的析构函数是私有的
    A *aa = new A();//通过编译,在堆上生成对象
}

 

只能在栈上

方法:将 new 和 delete 重载为私有

原因:在堆上生成对象,使用 new 关键词操作,其过程分为两阶段:第一阶段,使用 new 在堆上寻找可用内存,分配给对象;第二阶段,调用构造函数生成对象。将 new 操作设置为私有,那么第一阶段就无法完成,就不能够在堆上生成对象。

#include <iostream>
using namespace std;

class A{
  public:
    A(){};
    ~A(){};
   private:
    void * operator  new ( size_t  t){}//重载new运算符为私有类型
    void operator delete ( void * ptr){}//重载delete运算符为私有类型
};

int main(){
    A a;//通过编译,在栈上建立了对象
    A *aa = new A();//无法通过编译,提示new运算符是A的私有成员
}

 

翻阅以前的代码,时常会看到如下代码:

if(str.size() == 0) {}
if(!vec.size())     {}
if(!list.size())    {}
// ......

这些例子中只是把 size() 的返回值简单地进行布尔逻辑比较,意思是判断容器空与非空。

代码没有逻辑问题,只是可能效率不够高。

在C++的标准库容器中都有一个 empty() 方法,返回布尔值,表明容器当前是否为空。

使用 size() 判断容器非空与否的不好之处在于:某些标准库中的实现中对某些容器的 size() 求值操作不是线性的。

比如 std::list<>,在某些实现中,每一次调用 size() 都会遍历整个 list 来求 size,这会带来一定的性能问题。如果是线性容器则不会有此问题。

总之,如果只是想判断空与非空,则应总是使用 empty(),而不是 size()

#include <iostream>
#include<vector>
using namespace std;


void quickSort(vector<int>&a,int first , int last){
    if(first >= last){
        return;
    }
    int i = first,j = last;
    int key = a[first];//选择当前数字中第一个数作为基准key
    while(i < j){
        while(i < j && a[j] > key){
            j--;
        }
        a[i] = a[j];//在数组的后面遇到了比基准key小的数,放到前面去
        while(i < j && a[i] < key){
            i++;
        }
        a[j] = a[i];//在数组的前面遇到了比基准key大的数,放到后面去,刚好覆盖上次那个比基准大的数的位置
    }
    a[j] = key;//此时i==j,这个位置应该就是我们的基准key应该放到的地方
    quickSort(a,first,j-1);//递归对目前的key左边部分使用快速排序
    quickSort(a,i+1,last );//递归对目前的key右边部分使用快速排序
}

int main()
{
    vector<int>a = {22,32,54,79,154,2,10,0,-6,48,99};
    quickSort(a,0,10);
    for(int i = 0;i<11;i++){
        cout<<a[i]<<" ";
    }
}

快速排序是综合性能最好的排序方式,平均时间复杂度为O(nlogn),且不具有稳定性。

当序列已经是递增序列的时候,快速排序此时的时间复杂度最高,为O(n²)。

运算符重载就是用同一个运算符完成不同的运算功能,和函数重载一样,运算符重载是在编译阶段完成的,体现出静态的多态性。

C++运算符重载的规定如下:

  • 不能改变原运算符的优先级
  • 不能改变原运算符的结合性
  • 默认参数不能和运算符重载一起使用
  • 不能改变原运算符的操作数个数
  • 不能创建新的运算符,且部分已有运算符可能因为存在二义性问题所以无法被重载
  • 当运算符作用于C++内部提供的数据类型时,原来的含义保持不变。
  • 运算符可以被重载用于用户定义的类对象或者用户定义的类对象与内置数据类型变量的组合

C++中不能重载的运算符:

  1. .
  2. .*
  3. ::
  4. ?:
  5. sizeof

运算符重载为类成员函数时主要有3种形式:重载为类的成员函数、重载为类的友元函数、重载为普通函数。

 

重载++,–单目运算符

++和–重载运算符有前缀和后缀两种运算符重载形式,这里以++重载运算符为例,采用成员函数重载。

#include<iostream>
using namespace std;

class A
{
    int n;
public:
    A(int i){n = i;}
    operator ++(){//重载前缀运算符
     n++;
    }
    operator ++(int){//重载后缀运算符
     n = n+2;
    }
void show(){
cout<<"n="<<n<<endl;
}

};

int main()
{
    A a(5);
    A b(5);
    ++a;
    b++;
    a.show();
    b.show();
}

 

输出结果为:

n=6
n=7

 

如果改用成员函数的调用方式,重载后缀运算符的调用方式是a.operator++(1),其中1可以改为任意整数,它只是一个占位符。重载前缀运算符的调用方式是b.operator()。

 

重载下标运算符

下标运算符[]通常用于取数组的某个元素,下标运算符重载可以实现数组下标的越界检测等,如下Words类所示:

class Words
{
    int len;
    char *str;
public:
    Words(char *s){
    str = new char[strlen(s)+1];
    strcpy(str,s);
    len = strlen(s);
    }

    char operator[](int n){
    if(n > len-1){
        cout<<"数组下标越界";
        return ' ';//返回一个特殊字符即可
    }
    else return *(str+n);
    }
};

 

重载运算符new/delete

C++提供了new和delete两个运算符用于内存管理,在大多数情况下它们是非常有效的,但在有些情况下需要自己管理内存,以克服原new与delete的不足,这就是重载运算符new和delete。delete和delete只能被重载为类的成员函数或者普通函数,不能被重载为友元函数,而且不论是否使用关键字static进行修饰,重载了的new和delete均为类的静态成员函数。

重载new运算符的一般格式:

void *类名::operator new(size_t size,其他形参){
     //使用malloc完成分配工作
     //完成自己需要的操作
     return void *型指针;
}

上述new重载函数应返回一个无值型的指针,形参可以有多个,但第1个参数一定是size_t类型的参数,它表示要分配空间的大小,再调用时由系统自动获取。

在使用重载new运算符时先调用new的重载成员函数,再调用该类的构造函数。

重载delete运算符的一般格式:

void *类名::operator delete(void *p){
     //使用free完成内存释放工作
     //完成自己需要的操作
}

在使用重载delete运算符时默认先调用类的析构函数,再调用重载的delete成员函数。

重载new[]/delete[]和重载new/delete类似。

 

重载输入/输出运算符

重载插入运算符的一般格式如下:

friend ostream& operator<< (ostream & stream,类名 &类引用名){
  //函数体
   return stream;
}

 

重载输出运算符的一般格式如下:

friend istream& operator>> (ostream & stream,类名 &类引用名){
  //函数体
   return stream;
}

 

设计单例模式的意图是保证一个类仅有一个实例,并提供类的一个全局访问点,该实例被所有程序模块共享。

采用C++实现单例模式有多种方式,这里采用嵌套类实现。

其中类A实现单例模式。

  • 它的构造函数的私有的,这样就不能从别处创建该类的实例。
  • 它有一个唯一实例的静态对象指针pinstance,且是私有的。
  • 它有一个共有函数GetInstance(),可以获取这个唯一的实例,并在需要的时候创建该实例。
  • 设计嵌套类的目的是为了定义它的静态子对象,在程序结束时会调用该子对象的析构函数以释放唯一的实例。
  • 如果采用在类A中设计析构函数来释放实例,则该析构函数必须是公用的,这在单例模式中是不恰当的。

源代码如下:

#include<iostream>
using namespace std;

class A{
   //其他数据成员
public:
    static A *GetInstance(){
    if(pinstance ==NULL){
        pinstance = new A();
    }
    return pinstance;
    }
private:
    static A *pinstance;//返回唯一实例的指针
    class B //嵌套类,它的唯一工作就是在析构函数中释放实例
    {
    public:
        ~B(){
          if(A::pinstance!=NULL){
            delete A::pinstance;
            cout<<"delete";
          }
        }
    };
    static B b;//定义一个子对象,在程序结束时会调用它的析构函数
};

A *A::pinstance=NULL;//静态子对象指针初始化
A::B A::b;//静态子对象初始化

int main(){
    A *p= A::GetInstance();
    A *q = A::GetInstance();
    if(p == q) cout<<"Same"<<endl;
    return 0;
}

 

输出结果为:

Same
delete

 

从结果可以看出类A的两个对象指针指向同一个实例,说明只能创建唯一的实例,并且该唯一实例是自动销毁的。