Understanding Data Structures and Abstract Data Types in Computational Thinking
Data organization and abstraction play a crucial role in computational thinking. Data structures like fasteners exemplify how different types of operations are associated with distinct characteristics. Abstract Data Types (ADTs) serve as specifications for data structures, outlining their essential characteristics and operations. By formalizing data representations and structures, we can model various systems effectively.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
ESSENTIAL COMPUTATIONAL THINKING: CHAPTER 06 Dr. Ricky J. Sethi Essential Computational Thinking
Chapter 6 Data Structures
The story so far We found that data was the structured raw facts, or values, observed from the physical world The way that data is organized has a significant impact on how effectively it can be used The types of values represented by the data, the structured values, also determine the various operations defined on it In addition, abstraction, the idea of ignoring or hiding certain details about some system we re studying, can help us model or represent it Let s formalize this for different data representations and structures
Non-Technical Abstract Type A familiar idea: different types of data will hold different kinds of values and so have different kinds of operations associated with it For example: screws and nails! We can distinguish between the two types of fasteners based on their characteristics (e.g., the value of the kind of head they have) and their operations (the kinds of things you can do to or with them)
Abstract Fastener Type We can abstract out the essential elements of all Fasteners They have a certain value for the Head characteristic (is it flat or slotted, for example) They have certain common operations (they can both be inserted using some driving implement like a screwdriver or hammer, for example) We can then specify the Abstract Fastener Type This is like a like a blueprint or an outline It doesn t have any details for any specific kind of Fastener but describes those elements that all Fasteners must have
Abstract Data Type (ADT) Like the AFT, ADTs delineate the characteristics and operations for many kinds of data, not just fasteners Abstract Data Type denotes the kinds of characteristics a certain data structure can have and the kinds of operations it can do or have done on it Abstract Data Types show what they do but not the details of how they do it abstract! For this reason, ADTs are sometimes called the specification or the interface for the data type
Advantages of ADTs ADTs make our computational solutions simpler and easier to understand or modify by omitting details of how the operations will be implemented E.g., all fasteners have the drive in operation but the Abstract Fastener Type doesn t specify that they should all use only hammers ADTs give us the flexibility to structure the data in memory in the way that s optimal for a specific data type without forcing all data types to follow the same approach E.g., all fasteners have a HEAD value but the Abstract Fastener Type doesn t dictate the same HEAD value for all fasteners ADTs support reuse and organization by providing the ability to generalize the use of similar data types and the ability to group tasks E.g., we can specify we ll use a fastener for two tasks in some solution and the two tasks can use different types of fasteners but we know both tasks are fastener tasks
ADTs vs Data Structures A Data Type is the logical expression, independent of any language, of a type, the collection of values, and the operations that are permitted on that type An Abstract Data Type (ADT) is the logical specification of a Data Type in some particular language but without any implementation details A Data Structure is the implementation of that ADT in that particular language
Data Structures The ADT is just the interface without any implementation details, it is a theoretical concept that is a representation of a Data Type An Abstract Data Type is a logical description while the Data Structure itself is a concrete implementation A particular data structure gives you the concrete implementations for both the characteristics and the operations
Logical Interface vs Physical Implementation This idea of only examining what a system does is a form of abstraction, hence the word abstract in Abstract Data Type. Abstraction also allows us to differentiate between a logical view and a physical view of the system or problem. The logical perspective of the system is sometimes called the interface or logical interface. For example, when you turn on your television, you use a remote control and don t need to know anything about how the TV works, how the image is produced, or what the circuits look like. The circuits and other machinery of the television are the physical implementation and the remote control would constitute the logical interface, which only references what the TV does and not the details of how it does it.
Strings A String is also an example of a Sequential Data Type in Python Some useful Sequence Data Structures that Python gives us are list and tuple A string is simply some ordered collection of characters, or valid symbols, in Python. This ordered collection is called a sequence Since a string is composed of multiple characters it is also sometimes called a compound data type As opposed to something like the int data type, which is a simple data type since it only holds a single value It turns out that we can access individual components of a string as each character, or element, is assigned a unique index in the string
Mangoes! E.g., we can access each individual character via the index, which is a number indicating the position of a particular character in the string The index starts at 0 as arrays and sequences are zero-indexed in both Python and Java. This often leads to the infamous off-by-one error, in which the programmer forgets that indexing begins at zero and mistakenly starts indexing from 1 We can use the subscript operator, which is indicated by [], to access any element at a specific index, or range of indices. We can see this where we first initialized the variable foo to mango and then used the subscript operator to access the first character at index 0 >>> foo = " mango " >>> letter = foo [0] >>> print ( letter ) m >>> letters = foo [0:3] >>> print ( letters ) man
Python String Oddities We can access any sub-sequence of characters in a string using the subscript operator. We can indicate individual elements with a single numeric index or a sub-sequence using a numeric range with the : character. This is called slicing a string It ranges from the lower index (including the element at the lower index itself) to the upper index (excluding the element at the upper index). We can also leave off either the lower or upper index to indicate the lowest or highest value One other quick oddity about Python: strings are immutable This is true for all objects and values So unlike other languages like Java, we can t use the subscript operator to assign values to strings We can also use the subscript operator on a string to access (not modify) individual elements or a range of elements or also access any subset of elements via a for loop >>> print (foo [:3]) man >>> print (foo [3:]) go >>> count = 0 >>> for eachLetter in foo: ... if eachLetter == a : ... count = count + 1 ... >>> print ( count ) 1
A First Look at Objects Strings are actually objects, which you can think of as being derived from an ADT, in a way We ll be exploring objects, and the classes which create them, in quite some depth when we get to Object-Oriented Programming Just about everything in Python is an object Objects have access to both their data, like the string value stored in a string variable, and methods, or operations that you can perform on their data We can use any string method using the string object s name (the name of the variable that represents that object) followed by the dot operator >>> bar = foo.upper() >>> print(bar) MANGO >>> bar = foo.lower() >>> print(bar) mango
Lists One of the most obvious and useful ways to organize data is as a list E.g., we use lists in our everyday lives: shopping lists, to-do lists, checklists, etc. A list is a means of structuring and accessing a collection of data In particular, a way of organizing data in a linear sequence The list ADT can keep track of elements in a list The list ADT describes what kinds of values lists can hold and the operations they can have Like insert a new element, locate an existing element, delete an existing element, etc. Then, we can create specific implementations, or Data Structures, like ArrayList, LinkedList, etc. which implement that required behaviour in very different ways different languages implement them differently The different ways to implement the list ADT depend on the kinds of problems those data structures will help tackle Python implements the list ADT as the list data structure
Lists and Tuples Just like a string is a sequence of characters, a list is a sequence of values of any type at all, including other lists (or tuples) Just like with strings, we can use the subscript operator to access elements or sub-sequences of lists Unlike strings, though, lists are mutable You can use the subscript operator to set or change elements of a list We can still use loops to traverse, or access all the elements of, the list We can also use built-in methods of Python like len() to find the length of any sequence like strings, lists, or tuples There are many methods only available to list objects that allow you to do things like append() new elements to the lists, extend() the list with another list, and sort() the elements of the list We can do things like use the + operator to concatenate lists, the * operator to repeat a list for the number of times in the right operand, and do the same kind of slicing as you did for strings
Tuples A tuple is just like a list but: It s declared using parentheses, (), rather than brackets, [] It s not mutable once you ve created it Tuples are also objects that are comparable, which means that we can sort lists of tuples They re also hashable, which is helpful when we meet the dict data type
