home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c072 / 1.ddi / PRG4_2G.C < prev    next >
Encoding:
C/C++ Source or Header  |  1987-09-21  |  7.8 KB  |  275 lines
  1. /*Program 4_2g -- The Final Solution to the IRS Sort
  2.    by Stephen R. Davis, 1987
  3.  
  4.   This is merely a combination of the various parts of the solution
  5.   already developed.  This program would normally be linked together
  6.   the General Sort procedure -- we have included directly into the
  7.   same source here for clarity.
  8. */
  9.  
  10. #include <stdio.h>
  11. #include <ctype.h>
  12. #include <alloc.h>
  13. #include <process.h>
  14.  
  15. #define NULL (struct IRSdata *)0
  16. #define IRSsignature 0x1234
  17.  
  18. /*prototype declarations --*/
  19.                                        /*structure creation*/
  20. struct IRSdata *create (void);
  21. void getfield (char *, char *, unsigned);
  22. void output (struct IRSdata *);
  23.                                        /*linked list routines*/
  24. int insert (struct IRSdata *, struct IRSdata *, struct IRSdata *);
  25. int remove (struct IRSdata *);
  26. int check (struct IRSdata *, char *);
  27. struct IRSdata *alloc (void);
  28. void init (void);
  29.                                        /*swap routines*/
  30. int swap (struct IRSdata *, struct IRSdata *);
  31. int compare (struct IRSdata *, struct IRSdata *);
  32. struct IRSdata *sequence (struct IRSdata *);
  33. int sort (int (*)(void *, void *), int (*)(void *, void *),
  34.       void *(*)(void *));
  35.  
  36. /*structure declaration for IRS data*/
  37. struct IRSdata{
  38.                struct IRSdata *previous,*next;
  39.                unsigned fingerprint;
  40.                char lastname [11];
  41.                char firstname [11];
  42.                char sex;
  43.                struct {
  44.                        char street [16];
  45.                        char city [11];
  46.                        char state [3];
  47.                       } address;
  48.                char ssnum [10];
  49.                int taxrate;
  50.               };
  51. struct IRSdata *MARKER;
  52. char buffer [256];
  53.  
  54. /*Create - allocate an IRSdata entry and fill in the data from 'stdin'*/
  55. struct IRSdata * create ()
  56. {
  57.     char answer [2];
  58.     struct IRSdata *ptr;
  59.  
  60.     getfield ("Another entry? ", answer, 1);
  61.     if (tolower (answer [0]) == 'n')
  62.          return NULL;
  63.  
  64.     if (ptr = alloc ()) {
  65.          getfield ("Enter last name:    ", ptr -> lastname, 10);
  66.          getfield ("      first name:   ", ptr -> firstname, 10);
  67.          getfield ("      street addr:  ", ptr -> address.street, 15);
  68.          getfield ("      city address: ", ptr -> address.city, 10);
  69.          getfield ("      state (2 ltr):", ptr -> address.state, 2);
  70.          getfield ("      soc sec #:    ", ptr -> ssnum, 9);
  71.          printf   ("      tax bracket:  ");
  72.  
  73.          gets (buffer);
  74.          sscanf (buffer, "%d", &(ptr -> taxrate));
  75.     } else {
  76.          printf ("Sorry.  No more room for data.\n");
  77.     }
  78.  
  79.     return (ptr);
  80. }
  81.  
  82. /*GetField - pose a question, then get an answer.  Save up to
  83.              'size' characters*/
  84. void getfield (question, answer, size)
  85.     char *question,*answer;
  86.     unsigned size;
  87. {
  88.     unsigned i;
  89.  
  90.     printf (question);
  91.     while (!gets (buffer));
  92.     for (i = 0; size; size--)
  93.          *answer++ = buffer [i++];
  94.     *answer = '\0';
  95. }
  96.  
  97. /*Output - output a subset of IRSdata structure to 'stdout'*/
  98. void output (ptr)
  99.     struct IRSdata *ptr;
  100. {
  101.     if (ptr)
  102.          printf ("%s %s, %s, taxrate = %u\n", ptr -> firstname,
  103.                     ptr -> lastname, ptr -> ssnum, ptr -> taxrate);
  104. }
  105.  
  106. /*Insert - insert a structure in between two doubly linked entries.
  107.            Return a 0 if successful, and a nonzero if not*/
  108. int insert (before, after, current)
  109.     struct IRSdata *before, *after, *current;
  110. {
  111.     if (before -> next != after) return -1;
  112.     if (before != after -> previous) return -1;
  113.  
  114.     if (check (before,  "arg 'before' to insert()")) return -1;
  115.     if (check (after,   "arg 'after' to insert()")) return -1;
  116.     if (check (current, "arg 'current' to insert()")) return -1;
  117.  
  118.     before -> next = current;
  119.     current -> previous = before;
  120.  
  121.     after -> previous = current;
  122.     current -> next = after;
  123.     return 0;
  124. }
  125.  
  126. /*Remove - remove an entry from a doubly linked list*/
  127. int remove (entry)
  128.     struct IRSdata *entry;
  129. {
  130.     struct IRSdata *before, *after;
  131.  
  132.     if (check (entry, "arg 'entry' to remove()")) return -1;
  133.  
  134.     before = entry -> previous;
  135.     after = entry -> next;
  136.  
  137.     before -> next = after;
  138.     after -> previous = before;
  139.  
  140.     entry -> previous = entry -> next = NULL;
  141.     return 0;
  142. }
  143.  
  144. /*Init - initialize the linked list to empty*/
  145. void init (void)
  146. {
  147.     struct IRSdata *alloc ();
  148.  
  149.     MARKER = alloc ();
  150.     MARKER -> previous = MARKER -> next = MARKER;
  151. }
  152.  
  153. /*Check - check the integrity of an IRS pointer.  If OK, return a
  154.           0, else print message and return a -1.*/
  155. int check (ptr, msg)
  156.     struct IRSdata *ptr;
  157.     char *msg;
  158. {
  159.     if (ptr -> fingerprint == IRSsignature)
  160.          return 0;
  161.     printf ("Error:\n  Pointer failure on %s\n", msg);
  162.     return -1;
  163. }
  164.  
  165. /*Alloc - allocate a structure and "sign it" with the IRS
  166.           signature*/
  167. struct IRSdata *alloc(void)
  168. {
  169.     struct IRSdata *ptr;
  170.  
  171.     if (ptr = (struct IRSdata *)malloc (sizeof (struct IRSdata)))
  172.          ptr -> fingerprint = IRSsignature;
  173.     return ptr;
  174. }
  175.  
  176. /*Sort - impliment bubble sort*/
  177. int sort (compare, swap, sequence)
  178.      int (*compare)(void *, void *), (*swap)(void *, void *);
  179.      void *(*sequence)(void *);
  180. {
  181.     int flag;
  182.     void *p1, *p2;
  183.  
  184.     do {
  185.          flag =  0;
  186.          p2 = (*sequence)(0);          /*starting w/ first entry...*/
  187.          while (p1 = p2, p2 = (*sequence) (p2)) /*...sequence thru*/
  188.          {
  189.               if ((*compare)(p1, p2) > 0) {     /*if p1 > p2...*/
  190.                    if ((*swap)(p1, p2)) return -1;/*...swap p1 & p2*/
  191.                    flag = 1;
  192.               }
  193.          }
  194.        } while (flag);                 /*stop when all are in order*/
  195.     return 0;
  196. }
  197.  
  198. /*Swap - swap the position of the two entries passed.  Return
  199.          a 0 if successful and a -1 if not.*/
  200. int swap (first, second)
  201.     struct IRSdata *first, *second;
  202. {
  203.  
  204.     if (remove (second))
  205.          return -1;
  206.     return (insert (first -> previous, first, second));
  207. }
  208.  
  209. /*Compare - compare two IRS data structures.  Return as follows:
  210.             1 -> a.taxrate > b.taxrate
  211.             0 -> a.taxrate = b.taxrate
  212.            -1 -> a.taxrate < b.taxrate*/
  213. int compare (a, b)
  214.     struct IRSdata *a, *b;
  215. {
  216.     if (a -> taxrate > b -> taxrate)
  217.          return  1;
  218.     if (a -> taxrate < b -> taxrate)
  219.          return -1;
  220.     return 0;
  221. }
  222.  
  223. /*Sequence - given an entry, return the address of the next
  224.              entry.  Return a 0 on end of list.*/
  225. struct IRSdata *sequence (entry)
  226.     struct IRSdata *entry;
  227. {
  228.     struct IRSdata *value;
  229.  
  230.     if (entry == 0)                    /*given 0...*/
  231.          entry = MARKER;               /*...start with beginning*/
  232.  
  233.     if (check (entry, "arg 'entry' to sequence()"))
  234.          return NULL;
  235.  
  236.     if ((value = entry -> next) == MARKER) /*if end of chain...*/
  237.          return NULL;                  /*...return a NULL*/
  238.     else
  239.          return value;
  240. }
  241.  
  242. /*Main - now invoke the above routines*/
  243. main ()
  244. {
  245.     struct IRSdata *ptr, *ptrold;
  246.  
  247.     /*initialize linked list to empty*/
  248.     init ();
  249.  
  250.     /*now read in entries and add them to the chain*/
  251.     ptrold = MARKER;
  252.     while (ptr = create ()) {
  253.          if (insert (ptrold, MARKER, ptr))
  254.               abort ();
  255.          ptrold = ptr;
  256.     }
  257.  
  258.     /*display the entries in input order*/
  259.     printf ("\n\n\nHere are the entries as entered:\n\n");
  260.     ptr = MARKER;
  261.     while (ptr = sequence (ptr))
  262.          output (ptr);
  263.  
  264.     /*now sort the list*/
  265.     if (sort (compare, swap, sequence))
  266.          printf ("failure during sort!\n");
  267.  
  268.     /*and reoutput the list*/
  269.     printf ("\n\n\nHere are the entries sorted by taxrate:\n\n");
  270.     ptr = MARKER;
  271.     while (ptr = sequence (ptr))
  272.          output (ptr);
  273.  
  274.     printf ("\nCompleted successfully\n");
  275. }