Problem Solving with Algorithms and DataStructures using python

【实例简介】
Python版的数据结构和算法，是一本极优的python数据结构入门教材，同时提供英文版的官方网站，可进行在线的程序演示。www.interactivepython.org/runestone/static/pythonds/index.html
CONTENTS 1 Introduction 3 1.1 Objectives 2 Getting Star 1. 3 What Is Computer Science? 4 1. 4 Review of Basic Python 1.5 Summary 38 1.6 Key te 38 Programming Exercises 2 Algorithm Al nalvsis 41 2.1 Objectives 41 2.2 What Is Algorithm Analysis? 41 2.3 Performance of Python Data Structures 2.4 Summary 59 2.5 Key terms 59 2.6 Discussion Questions ·着D 59 2.7 Programming exercises 3 Basic data structures 3.1 Obiective: 61 3.2 What Are Linear structures 3.3 Stacks 3.4 The Stack Abstract Data Type 64 3.5ue 82 3.6 Deques 94 3.7 Lists 97 3.8 The Unordered List Abstract Data Type 3.9 Implementing an Unordered List: Linked Lists 98 3.10 The Ordered List Abstract Data Type 108 3.11 Summary· 3.12 Key Terms ,112 3.13 Discussion Questions 112 3.14 Programming Exercises 113 4 Recursion 17 4.1 Objectives 117 4.2 What is recursion ,,,,,,,,,,,,117 4.3 Stack Frames: Implementing Recursion 123 4.4 Visualising Recursion 125 4.5 Complex Recursive Problems ,,,,.133 4.6 Exploring a maze 135 4.7 Summary .144 4.8 Key Terms 145 4.9 Discussion Questions 145 4.10 Programming Exercises 145 5 Sorting and Searching 147 1 Objectives 147 5.2 Searching... 147 5.3 Sorting·· 163 5.4 Summary 181 5.5 Key Ter rms 182 5.6 Discussion Questions 182 5.7 Programming exercises 183 6 Trees and Tree algorithms 185 6.1 Objective 185 6.2 Examples Of Trees .185 6.3 Vocabulary and Definitions 188 6.4 Implementation 6.5 Priority queues with Binary heaps l98 6.6 Binary Tree Applications ..206 6.7 Tree Traversals 212 6.8 Binary Search Trees 215 6.9 Summary 231 6.10 Key Terms 232 6. 11 Discussion Questions 232 6. 12 Programming Exercises 233 7 JSON 235 7.1 Objectives 235 7. 2 What is json? 235 7.3 The ISON Syntax 235 Problem Solving with algorithms and Data Structures, Release 3.0 TM python CONTENTS Problem Solving with algorithms and data structures Release 3.0 CONTENTS CHAPTER ONE INTRODUCTION 1.1 Objectives To review the ideas of computer science, programming, and problem-solving To understand abstraction and the role it plays in the problem-solving process To understand and implement the notion of an abstract data type To review the Python programming language 1.2 Getting started The way we think about programming has undergone many changes in the ycars sincc the first electronic computers required patch cables and switches to convey instructions from human to machine. As is the case with many aspects of society, changes in computing technology provide computer scicntists with a growing number of tools and platforms on which to practice their craft. Advances such as faster processors, high-spced networks, and largc memory ca pacitics havc created a spiral of complexity through which computer scicntists must navigate Throughout all of this rapid cvolution, a number of basic principles have remained constant The science of computing is concerned with using computers to solve problems You have no doubt spent considerable time learning the basics of problem-solving and hope- fully feel confident in your ability to take a problem statement and develop a solution. You have also learned that writing computer programs is often hard. The complexity of large problems and the corresponding complexity of the solutions can tend to overshadow the fundamental ideas related to the problem-solving process This chapter emphasizes two important areas for the rest of the text. First, it reviews the frame work within which computer science and the study of algorithms and data structures must fit in particular, the reasons why we need to study these topics and how understanding these top ics helps us to become better problem solvers. Second, we review the Python programming language. Although we cannot provide a detailed exhaustive reference we will give examples and explanations for the basic constructs and ideas that will occur throughout the remaining chapters Problem Solving with algorithms and data structures Release 3.0 1. 3 What Is Computer Science? Computer science is often difficult to define. This is probably due to the unfortunate use of the word computer"in the name. As you are perhaps aware, computer science is not simply the study of computers. Although computers play an important supporting role as a tool in the discipline they are just that -tools Computer science is the study of problems, problem-solving, and the solutions that come out of the problem-solving process. Given a problem, a computer scientist's goal is to develop an algorithm, a step-by-step list of instructions for solving any instance of the problem that might arise. Algorithms are finite processes that if followed will solve the problem. Algorithms are solutions Computer science can be thought of as the study of algorithms. however we must be careful to include the fact that some problems may not have a solution. Although proving this statement is beyond the scope of this text, the fact that some problems cannot be solved is important for those who study computer science. We can fully define computer science, then, by including both types of problems and stating that computer science is the study of solutions to problems as well as the study of problems with no solutions It is also very common to include the word computable when describing problems and solu- tions. We say that a problem is computable if an algorithm exists for solving it. An alternative definition for computer science, then, is to say that computer science is the study of problems that are and that are not computable the study of the existence and the nonexistence of algo- rithms. In any case, you will note that the word"computer"did not come up at all. Solutions are considered independent from the machine Computer science, as it pertains to the problem-solving process itself, is also the study of abstraction. Abstraction allows us to view the problem and solution in such a way as to separate the so-called logical and physical perspectives. The basic idea is familiar to us in a common example Consider the automobile that you may have driven to school or work today. as a driver, a user of the car, you have certain interactions that take place in order to utilize the car for its intended purpose. You get in, insert the key, start the car, shift, brake, accclcratc, and steer in order to drive. From an abstraction point of vicw, we can say that you are seeing the logical perspective of the automobile. You are using the functions provided by the car designers for the purpose of transporting you from one location to another. These functions are sometimes also referred to as the interface On the other hand the mechanic who must repair your automobile takes a very different point of view. She not only knows how to drive but must know all of the details necessary to carr out all the functions that we take for granted. She needs to understand how the engine works how the transmission shifts gears, how temperature is controlled and so on. This is known as the physical perspective, the details that take place"under the hood The same thing happens when we use computers. Most people use computers to write docu ments, send and receive cmail, surf the web, play music, store images, and play games without any know ledge of the details that take place to allow those types of applications to work. They view computers from a logical or user perspective. Computer scicntists, programmers, technol ogy support staff, and systcm administrators take a very diffcrent vicw of thc computcr. Thcy Chapter 1. Introduction Problem Solving with algorithms and Data Structures, Release 3.0 sqrt() square root of n Figure ll: Procedural abstraction must know the details of how operating systems work, how network protocols are configured and how to code various scripts that control function. They must be able to control the low-level details that a user simply assumes The common point for both of these examples is that the user of the abstraction, sometimes also called the client, does not need to know the details as long as the user is aware of the way the interface works. This interface is the way we as users communicate with the underlying complexities of the implementation. As another example of abstraction, consider the Python math module. Once we import the module, we can perform computations such as >> import math >> math sart (16) 4.0 >>> This is an example of procedural abstraction. We do not necessarily know how the square root is being calculated but we know what the function is called and how to use it if we perform the import correctly, we can assume that the function will provide us with the correct results. We know that somconc implemented a solution to thc square root problcm but we only need to know how to use it. This is sometimes referred to as a"black box vicw of a process We simply describe the interface: the name of the function, what is needed(the parameters), and what will be returned. The details are hidden inside(see Figure 1.1) 1.3.1 What Is Programming ? Programming is the process of taking an algorithm and encoding it into a notation, a pro- gramming language, so that it can be executed by a computer. Although many programming languages and many different types of computers exist, the important first step is the need to have the solution. Without an algorithm there can be no program Computer science is not the study of programming. Programming, however, is an important part of what a computer scientist does. Programming is often the way that we create a repre- sentation for our solutions. Therefore, this language representation and the process of creating it becomes a fundamental part of the discipline Algorithms describe the solution to a problem in terms of the data needed to represent the problem instance and the set of steps necessary to produce the intended result. Programming languages must provide a notational way to represent both the process and the data. To this end, languages provide control constructs and data types 1.3. What Is Computer Science? Problem Solving with algorithms and data structures Release 3.0 Control constructs allow algorithmic steps to be represented in a convenient yet unambiguous way. At a minimum, algorithms require constructs that perform sequential processing, selection for decision-making, and iteration for repetitive control. As long as the language provides these basic statements, it can be used for algorithm representation. All data items in the computer are represented as strings of binary digits. In order to give these strings mcaning, we nccd to have data types. Data types provide an intcrpretation for thi binary data so that we can think about the data in terms that make sense with respect to the problem being solved. These low-level, built-in data types(sometimes called the primitive data types)provide the building blocks for algorithm development For example, most programming languages provide a data type for integers. Strings of binary digits in the computer's memory can be interpreted as integers and given the typical meanings that we commonly associate with integers(e.g. 23, 654, and -19) In addition, a data type also provides a description of the operations that the data items can participate in. With integers, operations such as addition, subtraction, and multiplication are common. we have come to expect that numeric types of data can participate in these arithmetic operations The difficulty that often arises for us is the fact that problcms and thcir solutions are very complex. These simple, languagc-provided constructs and data types, although certainly suf- ficient to represent complex solutions, are typically at a disadvantage as we work through the problcm-solving proccss. We need ways to control this complexity and assist with the creation of solutions 1.3.2 Why Study Data Structures and Abstract Data Types? To manage the complexity of problems and the problem-solving process, computer scientists use abstractions to allow them to focus on the"big picture without getting lost in the details By creating models of the problem domain, we are able to utilize a better and more efficient problem-solving process. These models allow us to describe the data that our algorithms will manipulate in a much more consistent way with respect to the problem itself. Earlier, we referred to procedural abstraction as a process that hides the details of a particular function to allow the uscr or client to vicw it at a very high level. We now turn our attention to a similar idea, that of data abstraction An abstract data type somctimes called an adt, is a logical description of how we view the data and the operations that are allowed without regard to how they will be implemented. This mcans that we are concerned only with what the data is representing and not with how it will eventually be constructed. By providing this level of abstraction, we arc crcating an encapsulation around the data. The idca is that by encapsulating the details of the implementation, we arc hiding them from the user's view. This is called information hiding Figure 1.2 shows a picture of what an abstract data ty pe is and how it operates. The user interacts with the interface, using the operations that have been specified by the abstract data type The abstract data type is the shell that the user interacts with. The implementation is hidden one level deeper. The user is not concerned with the details of the implementation Thc implementation of an abstract data type, often referred to as a data structure, will require that we provide a physical view of the data using some collection of programming constructs and primitive data types. As wc discussed carlicr, the scparation of these two perspectives will Chapter 1. Introduction 【实例截图】
【核心代码】