home *** CD-ROM | disk | FTP | other *** search
/ POINT Software Programming / PPROG1.ISO / pascal / swag / pointers.swg / 0015_Linked List Queues.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1994-01-27  |  4.0 KB  |  156 lines
  1. {
  2. │ I'm trying to understand the rudiments of linked lists
  3.  
  4. │ 4) What are common uses for linked lists?  Is any one particular form
  5. │    (oneway, circular etc ) preferred or used over any other form?
  6.  
  7. One use is to maintain queues.  New people, requests, or jobs come in at
  8. the end of the line (or break in with priority), but once the head of
  9. the line has been serviced, there is no need to maintain its location in
  10. the queue.  I wrote the following last semester:
  11. ---------------------------------------------------------------
  12. Purpose:
  13.   Maintains a queue of jobs and priorities of those jobs in a linked list.
  14.   The user will be prompted for job number and priority and can list the
  15.   queue, remove a job from the front of the queue (as if it ran), and stop
  16.   the program.  A count of jobs outstanding at the end will be displayed. }
  17.  
  18. type
  19.   PriRange = 0 .. 9;
  20.   JobPnt   = ^JobNode;
  21.   Jobnode  = RECORD
  22.     Numb     : integer;
  23.     Priority : PriRange;
  24.     Link     : JobPnt
  25.   END;
  26.  
  27. procedure addrec(var Start : JobPnt; comprec : Jobnode);
  28. var
  29.   curr,
  30.   next,
  31.   this  : JobPnt;
  32.   found : boolean;
  33. begin
  34.   new(this);
  35.   this^.Numb := comprec.Numb;
  36.   this^.Priority := comprec.Priority;
  37.   if Start = NIL then
  38.   begin
  39.     Start := this;   {Points to node just built}
  40.     Start^.Link := NIL; {Is end of list}
  41.   end
  42.   else    {Chain exists, find a place to insert it}
  43.   if comprec.Priority > Start^.Priority then
  44.   begin
  45.     this^.Link := Start;     {Prep for a new beg of chain}
  46.     Start := this
  47.   end {Condition for insert at beg of chain}
  48.   else
  49.   begin {Begin loop to insert after beg of chain}
  50.     found := false;  {To initialize}
  51.     curr  := start;
  52.     while not found do
  53.     begin
  54.       next := curr^.link;
  55.       if (next = NIL) or (comprec.Priority > next^.Priority) then
  56.         found := true;
  57.         if not found then
  58.           curr:= next  {another iteration needed}
  59.     end;
  60.     {Have found this^ goes after curr^ and before next^}
  61.     this^.Link := next; {Chain to end (even if NIL)}
  62.     curr^.Link := this;  {Insertion complete}
  63.   end;
  64. end;
  65.  
  66. procedure remove(Var Start : JobPnt);
  67. var
  68.   hold : JobPnt;
  69. begin
  70.   if Start = NIL then
  71.     Writeln('Cannot remove from empty queue', chr(7))
  72.   else
  73.   begin
  74.     hold := Start^.Link; {Save 1st node of new chain}
  75.     dispose(Start);     {Delete org from chain}
  76.     Start := hold;       {Reset to new next job}
  77.   end;
  78. end;
  79.  
  80. procedure list(Start : JobPnt); {List all jobs in queue. "var" omitted}
  81. begin
  82.   if Start = NIL then
  83.     Writeln('No jobs in queue')
  84.   else
  85.   begin
  86.     Writeln('Job No     Priority');
  87.     Writeln;
  88.     while Start <> NIL do
  89.     begin
  90.       Writeln('  ',Start^.Numb : 3, '          ', Start^.Priority);
  91.       Start:=Start^.Link
  92.     end;
  93.     Writeln;
  94.     Writeln('End of List');
  95.   end;
  96. end;
  97.  
  98. {Main Procedure starts here}
  99. var
  100.   cntr  : integer;
  101.   build : JobNode;
  102.   work,
  103.   Start : JobPnt;
  104.   Achar : char;
  105.  
  106. begin
  107.   Start := NIL; {Empty at first}
  108.   cntr  := 0;
  109.   REPEAT
  110.     Write('Enter (S)top, (R)emove, (L)ist, or A jobnumb priority to');
  111.     Writeln(' add to queue');
  112.     Read(Achar);
  113.  
  114.     CASE Achar of
  115.       'A', 'a' :
  116.       begin
  117.         Read(build.Numb);
  118.         REPEAT
  119.           Readln(build.Priority);
  120.           if (build.Priority < 0) or (build.priority > 9) then
  121.             Write(chr(7), 'Priority between 0 and 9, try again ');
  122.         UNTIL (build.Priority >= 0) and (build.Priority <= 9);
  123.         addrec(Start, build);
  124.       end;
  125.  
  126.       'R', 'r' :
  127.       begin
  128.         Readln;
  129.         remove(Start);
  130.       end;
  131.  
  132.       'L', 'l' :
  133.       begin
  134.         Readln;
  135.         list(Start);
  136.       end;
  137.  
  138.       'S', 's' : Readln; {Will wait until out of CASE loop}
  139.  
  140.       else
  141.       begin
  142.         Readln;
  143.         Writeln('Invalid option',chr(7))
  144.       end;
  145.     end;
  146.  
  147.   UNTIL (Achar = 's') or (Achar = 'S');
  148.   work := start;
  149.   while work <> NIL do
  150.   begin
  151.     cntr := cntr + 1;
  152.     work := work^.link
  153.   end;
  154.   Writeln('Number of jobs remaining in queue: ', cntr);
  155. end.
  156.