学步园

偶然间写了一个字符串数组的排序函数，但老是达不到理想的效果，找了半天才发现是形式参数与实际参数维度不等长导致的。一个简单的二分查找字符串数组算法实现程序如下： 

int BinarySearch( const char sArr[][100], const char *sSub, int iLen)
{
    int iLeftIdx = 0;
    int iRightIdx= iLen - 1;
    int iMidIdx = 0;
    while(iLeftIdx <= iRightIdx)
    {
        iMidIdx = (iLeftIdx + iRightIdx) / 2;
        if (strcmp (sSub, sArr[iMidIdx]) == 0) return iMidIdx;
        if (strcmp (sSub, sArr[iMidIdx]) > 0)
            iLeftIdx = iMidIdx + 1;
        else
            iRightIdx = iMidIdx - 1;
    }
    return -1;
}

调用二分查找法的一个简单的调用程序如下：

void main()
{
    char ss[4][20];
    int k = 0;
    for (int i=0; i<4; i++)
    {
        sprintf (ss[i], "%d", i+1);
    }
    k = BinarySearch(ss, "2", 4);
    printf ("%d", k);   
} 

大家猜一下，这段程序会输出什么？

＝＝＝========

答案是输出:　-1 

如果你已经找到了原因，可以略过以下部分不看。如果你还没想到为什么会这样，那我建议你稍微看一眼。

其实原因一点也不复杂，说起来反而很简单，就是Ｃ语言二维数据在内存中的存放问题。

在Ｃ语言里，二维数组在内存中是按顺序连续存放的，比如定义了数组int a[2][2],那么它在32位机器内存中的存放方式将如下所示：

| a[0][0] | a[0][1] | a[1][0] | a[1][1] |

|4 bytes|4 bytes|4 bytes|4 bytes|

每一个数组元素占了４个字节，a[1]（第1行的首地址，即a[1][0]的地址）与a[0]（第0行的首地址，即a[0][0]的地址）之间相差两个元素，共有８个字节。即两行首地址之间内存距离为　每个元素占字节数*第二维数组长度=4*2=8字节

知道了这个原理，就不难理解前面程序为什么会输出　-1 了。因为在上述二分法函数中，参数数组sArr两行首地址之间的距离为　1*100=100字节。但实际参数ss两行首地址之间的距离为1*20=20字节。因此，在二分查找函数中，sArr[iMidIdx]根本就没有指向ss[iMidIdx]，而是指向ss[iMidIdx]的后面的某一块内存地址，这块地址可能还未被分配。

（ps:看了上面的解释， 是不是感觉自己老了呢？其它有时候写程序写多了，一些基本的东西反而不会用了，所以说温故而知新，真的是要常常学习啊！)

解决上述问题的方法有几一个。最简单的办法是直接将形式参数和实际参数第二维的长度定义一样长。但这样的函数显然不能通用。如果想定义一个通用的函数，还是通过将二维数组转化为一维数据，使用内存距离动态计算后面元素的地址来取值。这种方法要求将第二维的长度了通过参数传入函数中。

 修改后的二分法查找字符串如下所示：

int BinarySearch( const char **sArr, const char *sSub, int iLen1, int iLen2)
{
    int iLeftIdx = 0;
    int iRightIdx= iLen1 - 1;
    int iMidIdx = 0;
    char *p ;
    while(iLeftIdx <= iRightIdx)
    {
        iMidIdx = (iLeftIdx + iRightIdx) / 2;
        p = (char *)sArr+iMidIdx*iLen2;
        if (strcmp (sSub, p) == 0) return iMidIdx;
        if (strcmp (sSub, p) > 0)
            iLeftIdx = iMidIdx + 1;
        else
            iRightIdx = iMidIdx - 1;
    }
    return -1;
}

/*
也可以通过指针转化的方式，形式参数直接定义为一维指针，调用函数时将实际参数的二维指针转化为我们熟悉的一维指针
*/
int BinarySearch3( const char *sArr, const char *sSub, int iLen1, int iLen2)
{  
    int iLeftIdx = 0;
    int iRightIdx= iLen1 - 1;
    int iMidIdx = 0; 
    char *p ;
    while(iLeftIdx <= iRightIdx)
    {
        iMidIdx = (iLeftIdx + iRightIdx) / 2; 
        p = sArr+iMidIdx*iLen2;
        if (strncmp (sSub, p, iLen2) == 0) return iMidIdx;        
        if (strncmp (sSub, p, iLen2) > 0) 
            iLeftIdx = iMidIdx + 1;
        else 
            iRightIdx = iMidIdx - 1;
    }
    return -1;
}

/*
调用方式：k=BinarySearch3((char *)ss, "2", 4, 20);
*/