计算机科学丛书 HZBOOKS 华章教育 Mc 原书第2版 Graw Hill Education 数据结构、算法与应用 C++语言描述 【美】萨特吉·萨尼（Sartaj Sahni）著 王立柱刘志红译 DataStructures,Algorithms and Applications in C++ Second Edition DATA STRUCTURES ALGORITHMS,AND APPLICATIONS IN C++ SECONDEDITION SAHNI 机械工业出版社 China Machine Press 数据结构、算法与应用C++语言描述原书第2版 Data Structures,Algorithms,andApplicationsin C++ SecondEdition 《数据结构、算法与应用一C++语言描述》 勺数据结构教科书的第2版。它完整地包含了基本 数据结构的内容，是CS2课程的理想用书。作者SartajSahni通过循循善诱的讲解、直观具体的讨论和基于现实 的应用，让读者轻松、愉快地学习。新版书着重利用标准模板库（STL)，把书中开发的数据结构和算法与相应的 STL实现方法相互关联。本书还增加了很多新的实例和练习题 书中的应用实例是它的特色。Sahni博士为每一个数据结构和算法都提供了若干个应用实例，涉及排序 压缩编码和图像处理等多个方面。这些实例把概念和应用结合在一起，使理论与实践统一，从而让概念容易理 解，使学生增加学习动力和兴趣。 习题，包括理解题和简单的编程题和工程设计题）。除此之外，本书的配套网站上包含书中的所有程序、示例 数据、运行结果、部分练习的解答和带有结果的示例测试 作者简介 Sartaj Sahni 佛罗里达大学计算机与信息科学工程系杰出教授，欧洲科学院院士，美国电 气和电子工程师协会（IEEE）、美国计算机协会（ACM）、美国科学促进会（AAAS）和明尼苏达超级 计算机研究所的成员，坎普尔印度理工学院（IIT）的杰出校友。Sahni博士获得1997年IEEE计 算机分会的TaylorL.Booth教育奖，2003年IEEE计算机分会的W.WallaceMcDowell奖和2003 年ACM的KarlKarlstrom杰出教育家奖。他目前还担任ACM《ComputingSurveys》期刊的总编 辑，还是17个期刊编委会成员。他在坎普尔印度理工学院获得电子工程学士学位，在康奈尔大 学获得计算机科学硕士和博士学位，发表过250多篇论文，编写了15本教科书，研究成果所涉及 的领域包括有效算法的设计与分析、并行计算、互联网、自动化设计和医用算法 上架指导：计算机数据结构 raw Hill Education www.mheducation.com 投稿热线：（010)88379604 www.hzbook.com 客服热线：（010）8837899188361066 www.china-pub.com 917871111496007 购书热线：（010）68326294 88379649 6899525 www.hzmedia.com.cn 定价：79.00元 设计 锡彬 计算机科学丛 原书第2版 数据结构、算法与应用 C++语言描述 [美］萨特吉·萨尼（SartajSahni）著 王立柱刘志红 译 Data Structures,Agorithms. andApplicafioneiniC++ seventh Edition DADINUCIURES, ALGORITHMS,AND APPLICATIONSIN C++ SECONO EDITION SAHNI O机械工业出版社 ChinaMachinePress 图书在版编目（CIP）数据 数据结构、算法与应用：C++语言描述（原书第2版）/（美）萨尼（Sahni，S.）著；王立柱， 刘志红译.一北京：机械工业出版社，2015.3 （计算机科学丛书） 书名原文：DataStructures，Algorithms，andApplicationsinC++，SecondEdition ISBN978-7-111-49600-7 I.数I.①萨.·②王③刘III.①数据结构 ②算法分析③C语言-程序设 计IV.①TP311.12②TP312 中国版本图书馆CIP数据核字（2015）第047638号 本书版权登记号：图字：01-2011-3946 Sartaj Sahni:DataStructures,Algorithms,and Applications in C++,Second Edition(ISBN 978-0-929306-32-2）， Copyright2005byMcGraw-Hill Education. All rights reserved.No part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including without limitation photocopying recording, taping, or any database,information or retrieval system, without the prior written permission of thepublisher. This authorized Chinesetranslation edition is jointlypublishedby McGraw-Hill Education and China Machine Press.This edition is authorized for sale in the People's Republic of China only,excluding Hong Kong,Macao SARand Taiwan Copyright2015byMcGraw-Hill EducationandChina MachinePress. 版权所有。未经出版人事先书面许可，对本出版物的任何部分不得以任何方式或途径复制或传播， 包括但不限于复印、录制、录音，或通过任何数据库、信息或可检索的系统。 本授权中文简体字翻译版由麦格劳－希尔（亚洲）教育出版公司和机械工业出版社合作出版。此版 本经授权仅限在中华人民共和国境内（不包括香港特别行政区、澳门特别行政区和台湾）销售。 版权①2015由麦格劳－希尔（亚洲）教育出版公司与机械工业出版社所有。 本书封面贴有McGraw-HillEducation公司防伪标签，无标签者不得销售。 全书共分三个部分。第一部分从第1章到第4章，旨在复习C++程序设计的概念以及程序性能的 分析和测量方法。第二部分从第5章到第16章，研究数据结构，包括线性表的数组描述和链式描述， 以及用这两种描述方法描述的数组和矩阵、栈、队列、字典、二叉树、优先级队列、竞赛树和图等数据 结构。第三部分从第17章到第21章，研究常用算法，包括贪婪算法、分而治之算法、动态规划、回溯 算法和分支定界算法。 本书内容广博、组织合理、论述清晰、循序渐进，每章包含丰富的习题，对程序性能的分析和测量 系统且细致，不仅是数据结构和算法的经典教材，而且是计算机科学与工程领域的理想参考书。 出版发行：机械工业出版社（北京市西城区百万庄大街22号邮政编码：100037） 责任编辑：朱秀英 责任校对：股虹 印 刷：北京诚信伟业印刷有限公司 版 次：2015年4月第1版第1次印刷 开 本：185mm×260mm1/16 印 张：35 号：ISBN978-7-111-49600-7 定 价：79.00元 凡购本书，如有缺页、倒页、脱页，由本社发行部调换 客服热线：（010）88378991 88361066 投稿热线：（010）88379604 购书热线：（010）68326294 ：88379649 68995259 读者信箱：[email protected] 版权所有·慢权必究 封底无防伪标均为盗版 本书法律顾问：北京大成律师事务所韩光/邹晓东 厂出版者的话 Data Structurs,gorithm,and Applicatons inC++,Sondditio 文艺复兴以来，源远流长的科学精神和逐步形成的学术规范，使西方国家在自然科学的 各个领域取得了垒断性的优势；也正是这样的优势，使美国在信息技术发展的六十多年间名 家辈出、独领风骚。在商业化的进程中，美国的产业界与教育界越来越紧密地结合，计算机 学科中的许多泰山北斗同时身处科研和教学的最前线，由此而产生的经典科学著作，不仅擎 划了研究的范畴，还揭示了学术的源变，既遵循学术规范，又自有学者个性，其价值并不会 因年月的流逝而减退。 近年，在全球信息化大潮的推动下，我国的计算机产业发展迅猛，对专业人才的需求日 益迫切。这对计算机教育界和出版界都既是机遇，也是挑战；而专业教材的建设在教育战略 上显得举足轻重。在我国信息技术发展时间较短的现状下，美国等发达国家在其计算机科学 发展的几十年间积淀和发展的经典教材仍有许多值得借鉴之处。因此，引进一批国外优秀计 算机教材将对我国计算机教育事业的发展起到积极的推动作用，也是与世界接轨、建设真正 的世界一流大学的必由之路。 机械工业出版社华章公司较早意识到“出版要为教育服务”。自1998年开始，我们 就将工作重点放在了述选、移译国外优秀教材上。经过多年的不邂努