# Giáo trình C++ P2

Chia sẻ: Hoang Nguyen | Ngày: | Loại File: PDF | Số trang:0

0
197
lượt xem
90

Mô tả tài liệu

Data Structures

Chủ đề:

Bình luận(0)

Lưu

## Nội dung Text: Giáo trình C++ P2

1. Week 2 Game Institute Introduction to C and C++ by Stan Trujillo www.gameinstitute.com Introduction to C and C++ : Week 2: Page 1 of 39
2. © 2001, eInstitute, Inc. You may print one copy of this document for your own personal use. You agree to destroy any worn copy prior to printing another. You may not distribute this document in paper, fax, magnetic, electronic or other telecommunications format to anyone else. This is the companion text to the www.gameinstitute.com course of the same title. With minor modifications made for print formatting, it is identical to the viewable text, but without the audio. www.gameinstitute.com Introduction to C and C++ : Week 2: Page 2 of 39
3. Table of Contents Lesson 2 – Data Structures............................................................................................................................4 Complex Data Types.................................................................................................................................4 Arrays ....................................................................................................................................................5 Structures.............................................................................................................................................11 Mixing Complex Types.......................................................................................................................12 Memory Usage ....................................................................................................................................14 Pointers................................................................................................................................................15 Pointers and Functions ........................................................................................................................19 References ...........................................................................................................................................21 Pointer arithmetic ................................................................................................................................24 Memory Allocation .............................................................................................................................27 Automatic Variables............................................................................................................................28 Dynamic Memory ...............................................................................................................................29 Global Memory ...................................................................................................................................30 The PlayerList Sample ........................................................................................................................31 Exercises..............................................................................................................................................36 What’s next?........................................................................................................................................39 www.gameinstitute.com Introduction to C and C++ : Week 2: Page 3 of 39
4. Lesson 2 – Data Structures In Lesson 1 we used the data types that are intrinsic to C and C++, such as int, float, and char. As intrinsic types, these data types are directly supported by the language. In a sense, these are the only types of data that are supported. For game programming, all of the creepy monsters, hordes of aliens, simulated vehicles, and the virtual worlds in which these entities exist, are ultimately represented by these simple data types. Thankfully, C and C++ allow us to use the intrinsic data types to construct larger and more complex types. The intrinsic data types can be used directly, or as building blocks from which virtually any entity or system of entities can be represented. Once a complex data type has been defined, it can be used just like an intrinsic type. Variables of that type can be declared, passed to functions, saved to disk, and manipulated by assigning new values. The only difference is that the complex data structure is bigger (it occupies more memory), and it represents something that is more specific than each of its individual parts. In this lesson, in addition to learning how to create complex data structures, we’ll learn how to manage them efficiently: how to pass them to functions, and manage collections of data structures. We’ll also learn the different ways in which the memory required to represent these data types can be allocated. Complex Data Types There are two basic ways in which multiple data elements can be assembled into a larger data element. The first is to assemble a collection of homogenous types. This is called an array. An array uses a single data type as a building block, and is a new data type only because it represents two or more instances of that type. Arrays can be used to represent a collection of any data type. In Lesson 1, we used an array of the char type to represent a string. In this case each element in the array represents a character, and together the characters represent a text string. Strings are often used in games, to store player names, display in-game status information, and to display menus. Games can also use arrays of other data types. Some examples are list of scores, lists of monsters, or a list of network addresses. We’ll continue our discussion of arrays in the next section. The second method of defining a complex type is to use heterogeneous data types to create a new data type. This method allows any number of different data types to be used to define a new category of data type. This is called a structure. Unlike an array, which is formed as a collection of similar items, a structure can be used to represent entities that require multiple data types for representation. In a racing game, for example, a car might be represented as a structure that contains the make, model, weight, dimensions, fuel capacity, and handling characteristics of the vehicle. Structures are used extensively in games, and are best defined—at least in a rough form—early in the game development process. We’ll learn how to create and structures after we’ve covered arrays. If you’re familiar with the concepts behind object-oriented languages, you might be asking yourself why objects haven’t entered the picture yet. We will cover objects in detail in Lesson 3, building directly on what we cover in this lesson. By concentrating on data structures now, we’ll have less to digest when we introduce objects, because objects rely on the same data structures we’re using in this lesson. www.gameinstitute.com Introduction to C and C++ : Week 2: Page 4 of 39
5. Arrays C++ uses square brackets to denote an array. Declaring an array looks very much like a non-array variable declaration, but arrays require that the variable name be followed by square brackets. Typically the square bracket set contains the number of elements in the array. We can declare an array of integers like this: int playerScores[8]; This snippet declares an array of 8 integers that are collectively represented by the variable name playerScores. Each element of the playerScores array has int for a data type, and contains a value that can be inspected or modified using any operator that is appropriate for integers. Arrays use square brackets for declaration, and for accessing array elements. For declaration, the brackets contain the array size. For accessing array elements after the array has been declared, the brackets contain a numeric value called an index that indicates the desired element. Using the playerScore array declared earlier, a value can be stored in the first array element like this: playerScores[0] = 1; This assigns the first element in the array to 1. In this example we’ve used an index of zero, indicating the first element in the array. C++ uses a zero-based indexing scheme: the first element of an array is indexed as 0, not 1. This means that the last element of the array--in our example--has an index of 7, and not 8. This frequently leads to bugs for people with experience in Basic or Pascal which both use 1 to index the first array element. The code above demonstrates how a single array element can be assigned. To assign all of the elements in this array, we could use eight similar assignments, each with a different index, like this: playerScore[0] = 0; playerScore[1] = 0; playerScore[2] = 0; playerScore[3] = 0; playerScore[4] = 0; playerScore[5] = 0; playerScore[6] = 0; playerScore[7] = 0; Clearly, this is impractical for large arrays. Alternatively a loop can be used to iterate through the array: for (int i = 0; i < 8; i++) { playerScore[i] = 0; } Instead of a literal index, we’re using the variable i as the index, so that each element of the array is affected in turn. In this case we’re assigning each player score to zero using the assignment operator. Notice that we’re using the number 8 in the for loop as part of the terminating condition. This works only because we’re the terminating condition indicates that i must be less than 8. If we used the “less than or equal to” operator instead (
6. for (int i = 0; i
7. Providing an index to an array selects an array element. This array element is a variable of that type, and as such can be used in any context that is legal for that type. Attempting to pass these the entire array in the same context is illegal: DisplayPlayerScore( playerScore ); // compiler error! This won’t work because the DisplayPlayerScore, as we’ve defined it, takes an integer, and not an array of integers. In order to pass the entire array to a function, the function in question would have to accept an array instead of an integer. A function with this prototype, for example: void DisplayAllPlayerScores( int s[8] ); Would accept the entire array, like this: DisplayAllPlayerScores( playerScores ); For reasons that we’ll discuss later in this lesson, passing entire arrays to functions in this manner is best avoided in most cases. Like non-array variable declarations, a newly declared array has an undetermined state. The playerScore array used in this section, for example, contains 8 integer elements that have virtually random values. Using these values without first assigning known values will likely lead to undesirable results. Arrays can either be initialized using a loop shortly after declaration, as shown previously, or initialized when they are declared. In Lesson 1 we learned that intrinsic data types can be declared and initialized in a single statement, as shown below: int variable1= 0; float variable2 = 0.0f; Likewise, our playerScores array might be initialized like this: int scores[8] = { 0, 1, 2, 3, 4, 5, 6, 7 }; This declaration initializes each score to a known value. The first value to appear (zero) is assigned to the first array element, the second value to the second array element, and so forth. Initializing arrays requires that the declaration be followed by the assignment operator and that the initial values are enclosed in curly braces, separated by commas. All of the intrinsic data types support this notation. Here are some more examples: bool engineStates[4] = { true, true, false, true }; float fueltankStates[2] = { 100.0f, 0.0f }; The declarations above create an array of Booleans and an array of floating point values. Each array element is assigned initial values, so there’s no ambiguity about the array contents. When initial array values are provided in this fashion, there is no need to provide the array size. The previous declarations can also be written this way: bool engineStates[ ] = { true, true, false, true }; www.gameinstitute.com Introduction to C and C++ : Week 2: Page 7 of 39
8. float fueltankStates[ ] = { 100.0f, 0.0f }; The compiler can determine the size of the array for us by counting the number of initial values provided, so the two arrays above have 4 and 2 elements respectively. The char data type, when used in an array, is the standard format for representing text strings. As such, char arrays get some special treatment. This support takes the form of special initialization syntax, and a host of string handling functions that are provided in the standard libraries. For example, consider these two declarations, which result in two arrays with identical content. char str1[] = { 'a', 'b', 'c', 0 }; char str2[] = "abc"; The first declaration initializes each array element using the typical array initialization syntax, whereas the second uses a string literal. Notice that the first declaration, in addition to being harder to read, requires that we add a null-terminator explicitly (the zero as the last array element). Failing to do so would cause subsequent string operations to fail. In the second declaration, the compiler automatically adds a null-terminator. As a result, both of these arrays have a length of 4. Notice also that C++ requires that individual characters be enclosed in single quotations when used as literals. Of the two declarations above, the latter is preferred, due to better readability and the implicit null-termination. Not every array element must be initialized during declaration. If you wanted the first two array elements to be initialized, but didn’t care to assign values to the remainder of the array, you could write this: int scores[8] = { 100, 200 }; This declaration creates an array with 8 elements, and initializes the first two elements to 100 and 200. The remaining six elements are not explicitly initialized. Interestingly, the compiler automatically initializes any remaining array elements to zero. The presence of an array initializer list prompts the compiler to initialize the remaining the elements to zero. For example: long largeArray[64000] = { 0 }; In this example, despite the fact that only one array element is explicitly initialized, all 64,000 elements will be initialized to zero. If an array initializer list is present, array elements that are not explicitly initialized, are set to zero. In this example: long largeArray[64000] = { 1 }; The first element is assigned to 1, but the remaining 59,999 elements to be assigned a zero value. It is important to remember that array elements are not initialized unless at least one element is initialized. Here are some examples that explore the different array declaration notations: int a[10]; // all 10 array elements contain unknown values int b[10] = { 0 }; // all 10 array elements are initialized to zero int c[10] = { 100 }; // the first element is assigned to 100, the rest to zero. int d[]; // illegal (compiler error) array size or initializer list required int e[] = { 33, 44 }; // array size is 2, as determined by the initializer list char f[] = “zxy”; // creates a char array, or string, that has a length of 4 char g[] = { ‘z’, x’, ‘y’ }; // acceptable but risky (should not be treated as a string) char h[] = { ‘z’, ‘x’, ‘y’, 0 }; // safe, but not as readable as f www.gameinstitute.com Introduction to C and C++ : Week 2: Page 8 of 39
9. Note that if the g array is used as a string, a bug is likely due to the lack of a null-terminator. Furthermore, the size of the array is set to 3 because 3 values are provided in the initializer list, so there is no room in the array to add a terminator later without shortening the effective string length to 2. A common misconception is that strings that are initialized during declaration cannot be modified because its value was assigned at declaration. We’ll talk about conditions where this is true in Lesson 3, but in all of the declarations we’ve looked at so far, the contents of the resulting array can be modified at will. To demonstrate this fact, and write some code that manipulates an array, let’s write a sample called StringEdit. This sample displays a string, and allows the user to modify the contents of the underlying array by specifying an index. The String Edit sample looks like this: The StringEdit sample uses a char array to represent a string. The array is initialized with text that describes the array, and is displayed using cout. This string appears between the two dotted lines, as shown above. The user is then prompted for an index or one of three special values. Entering the number 44 causes the user to be prompted for an index at which a null-terminator is to be added (44 is used because it is not a valid index—the string has just 40 elements.) This has the effect of truncating the string, demonstrating the significance of the value zero when used in a string. Entering 55 prompts the user for an index where a space will be assigned to the array (we’re using cin for input, which doesn’t accept spaces as input.) Entering a valid index (0 through 38) prompts the user for a character to be placed in the array. Entering negative 1 (-1) causes the sample to terminate. A valid index is a value between zero (indicating the first array element) and 38. We prevent the user from modifying index 39 because that element is used for the null-terminator. If this element were to be reassigned, cout would display any and all characters until the value zero is encountered. This would likely involve the display of a large amount of data outside our array, and would constitute a bug. www.gameinstitute.com Introduction to C and C++ : Week 2: Page 9 of 39
10. The StringEdit sample is implemented using just the main function. A loop is used to repeatedly display the current state of the array, and to process user input. The main function appears here, in its entirety: int main() { char str[40] = "initial string - declared char str[40]"; while ( true ) { cout
11. A while loop is used, but instead of testing a variable condition, as is normally the case, the true keyword is used. This creates an infinite loop that iterates forever—in theory. The sample provides a way out of the loop, by simply returning from the function. The loop is forced to terminate when the user enters an index of –1 because a return statement is executed which causes the entire function to terminate. The remainder of the cases are handled using an if/else if construct that handles each case. The array itself is named str, and is modified according to user request. Structures Now let’s turn our attention to another form of complex data types: structures. Structures allow any number of data types to be combined into a new data type. This allows new types to be created that represent virtually any entity. The resulting type can be used to declare variables, define function argument lists, and, as we’ll learn in Lesson 3, these new types can be made to behave just like intrinsic data types and even perform custom operations. Furthermore, the information provided in this section applies to the creation of objects, as we’ll see in Lesson 3. Structures are supported through the struct keyword, which prefaces the definition of a new structure. This keyword is followed by a name for the structure, and a body containing one or more variable declarations. Let’s begin with a simple example that represents a game player. We’ll include two data items inside the structure: a string for the player name, and an integer indicating his score: struct Player { char name[80]; int score; }; The structure body is enclosed in curly braces, and is followed by a semicolon. The body contains variable declarations that collectively form the new data type. The Player structure contains two such variables, one for the player name, and one for the player’s score. These entries are often called fields, but it is more accurate to call them data members. In this case the Player structure is said to have one data member called name, and one called score. At first glace a structure definition might look like a function definition, but the two differ in the following ways: • Structures definitions begin with the struct keyword • Structures definitions do not have argument lists • Instead of statements, loops, and conditionals, structures contain only data member declarations • Structure definitions are terminated with a semicolon (functions aren’t) It is important to note that the data member definitions in a structure are not variable declarations. The Player structure defined above is a data type—not a variable. Although the structure appears to have variables inside it, they are used only to describe the format of the Player structure. As a data type, the Player structure provides a data description, or blueprint, but by itself is not functional. It cannot store values, and it occupies no memory. The Player structure does not represent a single player—it is a data type that can be used to represent a player. A structure can be used to create variables that can store values and occupy memory. A variable declaration for the Player structure looks like this: www.gameinstitute.com Introduction to C and C++ : Week 2: Page 11 of 39
12. Player player1; The syntax is exactly like that of a variable that is based on an intrinsic type. This is because we have created a new data type: a Player. It isn’t provided by C++, but, now that we’ve created it, we can use it as though it were. As with variables based on intrinsic types, the new variable created above (player1), is un-initialized. We can assign values to its data members using the dot (.) operator, like this: player1.score = 0; The name to the left of the dot operator indicates the variable based on the structure, and the name to the right indicates the data member within the structure that we wish to access. In this case we’re accessing the score field (an int) and setting it to zero. It is logical to assume that we would proceed by assigning the name field in the same fashion, like this: player1.name = “unnamed player”; // compiler error! The problem is that the name field is a char array, and the assignment operator cannot be used on arrays except during initialization. We can’t use the assignment operator here because the player1 variable has already been declared. Instead, we can use the strcpy function, which is provided in the standard C++ library (strcpy is declared in the string.h header file): strcpy( player1.name, “unnamed player” ); The strcpy function copies string data, and takes two arguments. The first is the string to be assigned (the ‘destination’ string), and the second is the source string. The code above uses the strcpy function to assign the string “unnamed player” into the data member name contained within the player1 variable. (We’ll study strcpy in more detail later in this lesson when we talk about pointers.) Alternatively, the player1 variable can be initialized in the same way that we initialized arrays in the previous section, like this: Player player1 = { "unnamed player", 100 }; Initializing a structure looks just like array initialization, except that the initial values must each be matched to the type of the data member to which it refers. In this case we’re using a string to initialize the first data member (name), and an integer to initialize the second data member (score). This is clearly preferable, but is limited to declaration. This syntax can’t be used on a variable that already exists. Also, the initializer values must appear in the order in which the data members are declared in the structure. Mixing Complex Types Arrays and structures can be mixed in any fashion. You can create arrays of structures, structures containing arrays, arrays of arrays, and structures that are composed of other structures. In addition, you can embed structures and arrays in into larger types over and over. You can define structures within structures within structures, arrays within arrays, within arrays and…well, you get the idea. Let’s look at some examples: struct Projectile { www.gameinstitute.com Introduction to C and C++ : Week 2: Page 12 of 39
13. float locationX, locationY; float velocityX, velocityY; }; Projectile projectileArray[100]; In this example, a structure called Projectile is defined that contains data members representing the current location and velocity of a bullet or missile. The Projectile structure is then used to declare an array containing 100 projectiles. This is an example of an array of structures. Modifying or inspecting the contents of this array requires both the square bracket syntax and the dot operator, like this: st projectileArray[0].locationX = 1000.0f; // assigns the locationX data member of the 1 element projectileArray[99].velocityX = 0.0f; // assigns the velocityX data member of the last element We’ve already seen an example of a structure that contains an array: the Player structure: struct Player { char name[80]; int score; }; Previously we used the dot operator to assign the name array with the help of the strcpy function. Alternatively, each element in the array can be accessed using the square bracket syntax together with the dot operator: Player p1; th p1.name[4] = ‘v’; // assigns the character ‘v’ to the 5 character of the player name p1.name[79] = 0; // adds a null-terminator to the end of the player name data member in p1 Structures and arrays can be used as building blocks for new types. For example, we can use the Player structure as the basis for a new structure, like this: struct GamePlayers { Player allPlayers[10]; }; This example uses the Player structure to define a new structure called GamePlayers. While Player represents a single player, the GamePlayers structure represents all of the players in the game (the game is limited to 10 players in this case). The GamePlayers structure contains an array of Player structures. GamePlayers is an example of a structure that contains an array, and the allPlayers field is another example of an array of structures. As the complexity of the data type increases, so does the syntax required access variables of that type. To access individual characters of a player’s name, for example, requires two dot operators and two array indices: GamePlayers players; th players.allPlayers[4].name[0] = ‘a’; // assigns ‘a’ to the first character of the 5 player name This code creates a variable called players that represents all of the players in a game. The next line assigns the character ‘a’ as the first character of the 5th player’s name. www.gameinstitute.com Introduction to C and C++ : Week 2: Page 13 of 39
14. Memory Usage When I was in college, I had a professor that was obsessed with saving memory. His assignments were usually along the lines of, write a program that does such and such using no more than only 6 bytes. His fascination with saving memory was borne out of his having learned how to program on computers that had less that a kilobyte of RAM—less than 1024 bytes. It is not uncommon for modern PCs to be equipped with 512 megabytes of RAM, or 52,428,800 bytes. Clearly, concerning yourself with saving a byte or two is unnecessary. Why then, given the ample memory stores on today’s desktops, are we looking at memory usage? The problem is that, while each intrinsic type is very cheap to use memory-wise, they add up quickly, especially when arrays are involved. In Lesson 1 we learned that variables occupy memory, and that the amount of memory a variable requires depends on its data type. Here’s a table with the key intrinsic types, and the memory required by each variable of that type. (The values displayed are for 32-bit compilers.) Memory usage for intrinsic types Type Bits Bytes bool 8 1 char 8 1 short 16 2 long 32 4 int 32 4 float 32 4 double 64 8 The size of any data type can be retrieved using the sizeof operator. This operator, given a data type, returns the number of bytes required to represent variables of the given type. The values in the table above can be displayed with this code: int main() { cout
15. char name[80]; int score; }; cout