程序描绘人生

posted @ 2008-05-26 10:14 胡满超阅读(1590) | 评论 (3) | 编辑收藏

有一个单链表，其中可能有一个环，也就是某个节点的next指向的是链表中在它之前的节点，这样在链表的尾部形成一环。

问题：

1、如何判断一个链表是不是这类链表？
2、如果链表为存在环，如何找到环的入口点？

解答：

一、判断链表是否存在环，办法为：

设置两个指针(fast, slow)，初始值都指向头，slow每次前进一步，fast每次前进二步，如果链表存在环，则fast必定先进入环，而slow后进入环，两个指针必定相遇。(当然，fast先行头到尾部为NULL，则为无环链表)程序如下：

bool IsExitsLoop(slist *head)
{
    slist *slow = head, *fast = head;

    while ( fast && fast->next )
    {
        slow = slow->next;
        fast = fast->next->next;
        if ( slow == fast ) break;
    }

    return !(fast == NULL || fast->next == NULL);
}

二、找到环的入口点

当fast若与slow相遇时，slow肯定没有走遍历完链表，而fast已经在环内循环了n圈(1<=n)。假设slow走了s步，则fast走了2s步（fast步数还等于s 加上在环上多转的n圈），设环长为r，则：

2s = s + nr
s= nr

设整个链表长L，入口环与相遇点距离为x，起点到环入口点的距离为a。
a + x = nr
a + x = (n – 1)r +r = (n-1)r + L - a
a = (n-1)r + (L – a – x)

(L – a – x)为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。程序描述如下：

slist* FindLoopPort(slist *head)
{
    slist *slow = head, *fast = head;

    while ( fast && fast->next )
    {
        slow = slow->next;
        fast = fast->next->next;
        if ( slow == fast ) break;
    }

    if (fast == NULL || fast->next == NULL)
        return NULL;

    slow = head;
    while (slow != fast)
    {
         slow = slow->next;
         fast = fast->next;
    }

    return slow;
}

扩展问题：

判断两个单链表是否相交，如果相交，给出相交的第一个点（两个链表都不存在环）。

比较好的方法有两个：

一、将其中一个链表首尾相连，检测另外一个链表是否存在环，如果存在，则两个链表相交，而检测出来的依赖环入口即为相交的第一个点。

二、如果两个链表相交，那个两个链表从相交点到链表结束都是相同的节点，我们可以先遍历一个链表，直到尾部，再遍历另外一个链表，如果也可以走到同样的结尾点，则两个链表相交。

这时我们记下两个链表length，再遍历一次，长链表节点先出发前进(lengthMax-lengthMin)步，之后两个链表同时前进，每次一步，相遇的第一点即为两个链表相交的第一个点。

posted @ 2008-04-17 10:21 胡满超阅读(34757) | 评论 (23) | 编辑收藏

迷宫最短路径问题解析

摘要: 有一个二维数组，0表示路，-1表示墙，求其中任意两点的最短路径。我们先看，怎么求一条路径：求两点路径是一个数据结构上的典型的迷宫问题，很多数据结构的书上都有介绍，解决办法如下：从一点开始出发，向四个方向查找，每走一步，把走过的点的值+1(即本节点值+1)，防止重复行走，并把走过的点压入堆栈(表示路径)，如果遇到墙、或者已走过的点则不能前进，如果前方已经无路可走，则返回，路径退栈，这样递归调... 阅读全文

posted @ 2008-03-18 17:47 胡满超阅读(8818) | 评论 (4) | 编辑收藏

为二维数组循环赋值

曾经遇到一个为二维数组循环赋值的问题，即赋值后的二维数组为如下情形：

当时在网上找了一下答案，基本上都是1层大循环套4层小循环还实现的，感觉不够优雅。最近翻了一下数据结构的书，看到迷宫问题受到了一点启发，感觉同样是实现这个功能，如下代码要优雅一些：

const int ROW__ = 10;
const int COL__ = 10;
int mat[ROW__][COL__];

struct Position
{
    int    nRow;
    int nCol;
};

void printMat(int mat[ROW__][COL__]);

int main(int argc, char* argv[])
{
    Position offset[4];
    offset[0].nRow = 0;        offset[0].nCol = 1;
    offset[1].nRow = 1;        offset[1].nCol = 0;
    offset[2].nRow = 0;        offset[2].nCol = -1;
    offset[3].nRow = -1;    offset[3].nCol = 0;

    Position curPos;
    curPos.nRow = 0;
    curPos.nCol = 0;
    mat[0][0] = 1;

    int nOffset = 0;

    Position tempPos;
    for (int i = 1; i < ROW__*COL__; i++)
    {
        // nOffset % 4 ------> 右->下->左->上循环
        tempPos.nRow = curPos.nRow + offset[nOffset % 4].nRow;
        tempPos.nCol = curPos.nCol + offset[nOffset % 4].nCol;

        if (   tempPos.nRow >= ROW__ || tempPos.nRow < 0
            || tempPos.nCol >= COL__ || tempPos.nCol < 0    // 不超过边界
            || mat[tempPos.nRow][tempPos.nCol] > 0)         // 已经有值
        {
            i--;
            nOffset++;
            continue;
        }

        curPos = tempPos;
        mat[curPos.nRow][curPos.nCol] = i+1;
    }

    printMat(mat);

    return 0;
}

printMat函数这些就不提供了，它的功能是打印出这个数组。我上传了一下工程，有兴趣的朋友点此下载。

posted @ 2008-03-04 10:30 胡满超阅读(4816) | 评论 (2) | 编辑收藏

单链表逆序输出

刚刚有人考了我一道题，逆序输出单链表：
我是这样答的（下面的代码为伪代码，不能通过编译）：

void printSList(slist *pList)
{
    assert(pList);
    if (pList == NULL)
        return;

    string str;
    while (pList)
    {
        str = string(*pList) + str;
        pList = pList->next;
    }

    printf("%s", str.c_str());
}

后来他让我想一想还有没有更为简单的方法了，当时允许我上网，我用了几分钟到网上找了一下，没有找到更好的办法，如果先把链表逆序，再顺序输出时间复杂度更高。

我走出大楼以后，忽然想到，是递归呀，对是递归：

void printSList(slist *pList)
{
    assert(pList);
    if (pList == NULL)
        return;

    if (pList->next == NULL)
        printf("%s", *pList);
    else
    {
        printSList(pList->next);
        printf("%s", *pList);
    }
}

哎，人生中机会就是一瞬之间，错过不知道下一次又是什么时候。但只要做了就会收获，会一次比一次做的好。吃饭去了...

posted @ 2008-02-29 11:43 胡满超阅读(10331) | 评论 (19) | 编辑收藏

VC中取得毫秒级的时间

1000毫秒为一秒，毫秒可能是能够取到的最小的时间单位了，代码如下：

1 DWORD startTime = GetTickCount();
2 // do something

3 DWORD totalTime = GetTickCount() - startTime;

看到楼下两们仁兄的发言，我找了一下资料，如下的代码可以取得更为精确的时间值：

1 // 取得时钟频率
2 LARGE_INTEGER  litmp ;
3 QueryPerformanceFrequency(&litmp);
4
5 LARGE_INTEGER  start;
6 QueryPerformanceCounter(&start) ;
7
8 //do something

9
10 LARGE_INTEGER end;
11 QueryPerformanceCounter(&end) ;
12
13 double dTotalTime = (double)(end.QuadPart-start.QuadPart) / (double)litmp.QuadPart; //秒
14

posted @ 2008-02-27 10:42 胡满超阅读(9790) | 评论 (4) | 编辑收藏

怎么样把一堆数平均分成N份

一年半之前，我遇到一个问题：把一堆数平均分成N份，保证每一份的和接近于所有数之和除以N，不要求平分以后的每份数据个数相等。这是有现实的程序设计需求的，当时是3份。首先想到要先进行排序，再依次从已排序的数列中抽取，如何进行抽取方法有很多，我大概想了3种左右，感觉要拿一些数据去测试一下这几种方法哪一种可以逼近最优解。

当时经理要求算法一定能够得出最优解，但测试多组数据，没有发现哪一种实现能得到最优解。后来翻了一下《数据结构、算法与应用--C++语言描述》，忽然想到，原来这个是一个典型贪婪算法问题，这个问题没有最优解，用贪婪算法来解决这个问题可以让每一次结果逼近最优。实现如下(注：代码是我今天写的)：

typedef vector<int>       IntVector;
typedef vector<IntVector> IntMat;

void DeuceNumber(const IntVector &SourceVecNum,
                 const int       nShare,
                 IntMat          &OutVecVecNum)
{
    IntVector copySourceNum = SourceVecNum;
    sort(copySourceNum.begin(), copySourceNum.end(), greater<int>());

    IntVector sum(nShare);
    OutVecVecNum.resize(nShare);

    for (int i = 0; i < copySourceNum.size(); i++)
    {
        const int nMinSumPos     = min_element(sum.begin(), sum.end()) - sum.begin();
        OutVecVecNum[nMinSumPos].push_back(copySourceNum[i]);
        sum         [nMinSumPos] += copySourceNum[i];
    }
}

我上传了一个VC的测试工程，有兴趣的朋友点此下载。

理论的依据不仅指导了实践的选择，同时给选择以有力的支撑。

2007年就要结束了，在此预祝大家在新的一年里：身体健康，平安如意！

posted @ 2007-12-29 15:52 胡满超阅读(4113) | 评论 (12) | 编辑收藏

VC中怎么执行一个应用程序，并取得应用程序的返回值

假设需要执行的程序如下：

int main(int argc, char* argv[])
{
return argc;
}

执行它，并取得其返回值，我写了一个函数如下：

DWORD         WinExecAndWait32(    LPCTSTR lpszAppPath,   // 执行程序的路径
                                LPCTSTR lpParameters,  // 参数
                                LPCTSTR lpszDirectory, // 执行环境目录
                                DWORD dwMilliseconds)  // 最大等待时间, 超过这个时间强行终止
{
    SHELLEXECUTEINFO ShExecInfo = {0};
    ShExecInfo.cbSize    = sizeof(SHELLEXECUTEINFO);
    ShExecInfo.fMask    = SEE_MASK_NOCLOSEPROCESS;
    ShExecInfo.hwnd        = NULL;
    ShExecInfo.lpVerb    = NULL;
    ShExecInfo.lpFile    = lpszAppPath;
    ShExecInfo.lpParameters = lpParameters;
    ShExecInfo.lpDirectory    = lpszDirectory;
    ShExecInfo.nShow    = SW_HIDE;
    ShExecInfo.hInstApp = NULL;
    ShellExecuteEx(&ShExecInfo);

    // 指定时间没结束
    if (WaitForSingleObject(ShExecInfo.hProcess, dwMilliseconds) == WAIT_TIMEOUT)
    {    // 强行杀死进程
        TerminateProcess(ShExecInfo.hProcess, 0);
        return 0;    //强行终止
    }

    DWORD dwExitCode;
    BOOL bOK = GetExitCodeProcess(ShExecInfo.hProcess, &dwExitCode);
    ASSERT(bOK);

    return dwExitCode;
}

我上传了两个工程，希望对大家有所帮助！

http://www.cppblog.com/Files/humanchao/ExecExe.rar

posted @ 2007-12-28 11:20 胡满超阅读(5953) | 评论 (4) | 编辑收藏

字符集编码详解

字符是各种文字和符号的总称，包括各国家文字、标点符号、图形符号、数字等。字符集是多个字符的集合，字符集种类较多，每个字符集包含的字符个数不同，常见字符集名称：ASCII字符集、GB2312字符集、BIG5字符集、 GB 18030字符集、Unicode字符集等。计算机要准确的处理各种字符集文字，需要进行字符编码，以便计算机能够识别和存储各种文字。

中文文字数目大，而且还分为简体中文和繁体中文两种不同书写规则的文字，而计算机最初是按英语单字节字符设计的，因此，对中文字符进行编码，是中文信息交流的技术基础。本文将按照字符集的时间顺序讨论几种典型的字符集，选取几种代表性的中文字符集，研究历史由来、特点、技术特征。

汉字编码范围

名称第一字节第二字节

GB2312 0xB0-0xF7(176-247) 0xA0-0xFE（160-254）

GBK 0x81-0xFE（129-254） 0x40-0xFE（64-254）

Big5 0x81-0xFE（129-255） 0x40-0x7E（64-126）

0xA1－0xFE（161-254）

ASCII 字符集

1．名称的由来

ASCII（American Standard Code for Information Interchange，美国信息互换标准代码）是基于罗马字母表的一套电脑编码系统。

2．特点

它主要用于显示现代英语和其他西欧语言。它是现今最通用的单字节编码系统，并等同于国际标准ISO 646。

3．包含内容

控制字符：回车键、退格、换行键等。

可显示字符：英文大小写字符、阿拉伯数字和西文符号

4．技术特征

7位（bits）表示一个字符，共128字符

5．ASCII扩展字符集

7位编码的字符集只能支持128个字符，为了表示更多的欧洲常用字符对ASCII进行了扩展，ASCII扩展字符集使用8位（bits）表示一个字符，共256字符。

ASCII扩展字符集比ASCII字符集扩充出来的符号包括表格符号、计算符号、希腊字母和特殊的拉丁符号。

GB2312 字符集

1．名称的由来

GB2312又称为GB2312-80字符集，全称为《信息交换用汉字编码字符集·基本集》，由原中国国家标准总局发布，1981年5月1日实施。

2．特点

GB2312是中国国家标准的简体中文字符集。它所收录的汉字已经覆盖99.75%的使用频率，基本满足了汉字的计算机处理需要。在中国大陆和新加坡获广泛使用。

3．包含内容

GB2312收录简化汉字及一般符号、序号、数字、拉丁字母、日文假名、希腊字母、俄文字母、汉语拼音符号、汉语注音字母，共 7445 个图形字符。其中包括6763个汉字，其中一级汉字3755个，二级汉字3008个；包括拉丁字母、希腊字母、日文平假名及片假名字母、俄语西里尔字母在内的682个全角字符。

4．技术特征

（1）分区表示：

GB2312中对所收汉字进行了“分区”处理，每区含有94个汉字/符号。这种表示方式也称为区位码。

各区包含的字符如下：01-09区为特殊符号；16-55区为一级汉字，按拼音排序；56-87区为二级汉字，按部首/笔画排序；10-15区及88-94区则未有编码。

（2）双字节表示

两个字节中前面的字节为第一字节，后面的字节为第二字节。习惯上称第一字节为“高字节” ，而称第二字节为“低字节”。

“高位字节”使用了0xA1-0xF7 (把01-87区(88-94区未有编码)的区号加上0xA0)，“低位字节”使用了0xA1-0xFE (把01-94加上0xA0)。

5．编码举例

以GB2312字符集的第一个汉字“啊”字为例，它的区号16，位号01，则区位码是1601，在大多数计算机程序中，高字节和低字节分别加0xA0得到程序的汉字处理编码0xB0A1。计算公式是：0xB0=0xA0+16, 0xA1=0xA0+1。

GBK 字符集

1．名称的由来

GBK是GB2312的扩展，是向上兼容的，因此GB2312中的汉字的编码与GBK中汉字的相同。另外，GBK中还包含繁体字的编码，它与Big5编码之间的关系我还没有弄明白，好像是不一致的。

2. 特点

GBK中每个汉字仍然包含两个字节，第一个字节的范围是0x81-0xFE（即129-254），第二个字节的范围是0x40-0xFE（即64-254）。GBK中有码位23940个，包含汉字21003个。

BIG5 字符集

1．名称的由来

又称大五码或五大码，1984年由台湾财团法人信息工业策进会和五间软件公司宏碁 (Acer)、神通 (MiTAC)、佳佳、零壹 (Zero One)、大众 (FIC)创立，故称大五码。

Big5码的产生，是因为当时台湾不同厂商各自推出不同的编码，如倚天码、IBM PS55、王安码等，彼此不能兼容；另一方面，台湾政府当时尚未推出官方的汉字编码，而中国大陆的GB2312编码亦未有收录繁体中文字。

2．特点

Big5字符集共收录13,053个中文字，该字符集在中国台湾使用。耐人寻味的是该字符集重复地收录了两个相同的字：“兀”(0xA461及0xC94A)、“嗀”(0xDCD1及0xDDFC)。

3．字符编码方法

Big5码使用了双字节储存方法，以两个字节来编码一个字。第一个字节称为“高位字节”，第二个字节称为“低位字节”。高位字节的编码范围0xA1-0xF9，低位字节的编码范围0x40-0x7E及0xA1-0xFE。

各编码范围对应的字符类型如下：0xA140-0xA3BF为标点符号、希腊字母及特殊符号，另外于0xA259-0xA261，存放了双音节度量衡单位用字：兙兛兞兝兡兣嗧瓩糎；0xA440-0xC67E为常用汉字，先按笔划再按部首排序；0xC940-0xF9D5为次常用汉字，亦是先按笔划再按部首排序。

4．Big5 的局限性

尽管Big5码内包含一万多个字符，但是没有考虑社会上流通的人名、地名用字、方言用字、化学及生物科等用字，没有包含日文平假名及片假名字母。

例如台湾视“着”为“著”的异体字，故没有收录“着”字。康熙字典中的一些部首用字(如“亠”、“疒”、“辵”、“癶”等)、常见的人名用字(如“堃”、“煊”、“栢”、“喆”等) 也没有收录到Big5之中。

GB18030 字符集

1．名称的由来

GB 18030的全称是GB18030-2000《信息交换用汉字编码字符集基本集的扩充》，是我国政府于2000年3月17日发布的新的汉字编码国家标准，2001年8月31日后在中国市场上发布的软件必须符合本标准

2．特点

GB 18030字符集标准的出台经过广泛参与和论证，来自国内外知名信息技术行业的公司，信息产业部和原国家质量技术监督局联合实施。

GB 18030字符集标准解决汉字、日文假名、朝鲜语和中国少数民族文字组成的大字符集计算机编码问题。该标准的字符总编码空间超过150万个编码位，收录了27484个汉字，覆盖中文、日文、朝鲜语和中国少数民族文字。满足中国大陆、香港、台湾、日本和韩国等东亚地区信息交换多文种、大字量、多用途、统一编码格式的要求。并且与Unicode 3.0版本兼容，填补Unicode扩展字符字汇“统一汉字扩展A”的内容。并且与以前的国家字符编码标准（GB2312，GB13000.1）兼容。

3．编码方法

GB 18030标准采用单字节、双字节和四字节三种方式对字符编码。单字节部分使用0×00至0×7F码(对应于ASCII码的相应码)。双字节部分，首字节码从0×81至0×FE，尾字节码位分别是0×40至0×7E和0×80至0×FE。四字节部分采用GB/T 11383未采用的0×30到0×39作为对双字节编码扩充的后缀，这样扩充的四字节编码，其范围为0×81308130到0×FE39FE39。其中第一、三个字节编码码位均为0×81至0×FE，第二、四个字节编码码位均为0×30至0×39。

4．包含的内容

双字节部分收录内容主要包括GB13000.1全部CJK汉字20902个、有关标点符号、表意文字描述符13个、增补的汉字和部首/构件80个、双字节编码的欧元符号等。　　四字节部分收录了上述双字节字符之外的，包括CJK统一汉字扩充A在内的GB 13000.1中的全部字符。

对汉字进行hash

为了处理汉字的方便，在查找汉字的时候，我们通常会用到hash的方法，那怎么来确定一个汉字位置呢？这就和每种编码的排列有关了，这里主要给出一种hash函数的策略。

对于GB2312编码，设输入的汉字为GBword，我们可以采用公式(C1-176)*94 + (C2-161)确定GBindex。其中，C1表示第一字节，C2表示第二字节。具体如下：

GBindex = ((unsigned char)GBword.at(0)-176)*94 + (unsigned char)GBword.at(1) - 161;

之所以用unsigned char类型，是因为char是一个字节，如果用unsigend int，因为int是4个字节的，所以会造成扩展，导致错误。

对于GBK编码，设输入的汉字为GBKword，则可以采用公式 index=(ch1-0x81)*190+(ch2-0x40)-(ch2/128)，其中ch1是第一字节，ch2是第二字节。

具体的，

GBKindex = ((unsigned char)GBKword[0]-129)*190 +

((unsigned char)GBKword[1]-64) - (unsigned char)GBKword[1]/128;

怎样判断一个汉字的是什么编码

直接根据汉字的编码范围判断，对于GB2312和GBK可用下面两个程序实现。

1、判断是否是GB2312

bool isGBCode(const string& strIn)

{

unsigned char ch1;

unsigned char ch2;

if (strIn.size() >= 2)

{

ch1 = (unsigned char)strIn.at(0);

ch2 = (unsigned char)strIn.at(1);

if (ch1>=176 && ch1<=247 && ch2>=160 && ch2<=254)

return true;

else return false;

}

else return false;

}

2、判断是否是GBK编码

bool isGBKCode(const string& strIn)

{

unsigned char ch1;

unsigned char ch2;

if (strIn.size() >= 2)

{

ch1 = (unsigned char)strIn.at(0);

ch2 = (unsigned char)strIn.at(1);

if (ch1>=129 && ch1<=254 && ch2>=64 && ch2<=254)

return true;

else return false;

}

else return false;

}

3、对于Big5

它的范围为：高字节从0xA0到0xFE，低字节从0x40到0x7E，和0xA1到0xFE两部分。判断一个汉字是否是BIG5编码，可以如上对字符的编码范围判断即可。如何定位呢？那么也想象所有编码排列为一个二维坐标，纵坐标是高字节，横坐标是低字节。这样一行上的汉字个数：(0x7E-0x40+1)+(0xFE-0xA1+1)＝157。那么定位算法分两块，为:

if 0x40<=ch2<=0x7E: #is big5 char

index=((ch1-0xA1)*157+(ch2-0x40))*2

elif 0xA1<=ch2<=0xFE: #is big5 char

index=((ch1-0xA1)*157+(ch2-0xA1+63))*2

对于第二块，计算偏移量时因为有两块数值，所以在计算后面一段值时，不要忘了前面还有一段值。0x7E-0x40+1=63。

如果判断一个字符是西文字符还是中文字符

大家知道西文字符主要是指ASCII码，它用一个字节表示。且这个字符转换成数字之后，该数字是大于0的，而汉字是两个字节的，第一个字节的转化为数字之后应该是小于0的，因此可以根据每个字节转化为数字之后是否小于0，判断它是否是汉字。

例如，设输入字为strin，则，

If (strin.at(0) < 0)

cout << ”是汉字” << endl;

else cout << ”不是汉字” << endl;

编码表

Unicode字符集

1．名称的由来

Unicode字符集编码是Universal Multiple-Octet Coded Character Set 通用多八位编码字符集的简称，是由一个名为 Unicode 学术学会(Unicode Consortium)的机构制订的字符编码系统，支持现今世界各种不同语言的书面文本的交换、处理及显示。该编码于1990年开始研发，1994年正式公布，最新版本是2005年3月31日的Unicode 4.1.0。

2．特征

Unicode是一种在计算机上使用的字符编码。它为每种语言中的每个字符设定了统一并且唯一的二进制编码，以满足跨语言、跨平台进行文本转换、处理的要求。

3．编码方法

Unicode 标准始终使用十六进制数字，而且在书写时在前面加上前缀“U+”，例如字母“A”的编码为 004116 和字符“?”的编码为 20AC16。所以“A”的编码书写为“U+0041”。

4．UTF-8 编码

UTF-8是Unicode的其中一个使用方式。 UTF是 Unicode Translation Format，即把Unicode转做某种格式的意思。

UTF-8便于不同的计算机之间使用网络传输不同语言和编码的文字，使得双字节的Unicode能够在现存的处理单字节的系统上正确传输。

UTF-8使用可变长度字节来储存 Unicode字符，例如ASCII字母继续使用1字节储存，重音文字、希腊字母或西里尔字母等使用2字节来储存，而常用的汉字就要使用3字节。辅助平面字符则使用4字节。

5．UTF-16 和 UTF-32 编码

UTF-32、UTF-16 和 UTF-8 是 Unicode 标准的编码字符集的字符编码方案，UTF-16 使用一个或两个未分配的 16 位代码单元的序列对 Unicode 代码点进行编码；UTF-32 即将每一个 Unicode 代码点表示为相同值的 32 位整数

posted @ 2007-09-27 09:28 胡满超阅读(2361) | 评论 (0) | 编辑收藏

仅列出标题

留言簿(16)

随笔分类(56)

随笔档案(89)

文章分类

推荐博客

搜索

最新随笔

最新评论

阅读排行榜