C++博客-程序描绘人生

将字符串里词顺序倒置

胡满超 — Fri, 12 Sep 2008 12:42:00 GMT

将字符串里词顺序倒置，如"Times New Roman"变为"Roman New Times"。以空格为分隔符。

解决方案为：先将整个字串倒置，然后依次把倒置后串中的每一个单词倒置。

这个问题解答的思路很简单，但是要考虑到很多种的情况，比如字符串的头、尾有多余的空格怎么办，如果字符串中只有空格，还有字符串中间可能会有两个以上并列的空格。

程序如下：

1 void ReverseStr(char *pStr, int len)
2 {
3     assert(pStr);
4
5     char ch;
6     for (int i = 0; i < len/2 ; i++)
7     {
8         ch = pStr[i];
9         pStr[i] = pStr[len-1-i];
10         pStr[len-1-i] = ch;
11     }
12 }
13
14 void ReverseStrWord(char *pStr, int len)
15 {
16     assert(pStr);
17
18     if (len <= 1)
19         return;
20
21     // 倒置整个字符串
22     ReverseStr(pStr, len);
23
24     // 处理头多余的空格
25     int i = 0;
26     if (pStr[0] == ' ')            while (pStr[i] == ' ' && i < len)        i++;
27
28     // 整个串都是空格
29     if (i == len)
30         return;
31
32     // 处理尾多余的空格
33     if (pStr[len - 1] == ' ')    while (pStr[len - 1] == ' ' && len - 1 > 0)    len--;
34
35     for (int start = i; i < len; i++)
36     {
37         // 最后的end要+1
38         if (i == len-1)
39         {
40             ReverseStr(pStr+start, i-start+1);
41             break;
42         }
43
44         // 倒置一个单词
45         if (pStr[i] == ' ')
46         {
47             ReverseStr(pStr+start, i-start);
48             start = i+1;
49             // 处理内部并列的空格
50             if (pStr[start] == ' ')
51             {
52                 while(pStr[start] == ' ') {i++;start++;};
53             }
54         }
55     }
56 }
57

说实话，如果是突然面对这样一个问题，要在一张纸上写下比较完整的程序是不大可能。能边调试边写程序有的时候也是一件幸事。
中秋节要到了，我要换工作了，告别已经工作两年多熟悉的环境，感觉这两年没有太大的进步，奋斗吧，趁着自己还年轻！

胡满超 2008-09-12 20:42 发表评论

求整数1~N范围和为M的所有组合

胡满超 — Fri, 29 Aug 2008 08:13:00 GMT

问题：找出整数1~N范围和为M的所有集合，M<=N且M>1，集合里的数不允许重复。

解答：这个问题用递归解决最简单，代码如下：

1 #define MAX_NUM 20        //要足够大
2 int log[MAX_NUM];        //记录和数
3 int index = 0;            //log[]数组的当前指针
4
5 void calc(int start, int n)
6 {
7     if (n == 0)
8     {
9         for(int j = 0; j < index; j++)
10             printf("%d ", log[j]);
11         printf("\n");
12     }
13     else
14     {
15         for(int i = start; i<=n; i++)
16         {
17             log[index++] = i;
18             calc(i + 1, n - i);
19         }
20     }
21
22     index--;
23 }

如果允许重复只需要将上面第18条代码改为：

calc(i, n - i);

即可。

扩展问题：在数组{5,1,7,9,2,10,11,4,13,14}中找到和为28的所有集合，集合中不允许有重复的数。

解答：第一步要先对数组排序，然后按照上去的思路，对程序略做一些改动。
代码如下：

1 #define MAX_NUM 20        //要足够大
2 int log[MAX_NUM];        //记录和数
3 int index = 0;            //log[]数组的当前指针
4
5 void calc__(int *nArr     //数组,
6             int start    //数组起始元素下标,
7             int nArrLen    //数组长度,
8             int sum)
9 {
10     if (sum == 0)
11     {
12         for(int j = 0; j < index; j++)
13             printf("%d ", log[j]);
14         printf("\n");
15     }
16     else
17     {
18         for(int i = start; i < nArrLen; i++)
19         {
20             log[index++] = nArr[i];
21             calc__(nArr, i+1, nArrLen, sum - nArr[i]);
22         }
23     }
24
25     index--;
26 }

这个问题的解答思路是相当简单的，但如何把程序写的细致、简捷是除了解答思路以外的另一个关键。就像迷宫最短路径的那个问题，言语描述很简单，但把实现的程序写好确要花一些时间。

胡满超 2008-08-29 16:13 发表评论

重建二叉树

胡满超 — Wed, 27 Aug 2008 09:51:00 GMT

已知前序和中序：

struct NODE
{
    NODE *pLeft;
    NODE *pRight;
    char chValue;
};

int  CharInStrFirstPos(char ch, char *str, int nLen)
{
    char *pOrgStr = str;
    while (nLen > 0 && ch != *str)
    {
        str++;
        nLen--;
    }

    return (nLen > 0) ? (str - pOrgStr) : -1;
}

void ReBuild_PreIn(char *pPreOrder, char *pInOrder, int nTreeLen, NODE **pRoot)
{
    if (pPreOrder == NULL || pInOrder == NULL)
    {
        return;
    }

    NODE *pTemp = new NODE;
    pTemp->chValue = *pPreOrder;
    pTemp->pLeft = NULL;
    pTemp->pRight = NULL;

    if (*pRoot == NULL)
    {
        *pRoot = pTemp;
    }

    if (nTreeLen == 1)
    {
        return;
    }

    int nLeftLen = CharInStrFirstPos(*pPreOrder, pInOrder, nTreeLen);
    assert(nLeftLen != -1);
    int nRightLen = nTreeLen - nLeftLen -1;

    if (nLeftLen > 0)
    {
        ReBuild_PreIn(pPreOrder + 1, pInOrder, nLeftLen, &((*pRoot)->pLeft));
    }

    if (nRightLen > 0)
    {
        ReBuild_PreIn(pPreOrder + nLeftLen + 1, pInOrder + nLeftLen + 1,
            nRightLen, &((*pRoot)->pRight));
    }
}

已知后序和中序：

void ReBuild_AftIn(char *pAftOrder, char *pInOrder, int nTreeLen, NODE **pRoot)
{
    if (pAftOrder == NULL || pInOrder == NULL)
    {
        return;
    }

    NODE *pTemp = new NODE;
    pTemp->chValue = *pAftOrder;
    pTemp->pLeft   = NULL;
    pTemp->pRight  = NULL;

    if (*pRoot == NULL)
    {
        *pRoot = pTemp;
    }

    if (nTreeLen == 1)
    {
        return;
    }

    int nLeftLen = CharInStrFirstPos(*pAftOrder, pInOrder, nTreeLen);
    assert(nLeftLen != -1);
    int nRightLen = nTreeLen - nLeftLen -1;

    if (nLeftLen > 0)
    {
        ReBuild_AftIn(pAftOrder + nRightLen + 1, pInOrder, nLeftLen, &((*pRoot)->pLeft));
    }

    if (nRightLen > 0)
    {
        ReBuild_AftIn(pAftOrder + 1, pInOrder + nLeftLen + 1,
            nRightLen, &((*pRoot)->pRight));
    }
}

我上传了一个工VC的工程，有兴趣的朋友点此下载。代码参考于《编程之美》。

胡满超 2008-08-27 17:51 发表评论

断言式编程

胡满超 — Tue, 19 Aug 2008 02:00:00 GMT

我们先看一个函数：函数的功能完成1~10的加法。

int Add1to10(int a, int b)
{
return a +b;
}

但是一般我们还需要加上几条代码：

int Add1to10(int a, int b)
{
    assert(a >= 1 && a <= 10);
    assert(b >= 1 && b < =10);

    if ( a < 1 || a > 10 || b < 1 || b > 10)
        return -1;

    return a +b;
}

加上上面几条代码的作用是检查函数的输入参数，当参数不正确的时候不光要在返回值上得到体现，而且会触发assert断言，提醒我们参数有误。

断言式编程体现一个编程的思想，在我们的程序执行偏离预想的路线时给出提醒。当程序执行偏离预想的路线时一般会出现两种可能：即断言以上的程序没有理解下面程序的调用条件、或断言以下的程序需要接受更为宽泛输入条件。以下分别讨论修改方法：

1、如果函数的输入参数是我们编程的一个疏漏，我们认为根本就不应该出现或产生这样的值，那我们应该修改调用函数处的代码，避免非预想的值出现。

2、如果无法避免出现或者产生一个非法输入值，那我们要么在函数调用处加入判断，产生符合条件的值时调用函数，不符合参数条件else处理；要么修改函数，使函数可以接受更为宽泛输入条件，并调整断言内容和参数判断逻辑。

断言不仅可以出现在函数的参数检查的场合，也可以出现在其他的上下文调用的场合。而且它还会随着程序的开发进程逐渐的增加、删除和调整。它可以验证程序是按照我们预想的思路在执行，当出现意外时及时的给出提醒，提醒我们修正程序或者自己的思路。

胡满超 2008-08-19 10:00 发表评论

Quick Sort C Code Implement

胡满超 — Mon, 18 Aug 2008 09:02:00 GMT

void QuickSort(int* pData,int left,int right)
{
    int i = left, j = right;
    int middle = pData[(left+right)/2];        // midlle value
    int iTemp;
    do
    {
        while (pData[i] < middle && i < right)            i++;
        while (pData[j] > middle && j > left)            j--;
        if (i < j)                            // swap
        {
            iTemp    = pData[i];
            pData[i] = pData[j];
            pData[j] = iTemp;
            i++;            j--;
        }
        else if (i == j)
        {
            i++;            j--;
        }
    } while (i < j);

    if (left  < j)        QuickSort(pData,left,j);
    if (right > i)        QuickSort(pData,i,right);
}

没的说，理解不了就是背也得把这段代码背下来。

胡满超 2008-08-18 17:02 发表评论

（转）数据结构和算法Flash动画演示

胡满超 — Thu, 24 Jul 2008 08:19:00 GMT

学习数据结构和算法的好东西，非常形象，制作水平比较高，向制作者致敬！里面包含以下算法的过程演示：

B树的删除
B树的生长过程
三元组表的转置
中序线索化二叉树
串的顺序存储
二分查找
二叉排序树的删除
二叉排序树的生成
二叉树的建立
克鲁斯卡尔算法构造最小生成树
冒泡排序
分块查找
单链表结点的删除
单链表结点的插入
图的深度优先遍历
基数排序
堆排序
头插法建单链表
寻找中序线索化二叉树指定结点的前驱
寻找中序线索化二叉树指定结点的后继
尾插法建表
希儿排序
开放定址法建立散列表
循环队列操作演示
快速排序
拉链法创建散列表
拓扑排序
数据结构和算法Flash动画演示.rar
最短路径
朴素串匹配算法过程示意
构造哈夫曼树的算法模拟
构造哈夫曼树过程
栈与递归
...更多

点击下载

胡满超 2008-07-24 16:19 发表评论

如何在NSIS中执行BAT文件

胡满超 — Wed, 23 Jul 2008 08:47:00 GMT

如果BAT不带参数，脚本内容如下：

SetOutPath '$INSTDIR'
ExecWait '$INSTDIR\A.bat'

如果BAT需要参数时，要把带参数的命令写入另外一个新的BAT中，执行新BAT：

B.bat内容：
CALL A.bat install

NSIS 脚本：
SetOutPath '$INSTDIR'
ExecWait '$INSTDIR\B.bat'

胡满超 2008-07-23 16:47 发表评论

VC取得目录大小

胡满超 — Wed, 02 Jul 2008 08:33:00 GMT

#import   "scrrun.dll"   raw_interfaces_only

// 参数格式："c:\" 或 "c:\test"
ULONGLONG GetPathUseSpace(const char *szPath)
{
    ASSERT(szPath != NULL);

    int nLen = strlen(szPath);
    if (nLen == 0)
        return 0;

    ULONGLONG result = 0;

    if (nLen == 3)      // c:\
    {
        ULARGE_INTEGER nFreeBytesAvailable;
        ULARGE_INTEGER nTotalNumberOfBytes;
        ULARGE_INTEGER nTotalNumberOfFreeBytes;
        //
        if (GetDiskFreeSpaceEx(szPath,
              &nFreeBytesAvailable,
              &nTotalNumberOfBytes,
              &nTotalNumberOfFreeBytes))
        {
            result = nTotalNumberOfBytes.QuadPart - nFreeBytesAvailable.QuadPart;
        }
    }
    else
    {
        CoInitialize(NULL);
        {
            try
            {
                Scripting::IFileSystem3Ptr   fs;
                fs.CreateInstance(__uuidof(Scripting::FileSystemObject));

                Scripting::IFolderPtr   folder;
                fs->GetFolder(_bstr_t(szPath),&folder);

                _variant_t vsize;
                folder->get_Size(&vsize);
                result = (double)vsize;
            }
            catch(_com_error &e)
            {
                result = -1;
            }
        }

        CoUninitialize();
    }

    return result;
}

VC取得目录的大小可以用COM方式，但是在某些操作系统上使用COM方式取根目录大小（即某一个盘已用空间）会出现问题，可以用GetDiskFreeSpaceEx，上面是我写了一个小函数。

胡满超 2008-07-02 16:33 发表评论

图解快速排序:转

胡满超 — Mon, 26 May 2008 02:14:00 GMT

胡满超 2008-05-26 10:14 发表评论

判断单链表是否存在环，判断两个链表是否相交问题详解

胡满超 — Thu, 17 Apr 2008 02:21:00 GMT

有一个单链表，其中可能有一个环，也就是某个节点的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)步，之后两个链表同时前进，每次一步，相遇的第一点即为两个链表相交的第一个点。

胡满超 2008-04-17 10:21 发表评论

迷宫最短路径问题解析

胡满超 — Tue, 18 Mar 2008 09:47:00 GMT

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

胡满超 2008-03-18 17:47 发表评论

为二维数组循环赋值

胡满超 — Tue, 04 Mar 2008 02:30:00 GMT

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

当时在网上找了一下答案，基本上都是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函数这些就不提供了，它的功能是打印出这个数组。我上传了一下工程，有兴趣的朋友点此下载。

胡满超 2008-03-04 10:30 发表评论

单链表逆序输出

胡满超 — Fri, 29 Feb 2008 03:43:00 GMT

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

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);
    }
}

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

胡满超 2008-02-29 11:43 发表评论

VC中取得毫秒级的时间

胡满超 — Wed, 27 Feb 2008 02:42:00 GMT

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

胡满超 2008-02-27 10:42 发表评论

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

胡满超 — Sat, 29 Dec 2007 07:52:00 GMT

一年半之前，我遇到一个问题：把一堆数平均分成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年就要结束了，在此预祝大家在新的一年里：身体健康，平安如意！

胡满超 2007-12-29 15:52 发表评论