C++ Language - Session 2: Data Structures - FPT University

Nội dung text: C++ Language - Session 2: Data Structures - FPT University

1. Session 2 - Data Structures Pointers and Arrays Derived Types Walkthroughs, Arrays, and Aggregates Session 2 - Data Structures 1/36
2. Objectives • Pointers and Arrays – Pointers – Arrays and Pointers – Unmodifiable Arrays – Unmodifiable Variables • Structs – Member Access – Compactness – Pass By Value – Passing an Address – Arrow Notation – Copying – In-Class Practice Session 2 - Data Structures 2/36
3. Review(1) • A Language for Complex Applications – Complexity – Three Languages – A First Example • Object Terminology – Abstraction – Encapsulation – Hierarchy – Modularity • Compiling Modular Programs – A demonstration Session 2 - Data Structures 3/36
4. Review(2) • The four fundamental concepts applied in object- oriented software development are: Abstraction: focuses on the external view of an object, identifying the essential features that distinguish it from all other objects. Encapsulation: focuses on the implementation of each object; identifying the data that describes its state and developing the algorithms that describe its behavior. Hierarchy: ranks and orders objects amongst other objects. Aggregation defines object-wise containment, while inheritance defines class-wise ranking. Modularity: identifies physical components of a solution. Session 2 - Data Structures 4/36
5. Pointers and Arrays • Pointers and arrays are building blocks of data structures. • "A data structure is a way of storing data in memory so that it can be used efficiently" Wikipedia (2007). Session 2 - Data Structures 5/36
6. Pointers(1) • A pointer declaration type* identifier; double* factor; – The compiler does not initialize a pointer. Before assigning a value to an address pointed to by a pointer, we must specify the address itself. factor =&var; Session 2 - Data Structures 6/36
7. Pointers(2) NULL Address • The C and C++ libraries include the definition of a special address that does not hold any valid data or program instruction. Typically, this address is 0, the first address in memory. We call this address the NULL address. double* factor = NULL; Session 2 - Data Structures 7/36
8. Arrays and Pointers(1) • Compilers convert array subscript notation into the equivalent pointer notation. • The name of a one-dimensional array without brackets is the address of the first element of that array. • When we use an array name as an argument in a function call, the call passes the address of that array to the corresponding parameter. Session 2 - Data Structures 8/36
9. Arrays and Pointers(2) • Array and pointer notations are equivalent in parameter declarations: type* identifier is equivalent to type identifier[] Session 2 - Data Structures 9/36
10. Arrays and Pointers(3) • To refer to the array element a[i] using pointer notation, we add the element's index to the array's address, and then dereference the calculated address *(a + i) Session 2 - Data Structures 10/36
11. Unmodifiable Arrays(1) • To bar a function that receives the address of an array from changing the contents of that array, we qualify the array as unmodifiable using the keyword const. void display(const int a[], int n); • In some functions, we might choose to return the address of a string. To prohibit changes to the returned string, we qualify the function return data type as const. Session 2 - Data Structures 11/36
12. Unmodifiable Arrays(2) Session 2 - Data Structures 12/36
13. Unmodifiable Arrays(3) strcpy(truncate(str, MAX), str); /* ERROR */ Note that we are returning an address that has been passed into the function through the parameter list. We should avoid returning the address of an array that is defined within the function itself, since the address will go out of scope upon returning from the function. Session 2 - Data Structures 13/36
14. Unmodifiable Variables(1) • We may qualify any type as unmodifiable. const type identifier = initialValue; • For example, to declare a variable that holds 3.14159, we write const double pi = 3.14159; – Any subsequent attempt to change the value of pi will trigger a compile-time error. Session 2 - Data Structures 14/36
15. Unmodifiable Variables(2) • We can define program constants using const instead of #define. const int MAX 100; Session 2 - Data Structures 15/36
16. Pointers to Unmodifiable Variables • While the pointer does point to an unmodifiable variable, a backdoor does exist to changing the value of the variable. double pi = 3.14159; const double* factor = NULL; factor = π pi = 3.14; *factor=3.14;/*Error*/ Session 2 - Data Structures 16/36
17. Unmodifiable Pointers • A pointer itself can be unmodifiable. type* const identifier = initial address; For Example: double* const factor = π Session 2 - Data Structures 17/36
18. Unmodifiable Pointers to Unmodifiable Variables • The address pointed to cannot change and the value pointed to cannot change. const type* const identifier = initial address value; Session 2 - Data Structures 18/36
19. Derived Types • A fundamental unit for describing data structures is the derived type. A derived type is a collection of types that describes the rules for interpreting the information stored in a region of memory. Session 2 - Data Structures 19/36
20. structs • The keyword struct identifies a derived type. • We refer to data described by a derived type as an instance of that type. • We refer to the components of the instance as members of the derived type. A member of a derived type may be of primitive type or of a previously declared, derived type. Session 2 - Data Structures 20/36
21. Primitive Types • C and C++ define fixed sets of primitive types. We cannot redefine these sets or introduce new primitive types. • Each primitive type describes how to interpret information stored in a region of memory. Session 2 - Data Structures 21/36
22. Derived Types(1) struct Type { For Example: type identifier; struct Student { // int no; // student number }; char grades[14]; // grades }; Session 2 - Data Structures 22/36
23. Derived Types(2) Allocating Memory • The declaration of a derived type describes the rules for allocating memory and interpreting its contents. To allocate memory for an instance of a derived type, we define the instance. struct Type identifier; struct Student harry; Session 2 - Data Structures 23/36
24. Derived Types(3) • Initialization struct Type identifier = { value, , value }; For Example: struct Student harry = { 975, {'A','B','C'}}; Or struct Student harry = { 975, "ABC"}; Session 2 - Data Structures 24/36
25. Member Access • Access a member of an instance of a derived type using dot notation. instance.member For example: harry.no • Access the address of a non-array member using the address of operator (&). &instance.member For example: &harry.no • Access an element of an array member using index notation. instance.member[index] • Access the address of an element of an array member. &instance.member[index] Session 2 - Data Structures 25/36
26. Compactness(1) • Treating the data values in an instance of a derived type as a set promotes compactness. We pass the instance as an argument to a function instead of passing each of its members as separate arguments. Session 2 - Data Structures 26/36
27. Compactness(2) Session 2 - Data Structures 27/36
28. Compactness(3) Session 2 - Data Structures 28/36
29. Pass By Value • C and C++ compilers pass an instance of a derived type by value. That is, they copy the argument in a function call to the corresponding function parameter, as its initial value. Any change within the function to the value of any member of the copy does not alter the original member. void set(struct Student student); Session 2 - Data Structures 29/36
30. Passing an Address (1) • To change an instance of a derived type from within a function, we pass the address of the instance as an argument to the function. The function receives the address in a pointer parameter. void set(struct Student* student); Session 2 - Data Structures 30/36
31. Passing an Address (2) • The most efficient way of passing an instance of a derived type to a function is by address. • Passing the address of the instance avoids copying all of the data, saving substantial time and space in cases where one or more members are large arrays. • Passing an instance by address only involves copying and storing a single address, which typically spans 4 bytes. Session 2 - Data Structures 31/36
32. Passing an Address (3) • If we pass the address of an instance for efficiency, but do not intend to change the instance within the function, we add the const qualifier to protect the instance from modification within the function void display(const struct *Student student); Session 2 - Data Structures 32/36
33. Arrow Notation • The syntax (*student).no is awkward notation. A cleaner alternative is arrow notation pointer->member • Arrow notation takes a pointer to an instance of a derived type on its left side and a member name on its right side. void set(struct Student* student){ student->no = 306; strcpy(student->grade, "BBB"); } Session 2 - Data Structures 33/36
34. Copying • Most compilers perform member-by-member copying in each of the following operations: – copying • initialize an instance using an existing instance • pass an instance by value • return an instance by value – assign an instance to an existing instance Session 2 - Data Structures 34/36
35. In-Class Practice • As an exercise, upgrade the accounting example from the Compiling Modular Programs reading as follows: – declare a struct that describes the data for a single transaction – define and use an instance of this derived type to upgrade the original solution Session 2 - Data Structures 35/36
36. Summary • Pointers and Arrays – Pointers – Arrays and Pointers – Unmodifiable Arrays – Unmodifiable Variables Q&A • Structs – Member Access – Compactness – Pass By Value – Passing an Address – Arrow Notation – Copying – In-Class Practice Session 2 - Data Structures 36/36