Visual Studio 6: The Complete Reference

Chapter 14 - Advanced Programming Topics

Visual C++ 6: The Complete Reference
Chris H. Pappas and William H. Murray, III
  Copyright 1998 The McGraw-Hill Companies
Dynamic Memory Allocation—Linked Lists
Linked lists are often the best choice when trying to create memory-efficient algorithms. Previous programs involving arrays of structures (see Chapter 9 and 13, for example) have all included definitions for the total number of structures used. For example, MAX_BOATS might be set to 25. This means that the program can accept data for a maximum of 25 boats. If 70 or 100 boats are brought into the marina, the program itself will have to be altered and recompiled to accommodate the increased number. This is because the structure allocation is static (do not confuse this with the storage class modifier—static). Static used in this sense means a variable that is created by the compiler at compile time. These types of variables exist for their normal scope and the programmer cannot create more of them, or destroy any of them, while the program is executing. The disadvantage of static allocation should be immediately clear.
One way around the problem is to set the number of structures higher than needed. If MAX_BOATS is set to 10000, not even Nineveh Boat Sales could have a marina that large. However, 10000 means that you are requiring the computer to set aside more than 400 times more memory than before. This is not a wise or efficient way to program.
A better approach is to set aside memory dynamically, as it is needed. With this approach, memory allocation for structures is requested as the inventory grows. Linked lists allow the use of dynamic memory allocation.
A linked list is a collection of structures. Each structure in the list contains an element or pointer that points to another structure in the list. This pointer serves as the link between structures. The concept is similar to an array, but enables the list to grow dynamically. Figure 14-1 shows the simple linked list structure for the Nineveh Boat Sales Program.
Figure 14-1: Implementation of a standard list
The linked list for this example includes a pointer to the next boat in the inventory:
struct stboat { char sztype[15]; char szmodel[15]; char sztitle[20]; char szcomment[80]; int iyear; long int lmotor_hours; float fretail; float fwholesale; struct stboat *nextboat;} Nineveh, *firstboat,*currentboat;
The user-defined structure type stboat is technically known as a self-referential structure because it contains a field that holds an address to another structure just like itself. The pointer, nextboat, contains the address of the next related structure. This allows the pointer, *nextboat, in the first structure to point to the second structure, and so on. This is the concept of a linked list of structures.
Considerations when Using Linked Lists
To allow your program to dynamically reflect the size of your data, you need a means for allocating memory as each new item is added to the list. In C, memory allocation is accomplished with the malloc( ) function while in C++ new( ) is used. In the section below titled “A Simple Linked List,” the complete program allocates memory for the first structure with the code:
firstboat=new (struct stboat);
The following code segment demonstrates how you can use a similar statement to achieve subsequent memory allocation for each additional structure. The while loop continues the entire process while there is valid data to be processed:
while (datain(&Nineveh) == 0) {  currentboat->nextboat = new (struct stboat); if (currentboat->nextboat == NULL) return(1);  currentboat=currentboat->nextboat; *currentboat=Nineveh;}
To give you some experience with passing structures, the while loop begins by sending datain( ), the address of the stboat structure, &Nineveh. The function datain( ) takes care of filling the structure with valid data or returns a value of 1 if the user has entered the letter “Q” indicating that he or she wants to quit. If datain( ) does not return a 1, the pointer currentboat->nextboat is assigned the address of a dynamically allocated stboat structure. The if statement checks to see if the function call to new( ) was successful or not (new( ) returns a NULL if unsuccessful).
Since the logical use for currentboat is to keep track of the address of the last valid stboat structure in the list, the statement after the if updates currentboat to the address of the new end of the list, namely, currentboat‘s new nextboat address.
The last statement in the loop takes care of copying the contents of the stboat structure Nineveh into the new dynamically allocated structure pointed to by *currentboat. The last structure in the list will have its pointer set to NULL. Using NULL marks the end of a linked list. See if you can tell where this is done in the complete program that follows.
A Simple Linked List
The following program shows how to implement the Nineveh Boat Sales example using linked lists. Compare this program with the one in Chapter 13 under the section titled “Constructing an Array of Structures.” The C example in Chapter 13 is similar except that it uses a static array implementation. Study the two listings and see which items are similar and which have changed.
////    C++ program is an example of a simple linked list.//    Nineveh used boat inventory example is used again//    Copyright (c) Chris H. Pappas and William H. Murray, 1998//#include <stdlib.h>#include <iostream.h>
struct stboat { char sztype[15]; char szmodel[15]; char sztitle[20]; char szcomment[80]; int iyear; long int lmotor_hours; float fretail; float fwholesale; struct stboat *nextboat;} Nineveh, *firstboat,*currentboat;void boatlocation(struct stboat *node);void output_data(struct stboat *boatptr);int datain(struct stboat *Ninevehptr);
main( ){ firstboat=new (struct stboat); if (firstboat==NULL) exit(1); if (datain(&Nineveh) != 0) exit(1); *firstboat=Nineveh; currentboat=firstboat; while (datain(&Nineveh)==0) { currentboat->nextboat=   new (struct stboat); if (currentboat->nextboat==NULL) return(1); currentboat=currentboat->nextboat; *currentboat=Nineveh; } currentboat->nextboat=NULL; // signal end of list
 boatlocation(firstboat); return (0);}void boatlocation(struct stboat *node){ do {   output_data(node); } while ((node=node->nextboat) != NULL);}void output_data(struct stboat *boatptr){ cout << “\n\n\n”; cout << “A ” << boatptr->iyear << “ ”  << boatptr->sztype << boatptr->szmodel << “ ”  << “beauty with ” << boatptr->lmotor_hours << “ ”  << “low miles.\n”; cout << boatptr->szcomment << “.\n”; cout << “Grab the deal by asking your Nineveh salesperson for”; cout << “ #” << boatptr->sztitle << “ ONLY! $”  << boatptr->fretail << “.\n”;}
int datain(struct stboat *Ninevehptr){ char newline; cout << “\n[Enter new boat information - a Q quits]\n\n”; cout << “Enter the make of the boat.\n”; cin >> Ninevehptr->sztype; if (*(Ninevehptr->sztype) == ‘Q’) return(1); cout << “Enter the model of the boat.\n”; cin >> Ninevehptr->szmodel; cout << “Enter the title number for the boat.\n”; cin >> Ninevehptr->sztitle; cout << “Enter the model year for the boat.\n”; cin >> Ninevehptr->iyear; cout << “Enter the number of hours on the boat motor.\n”; cin >> Ninevehptr->lmotor_hours;
 cout << “Enter the retail price of the boat.\n”; cin >> Ninevehptr->fretail; cout << “Enter the wholesale price of the boat.\n”; cin >> Ninevehptr->fwholesale; cout << “Enter a one line comment about the boat.\n”; cin.get(newline);    // process carriage return cin.get(Ninevehptr->szcomment,80,’.’); cin.get(newline);    // process carriage return return(0);}
Notice that the three functions are all passed pointers to an stboat structure:
int datain(struct stboat *Ninevehptr)void boatlocation(struct stboat *node)void output_data(struct stboat *boatptr)
The function boatlocation( ) checks the linked list for entries before calling the function output_data( ). It does this with a do...while loop that is terminated whenever node pointer is assigned a NULL address. This is only true when you have tried to go beyond the last stboat structure in the list. The output_data( ) function formats the output from each linked list structure.
  Note As you test this application, don’t forget to add a period (.) at the end of the comment regarding each boat. Failure to do this will cause the program to hang.
In most high-level languages, linked lists provide the most efficient use of memory, but are often the most difficult to debug. You will learn in Chapter 16 that the use of object-oriented C++ classes can improve efficiency even more.
Books24x7.com, Inc 2000 –  
Related

Категории