计算机科学概论(第9版)LectureSlide_08.ppt

1、Data Abstraction Basic Data Structures,Chapter 8,Abstract Data Type,Abstract Data Type as a design tool Concerns only on the important concept or model No concern on implementation details. Stack they provide an easy implementation for several important abstract data structures, including stacks, qu

2、eues, hash tables, symbolic expressions, and skip lists. Detail about linked listed ( covered later),Data Structures,What is a Data structure? Associate different types of data together under one name. What is a Class? Data structures can be extended into a conglomeration of data types and functions

3、 which form the basis of an object.,Defining a Data Structure,When we define a data structure we are in fact creating a new data type of our own. i.e Using predefined types or previously user defined types. Such new types are then used to reference a variables type within a C/C+ program,Declaration,

4、struct my_record int height; int weight; A simple data structure declaration which can now be used within a C/C+ program.,Basic Use,Using our simple structure void main (void) struct my_record int height; int weight; ; struct my_record person1,person2; . / use the new variables So we have two new va

5、riables person1 person1.weight = 175;,Arrays of structures,A common need in system programming is to have an array of structures. struct my_record Names20; Now we have the element Names 0 to Names 19 To access the data items in the structure we use Names 1.height; Names 2.weight;,Complex Types in St

6、ructures,Structures need not only contain simple data types. We can use arrays We can use other structures.,Complex Structure,struct my_complex char Name20; struct my_record details; int id; ;,Access to Complex Structure,struct my_complex person2; person2.details.height = 33; So we first access the

7、person2 structure Then the details item and then The height item within details,Dynamic Structures,So far we have been dealing with simple variables declared from structure types. This is OK if we always know at compile time what variables are required during the execution of the program.,Pointers,P

8、ointers are one of the most central topics to any C/+ programmes. You have already learned pointers in C/C+ class. Remember a pointer simply holds the address of a variable! So a * can be read as “the value at address”,Pointers to Structures,Pointers to structures must be the most common mechanism u

9、sed in system programming. So common that a special C operator is used to indicate that we are accessing a structure with a pointer The - the so called arrow operator.,Pointers to Structures,Example struct my_data_structure int height; int weight; ; struct my_data_structure mydata; / the data struct

10、ure struct my_data_structure * mypointer; / a pointer to a structure mypointer = / is the same as mydata.height = 55,Pointers within a Data Structure,Obviously since a Data Structure can contain any type of data A structure can contain a pointer to a structure This offers the ability to create Link

11、Lists and Binary Tree constructs simply.,Linked Lists,A simple linked list has the form,Pointer to start,Data Structure,Pointer,Data Structure,Pointer,Data Structure,Pointer,Null,C+ Classes,C+ is an extension to the standard C language to encompass Object Orientation Any C code can normally be porte

12、d to within C+. C+ may seem a little more clumsy than JAVA this is because it is far more flexible,Classes,Classes in C/C+ are very much the same as in any other Object Oriented language. A Class is an extension to the concept of a structure Classes have function (methods) associated with the manipu

13、lation of the variable defined by the class.,A Simple Class,Say we started with a structure struct a_struct int an_int; int an_array20; ; struct a_struct my_struct; my_struct.an_int = 3; So we reached the variable in the structure with the dot operator.,A Simple Class,In a class we could do nearly t

14、he same. class a_class int an_array20; public: int an_int; void init(void); int a_function (int a-parameter); ; a_class my_object; my_object.an_int = 5; Access to items in the class is the same as a structure,Functions (Methods in class),In a class we can have a function class a_class int an_array20

15、; public: int an_int; void init(void); int a_function (int a-parameter); ; a_class my_object; my_object.a_function(35);/ call the class function,Constructor,Automatically called when an object is created class a_class int an_array20; public: int an_int; a_class(void); / declare the class constructor

16、 int a_function (int a-parameter); ; a_class:a_class (void) / Implementation of a constructor ,Destructor,class a_class int an_array20; public: int an_int; a_class(void); / declare the class constructor a_class(void);/ declare a destructor int a_function (int a-parameter); ; a_class:a_class (void) /

17、 Implementation of a destructor Destructors are optional ,Inheritance,Create a new class from a base or generic class. General Syntax. class a_class : base_class / inherit base_class object public data items void an_overloaded_function(int an_int); void an_overloaded_function char *a_string); Compil

18、er picks which to use based on the parameter in the call.,OverLoading (Different Number of Parameters),Again One Function many uses. Same function but with different number of formal parameters in list void another_overloaded_function (char a_char); void another_overloaded_function(char a_char, int

19、an_int); This is in fact improved on further by allowing any parameter in the list to be set to a default value and so calls to the function can pass as many or as few parameters as the developer wishes.,Overloading (generally),Any class function can be overloaded. Constructors are a common place fo

20、r using overloading Use in destructors is quite rare since we are dealing with the destruction of the whole object.,Pointers to Objects.,Work in the same way as pointers to structures. The same keyword - is used to access from the pointer to the item or function in the object.,This keyword,The this

21、pointer is implicitly passed to each data member or function within an object class a_class int an_array20; public: int an_int; void init(void); int a_function (int a-parameter); ; a_class my_object; my_object.an_int = 5; / is a short form for the actual this-my_object.an_int=5; / what the compiler

22、actually does.,Summary,Structures Used to group different data types into one complex user defined data type Can contain simple data types as well as complex data types Static Access to items within the structure is by use of the dot operator. The dot operator allows us to nest a hierarchical struct

23、ure,Summary,Pointers to structures One of the most common aspects of C/C+ Pointers contain the address of the variable that contains the data Pointers to structures use the - operator Pointers themselves may be part of the actual data structure.,Summary,Using Pointers and structures we can construct Linked lists Queues Binary trees etc Using dynamic memory allocation (a topic for a later lecture) we can build huge structures of these.,Summary,Classes Data members are basically structure items Can use Public and Private keywords Public can be seen from outside the object Private can on