Part II • Managing Data in C
Listing 10.4. continued
printf(“\nWrong answer, “
“please respond with ‘y’ or ‘n’”);
szBuffer[0] = ‘\0’;
}
}
}
if (!nNeedSaving)
{/* Do not need to save, so just exit */ break;
}
/* |
Else fall through to save routines */ |
case ‘S’: /* Save all records */ case ‘s’:
printf(“Saving customers\n”);
DataFile = fopen(szFileName, “wt”);
if (DataFile == NULL)
{/* Test for file re-open; if file can’t be opened, exit with message */
printf(“ERROR: File ‘%s’ couldn’t be opened.\n”, szFileName);
exit(4);
}
TempCustomer = FirstCustomer;
while (TempCustomer)
{
if (nDebug)
{
fprintf(DataFile,
“Name ‘%10s’ Me %lp Next %lp Prev %lp\n”, TempCustomer->szName,
Data Management: Sorts, Lists, and Indexes
TempCustomer, TempCustomer->NextCustomer, TempCustomer->PrevCustomer);
}
else
{
fprintf(DataFile,
“Name ‘%10s’ City ‘%10s’ State ‘%2s’ “ “ZIP ‘%5.5ld’\n”, TempCustomer->szName, TempCustomer->szCity, TempCustomer->szState, TempCustomer->lZip);
}
TempCustomer = TempCustomer->NextCustomer;
}
nNeedSaving = FALSE;
fclose(DataFile);
break;
}
}
}
void GiveHelp()
{
printf(
“\n”
“This program shows how a double linked list is created and\n” “used. It enables you to add records, display the list of\n” “records (which are always sorted by name), and save the\n” “list of records to the disk file.\n”
“\n”
“LINKLIST supports the following commands:\n”);
printf(
“\n”
continues
Part II • Managing Data in C
Listing 10.4. continued
“ |
A - Add a customer/supplier record.\n” |
“Adds a record. Each added record is placed\n”
“in the list in the correct order. Added\n”
“records are sorted by name.\n”);
printf( |
|
“\n” |
|
“ |
D - Display current list.\n” |
“Prints the current list of records in sorted\n”
“order. This list contains name and address\n”
“information or, in the debug mode, name and\n”
“pointer information.\n”);
printf( |
|
“\n” |
|
“ |
X - Exit from program.\n” |
“Ends the program. If records have been added\n”
“and not saved, prompts for save. All saves\n”
“are made to the file specified when the\n”
“program was started.\n”);
printf(
“\n”
“Z - Toggle debug mode.\n”
“Changes the information displayed for the\n”
“user. When on, debug mode shows where the newly\n”
“entered name is being placed in the list, and \ the\n”
“list pointers are displayed when a display command \ is\n”
“entered.\n”);
printf( |
|
|
|
“\n” |
|
|
|
“ |
? |
- |
Display the command list.\n” |
“ |
H |
- |
Display the command list.\n” |
“Displays this help information.\n”);
printf(
“\n”
Data Management: Sorts, Lists, and Indexes |
C C C |
|
10C |
|
C C C |
|
C C |
“S - Save the list.\n”
“Saves (to the specified save file) the current \ list\n”
“of records in sorted order. This list contains \ name\n”
“and address information or, in the debug mode,\n”
“name and pointer information.\n”
“\n”);
printf(
“Additional feature: This program includes a\n” “prompt to save when the exit command is given.\n” “This prompt is given only if the records have\n” “not been saved since the last added record.\n”);
printf(
“Additional feature: This program has a debug mode so that\n” “the user can see how the program works. The debug mode \
enables\n”
“the user to print the linked list and its pointers.\n”);
}
This program was developed from the CDB.C program, which was presented in Chapter 8, “Dynamic Memory Allocation.” In this section, you look at the program, and the code that manages the linked list. First, in the following code fragment, is a nonspecific structure definition (yes, this is a definition, not a declaration) that creates the _CUSTNAME structure name:
struct _CUSTNAME;
This allows _CUSTNAME to be used in the declaration of the structure as a set of pointers, as the third and fourth lines in the following code show:
typedef struct _CUSTNAME { |
|
|
|
|
int |
nRecordType; |
// 1 == Customer |
record. |
struct _CUSTNAME *NextCustomer; // |
Link |
to next, or NULL if none |
struct _CUSTNAME *PrevCustomer; // |
Link |
to previous, or NULL if none |
char |
szName[61]; |
// 60 |
chars |
for name; 1 for null at end |
char |
szAddr1[61]; |
// 60 |
chars |
for address; 1 for null at end |
Part II • Managing Data in C
char |
szAddr2[61]; |
// 60 |
chars |
for address; 1 for null at end |
char |
szCity[26]; |
// 25 |
chars |
for city; 1 for null at end |
char |
szState[3]; |
// 2-character state abbrev. plus null |
int |
lZip; |
// Print as |
%5.5ld for leading 0 |
int |
nRecordNumber; |
// Which record number? |
double |
dSalesTotal; |
// Amount the customer has purchased |
} CUSTNAME;
This section of the CUSTNAME structure declares members that point to the next member or the preceding member in the linked list.
The following code shows how the pointers to the first and last members in the linked list are defined:
PCUSTNAME |
FirstCustomer = NULL; |
PCUSTNAME |
LastCustomer = NULL; |
These lines could have been coded as
struct _CUSTNAME *FirstCustomer; struct _CUSTNAME *LastCustomer;
I suggest that you use the pointer names defined (if you write your structure prototype as I do) when you create the typedef structure.
Next, a few pointers are created for the program to use when a member is created or inserted into the list:
PCUSTNAME |
Customer = NULL; |
PCUSTNAME |
TempCustomer = NULL; |
The next significant part of the program is the section for adding a record, which is called when the user enters the A command. First, the program allocates a block of memory to hold the CUSTNAME structure using calloc(), which initializes this memory to zero. (Remember, malloc() does not initialize memory.) After the memory has been allocated, the program prompts for the name to be added:
case ‘A’: /* Add a record */ case ‘a’:
Customer = (PCUSTNAME)calloc(sizeof(CUSTNAME),
INCREMENT_AMOUNT);
printf(“Enter name %d: “, ++nRecord); gets(szBuffer);
Data Management: Sorts, Lists, and Indexes |
C C C |
|
10C |
|
C C C |
|
C C |
szBuffer[sizeof(Customer->szName) - 1] = ‘\0’; strcpy(Customer->szName, szBuffer);
if (strlen(Customer->szName) > 0)
If the user has entered a name (and not just pressed Return), this member must be added to the linked list. This program inserts members into the list in sorted order. Your program could insert members based on another criterion, for example, ZIP code or customer number.
Nothing prevents you from having two or more sets of links. You might have the list linked based on customer name, ZIP code, and customer number. Each additional key, however, slows the program’s performance when a record is inserted and requires an additional two pointers for the customer structure (the preceding pointer and the next pointer). When you create a linked list with more than one set of links, simply treat each set of links as a separate linked list.
When a record is inserted into a linked list, there are four possible scenarios. One, the list might have nothing in it, and this is the initial member. Thus, both FirstCustomer and LastCustomer must be initialized to this member, as follows:
{/* Insert this record in the list, sorted by name. */ nNeedSaving = TRUE;
if (FirstCustomer == NULL)
{
printf(“It is first record \n”); Customer->NextCustomer = NULL; Customer->PrevCustomer = NULL;
FirstCustomer = Customer;
LastCustomer = Customer; TempCustomer = NULL;
}
else
{
TempCustomer = FirstCustomer;
}
while (TempCustomer)
{
if (nDebug)
{
Part II • Managing Data in C
printf(“TESTING FOR ADD: ‘%s’ ‘%s’\n”, Customer->szName, TempCustomer->szName);
}
If this is not the list’s initial member, the program must go down the list searching for the correct insertion point. The record could be inserted in three places:
•At the beginning of the list, as the new first member.
•In the middle of the list.
•At the end of the list, as the last member.
Here is the code for inserting a member at the beginning of the list:
if (strcmp(Customer->szName, TempCustomer->szName) < 0 || TempCustomer == LastCustomer)
{
if (strcmp(Customer->szName, TempCustomer->szName) < 0 && TempCustomer == FirstCustomer)
{
if (nDebug)
{
printf(“Assigning as first\n”);
}
Customer->NextCustomer = FirstCustomer;
FirstCustomer = Customer;
Customer->PrevCustomer = NULL;
TempCustomer = Customer->NextCustomer;
TempCustomer->PrevCustomer = Customer;
When the member will be the first member in the list, the program updates the FirstCustomer variable and the old first member. The FirstCustomer variable and the old first member’s previous member pointer (->PrevCustomer) point to this new member. The new member’s previous member pointer (->PrevCustomer) points to NULL, and the new member’s next member pointer (->NextCustomer) points to the old first member (which has become the second member in the list).
Data Management: Sorts, Lists, and Indexes |
C C C |
|
10C |
|
C C C |
|
C C |
In Figure 10.6, the bold lines show which pointers must be changed when a record is inserted in the beginning of the list. Compare this figure with Figure 10.4.
Figure 10.6. Inserting a new member at the beginning of a linked list.
When the member will be the last member in the list, the LastCustomer variable and the old last member must be updated:
}
else
{
if (strcmp(Customer->szName, TempCustomer->szName) > 0 && TempCustomer == LastCustomer)
{
The LastCustomer variable and the old last member’s next member pointer (->NextCustomer) will now point to the new member. The new member’s next member pointer (->NextCustomer) will point to NULL, and the new member’s previous member pointer (->PrevCustomer) will point to the old last member (which has become the next-to-last member in the list).
The bold lines in Figure 10.7 show which pointers must be changed when a record is inserted at the end of the list. Compare this figure with Figure 10.4.
Part II • Managing Data in C
Figure 10.7. Inserting a new member at the end of a linked list.
The third insertion point is the middle of the list. Following is the code for inserting a member in the middle of the linked list:
if (nDebug)
{
printf(“Assigning as last\n”);
}
Customer->PrevCustomer = LastCustomer; LastCustomer = Customer; Customer->NextCustomer = NULL; TempCustomer = Customer->PrevCustomer; TempCustomer->NextCustomer = Customer;
}
else
{
if (nDebug)
{
printf(“Assigning inside list\n”);
}
The program must update what will be the previous customer’s next member pointer (->NextCustomer) to point to the new member. The new member’s prior member pointer (->PrevCustomer) will point to this previous customer member as
Data Management: Sorts, Lists, and Indexes |
C C C |
|
10C |
|
C C C |
|
C C |
well. The program must also update what will be the next customer’s prior member pointer (->PrevCustomer) to point to the new member. The new member’s next member pointer (->NextCustomer) will point to this next customer member as well.
See Figure 10.8, which shows what is happening when a member is inserted into the middle of the list. The bold lines indicate which pointers must be changed when a record is inserted in the middle of the list. Compare this figure with Figure 10.4.
Figure 10.8. Inserting a new member in the middle of a linked list.
The user must provide the program with other information, such as the address, city, and state. The program can get this information after the record has been inserted into the list. (However, you could change the program so that the information is obtained before the record insertion.)
Customer->PrevCustomer =
TempCustomer->PrevCustomer;
Customer->NextCustomer = TempCustomer; TempCustomer->PrevCustomer = Customer; TempCustomer = Customer->PrevCustomer; TempCustomer->NextCustomer = Customer;
}
}
The code to display records in the list in sorted order is simple because the program maintains sorted links.
