CS13002 Programming and Data Structures | Section 3/C, Spring 2003--2004 |
Lab Test III : Solution
Since my PC number is odd (53), I am solving only the Aquarium problem. `Even' students can readily change this code to suit their needs. In fact, the only difference will be in the names of the routines and the names of the animals.
Since I am given full flexibility to program as I like, I plan to carry out this assignment in an unconventional fashion. In fact, I write two programs. The first (genaqua.c) generates a random sequence of add/del/cnt commands on the given database of aquatic animals. The second program (aqua.c) reads the sequence of commands output by the first program and executes them one by one. I compile and run the programs in the following manner. Here $ represents the shell prompt.
$cc -o genaqua genaqua.c $cc -o aqua aqua.c $genaqua | aqua > aqua.outThe program genaqua generates output of the from:
add "Water Frog" 6 cnt "Platy" cnt "Cichlid" cnt "Killifish" add "Giant Danio" 6 add "Water Frog" 2 add "Rainbowfish" 1 add "Dwarf Rasbora" 1 add "Pygmy Rasbora" 2 add "Giant Danio" 5 add "Water Frog" 9 add "Rainbowfish" 4 cnt "Killifish" ... add "Pygmy Rasbora" 2 cnt "Snail" add "Guppy" 4 add "Water Frog" 4 add "Shrimp" 8 del "Labyrinth Fish" 9 dpy endThese are precisely the kinds of commands that the ADT program aqua understands. Instead of manually entering these commands I connect the output (stdout) of genaqua to the input (stdin) of aqua. This connection is established by the pipe command |. Finally, the output of aqua is redirected to the file aqua.out. You are instructed to save the C files, compile them in your machine, run each executable individually to understand their input/output behavior, and finally to use the pipe command to see how the transfer of the data among programs is handled by the system without your manual intervention. Unix is powerful!
Now here are the relevant files:
Command generator program: genaqua.c
#include <stdio.h> #define REQ_CNT 100 #define MAX_CNT 9 int nspecies; char spNames[64][128]; void addSpecies ( const char spName[] ) { strcpy(spNames[nspecies++],spName); } void addAllSpecies () { nspecies = 0; addSpecies("Catfish"); addSpecies("Goldfish"); addSpecies("Angelfish"); addSpecies("Rainbowfish"); addSpecies("Cichlid"); addSpecies("Rosy Barb"); addSpecies("Tiger Barb"); addSpecies("Cherry Barb"); addSpecies("Zebra Danio"); addSpecies("Pearl Danio"); addSpecies("Giant Danio"); addSpecies("Dwarf Rasbora"); addSpecies("Pygmy Rasbora"); addSpecies("Spotted Rasbora"); addSpecies("Red Rasbora"); addSpecies("Harlequin Fish"); addSpecies("Killifish"); addSpecies("Labyrinth Fish"); addSpecies("Platy"); addSpecies("Swordtail"); addSpecies("Molly"); addSpecies("Guppy"); addSpecies("Loach"); addSpecies("Characin"); addSpecies("Silverside"); addSpecies("Snail"); addSpecies("Shrimp"); addSpecies("Crab"); addSpecies("Water Frog"); } int main () { int i, j; srand((unsigned int)time(NULL)); addAllSpecies(); /* printf("nspecies = %d\n", nspecies); */ printf("new\n"); for (i=0; i<REQ_CNT; i++) { j = rand() & 7; if (!j) printf("cnt \"%s\"\n", spNames[rand()%nspecies]); else { printf("%s ",((i>=20)&&(j==1))?"del":"add"); printf("\"%s\" ",spNames[rand()%nspecies]); printf("%d\n",1+rand()%MAX_CNT); } } printf("dpy\n"); printf("end\n"); }Program that implements the ADT: aqua.c
#include <stdio.h> #include <string.h> typedef struct _node { /* Node in a linked list */ char *name; /* Name of the species */ int count; /* Count of the animals of the given species */ struct _node *next; /* The next pointer */ } node; typedef node *aquarium; aquarium newAquarium () { node *p; /* Create a dummy node at the beginning. This node helps add and delete routines much easier. */ p = (node *)malloc(sizeof(node)); p->name = NULL; p->count = 0; p->next = NULL; printf("New aquarium created.\n"); return(p); } void add ( aquarium A , const char spName[] , int n ) { node *p, *q; int cmpres; if (A == NULL) { printf("Error: uninitialized aquarium.\n"); return; } if (n <= 0) { printf("Error: positive integer expected.\n"); return; } /* Now we search the proper position for insertion. p points to the current node in the list and q the previous node. */ q = A; p = A->next; while (1) { if (p == NULL) cmpres = -1; /* To append a new record at the end */ else cmpres = strcmp(spName,p->name); if (cmpres == 0) { /* Node is already existing */ p->count += n; /* Just add the count */ printf("Current count of \"%s\" is %d.\n", spName, p->count); return; } if (cmpres < 0) { /* Insert between q and p */ p = (node *)malloc(sizeof(node)); p->name = (char *)malloc((1+strlen(spName))*sizeof(char)); strcpy(p->name,spName); p->count = n; p->next = q->next; q->next = p; printf("Current count of \"%s\" is %d.\n", spName, p->count); return; } /* Could not insert. Look at the next node. */ q = p; p = p->next; } } void del ( aquarium A , const char spName[] , int n ) { node *p, *q; int cmpres; if (A == NULL) { printf("Error: uninitialized aquarium.\n"); return; } if (n <= 0) { printf("Error: positive integer expected.\n"); return; } /* Search the existence of the node. p points to the current node and q to the previous one. */ q = A; p = A->next; while (1) { if (p == NULL) cmpres = -1; /* End of list reached. */ else cmpres = strcmp(spName,p->name); if (cmpres < 0) { /* The desired node is not found. */ printf("Error: Current count of \"%s\" is 0.\n", spName); return; } if (cmpres == 0) { /* The desired node is found. */ if (n > p->count) { /* Too many occurrences to delete */ printf("Error: Current count of \"%s\" is %d.\n", spName, p->count); return; } else p->count -= n; /* Delete occurrences */ printf("Current count of \"%s\" is %d.\n", spName, p->count); if (p->count == 0) { /* Delete the node pointed to by p */ q->next = p->next; free(p->name); p->name = NULL; free(p); } return; } /* Continue with the search */ q = p; p = p->next; } } void cnt ( aquarium A , const char spName[] ) { node *p; int cmpres; p = A->next; while (1) { if (p == NULL) cmpres = -1; /* End of list reached */ else cmpres = strcmp(spName,p->name); if (cmpres < 0) { /* The species is missing in the list */ printf("Current count of \"%s\" is 0.\n", spName); return; } if (cmpres == 0) { /* Node for the given species is found */ printf("Current count of \"%s\" is %d.\n", spName, p->count); return; } /* Look at the next node */ p = p->next; } } void dpy ( aquarium A ) { node *p; printf("\n"); p = A->next; while (p != NULL) { printf("%25s %d\n",p->name,p->count); /* Print current node */ p = p->next; /* Go to the next node */ } } int main () { char cmd[1024], *p, *q; aquarium A = NULL; while (1) { /* The command interpreter loop */ printf("Aquarium> "); fgets(cmd,1024,stdin); cmd[strlen(cmd)-1] = '\0'; printf("%s : ", cmd); if (!strncmp(cmd,"new",3)) { A = newAquarium(); } else if (!strncmp(cmd,"add",3)) { p = cmd + 5; q = strrchr(cmd,' '); if (q == NULL) printf("Error: invalid operand\n"); --q; *q = '\0'; q += 2; add(A,p,atoi(q)); } else if (!strncmp(cmd,"del",3)) { p = cmd + 5; q = strrchr(cmd,' '); if (q == NULL) printf("Error: invalid operand\n"); --q; *q = '\0'; q += 2; del(A,p,atoi(q)); } else if (!strncmp(cmd,"dpy",3)) { dpy(A); } else if (!strncmp(cmd,"cnt",3)) { p = cmd + 5; cmd[strlen(cmd)-1] = '\0'; cnt(A,p); } else if (!strncmp(cmd,"end",3)) { printf("Quitting...\n"); exit(0); } else { printf("Unknown command.\n"); } } }The output file: aqua.out
Aquarium> new : New aquarium created. Aquarium> add "Crab" 2 : Current count of "Crab" is 2. Aquarium> add "Goldfish" 1 : Current count of "Goldfish" is 1. Aquarium> add "Silverside" 2 : Current count of "Silverside" is 2. Aquarium> add "Labyrinth Fish" 7 : Current count of "Labyrinth Fish" is 7. Aquarium> add "Red Rasbora" 6 : Current count of "Red Rasbora" is 6. Aquarium> add "Harlequin Fish" 3 : Current count of "Harlequin Fish" is 3. Aquarium> add "Red Rasbora" 9 : Current count of "Red Rasbora" is 15. Aquarium> cnt "Labyrinth Fish" : Current count of "Labyrinth Fish" is 7. Aquarium> add "Goldfish" 8 : Current count of "Goldfish" is 9. Aquarium> add "Giant Danio" 4 : Current count of "Giant Danio" is 4. Aquarium> cnt "Catfish" : Current count of "Catfish" is 0. Aquarium> add "Tiger Barb" 6 : Current count of "Tiger Barb" is 6. Aquarium> add "Water Frog" 5 : Current count of "Water Frog" is 5. Aquarium> cnt "Characin" : Current count of "Characin" is 0. Aquarium> add "Giant Danio" 3 : Current count of "Giant Danio" is 7. Aquarium> add "Crab" 9 : Current count of "Crab" is 11. Aquarium> add "Crab" 2 : Current count of "Crab" is 13. Aquarium> add "Catfish" 5 : Current count of "Catfish" is 5. Aquarium> add "Labyrinth Fish" 8 : Current count of "Labyrinth Fish" is 15. Aquarium> add "Giant Danio" 7 : Current count of "Giant Danio" is 14. Aquarium> add "Molly" 1 : Current count of "Molly" is 1. Aquarium> add "Pygmy Rasbora" 1 : Current count of "Pygmy Rasbora" is 1. Aquarium> add "Shrimp" 6 : Current count of "Shrimp" is 6. Aquarium> add "Water Frog" 6 : Current count of "Water Frog" is 11. Aquarium> add "Shrimp" 8 : Current count of "Shrimp" is 14. Aquarium> add "Silverside" 2 : Current count of "Silverside" is 4. Aquarium> add "Characin" 2 : Current count of "Characin" is 2. Aquarium> add "Guppy" 7 : Current count of "Guppy" is 7. Aquarium> add "Platy" 6 : Current count of "Platy" is 6. Aquarium> del "Molly" 4 : Error: Current count of "Molly" is 1. Aquarium> add "Giant Danio" 4 : Current count of "Giant Danio" is 18. Aquarium> add "Cherry Barb" 9 : Current count of "Cherry Barb" is 9. Aquarium> add "Dwarf Rasbora" 8 : Current count of "Dwarf Rasbora" is 8. Aquarium> add "Spotted Rasbora" 9 : Current count of "Spotted Rasbora" is 9. Aquarium> del "Characin" 4 : Error: Current count of "Characin" is 2. Aquarium> cnt "Harlequin Fish" : Current count of "Harlequin Fish" is 3. Aquarium> cnt "Cherry Barb" : Current count of "Cherry Barb" is 9. Aquarium> add "Characin" 9 : Current count of "Characin" is 11. Aquarium> add "Cherry Barb" 7 : Current count of "Cherry Barb" is 16. Aquarium> add "Labyrinth Fish" 1 : Current count of "Labyrinth Fish" is 16. Aquarium> cnt "Zebra Danio" : Current count of "Zebra Danio" is 0. Aquarium> add "Crab" 5 : Current count of "Crab" is 18. Aquarium> add "Pygmy Rasbora" 1 : Current count of "Pygmy Rasbora" is 2. Aquarium> add "Guppy" 7 : Current count of "Guppy" is 14. Aquarium> add "Rainbowfish" 3 : Current count of "Rainbowfish" is 3. Aquarium> add "Tiger Barb" 1 : Current count of "Tiger Barb" is 7. Aquarium> add "Cichlid" 9 : Current count of "Cichlid" is 9. Aquarium> add "Rainbowfish" 3 : Current count of "Rainbowfish" is 6. Aquarium> add "Silverside" 3 : Current count of "Silverside" is 7. Aquarium> del "Guppy" 3 : Current count of "Guppy" is 11. Aquarium> add "Swordtail" 8 : Current count of "Swordtail" is 8. Aquarium> add "Catfish" 7 : Current count of "Catfish" is 12. Aquarium> cnt "Shrimp" : Current count of "Shrimp" is 14. Aquarium> add "Crab" 8 : Current count of "Crab" is 26. Aquarium> add "Crab" 9 : Current count of "Crab" is 35. Aquarium> cnt "Dwarf Rasbora" : Current count of "Dwarf Rasbora" is 8. Aquarium> add "Snail" 2 : Current count of "Snail" is 2. Aquarium> add "Catfish" 1 : Current count of "Catfish" is 13. Aquarium> del "Cichlid" 3 : Current count of "Cichlid" is 6. Aquarium> add "Molly" 3 : Current count of "Molly" is 4. Aquarium> add "Pygmy Rasbora" 5 : Current count of "Pygmy Rasbora" is 7. Aquarium> add "Angelfish" 2 : Current count of "Angelfish" is 2. Aquarium> add "Silverside" 8 : Current count of "Silverside" is 15. Aquarium> add "Guppy" 7 : Current count of "Guppy" is 18. Aquarium> cnt "Spotted Rasbora" : Current count of "Spotted Rasbora" is 9. Aquarium> add "Crab" 7 : Current count of "Crab" is 42. Aquarium> add "Giant Danio" 6 : Current count of "Giant Danio" is 24. Aquarium> cnt "Spotted Rasbora" : Current count of "Spotted Rasbora" is 9. Aquarium> del "Catfish" 4 : Current count of "Catfish" is 9. Aquarium> add "Snail" 5 : Current count of "Snail" is 7. Aquarium> add "Killifish" 7 : Current count of "Killifish" is 7. Aquarium> add "Water Frog" 1 : Current count of "Water Frog" is 12. Aquarium> add "Angelfish" 2 : Current count of "Angelfish" is 4. Aquarium> add "Platy" 9 : Current count of "Platy" is 15. Aquarium> add "Giant Danio" 5 : Current count of "Giant Danio" is 29. Aquarium> add "Characin" 6 : Current count of "Characin" is 17. Aquarium> add "Zebra Danio" 8 : Current count of "Zebra Danio" is 8. Aquarium> add "Killifish" 4 : Current count of "Killifish" is 11. Aquarium> cnt "Platy" : Current count of "Platy" is 15. Aquarium> del "Rosy Barb" 6 : Error: Current count of "Rosy Barb" is 0. Aquarium> cnt "Characin" : Current count of "Characin" is 17. Aquarium> cnt "Labyrinth Fish" : Current count of "Labyrinth Fish" is 16. Aquarium> add "Pearl Danio" 4 : Current count of "Pearl Danio" is 4. Aquarium> add "Dwarf Rasbora" 7 : Current count of "Dwarf Rasbora" is 15. Aquarium> add "Harlequin Fish" 9 : Current count of "Harlequin Fish" is 12. Aquarium> del "Guppy" 4 : Current count of "Guppy" is 14. Aquarium> add "Crab" 5 : Current count of "Crab" is 47. Aquarium> add "Rainbowfish" 3 : Current count of "Rainbowfish" is 9. Aquarium> add "Giant Danio" 8 : Current count of "Giant Danio" is 37. Aquarium> add "Red Rasbora" 6 : Current count of "Red Rasbora" is 21. Aquarium> add "Pygmy Rasbora" 2 : Current count of "Pygmy Rasbora" is 9. Aquarium> add "Tiger Barb" 2 : Current count of "Tiger Barb" is 9. Aquarium> add "Loach" 8 : Current count of "Loach" is 8. Aquarium> add "Goldfish" 8 : Current count of "Goldfish" is 17. Aquarium> cnt "Loach" : Current count of "Loach" is 8. Aquarium> del "Spotted Rasbora" 3 : Current count of "Spotted Rasbora" is 6. Aquarium> add "Cherry Barb" 4 : Current count of "Cherry Barb" is 20. Aquarium> add "Silverside" 9 : Current count of "Silverside" is 24. Aquarium> cnt "Pygmy Rasbora" : Current count of "Pygmy Rasbora" is 9. Aquarium> add "Cichlid" 8 : Current count of "Cichlid" is 14. Aquarium> dpy : Angelfish 4 Catfish 9 Characin 17 Cherry Barb 20 Cichlid 14 Crab 47 Dwarf Rasbora 15 Giant Danio 37 Goldfish 17 Guppy 14 Harlequin Fish 12 Killifish 11 Labyrinth Fish 16 Loach 8 Molly 4 Pearl Danio 4 Platy 15 Pygmy Rasbora 9 Rainbowfish 9 Red Rasbora 21 Shrimp 14 Silverside 24 Snail 7 Spotted Rasbora 6 Swordtail 8 Tiger Barb 9 Water Frog 12 Zebra Danio 8 Aquarium> end : Quitting...