2 Data Structures Basics in Python.pdf

Data Structures Basics in Python WMSU Review of what is Data Structure Addresses two fundamental concerns: 1. How the data will be stored and logical relationship among data elements. 2. What operations will be performed on it As data structure is a scheme for data orga...

Data Structures Basics in Python WMSU Review of what is Data Structure Addresses two fundamental concerns: 1. How the data will be stored and logical relationship among data elements. 2. What operations will be performed on it As data structure is a scheme for data organization so the functional definition of a data structure should be independent of its implementation. The functional definition of a data structure is known as ADT (Abstract Data Type) which is independent of implementation. For an example, a stack is a data structure which supports operations such as push and pop. A stack can be implemented in a number of ways, for example using an array or using a linked list. Example 1: When operating a car, the primary activities are steering, accelerating, and braking. On nearly all passenger cars, you steer by turning the steering wheel, accelerate by pushing the gas pedal, and brake by pushing the brake pedal. This design for cars can be viewed as an ADT with operations “steer,” “accelerate,” and “brake.” Two cars might implement these operations in radically different ways, say with different types of engine, or front- versus rear-wheel drive. Yet, most drivers can operate many different cars because the ADT presents a uniform method of operation that does not require the driver to understand the specifics of any particular engine or drive design. These differences are deliberately hidden. Shaffer, Clifford A. (2009). A Practical Introduction to Data Structures and Algorithms: Preliminarites Example 2: Sending Email When you log into your email, compose and send a mail. Again there is a whole lot of background processing involved, verifying the recipient, sending request to the email server, sending your email. Here you are only interested in composing and clicking on the send button. What really happens when you click on the send button, is hidden from you.  Data structures are the building blocks of a program; rightly chosen data structure surely ascertains efficiency of the program. For example, for frequent read operations on a list, array will be the right data structure, while for frequent write operations, linked list will be the right choice. Python Data Types Data Type Data type is a way to classify various types of data such as integer, string, etc. Determines the values that can be used with the corresponding type of data Determines the type of operations that can be performed on the corresponding type of data. Built-in Data Type Data types for which a language has built-in support – Integers – Boolean (true, false) – Floating (Decimal numbers) – Character and Strings Derived Data Type Those data types which are implementation independent as they can be implemented in one or the other way are known as derived data types. These data types are normally built by the combination of primary or built-in data types and associated operations on them. – List – Array – Stack – Queue Basic Operations The data in the data structures are processed by certain operations. The particular data structure chosen largely depends on the frequency of the operation that needs to be performed on the data structure. Traversing Deletion Searching Sorting Insertion Merging Python Variable Variables are nothing but reserved memory locations to store values. This means that when you create a variable you reserve some space in memory.  Based on the data type of a variable, the interpreter allocates memory and decides what can be stored in the reserved memory. Therefore, by assigning different data types to variables, you can store integers, decimals or characters in these variables. Assigning Values to Variables Python variables do not need explicit declaration to reserve memory space. The declaration happens automatically when you assign a value to a variable. The equal sign (=) is used to assign values to variables. counter = 100 # An integer assignment miles = 1000.0 # A floating point name = "John" # A string print (counter) print (miles) print (name) Multiple Assignment Python allows you to assign a single value to several variables simultaneously. For example − a=b=c=1 Here, an integer object is created with the value 1, and all three variables are assigned to the same memory location. You can also assign multiple objects to multiple variables. For example − a,b,c = 1,2,"john" Here, two integer objects with values 1 and 2 are assigned to variables a and b respectively, and one string object with the value "john" is assigned to the variable c. Standard Data Types Python has five standard data types − 1. Numbers 2. String 3. List 4. Tuple 5. Dictionary Python Numerals int long float complex int (signed integers) 10 51924361L 0.0 3.14j long (long integers, they can also be represented in 100 -0x19323L 15.20 45.j octal and hexadecimal) -786 0122L -21.9 9.322e-36j float (floating point real values) 080 0xDEFABCECBDAECBFBAEl 32.3+e18.876j complex (complex -0490 535633629843L -90. -.6545+0J numbers) -0x260 -052318172735L -32.54e100 3e+26J 0x69 -4721885298529L 70.2-E12 4.53e-7j Number Type Conversion Sometimes, you need to coerce a number explicitly from one type to another to satisfy the requirements of an operator or function parameter. – Type int(x) to convert x to a plain integer. – Type long(x) to convert x to a long integer. – Type float(x) to convert x to a floating-point number. – Type complex(x) to convert x to a complex number with real part x and imaginary part zero. – Type complex(x, y) to convert x and y to a complex number with real part x and imaginary part y. x and y are numeric expressions Click to see sample of Python Built-in Functions Python Strings Strings in Python are identified as a contiguous set of characters represented in the quotation marks. Python allows for either pairs of single or double quotes. Subsets of strings can be taken using the slice operator ([ ] and [:] ) The plus (+) sign is the string concatenation operator and the asterisk (*) is the repetition operator. For example - str = 'Hello World!' print (str) # Prints complete string print (str) # Prints first character of the string print (str[2:5]) # Prints characters starting from 3rd to 5th print (str[2:]) # Prints string starting from 3rd character print (str * 2) # Prints string two times print (str + "TEST") # Prints concatenated string This will produce the following result − Hello World! H llo llo World! Hello World!Hello World! Hello World!TEST Python Lists Lists are the most versatile of Python's compound data types. A list contains items separated by commas and enclosed within square brackets ([]). The values stored in a list can be accessed using the slice operator ([ ] and [:]) with indexes starting at 0 in the beginning of the list and working their way to end -1. The plus (+) sign is the list concatenation operator, and the asterisk (*) is the repetition operator. For example − list = [ 'abcd', 786 , 2.23, 'john', 70.2 ] tinylist = [123, 'john'] print (list) # Prints complete list print (list) # Prints first element of the list print (list[1:3]) # Prints elements starting from 2nd till 3rd print (list[2:]) # Prints elements starting from 3rd element print (tinylist * 2) # Prints list two times print (list + tinylist) # Prints concatenated lists This produce the following result − ['abcd', 786, 2.23, 'john', 70.2] abcd [786, 2.23] [2.23, 'john', 70.2] [123, 'john', 123, 'john'] ['abcd', 786, 2.23, 'john', 70.2, 123, 'john'] Python Tuples A tuple is another sequence data type that is similar to the list. A tuple consists of a number of values separated by commas. Unlike lists, however, tuples are enclosed within parentheses. The main differences between lists and tuples are: – Lists are enclosed in brackets ( [ ] ) and their elements and size can be changed – Tuples are enclosed in parentheses ( ( ) ) and cannot be updated. Tuples can be thought of as read-only lists. tuple = ( 'abcd', 786 , 2.23, 'john', 70.2 ) tinytuple = (123, 'john') print tuple # Prints complete list print tuple # Prints first element of the list print tuple[1:3] # Prints elements starting from 2nd till 3rd print tuple[2:] # Prints elements starting from 3rd element print tinytuple * 2 # Prints list two times print tuple + tinytuple # Prints concatenated lists This produce the following result − ('abcd', 786, 2.23, 'john', 70.2) abcd (786, 2.23) (2.23, 'john', 70.2) (123, 'john', 123, 'john') ('abcd', 786, 2.23, 'john', 70.2, 123, 'john')  tuple = ( 'abcd', 786 , 2.23, 'john', 70.2 ) list = [ 'abcd', 786 , 2.23, 'john', 70.2 ] tuple = 1000 list = 1000 The following code is invalid with tuple, because we attempted to update a tuple, which is not allowed. Similar case is possible with lists. Python Dictionary Python's dictionaries are kind of hash table type. They consist of key-value pairs. A dictionary key can be almost any Python type, but are usually numbers or strings. Values, on the other hand, can be any arbitrary Python object. Dictionaries are enclosed by curly braces ({ }) and values can be assigned and accessed using square braces ([]). dict = {} dict['one'] = "This is one" dict = "This is two" tinydict = {'name': 'john','code':6734, 'dept': 'sales'} print dict['one'] # Prints value for 'one' key print dict # Prints value for 2 key print tinydict # Prints complete dictionary print tinydict.keys() # Prints all the keys print tinydict.values() # Prints all the values This produce the following result − This is one This is two {'dept’:'sales', 'code': 6734, 'name': 'john'} ['dept', 'code', 'name'] ['sales', 6734, 'john'] Python Basic Operators Types of Operator Python language supports the following types of operators. – Arithmetic Operators – Comparison (Relational) Operators – Assignment Operators – Logical Operators – Bitwise Operators – Membership Operators – Identity Operators Arithmetic Operator Assume variable a holds 10 and variable b holds 20, then − Operator Description Example + Addition Adds values on either side of the operator. a + b = 30 - Subtraction Subtracts right hand operand from left hand operand. a – b = -10 * Multiplies values on either side of the operator a * b = 200 Multiplication / Division Divides left hand operand by right hand operand b/a=2 % Modulus Divides left hand operand by right hand operand and returns b%a=0 remainder ** Exponent Performs exponential (power) calculation on operators a**b =10 to the power 20 // Floor Division - The division of operands where the result is the 9//2 = 4 and 9.0//2.0 = 4.0, quotient in which the digits after the decimal point are removed. But if one of the operands is negative, the result is floored, i.e., rounded -11//3 = -4, -11.0//3 = -4.0 away from zero (towards negative infinity) − Comparison/Relational Operator Assume variable a holds 10 and variable b holds 20, then − Operator Description Example == If the values of two operands are equal, then the condition becomes true. (a == b) is not true. != If values of two operands are not equal, then condition becomes true. (a != b) is true. If values of two operands are not equal, then condition becomes true. (a b) is true. This is similar to != operator. > If the value of left operand is greater than the value of right operand, then (a > b) is not true. condition becomes true. < If the value of left operand is less than the value of right operand, then condition (a < b) is true. becomes true. >= If the value of left operand is greater than or equal to the value of right operand, (a >= b) is not true. then condition becomes true.