第三部分 应用  第11章 排序     问题：使用库排序函数并非总是有效的，因此在某些情况下程序员要自己编写排序函数。  插入排序：大多纸牌游戏的玩家都采用插入排序来排列手中的纸牌。他们保持已发到手中的牌有序，当拿到一张新牌时，即将其插入合适的位置，     伪代码：         for i = [1,n)             /* invariant: x[0..n-1] is sorted */             /* goal: sift x[i] down to its proper place in x[0..i] */ ...

第九章 代码调优 提高效率的高层次方法：问题定义、系统结构、算法设计、数据结构。本章讨论了低层次的方法：代码调优，首先要确定程序中开销较大的部分，然后进行少量修改，以提高其运行速度。 1、典型例子：关于一个复杂图像处理程序的调优。首先监视程序性能，发现程序的大部分运行时长花在对某一类型malloc分配空间上 ——>应用高速缓存原理解决问题：将常见类型的空闲记录缓存在一个链表中，因此可以直接快速访问链表来处理常见的请求而无需调用通用的分配程序——>时间缩短为45%，且减少了内存碎片。 2、调优技巧： a:整数取模，利用等价的代数表达式，如下所示，使用低开销的比...

第七章粗略估算 1、          问题引入：密西西比河一天流出多少水？ 估算河出口大约1英里宽、20英尺深（即1/250英里），猜测水流速度为每小时5英里或说是每年120英里，所以密西西比河每天大约流出1*1/250*120=1/2英里3/天，误差在一个数量级之内。 2、          基本技巧： （1）两个答案比一个答案好，使用不同的方法解决问题，通过比较问题的答案对估算的结果进行检验；例如，上述问题的估算方法有三种： a. 河流出口宽度*河流出口深度*流速 b. 流入水量 = 流域面积 * 日均降雨径流量； c. 从某年鉴数据，密西西比河...

第五章 编程小事 1、从伪代码到C程序：  int binarysearch(DataType t){ int l,u,m; l=0; u=n-1; while(l<=u){ m=(l+u)/2; if(x[m]<t) l=m+1; else if(x[m]==t) return m; else if(x[m]>t) u=m-1; } return -1; 2、测试工具: (1) 手动测试，输入一些小实例、单步跟踪调试、print语句 (2) 自动测试：添加断言、编写测...

第三章 数据决定程序结构 几个案例： 1、一个调查程序 输入：某学院的学生所填写的近2万份调查表，共25页分别代表8大类，每条记录表示每份调查表； 输出：3页相似输出以及其他密切相关的表，例如拒绝回答每个问题的学生数目。 程序设计：（三视图方法）关键在于用数组来存储数据；数组按照其输出结构或者按照其输入结构来组织。 2、格式信函编程 编写基于格式信函模板的格式信函发生器；$i代表记录中的第i个字段，长字符串数组表示该模板。 发生器+模板程序实现。将数据从控制中分离出来：如果重新设计信函，那么模板可以使用文本编辑器来修改，从而第二个特定页的准备也会...

《编程珠玑》学习笔记 第一部分 第1章 开篇（2018.07.11） ü 抛出问题：“怎样给一个磁盘文件排序” ü 引导明确问题：输入：最多包含N个正整数，每个书都小于N，N=107，无重复、关联数据； 输出：按升序排列的整数列表； 约束条件：最多约1MB内存空间可用，充足的磁盘存储空间可用，运行时间最多几分钟，10秒就无需再优化。 ü 程序设计：起点：基于磁盘的归并程序实现 利用排序问题的特殊性：每个号码7byte，1MB可存143000个；如每个号码32位证书，1MB可存250000个。可使用输入遍历文件40趟，内存中用快排完成排序。 ...