资源描述
Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,2007 Pearson Addison-Wesley.All rights reserved,0-,*,Chapter 8,Data Abstractions,Pearson Addison-Wesley.,All rights reserved,第1页,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,第2页,Basic Data Structures,Homogeneous array,Heterogeneous array,List,Stack,Queue,Tree,第3页,Figure 8.1,Lists,stacks,and queues,第4页,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,第5页,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,第6页,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,第7页,Figure 8.2,An example of an organization chart,第8页,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,第9页,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,第10页,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,第11页,Figure 8.3,Tree terminology,第12页,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,第13页,Figure 8.4,Novels arranged by title but linked according to authorship,第14页,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 block,Components can be stored in separate locations identified by pointers,第15页,Figure 8.5,The array of temperature readings stored in memory starting at address x,第16页,Figure 8.6,A two-dimensional array with four rows and five columns stored inrow major order,第17页,Figure 8.7,Storing the heterogeneous array Employee,第18页,Storing 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 list,第19页,Figure 8.8,Names stored in memory as a contiguous list,第20页,Figure 8.9,The structure of a linked list,第21页,Figure 8.10,Deleting an entry from a linked list,第22页,Figure 8.11,Inserting an entry into a linked list,第23页,Storing Stacks and Queues,Stacks usually stored as contiguous lists,Queues usually stored as,Circular Queues,Stored in a contiguous block in which the first entry is considered to follow the last entry,Prevents a queue from crawling out of its allotted storage space,第24页,Figure 8.12,A stack in memory,第25页,Figure 8.13,A queue implementation with head and tail pointers,第26页,Storing Binary Trees,Linked structure,Each node=data cells+two child pointers,Accessed via a pointer to root node,Contiguous array structure,A1=root node,A2,A3=children of A1,A4,A5,A6,A7=children of A2 and A3,第27页,Figure 8.14,The structure of a node in a binary tree,第28页,Figure 8.15,The conceptual and actual organization of a binary tree using a linked storagesystem,第29页,Figure 8.16,A tree stored without pointers,第30页,Figure 8.17,A sparse,unbalanced tree shown in its conceptual form and as it would bestored without pointers,第31页,Manipulating Data Structures,Ideally,a data structure should be manipulated solely by pre-defined procedures.,Example:A stack typically needs at least,push,and,pop,procedures.,The data structure along with these procedures constitutes a complete abstract tool.,第32页,Figure 8.18,A procedure for printing a linked list,第33页,Case Study,Problem:Construct an abstract tool consisting of a list of names in alphabetical order along with the operations search,print,and insert.,第34页,Figure 8.19,The letters A through M arranged in an ordered tree,第35页,Figure 8.20,The binary search as it would appear if the list were implemented as a linkedbinary tree,第36页,Figure 8.21,The successively smaller trees considered by the procedure in Figure 8.18when searching for the letter J,第37页,Figure 8.22,Printing a search tree in alphabetical order,第38页,Figure 8.23,A procedure for printing the data in a binary tree,第39页,Figure 8.24,Inserting the entry M into the list B,E,G,H,J,K,N,P stored as a tree,第40页,Figure 8.25,A procedure for inserting a new entry in a list stored as a binary tree,第41页,User-defined Data Type,A template for a heterogeneous structure,Example:,define type,EmployeeType,to be,char Name25;,int Age;,real SkillRating;,第42页,Abstract Data Type,A user-defined data type with procedures for access and manipulation,Example:,define type,StackType,to be,int StackEntries20;,int StackPointer=0;,procedure,push(value),StackEntriesStackPointer,value;,StackPointer StackPointer+1;,procedure,pop.,第43页,Class,An abstract data type with extra features,Characteristics can be inherited,Contents can be encapsulated,Constructor methods to initialize new objects,第44页,Figure 8.26,A stack of integers implemented in Java and C#,第45页,Pointers in Machine Language,Immediate addressing,:Instruction contains the data to be accessed,Direct addressing,:Instruction contains the address of the data to be accessed,Indirect addressing,:Instruction contains the location of the address of the data to be accessed,第46页,Figure 8.27,Our first attempt at expanding the machine language in Appendix C to take advantage of pointers,第47页,Figure 8.28,Loading a register from a memory cell that is located by means of a pointerstored in a register,第48页,
展开阅读全文