来自新世界:友元,异常及其他

一个蛋疼的问题

那就是在写友元函数时会出现循环嵌套的情况,这时,就要在那个死循环的前面加个声明:Class x,就好了

 

异常

abort()函数遇到错误情况会直接退出,而不返回main函数

 

try catch

简单来说就是在一个被调用的函数里面写一个条件加throw,然后在try模块中调用,如果出错了就会直接进入相匹配的catch模块。注意这里引用一个栈解退的概念,它和return不一样,它会直接回退到最近的try模块,即中间函数生成的对象会被自动调用析构函数(自动变量元素则被自动释放)。可以利用这个特性,把控制权交给不同的函数。

 

其他异常特性

可以把error变成一个对象,然后直接throw 一个problem对象,注意这里throw的对象是对象的副本。然后catch是这个problem的引用。

#include <iostream>
using namespace std;
class bad_1{
    public:
    virtual ~bad_1(){
        cout << "bad_1 has been destoried" << endl;
    }
    void show_1(){
        cout << "this message comes from bad_1" << endl;
        return;
    }
};
class bad_2:public bad_1{
    public:
    virtual ~bad_2(){
        cout << "bad_2 has been destoried" << endl;
    }
    void show_2(){
        cout << "this message comes from bad_2" << endl;
        return;
    }
};
class bad_3:public bad_2{
    public:
    virtual ~bad_3(){
        cout << "bad_3 has been destoried" << endl;
    }
    void show_3(){
        cout << "this message comes from bad_3" << endl;
        return;
    }
};
void dumpD(int i){
    if(i == 0){
        throw bad_1();
    }else if(i == 1){
        throw bad_2();
    }else{
        throw bad_3();
    }
}
int main(){
    int j;
    cin >> j;
    try{
        dumpD(j);
    }catch(bad_1 &b1){   //注意这里的顺序是错误的!
        b1.show_1();
    }catch(bad_2 &b2){
        b2.show_2();
    }catch(bad_3 &b3){
        b3.show_3();
    }
}

为什么说是错的?当我输入1或者2时,系统抛出的错误来源都是来自bad_1而不是bad_2或者bad_3,原因是因为bad_2/3都是bad_1的派生类,因此catch的第一个是适用于他们的,所以才进入了块一。

正确的是:

int main(){
    int j;
    cin >> j;
    try{
        dumpD(j);
    }catch(bad_3 &b3){
        b3.show_3();
    }catch(bad_2 &b2){
        b2.show_2();
    }catch(bad_1 &b1){   
        b1.show_1();
    }
}

除此之外,还可以像switch一样设置一个默认值:

catch(...){
        cout << "default" << endl;
    }

 

exception 类

1.stdexcept 类:你可以自己写一个异常类,继承std中的exception类,然后重定义what()方法

class bad_my :public std::exception{
        public:
            const char * what(){return "bad news created by myself"}
    }
try{
   /*code*/
}catch(exception &e){
   cout << e.what() << endl;
}

通过继承exception类又诞生出几种错误类型:

logic_error 类

  • domain_error 定义域/值域错误
  • length_error 没用足够空间来执行操作
  • out_of_bounds 通常用于指示索引错误
  • invalid_argument  传递了一个以外的值

runtime_error 类

  • range _error
  • overflow_error
  • underflow_error

通常runtime_error表明存在无法避免的问题

 

2.bad_alloc 和 new

当new申请的空间过大时会抛出这个bad_alloc类,这个类里面的what()方法返回“std::bad_alloc”字符串

重定义退出的方向

未捕获异常:简单来说就是出错后,可以自行定义怎么退出,可以自己定义一个没用参数,没用返回值的函数,然后把函数名传给set_terminate( myQuit )

意外异常:这里说一下怎么捕获所有的异常

#include <exception>
    using namespace std;
    void myUnexpected(){
        throw std::bad_exception(); //或者只写throw
    }

 set_unexpected(myUnexpected); //在开头写

 

内存泄漏

就是在throw exception 后控制权会返回到try后面的catch模块那里,在函数进行过程中创造的类会自动调用析构函数,但是假如在前面使用了new去申请内存,那么这时就会把指针给删掉,指针指向的内存就会没用办法再去用,这就造成了内存泄漏。

 

来自新世界:类模板

先回顾一下鸭!

template <class T> //普通模板
void swap(T &a,T &b)
{
    /*code*/
}
template <class T> //模板重载
void swap(T &a,T &b,int n)
{
    /*code*/
}
                                             //设job是一个结构
template <> void swap <job> (job &a,job &b)  //显示具体化,不加 <job> 也行
{                                            //意思是不要用swap模板生成函数定义
    /*MORE code*/                            //而应该使用专门为job类型显示地定义地函数声明
}

template void swap <double>(double &a,double &b) //显示实例化,实例化模板,当遇到参数是double时用
{                                                  //可以用在参数的强制转换上
    /*code*/
}

template <class T1,class T2> //普通模板
void add(T1 x,T2 y)
{
    decltype(x + y) result = x + y;  //确定x+y的结果的类型
    decltype(function(3)) m;   //确定函数返回值的类型(假如函数是个模板)
}

template <class T1,class T2> //普通模板
auto add(T1 x,T2 y)->decltype(x+y) //确保返回值是和结果一样的类型
{
    return x + y;
}

很好,接下来就是类模板了:

template <class Type>
class Stack
{
private:
    enum {MAX = 10};    // constant specific to class
    Type items[MAX];    // holds stack items
    int top;            // index for top stack item
public:
    Stack();
    bool isempty();
    bool isfull();
    bool push(const Type & item); // add item to stack
    bool pop(Type & item);        // pop top into item
};

template <class Type>
Stack<Type>::Stack()
{
    top = 0;
}

template <class Type>
bool Stack<Type>::isempty()
{
    return top == 0;
}

template <class Type>
bool Stack<Type>::isfull()
{
    return top == MAX;
}

template <class Type>
bool Stack<Type>::push(const Type & item)
{
    if (top < MAX)
    {
        items[top++] = item;
        return true;
    }
    else
        return false;
}

template <class Type>
bool Stack<Type>::pop(Type & item)
{
    if (top > 0)
    {
        item = items[--top];
        return true;
    }
    else
        return false; 
}

可以看出类模板的每个方法都是模板函数,而且方法前变成了 Stack<Type>::

而且注意的是必须显示地提供所需的类型:

Stack<int> A;
Stack<double> B;

那么这个类模板有什么卵用呢?

书上提到了一个远古的数据结构,就是栈(不是

想一想栈这个东西确实用的多,把它弄成什么东西都能装的栈就不用去一个一个地去写了,这里给出一个比较棘手的关于字符串的栈:

template <class Type>
class Stack
{
private:
    enum {SIZE = 10};    // default size
    int stacksize;
    Type * items;       // 其实是任一类型的指针
    int top;            // index for top stack item
public:
    explicit Stack(int ss = SIZE);
    Stack(const Stack & st);
    ~Stack() { delete [] items; }
    bool isempty() { return top == 0; }
    bool isfull() { return top == stacksize; }
    bool push(const Type & item);   // add item to stack
    bool pop(Type & item);          // pop top into item
    Stack & operator=(const Stack & st);
};

template <class Type>
Stack<Type>::Stack(int ss) : stacksize(ss), top(0)
{
    items = new Type [stacksize];    //创建了任意类型的数组,同时用成员items去跟踪
}

template <class Type>
Stack<Type>::Stack(const Stack & st)
{
    stacksize = st.stacksize;
    top = st.top;
    items = new Type [stacksize];
    for (int i = 0; i < top; i++)
        items[i] = st.items[i];
}

template <class Type>
bool Stack<Type>::push(const Type & item)
{
    if (top < stacksize)
    {
        items[top++] = item;    //入栈操作:其实就是把items(此时items是一个指向字符串的指针数组)中的格子设成指针
        return true;            //指向被“压进”栈的字符串
    }
    else
        return false;
}

template <class Type>
bool Stack<Type>::pop(Type & item)
{
    if (top > 0)
    {
        item = items[--top];
        return true;
    }
    else
        return false;
}

template <class Type>
Stack<Type> & Stack<Type>::operator=(const Stack<Type> & st)
{
    if (this == &st)
        return *this;
    delete [] items;
    stacksize = st.stacksize;
    top = st.top;
    items = new Type [stacksize];
    for (int i = 0; i < top; i++)
        items[i] = st.items[i];
    return *this; 
}
// stkoptr1.cpp -- testing stack of pointers
#include <iostream>
#include <cstdlib>     // for rand(), srand()
#include <ctime>       // for time()
#include "stcktp1.h"
const int Num = 10;
int main()
{
    std::srand(std::time(0)); // randomize rand()
    std::cout << "Please enter stack size: ";
    int stacksize;
    std::cin >> stacksize;
// create an empty stack with stacksize slots
    Stack<const char *> st(stacksize); 

// in basket
    const char * in[Num] = {
            " 1: Hank Gilgamesh", " 2: Kiki Ishtar",
            " 3: Betty Rocker", " 4: Ian Flagranti",
            " 5: Wolfgang Kibble", " 6: Portia Koop",
            " 7: Joy Almondo", " 8: Xaverie Paprika",
            " 9: Juan Moore", "10: Misha Mache"
            };
 // out basket
    const char * out[Num];

    int processed = 0;
    int nextin = 0;
    while (processed < Num)
    {
        if (st.isempty())
            st.push(in[nextin++]);
        else if (st.isfull())
            st.pop(out[processed++]);
        else if (std::rand() % 2  && nextin < Num)   // 50-50 chance
            st.push(in[nextin++]);
        else
            st.pop(out[processed++]);
    }
    for (int i = 0; i < Num; i++)
        std::cout << out[i] << std::endl;

    std::cout << "Bye\n";
    // std::cin.get();
    // std::cin.get();
	return 0; 
}

而且转念一想,要有“适应多种数据类型”的特性的模块,不就是基类吗?因此基类通常可以设置为类模板

你比如,我想存两个类型未定的值,这时就可以用模板了:

#include <iostream>
#include <string>
template <class T1, class T2>
class Pair
{
private:
    T1 a;   
    T2 b;
public:
    T1 & first();
    T2 & second();
    T1 first() const { return a; }
    T2 second() const { return b; }
    Pair(const T1 & aval, const T2 & bval) : a(aval), b(bval) { }
    Pair() {}
};

template<class T1, class T2>
T1 & Pair<T1,T2>::first()
{
    return a;
}
template<class T1, class T2>
T2 & Pair<T1,T2>::second()
{
    return b;
}

int main()
{
    using std::cout;
    using std::endl;
    using std::string;
    Pair<string, int> ratings[4] =         //类比int x[4]
    {
        Pair<string, int>("The Purpled Duck", 5),           //注意这里要用Pair<string,int>来调用构造函数
        Pair<string, int>("Jaquie's Frisco Al Fresco", 4),
        Pair<string, int>("Cafe Souffle", 5),
        Pair<string, int>("Bertie's Eats", 3)
    };

    int joints = sizeof(ratings) / sizeof (Pair<string, int>);
    cout << "Rating:\t Eatery\n";
    for (int i = 0; i < joints; i++)
        cout << ratings[i].second() << ":\t "
             << ratings[i].first() << endl;
    cout << "Oops! Revised rating:\n";
    ratings[3].first() = "Bertie's Fab Eats";
    ratings[3].second() = 6;
    cout << ratings[3].second() << ":\t "
         << ratings[3].first() << endl;
   // std::cin.get();
   return 0; 
}

类模板除了和模板函数有什么隐式具体化,显示/隐式实例化之外,还有部分具体化,说白了就是在限制了模板的通用性,详情请看 C++ Primer Plus 583页。现在感觉暂时用不到….

 

成员模板

然鹅更牛皮的是,还有个东西叫成员模板,就是在模板类里面加载个模板类

// tempmemb.cpp -- template members
#include <iostream>
using std::cout;
using std::endl;

template <typename T>
class beta
{
private:
    template <typename V>  // nested template class member
    class hold
    {
    private:
        V val;
    public:
        hold(V v  = 0) : val(v) {}
        void show() const { cout << val << endl; }
        V Value() const { return val; }
    };
    hold<T> q;             // 未确定类型的模板对象
    hold<int> n;           // 确定了类型的模板对象
public:
    beta( T t, int i) : q(t), n(i) {}
    template<typename U>   // template method
    U blab(U u, T t) { return (n.Value() + q.Value()) * u / t; }  //返回值的类型由第一个参数决定
    void Show() const { q.show(); n.show();}
};

int main()
{
    beta<double> guy(3.5, 3);
    cout << "T was set to double\n";
    guy.Show();
    cout << "V was set to T, which is double, then V was set to int\n";
    cout << guy.blab(10, 2.3) << endl;
    cout << "U was set to int\n";
    cout << guy.blab(10.0, 2.3) << endl;
    cout << "U was set to double\n";
    cout << "Done\n";
    // std::cin.get();
    return 0; 
}

 其中不同颜色代表不同的数据类型

 

 

还没完,这个模板还可以当成参数传进去:

// tempparm.cpp � templates as parameters
#include <iostream>
#include "stacktp.h"

template <template <typename T> class Thing>    //在此例中是把stack模板传进去 template <class type>class stack
class Crab
{
private:
    Thing<int> s1;   //实例化为 stack<int> s1
    Thing<double> s2;   //实例化为 stack<double> s2
public:
    Crab() {};
    // assumes the thing class has push() and pop() members
    bool push(int a, double x) { return s1.push(a) && s2.push(x); }
    bool pop(int & a, double & x){ return s1.pop(a) && s2.pop(x); }
};
    
int main()
{
    using std::cout;
    using std::cin;
    using std::endl;
    Crab<Stack> nebula;
// Stack must match template <typename T> class thing   
    int ni;
    double nb;
    cout << "Enter int double pairs, such as 4 3.5 (0 0 to end):\n";
    while (cin>> ni >> nb && ni > 0 && nb > 0)
    {
        if (!nebula.push(ni, nb))
            break;
    }
   
    while (nebula.pop(ni, nb))
           cout << ni << ", " << nb << endl;
    cout << "Done.\n";
    // cin.get();
    // cin.get();
    return 0; 
}

很明显的看到了,这种模板之间的组合极大的增加了灵活性与代码的重用

 

 

模板类的友元

 

  • 非模板的友元
  • 约束友元模板,即友元的类型取决于类被实例化时的类型
  • 非约束的模板友元,即友元的所有具体化都是类的每一个具体化的友元

 

1.非模板的友元(非模板函数):

template <class T>
class Test
{
    friend void reprot(Test<T> &);
    //friend void reprot(Test &);   错误!Test对象只有特定的具体化
};

并且在友元函数的实现中也要给定参数:

void reprot(Test<int> &){
   /*code*/
}
void reprot(Test<double> &){
   /*code*/
}

看上去就是友元函数的重载不是吗?

 

2.约束模板友元函数(模板函数):

先声明模板函数,再在模板类里面声明为友元:

friend void counts<T>();
friend void report<>(Father<T> &);  //创建一个模板为Father<int>/<double>/<char>....的友元模板函数

完整:

// tmp2tmp.cpp -- template friends to a template class
#include <iostream>
using std::cout;
using std::endl;

// template prototypes
template <typename T> void counts();
template <typename T> void report(T &);

// template class
template <typename TT>
class HasFriendT
{
private:
    TT item;
    static int ct;
public:
    HasFriendT(const TT & i) : item(i) {ct++;}
    ~HasFriendT() { ct--; }
    friend void counts<TT>();
    friend void report<>(HasFriendT<TT> &);
};

template <typename T>
int HasFriendT<T>::ct = 0;

// template friend functions definitions
template <typename T>
void counts()
{
    cout << "template size: " << sizeof(HasFriendT<T>) << "; ";
    cout << "template counts(): " << HasFriendT<T>::ct << endl;
}

template <typename T>
void report(T & hf)
{
    cout << hf.item << endl;
}

int main()
{
    counts<int>();
    HasFriendT<int> hfi1(10);
    HasFriendT<int> hfi2(20);
    HasFriendT<double> hfdb(10.5);
    report(hfi1);  // generate report(HasFriendT<int> &)
    report(hfi2);  // generate report(HasFriendT<int> &)
    report(hfdb);  // generate report(HasFriendT<double> &)
    cout << "counts<int>() output:\n";
    counts<int>();
    cout << "counts<double>() output:\n";
    counts<double>();
    // std::cin.get();
    return 0; 
}

 

3.非约束模板的友元函数

// manyfrnd.cpp -- unbound template friend to a template class
#include <iostream>
using std::cout;
using std::endl;

template <typename T>
class ManyFriend
{
private:
    T item;
public:
    ManyFriend(const T & i) : item(i) {}
    template <typename C, typename D> friend void show2(C &, D &);   
};

template <typename C, typename D> void show2(C & c, D & d)
{
    cout << c.item << ", " << d.item << endl;
}

int main()
{
    ManyFriend<int> hfi1(10);
    ManyFriend<int> hfi2(20);
    ManyFriend<double> hfdb(10.5);
    cout << "hfi1, hfi2: ";
    show2(hfi1, hfi2);
    cout << "hfdb, hfi2: ";
    show2(hfdb, hfi2);
    // std::cin.get();
    return 0;
}

我们可以看出,非约束的模板友元函数可以随着传进函数的参数的类型而生成相应的模板,“模板函数”这个特点更加明显,不再依赖于模板类的具体类型。这让这个函数可以处理各种各样的数据。

反观上面的约束模板友元函数,它生成的具体模板仅于模板类有关,因此说是 “被约束的”,作用我想是增加类模板的灵活性。

 

构造一个类和声明函数的混淆

哈哈哈,高浩裕看出来的

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

class A{
    public:
        A(int x):a(x=0){}
        void printA(){
            cout<<"a="<<a<<endl;
        }
    private:
        int a;
};

int main(){
    A objA;
    objA.printA();
    return 0;
}

当代码是这样子时,过不了

但是当代码改一下变成:

A objA();

当只有这一句时过了,然鹅并不能调用成员函数,这就很蛋疼

但是为什么可以过呢?

这一句其实不是声明一个A类,而是声明一个函数,它没用参数,返回一个A类的对象!

正确代码:

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

class A{
    public:
        A(int x=0):a(x){}
        void printA(){
            cout<<"a="<<a<<endl;
        }
    private:
        int a;
};

int main(){
    A objA;
    objA.printA();
    return 0;
}

 

 

来自新世界:多重继承

先引入一个问题..

这时我们可以发现,创建一个“劳动者”A,再用“人”的指针去调用这个“劳动者”A 时会发现有两个“人”对象—-“主播”的“人” 和 “老师” 的 “人”

这时我们就要用强制转换来指明这个指针到底要指向谁:

Worker ed;
Human *pw1 = (Teacher *)&ed;
Human *pw2 = (Singer *)&ed;

这样就很蛋疼,因此我们有了虚基类:

在singer 和 teacher 类的继承部分加个virtual ,就行了,这样做会使 worker 类只继承一次 human 类。

当然这里相对的就要引进新的构造函数:

worker(const human &hu, string &na, string &num)
    : human(hu), teacher(hu,na), singer(hu,num){}

然鹅,当我们想要打印出某位劳动者的信息时,我们要怎么定义show()函数呢?

void worker::show()
{
    singer::show();
    teacher::show();
}

这样做会使human基类里面的show() 函数被调用了两次,因此应该进行模块化设计:

void human::data()const{
    cout << "name:" << name << endl;
}
void teacher::data()const{
    cout << "school:" << school << endl;
}
void singer::data()const{
    cout << "company" << company << endl;
}
void worker::data()const{
    singer::data();
    teacher::data();
}
void worker::show(){
    cout << "Category:" << endl;
    human::data();
    data();
}

这种模块化设计可以把上述的data设为私有函数,协助公有接口。

 

来自新世界:私有继承

Has-a 关系….

其实就是在private里面塞了其他类,但是他们之间又不是继承关系,假设 Student 类里面有一个 string name 成员,那么它的构造函数是:

Student(const char*str):name(str){}

C++要求在构建对象的其他部分前先构建继承对象的所有成员对象,假如不使用列表初始化,那么 C++ 将使用成员对象所属类的默认构造函数(注意初始化顺序与声明顺序相关)

这里引入一个私有继承,它能很好的体现出 has-a 的特性

私有继承

#include <iostream>
using namespace std;
class A{
    private:
        int Ai;
    public:
        A(int ai=0):Ai(ai){}
        void show(){
            cout << "now is A's show() method" << endl;
        }
};
class B{
    private:
        int Bi;
    public:
        B(int bi=1):Bi(bi){}
        void show(){
            cout << "now is B's show() method" << endl;
        }
};
class C:private A,private B{
    public:
        C(int a,int b):A(a),B(b){}
        void show(){
            A::show();
            B::show();
        }
};
int main(){
    C c(10, 20);
    c.show();
}

 

 

那么问题来了,我要怎么样访问基类对象(A,B)呢?

答案是使用强制转换:

const A & A_num() const
        {
            return (const A &) * this; //this是指向本对象的指针,*this是本对象再将其转换为基类的引用
        }

 

鶸断腕(八)

继承与动态内存分配

当基类使用了new进行动态内存分配时,基类的继承要注意进行相应的配合

1.在构造复制构造函数和重载运算符时,可以这样做:

#include<iostream>
using namespace std;
Son::Son(const Son &hs):Father(hs)
{
    style = new char[std::strlen(hs.style) + 1];
    std::strcpy(style, hs.style);
}
Father & Father::operator=(const Father &rs)
{
    if(this == &rs)
        return *this;
    delete[] label;     //把原来父类对象中的label指向的内存给删掉
    label = new char[std::strlen(hs.label) + 1];  //重新赋值label
    std::strcpy(label, rs.label);
    return *this;
}
Son & Son::operator=(const Son &hs)
{
    if(this == &hs)
        return *this;
    Father::operator=(hs); //调用父类的复制构造函数,复制父类的部分
                           //实际上是 *this = hs
    delete[] style;     //把原来父类对象中的label指向的内存给删掉
    style = new char[std::strlen(hs.style) + 1];  //重新赋值label
    std::strcpy(style, hs.style);
    return *this;
}

2.友元函数

std::ostream & operator<<(std::ostream &os,const Son&hs){
    os << (const Father &)hs;   //将派生类转化为基类,再利用基类的友元函数来打印派生类中的基类部分
    os << "Style:" << hs.style << endl;
    return os;
}

这里也体现出继承的核心思想:能充分地利用基类的价值

 

各种各样的排序(持续更新)

1.冒泡排序

 

void BubbleSort(int array[], int n)
{
    int i, j, k;
    for(i=0; i<n-1; i++)
        for(j=0; j<n-1-i; j++)
        {
            if(array[j]>array[j+1])
            {
                k=array[j];
                array[j]=array[j+1];
                array[j+1]=k;
            }
        }
}

思想很明确,就是遇到比自己小的就立刻交换,注意此时比较大的那个(之前在比它小的前面)被转移到了后一位,那么j++后指向的对象就是这个比较大的,如果不是那么 j++ 指向的就是比 j++ 操作前指向的个体大的那个数,从而实现“冒泡”。

 

 

2.选择排序(没用)

 

void selectSort(int array[], int n)
{
    int i, j ,min ,k;
    for( i=0; i<n-1; i++)
    {
        min=i; //每趟排序最小值先等于第一个数,遍历剩下的数
        for( j=i+1; j<n; j++) //从i下一个数开始检查
        {
            if(array[min]>array[j])
            {
                min=j;
            }
        }
        if(min!=i)
        {
            k=array[min];
            array[min]=array[i];
            array[i]=k;
        }
    }
}

每次都要遍历一次数组,找到最小的,如果不是原来的就进行交换。

 

 

3.插入排序

 

void insertSort(int array[], int n)
{
    int i,j,temp;
    for( i=1;i<n;i++)
    {
        if(array[i]<array[i-1])  //确定这个数是要进行排序的
        {
            temp=array[i];          //把它提取出来
            for( j=i;j-1>=0 && array[j-1]>temp ;j--)  //如果这个数比前面的要小,就把提取出来的数的位置给它
            {
                array[j]=array[j-1];     //原来的位置被覆盖,一次便利到最后总会出现两个相同的值
            }
            array[j]=temp;  //插入操作
        }
    }
}

 

 

 

4.归并排序

 

void merging(int *list1, int list1_size, int *list2,  int list2_size)  //归并过程
{
    int i=0, j=0, k=0, m=0;      //注意这里的i的作用域在整个函数中
    int temp[1000];

    while(i < list1_size && j < list2_size)     //在两个数组中轮流选择,谁小谁上
    {
        if(list1[i]<list2[j])   
        {
            temp[k++] = list1[i++];
        }
        else
        {
            temp[k++] = list2[j++];
        }
    }                                    //事实上经过这样的选择融合后必定有一个数组是被选完的
    
    //说白了假如 list1或2 数组中如果有剩下的,那么说明就是它剩余的是比前面的数组都大的,直接加入就可以了

    while(i<list1_size)         //此时i不再是零而是在上面经过选择进入 temp 数组(这个过程)后指向 list1 的末尾(如果i不等于末尾的话)
    {
        temp[k++] = list1[i++];  //把 list1 数组中剩余的数复制进去 temp 数组中
    }
    while(j<list2_size)         //此时j不再是零而是在上面经过选择进入 temp 数组(这个过程)后指向 list2 的末尾(如果j不等于末尾的话)
    {
        temp[k++] = list2[j++];  //把 list2 数组中剩余的数复制进去 temp 数组中
    }

    for(m=0; m < (list1_size+list2_size); m++)
    {
        list1[m]=temp[m];
    }
}
 
void mergeSort(int array[], int n)
{
    if(n>1)             //判断是否返回的标准
    {
        int *list1 = array;
        int list1_size = n/2;
        int *list2 = array + n/2;
        int list2_size = n-list1_size;

        mergeSort(list1, list1_size);  //持续递归直到list数组只剩下两个
        mergeSort(list2, list2_size);  //持续递归直到list数组只剩下两个

        merging(list1, list1_size, list2, list2_size);   //对list 1 或 2 数组进行融合
    }
}

 

 

 

5.快排

 

//接口调整
void adjust_quicksort(int k[],int n)  
{  
   quicksort(k,0,n-1);  
}  
void quicksort(int a[], int left, int right)  
{  
    int i,j,t,temp;  
    if(left>right)   //(递归过程先写结束条件)
       return;  

    temp=a[left]; //temp中存的就是基准数  
    i=left;  
    j=right;  
    while(i!=j)  
    {  
                   //顺序很重要,要先从右边开始找(最后交换基准时换过去的数要保证比基准小,因为基准                               
                   //选取数组第一个数,在小数堆中) 
                   while(a[j]>=temp && i<j)  
                            j--;  
                   //再找右边的  
                   while(a[i]<=temp && i<j)  
                            i++;  
                   //交换两个数在数组中的位置  
                   if(i<j)  
                   {  
                            t=a[i];  
                            a[i]=a[j];  
                            a[j]=t;  
                   }  
    }  
    //最终将基准数归位 (之前已经temp=a[left]过了,交换只需要再进行两步)
    a[left]=a[i];  
    a[i]=temp;  

    quicksort(left,i-1);//继续处理左边的,这里是一个递归的过程  
    quicksort(i+1,right);//继续处理右边的 ,这里是一个递归的过程  
}  

 

 

6.桶排序

这个很简单没什么好说的 🙂

int main()
{
    int a[11],i,j,t;
    for(i=0;i<=10;i++)
        a[i]=0;  //初始化为0

    for(i=1;i<=5;i++)  //循环读入5个数
    {
        scanf("%d",&t);  //把每一个数读到变量t中
        a[t]++;  //进行计数(核心行)
    }

    for(i=0;i<=10;i++)  //依次判断a[0]~a[10]
        for(j=1;j<=a[i];j++)  //出现了几次就打印几次
            printf("%d ",i);

    return 0;
}

 

 

 

7.堆排序

 

//注意数组第一个是不设值的,即int a[]={0,899,5,58,62,14,17};
void heapSort(int array[], int n)
{
    int i;
    for (i=n/2;i>0;i--)               //建立最大堆,i为从右到左第一个非子叶节点
    {
        HeapAdjust(array,i,n);    //从下向上,从右向左调整
    }
    for( i=n;i>1;i--)       //开始进行排序
    {
        swap(array, 1, i);      //交换最大的和最后一个子叶点,实际上就是把最大的(堆顶)放在最后
        HeapAdjust(array, 1, i-1);//再次调整最大堆,从上到下,从左向右调整,i-1是对被调整到最后的最大值进行出堆操作
    
}
void HeapAdjust(int array[], int s, int n )
{
    int i,temp;
    temp = array[s];        
                                //下面的注释大都在描述第一次调整时的过程:)
    for(i=2*s;i<=n;i*=2)        //i为从右到左选择的第一个非子叶点的节点,(当它在倒数第二层乘了二后变为子叶点)(通常在倒数第三层后才会进行循环)
    {
        if(i<n && array[i]<array[i+1]) //不会越界因为 i 要小于节点总数 n 才行,此步骤为两个子叶点进行比较(前提是如果有两个)
        {
            i++;                  //如果右大于左,则把i设为指向右节点
        }
        if(temp>=array[i])      //如果父节点比两个子节点中最大的那个都要大,那么退出循环,注意这里的父节点是指循环第一次所选定的父节点
        {                       //今后的比较都是用这个temp值来比较
            break;
        }
        array[s]=array[i];  //否则将父节点的内容变成两个子节点中最大的那个,注意这里的交换只是数组内容的顶替
        s=i;    //更新指向原父节点的指针s的值,将其值变成(某)两个子节点中最大的那个的编号(i)的值
                //在下一轮循环中要找的子节点的编号是由s提供的,实际上s可以理解为一种指针,s永远指向相对的父节点
                //事实上(也可以注意到)某两个个节点中的值相同并不重要因为如果一开始指定的“父节点”原值已经被记录在 temp 中
                //如果这个值比剩下的两个节点都要大,就把它塞进去
                //如果还要再调整,即没用进入break模块,那么就把此时s指向的节点(相对的父节点)的值换成那个最大子节点的值
                //同时再次更新s指针,如果到底了就退出循环
    }
    //此时s已经指向一个子叶节点或者相对的父节点,而此时这个点的值还是原来某两个子节点中最大的那个的值,因此需要更新
    array[s]=temp; 
    //可以发现交换过程中父节点总是和相差最大的子节点进行“交换”行为
}
void swap(int array[], int i, int j)
{
    int temp;

    temp=array[i];
    array[i]=array[j];
    array[j]=temp;
}

思考了很久,事实上堆排序利用的就是最大堆的特性:堆顶的最大值,每次对堆顶的数字进行出堆操作同时放到数组的最后面。而关键的我猛然发现这个数组里面的“键值”,就是x[2]里面的2,可以理解为一种属性(废话),而把这种属性抽象出来就是一种“指针”。可以利用这一点对值进行相关的修改(废话)。像在这个堆排序里面就是这样子,设置了两个“指针”,i和s,i由s生,s又可以变成i,i永远指向s的子节点。

总之很牛皮。

 

 

8.希尔排序:

先粘贴上去,下次再想

//在插入排序基础上修改得到希尔排序
void SheelSort( int array[], int n)
{
    int i,j,temp;
    int gap=n; //~~~~~~~~~~~~~~~~~~~~~
    do{
        gap=gap/3+1;  //~~~~~~~~~~~~~~~~~~
        for( i=gap;i<n;i++ )
        {
            if(array[i]<array[i-gap])
            {
                temp=array[i];
                for( j=i-gap;array[j]>temp;j-=gap)
                {
                    array[j+gap]=array[j];
                }
                array[j+gap]=temp;
            }
        }
    }while(gap>1);  //~~~~~~~~~~~~~~~~~~~~~~

}

 

鶸断腕(七)

虚函数的复习

当子类要重新定义父类的函数时,为了让基类指针能够识别自己要调用的不是基类的方法,而是子类的方法,我们引进了虚函数,大致就是在父类的要重定义的方法前加个virtual。然鹅这不仅仅是加个标签这么简单,这涉及到了动态联编和静态联编,通过加个virtual来让编译器对某个函数进行跟踪,具体就是给每个对象添加一个隐藏成员,这个成员保存了一个指向函数地址数组的地址。如图:

而其中每个对象都会有这样的一个成员:vptr ——专门存放着自己类对应的虚函数表的地址。比如设 A objA里面的vptr的值就是01。

很明显只要开了虚函数就会带来一定的运行成本:

1.对象增大,多了一张表

2.每个类编译器都会创造一个虚函数地址表(只记录虚函数)

3.每个函数调用都要去找一下这个函数的地址(如果更新就用新地址记录的那个函数)

注意的点:

1.析构函数理应是虚函数,当出现如下情况时:

Father *p = new Son;
/* 
  代码...
*/
delete p;

这样做就会导致 p 调用父类的析构函数而没有调用子类的析构函数,从而子类带来的空间将无法释放,这时如果设成虚函数,那么p将先调用子类的虚构函数,再调用父类的析构函数。

2.虚函数重新定义不等于重载!重新定义意味着虚函数表的覆盖,子类和父类的虚函数的声明应该一样,除了返回的参数允许修改为指向派生类的指针或者引用。

鶸断腕(六)

关于数组和类….

想要声明一个类的数组,然后输入数据进行初始化,怎么办?

直接 ClassName  a[i]  和  a[i](balbla) 是不行的,因为没有这样的构造函数,因此应该

Class[i]={baseMan(Name, Age, Height, Weight, Sex)};

这样子。当然注意到这里是生成了一个“无名氏”,因为是用了构造函数并且赋给class[i],因此当涉及内存管理时要进行深度复制。

如果不想麻烦写构造函数还可以这样子操作:

#include "baseMan.cpp"
using namespace std;
int main(){
    string Name;
    int Age;
    double Height;
    double Weight;
    string Sex;
    baseMan *Class[3];
    for (int i = 0; i <3;i++){
        cin >> Name >> Age >> Height >> Weight >> Sex;
        Class[i] = new baseMan;
        bool result = Class[i]->change_p(Name, Age, Height, Weight, Sex);
        if(result){
            cout << "change successfully" << endl;
        }
    }
    for (int i = 0; i <3;i++){
        Class[i]->show();
    }
   
    /*int i;
    cout << "the one you want to change:";
    cin >> i;
    Class[i].change(Class[i], "rong", 18, 178.2, 70.2, "man");*/
}

利用指针进行访问类中的函数,而且还可以有助于日后多态化的实现

鶸断腕(五)

发现的一些奇怪的错误

总的来说就是默认值重复的问题,就是在给类的声明文件(头文件)里面的公有函数写了默认值以后再在方法实现的文件中写函数内容时,在那里假如又写了一次默认值的话,就会报错,事实上是这就是默认值重复造成的错误。

//在头文件中
public:
      baseMan(const string &na = "none", int a = 0, double h = 0, double w = 0, string s = "null");

//在方法实现文件中
baseMan::baseMan(const string &na,int a , double h, double w, string s):name(na),age(a),height(h),weight(w),sex(s){
    std::cout << "a man has been created." << std::endl;
}
//这里不用再写一次默认值!!