The example below works through an implementation for a linked list of key value pairs. (Key/value pairs are a commonly used data storage/retrieval concept)
A key/value pair has a name and an associated value, typically
both stored as strings (here representing strings with character arrays of size 80).
The meaning associated with the value
depends entirely on how the information is used, but a pair might
look something like:
Key: "Student1317921Mark"
Value: "78.5%"
To maintain a collection of pairs we could use a linked list, where each item in the list is a key/value pair, and each item includes a pointer to the next pair in the list.
For the list as a whole we might want additional information such as a name for the list (E.g. "StudentMarks") and a pointer to the first pair in the list.
Exercise: read and comment the code below, making sure you understand how/why the various routines work.
// KeyValue pairs:
// each has a string key and value,
// along with a pointer to the next key/value pair
// (if any) to allow lists of pairs
const int Len = 80;
typedef char string[80];
struct KeyValue {
string key, value;
KeyValue *next;
};
|
// print the contents (key and value) of a pair
void printKV(KeyValue kv)
{
printf("Key: %s = %s\n", kv.key, kv.value);
}
|
// AllPairs:
// allows storage of a list of key/value pairs
// under a specific heading or title
// tracks the number of pairs currently stored
// and a pointer to the front pair in the list
struct AllPairs {
string title;
int numPairs;
KeyValue *front;
};
|
// initialize an empty list of pairs, setting the title void initialize(AllPairs &list, string title); // find the KeyValue element in the list whose value matches key, // returning a pointer to it KeyValue* lookup(AllPairs list, string key); // see if the list contains an element with the specified key // if it does NOT then return false // otherwise get the associated value and return true bool lookup(AllPairs list, string key, string &value); // insert a new key/value pair in the list bool insert(AllPairs &list, string key, string value); // update the value associated with a key in the list bool update(AllPairs list, string key, string value); // print all the key/value pairs currently in the list void printAP(AllPairs list); // deallocate the list contents void deallocate(AllPairs &list); |
void initialize(AllPairs &list, string title)
{
list.title = title;
list.front = NULL;
list.numPairs = 0;
}
KeyValue* lookup(AllPairs list, string key)
{
KeyValue *curr = list.front;
while (curr) {
if (curr->key == key) return curr;
curr = curr->next;
}
return NULL;
}
bool lookup(AllPairs list, string key, string &value)
{
KeyValue* curr = lookup(list, key);
if (!curr) return false;
value = curr->value;
return true;
}
bool insert(AllPairs &list, string key, string value)
{
string v = "";
if (lookup(list, key, v)) {
printf("key %s is alread in the list", key);
printf(" with value %s,\n", v);
printf("use the %c", << (char)(Update));
printf(" command to alter its value\n");
return false;
}
KeyValue *newPair = new KeyValue;
if (!newPair) return false;
newPair->key = key;
newPair->value = value;
newPair->next = list.front;
list.front = newPair;
list.numPairs++;
return true;
}
bool update(AllPairs list, string key, string value)
{
KeyValue* kv = lookup(list, key);
if (!kv) return false;
kv->value = value;
return true;
}
void deallocate(AllPairs &list)
{
KeyValue *curr = list.front;
while (curr) {
KeyValue *victim = curr;
curr = curr->next;
delete victim;
}
list.front = NULL;
}
void printAP(AllPairs list)
{
printf("%s contents:\n", list.title);
KeyValue *curr = list.front;
while (curr) {
printKV(*curr);
curr = curr->next;
}
}
|
enum Commands {
DoNothing = 'N', Lookup = 'L', Insert = 'I', Help = 'H',
Update = 'U', Print = 'P', Quit = 'Q', Deallocate = 'D'
};
void printMenu();
Commands selectCmd();
void processCmd(Commands cmd, AllPairs &AP);
string getTitle();
// =================================================
int main()
{
AllPairs myList;
Commands cmd;
initialize(myList, getTitle());
printMenu();
do {
cmd = selectCmd();
processCmd(cmd, myList);
} while (cmd != Quit);
}
// =================================================
// Control operations
// Commands: DoNothing, Lookup, Insert,
// Update, Print, Quit, Deallocate
string getTitle()
{
string title;
printf("Enter a title for the list of key/value pairs\n");
scanf("%80s", title);
return title;
}
void printMenu()
{
printf("Enter %c to lookup a key\'s value,\n", (char)(Lookup));
printf(" or %c to update a key\'s value,\n", (char)(Update));
printf(" or %c to insert a new key/value pair,\n", (char)(Insert));
printf(" or %c to print the list of key/value pairs,\n", (char)(Print));
printf(" or %c to delete the list of key/value pairs,\n", (char)(Deallocate));
printf(" or %c for help,\n", (char)(Help));
printf(" or %c to quit\n", (char)(Quit));
}
Commands selectCmd()
{
char cmd;
printf("Enter your command:\n");
scanf("%c", &cmd);
cmd = toupper(cmd);
switch (cmd) {
case Lookup:
case Update:
case Insert:
case Print:
case Help:
case Deallocate:
case Quit:
return (Commands)(cmd);
default:
printf("Invalid command selected \'%c", cmd);
printf("\', please try again\n");
printMenu();
return DoNothing;
}
}
void processCmd(Commands cmd, AllPairs &AP)
{
string key, value;
switch (cmd) {
case Lookup:
printf("Enter the key whose value you wish to look up\n");
scanf("%80s", key);
if (!lookup(AP, key, value)) {
printf("No key found matching %s\n", key);
} else {
printf("Key %s has value %s\n", key, value);
}
break;
case Update:
printf("Enter the key whose value you wish to update\n");
scanf("%80s", key);
printf("Enter the new value you wish to apply\n");
scanf("%80s", value);
if (!update(AP, key, value)) {
printf("Update unsuccessful\n");
}
break;
case Insert:
printf("Enter the new key and value you wish to insert\n");
printf("Key:");
scanf("%80s", key);
printf("Value:");
scanf("%80s", value);
if (!insert(AP, key, value)) {
printf("Insert unsuccessful\n");
}
break;
case Print: printAP(AP);
break;
case Deallocate: deallocate(AP);
break;
case Quit: printf("Bye!\n");
break;
case Help: printMenu();
break;
default:
break;
}
}
|