Fundamentals of Python - bedford-computing.co.uk

1 Fundamentals of Python : Data Structures Kenneth A. Lambert Cengage Learning PTR. Australia Brazil Japan Korea Mexico Singapore Spain United Kingdom United States Fundamentals of Python : 2014 Cengage Learning PTR. Data Structures CENGAGE and CENGAGE LEARNING are registered trademarks of Cengage Kenneth A. Lambert Learning, Inc., within the United States and certain other jurisdictions. Publisher and General Manager, ALL RIGHTS RESERVED. No part of this work covered by the copyright Cengage Learning PTR: Stacy L. Hiquet herein may be reproduced, transmitted, stored, or used in any form or by Associate Director of Marketing: any means graphic, electronic, or mechanical, including but not limited to Sarah Panella photocopying, recording, scanning, digitizing, taping, web distribution, information networks, or information storage and retrieval systems, except Manager of Editorial Services: as permitted under Section 107 or 108 of the 1976 United States Copyright Heather Talbot Act, without the prior written permission of the publisher.

2 Senior Marketing Manager: Mark Hughes For product information and technology assistance, contact us at Senior Acquisitions Editor: Mitzi Koontz Cengage Learning Customer & Sales Support, 1-800-354-9706. Project Editor/Copy Editor: For permission to use material from this text or product, Gill Editorial Services submit all requests online at Technical Reviewer: Serge Palladino Further permissions questions can be emailed to Interior Layout Tech: MPS Limited Cover Designer: Luke Fletcher Indexer/Proofreader: Python is a registered trademark of the Python Software Foundation. All Kelly Talbot Editing Services other trademarks are the property of their respective owners. All images Cengage Learning unless otherwise noted. library of Congress Control Number: 2013932034. ISBN-13: 978-1-285-75200-6. ISBN-10: 1-285-75200-7. eISBN-10: 1-285-43464-1. Cengage Learning PTR. 20 Channel Center Street Boston, MA 02210. USA.

3 Cengage Learning is a leading provider of customized learning solutions with office locations around the globe, including Singapore, the United Kingdom, Australia, Mexico, Brazil, and Japan. Locate your local office at: Cengage Learning products are represented in Canada by Nelson Education, Ltd. For your lifelong learning solutions, visit Visit our corporate website at Printed in the United States of America 1 2 3 4 5 6 7 15 14 13. To my grandchildren, Lucy and Wyatt Redpath and Lennox Barker. Kenneth A. Lambert Lexington, VA. Acknowledgments I would like to thank my friend, Martin Osborne, for many years of advice, friendly criticism, and encouragement on several of my book projects. I would also like to thank my students in Computer Science 112 at Washington and Lee University for classroom testing this book over several semesters. Finally, I would like to thank Serge Palladino, MQA tester, who helped to ensure that the content of all data and solution files used for this text were correct and accurate.

4 Karen Gill, my project editor and copy editor; and Mitzi Koontz, senior acquisitions editor at Cengage Learning PTR. iv About the Author Kenneth A. Lambert is a professor of computer science and the chair of that department at Washington and Lee University. He has taught introductory programming courses for 29 years and has been an active researcher in computer science education. Lambert has authored or coauthored a total of 25 textbooks, including a series of introductory C++. textbooks with Douglas Nance and Thomas Naps, a series of introductory Java textbooks with Martin Osborne, and a series of introductory Python textbooks. His most recent textbook is Easy GUI Programming in Python . v Contents Introduction.. xvii Chapter 1 Basic Python Programming.. 1. Basic Program Elements ..1. Programs and Modules.. 1. An Example Python Program: Guessing a Number .. 2. Editing, Compiling, and Running Python Programs.

5 3. Program Comments .. 4. Lexical Elements .. 4. Spelling and Naming Conventions .. 4. Syntactic Elements .. 5. Literals .. 5. String Literals.. 5. Operators and Expressions.. 6. Function Calls.. 7. The print Function.. 7. The input Function .. 7. Type Conversion Functions and Mixed-Mode Operations .. 7. Optional and Keyword Function Arguments.. 7. Variables and Assignment Statements .. 8. Python Data Typing .. 9. Import Statements .. 9. Getting Help on Program Components .. 9. Control Statements ..10. Conditional Statements .. 10. vi Contents vii Using if __name__ == "__main__" .. 11. Loop Statements .. 12. Strings and Their Operations ..13. Operators .. 13. Formatting Strings for Output .. 14. Objects and Method Calls .. 16. Built-In Python Collections and Their Operations ..17. Lists .. 17. Tuples .. 18. Loops Over Sequences .. 18. Dictionaries .. 19. Searching for a Value .. 19. Pattern Matching with Collections.

6 19. Creating New Functions ..20. Function Definitions .. 20. Recursive Functions.. 21. Nested Function Definitions .. 24. Higher-Order Functions .. 24. Creating Anonymous Functions with lambda .. 25. Catching Exceptions ..26. Files and Their Operations ..27. Text File Output .. 27. Writing Numbers to a Text File .. 28. Reading Text from a Text File .. 29. Reading Numbers from a File .. 30. Reading and Writing Objects with pickle.. 31. Creating New Classes ..32. Projects ..36. Chapter 2 An Overview of Collections .. 39. Collection Types ..39. Linear Collections .. 40. Hierarchical Collections .. 40. Graph Collections .. 41. Unordered Collections .. 41. Sorted Collections .. 41. A Taxonomy of Collection Types .. 42. Operations on Collections ..43. Implementations of Collections..45. Summary ..47. viii Contents Review Questions ..47. Projects ..48. Chapter 3 Searching, Sorting, and Complexity Analysis .. 49.

7 Measuring the Efficiency of Algorithms..49. Measuring the Run Time of an Algorithm .. 50. Counting Instructions .. 52. Measuring the Memory Used by an Algorithm .. 55. Exercises .. 55. Complexity Analysis ..56. Orders of Complexity .. 56. Big-O Notation .. 58. The Role of the Constant of Proportionality .. 58. Exercises .. 59. Search Algorithms..60. Search for the Minimum .. 60. Sequential Search of a List .. 60. Best-Case, Worst-Case, and Average-Case Performance .. 61. Binary Search of a Sorted List .. 62. Comparing Data Items .. 63. Exercises .. 65. Basic Sort Algorithms ..65. Selection Sort.. 66. Bubble Sort .. 67. Insertion Sort .. 68. Best-Case, Worst-Case, and Average-Case Performance Revisited .. 70. Exercises .. 71. Faster Sorting ..71. Overview of Quicksort .. 72. Merge Sort .. 76. Exercises .. 79. An Exponential Algorithm: Recursive Fibonacci ..80. Converting Fibonacci to a Linear Algorithm .. 81.

8 Case Study: An Algorithm Profiler ..82. Request.. 82. Analysis.. 82. Design.. 84. Implementation (Coding).. 85. Summary ..87. Review Questions ..88. Projects ..90. Contents ix Chapter 4 Arrays and Linked Structures .. 93. The Array Data Structure ..93. Random Access and Contiguous Memory .. 96. Static Memory and Dynamic Memory .. 97. Physical Size and Logical Size.. 97. Exercises .. 98. Operations on Arrays ..98. Increasing the Size of an Array .. 99. Decreasing the Size of an Array .. 99. Inserting an Item into an Array That Grows .. 100. Removing an Item from an Array .. 101. Complexity Trade-Off: Time, Space, and Arrays .. 102. Exercises .. 103. Two-Dimensional Arrays (Grids) .. 104. Processing a Grid .. 104. Creating and Initializing a Grid .. 105. Defining a Grid Class.. 105. Ragged Grids and Multidimensional Arrays .. 106. Exercises .. 106. Linked Structures .. 107. Singly Linked Structures and Doubly Linked Structures.

9 107. Noncontiguous Memory and Nodes .. 109. Defining a Singly Linked Node Class.. 111. Using the Singly Linked Node Class .. 111. Exercises .. 113. Operations on Singly Linked Structures .. 113. Traversal .. 113. Searching .. 114. Replacement .. 115. Inserting at the Beginning .. 116. Inserting at the End .. 117. Removing at the Beginning .. 118. Removing at the End .. 118. Inserting at Any Position .. 120. Removing at Any Position .. 121. Complexity Trade-Off: Time, Space, and Singly Linked Structures .. 123. Exercises .. 124. Variations on a Link .. 124. A Circular Linked Structure with a Dummy Header Node .. 124. Doubly Linked Structures .. 125. Exercises .. 128. x Contents Summary .. 128. Review Questions .. 129. Projects .. 129. Chapter 5 Interfaces, Implementations, and Polymorphism .. 133. Developing an Interface.. 134. Designing the Bag Interface .. 134. Specifying Arguments and Return Values .. 135.

10 Constructors and Implementing Classes .. 137. Preconditions, Postconditions, Exceptions, and Documentation .. 138. Coding an Interface in Python .. 139. Exercises .. 140. Developing an Array-Based Implementation .. 140. Choose and Initialize the Data Structures .. 141. Complete the Easy Methods First .. 142. Complete the Iterator.. 143. Complete the Methods That Use the Iterator .. 144. The in Operator and the __contains__ Method.. 145. Complete the remove Method .. 145. Exercises .. 146. Developing a Link-Based Implementation .. 146. Initialize the Data Structures .. 147. Complete the Iterator.. 148. Complete the Methods clear and add .. 148. Complete the Method remove .. 148. Exercises .. 150. Run-Time Performance of the Two Bag Implementations.. 150. Testing the Two Bag Implementations.. 150. Diagramming the Bag Resource with UML .. 152. Summary .. 153. Review Questions .. 153. Projects .. 154. Chapter 6 Inheritance and Abstract Classes.