This month I'm venturing further into C++ with a new class, the LinkedList. Programmers have been using the linked list data structure for years. It allows you to store an unknown number of data items in a table where the entries do not need to be adjacent in memory. It also solves the problems encountered with standard arrays when the entries have different sizes. Here's how the linked list works.
A linked list data structure links a list of data items together with a set of pointers. The list itself has a pointer to the first and last entries in the list. These pointers are called the "list head." A linked list consists of the list head and the data entries. Each data entry in the list has a pointer to the one just previous to it and a pointer to the one just past it. The first and last pointers in the list head are initially NULL. They are initialized with non-NULL values when the first item is added to the list. The first item in the list has a NULL previous-item pointer, and the last item in the list has a NULL next-item pointer.
To traverse a linked list in a forward sequence, you start with the value in the first-item pointer from the list head. If that pointer is NULL, the list is empty. Otherwise, it points to the first data item. That item has a pointer to the next data item. You move forward by using the next-item pointer in each successive item until you find an item with a NULL next-item pointer, meaning you are at the end of the list. A reverse-sequence route through the list works the same way but starts with the last-item pointer in the list head and uses the previous-item pointer in the items.
To add an item to the end of the list, you make its previous-item pointer point to where the last-item pointer points, and you make the last-item pointer point to the new item. You must also make the next-item pointer in what was the last item point, with its next-item pointer, to the new item.
Deleting an entry from a linked list is a matter of breaking and repairing the next-last chain. The deleted item's previous item must now point to the deleted item's next item and vice versa. Of course, you must test if the deleted item is the first or last (or both) and repair the first and last pointers in the list head accordingly.
That's what a linked list is. They all work pretty much the same. Where they differ is in the format of the data items they manage. As such, the linked list is a good candidate to be a generic C++ class, and I'm sure that's not a new idea.
Listing One, page 152 and Listing Two, page 152, are linklist.h and linklist.cpp, the source files that implement the LinkedList class.
To use the LinkedList class, you include linklist.h in your program. Surrounding a data structure with the properties of a linked list is simply a matter of declaring a LinkedList object and adding those structures as entries to the list. The data structure itself can be as simple as a character and as complex as a new class. When you pass its address and size to the linked list member function (method) that adds entries, you control the data in a linked list. Here is how you declare a list:
That's all there is to it. Until the class goes out of scope, the list, empty at first, exists. Here is how you add data entries to the list:
If you declare a list and then begin to add entries, they will be added in turn at the end of the list. Each new entry follows the one just before it, and is at the end until another one comes along.
If you traverse a list and then add an entry while positioned in the middle of the list, the entry will be added just past the one you most recently retrieved. If you are positioned at the start of the list, the entry will be added as the first one.
To retrieve an entry from a linked list, you meander through the list forwards or backwards and look at the data values within each entry. Each of the member functions that pass through the list returns a pointer to the list entry that it found. Here are the methods for traversing the list:
You would call one of them in this manner:
Each of these member functions returns a pointer to the data value of the found entry. You can assign these returned values to a pointer to whatever you have in the list. If the list is empty or a list scan reaches the end or beginning, the function returns a NULL pointer.
To delete an entry, you navigate to it and call the member function that deletes the current entry. Here is the call for that operation:
Listing Three, page 152 is demolist.cpp, a C++ program that uses the LinkedList class to collect and manipulate a list of names. The program uses the string class from last month, and the first thing I realized was that the string class needs a member function that returns the size of the string. Now this is the time when a rigorously controlled object-oriented project would likely build a derived class just to add that feature. But, because we are not so rigorous, and not controlled at all, we'll just add the function to our original string class. Refer to strings.h from last month, and insert these lines with the member functions:
The demolist program prompts you to type some names into a string. It adds each name you type to a LinkedList. When you are done, you type "end," and the program displays a menu. You can display the names, insert a new name at the current location, move forward and backward through the list, and delete the current name.
The C++ code for the past few months works with Zortech C++. I compiled and ran the string code from last month with two other PC compilers, Intek C++ and Guidelines C++. These compilers are ports of the AT&T C++ 1.2 release, and, as such, are really language translators. You need a compiler as well as to compile the C code that the C++ translator builds from your C++ source code.
Intek C++ has versions that work with Watcom C, Turbo C, Microsoft C, and MetaWare High C. The Intek compiler works only on a 386 machine with extended memory. I had to disable my Expanded Memory Manager to use Intek C++, and I found one serious bug: The compiler driver program only works every other time you run it. It needs a control file, which it builds if it does not find it. After the compile is done, if the compile goes to completion, the compiler process deletes the file. The problem is that if the file is not there, the program builds it but aborts. If the file is there, the program uses it and deletes it. Therefore, the program works only every other time. The technical support people at Intek were not aware of this problem and seemed to think there was something wrong with my setup. Only after I told them the exact sequence of steps to reproduce the problem did they acknowledge and promise to fix it. I got around it with a batch file that saves and restores the critical control file. Because of the hardware requirements and the price ($495 plus the price of your compiler), I don't see much of a future for this product in the PC world.
Guidelines C++ is cheaper ($295) than Intek and does not require a 386 or extended memory. You do need to add the price of a compiler, however. Guidelines C++ is available to work with Microsoft C only, although they tell me a Turbo C version will be included when they release their port of the AT&T C++ 2.0 release, which should have occurred by the time you read this. I found no problems with Guidelines C++ other than those imposed by C++ 1.2 itself. The AT&T translator is not aware of the ANSI C treatment of void pointers against real pointers. ANSI C allows a function to have a prototype that specifies a void pointer. The calling function can pass any kind of pointer, and the called function deals with it as though it were a character pointer. Similarly, a function that is prototyped to return a void pointer can be called to assign its value to any kind of data pointer. This convention allows you to use functions such as malloc and memcpy without needing casts. It also allows the NULL global to be #defined as a void pointer with the value zero. The AT&T C++ 1.2 translator gags on such doings, and so the code in this month's column works with neither Intek nor Guidelines C. I gagged at putting all those casts in, being spoiled by my use of ANSI-conforming compilers of late, and so I decided to stick with Zortech C++ until the others come out with C++ 2.0.
The Zortech C++ compiler is a real bargain when compared to the others. It has a list price of $150, and you do not need another compiler to use it. It is built to work with the new-style ANSI conventions. (A C compiler comes with the package.) Its disadvantage is that it is not a pure port of the AT&T code; it does not share the same bugs and features with the rest of the C++ world, and so your code will not be as portable as you might want it to be.
Do you wonder why it takes so long to get a language standard approved? The ANSI X3J11 committee is nearing six years defining the standard for the C language. Perhaps this story will help to explain why.
Many years ago, I worked for a small consulting firm. We bid on a government contract that disqualified as bidders any manufacturers of computing equipment. The government awarded the job to a large firm, and my boss wrote a letter of protest saying the winning bidder should have been disqualified because they manufactured teletype machines, then a common console terminal device. Such a protest automatically invokes a bureaucratic procedure of response and usually delays the work until the matter is closed. Every time we got an official reply, we simply wrote another letter, keeping the wheels of inquiry turning while the wheels of progress were stuck. I asked him why he bothered. He said that the letters cost him only his time, while the rewards were in knowing that he had thrown a monkey wrench into the works. And, as he said, "... just because they p***ed me off."
The ANSI X3J11 committee has similarly irritated a C programmer, a Mr. Russell Hansberry, and he has responded in turn with an appeal that challenges the validity of X3J11's work. Like the nuisance letters of my whimsical boss of yore, this appeal has further delayed approval of the proposed C standard.
The first problem was that Hansberry's original comments were overlooked by the committee, probably lost in the shuffle. The committee, having mislaid the letter, failed to prepare the required formal response before submitting the draft standard to X3, and so the letter's author could and did demand that the committee back up and address his concerns.
X3J11 considered each of the points in the letter and voted to disapprove them all. There was much ado and flapdoodle, but the disapproval prevailed by democratic action. Most people who embrace the concepts of a self-governing free society would have accepted majority rule and retreated. Hansberry, apparently deciding that democracy was not working in his favor, chose instead to attack on other fronts. Justice is never swift where people are free. Hansberry exercised his rights and filed an appeal that raised 40 technical and procedural issues in an apparent attempt to invalidate all of the committee's work. X3 voted in August in a reconsideration ballot, and no negative votes were cast, so the technical issues of Hansberry's appeal were effectively defeated. The procedural issues, however, still remain, and they must be addressed before approval is final. If X3 votes down these issues, Hansberry can still appeal to ANSI. Some of his concerns have merit, but others are aimed at changing the language in ways that would endanger existing code. In the meantime, the rest of us are waiting for an approved standard for the C language.
Maybe next year....
Although the original charter for the ANSI C standard specification was to document a standard for existing practice of the C language, the proposed draft does add some features to the C language. The most notable of these is the new-style function definitions and declarations, called "prototypes," which were adopted from C++. Other new features are useful, too, but could possibly go unnoticed unless you took the time to learn them. Among these additions are trigraphs, hexadecimal escape sequences, a few new character constants, and adjacent string literals.
Trigraphs aren't as useful as the other additions, but you'll need to know about them because you might trip over them some day. A trigraph is a way to express those characters that C uses extensively but that do not exist in some non-ASCII character sets, most notably a set defined by the International Standards Organization as ISO 646. There are nine such characters that ISO 646 does not include. These are #, [, ], {, }, \, |, ~, and ^. Try writing a C program without them. To allow users of ISO 646 to program in C, ANSI has introduced the use of trigraphs as a way to express these characters. A trigraph is two question marks followed by a character that does exist in ISO 646 and that resembles the missing character. These are the trigraphs for the missing characters:
Write a program with these trigraphs, and it would probably win one of those stupid obfuscated C contests (or a beautiful APL contest). Nonetheless, the users of those other character sets should not be denied the language, and so some accommodation was needed. The trigraphs are an inelegant but workable solution. Most of us will never need to know about trigraphs except to deal with the rare occasion when we want to put "??" into a string while the compiler wants to turn it into a trigraph. (Use "? \ ?".)
In the C lexicon, an escape sequence is a value in a constant or string literal that begins with the backslash character and that translates into a character value. You already know about octal escape sequences. They have been in traditional K&R C since the beginning. You can code a character constant with an octal value like this:
The backslash character followed by an octal digit (O to 7) tells the compiler that the digits following the backslash form a character value from an octal expression. With ANSI-conforming compilers you can now also express character constants by using hexadecimal digits as shown here:
The backslash-x escape sequence tells the compiler that the digits that follow will be a hexadecimal character constant. Both examples just given form the character value for the ASCII 'A' and would be better expressed in this manner:
With an octal escape sequence, you are allowed from one to three octal digits (O to 7) to form the value. This gives you a theoretical maximum value of '\777' or 511. ANSI specifies, however, that a character constant cannot exceed the range of an unsigned char, which, on a PC is 8 bits wide or a maximum of '\377' or 255. Machines that have wide characters can have character constants that extend to that limit, but the three-digit limit for octal constants still applies, so the maximum for wide characters is 511 regardless of the wide character's width.
While an octal escape sequence can have no more than three digits, a hexadecimal character constant can have any number of hex digits following the backslash-x escape sequence. It, too, is restricted to the maximum value of the unsigned char, so its limit on a computer with an 8-bit character is '\ xf f' or wider if wide characters are implemented. Other character sets might have much wider character sizes, so ANSI does not define a theoretical limit for the hexadecimal character constant, thus allowing for the expression of all character constant values in those cultures (Japan, for example) where there are far more than 256 characters in the character set.
Several common character values cannot be expressed with single alphabetic, numeric, or graphic characters. The Escape and Carriage Return characters are two examples. You could express these characters with octal or hexadecimal character constants, but such expressions would not be portable to machines with incompatible character sets. ANSI provides for escape sequences for some but not all of the non-displayable characters. The values shown here are in the standard for some of the character constants that have, in the ANSI view, universal application:
The '\ a' and '\ v' were added by X3J11.
They were not a part of the K&R definition, but the committee added them to the standard because they have universal application. Most console devices have a bell (BEL in ASCII) character that sounds an audible alarm, and many printers will respond to a vertical tab character. ANSI decided not to include '\ e' for the Escape character because some character sets -- EBCDIC, for example -- have no equivalent character.
Some displayable ASCII characters have meaning in the context of a character constant or string literal. To allow you to represent these characters, ANSI provides the following escape sequences to provide portable expressions of their values:
The single quote needs the backslash in a character constant but will work either way in a string literal. Conversely, the double quote needs the backslash in a string literal but works either way in a character constant.
The '\?' is specified in the ANSI draft to accommodate its expression in character sets that require the trigraphs discussed earlier. To get a double question mark in a string, you code "?\?".
Although the draft is not specific at this point, if a backslash is followed by anything other than an octal digit or one of the characters ?, '< ", a, b, f, n, r, t, v, x, ', or \, the lonely backslash is ignored (unless nothing follows it on the line, in which case the string is assumed to continue in the first position of the next line). At least that is a convention followed by most so-called ANSI-conforming compilers.
You can put octal and hexadecimal escape sequences into character string literals as well, making these usages possible, all of which deliver the same string value.
An octal escape sequence in a string continues until the compiler finds a non-octal digit or hits the third octal digit. A hexadecimal escape sequence continues for as long as the compiler finds hexadecimal digits. Compilers should warn you if the character values formed exceed the upper limit of a character on the computer.
Obviously, the third format is what you would use for the value given in the example above, but there are occasions where you will want string values that contain characters not represented by displayable characters. The control strings that command an ANSI video terminal use an Escape sequence to let the terminal know that a command is coming. To clear the screen on an ANSI terminal (or a PC with ANSI.SYS installed), you can use this statement:
The " \ 33" is an octal escape sequence that forms the single character value for the Escape character. Suppose your command string needed to have the Escape character followed by "345". This string would not work:
The compiler would treat the third '3' as part of the octal character constant and would build a string that began with the character '\ 333' followed by "45". Because octal character constants are limited to three digits, you can code the string this way:
The leading zero does the trick by forcing the \ 033 into the maximum three digits. (Users of Turbo C 2.0 should be aware that a bug in the compiler makes it think that all the digits in the string are part of the octal constant.)
Here is the clear-screen statement with a hexadecimal escape sequence:
The " \ x1b" is the hexadecimal escape sequence for the Escape character. Suppose now that you wanted the Escape, "345" string used above. This would not work:
The compiler would assume that all the digits following the " \x" are part of the character constant because hexadecimal character constants can be wider than two digits. A compiler for an 8-bit character machine should issue a warning for this example, because the value exceeds the range of the unsigned character. It should not, however, assume that you meant it to be Escape, "345" just because you have 8-bit characters. Such a convention would promote the development of non-portable code. So, how do you get it to work? You could write it this way:
That would work, but only where you are using the printf-style formatted output. Suppose you wanted to write the string with the puts function instead of printf. For that purpose ANSI introduced the adjacent string literal.
If you code two string literals side-by-side, they are concatenated as one null-terminated string. Here is a familiar example:
This feature has several advantages. You can express long string literals more legibly by breaking them into several adjacent strings and putting each part on its own line. But, even better, the problem of the hexadecimal character escape sequence is solved. Now we can do this:
And, finally, a more descriptive way of coding the string is this:
One other thing X3J11 added to our culture was the word, "stringizing," which they coined to mean something new for the C preprocessor. It's an awful word but a useful feature. I'll use the feature, but I'll never use the word again except maybe to tell you how awful it is. Next month I'll explain the feature with the awful S word.
_C PROGRAMMING COLUMN_
by Al Stevens
[LISTING ONE]
Copyright © 1989, Dr. Dobb's Journal LinkList mylist;
mylist.addentry(&data, sizeof(data));
void *getfirst(void);
void *getnext(void);
void *getprev(void);
void *getlast(void);
void *getcurr(void);
char *cp = mylist.getfirst();
mylist.delete_entry();
// -------- return the length of a string
int length(void) { return strlen(sptr)+1;}
C++ Compilers
The ANSI Corner: Protests, Trigraphs, Escape Sequences, and Strings
ANSI Additions
Trigraphs
Trigraph Replaces
??= #
??( [
??/ \
??) ]
??' ^
??< {
??! |
??> }
??- ~
Escape Sequences
char c = '\ 101';
char c = '\ x 41';
char c = 'A';
'\a' audible alarm
'\b' backspace
'\f' form feed
'\n' newline
'\r' carriage return
'\t' horizontal tab
'\v' vertical tab
'\" single quote
'\"' double quote
'\?' question mark
'\\' backslash
Strings
char *cp = "\ 101phids";
char *cp = "\ x41phids";
char *cp = "Aphids";
printf(" \ 33[2J");
printf(" \ 333 45");
printf(" \ 0 333 45");
printf(" \ x1b [2J");
printf(" \ x 1b 3 45");
printf(" % d 3 4 5", '\ x1b');
Adjacent String Literals
printf("Hello," " world");
printf(" \ x1b" "345");
#define ESCAPE " \ x1b"
printf(ESCAPE "345");
Nobody Says the S Word....
<a name="0243_000d">
// -------- linklist.h
#ifndef LINKLIST
#define LINKLIST
#include <stdio.h>
class LinkedList {
typedef struct list_entry {
struct list_entry *NextEntry;
struct list_entry *PrevEntry;
void *entrydata;
} ListEntry;
ListEntry *FirstEntry;
ListEntry *LastEntry;
ListEntry *CurrEntry;
public:
// ---- constructor
LinkedList(void)
{ FirstEntry = LastEntry = CurrEntry = NULL; }
// ---- destructor
~LinkedList(void);
// ---- add an entry
void addentry(void *newentry, int size);
// ---- delete the current entry
void delete_entry(void);
// ---- get the first entry in the list
void *getfirst(void);
// ---- get the next entry in the list
void *getnext(void);
// ---- get the previous entry in the list
void *getprev(void);
// ---- get the last entry in the list
void *getlast(void);
// ---- get the current entry in the list
void *getcurr(void)
{return CurrEntry==NULL ? NULL : CurrEntry->entrydata;}
};
#endif
<a name="0243_000e"><a name="0243_000e">
<a name="0243_000f">[LISTING TWO]<a name="0243_000f">
// -------------- linklist.cpp
#include <string.h>
#include "linklist.h"
// ------- linked list destructor
LinkedList::~LinkedList(void)
{
ListEntry *thisentry = FirstEntry;
while (thisentry != NULL) {
delete thisentry->entrydata;
ListEntry *hold = thisentry;
thisentry = thisentry->NextEntry;
delete hold;
}
}
// --------- add an entry to the list
void LinkedList::addentry(void *newentry, int size)
{
/* ------- build the new entry ------- */
ListEntry *thisentry = new ListEntry;
thisentry->entrydata = new char[size];
memcpy(thisentry->entrydata, newentry, size);
if (CurrEntry == NULL) {
thisentry->PrevEntry = NULL;
// ---- adding to the beginning of the list
if (FirstEntry != NULL) {
/* ---- already entries in this list ---- */
thisentry->NextEntry = FirstEntry;
FirstEntry->PrevEntry = thisentry;
}
else {
// ----- adding to an empty list
thisentry->NextEntry = NULL;
LastEntry = thisentry;
}
FirstEntry = thisentry;
}
else {
// ------- inserting into the list
thisentry->NextEntry = CurrEntry->NextEntry;
thisentry->PrevEntry = CurrEntry;
if (CurrEntry == LastEntry)
// ---- adding to the end of the list
LastEntry = thisentry;
else
// ---- inserting between existing entries
CurrEntry->NextEntry->PrevEntry = thisentry;
CurrEntry->NextEntry = thisentry;
}
CurrEntry = thisentry;
}
// ---------- delete the current entry from the list
void LinkedList::delete_entry(void)
{
if (CurrEntry != NULL) {
if (CurrEntry->NextEntry != NULL)
CurrEntry->NextEntry->PrevEntry = CurrEntry->PrevEntry;
else
LastEntry = CurrEntry->PrevEntry;
if (CurrEntry->PrevEntry != NULL)
CurrEntry->PrevEntry->NextEntry = CurrEntry->NextEntry;
else
FirstEntry = CurrEntry->NextEntry;
delete CurrEntry->entrydata;
ListEntry *hold = CurrEntry->NextEntry;
delete CurrEntry;
CurrEntry = hold;
}
}
// ---- get the first entry in the list
void *LinkedList::getfirst(void)
{
CurrEntry = FirstEntry;
return CurrEntry == NULL ? NULL : CurrEntry->entrydata;
}
// ---- get the next entry in the list
void *LinkedList::getnext(void)
{
if (CurrEntry == NULL)
CurrEntry = FirstEntry;
else
CurrEntry = CurrEntry->NextEntry;
return CurrEntry == NULL ? NULL : CurrEntry->entrydata;
}
// ---- get the previous entry in the list
void *LinkedList::getprev(void)
{
if (CurrEntry == NULL)
CurrEntry = LastEntry;
else
CurrEntry = CurrEntry->PrevEntry;
return CurrEntry == NULL ? NULL : CurrEntry->entrydata;
}
// ---- get the last entry in the list
void *LinkedList::getlast(void)
{
CurrEntry = LastEntry;
return CurrEntry == NULL ? NULL : CurrEntry->entrydata;
}
<a name="0243_0010"><a name="0243_0010">
<a name="0243_0011">[LISTING THREE]<a name="0243_0011">
// -------- demolist.cpp
#include <stream.hpp>
#include "strings.h"
#include "linklist.h"
void collectnames(LinkedList& namelist);
int menu(void);
void displaynames(LinkedList& namelist);
void stepforward(LinkedList& namelist);
void stepbackward(LinkedList& namelist);
string insertname(LinkedList& namelist);
void main(void)
{
cout << "Enter some names followed by \"end\"\n";
// ------ a linked list of names
LinkedList namelist;
collectnames(namelist);
int key = 0;
while (key != 6) {
switch (key = menu()) {
case 1:
displaynames(namelist);
break;
case 2:
stepforward(namelist);
break;
case 3:
stepbackward(namelist);
break;
case 4:
insertname(namelist);
break;
case 5:
namelist.delete_entry();
break;
case 6:
cout << "Quitting...";
break;
default:
break;
}
}
}
void collectnames(LinkedList& namelist)
{
// ------- until the user types "end"
while (insertname(namelist) != "end")
;
}
int menu(void)
{
cout << "\n1 = display the names";
cout << "\n2 = step forward through the names";
cout << "\n3 = step backward through the names";
cout << "\n4 = insert a name";
cout << "\n5 = delete the current name";
cout << "\n6 = quit";
cout << "\nEnter selection: ";
int key;
cin >> key;
return key;
}
// ------ read the names in a list and display them
void displaynames(LinkedList& namelist)
{
cout << "------ NAME LIST ------\n";
char *name = namelist.getfirst();
while (name != NULL) {
cout << name << "\n";
name = namelist.getnext();
}
cout << "-----------------------\n";
}
// ------- step forward through the list of names
void stepforward(LinkedList& namelist)
{
char *name = namelist.getnext();
cout << (name ? name : "-- End of list --") << "\n";
}
// ------- step backwardward through the list of names
void stepbackward(LinkedList& namelist)
{
char *name = namelist.getprev();
cout << (name ? name : "-- Beginning of list --") << "\n";
}
// ------- insert a name into the list
string insertname(LinkedList& namelist)
{
cout << "Enter a name: ";
// ----- a string to hold one name
string name(80);
// ------- read a name
cin >> name.stradr();
// ------- add it to the list
if (name != "end")
namelist.addentry(name.stradr(), name.length());
return name;
}
