计算机科学概论原版课件(第九版)-8.pptVIP

Chapter 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 Language Basic Data Structures Homogeneous array Heterogeneous array List Stack Queue Tree Figure 8.1 Lists, stacks, and queues Terminology for Lists List: A collection of data whose entries are arranged sequentially Head: The beginning of the list Tail: The end of the list Terminology 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 top Terminology for Queues Queue: A list in which entries are removed at the head and are inserted at the tail FIFO: First-in-first-out Figure 8.2 An example of an organization chart Terminology 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 bottom Terminology 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 parent Terminology 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 leaf Figure 8.3 Tree terminology Additional 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 data Figure 8.4 Novels arranged by title but linked according to authorship Storing 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 b