《计算机导论课件：ch12[Part4.Data Organization] Abstract Data Types2》由会员分享，可在线阅读，更多相关《计算机导论课件：ch12[Part4.Data Organization] Abstract Data Types2（57页珍藏版）》请在金锄头文库上搜索。
1、Chapter 12AbstractData TypeUnderstand the concept of an Understand the concept of an abstract data typeabstract data type (ADT). (ADT).Understand the concept of a Understand the concept of a linear listlinear list as well as its operations as well as its operations and applications.and applications.
2、After reading this chapter, the reader should be able to:OBJECTIVESUnderstand the concept of a Understand the concept of a stackstack as well as its operations as well as its operations and applications. and applications. Understand the concept of a Understand the concept of a queuequeue as well as
3、its operations as well as its operations and applications.and applications.Understand the concept of a Understand the concept of a treetree as well as its operations as well as its operations and applications.and applications.Understand the concept of aUnderstand the concept of a graph graph as well
4、 as its operations as well as its operations and applications.and applications.BACKGROUNDBACKGROUND12.1Dont Reinvent the Wheel!Every software developer wants to create new and Every software developer wants to create new and exciting stuff, but very often the same things are exciting stuff, but very
5、 often the same things are reinvented over and over again. reinvented over and over again. The concept of abstraction means:1. You know what a data type can do.2. How it is done is hidden. Note:E Examples: xamples: read read keyboar,readkeyboar,read file, file,C functionsC functionsbank queue,bank q
6、ueue,SeparatingWhat and How Abstract Data Type1.Declaration of data2.Declaration of operations3.Encapsulation of data and operations and hide them from the userNote:ADT DefinitionFigure 12-1Model for ADTFigure 12-1Operations on ADTsOperational InterfaceOperational InterfaceLINEARLINEARLISTSLISTS12.2
7、Figure 12-2Linear listA linear list is a list in which each element has a unique successor.Figure 12-3Categories of linear listsOperations on linear listsInsertion Insertion DeletionDeletionRetrievalRetrievalTraversalTraversalF For general ordered linear listsor general ordered linear listsFigure 12
8、-4Insertion in a linear listInsertion in a linear listFigure 12-5Deletion from a linear listDeletion from a linear listFigure 12-6Retrieval from a linear listRetrieval from a linear listFigure 12-7Traversal of a linear listTraversal of a linear listImplementation of a general linear list Array Array
9、 Linked listLinked listLinear list application Be used in situations where Be used in situations where the elements are accessed the elements are accessed randomly. randomly. Students information in Students information in collegecollegeSTACKSSTACKS12.3A restricted linear list-LIFOA restricted linea
10、r list-LIFOFigure 12-8Three representations of a stackFigure 12-9Push operation in a stackFigure 12-10Pop operation in a stackFigure 12-10Empty operation in a stackThis operation checks to see if the stack is empty or not.This operation checks to see if the stack is empty or not.If not If not empty(
11、Sempty(S) then) thenExample 1Show the result of the following operations on a stack S.push (S , 10)push (S , 12)push (S , 8)if not empty (S), then pop (S)push (S , 2)SolutionSee Figure 12.11 (next slide).Figure 12-11Example 1push (S , 10)push (S , 10)push (S , 12)push (S , 12)push (S , 8)push (S , 8
12、)if not empty (S), then pop (S)if not empty (S), then pop (S)push (S , 2)push (S , 2)Implementation of a stack Array Array Linked listLinked listStack applications Reversing dataReversing dataParsingParsingPostponementPostponementBacktrackingBacktrackingQUEUESQUEUES12.4A restricted linear list-FIFOA
13、 restricted linear list-FIFOFigure 12-12Queue representationFigure 12-13Enqueue operationFigure 12-14Dequeue operationExample 2Show the result of the following operations on a queue Q.enqueue (Q , 23)if not empty (Q), dequeue (Q)enqueue (Q , 20)enqueue (Q , 19)if not empty (Q), dequeue (Q)SolutionSe
14、e Figure 12.15 (next slide).Figure 12-15Example 2enqueueenqueue (Q , 23) (Q , 23)if not empty (Q), if not empty (Q), dequeuedequeue (Q) (Q)enqueueenqueue (Q , 20) (Q , 20)enqueueenqueue (Q , 19) (Q , 19)if not empty (Q), if not empty (Q), dequeuedequeue (Q) (Q)TREESTREES12.5Figure 12-16Representatio
15、n of a treeFigure 12-17Tree terminologyFigure 12-18SubtreesBINARYBINARYTREESTREES12.6Figure 12-19Binary treeFigure 12-20Examples of binary treesFigure 12-21Depth-first traversal of a binary treeFigure 12-22Preorder traversal of a binary treeFigure 12-23Inorder traversal of a binary treeFigure 12-24P
16、ostorder traversal of a binary treeFigure 12-25Breadth-first traversal of a binary treeFigure 12-26Expression treeGRAPHSGRAPHS12.7Figure 12-27Directed and undirected graphsFigure 12-28Add vertexFigure 12-29Delete vertexFigure 12-30Add edgeFigure 12-31Delete edgeFigure 12-32Find vertexFigure 12-33Depth-first traversal of a graphFigure 12-34Breadth-first traversal of a graphFigure 12-35: Part IGraph implementationsFigure 12-35: Part 2Graph implementations
