Posts Tagged C++
决定暂时放一放CBigInt，顺便公布下部分SRC
Posted by kingsamchen in PROGRAMMING on 2010 年 06 月 17 日
RT
一个人写这个写的有点累了，目前的进度在Subtract。由于很多细节让我感到有点累～所以过几天再写～
可能明天先着手写ID Fighter或者做CLRS上的习题也说不定
总之，看情况吧～
刚才因为数据表示而导致中间0个数的问题，感谢D大给予帮助～
由于实现的SRC有点多，所以不贴，给出下载～只贴声明部分
欢迎感兴趣的人一同探讨研究～
Read the rest of this entry »
C++类中成员的一个“Feature”
Posted by kingsamchen in PROGRAMMING on 2010 年 06 月 17 日
这其实是我昨晚在写CBigInt的operator+的时候碰到的一个比较郁闷的问题
先看一段代码：
#include <string>
#include <iostream>
using namespace std;
int main()
{
T c;
cout<<c.Put(); // first position
c.a(); // second position
return 0;
}
class T
{
public:
int Put()
{
T t;
return t.a(); // look at here
}
private:
int a()
{
m_n = 5;
return m_n;
}
int m_n;
};
这段代码能正常运行么？答案显然是否定的
但是，第一处的代码是没问题的，第二处才有问题。
按照个人以往对于private/protected的理解是，在类内部可见，外部不可见。即，外部的类对象不能直接调用private或protected类型的成员。按照这一规定，很显然，第二处直接调用私有成员函数是不合法的，因为编译器会给错。
Read the rest of this entry »
在C/C++中使用Unicode字符串
Posted by kingsamchen in PROGRAMMING on 2010 年 04 月 10 日
KC曾经写过这方面的文章，但是当时只是浅尝辄止，而且似乎“宣传”的效果也不怎么好，所以这次有必要进行一次深入的探讨。
1.ANSI(MBCS)和UNICODE的前世今生
ANSI是最先采用的字符集，以1Byte表示一个字符，后来为了表示含有音标的字母而产生了变种系列。但是这种字符集最大的问题是，无法表示诸如汉字、日本这样的“大字符”
于是，当初设计ANSI的那批人（瞎猜的，出错勿怪）很天才的设计了一种新的字符集，即后来的MBCS（MBCS中最常用也最常见的是DBCS）。MBCS利用1Byte表示原有的那些字符，并利用2Bytes或更高来表示大字符，于是乎，就可以解决原先的问题了。
但是，这个看似高明的方法并不高明。因为某些字符是1Byte，而某些则是2Bytes或更高。程序员在遍历字符串的时候，必须检查下一个字节，才知道正在处理的是小字符还是大字符。这对程序员和项目经理来说，无疑是一场噩梦。
内牛满面的科学家通过不断的猜想，建模，设计，最终设计产生了目前最广泛使用的UNICODE字符集。
题外话：这里我们要感谢Apple、Xerox、Compaq、IBM、Microsoft、Oracle.etc，否则我们这批Coder也要继续内牛满面。
UNICODE字符集中，每个字符都是用2Bytes来表示，包括’\0′。统一的规范的结果则是效率的提升。
更让人欣喜的是，UNICODE可以在原来拥有超强语言字符支持的基础上，引入新的文字符号，包括标点符号、数学符号和技术符号等。
既然1F的swd同学指出来了，那么这里我们就在“深入”一点
事实上，默认的UNICODE指的是UTF-16，并且也存在其他表示字符的UTF标准。
UTF-8.UTF-8将一些字符编码为1Byte，一些为2Bytes，一些为3Bytes，而一些甚至可以达到4Bytes。值在0×0080以下的字符压缩为1Byte，这对US使用的字符非常合适。而0×0080到0x07FF之间的字符转换2Bytes，常用于欧洲和中东地区的字符。0×0080以上的字符为3Bytes，用于东亚字符，而最后把代理类型设置成4Bytes。但是当存在大量0×0080字符时，效率不如UTF-16高，好处是可以和原有的ANSI兼容
UTF-32是另一种标准。它将每个字符编码为4Bytes，除了程序内部之间使用之外，MS用的不多。
AutorunLoadViewer V1 Beta
Posted by kingsamchen in PROGRAMMING on 2010 年 02 月 18 日
从去年暑假开始折腾，一直折腾到现在，终于把他给Beta了，HIAHIA
之前交给Lieo的那份是Demo的，而目前的这份Beta多了两个功能，显示Item的图标和公司信息。
不过也就为了增加这两个功能，也着实浪费了我一点时间，主要是在增加功能的前提下，不能破坏原有的架构（其实就是增加了一个CQueryExeInfo的类罢了）。
谢天谢地，这玩意儿终于让我KO了~终于可以对ARV实行烂尾手段了囧…
似乎上次Lieo没有公开这部分的SRC。厄，不错没关系，自己看好了，鉴于篇幅原因（数了下，不包括.h的话，大约在1700±100 Rows左右），只放下新增加的代码。
/**************************************************
** Project:AutorunLoadViewer
** File:QueryExeInfo.h
** Edition:v1.0.0 Beta
** Coder:KingsamChen [MDSA Group]
** Last Modify:2010-2-18
**************************************************/
#pragma once
#pragma comment(lib, "version.lib")
class CQueryExeInfo : public CObject
{
public:
CQueryExeInfo();
virtual ~CQueryExeInfo();
HICON QueryExeIcon(LPCTSTR lpszExePath);
static void FreeIconBuffer(HICON hIcon);
void QueryExeCompanyName(LPCTSTR lpszExePath, CString& sCompanyName);
protected:
DWORD GetExeVersionInfo(LPCTSTR lpszExePath);
void FreeVersionBuffer();
protected:
LPVOID m_lpVersionBuffer;
LPVOID m_szCompanyName;
};
逆序对以及其算法设计
Posted by kingsamchen in PROGRAMMING on 2010 年 02 月 13 日
同样的，这也是来自CLRS的一道题目，但是KC个人觉得这道题很有意思，所以同样的独立来写~
首先，我们要知道什么是逆序对。逆序对的定义如下：设A[1...n]是一个包含n个不同个元素的数组。如果在i< j的情况下，有A[i]>A[j]，则(i,j)就称之为A中的一个逆序对（Inversion）
逆序对有很多用处，一个最明显的作用就是，一个数列中逆序队的数量和插入排序法所需要的时间是成正比的。而在某些情况下，对小数组采用插入排序法是一个比较好的选择。（在CLRS中，有关于在归并排序中利用插入排序对小数组进行排序的题目，但是由于题目最后两道题太难，做不出来，所以没有公布。）
那么，如何设计算法来求一个数列中的逆序对个数呢？
很自然，我们可以想到利用两次循环，逐一的比较。但是，这个算法的时间复杂度是[latex]O\left(n^{2} \right)[/latex]，这是一个很烂的情况。
而CLRS中的要求则是算法的时间复杂度应该在[latex]O\left(nlog_{2}^{n} \right)[/latex]，并且给出了提示信息：修改归并排序法。
我们回忆下归并排序法的模型，不难发现，和目前这个求逆序对的模型具有惊人的相似。
在合并中，左边的逆序对数量加上右边的逆序对数量，则是一个整体的逆序对数量。
Read the rest of this entry »
CLRS Exercise Chapter 2 (二)
Posted by kingsamchen in PROGRAMMING on 2010 年 02 月 10 日
这里只有一道题，不过在CLRS上打着*号，所以感觉单独分离出来讨论比较好~
题目描述：请给出一个时间复杂度为[latex]O\left(nlog_{2}^{n} \right )[/latex]的算法，使之能够在给定的一个由n个元素构成的集合S和另一个整数x时，判断出S中是否存在两个元素，使其和等于X。如果存在，则输出true，否则为false
自己想过几个算法，第一个时间复杂度没达到要求（但是经过修改之后，最后还是可以从理论上解决了……），后面几个中间出了些问题，最后回顾快速排序法的实现时，偶然想到了一个。
先说说简单的那个好了。
我们可以做如下判断：在一个已排序的数列中，如果存在两个数的和为一个给定整数（不考虑多对情况），那么其他两个数的和必然大于或小于给定的数。
而即使在多对的情况下，去掉那些相等的数对，也同样成立
类似QS，我们可以利用两个指向头尾的游标指针，相向遍历。
Read the rest of this entry »
CLRS Exercise Chapter 2 (一)
Posted by kingsamchen in PROGRAMMING on 2010 年 02 月 09 日
KC最近开始发愤图强了，这次是认真的，所以连CLRS后面的习题都开始认真做了（小部分不太有意思的可能就不做了……），并且决定每次都把结果写到Blog上，一来可以督促自己，二来可以和大家分享&探讨~
2.3.3 利用数学归纳法证明：当n是2的整数次幂时，对于递归式
[latex]T\left ( n \right )=\begin{cases}
2 & \mbox{if }n\mbox{ = 2} \\
2T\left ( \frac{n}{2} \right )+n & \mbox{if }n = 2^{k}, k>1
\end{cases}[/latex]
的解为[latex]T\left(n \right )=nlogn~~~~\left(define~~logn = log_{2}^{n} \right )[/latex]
很明显，要证明的式子本身具有递推性，所以
[latex]\textcircled{1}\quad when\,n=2,\;left=T\left(2 \right )=2 \\
~~~~~~~~~~~~right=T\left(2 \right )=2\cdot log2=2\cdot 1=2 \\
~~~~~~~~~~~~left=right~~~~\therefore proved~out \\
\,\textcircled{2}\quad when~n=2^{k},k>1,~assume~T\left(n \right )=nlogn~is~correct~~then \\
~~~~~~~~~~~~left=T\left(n \right )=2T\left(\frac{n}{2} \right )+n=2\cdot \frac{n}{2}log^{\frac{n}{2}}+n \\
~~~~~~~~~~~~~~~~~=nlog^{\frac{n}{2}}+nlog2=nlogn=right \\
~~~~~~~\therefore Proved~out~too \\
\,For~~\textcircled{1}and\textcircled{2},the~whole~inductive~proof~is~correct
[/latex]
Read the rest of this entry »
CTray for MFC v1.0.0 Final
Posted by kingsamchen in PROGRAMMING on 2010 年 01 月 30 日
在以前的CTray的基础上改的，适用于以MFC为框架的工程。
增加了BallonTip的功能，重写了部分代码，并且最重要的是，改变了最初通过重写WinProc来实现托盘重建的方法。取而代之的是利用ON_REGISTER消息映射。但是由此产生的缺点就是，在CTray中增加了一个static变量保存任务栏重建消息。
仍然保存了原有的Tray消息处理模式，即在CWnd的子类中，转发消息到CTray的OnTrayProc。为什么要这么做呢？原因很简单。从软件工程和设计角度来说，各个类之间具有一定的独立性，能够进行模块化分离，即属于CTray部分的内容应独立从属于CTray。 连锁性太强的设计很容易代码变成spaghetti。虽然很多人不承认，但事实上，VB6的确是典型的反面教材……
虽然在CTray中Subclass窗体的消息可以避免使用MessageMap，但是会破坏原有的架构。所以才使用上述方法。
Read the rest of this entry »
菱形字符输出游戏
Posted by kingsamchen in PROGRAMMING on 2010 年 01 月 14 日
从某处发现的一个比较有意思的游戏，题目如下：
输入一个奇数n，输出对角线长为n的实心或者空心的菱形图案
如当n=5时，有：
*
***
*****
***
*
一番思索之后，偶建立了一个一般模型，即，定位每一行的第一个输出点和输出长度既可以确定这行的输出序列。由于上下对称，所以输出长度用输出行和横对称轴的长度差的绝对值表示
确定的方法主要是将菱形分割成四个全等三角形，利用竖对称轴所在点求出起始输出点。
可以达到如图效果：
Binary_Clock源代码导读
Posted by kingsamchen in PROGRAMMING on 2010 年 01 月 10 日
事先声明，此程序并非我所写，而是来自一位叫做透明de面具的尹大牛。之所以用这个程序来作为KC源代码导读系列的奠基性文章，主要有两个原因：
一是大尹一直是KC偶崇拜的一只大牛，既谓之大牛，其代码必有过人之处。其二是大尹从事C++&WTL开发，而KC从事（似乎这里言之尚早）C++&MFC开发，由于WTL和MFC的相似性，代码组织上容易理解。
不多说，直入主题！
Binary_Clock的文件组织相对有点复杂（WTL再怎么简化也不可能把C++弄成VB6那种状态），其目录下 主要有以下文件： \stdafx.h \stdafx.cpp // 用过MFC的人对上面两个文件肯定是再熟悉不过了 \resource.h // 资源定义文件，里面定义了大量控件等资源ID \Binary_Clock.h // 主程序头文件，很高兴，这个程序中，这个文件是空的≡ω≡ \Binary_Clock.cpp // 主程序实现文件，主要用于启动程序，创建并启动窗体及其循环 \MainDlg.h // 窗体的头文件 \MainDlg.cpp // 窗体代码实现文件，这里是重点了
我们先看stdafx.h，里面有一行很值得关注
extern CAppModule _Module;
和MFC一样，WTL同样是由一个完整的全局对象引导启动。一个应用程序就是一个类对象。不过不同的是，MFC的这行代码出现在主程序的h文件中，而且全局对象的名字一直叫做theApp
Read the rest of this entry »
LICENCE
COMMENTS