From: mabht@levels.unisa.edu.au
Newsgroups: unisa.cis.dslss
Subject: Chapter 7 answers
Date: 5 Nov 92 17:24:35 +1030
Organization: University of South Australia

chapter 7 answers


8.    (a)   C^.Next^.Info
      (b)   B^.Back^.Info
      (c)   A^.Next^.Next
      (d)   C^.Back^.Next
      (e)   B^.Back^.Back^
      (f)   C^.Back^.Back
      (g)   A^.Back

9.    (a)   a pointer
      (b)   a record
      (c)   a character string
      (d)   an integer
      (e)   a pointer
      (f)   a character

21.   (a)  Procedure to add two positive numbers:
      PROCEDURE Add
        (Num1, Num2 : BigInteger;
         VAR Num3   : BigInteger);
      (* Adds the big integers in linked lists pointed to by  *)
      (* Num1 and Num2. Assumes neither Num1 or Num2 are NIL. *)

      VAR
        Carry     : Integer;
        Sum       : Integer;
        NewDigit  : PointerType;
        LastDigit : PointerType;

      BEGIN  (* Add *)

        Carry := 0;
        Num3  := NIL;

        (* Create nodes of sum list. *)
        WHILE (Num1 <> NIL) AND (Num2 <> NIL) DO
          BEGIN
            New (NewDigit);
            Sum := Num1^.Digit + Num2^.Digit + Carry;
            NewDigit^.Digit := Sum MOD 10;
            Carry := Sum DIV 10;

            (* Link new digit node to Num3. *)
            IF Num3 = NIL
              THEN Num3 := NewDigit
              ELSE LastDigit^.Next := NewDigit
            LastDigit := NewDigit;
            Num1 := Num1^.Next;
            Num2 := Num2^.Next
          END; (* WHILE *)

        (* One, or both of the numbers has no more digits. *)
        (* Make Num1 point to the remaining digits, if any. *)
        IF Num1 = NIL
          THEN Num1 := Num2;

        (* Copy the remaining digits to Num3 list. *)
        WHILE Num1 <> NIL DO
          BEGIN
            New3 (NewDigit);
            Sum := Num1^.Digit + Carry;
            NewDigit^.Digit := Sum MOD 10;
            Carry := Sum DIV 10;
            LastDigit^.Next := NewDigit;
            LastDigit := NewDigit;
            Num1 := Num1^.Next

          END; (* WHILE *)

        IF Carry > 0
          THEN
            BEGIN
              New (NewDigit);
              NewDigit^.Digit := Carry;
              LastDigit^.Next := NewDigit;
              LastDigit := NewDigit
            End; (* IF *)

        (* Mark the end of the list. *)
        LastDigit^.Next := NIL
      END;  (* Add *)

      (b) Procedure to subtract one positive number from another
          (assumes second number is smaller than the first):

      PROCEDURE Subtract
        (Num1, Num2 : BigInteger;
         VAR Num3   : BigInteger);

      VAR
        Borrow    : Integer;
        Diff      : Integer;
        NewDigit  : PointerType;
        LastDigit : PointerType;

      BEGIN  (* Subtract *)

        Num3   := NIL;
        Borrow := 0;

        WHILE (Num1 <> NIL) AND (Num2 <> NIL) DO
          BEGIN

            New (NewDigit);
            Diff := (Num1^.Digit - Borrow) - Num2^.Digit;

            IF Diff < 0
              THEN
                BEGIN
                  Diff := Diff + 10;
                  Borrow := 1
                End (* IF *)
              ELSE Borrow := 0;

            NewDigit^.Digit := Diff;

            (* Link new digit node to num3. *)
            IF Num3 = NIL
              THEN Num3 := NewDigit
              ELSE LastDigit^.Next := NewDigit

            LastDigit := NewDigit;
            Num1 := Num1^.Next;
            Num2 := Num2^.Next

          END; (* WHILE *)

        (* Any additional digits are in Num1.       *)
        (* Copy the remaining digits to Num3 list.  *)
        WHILE Num1 <> NIL DO
          BEGIN

            Diff := (Num1^.Digit - Borrow);

            IF Diff < 0
              THEN
                BEGIN
                  Diff := Diff + 10;
                  Borrow := 1
                END (* IF *)
              ELSE Borrow := 0;

            New (NewDigit);
            NewDigit^.Digit := Diff;
            LastDigit^.Next := NewDigit;
            LastDigit := NewDigit;
            Num1 := Num1^.Next

          END; (* WHILE *)

       (* Mark the end of the list. *)
       LastDigit^.Next := NIL

     END; (* Subtract *)

     (c)   See PrintReverse procedure in Exercise #6

22   (a)           ------------------------------------
                   |/|    ---Top of File---         |o|
                   ----------------------------------|-
                    ^                                v
                   -|----------------------------------
                   |o|This is the first line of text|o|
                   ----------------------------------|-
                    ^                                v
           ---     -|----------------------------------
    LinePtr|o| ->  |o|This is the last line of text |o|
           ---     ----------------------------------|-
                    ^                                v
                   -|----------------------------------
                   |o| This is the second line      |o|
                   ----------------------------------|-
                    ^                                v
                   -|----------------------------------
                   |o| ---Bottom of File---         |/|
                   ------------------------------------

     (b)    The declarations:
     CONST
       MaxLine = 80;

       (* Each of the following strings have 80 characters. *)
       TopLine =
         '---Top of File---                                      ';
       BottomLine =
         '---Bottom of File---                                   ';

     TYPE
       LineType     = PACKED ARRAY[ 1..MaxLine] OF Char;

       LinePtrType  = ^LineNodeType;

       LineNodeType = RECORD
         LineText : LineType;
         Next     : LinePtrType;
         Back     : LinePtrType;
       END; (* LineNodeType *)

       ListType = LinePtrType;

     VAR
       Lines : ListType;
         (* external pointer to line data structure *)

     (c)
     PROCEDURE CreateList
       (VAR List : ListType);

     BEGIN (* CreateList *)

       (* Set up the header. *)
       New (List);
       List^.LineText := TopLine;
       List^.Back     := NIL;

       (* Set up the trailer node. *)
       New (List^.Next);  (* hooks trailer to header *)
       List^.Next^.LineText := BottomLine;
       List^.Next^.Next     := NIL;
       List^.Next^.Back     := List

     END;  (* CreateList *)

     (d)
     PROCEDURE GoToTop
       (VAR LinePtr : LinePtrType);

       (* LinePtr is set to access "first" line. *)

     BEGIN  (* GoToTop *)
       WHILE LinePtr^.LineText <> TopLine DO
         LinePtr := LinePtr^.Back

     END; (* GoToTop *)

     PROCEDURE GoToBottom
       (VAR LinePtr : LinePtrType);

       (* LinePtr is set to access "last" line *)
       (* (the line before the trailer line).  *)

     BEGIN  (* GoToBottom *)

       WHILE LinePtr^.Next^.LineText <> BottomLine DO
         LinePtr := LinePtr^.Next

     END;  (* GoToBottom *)

     (e)    These GoToTop and GoToBottom operations are O(N).
            If we kept external pointers to both the top and
            bottom nodes, in addition to the single "current"
            pointer, these could be implemented as O(1) operations.

     (f)
     PROCEDURE InsertLine
       (LinePtr : LinePtrType;
        NewLine : LineType);

       (* Insert NewLine after the "current" line. *)
     VAR
       NewNode : LinePtrType;

     BEGIN (* InsertLine *)

       (* Create node and insert after current line. *)
       New (NewNode);
       NewNode^.LineText := NewLine;
       NewNode^.Next := LinePtr^.Next;
       NewNode^.Back := LinePtr;
       NewNode^.Next^.Back := NewNode;
       NewNode^.Back^.Next := NewNode;

     END;  (* InsertLine *)

     (g)   It is not necessary to make LinePtr a VAR parameter because
           LinePtr is not Changed by this procedure.  If we wanted to
           add the postcondition that the new line becomes the current
           line, we would need to make LinePtr a VAR parameter.

     (h)
     PROCEDURE PrintText
       (LinePtr : LinePtrType);
       (* Print all the lines from "first" to "last." *)

     BEGIN (* PrintText *)

       GoToTop (LinePtr)

       (* Adjust LinePtr to avoid printing header line. *)
       LinePtr := LinePtr^.Next;

       WHILE LinePtr^.LineText <> BottomLine DO
         BEGIN
           Writeln (LinePtr^.LineText);
           LinePtr := LinePtr^.Next
         END;  (* WHILE *)
     END;  (* PrintText *)

     (i)    After the call, PrintText (TextLine), TextLine accesses
            whatever node it accessed before the call; the formal
            parameter LinePtr is a value parameter and is not changed
            by executing the PrintText procedure.






#! rnews 2170