Python数据结构与算法实战

需积分: 10 34 浏览量更新于2024-07-15 收藏 12.92MB PDF 举报

"Data Structures and Algorithms with Python - Kent D. Lee, Steve Hubbard" 这本书是"Undergraduate Topics in Computer Science"系列的一部分，由Kent D. Lee和Steve Hubbard撰写，旨在为计算机科学专业的本科生提供数据结构和算法的深入理解。作者们假设读者具有一定的编程基础，特别是面向对象编程的经验，但不一定要精通Python。书中的内容经过课堂测试，以项目为导向，通过实际案例帮助读者理解算法的重要性。本书涵盖了从基础到高级的数据结构和算法主题，适合入门级和高级水平的课程。每个章节都包含学习目标、复习问题、编程练习和丰富的示例，以增强实践能力。此外，读者可以在相关网站上找到可下载的程序和补充材料，以及作者提供的教学资源。书中讨论的关键主题包括： 1. 入门级数据结构，如数组、链表、栈和队列，这些是构建复杂数据结构的基础。 2. 哈希表在集合和映射中的应用，它们提供了快速的查找和存储操作。 3. 二叉搜索树和树遍历，这对于数据的高效检索至关重要。 4. 图的深度优先搜索，这是解决网络问题和路径寻找问题的常用技术。 5. 高级话题，如成员资格结构、堆、平衡的二进制搜索树（如AVL树和红黑树）、B树以及启发式搜索算法（如A*搜索），这些都是在处理大规模数据时提高性能的关键工具。这本书不仅适用于学术环境，也适合希望使用Python进行数据结构和算法学习的程序员。无论你是初学者还是有经验的开发者，都能从这本书中获益，它将帮助你更好地理解和运用这些核心概念，提升你的编程能力。对于计算机科学的学生而言，这本书提供了丰富的实践和理论知识，有助于他们在学术和职业生涯中取得成功。而对于专业程序员，这本书则是一份宝贵的资源，可以作为转战Python领域的引导，帮助他们适应新的工作需求。

Python Programming 101

This Computer Science text further develops the skills you learned in your ﬁrst CS

text or course and adds to your bag of tricks by teaching you how to use efﬁcient

algorithms for dealing with large amounts of data. Without the proper understanding

of efﬁciency, it is possible to bring even the fastest computers to a grinding halt when

working with large data sets. This has happened before, and soon you will understand

just how easy it can occur. But ﬁrst, we’ll review some patterns for programming and

look at the Python programming language to make sure you understand the basic

structure and syntax of the language.

To begin writing programs using Python you need to install Python on your com-

puter. The examples in this text use Python 3. Python 2 is not compatible with Python

3 so you’ll want to be sure you have Python 3 or later installed on your computer.

When writing programs in any language a good Integrated Development Environ-

ment (IDE) is a valuable tool so you’ll want to install an IDE, too. Examples within

this text will use Wing IDE 101 as pictured in Fig. 1.1, although other acceptable

IDEs are available as well. The Wing IDE is well maintained, simple to use, and has

a nice debugger which will be useful as you write Python programs. If you want to

get Wing IDE 101 then go to http://wingware.com. The website http://cs.luther.edu/

~leekent/CS1 has directions for installing both Python 3 and Wing IDE 101. Wing

IDE 101 is the free version of Wing for educational use.

There are some general concepts about Python that you should know when reading

the text. Python is an interpreted language. That means that you don’t have to go

through any extra steps after writing Python code before you can run it. You can

simply press the debug button in the Wing IDE (it looks like an insect) and it will

ask you to save your program if you haven’t already done so at least once. Then

it will run your program. Python is also dynamically typed. This means that you

will not get any type errors before you run your program as you would with some

programming languages. It is especially important for you to understand the types of

data you are using in your program. More on this in just a bit. Finally, your Python

programs are interpreted by the Python interpreter. The shell is another name for

the Python interpreter and Wing IDE 101 gives you access to a shell within the IDE

K.D. Lee and S. Hubbard, Data Structures and Algorithms with Python,

Undergraduate Topics in Computer Science, DOI 10.1007/978-3-319-13072-9_1

This copy belongs to 'acha04'

1 Python Programming 101 3

To motivate learning or reviewing Python in this chapter, the text will develop

a simple drawing application using turtle graphics and a Graphical User Interface

(GUI) framework called Tkinter. Along the way, you’ll discover some patterns for

programming including the accumulator pattern and the loop and a half pattern for

reading records from a ﬁle. You’ll also see functions in Python and begin to learn

how to implement your own datatypes by designing and writing a class deﬁnition.

1.1 Chapter Goals

By the end of this chapter, you should be able to answer these questions.

• What two parts are needed for the accumulator pattern?

• When do you need to use the loop and a half pattern for reading from a ﬁle?

• What is the purpose of a class deﬁnition?

• What is an object and how do we create one?

• What is a mutator method?

• What is an accessor method?

• What is a widget and how does one use widgets in GUI programming?

1.2 Creating Objects

Python is an object-oriented language. All data items in Python are objects. In Python,

data items that could be thought of as similar are named by a type or class. The term

type and class in Python are synonymous: they are two names for the same thing. So

when you read about types in Python you can think of classes or vice versa.

There are several built-in types of data in Python including int, ﬂoat, str, list, and

dict which is short for dictionary. These types of data and their associated operations

are included in the appendices at the end of the text so you have a quick reference

if you need to refer to it while programming. You can also get help for any type

by typing help(typename) in the Python shell, where typename is a type or class in

Python. A very good language reference can be found at http://python.org/doc, the

ofﬁcial Python documentation website.

1.2.1 Literal Values

There are two ways to create objects in Python. In a few cases, you can use a literal

value to create an object. Literal values are used when we want to set some variable

to a speciﬁc value within our program. For example, the literal 6 denotes any object

with the integer value of 6.

x = 6

This creates an int object containing the value 6. It also points the reference called

x at this object as pictured in Fig. 1.2. All assignments in Python point references

This copy belongs to 'acha04'

4 1 Python Programming 101

Fig. 1.2 A Reference and Object

at objects. Any time you see an assignment statement, you should remember that

the thing on the left side of the equals sign is a reference and the thing on the right

side is either another reference or a newly created object. In this case, writing x = 6

makes a new object and then points x at this object.

Other literal values may be written in Python as well. Here are some literal values

that are possible in Python.

• int literals: 6, 3, 10, −2, etc.

• ﬂoat literals: 6.0, −3.2, 4.5E10

• str literals: ‘hi there’, “how are you”

• list literals: [], [6, ‘hi there’]

• dict literals: {}, {‘hi there’:6, ‘how are you’:4}

Python lets you specify ﬂoat literals with an exponent.

So, 4.5E10 represents the ﬂoat 45000000000.0. Any number written with a deci-

mal point is a ﬂoat, whether there is a 0 or some other value after the decimal point. If

you write a number using the E or exponent notation, it is a ﬂoat as well. Any number

without a decimal point is an int, unless it is written in E notation. String literals are

surrounded by either single or double quotes. List literals are surrounded by [ and ].

The [] literal represents the empty list. The {} literal is the empty dictionary.

You may not have previously used dictionaries. A dictionary is a mapping of keys

to values. In the dictionary literal, the key ‘hi there’ is mapped to the value 6, and

the key ‘how are you’ is mapped to 4. Dictionaries will be covered in some detail in

Chap. 5.

1.2.2 Non-literal Object Creation

Most of the time, when an object is created, it is not created from a literal value.

Of course, we need literal values in programming languages, but most of the time

we have an object already and want to create another object by using one or more

existing objects. For instance, if we have a string in Python, like ‘6’ and want to

create an int object from that string, we can do the following.

y = ’6’

x = int(y)

print(x)

This copy belongs to 'acha04'

1.2 Creating Objects 5

In this short piece of code, y is a reference to the str object created from the string

literal. The variable x is a reference to an object that is created by using the object

that y refers to. In general, when we want to create an object based on other object

values we write the following:

variable = type(other_object_values)

The type is any type or class name in Python, like int, ﬂoat, str or any other

type. The other_object_values is a comma-separated sequence of references to other

objects that are needed by the class or type to create an instance (i.e. an object) of

that type. Here are some examples of creating objects from non-literal values.

z = float(’6.3’)

w = str(z)

u = list(w)

this

results

the

list

[’6’,

’.’,

’3’]

1.3 Calling Methods on Objects

Objects are useful because they allow us to collect related information and group

them with behavior that act on this data. These behaviors are called methods in

Python. There are two kinds of methods in any object-oriented language: mutator

and accessor methods. Accessor methods access the current state of an object but

don’t change the object. Accessor methods return new object references when called.

x = ’how are you’

y = x.upper()

print(y)

Here, the method upper is called on the object that x refers to. The upper accessor

method returns a new object, a str object, that is an upper-cased version of the

original string. Note that x is not changed by calling the upper method on it. The

upper method is an accessor method. There are many accessor methods available on

the str type which you can learn about in the appendices.

Some methods are mutator methods. These methods actually change the existing

object. One good example of this is the reverse method on the list type.

myList = [1, 2, 3]

myList.reverse()

print(myList)

This

prints

[3,

the

screen

The reverse method mutates the existing object, in this case the list that myList

refers to. Once called, a mutator method can’t be undone. The change or mutation

is permanent until mutated again by some other mutator method.

All classes contain accessor methods. Without accessor methods, the class would

be pretty uninteresting. We use accessor methods to retrieve a value that is stored

in an object or to retrieve a value that depends on the value stored in an object.

This copy belongs to 'acha04'

剩余368页未读，继续阅读

迭雅哥2

粉丝: 0
资源: 4

Python数据结构与算法实战

Python 2013：学习数据结构与算法的SciPy实战指南

"矩阵实验报告：三对角、下三角和稀疏矩阵转置操作

TensorFlow Python API 指南

Data Structures and Algorithms with Python by Kent D. Lee and Steve Hubbard

Data Structures and Algorithms Using Python - 2011.pdf

Data Structures and Algorithms with Object-Oriented Design Patterns in CSharp - Bruno R. Preiss.chm

Data-Structures-and-Algorithms-with-Python-Undergraduate-Topics-in-Computer-Science.pdf.pdf

Data Structures and Algorithms in Kotlin - v1.zip

Data Structures And Algorithms With Object-Oriented Design Patterns In Python

Data Structures and Algorithms with Object-Oriented Design Patterns in Python

最新资源