Python Data Structures Pocket Primer E-Book

Mercury Learning and Information

• Herausgeber: Packt Publishing
• Kategorie: Fachliteratur
• Sprache: Englisch

Seitenzahl: 280

Veröffentlichungsjahr: 2024

Beschreibung

This Pocket Primer book introduces the fundamentals of data structures using Python. It provides a comprehensive yet fast-paced introduction to core Python concepts and data structures, emphasizing their importance in managing large datasets and implementing search and sort algorithms effectively. The course starts with a basic introduction to Python, setting a solid foundation for more complex topics.
The journey continues with an exploration of recursion and combinatorics, followed by detailed discussions on strings, arrays, and various search and sort algorithms. Further, the book delves into linked lists, queues, and stacks, illustrating their practical applications with numerous code samples. This structured approach ensures that learners can progressively build their knowledge and skills in data structures, reinforced by hands-on coding examples.
With companion files available for download, the book provides additional resources for practice and deeper understanding. This comprehensive guide is ideal for both beginners and those looking to strengthen their grasp of data structures in Python, equipping them with essential tools for managing and manipulating large datasets.

Leseprobe

PYTHON DATASTRUCTURES

Pocket Primer

LICENSE, DISCLAIMER OF LIABILITY, AND LIMITED WARRANTY

By purchasing or using this book and companion files (the “Work”), you agree that this license grants permission to use the contents contained herein, including the disc, but does not give you the right of ownership to any of the textual content in the book / disc or ownership to any of the information or products contained in it. This license does not permit uploading of the Work onto the Internet or on a network (of any kind) without the written consent of the Publisher. Duplication or dissemination of any text, code, simulations, images, etc. contained herein is limited to and subject to licensing terms for the respective products, and permission must be obtained from the Publisher or the owner of the content, etc., in order to reproduce or network any portion of the textual material (in any media) that is contained in the Work.

MERCURY LEARNING AND INFORMATION (“MLI” or “the Publisher”) and anyone involved in the creation, writing, or production of the companion disc, accompanying algorithms, code, or computer programs (“the software”), and any accompanying Web site or software of the Work, cannot and do not warrant the performance or results that might be obtained by using the contents of the Work. The author, developers, and the Publisher have used their best efforts to ensure the accuracy and functionality of the textual material and/or programs contained in this package; we, however, make no warranty of any kind, express or implied, regarding the performance of these contents or programs. The Work is sold “as is” without warranty (except for defective materials used in manufacturing the book or due to faulty workmanship).

The author, developers, and the publisher of any accompanying content, and anyone involved in the composition, production, and manufacturing of this work will not be liable for damages of any kind arising out of the use of (or the inability to use) the algorithms, source code, computer programs, or textual material contained in this publication. This includes, but is not limited to, loss of revenue or profit, or other incidental, physical, or consequential damages arising out of the use of this Work.

The sole remedy in the event of a claim of any kind is expressly limited to replacement of the book and/or disc, and only at the discretion of the Publisher. The use of “implied warranty” and certain “exclusions” vary from state to state, and might not apply to the purchaser of this product.

Companion files for this title are available by writing to the publisher at [email protected].

PYTHON DATASTRUCTURES

Pocket Primer

Oswald Campesato

MERCURY LEARNING AND INFORMATION

Dulles, Virginia

Boston, Massachusetts

New Delhi

Copyright ©2023 by MERCURY LEARNING AND INFORMATION LLC. All rights reserved.

This publication, portions of it, or any accompanying software may not be reproduced in any way, stored in a retrieval system of any type, or transmitted by any means, media, electronic display or mechanical display, including, but not limited to, photocopy, recording, Internet postings, or scanning, without prior permission in writing from the publisher.

Publisher: David Pallai

MERCURY LEARNING AND INFORMATION

22841 Quicksilver Drive

Dulles, VA 20166

[email protected]

www.merclearning.com

800-232-0223

O. Campesato. Python Data Structures Pocket Primer.

ISBN: 978-1-68392-757-0

The publisher recognizes and respects all marks used by companies, manufacturers, and developers as a means to distinguish their products. All brand names and product names mentioned in this book are trademarks or service marks of their respective companies. Any omission or misuse (of any kind) of service marks or trademarks, etc. is not an attempt to infringe on the property of others.

Library of Congress Control Number: 2022947023

222324321  This book is printed on acid-free paper in the United States of America.

Our titles are available for adoption, license, or bulk purchase by institutions, corporations, etc. For additional information, please contact the Customer Service Dept. at 800-232-0223(toll free).

All of our titles are available in digital format at academiccourseware.com and other digital vendors. Companion files (figures and code listings) for this title are available by contacting [email protected]. The sole obligation of MERCURY LEARNING AND INFORMATION to the purchaser is to replace the disc, based on defective materials or faulty workmanship, but not based on the operation or functionality of the product.

I’d like to dedicate this book to my parents – may this bring joy and happiness into their lives.

CONTENTS

Preface

Chapter 1: Introduction to Python

Some Standard Modules in Python

Simple Data Types in Python

Working With Numbers

Working With Other Bases

The chr() Function

The round() Function in Python

Unicode and UTF-8

Working With Unicode

Working With Strings

Comparing Strings

Uninitialized Variables and the Value None in Python

Slicing and Splicing Strings

Testing for Digits and Alphabetic Characters

Search and Replace a String in Other Strings

Precedence of Operators in Python

Python Reserved Words

Working With Loops in Python

Python for Loops

Numeric Exponents in Python

Nested Loops

The split() Function With for Loops

Using the split() Function to Compare Words

Python while Loops

Conditional Logic in Python

The break/continue/pass Statements

Comparison and Boolean Operators

The in/not in/is/is not Comparison Operators

The and, or, and not Boolean Operators

Local and Global Variables

Scope of Variables

Pass by Reference Versus Value

Arguments and Parameters

User-Defined Functions in Python

Specifying Default Values in a Function

Returning Multiple Values From a Function

Lambda Expressions

Working With Lists

Lists and Basic Operations

Lists and Arithmetic Operations

Lists and Filter-Related Operations

The join(), range(), and split() Functions

Arrays and the append() Function

Other List-Related Functions

Working With List Comprehensions

Working With Vectors

Working With Matrices

Queues

Tuples (Immutable Lists)

Sets

Dictionaries

Creating a Dictionary

Displaying the Contents of a Dictionary

Checking for Keys in a Dictionary

Deleting Keys From a Dictionary

Iterating Through a Dictionary

Interpolating Data From a Dictionary

Dictionary Functions and Methods

Other Sequence Types in Python

Mutable and Immutable Types in Python

Summary

Chapter 2: Recursion and Combinatorics

What Is Recursion?

Arithmetic Series

Calculating Arithmetic Series (Iterative)

Calculating Arithmetic Series (Recursive)

Calculating Partial Arithmetic Series

Geometric Series

Calculating a Geometric Series (Iterative)

Calculating Arithmetic Series (Recursive)

Factorial Values

Calculating Factorial Values (Iterative)

Calculating Factorial Values (Recursive)

Calculating Factorial Values (Tail Recursion)

Fibonacci Numbers

Calculating Fibonacci Numbers (Recursive)

Calculating Fibonacci Numbers (Iterative)

Task: Reverse a String via Recursion

Task: Check for Balanced Parentheses

Task: Calculate the Number of Digits

Task: Determine if a Positive Integer Is Prime

Task: Find the Prime Factorization of a Positive Integer

Task: Goldbach’s Conjecture

Task: Calculate the GCD (Greatest Common Divisor)

Task: Calculate the LCM (Lowest Common Multiple)

What Is Combinatorics?

Working With Permutations

Working With Combinations

Task: Calculate the Sum of Binomial Coefficients

The Number of Subsets of a Finite Set

Task: Subsets Containing a Value Larger Than k

Summary

Chapter 3: Strings and Arrays

Time and Space Complexity

Task: Maximum and Minimum Powers of an Integer

Task: Binary Substrings of a Number

Task: Common Substring of Two Binary Numbers

Task: Multiply and Divide via Recursion

Task: Sum of Prime and Composite Numbers

Task: Count Word Frequencies

Task: Check if a String Contains Unique Characters

Task: Insert Characters in a String

Task: String Permutations

Task: Find All Subsets of a Set

Task: Check for Palindromes

Task: Check for the Longest Palindrome

Working With Sequences of Strings

The Maximum Length of a Repeated Character in a String

Find a Given Sequence of Characters in a String

Task: Longest Sequences of Substrings

The Longest Sequence of Unique Characters

The Longest Repeated Substring

Task: Match a String With a Word List (Simple Case)

The Harder Case

Working With 1D Arrays

Rotate an Array

Task: Shift Non-Zero Elements Leftward

Task: Sort Array In-Place in O(n) Without a Sort Function

Task: Invert Adjacent Array Elements

Task: Generate 0 That Is Three Times More Likely Than a 1

Task: Invert Bits in Even and Odd Positions

Task: Invert Pairs of Adjacent Bits

Task: Find Common Bits in Two Binary Numbers

Task: Check for Adjacent Set Bits in a Binary Number

Task: Count Bits in a Range of Numbers

Task: Find the Right-Most Set Bit in a Number

Task: The Number of Operations to Make All Characters Equal

Task: Compute XOR Without XOR for Two Binary Numbers

Working With 2D Arrays

The Transpose of a Matrix

Summary

Chapter 4: Search and Sort Algorithms

Search Algorithms

Linear Search

Binary Search Walk-Through

Binary Search (Iterative Solution)

Binary Search (Recursive Solution)

Well-Known Sorting Algorithms

Bubble Sort

Find Anagrams in a List of Words

Selection Sort

Insertion Sort

Comparison of Sort Algorithms

Merge Sort

Merge Sort With a Third Array

Merge Sort Without a Third Array

Merge Sort: Shift Elements From End of Lists

How Does Quick Sort Work?

Quick Sort Code Sample

Shellsort

Summary

Chapter 5: Linked Lists

Types of Data Structures

Linear Data Structures

Nonlinear Data Structures

Data Structures and Operations

Operations on Data Structures

What Are Singly Linked Lists?

Trade-Offs for Linked Lists

Singly Linked Lists: Create and Append Operations

A Node Class for Singly Linked Lists

Appending a Node in a Linked List

Python Code for Appending a Node

Singly Linked Lists: Finding a Node

Singly Linked Lists: Update and Delete Operations

Updating a Node in a Singly Linked List

Python Code to Update a Node

Deleting a Node in a Linked List: Method #1

Python Code for Deleting a Node: Method #2

Circular Linked Lists

Python Code for Updating a Circular Linked List

Working With Doubly Linked Lists (DLL)

A Node Class for Doubly Linked Lists

Appending a Node in a Doubly Linked List

Python Code for Appending a Node

Python Code for Inserting an Intermediate Node

Searching and Updating a Node in a Doubly Linked List

Updating a Node in a Doubly Linked List

Python Code to Update a Node

Deleting a Node in a Doubly Linked List

Python Code to Delete a Node

Summary

Chapter 6: Linked Lists and Common Tasks

Task: Adding Numbers in a Linked List (1)

Task: Reconstructing Numbers in a Linked List (1)

Task: Reconstructing Numbers in a Linked List (2)

Task: Display the First k Nodes

Task: Display the Last k Nodes

Display a Singly Linked List in Reverse Order via Recursion

Task: Remove Duplicate Nodes

Task: Concatenate Two Lists

Task: Merge Two Lists

Task: Split a Single List into Two Lists

Task: Find the Middle Element in a List

Task: Reversing a Linked List

Task: Check for Palindromes in a Linked List

Summary

Chapter 7: Queues and Stacks

What Is a Queue?

Types of Queues

Creating a Queue Using a Python List

Creating a Rolling Queue

Creating a Queue Using an Array

What Is a Stack?

Use Cases for Stacks

Operations With Stacks

Working With Stacks

Task: Reverse and Print Stack Values

Task: Display the Min and Max Stack Values (1)

Creating Two Stacks Using an Array

Task: Reverse a String Using a Stack

Task: Balanced Parentheses

Task: Tokenize Arithmetic Expressions

Task: Evaluate Arithmetic Expressions

Infix, Prefix, and Postfix Notations

Summary

Index

CHAPTER 1

INTRODUCTION TO PYTHON

This chapter provides an introduction to basic features of Python, including examples of working with Python strings, arrays, and dictionaries. Please keep in mind that this chapter does not contain details about the Python interpreter: you can find that information online in various tutorials.

You will also learn about useful tools for installing Python modules, basic Python constructs, and how to work with some data types in Python.

The first part of this chapter shows you how to work with simple data types, such as numbers, fractions, and strings. The third part of this chapter discusses exceptions and how to use them in Python scripts.

The second part of this chapter introduces you to various ways to perform conditional logic in Python, as well as control structures and user-defined functions in Python. Virtually every Python program that performs useful calculations requires some type of conditional logic or control structure (or both). Although the syntax for these Python features is slightly different from other languages, the functionality will be familiar to you.

The third part of this chapter contains examples that involve nested loops and user-defined Python functions. The remaining portion of the chapter discusses tuples, sets, and dictionaries.

NOTEThePythonscripts in this book are forPython3.x.

SOME STANDARD MODULES IN PYTHON

The Python Standard Library provides many modules that can simplify your own Python scripts. A list of the Standard Library modules is here:

http://www.python.org/doc/

Some of the most important Python modules include cgi, math, os, pickle, random, re, socket, sys, time, and urllib.

The code samples in this book use the modules math, os, random, and re. You need to import these modules in order to use them in your code. For example, the following code block shows you how to import standard Python modules:

import re import sys import time

The code samples in this book import one or more of the preceding modules, as well as other Python modules. The next section discusses primitive data types in Python.

SIMPLE DATA TYPES IN PYTHON

Python supports primitive data types, such as numbers (integers, floating point numbers, and exponential numbers), strings, and dates. Python also supports more complex data types, such as lists (or arrays), tuples, and dictionaries, all of which are discussed later in this chapter. The next several sections discuss some of the Python primitive data types, along with code snippets that show you how to perform various operations on those data types.

UNICODE AND UTF-8

A Unicode string consists of a sequence of numbers that are between 0 and 0x10ffff, where each number represents a group of bytes. An encoding is the manner in which a Unicode string is translated into a sequence of bytes. Among the various encodings, UTF-8 (Unicode Transformation Format) is perhaps the most common, and it’s also the default encoding for many systems. The digit 8 in UTF-8 indicates that the encoding uses 8-bit numbers, whereas UTF-16 uses 16-bit numbers (but this encoding is less common).

The ASCII character set is a subset of UTF-8, so a valid ASCII string can be read as a UTF-8 string without any re-encoding required. In addition, a Unicode string can be converted into a UTF-8 string.

PRECEDENCE OF OPERATORS IN PYTHON

When you have an expression involving numbers, you might remember that multiplication (“*”) and division (“/”) have higher precedence than addition (“+”) or subtraction (“–”). Exponentiation has even higher precedence than these four arithmetic operators.

However, instead of relying on precedence rules, it’s simpler (as well as safer) to use parentheses. For example, (x/y)+10 is clearer than x/y+10, even though they are equivalent expressions.

As another example, the following two arithmetic expressions are the equivalent, but the second is less error prone than the first:

x/y+3*z/8+x*y/z-3*x (x/y)+(3*z)/8+(x*y)/z-(3*x)

In any case, the following website contains precedence rules for operators in Python:

http://www.mathcs.emory.edu/~valerie/courses/fall10/155/resources/op_precedence.html

WORKING WITH LOOPS IN PYTHON

Python supports for loops, while loops, and range() statements. The following subsections illustrate how you can use each of these constructs.

Python for Loops

Python supports the for loop whose syntax is slightly different from other languages (such as JavaScript and Java). The following code block shows you how to use a for loop in Python