转载请注明出处
作者:小马
最近在看斯坦福大学的<<programming abstractions>>课程，觉得其中的一节课讲得特别好，大概50分钟左右的一节课的视频, 仅仅一节课，就让我深刻体会到国内大学的计算机教育跟美国的差别.
可以回忆一下自己在学校读书时, 老师是怎么讲C或c++语言的. 反正我就记得几乎没见过老师自己敲过几行代码, 都是照着PPT读.
斯坦福这节课主要是讲如何用C实现一个通用的线性查找函数, 所谓通用,就是指可以查找任何类型的数据. 在C++中可以用模板, 如果用C实现, 只能用指针, 所以这节课其实是通过一个具体的应用, 让学生更好的理解指针.(如果我没记错的话，我大学考C语言，指针不在考试范围内!!!!)
这个老师只写出一些重要的代码实现. 我在这里加入一些应用代码, 以及一些必要的解释, 把整节课的核心整理成之篇博文, 希望能对大家理解上有帮助,尤其是希望能对目前还没有毕业的计算机专业的大学生有所启发.
以下程序全部在visual studio 2008下调试通过.
先来看看这个线性查找函数是如何实现的, 如下:
void *ISearch(void *key, void *base, int n, int elementSize,
int (* Compare)(void *, void *))
{
int i = 0;
void *pTmp = NULL;
for (i = 0; i < n; i++)
{
pTmp = (char *)base + i*elementSize;
if (Compare(key, pTmp) == 0)
{
return pTmp;
}
}
return NULL;
}
这个函数比较容易理解, 第一个参数传入一个指向要查找元素的指针, 第二个是查找范围的基地址, 第三个参数是每个元素的大小, 比如int型, 在32位的机器上就是4. 第四个参数传入一个函数指针, 这个函数的作用是比较要查找的元素与查找 序列中的某一个元素是否相等. 针对不同的数据类型, 有不同的实现形式.
先来看一个最简单的应用, 在一个整型数组中查找某一个整型数是否存在. 主函数这样写:
int _tmain(int argc, _TCHAR* argv[])
{
int nArray[] = {3, 1, 45, 22, 0, 4};
int n = 6;
int key = 22;
int *findPosition = ISearch(&key, nArray, n, sizeof(int),
IntCompare);
if (findPosition == NULL)
{
printf("can not find the key!/n");
}
else
{
printf("find the key %d!/n", *findPosition);
}
return 0;
}
思路很清晰, 根据ISearch的接口定义传入相应的参数, 现在唯一要做的就是实现比较函数, 这个也是很简单,如下:
int IntCompare(void *element1, void *element2)
{
int *pTmp1 = element1;
int *pTmp2 = element2;
return (*pTmp1 - *pTmp2);
}
下面增加一些难度，换浮点数查找. 其实原理是一样的, 说难度增加，只是因为浮点数在比较大小时需要一些特殊处理. 先看主函数吧.
int _tmain(int argc, _TCHAR* argv[])
{
double nArray[] = {3.01, 1.00, 45.045, 22, 0, 4.1};
int n = 6;
double key = 4.099999;
double *findPosition = ISearch(&key, nArray, n, sizeof(double),
DoubleCompare);
if (findPosition == NULL)
{
printf("can not find the key!/n");
}
else
{
printf("find the key %lf!/n", *findPosition);
}
return 0;
}
DoubleCompare函数在做一些特殊处理, 因为计算机是不能精确表示浮点数的, 因为计算机用的都是离散化的数据量，只能在一定的精度范围内表示浮点数. 所以我们不能直接用比较运算符直接操作浮点数. 我们可以设定一个阀值，规定两个浮点数的差的绝对值小于这个阀值，就认为两个数相等.
int DoubleCompare(void *element1, void *element2)
{
double dLimit = 0.000001; //比较阀值,
int nRet = 0;
double *pTmp1 = element1;
double *pTmp2 = element2;
if ( (*pTmp1 - *pTmp2) > dLimit )
{
nRet = 1;
}
else if (((*pTmp1 - *pTmp2) < dLimit) && ((*pTmp1 - *pTmp2) > -dLimit))
{
nRet = 0;
}
else
{
nRet = -1;
}
return nRet;
}
进一步增加难度, 字符串的应用, 举例如下:
一个字符串数组:
char *strArrany[] = {"ab", "Bcddeee", "#*", "fB"};
要查找char *strKey = “fB”是否在该字符串中.
这个用法跟前两个有很大的差别, 前两个应用中, 数组中的元素就是值本身, 比如整型数组, 元素就是一个整型数. 而字符串数组, 数组中的元素确不是字符串, 而是指向这些字符串的指针. 所以数组中每一个元素的大小其实是指针的大小,也就是sizeof(char *).理解这个很重要.
如果我把字符串数组用下面的图表示，可能会有助于理解:
从图上看, 字符串数组里的每一个元素其是就是一个指针, 所以它的一个元素的大小就是sizeof(char *).然后我们再看ISearch的第一个参数是传递要查找元素的地址, 对指针当然也不例外, 所以第一个参数形式为&strKey.
理解了上面那些，很容易写出主函数.
int _tmain(int argc, _TCHAR* argv[])
{
char *strArrany[] = {"ab", "Bcddeee", "#*", "fB"};
int n = 4;
char *strKey = "fB";
char *findPosition = ISearch(&strKey, strArrany, n, sizeof(char *),
StrCompare);
if (findPosition == NULL)
{
printf("can not find the key!/n");
}
else
{
printf("find the key %s!/n", *findPosition);
}
return 0;
}
最难理解的部分就是比较函数了.它的实现如下:
int StrCompare(void *element1, void *element2)
{
char *pTmp1 = *(char **)element1;
char *pTmp2 = *(char **)element2;
return strcmp(pTmp1, pTmp2);
}
可能你会对
char *pTmp1 = *(char **)element1;
这样的用法充满了疑惑. 下面就来一步步解惑. element1是一个指针, 它的形参是void*, 也就是没有类型的指针, 它指向何处要看传入的实参. 在ISearch的实现中, 找到这样几行:
if (Compare(key, pTmp) == 0)
{
return pTmp;
}
原来传入的是key, 那么key又是什么呢? 它是ISearch接口的第一个参数,如下:
void *ISearch(void *key, void *base, int n, int elementSize, int (* Compare)(void *, void *));
key指向的实参是什么呢? 在主函数中找到ISearch被调用的地方, 如下:
char *strKey = "fB";
char **findPosition = ISearch(&strKey, strArrany, n, sizeof(char *),StrCompare);
strKey本身是一个指向一个字符串常量(“fB”)的指针, 而传到ISearch里的是&strKey,也就是这个指针的地址. 所以, key就是一个指针, 这个指针的指向的值也是是一个指针, 这个指针指向的地址上放的内容是”fB”, 所以key实际上是一个char **的变量,从而element1也就是一个char **的变量. 又加一个”*”,这是通过解引用把指向”fB”的那个地址取出来.
如果说到这里，你还是不能理解. 那么我换一种方式实现StrCompare, 是不是会有助于理解呢?
int StrCompare(void *element1, void *element2)
{
char **pTmp1 = element1; //
char **pTmp2 = element2;
return strcmp(*pTmp1, *pTmp2);
}
如果你还是在校的大学生，对这部分理解的不清楚也不用着急, 我看到视频上，我们的美国同学也是对这个用法有很多的不解,看来大家的水平还是差不多的. 呵呵. 我的建议是多练习，多思考.