本书是为计算机科学专业二级教程编写的，在美国许多大学称之为CS 2课程。本书继承了上一版关注基本数据结构的特点，将授课**放在基本数据类型的规范说明、设计、实现和使用上。此外，本书还涵盖了重要的编程技术，并提供各自独立的抽象技术、面向对象编程、大O时间分析算法和排序等内容。本书的设计非常灵活，学生可以根据自身需要将学习的**放在面向对象、递归以及排序上，以加快学习的进程 　 本书适合作为高等院校计算机及相关专业本科学生的教材，也是一本技术含量很高的专业参考书。

第1章软件开发阶段1.1.1规范说明.设计和实现21.1.1概念设计:问题分解31.1.2前置条件和后置条件41.1.3使用其他程序员提供的函数61.1.4有关ANSI/ISOC++标准的实现问题71.1.5自测习题121.2运行时间分析131.2.1台阶计数问题131.2.2大O表示法171.2.3C++函数的时间分析181.2.4*坏情况.平均情况和*好情况下的时间分析201.2.5自测习题201.3测试和调试211.3.1选择测试数据211.3.2边界值221.3.3完全代码测试221.3.4调试231.3.5自测习题231.4本章小结241.5自测习题答案24第2章抽象数据类型和C++类272.1类和成员282.1.1编程示例:节流阀类282.1.2使用类312.1.3节流阀类的示范程序332.1.4实现成员函数342.1.5自测习题372.2构造函数372.2.1节流阀类的构造函数382.2.2修改节流阀类的成员函数402.2.3内联成员函数412.2.4自测习题422.3使用命名空间.头文件和实现文件422.3.1创建命名空间422.3.2头文件432.3.3实现文件472.3.4使用命名空间中的数据项492.3.5自测习题512.4类和参数522.4.1编程示例:point类522.4.2默认参数552.4.3参数572.4.4当函数返回值的类型是类时622.4.5自测习题632.5操作符重载642.5.1重载二元比较操作符642.5.2重载二元算术操作符652.5.3重载输出和输入操作符662.5.4友元函数692.5.5Point类——内容汇总702.5.6操作符重载的总结722.5.7自测习题732.6本章小结732.7自测习题答案742.8编程项目77第3章容器类853.1包类853.1.1包类——规范说明863.1.2包类——文档说明923.1.3包类——示范程序933.1.4包类——设计953.1.5类的不变式963.1.6包类——实现973.1.7包类——内容汇总1033.1.8包类——测试1063.1.9包类——分析1073.1.10自测习题1083.2编程项目:序列类1093.2.1序列类——规范说明1093.2.2序列类——文档说明1123.2.3序列类——设计1143.2.4序列类——实现的伪代码1153.2.5自测习题1173.3交互式测试程序1173.4本章小结1223.5自测习题答案1233.6编程项目125第4章指针和动态数组1314.1指针和动态内存1314.1.1指针变量1324.1.2使用指针的赋值操作符1344.1.3动态变量和new操作符1354.1.4使用new分配动态数组1364.1.5堆和bad_alloc异常1384.1.6操作符delete1394.1.7自测习题1404.2指针和数组作为参数1414.2.1指针作为值参数1414.2.2数组参数1434.2.3指针或数组作为常量参数1444.2.4指针作为引用参数1454.2.5自测习题1474.3用动态数组实现的包类1494.3.1指针成员变量1504.3.2成员函数按需分配动态内存1514.3.3值语义1544.3.4析构函数1564.3.5修改后的包类——类定义1574.3.6修改后的包类——实现1594.3.7修改后的包类——内容汇总1634.3.8自测习题1654.4有关动态类的规定1664.4.14条规则1664.4.2复制构造函数的特殊重要性1664.4.3自测习题1674.5编程项目:字符串类1674.5.1以null终结的字符串1674.5.2初始化字符串变量1684.5.3空字符串1684.5.4读写字符串变量1694.5.5函数strcpy1694.5.6函数strcat1704.5.7函数strlen1704.5.8函数strcmp1714.5.9字符串类——规范说明1714.5.10字符串类——设计1754.5.11字符串类——实现1754.5.12字符串类的示范程序1774.5.13串接输出操作符1784.5.14声明常量对象1794.5.15产生构造函数的转换1794.5.16在表达式中使用重载的操作符1804.5.17本文的字符串类与C++库中的字符串类1804.5.18自测习题1804.6编程项目:多项式1804.7本章小结1844.8自测习题答案1844.9编程项目186第5章链表1895.1链表的基本节点类1895.1.1为节点声明类1905.1.2在链表节点中使用typedef语句1915.1.3头指针和尾指针1915.1.4空指针1925.1.5头指针或尾指针为NULL时的含义1935.1.6节点构造函数1935.1.7节点成员函数1945.1.8成员选择操作符1955.1.9自测习题1985.2链表工具包1995.2.1链表工具包——头文件1995.2.2计算链表的长度2005.2.3链表的参数2035.2.4在链表头插入一个新节点2045.2.5在非头节点处插入一个新节点2065.2.6在链表中查找数据项2105.2.7在链表中根据节点的位置寻找节点2115.2.8复制链表2125.2.9从链表头删除节点2155.2.10删除链表中不在头部的节点2165.2.11清除链表2175.2.12链表工具包——内容汇总2185.2.13使用链表工具包2225.2.14自测习题2225.3用链表实现的包类2235.3.1第三个包——规范说明2235.3.2第三个包——类定义2235.3.3如何匹配包的value_type和节点的value_type2265.3.4在类中使用动态内存应当遵循的规则2275.3.5第三个包类——实现2275.3.6第三个包类——内容汇总2345.3.7自测习题2365.4编程项目:用链表实现的序列类2375.4.1修改的序列类——设计建议2375.4.2修改后的序列类——值语义2385.4.3自测习题2395.5动态数组.链表和双向链表2395.5.1做出抉择2415.5.2自测习题2415.6本章小结2415.7自测习题答案2425.8编程项目246第6章利用模板.迭代器和STL进行软件开发2516.1模板函数2516.1.1模板函数的语法2536.1.2使用模板函数2536.1.3模板函数——交换两个值2556.1.4模板函数的参数匹配2566.1.5模板函数——在数组中寻找*大项2576.1.6模板函数——在排序数组中插入一个数据项2586.1.7自测习题2606.2模板类2606.2.1模板类的语法2606.2.2关于模板实现文件的其他内容2626.2.3模板类成员函数的参数匹配2676.2.4使用模板类2676.2.5编故事程序的细节2706.2.6自测习题2706.3标准模板类及其迭代器2716.3.1多集模板类2716.3.2多集成员2726.3.3迭代器和[…)模式2726.3.4测试迭代器的等同性2746.3.5其他多集操作2746.3.6集合算法2756.3.7无效的迭代器2766.3.8迭代器的标准类别2776.3.9数组的迭代器2786.3.10标准模板库列表类2796.3.11自测习题2806.4节点模板类2806.4.1返回引用类型的函数2816.4.2将引用返回值复制到别处时发生的情况2836.4.3成员函数data目前需要两个版本2836.4.4新节点的头文件和实现文件2836.4.5自测习题2906.5链表的迭代器2916.5.1节点迭代器2916.5.2节点迭代器源自std::iterator2936.5.3节点迭代器的私有成员变量2936.5.4节点迭代器——构造函数2936.5.5节点迭代器——*操作符2936.5.6节点迭代器——操作符++的两个版本2946.5.7节点迭代器——相等和不相等的比较2956.5.8常量集合的迭代器2966.5.9自测习题2976.6含有迭代器的包模板类的链表版本2986.6.1如何为容器类提供迭代器2986.6.2包迭代器299..6.6.3将迭代器定义在包中的原因2996.6.4自测习题3066.7本章小结和5个包的总结3066.8自测习题答案3076.9编程项目311第7章堆栈3137.1堆栈和STL堆栈的简介3137.1.1标准库的堆栈类3157.1.2编程示例:翻转单词3167.1.3自测习题3167.2堆栈的应用3177.2.1编程示例:括号的平衡3177.2.2编程示例:算术表达式求值3197.2.3算术表达式求值——规范说明3197.2.4算术表达式求值——设计3197.2.5算术表达式求值——实现3257.2.6计算器程序使用的函数3257.2.7算术表达式求值——测试与分析3257.2.8算术表达式求值——改进3267.2.9自测习题3267.3堆栈类的实现3277.3.1堆栈的数组实现3277.3.2堆栈的链表实现3307.3.3Koenig查找3337.3.4自测习题3337.4更复杂的堆栈应用3347.4.1后缀表达式求值3347.4.2将中缀表示法转换成后缀表示法3367.4.3在中缀表达式中使用优先级规则3387.4.4中缀转换为后缀的正确性3407.4.5自测习题3417.5本章小结3427.6自测习题答案3427.7编程项目344第8章队列3498.1队列和STL队列的简介3498.1.1标准库的队列类3508.1.2队列的使用3508.1.3自测习题3528.2队列的应用3528.2.1编程示例:识别回文3528.2.2自测习题3558.2.3编程示例:洗车模拟3558.2.4洗车模拟——规范说明3558.2.5洗车模拟——设计3558.2.6洗车模拟——实现洗车类3588.2.7洗车模拟——实现模拟函数3638.2.8自测习题3658.3队列类的实现3658.3.1队列的数组实现3658.3.2有关队列中循环数组实现的讨论3698.3.3队列的链表实现3718.3.4实现细节3728.3.5自测习题3778.4优先队列3778.4.1如何指定优先级3788.4.2标准库的优先队列类3788.4.3优先队列类——实现思想3798.4.4自测习题3798.5堆栈.队列和优先队列类的引用返回值3798.6本章小结3808.7自测习题答案3808.8编程项目381第9章递归思想3859.1递归函数3859.1.1递归思想的**个例子3859.1.2跟踪递归调用3879.1.3编程示例:write_vertical的一个扩展3889.1.4深入分析递归3899.1.5成功递归函数的一般形式3929.1.6自测习题3929.2递归的研究:分形和迷宫3939.2.1编程示例:产生随机分形3939.2.2用于产生随机分形的函数——规范说明3959.2.3分形函数的设计和实现3969.2.4如何显示随机分形3989.2.5编程示例:穿越迷宫3999.2.6穿越迷宫——规范说明3999.2.7穿越迷宫——设计4019.2.8穿越迷宫——实现4019.2.9运用回溯穷举搜索的递归模式4039.2.10编程示例:玩具熊游戏4049.2.11自测习题4069.3推导递归4069.3.1如何确保没有无限递归4089.3.2归纳推导递归函数的正确性4109.3.3自测习题4119.4本章小结4119.5自测习题答案4129.6编程项目414第10章树41910.1树的简介41910.1.1二叉树41910.1.2二叉分类树42210.1.3一般树42210.1.4自测习题42310.2树的表示法42410.2.1完全二叉树的数组表示法42410.2.2使用节点类表示二叉树42710.2.3自测习题42810.3二叉树节点类42910.3.1编程示例:猜动物43210.3.2动物猜测程序——设计和实现43410.3.3动物猜测程序——改进43810.3.4自测习题44110.4树的遍历44110.4.1二叉树的遍历44110.4.2从树的节点中输出数据44510.4.3遍历中的问题44610.4.4函数作为参数44710.4.5apply函数的一个模板版本44810.4.6使apply模板函数更具有通用性44910.4.7树遍历的模板函数45010.4.8自测习题45110.5二叉搜索树45810.5.1二叉搜索树存储机制45810.5.2第6个包——类定义46210.5.3第6个包——某些简单函数的实现46210.5.4计算某个元素在二叉搜索树中出现的次数46210.5.5添加一个新元素到二叉搜索树中46310.5.6从二叉搜索树中移除某个元素46410.5.7二叉搜索树的组合操作符46710.5.8时间分析和迭代器46910.5.9自测习题46910.6本章小结46910.7自测习题答案47010.8编程项目473第11章树项目47911.1堆47911.1.1堆的存储规则47911.1.2使用堆结构实现的优先队列ADT48011.1.3插入新项48011.1.4删除项48211.1.5自测习题48411.2B树48411.2.1非平衡树的问题48411.2.2B树的规则48511.2.3B树的一个示例48611.2.4B树实现的集合ADT48711.2.5在B树中查找项49111.2.6在B树中插入项49311.2.7B树的松散插入操作49311.2.8修正子节点多余项的私有成员函数49511.2.9回到成员函数Insert49611.2.10采用自顶向下方法设计49711.2.11从B树中删除项49811.2.12B树的松散删除操作49911.2.13解决子节点项短缺问题的私有成员函数50111.2.14从B树中删除*大的项50311.2.15外部B树50511.2.16自测习题50511.3树.日志和时间分析50611.3.1二叉搜索树的时间分析50611.3.2堆的时间分析50711.3.3对数运算50811.3.4对数级算法50911.3.5自测习题51011.4本章小结51011.5自测习题答案51011.6编程项目513第12章查找51512.1顺序查找和二分查找51512.1.1顺序查找51512.1.2顺序查找——分析51612.1.3二分查找51712.1.4二分查找——设计51812.1.5二分查找——分析52012.1.6标准库查找函数52312.1.7用于有序域的函数52312.1.8用于无序域的函数52512.1.9STL查找函数52612.1.10自测习题52612.2开地址散列52612.2.1散列简介52612.2.2表类——声明52912.2.3表类——设计53012.2.4表ADT——实现53312.2.5选择散列函数来减少冲突53812.2.6再散列减少聚类53812.2.7自测习题54012.3链式散列54012.3.1链式散列54012.3.2自测习题54212.4散列的时间分析54212.4.1散列表的装填因子54212.4.2自测习题54512.5程序设计:使用STL向量的表类54512.5.1新表类54512.5.2在新表类中使用向量54512.5.3常量模板参数54512.5.4函数模板参数54612.5.5实现新表类54612.5.6自测习题54712.6STL中的匹配和多重匹配54712.7本章小结54812.8自测习题答案54912.9编程项目552第13章排序55513.1二次排序算法55513.1.1选择排序——规范说明55513.1.2选择排序——设计55613.1.3选择排序——实现55813.1.4选择排序——分析56013.1.5插入排序56113.1.6插入排序——分析56413.1.7自测习题56613.2递归排序算法56713.2.1使用递归的分治法56713.2.2合并排序56913.2.3合并函数57113.2.4动态内存在合并排序中的应用57513.2.5合并排序——分析57513.2.6文件的合并排序57713.2.7快速排序57713.2.8partition函数57913.2.9快速排序——分析58113.2.10快速排序——选择一个好的基准元素58313.2.11自测习题58313.3使用堆的O(nlogn)算法58413.3.1堆排序58413.3.2构建堆58913.3.3向下重排59013.3.4堆排序——分析59113.3.5自测习题59213.4使用库函数排序和随机访问迭代器59213.4.1原始Cqusort函数59213.4.2STL排序函数59313.4.3使用迭代器编写一个排序函数59313.5本章小结59413.6自测习题答案59513.7编程项目597第14章派生类和继承60114.1派生类60114.1.1如何声明派生类60314.1.2派生类的自动构造函数60414.1.3使用派生类60514.1.4派生类的自动赋值操作符60614.1.5派生类的自动析构函数60714.1.6覆盖继承的成员函数60714.1.7自测习题60814.2仿真生态系统60814.2.1实现部分生物对象层次60914.2.2organism类60914.2.3animal类:具有新私有成员变量的派生类61214.2.4如何为派生类提供新的构造函数61214.2.5animal类的其他成员函数61414.2.6自测习题61714.2.7Herbivore类61814.2.8池塘生活仿真程序62014.2.9池塘生活——实现细节62314.2.10使用池塘模型62414.2.11动态内存的使用62514.2.12自测习题62514.3虚拟成员函数和game类62514.3.1game类简介62614.3.2受保护的成员62914.3.3虚拟成员函数62914.3.4虚拟析构函数63014.3.5游戏类的受保护虚拟成员函数63014.3.6玩ConnectFour游戏的派生类63114.3.7ConnectFour游戏类的私有成员变量63114.3.8ConnectFour的构造函数和重启函数63314.3.9三个处理游戏状态的ConnectFour函数63314.3.10三个处理移动的ConnectFour函数63414.3.11Clone函数63414.3.12编写派生自game类的游戏63514.3.13使用minimax的游戏类的play算法63514.3.14自测习题63814.4本章小结63814.5进阶阅读63914.6自测习题答案63914.7编程项目643第15章图64515.1图的定义64515.1.1无向图64515.1.2有向图64815.1.3图的更多术语64915.1.4航线的例子65015.1.5自测习题65015.2图的实现65115.2.1使用邻接矩阵表示图65115.2.2使用二维数组存储邻接矩阵65215.2.3使用边列表表示图65215.2.4使用边集表示图65315.2.5哪种表示方法*好65315.2.6编程示例:标签图类65415.2.7用于增加顶点和边的成员函数65515.2.8标签图类——重载下标操作符65515.2.9下标操作符的常量版本65615.2.10标签图类——函数neighbors65715.2.11标签图类——实现65715.2.12自测习题65715.3图的遍历66215.3.1深度优先搜索66315.3.2宽度优先搜索66615.3.3深度优先搜索——实现66815.3.4宽度优先搜索——实现66915.3.5自测习题66915.4路径算法67115.4.1判断某条路径是否存在67115.4.2具有加权边的图67215.4.3*短距离算法67215.4.4*短路径算法68015.4.5自测习题68115.5本章小结68115.6自测习题答案68115.7编程项目683附录AASCII字符集类687附录B大O表达式689附录C操作符的优先顺序693附录D命令行编译和链接695附录E使用旧式编译器699附录FC++的输入和输出703附录G选择库函数711附录H标准模板类简介715附录Iuseful函数的工具箱725附录J基本格式指南729附录K下载GNU编译器和软件731附录L异常处理733...

本书是为计算机科学专业二级教程编写的,在美国许多大学称之为CS 2课程。本书继承了上一版关注基本数据结构的特点,将授课**放在基本数据类型的规范说明、设计、实现和使用上。此外,本书还涵盖了重要的编程技术,并提供各自独立的抽象技术,面向对象编程,大O时间分析算法和排序等内容。本书的设计非常灵活,学生可以根据自身需要将学习的**放在面向对象、递归以及排序上,以加快学习的进程。.
本书适合作为高等院校计算机及相关专业本科学生的教材,也是一本技术含量很高的专业参考书。
本书特色:..
◆全面介绍了标准模板库(STL)
◆全面回顾了C++语法和OOP概念;适合任何层次的学生
◆代码已经更新并经过测试,符合*新的ANSI/ISO C++标准
◆每一章中都精心设置自测习题和编程项目...