Data Structures and Algorithms in Python

This book is based upon the book Data Structures and Algorithms in Java by Goodrich and Tamassia, and the related Data Structures and Algorithms in C++ by Goodrich, Tamassia, and Mount. However, this book is not simply a translation of those other books to Python. In adapting the material for this b
Data Structures and Algorithms in Python Michael T. Goodrich Department of computer Science University of California, Irvine Roberto tamassia Department of Computer Science Brown University Michael H. Goldwasser Department of Mathematics and Computer Science Saint louis university WILEY vp Publisher Don Fowley EXECUTIVE EDITOR Beth lang golub EDITORIAL PROGRAM ASSISTANT Katherine willis MARKETING MANAGER Christopher ruel DESIGNER Kenji ngieng SENIOR PRODUCTION MANAGER Janis soo ASSOCIATE PRODUCTION MANAGER Joyce Poh This book was set in LA tEX by the authors. Printed and bound by courier Westford The cover was printed by courier westford This book is printed on acid free paper Founded in 1807, John Wiley sons, InC. has been a valued source of knowledge and understanding for more than 200 years, helping people around the world meet their needs and fulfill their aspirations. Our company is built on a foundation of principles that include responsibility to the communities we serve and where we live and work. In 2008, we launched a Corporate Citizenship Initiative, a global effort to address the environmental, social, economic, and ethical challenges we face in our business. Among the issues we are addressing are carbon impact, paper specifications and procurement, ethical conduct within our business and among our vendors, and community and charitable support. For more information, please visit our website www.wiley.com/go/citizenship Copyright o 2013 John Wiley sons, Inc. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except as permitted under Sections 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the publisher, or authorization through payment of the appropriate per copy fee to the Copyright Clearance Center, InC. 222 RosewoodDrive,Danvers,Mao1923,websitewww.copyright.comRequeststothePublisherforpermission should be addressed to the Permissions Department, John Wiley sons, Inc, 1ll River Street, Hoboken, Nj070305774,(201)7486011,fax(201)7486008,websitehttp:/www.wiley.com/go/permissions Evaluation copies are provided to qualified academics and professionals for review purposes only, for use in their courses during the next academic year. These copies are licensed and may not be sold or transferred to a third party. Upon completion of the review period, please return the evaluation copy to Wiley. Return instructionsandafreeofchargereturnmailinglabelareavailableatwww.wiley.com/go/returnlabel.Ifyou have chosen to adopt this textbook for use in your course, please accept this book as your complimentary desk copy. Outside of the United States, please contact your local sales representative Printed in the United States of america 10987654321 To Karen Paul. anna and jack Michael. goodrich To Isabel Roberto tamassia To Susan, Calista, and maya Michael h. goldwasser Preface The design and analysis of efficient data structures has long been recognized as a vital subject in computing and is part of the core curriculum of computer science and computer engineering undergraduate degrees. Data Structures and algorithms in Python provides an introduction to data structures and algorithms, including their design, analysis, and implementation. This book is designed for use in a beginning level data structures course, or in an intermediatelevel introduction to algorithms course. We discuss its use for such courses in more detail later in this preface To promote the development of robust and reusable software, we have tried to take a consistent objectoriented viewpoint throughout this text. One of the main ideas of the objectoriented approach is that data should be presented as being en apsulated with the methods that access and modify them. That is, rather than simply viewing data as a collection of bytes and addresses, we think of data ob jects as instances of an abstract data type(ADt), which includes a repertoire of methods for performing operations on data objects of this type. We then empha size that there may be several different implementation strategies for a particular ADT, and explore the relative pros and cons of these choices. We provide complete Python implementations for almost all data structures and algorithms discussed and we introduce important objectoriented design patterns as means to organize those implementations into reusable components Desired outcomes for readers of our book include that They have knowledge of the most common abstractions for data collections (e.g., stacks, queues, lists, trees, maps) They understand algorithmic strategies for producing efficient realizations of common data structures They can analyze algorithmic performance, both theoretically and experi mentally, and recognize common tradeoffs between competing strategies They can wisely use existing data structures and algorithms found in modern programming language libraries They have experience working with concrete implementations for most foun dational data structures and algorithms e They can apply data structures and algorithms to solve complex problems In support of the last goal, we present many example applications of data structures throughout the book, including the processing of file systems, matching of tags in structured formats such as HTML, simple cryptography, text frequency analy sis, automated geometric layout, Huffman coding, DNA sequence alignment, and search engine indexing Preface Book features This book is based upon the book Data Structures and Algorithms in Java by Goodrich and Tamassia, and the related Data Structures and algorithms in C++ by Goodrich, Tamassia, and Mount. However, this book is not simply a translation of those other books to python In adapting the material for this book, we have significantly redesigned the organization and content of the book as follows e The code base has been entirely redesigned to take advantage of the features of python, such as use of generators for iterating elements of a collection e Many algorithms that were presented as pseudocode in the Java and C++ versions are directly presented as complete Python code. e In general, adts are defined to have consistent interface with pythons built in data types and those in pythons collections module Chapter 5 provides an indepth exploration of the dynamic arraybased un derpinnings of pythons builtin list tuple and str classes New appendix a serves as an additional reference regarding the functionality of the str class e Over 450 illustrations have been created or revised e New and revised exercises bring the overall total number to 750 Online resources This book is accompanied by an extensive set of online resources, which can be found at the following Web site www.wiley.com/college/goodrich Students are encouraged to use this site along with the book, to help with exer cises and increase understanding of the subject. Instructors are likewise welcome to use the site to help plan, organize, and present their course materials. Included on this Web site is a collection of educational aids that augment the topics of this book. for both students and instructors because of their added value. some of these online resources are pass word protected For all readers, and especially for students, we include the following resources All the python source code presented in this book PDF handouts of Powerpoint slides(fourperpage) provided to instructors a database of hints to all exercises, indexed by problem number For instructors using this book, we include the following additional teaching aids e Solutions to hundreds of the book's exercises e Color versions of all figures and illustrations from the book Slides in Powerpoint and PDF(oneperpage)format The slides are fully editable, so as to allow an instructor using this book full free dom in customizing his or her presentations. All the online resources are provided at no extra charge to any instructor adopting this book for his or her course Presa Contents and Organization The chapters for this book are organized to provide a pedagogical path that starts with the basics of python programming and objectoriented design We then add foundational techniques like algorithm analysis and recursion. In the main portion of the book, we present fundamental data structures and algorithms, concluding with a discussion of memory management(that is, the architectural underpinnings of data structures). Specifically, the chapters for this book are organized as follows 1. Python Primer 2. ObjectOriented Programming 3. Algorithm Analysis 4. Recursion 5. ArrayBased Sequences 6. Stacks, Queues, and deques 7. Linked Lists 8. Trees 9. Priority Queues 10. Maps, Hash Tables, and skip lists 11. Search trees 12. Sorting and selection 13. Text Processing 14. Graph algorithms 15. Memory Management and BTrees A. Character Strings in Python B. Useful mathematical facts A more detailed table of contents follows this preface, beginning on page xi Prerequisites We assume that the reader is at least vaguely familiar with a highlevel program ming language such as c, c++, python or Java, and that he or she understands the main constructs from such a highlevel language, including e Variables and expressions Decision structures(such as ifstatements and switchstatements) Iteration structures(for loops and while loops) Functions(whether standalone or objectoriented methods) For readers who are familiar with these concepts, but not with how they are ex pressed in Python, we provide a primer on the python language in Chapter l Still this book is primarily a data structures book, not a Python book; hence, it does not give a comprehensive treatment of python vl Preface We delay treatment of objectoriented programming in Python until Chapter 2 This chapter is useful for those new to Python, and for those who may be familiar with Python, yet not with objectoriented programming In terms of mathematical back ground, we assume the reader is somewhat famil iar with topics from highschool mathematics. Even So, in Chapter 3, we discuss the seven mostimportant functions for algorithm analysis. In fact, sections that use something other than one of these seven functions are considered optional, and are indicated with a star(*). We give a summary of other useful mathematical facts, including elementary probability, in Appendix b Relation to Computer Science curriculum To assist instructors in designing a course in the context of the IEEE/ACM 2013 Computing Curriculum, the following table describes curricular knowledge units that are covered within this book Knowledge Unit Relevant material AL/Basic analysis Chapter 3 and Sections 4.2& 12.2.4 AL/Algorithmic Strategies Sections12.2.1,13.2.1,13.3,&13.4.2 AL/Fundamental Data Structures Sections 4.1.3, 5.5.2, 9.4.1, 9.3, 10.2, 11.1, 13.2, and algorithms Chapter 12 much of Chapter 14 AL/Advanced data Structures Sections5.3,10.4,11.2 through11.6,12.3.1, 13.5,14.5.1,&15.3 AR/Memory System Organization Chapter 15 and Architecture DS/Sets, Relations and Functions Sections 10.5. 1, 10.5.2, &9.4 DS/Proof Techniques Sections3.4,4.2,53.2,9.3.6,&12.4.1 DS/Basics of Counting Sections 2.4.2, 6.2.2, 12.2.4, 8.2.2& appendix b DS/Graphs and Trees Much of Chapters 8 and 14 DS/Discrete Probability Sections1.11.1.10.2.10.4.2.&12.3.1 PL/ObJectOriented Programming Sectio. of the book, yet especially Chapter 2 and PL/Functional Programming Section 1.10 SDF/Algorithms and Design Sections 2.1, 3.3, &12.2.1 SDF/Fundamental Programming Chapters 1 &4 Concepts SDF/Fundamental Data Structures Chapters 6& 7, appendix a, and Sections 1. 2.1 5.2,5.4,9.1,&10.1 SDF/Developmental methods Sections 1.7& 2.2 SE/Software Design Sections 2.1 & 2.1.3 Mapping IEEE/ACM 2013 Computing Curriculum knowledge units to coverage in this book

20190529
 7.84MB
Data Structures and Algorithms in Python.pdf
20180421python版的数据结构和算法，python版的数据结构和算法
Data Structures and Algorithms in Python.pdf下载_course
20200705这是一本基于python的数据结构与算法教程（英文版），python入门中级读物。 相关下载链接：//download.csdn.net/download/weixin_44673658/112866
 5.89MB
Data Structure and Algorithms in Python
20190404《Data Structure and Algorithms in Python》高清PDF版！！！很不错的一本Python数据结构书，如果感兴趣，可以阅读，锻炼英文水平！！！
 data structure and algorithms in python[solutions to exercises in Chapter 2] 143220180526R2.5 Use the techniques of Section 1.7 to revise the charge and make payment methods of the CreditCard class to ensure that the caller sends a number as a parameter.class CreditCard: """A consumer ...
 6.46MB
Data Structure and Algorithms in Python.pdf
20180122About the Authors Michael Goodrich received his Ph.D. in Computer Science from Purdue University in
 6.60MB
Data Structures and Algorithms in Python(Wiley,2013)
20150401Based on the authors' market leading data structures books in Java and C++, this textbook offers a c
 6.4MB
Data Structures and Algorithms in Python（文字版英文pdf+习题提示+示例源码）
20180622《数据结构与算法：Python描述》的英文版pdf+习题提示+示例源码
Data Structures and Algorithms in Python.pdf 英文原版. Python数据结构和算法下载_course
20180730Based on the authors’ market leading data structures books in Java and C++, this textbook offers a c
 61.4MB
Data Structures and Algorithms in python
20190419数据结构算法python语言实现原版英文，整理不易，高清无水印，希望大家多多支持。
 8.14MB
Data Structures and Algorithms in Python .pdf
20171031利用python实现数据结构与常见的算法，涵盖面广，讲解详细
 数据结构与算法Python语言实现《Data Structures & Algorithms in Python》手写课后答案第七章 18020200726第七章 本章重点为灵活使用链表，深度理解位置链表 习题代码如下(部分代码引用书中源代码，源代码位置目录在第二章答案中介绍) # 本节默认队列使用书中源代码队列 # 单链表应该以None结尾,并未给出链表示列 # 简述：next为共有节点，可公共访问，first()返回头节点,没有保存尾节点 # 7.1 def text1(link): '''yield every node since after the second node from a link ''' node = lin
Data Structures and Algorithms in Python下载_course
20200812Based on the authors' market leading data structures books in Java and C++, this book offers a compr
 6.0MB
Data Structures and Algorithms in Python 无水印pdf
20171003Data Structures and Algorithms in Python 英文无水印pdf pdf所有页面使用FoxitReader和PDFXChangeViewer测试都可以打开 本资源转
 5.87MB
Data Structures and Algorithms in Python2013
20180917Data Structures and Algorithms in Python2013
 44.51MB
数据结构与算法Data Structures and Algorithms（中文版）高清版.pdf
20170518数据结构与算法Data Structures and Algorithms（中文版）高清版.pdf 个人收集电子书，仅用学习使用，不可用于商业用途，如有版权问题，请联系删除！
 9.50MB
Data Structures and Algorithms with Python 无水印pdf
20171003Data Structures and Algorithms with Python 英文无水印pdf pdf所有页面使用FoxitReader和PDFXChangeViewer测试都可以打开 本资
 17.16MB
Data Structures and Algorithms in Python.pdf 英文原版. Python数据结构和算法
20180729Based on the authors’ market leading data structures books in Java and C++, this textbook offers a c

博客
【AC自动机】P2414 [NOI2011] 阿狸的打字机
【AC自动机】P2414 [NOI2011] 阿狸的打字机

博客
TableauChapter02数据预处理、折线图、饼图
TableauChapter02数据预处理、折线图、饼图

博客
计算几何 点积 叉积 凸包
计算几何 点积 叉积 凸包

下载
关于remixIDE资源
关于remixIDE资源

下载
visual c++ vc修改文件属性中的创建时间,修改时间,访问时间.zip
visual c++ vc修改文件属性中的创建时间,修改时间,访问时间.zip

学院
大数据Hive on MR/TEZ与hadoop的整合应用
大数据Hive on MR/TEZ与hadoop的整合应用

博客
牛客 Rinne Loves Edges 树形dp
牛客 Rinne Loves Edges 树形dp

下载
QT 多文档文本编辑器
QT 多文档文本编辑器

学院
【数据分析随到随学】数据可视化
【数据分析随到随学】数据可视化

学院
ArcGIS Pro2.6和ArcGIS Enterprise学习
ArcGIS Pro2.6和ArcGIS Enterprise学习

学院
彻底学会正则表达式
彻底学会正则表达式

学院
【数据分析随到随学】Hadoop数据分析
【数据分析随到随学】Hadoop数据分析

博客
linux下网卡bonding配置
linux下网卡bonding配置

下载
QT 拼图游戏
QT 拼图游戏

下载
install_flash_player_ax_cn_34_0_0_92离线安装包.zip
install_flash_player_ax_cn_34_0_0_92离线安装包.zip

下载
linux进程的最大线程数 及最大进程数.zip
linux进程的最大线程数 及最大进程数.zip

下载
阿里巴巴大数据工程师必读手册.pdf
阿里巴巴大数据工程师必读手册.pdf

下载
prototype.js使用教程.zip
prototype.js使用教程.zip

下载
html个人简历表格制作
html个人简历表格制作

学院
three.js入门速成
three.js入门速成

下载
一个很不错的visual c++ vc内存池的源码,本人在项目中使用.很有价值.zip
一个很不错的visual c++ vc内存池的源码,本人在项目中使用.很有价值.zip

博客
栈的概念被极大量的运用于各种程序设计之中
栈的概念被极大量的运用于各种程序设计之中

学院
【数据分析随到随学】Hive详解
【数据分析随到随学】Hive详解

博客
QT报make: Circular all ＜ first dependency dropped.错误解决。
QT报make: Circular all ＜ first dependency dropped.错误解决。

学院
Java星选一卡通
Java星选一卡通

学院
Kotlin协程极简入门与解密
Kotlin协程极简入门与解密

下载
linux 内存池三方库 用了他你就不需要自己编写内存池了.zip
linux 内存池三方库 用了他你就不需要自己编写内存池了.zip

博客
剑指offer刷题GZ16合并两个排序的链表
剑指offer刷题GZ16合并两个排序的链表

下载
MTA软件连线使用说明书
MTA软件连线使用说明书

博客
插入的结点的next指针指向下一个结点的方式完成插入操作
插入的结点的next指针指向下一个结点的方式完成插入操作