专栏首页犀牛饲养员的技术笔记看看斯坦福大学是如何教学生编程的

看看斯坦福大学是如何教学生编程的

最近在看斯坦福大学的<<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);
}

本文分享自微信公众号 - 犀牛饲养员的技术笔记(coder_start_up),作者:siwuxie18

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-09-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • lua执行redis脚本找不到脚本的问题

    有个项目,利用redis做统计功能。一向对性能追求极致的我怎么能随便写几条redis的统计语句就应付呢。于是我打算使用lua脚本把用到的几条redis指令封装一...

    用户7634691
  • 一文说透如何同步的方式操作HashMap

    很多人都知道HashMap是非线程安全的。比如下面这段代码,多运行几次,基本每次会抛出异常:

    用户7634691
  • 从一个问题来解释下什么是mysql的可重复读

    补充解释下这个问题,mysql环境,innodb引擎,事务的隔离级别是可重复读,一个表只有两个字段,然后插入4条数据,希望你构造上图中的一种情况,就是明明upd...

    用户7634691
  • C学习笔记(2)--指针

    一、多文件结构总结 1.子源文件里面包含自己对应的头文件 2.无论是何源文件调用库函数,都需要包含该库函数的声明所在的头文件 3.头文件又叫接口文件,.c对数据...

    hbbliyong
  • 从零开始学C++之模板(三):缺省模板参数(借助标准模板容器实现Stack模板)、成员模板、关键字typename

    一、缺省模板参数 回顾前面的文章,都是自己管理stack的内存,无论是链栈还是数组栈,能否借助标准模板容器管理呢?答案是肯定的,只需要多传一个模板参数即可,而且...

    s1mba
  • 用python做时间序列预测五:时间序列缺失值处理

    程序员一一涤生
  • 程序员C语言快速上手——进阶篇(六)

    由上例可验证,数组的内存空间是连在一起的,它的第一个元素地址是0x22fe30,第二个元素的地址是0x22fe34,紧随其后。因为是int数组,每个元素都需要占...

    arcticfox
  • 在线教育平台开发中,如何接入sdk实现小班课

    在线教育平台开发过程中,有些功能并不是通过公司一手打造的,而是通过接入第三方实现的,因为相比于重新开发,接入第三方反而更加保险和稳定,接下来,小编将以声网sdk...

    万岳教育系统
  • 深度解读 | 电信联通合并,到底意味着什么?

    最近,关于电信联通合并的传闻此起彼伏,牵动着很多人的神经,也引起了行业内外的广泛关注。

    鲜枣课堂
  • 哈希表问题-LeetCode 146、290、299、300(哈希表,双向链表,最小上升序列)

    运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作:获取数据 get 和 写入数据 put 。

    算法工程师之路

扫码关注云+社区

领取腾讯云代金券