没有合适的资源?快使用搜索试试~ 我知道了~
首页Python数据结构入门经典指南
"《Python数据结构与算法》是一本经典的IT学习教材,专为Python初学者设计。作者Rance D. Necaise,来自威廉玛丽学院计算机科学系,该书由John Wiley & Sons, Inc.出版,强调了在Python编程语言中理解和应用基础数据结构和算法的重要性。本书旨在帮助读者掌握诸如列表、元组、集合、字典、栈、队列、排序算法(如冒泡排序、插入排序、快速排序)、搜索算法(如线性查找、二分查找)等核心概念。 作为入门必备读物,它通过清晰的讲解和实用的示例,引导读者逐步理解数据结构在程序设计中的作用,以及如何利用这些结构提高代码的效率和可维护性。书中不仅理论知识扎实,还包含了丰富的实践环节,使读者能在实践中巩固所学,并能灵活运用到实际项目中。 版权方面,本书享有2011年John Wiley & Sons, Inc.的版权保护,除非获得出版社的书面许可或通过Copyright Clearance Center, Inc.支付相应的复制费用,否则任何形式的复制、存储、传输都是被严格限制的。这体现了对知识产权的尊重和行业的规范。 总体而言,《Python数据结构》是一本深入浅出、既有理论又有实战的教程,是Python程序员成长过程中不可或缺的参考资料,无论是自学还是教学,都能从中获益匪浅。"
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/9661389/bg10.jpg)
xvi PREFACE
Chapter 5: Searching and Sorting. Introduces the concepts of searching and
sorting and illustrates how the efficiency of some ADTs can be improved when
working with sorted sequences. Search operations for an unsorted sequence are
discussed and the binary search algorithm is introduced as a way of improving this
operation. Three of the basic sorting algorithms are also introduced to further
illustrate the use of algorithm analysis. A new implementation of the Set ADT is
provided to show how different data structures or data organizations can change
the efficiency of an ADT.
Chapter 6: Linked Structures. Provides an introduction to dynamic structures
by illustrating the construction and use of the singly linked list using dynamic
storage allocation. The common operations — traversal, searching, insertion, and
deletion — are presented as is the use of a tail reference when appropriate. Several
of the ADTs presented in earlier chapters are reimplemented using the singly linked
list, and the run times of their operations are compared to the earlier versions.
A new implementation of the Sparse Matrix is especially eye-opening to many
students as it uses an array of sorted linked lists instead of a single Python list as
was done in an earlier chapter.
Chapter 7: Stacks. Introduces the Stack ADT and includes implementations
using both a Python list and a linked list. Several common stack applications
are then presented, including balanced delimiter verification and the evaluation of
postfix expressions. The concept of backtracking is also introduced as part of the
application for solving a maze. A detailed discussion is provided in designing a
solution and a partial implementation.
Chapter 8: Queues. Introduces the Queue ADT and includes three different
implementations: Python list, circular array, and linked list. The priority queue
is introduced to provide an opportunity to discuss different structures and data
organization for an efficient implementation. The application of the queue presents
the concept of discrete event computer simulations using an airline ticket counter
as the example.
Chapter 9: Advanced Linked Lists. Continues the discussion of dynamic struc-
tures by introducing a collection of more advanced linked lists. These include the
doubly linked, circularly linked, and multi linked lists. The latter provides an
example of a linked structure containing multiple chains and is applied by reimple-
menting the Sparse Matrix to use two arrays of linked lists, one for the rows and
one for the columns. The doubly linked list is applied to the problem of designing
and implementing an Edit Buffer ADT for use with a basic text editor.
Chapter 10: Recursion. Introduces the use of recursion to solve various pro-
gramming problems. The properties of creating recursive functions are presented
along with common examples, including factorial, greatest common divisor, and
the Towers of Hanoi. The concept of backtracking is revisited to use recursion for
solving the eight-queens problem.
![](https://csdnimg.cn/release/download_crawler_static/9661389/bg11.jpg)
PREFACE xvii
Chapter 11: Hash Tables. Introduces the concept of hashing and the use of hash
tables for performing fast searches. Different addressing techniques are presented,
including those for both closed and open addressing. Collision resolution techniques
and hash function design are also discussed. The magic behind Python’s dictionary
structure, which uses a hash table, is exposed and its efficiency evaluated.
Chapter 12: Advanced Sorting. Continues the discussion of the sorting problem
by introducing the recursive sorting algorithms—merge sort and quick sort—along
with the radix distribution sort algorithm, all of which can be used to sort se-
quences. Some of the common techniques for sorting linked lists are also presented.
Chapter 13: Binary Trees. Presents the tree structure and the general binary
tree specifically. The construction and use of the binary tree is presented along
with various properties and the various traversal operations. The binary tree is
used to build and evaluate arithmetic expressions and in decoding Morse Code
sequences. The tree-based heap structure is also introduced along with its use in
implementing a priority queue and the heapsort algorithm.
Chapter 14: Search Trees. Continues the discussion from the previous chapter
by using the tree structure to solve the search problem. The basic binary search
tree and the balanced binary search tree (AVL) are both introduced along with
new implementations of the Map ADT. Finally, a brief introduction to the 2-3
multi-way tree is also provided, which shows an alternative to both the binary
search and AVL trees.
Appendix A: Python Review. Provides a review of the Python language and
concepts learned in the traditional first course. The review includes a presentation
of the basic constructs and built-in data structures.
Appendix B: User-Defined Modules. Describes the use of modules in creating
well structured programs. The different approaches for importing modules is also
discussed along with the use of namespaces.
Appendix C: Exceptions. Provides a basic introduction to the use of exceptions
for handling and raising errors during program execution.
Appendix D: Classes. Introduces the basic concepts of object-oriented program-
ming, including encapsulation, inheritance, and polymorphism. The presentation
is divided into two main parts. The first part presents the basic design and use
of classes for those instructors who use a “back to basics” approach in teaching
data structures. The second part briefly explores the more advanced features of
inheritance and polymorphism for those instructors who typically include these
topics in their course.
![](https://csdnimg.cn/release/download_crawler_static/9661389/bg12.jpg)
xviii PREFACE
Acknowledgments
There are a number of individuals I would like to thank for helping to make this
book possible. First, I must acknowledge two individuals who served as mentors
in the early part of my career. Mary Dayne Gregg (University of Southern Mis-
sissippi), who was the best computer science teacher I have ever known, shared
her love of teaching and provided a great role model in academia. Richard Prosl
(Professor Emeritus, College of William and Mary) served not only as my graduate
advisor but also shared great insight into teaching and helped me to become a good
teacher.
A special thanks to the many students I have taught over the years, especially
those at Washington and Lee University, who during the past five years used draft
versions of the manuscript and provided helpful suggestions. I would also like to
thank some of my colleagues who provided great advice and the encouragement
to complete the project: Sara Sprenkle (Washington and Lee University), Debbie
Noonan (College of William and Mary), and Robert Noonan (College of William
and Mary).
I am also grateful to the following individuals who served as outside review-
ers and provided valuable feedback and helpful suggestions: Esmail Bonakdarian
(Franklin University), David Dubin (University of Illinois at Urbana-Champaign)
Mark E. Fenner (Norwich University), Robert Franks (Central College), Charles J.
Leska (Randolph-Macon College), Fernando Martincic (Wayne State University),
Joseph D. Sloan (Wofford College), David A. Sykes (Wofford College), and Stan
Thomas (Wake Forest University).
Finally, I would like to thank everyone at John Wiley & Sons who helped make
this book possible. I would especially like to thank Beth Golub, Mike Berlin, and
Amy Weintraub, with whom I worked closely throughout the process and who
helped to make this first book an enjoyable experience.
Rance D. Necaise
![](https://csdnimg.cn/release/download_crawler_static/9661389/bg13.jpg)
CHAPTER
1
Abstract Data Types
The foundation of computer science is based on the study of algorithms. An al-
gorithm is a sequence of clear and precise step-by-step instructions for solving a
problem in a finite amount of time. Algorithms are implemented by translating
the step-by-step instructions into a computer program that can be executed by
a computer. This translation process is called computer programming or sim-
ply programming. Computer programs are constructed using a programming
language appropriate to the problem. While programming is an important part
of computer science, computer science is not the study of programming. Nor is
it about learning a particular programming language. Instead, programming and
programming languages are tools used by computer scientists to solve problems.
1.1 Introduction
Data items are represented within a computer as a sequence of binary digits. These
sequences can appear very similar but have different meanings since computers
can store and manipulate different types of data. For example, the binary se-
quence 01001100110010110101110011011100 could be a string of characters, an in-
teger value, or a real value. To distinguish between the different types of data, the
term type is often used to refer to a collection of values and the term data type to
refer to a given type along with a collection of operations for manipulating values
of the given type.
Programming languages commonly provide data types as part of the language
itself. These data types, known as primitives, come in two categories: simple
and complex. The simple data types consist of values that are in the most
basic form and cannot be decomposed into smaller parts. Integer and real types,
for example, consist of single numeric values. The complex data types, on the
other hand, are constructed of multiple components consisting of simple types or
other complex types. In Python, objects, strings, lists, and dictionaries, which can
1
![](https://csdnimg.cn/release/download_crawler_static/9661389/bg14.jpg)
2 CHAPTER 1 Abstract Data Types
contain multiple values, are all examples of complex types. The primitive types
provided by a language may not be sufficient for solving large complex problems.
Thus, most languages allow for the construction of additional data types, known
as user-defined types since they are defined by the programmer and not the
language. Some of these data types can themselves be very complex.
1.1.1 Abstractions
To help manage complex problems and complex data types, computer scientists
typically work with abstractions. An abstraction is a mechanism for separat-
ing the properties of an object and restricting the focus to those relevant in the
current context. The user of the abstraction does not have to understand all of
the details in order to utilize the object, but only those relevant to the current task
or problem.
Two common types of abstractions encountered in computer science are proce-
dural, or functional, abstraction and data abstraction. Procedural abstraction
is the use of a function or method knowing what it does but ignoring how it’s
accomplished. Consider the mathematical square root function which you have
probably used at some point. You know the function will compute the square root
of a given number, but do you know how the square root is computed? Does it
matter if you know how it is computed, or is simply knowing how to correctly use
the function sufficient? Data abstraction is the separation of the properties of a
data type (its values and operations) from the implementation of that data type.
You have used strings in Python many times. But do you know how they are
implemented? That is, do you know how the data is structured internally or how
the various operations are implemented?
Typically, abstractions of complex problems occur in layers, with each higher
layer adding more abstraction than the previous. Consider the problem of repre-
senting integer values on computers and performing arithmetic operations on those
values. Figure 1.1 illustrates the common levels of abstractions used with integer
arithmetic. At the lowest level is the hardware with little to no abstraction since it
includes binary representations of the values and logic circuits for performing the
arithmetic. Hardware designers would deal with integer arithmetic at this level
and be concerned with its correct implementation. A higher level of abstraction
for integer values and arithmetic is provided through assembly language, which in-
volves working with binary values and individual instructions corresponding to the
underlying hardware. Compiler writers and assembly language programmers would
work with integer arithmetic at this level and must ensure the proper selection of
assembly language instructions to compute a given mathematical expression. For
example, suppose we wish to compute x = a + b − 5. At the assembly language
level, this expression must be split into multiple instructions for loading the values
from memory, storing them into registers, and then performing each arithmetic
operation separately, as shown in the following psuedocode:
loadFromMem( R1,
'
a
'
)
loadFromMem( R2,
'
b
'
)
剩余537页未读,继续阅读
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/2ee6e517a33d423a8bf2923be859f58d_u010886217.jpg!1)
RayBreslin
- 粉丝: 4w+
- 资源: 10
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 多模态联合稀疏表示在视频目标跟踪中的应用
- Kubernetes资源管控与Gardener开源软件实践解析
- MPI集群监控与负载平衡策略
- 自动化PHP安全漏洞检测:静态代码分析与数据流方法
- 青苔数据CEO程永:技术生态与阿里云开放创新
- 制造业转型: HyperX引领企业上云策略
- 赵维五分享:航空工业电子采购上云实战与运维策略
- 单片机控制的LED点阵显示屏设计及其实现
- 驻云科技李俊涛:AI驱动的云上服务新趋势与挑战
- 6LoWPAN物联网边界路由器:设计与实现
- 猩便利工程师仲小玉:Terraform云资源管理最佳实践与团队协作
- 类差分度改进的互信息特征选择提升文本分类性能
- VERITAS与阿里云合作的混合云转型与数据保护方案
- 云制造中的生产线仿真模型设计与虚拟化研究
- 汪洋在PostgresChina2018分享:高可用 PostgreSQL 工具与架构设计
- 2018 PostgresChina大会:阿里云时空引擎Ganos在PostgreSQL中的创新应用与多模型存储
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)