CSc 17  Test 2   20 November 2000
  >>>>>>>>>>>>>>>>>>>>>>>SUGGESTED ANSWERS<<<<<<<<<<<<<<<<<<<<<<<<<<<<,
  1.  (20 pts)  Assume the class LinkList below.  Write a member function
  of LinkList called same() which returns true if and only if two linked
  lists have the same data in the same order.  Given the declaration
  LinkList a,b;, the call to same() would be a.same(b); (or b.same(a);).
  (You need not provide the prototype for same())
   class LinkList{
     private:
       class Link{
        public:
          Link();
          Link(int x);
          int key;
          Link *next;
       };
       Link *root;
     public:
      ...
      ...
   };

  bool LinkList::same(LinkList &list){
      Link *one,*two;
      one=root;
      two=list.root;
      while(one!=NULL && two!=NULL && one->key==two->key){
        one=one->next;
        two=two->next;
      }
      return one==NULL && two==NULL;
  }

  2.  (25 pts)  For the class X below overload the operators "+" and "<<".
  When we have the declaration X a,b;  a+b should return an instance of
  X whose data member x contains the sum of the x's of a and b, and
  if a.x=4, cout<<a; should display a in the form "X(4)".  Provide both
  the prototypes and the definitions of the two operators.
    class X{
      public:
       int x;
    };

   Add the following two lines to the above class (public):
        X operator+(const X &a)const;
        friend ostream &operator<<(ostream &out,const X &a);

   ostream &operator<<(ostream &out,const X&a){
      out<<"X("<<a.x<<")";
      return out;
   }

   X X::operator+(const X &a)const{
       X temp;
       temp.x=x+a.x;
       return temp;
   }

  3.  (10 pts)  Assume that the class Stack stores ints and has the usual
  stack properties. I wrote the following member function for Stack but
  forgot, as usual, to document it.  Provide the documentation.

   //PreCondition:  The Stack is well defined.
   //PostConditions:  If the stack had 0 or 1 entries, the Stack is
   //                 unchanged.  If it had two or more entries, the
   //                 top entry is now at the bottom.  The order of
   //                 the remaining entries is unchanged.
     void Stack::huh(){
       Stack tempSt(capacity());
       int temp;
       if(!empty()){
         temp=pop();
         while(!empty())
           tempSt.push(pop());
         push(temp);
         while(!tempSt.empty())
           push(tempSt.pop());
       }
     }

  4.  (25 pts)  Write a function longest() which finds the length of the
  longest line in a file of text.  Given the declaration ifstream fin; the
  call to the function would be longest(fin);.

   void getch(istream &fin){
     if(!fin.eof())
       fin.get(ch);
     if(fin.eof())
       ch='\n';
   }

   int longest(istream & fin){
        int count,max;
        char ch;
        max=0;
        getch(fin,ch);
        while(!fin.eof()){
          count=0;
          while(ch!='\n'){
             getch(fin,ch);
             count++;
          }
          if(count>max)
            max=count;
          getch(fin,ch);
        }
        return max;
   }

  5.  (20 pts)  Assume the class Tree below.  Write a member function
  product() which returns the product of the entries in the tree.  Given
  the declaration Tree a; the call to product would be a.product();.  The
  function product() may call other functions which you write.
     class Tree{
     private:
       class Node{
        public:
          Node();
          Node(int x);
          int key;
          Node *child[2];
       };
       Node *root;
     public:
      ...
      ...
   };
  int Tree::product(){
      return product(root);
  }

  int Tree::product(Node *rt){
      if(rt==NULL)
         return 1;
      else return rt->key*product(rt->child[0])*product(rt->child[1]);
  }