home *** CD-ROM | disk | FTP | other *** search
/ Resource for Source: C/C++ / Resource for Source - C-C++.iso / codelib8 / v_10_06 / 1006095a < prev    next >
Encoding:
Text File  |  1995-11-01  |  6.3 KB  |  268 lines
  1.  
  2. /* --------------------------------------------------------------
  3.  
  4. This program creates and manages a queue of strings stored as a
  5. linked list.  Each node of this list represents an entry in the
  6. queue.  The user can either add new entries to the rear of the
  7. queue or remove old entries from the front.
  8.  
  9. -------------------------------------------------------------- */
  10.  
  11. #include <stdio.h>
  12. #include <ctype.h>
  13. #include <stdlib.h>
  14. #include <string.h>
  15.  
  16. #define ADD_NODE 'A'
  17. #define EXIT 'E'
  18. #define HELP '?'
  19. #define REMOVE_NODE 'D'
  20. #define LIST_QUEUE 'L'
  21.  
  22. #define MAX_LEN 10    /* max length of string in entry */
  23.  
  24. typedef struct node {
  25.     struct node *pfwd;    /* ptr to next node in queue */
  26.     char *pstring;        /* ptr to node's string value */
  27. } Node;
  28.  
  29. Node *get_free_node(void);
  30. void put_free_node(Node *pnode);
  31.  
  32. void help(void);        /* action functions */
  33. void add_node(const char *string);
  34. void remove_node(char *string);
  35. void list_queue(void);
  36.  
  37. Node *proot_node = NULL;    /* start of data queue */
  38. Node *ptail_node = NULL;    /* end of data queue */
  39. Node *pfree_node = NULL;    /* next free node */
  40.  
  41. main()
  42. {
  43.     int inchar = 'x';    /* force initial prompt */
  44.     char string[MAX_LEN + 1];
  45.  
  46.     while (1) {
  47.         if (inchar != ' ')
  48.             printf("\nEnter Action Code (%c for help): ", HELP);
  49.         switch(toupper(inchar = getchar())) {
  50.  
  51.     default:
  52.         printf("\n   Invalid command. Please try again\n");
  53.         break;
  54.  
  55.     case HELP:
  56.         help();
  57.         break;
  58.  
  59.     case EXIT:
  60.         exit(EXIT_SUCCESS);
  61.         break;
  62.  
  63.     case '\n':    /* ignore white space on input */
  64.     case ' ' :
  65.     case '\t':
  66.     case '\v':
  67.     case '\f':
  68.         inchar = ' ';    /* indicate white space input */
  69.         break;
  70.  
  71.     case ADD_NODE:
  72.         printf("\n   Enter new node's value: ");
  73.         scanf("%10s", string);
  74.         add_node(string);
  75.         break;
  76.  
  77.     case REMOVE_NODE:
  78.         remove_node(string);
  79.         if (string[0] != '\0') {
  80.             printf("   String stored in removed node = %s\n",
  81.                 string);
  82.         }
  83.         break;
  84.  
  85.     case LIST_QUEUE:
  86.         list_queue();
  87.         break;
  88.         }
  89.     }
  90.  
  91.     return 0;
  92. }
  93.  
  94. void help(void)
  95. {
  96.     printf("\n   The action codes are:\n");
  97.     printf("\t%c - Produces this help message\n", HELP);
  98.     printf("\t%c - Exit this program\n", EXIT);
  99.     printf("\t%c - Add a new node to the tail\n", ADD_NODE);
  100.     printf("\t%c - Remove head node\n", REMOVE_NODE);
  101.     printf("\t%c - List all entries in the queue\n", LIST_QUEUE);
  102. }
  103.  
  104. /* --------------------------------------------------------------
  105.  
  106. FUNCTION ADD_NODE: The steps to add a new node to the end of the
  107. queue are:
  108.  
  109. A.  Get a free node from free node list.  If no more, complain and
  110.     get out.
  111.  
  112. B.  Get space for new node's string.  If no more, complain and get
  113.     out releasing node allocated in A.
  114.  
  115. C.  Initialize new node's string pointer and copy user string to
  116.     allocated space.
  117.  
  118. D.  If this is the first node, make it the head and tail. Otherwise,
  119.     make it the new tail node. Make forward pointer null.
  120.  
  121. -------------------------------------------------------------- */
  122.  
  123. void add_node(const char *string)
  124. {
  125.     Node *pnew_node;    /* ptr to new node */
  126.     char *pstring;        /* ptr to alloced string space */
  127.  
  128. /*A*/    pnew_node = get_free_node();
  129.     if (pnew_node == NULL) {
  130.         printf("\n   No nodes available\n");
  131.         return;
  132.     }
  133.  
  134. /*B*/    pstring = malloc(strlen(string) + 1);
  135.     if (pstring == NULL) {
  136.         printf("\n   No string space available\n");
  137.         put_free_node(pnew_node);
  138.         return;
  139.     }
  140.  
  141. /*C*/    pnew_node->pstring = pstring;
  142.     strcpy(pnew_node->pstring, string);
  143.  
  144. /*D*/    if (proot_node == NULL) {
  145.         proot_node = pnew_node;
  146.     }
  147.     else {
  148.         ptail_node->pfwd = pnew_node;
  149.     }
  150.  
  151.     ptail_node = pnew_node;
  152.     pnew_node->pfwd = NULL;
  153.  
  154.     printf("\n   Node added\n");
  155. }
  156.  
  157. /* --------------------------------------------------------------
  158.  
  159. FUNCTION REMOVE_NODE: The steps to remove the tail node are:
  160.  
  161. A.  Complain if queue empty.
  162.  
  163. B.  If this is the only node in the queue, clear root and tail
  164.     pointers.  Otherwise, adjust root pointer to new first node.
  165.  
  166. C.  Save a copy of the string being released and free the node.
  167.  
  168. -------------------------------------------------------------- */
  169.  
  170. void remove_node(char *string)
  171. {
  172.     Node *ptmp_node = proot_node;
  173.  
  174. /*A*/    if (proot_node == NULL) {
  175.         printf("\n   Queue contains no nodes\n");
  176.         *string = '\0';
  177.         return;
  178.     }
  179.  
  180. /*B*/    if (proot_node == ptail_node) {
  181.         proot_node = ptail_node = NULL;
  182.     }
  183.     else {
  184.         proot_node = proot_node->pfwd;
  185.     }
  186.  
  187. /*C*/    strcpy(string, ptmp_node->pstring);
  188.     free(ptmp_node->pstring);
  189.     put_free_node(ptmp_node);
  190.     printf("\n   Node removed\n");
  191. }
  192.  
  193. /* --------------------------------------------------------------
  194.  
  195. FUNCTION LIST_QUEUE: The steps to display all nodes in the queue are:
  196.  
  197. A.  Complain if queue empty.
  198.  
  199. B.  Traverse queue starting at the head node displaying each node's
  200.     string and the logical node number.
  201.  
  202. -------------------------------------------------------------- */
  203.  
  204. void list_queue(void)
  205. {
  206.     Node *ptmp_node;
  207.     unsigned int node_number;
  208.  
  209. /*A*/    if (proot_node == NULL) {
  210.         printf("\n   Queue contains no nodes\n");
  211.         return;
  212.     }
  213.  
  214.     printf("\n   Queue nodes are as follows:\n");
  215.  
  216. /*B*/    ptmp_node = proot_node;
  217.     node_number = 0;
  218.     while (ptmp_node != NULL) {
  219.         printf("\tNode %u => %s\n", ++node_number, ptmp_node->pstring);
  220.         ptmp_node = ptmp_node->pfwd;
  221.     }
  222. }
  223.  
  224. /* --------------------------------------------------------------
  225.  
  226. FUNCTION GET_FREE_NODE: The steps to get a node from the free node
  227.     list are:
  228.  
  229. A.  If the free node list is empty, get memory for a new node and 
  230.     return its address.
  231.  
  232. B.  Else remove the first node from the free list and use that.
  233.  
  234. -------------------------------------------------------------- */
  235.  
  236. Node *get_free_node(void)
  237. {
  238.     Node *pnew_node;
  239.  
  240. /*A*/    if (pfree_node == NULL) {
  241.         pnew_node = malloc(sizeof(Node));
  242.     }
  243. /*B*/    else {
  244.         pnew_node = pfree_node;    
  245.         pfree_node = pfree_node->pfwd;    
  246.     }
  247.  
  248.     return pnew_node;
  249. }
  250.  
  251. /* --------------------------------------------------------------
  252.  
  253. FUNCTION PUT_FREE_NODE: The steps to release an active node and add
  254.     it to the front of the free list are:
  255.  
  256. A.  Insert the node at the start of the free node list.
  257.  
  258. -------------------------------------------------------------- */
  259.  
  260. void put_free_node(Node *pnode)
  261. {
  262. /*A*/    pnode->pfwd = pfree_node;
  263.     pfree_node = pnode;
  264. }
  265.  
  266. /* ----------------------------------------------------------- */
  267.  
  268.