UT CS 302 - Chapter 8 - Data Abstractions

Unformatted text preview:

PowerPoint PresentationChapter 8: Data AbstractionsBasic Data StructuresFigure 8.1 Lists, stacks, and queuesTerminology for ListsTerminology for StacksTerminology for QueuesFigure 8.2 An example of an organization chartTerminology for a TreeTerminology for a Tree (continued)Slide 11Figure 8.3 Tree terminologyAdditional ConceptsFigure 8.4 Novels arranged by title but linked according to authorshipStoring ArraysFigure 8.5 The array of temperature readings stored in memory starting at address xFigure 8.6 A two-dimensional array with four rows and five columns stored in row major orderFigure 8.7 Storing the heterogeneous array EmployeeStoring ListsFigure 8.8 Names stored in memory as a contiguous listFigure 8.9 The structure of a linked listFigure 8.10 Deleting an entry from a linked listFigure 8.11 Inserting an entry into a linked listStoring Stacks and QueuesFigure 8.12 A stack in memoryFigure 8.13 A queue implementation with head and tail pointersStoring Binary TreesFigure 8.14 A circular queue containing the letters P through VFigure 8.15 The structure of a node in a binary treeFigure 8.16 The conceptual and actual organization of a binary tree using a linked storage systemFigure 8.17 A tree stored without pointersFigure 8.18 A sparse, unbalanced tree shown in its conceptual form and as it would be stored without pointersManipulating Data StructuresFigure 8.19 A procedure for printing a linked listCase StudyFigure 8.20 The letters A through M arranged in an ordered treeFigure 8.21 The binary search as it would appear if the list were implemented as a linked binary treeFigure 8.22 The successively smaller trees considered by the procedure in Figure 8.18 when searching for the letter JFigure 8.23 Printing a search tree in alphabetical orderFigure 8.24 A procedure for printing the data in a binary treeFigure 8.25 Inserting the entry M into the list B, E, G, H, J, K, N, P stored as a treeFigure 8.26 A procedure for inserting a new entry in a list stored as a binary treeUser-defined Data TypeAbstract Data TypeClassFigure 8.27 A stack of integers implemented in Java and C#Pointers in Machine LanguageFigure 8.28 Our first attempt at expanding the machine language in Appendix C to take advantage of pointersFigure 8.29 Loading a register from a memory cell that is located by means of a pointer stored in a registerCopyright © 2012 Pearson Education, Inc. Chapter 8:Data AbstractionsComputer Science: An OverviewEleventh Editionby J. Glenn BrookshearCopyright © 2012 Pearson Education, Inc. 0-2Chapter 8: Data Abstractions•8.1 Data Structure Fundamentals•8.2 Implementing Data Structures•8.3 A Short Case Study•8.4 Customized Data Types•8.5 Classes and Objects•8.6 Pointers in Machine LanguageCopyright © 2012 Pearson Education, Inc. 0-3Basic Data Structures•Homogeneous array•Heterogeneous array•List–Stack–Queue•TreeCopyright © 2012 Pearson Education, Inc. 0-4Figure 8.1 Lists, stacks, and queuesCopyright © 2012 Pearson Education, Inc. 0-5Terminology for Lists•List: A collection of data whose entries are arranged sequentially•Head: The beginning of the list•Tail: The end of the listCopyright © 2012 Pearson Education, Inc. 0-6Terminology for Stacks•Stack: A list in which entries are removed and inserted only at the head•LIFO: Last-in-first-out•Top: The head of list (stack)•Bottom or base: The tail of list (stack)•Pop: To remove the entry at the top•Push: To insert an entry at the topCopyright © 2012 Pearson Education, Inc. 0-7Terminology for Queues•Queue: A list in which entries are removed at the head and are inserted at the tail•FIFO: First-in-first-outCopyright © 2012 Pearson Education, Inc. 0-8Figure 8.2 An example of an organization chartCopyright © 2012 Pearson Education, Inc. 0-9Terminology for a Tree•Tree: A collection of data whose entries have a hierarchical organization•Node: An entry in a tree•Root node: The node at the top•Terminal or leaf node: A node at the bottomCopyright © 2012 Pearson Education, Inc. 0-10Terminology for a Tree (continued)•Parent: The node immediately above a specified node•Child: A node immediately below a specified node•Ancestor: Parent, parent of parent, etc.•Descendent: Child, child of child, etc.•Siblings: Nodes sharing a common parentCopyright © 2012 Pearson Education, Inc. 0-11Terminology for a Tree (continued)•Binary tree: A tree in which every node has at most two children•Depth: The number of nodes in longest path from root to leafCopyright © 2012 Pearson Education, Inc. 0-12Figure 8.3 Tree terminologyCopyright © 2012 Pearson Education, Inc. 0-13Additional Concepts•Static Data Structures: Size and shape of data structure does not change•Dynamic Data Structures: Size and shape of data structure can change•Pointers: Used to locate dataCopyright © 2012 Pearson Education, Inc. 0-14Figure 8.4 Novels arranged by title but linked according to authorshipCopyright © 2012 Pearson Education, Inc. 0-15Storing Arrays•Homogeneous arrays–Row-major order versus column major order–Address polynomial•Heterogeneous arrays–Components can be stored one after the other in a contiguous block–Components can be stored in separate locations identified by pointersCopyright © 2012 Pearson Education, Inc. 0-16Figure 8.5 The array of temperature readings stored in memory starting at address xCopyright © 2012 Pearson Education, Inc. 0-17Figure 8.6 A two-dimensional array with four rows and five columns stored in row major orderCopyright © 2012 Pearson Education, Inc. 0-18Figure 8.7 Storing the heterogeneous array EmployeeCopyright © 2012 Pearson Education, Inc. 0-19Storing Lists•Contiguous list: List stored in a homogeneous array•Linked list: List in which each entries are linked by pointers–Head pointer: Pointer to first entry in list–NIL pointer: A “non-pointer” value used to indicate end of listCopyright © 2012 Pearson Education, Inc. 0-20Figure 8.8 Names stored in memory as a contiguous listCopyright © 2012 Pearson Education, Inc. 0-21Figure 8.9 The structure of a linked listCopyright © 2012 Pearson Education, Inc. 0-22Figure 8.10 Deleting an entry from a linked listCopyright © 2012 Pearson Education, Inc. 0-23Figure 8.11 Inserting an entry into a linked listCopyright © 2012 Pearson Education, Inc. 0-24Storing Stacks and Queues•Stacks usually stored as contiguous lists•Queues usually stored as Circular Queues–Stored in a contiguous block in


View Full Document

UT CS 302 - Chapter 8 - Data Abstractions

Download Chapter 8 - Data Abstractions
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Chapter 8 - Data Abstractions and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Chapter 8 - Data Abstractions 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?