- 单词
第一个问题是为文档中包含的单词生成一个列表。可以使用C++标准模版库中的sets和strings:
int main(void){ set S; set ::iterator j; string t; while (c[......]
第一个问题是为文档中包含的单词生成一个列表。可以使用C++标准模版库中的sets和strings:
int main(void){ set S; set ::iterator j; string t; while (c[......]
本章重点关注的是一种特殊的数据结构——堆。这种结构在数据结构课和算法课中多有介绍(其实本章内容与《算法导论》中第6章的内容“堆排序”比较相似)。本章介绍了堆以及其两种用途——优先级队列和排序。
<li><strong>堆数据结构</strong></l[......]
<li><strong>二分搜索树</strong></li>
二分搜索树可以认为是在链表的基础上进一步进行扩展——它支持快速搜索和插入。
二分搜索树基于一个事实:任何一个结点,其左孩子的值小于其值,其右孩子的值大于其值。
pri[......]
本章讨论的是搜索问题中的数据结构。作者依次描述了适用于不同情境下的数据结构,存储的数据信息均为整数。
要实现的伪代码:
initialize set S to empty size = 0 while size < m do t = bigrand() % maxval if t is not in S insert t into S size ++ print the elements of S in sorted order
(数据结构)接口的定义:
class I[......]
本章的关注点是随机对象的选取。具体来讲,就是从n个对象中随机选取m个对象的问题,其中要用到随机数生成函数。
假设:一个能返回很大随机整数的的函数bigrand(),一个能返回i..j范围内均匀选择的随机整数函数randint(i,j)。
在C语言中,随机函数rand()通常返回约15个随[……]
插入排序
直观的插入排序isort1:
for i = [1, n) for (j=i; j > 0 && x[j-1] > x[j]; j--) swap(j-1, j)
将swap展开后得到isort2,展开代码为:
t = x[j] ;[......]
本章涉及到两个问题,其一是数据空间技术,目标是减少程序所需数据的存储空间;其二是代码空间技术,目标是减少执行期间保存程序时所用的内存。
数据空间技术
不存储,重新计算。 如果我们在需要某一给定对象的任何时候,都对其进行重新计算而不保存,那么保存该对象所需的空间就可以急剧地减少。此方[……]
在本章的第一部分,作者通过一个具体事例引出了代码调优的主题,也交代了调优的基本步骤:监视程序的性能-研究时间占用最多的代码段/函数-针对具体的代码段进行改进。在这个事例中,占用运行时间最多的是malloc函数,最终的改进方法是利用高速缓存优化。
在第二部分,作者通过连续4个问题进一步阐述了[……]
在这一章中,作者对同一个问题依次介绍了4种不同时间复杂度的算法,算法的执行速度依次变得更快。据此阐述了作者的(其实也是被普遍认同的)一个观点:复杂深奥的算法有时可以极大地提高程序性能。(纵然在体系结构领域结论往往是相反的。)
来自一维模式识别的问题。问题的输入是具有n个[……]
本章内容比较有意思,它指导读者在日常生活中或工程计算中通过一些最简单的粗略计算来解决或评价一些具体的问题,比如估算项目完成后能否符合实际情况的需要,程序约需要多大的内存空间以及在大数据集下的与运行时间等。
两个答案比一个答案好。 从不同的角度考虑同一个问题[……]