c++日记

积累知识，慢慢沉淀

1.  char 转 wchar_t*

const WCHAR* g_strMsg = L"登录失败，请重试！";//message send to screen of the result

wchar_t* wchMsg;

char chMsg[100];
sprintf(chMsg ,"登录失败，原因：用户PIN码错误(%d)，错误%d次将锁定该用户5分钟！",nThis,nAlltime);
int n = MultiByteToWideChar(CP_ACP,MB_PRECOMPOSED,chMsg,-1,NULL,0);
wchMsg = new wchar_t[n];
MultiByteToWideChar(CP_ACP,MB_PRECOMPOSED,chMsg,-1,wchMsg,n);
g_strMsg = wchMsg;

可以将char转换为wchar_t*的。
Write time： 2014.02.25

2.数组

 1）数组初始化必须指明大小如： int arr[10];
      其实arr相当于一个常量指针，在传递给一个函数的时候必须将大小（10）作为附加参数传递。
  2）如果数组大小未知，必须显示的声明一个指针，用动态内存来分配空间：new []
      int *arr = new int[n];但是不要忘记了 delete[] arr;不然会造成内存泄露。

Write time： 2014.02.28
     

3.函数模板    

4.类模板

5.函数对象

eg:

#include <string>
#include <vector>
using namespace std;
//Write time:2014.03.04
//By:zhengxianle

//Generic findMax,with a function object,Version 1.0
//Precondition: a.size() > 0.
template <typename Object , typename Comparator>
const Object & findMax(const vector<Object>&arr,Comparator cmp)
{
    int maxIndex = 0;
    for(int i = 0 ; i < arr.size() ; i++)
    {
        if(cmp.isLessThan(arr[maxIndex],arr[i]))
            maxIndex = i;
    }
    return arr[maxIndex];
}

class CaseInsensitiveCompare
{
public:
    bool isLessThan(const string &lhs,const string &rhs) const
    {
        return stricmp(lhs.c_str(),rhs.c_str()) < 0 ;
    }
};
void main()
{
    vector<string> arr(3);
    arr[0] = "ZEBRA";
    arr[1] = "alligator";
    arr[2] = "crocodole";
    cout<<findMax(arr,CaseInsensitiveCompare())<<endl;

}

The result is:ZEBRA

6.算法分析

    1）运行时间
         1.1一般法则
             法则1：for循环     一个for循环的运行时间至多是该for循环内语句（包括测试）的运行时间乘以迭代的次数。
             法则2：嵌套循环  从里向外分析这些循环。在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有循环的大小的乘积。
                        eg：时间O（N²）：
                        

for(int i = 0; i < n ; i++ )
     for(int j = 0; j < n ; j++ )
         k++;

             法则3：顺序语句   将各个语句的运行时间求和即可。
                       如果一个为O（N），另一个为O(N²).则总时间复杂度为O（N²）！
             法则4：if/else语句 具体问题具体分析，但一般是if分支或者else分支时间最长的一个。

    2）最大子序列和问题
         给定整数A₁ ,A₂ ,...,A_N    （可能有负数），求Σ_k=i^j A_k  的最大值。

        下面给的是最优解：

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

//Write time:2014.03.14
//By:zhengxianle
//时间复杂度为：O（N） 一次for循环！
int maxSubSum(const vector<int> &a )
{
    int nMaxSum = 0, nThisSum = 0;
    int nBegin = 0, nEnd = 0, nExchange = 0;

    for( int nThis = 0; nThis < a.size() ; nThis++ )
    {
        nThisSum += a[nThis];
        if( nThisSum > nMaxSum )
        {
            nMaxSum = nThisSum ;
            nBegin = nExchange + 1;
            nEnd = nThis + 1;
        }
        else if( nThisSum < 0 )
        {
            nThisSum = 0;
            nExchange = nThis + 1;
        }
    }

    cout<<"Begin is: " <<nBegin <<" End is: " <<nEnd <<endl;

    return nMaxSum;
}
int main()
{
    vector<int> vData;

    //容器放入数据
    vData.push_back(-9);
    vData.push_back(3);
    vData.push_back(7);
    vData.push_back(1);
    vData.push_back(-5);
    vData.push_back(6);
    vData.push_back(-4);
    vData.push_back(-3);
    vData.push_back(5);
    vData.push_back(-6);
    vData.push_back(9);

    //求最大子序列和
    cout<<maxSubSum(vData)<<endl;

    return 0;
}

   3)运行时间中的对数

      1、二分搜索 O(log N)
           给定一个整数X和整数A₀,A₁,...,A_N,后者已经预先排序并在内存中，求下标 i 是的A_i = X，如果X不在数据中，则返回 i =  -1.

//Write time:2014.03.17
//By:zhengxianle
//二分搜索法（已排序）,时间复杂度：O(log N)
template <typename DataType>
int binaryFind(const vector<DataType> &a, const DataType &value)
{
    int low = 0, hight = a.size() - 1;

    while(low <= hight)
    {
        int mid = (low + hight) / 2;

        if(a[mid] < value)
        {
            low = mid + 1;
        }
        else if(a[mid] > value)
        {
            hight = mid - 1;
        }
        else
            return mid;
    }

    return -1;
}
int main()
{
    vector<int> a;
    a.push_back(10);
    a.push_back(11);
    a.push_back(12);
    a.push_back(13);
    a.push_back(14);
    a.push_back(15);
    a.push_back(16);
    a.push_back(17);
    a.push_back(18);

    cout<<"The location is at:"<<binaryFind(a,16)<<endl;
    //Result is 6
    return 0;
}

      2、欧几里得算法 O(log N)
            两个整数的最大公约数（gcd）是同时整除二者的最大整数。gcd（50,15） = 5 ，gcd（M,N），假设M >= N。

#include <iostream>
#include <string>
#include <vector>
using namespace std;
//Write time: 2014.03.17
//By :zhengxianle
//欧几里得算法：计算最大公约数
long gcd( long m , long n)
{
    while( n != 0 )
    {
        long ex = m % n;
        m = n;
        n = ex ;
    }
    return m;
}
int main ()
{
    cout<<gcd(50,15)<<endl;
    //The result is : 5
    return 0;
}

      3、幂运算 O(log N)
           

#include <iostream>
#include <string>
#include <vector>
#include <time.h>
using namespace std;

//Write time: 2014.03.17
//By :zhengxianle
//幂运算：最少次数的乘法
bool isEven(const int power)
{
    return power % 2 == 0 ? true : false ;
}

long double pow(long double x,int power)
{
    if(power < 0)
    {
        return 0;
    }
    else if(0 == power)
    {
        return 1;
    }
    else if(1 == power)
    {
        return x;
    }
    if(isEven(power))
    {
        return pow(x * x, power / 2);
    }
    else
    {
        return pow(x * x ,(power - 1) / 2) * x ;
    }
}
int main ()
{
    long x = 0;
    int power = 0;
    cin>>x>>power;
    cout<<"The "<<x<<"^ "<<power<<" is:"<<pow(x,power)<<endl;
    return 0;
}