A dangling pointer is a pointer to memory that you do not own, either because you have not allocated it or because the memory has been deallocated, either explicitly by you or implicitly by the run-time system.

The consequences can be devastating to the program. You can destroy data structures irreparably, you can change the values of variables by accident, and you can even put a dagger in the heart of the memory allocator, making it impossible to allocate any more memory.

Dangling pointer errors can be very difficult to track down, because they often show up far from the position where they occur. A great deal of care should be taken to avoid using dangling pointers. You do not want to deallocate memory before you are ready to.

The physical level of detail is concerned with memory management and low level organization of data structures. If you ignore that, you can get a program that looks reasonable from a conceptual point of view, but that does not work because it does not allocate or deallocate memory correctly.

1. int x;

   You don't deallocate x. It is deallocated automatically, since it is in the run-time stack.

2. int* x = new int;

   Say delete x;

3. int x[10];

   You don't deallocate x. It is deallocated automatically, since it is in the run-time stack.

4. int* x = new int[10];

   Say delete[] x;

A memory leak occurs when a program does not deallocate memory that it is done with. A small memory leak is often not a problem. A large memory leak will cause a program to stop running because it has run out of memory, even though the total memory actually in use by the program might be small.

The interface tells anyone who wants to use a function what he or she needs to know. It consists of the contract and the function prototype.

The implementation of a function is the function body. It tells how the function works, and is what the computer performs when the function is called.

The interface of an abstract data type consists of a type and a collection of functions on that type. Each function is given by a function interface.

The implementation of an abstract data type consists of a representation for the type and implementations of the functions.

Typically, the consequence of violating an abstraction is that a program becomes more difficult to modify. Programs that use few abstractions, or that violate the abstractions that they do use, can be so difficult to modify that nobody is willing to try to change them.

To compare A and B, use strcmp(A,B). The result is 0 if A and B are equal, and nonzero if they are not equal. (In fact, the result is related to zero in the same way in which A and B are related. So if r = strcmp(A,B), then

• r == 0 if A == B,
• r < 0 if A < B,
• r > 0 if A > B.

strcpy(B,A);

Note that strcpy use the same order as assignment statements. It copies the right-hand thing into the left-hand thing.

The smallest value is as far to the left as possible. The largest value is as far to the right as possible. A value that is near the middle (median) of all of the values is found in the root. You can also find a value that is close to the middle as the value that immediately follows the root (the smallest value in the right subtree) or that immediately precedes the root (the largest value in the left subtree).

An object contains variables and functions. You can also say that an object contains data and functions, or data and methods, or variables and methods.

All objects of the same class as an object can use the private variables that are in an object.

(Technically, the limitation is on where the code occurs. All code that is part of class A can use the private things in ANY object of class A.)

The protected parts of class A can be used in class A and in all subclasses of class A. A subclass of A is a class that is derived from A, either directly or indirectly.

A wrapper class is used to encapsulate a non-object-oriented implementation of a data type into an object-oriented module. It can make a classical data structure easier to use.

x = s.pop();

C++ templates provide a form of polymorphism, making programs more general. They are typically used in general purpose libraries.

A destructor is used to clean up the resources that are used by an object when the object is destroyed. Typically, it deallocates memory that the object is using, but that is not physically part of the object. (The object refers to that memory using pointers, or indirectly using pointers to pointers, etc.)

A copy constructor makes a copy of an object. It is called when an assignment is done, or when a parameter is passed by value, where the type of the thing being copied is the class to which the copy constructor belongs. The prototype for the copy constructor of class Widget is

    Widget(const Widget&);
 

1. Look up a value in a balanced binary search tree that has n values in it.

   log₂(n)

2. Insert a value into a binary search tree that has n values in it.

   log₂(n)

3. Compute the length of a linked list where the length is n.

   n

4. Add a value to the front of a linked list of length n.

   Constant, independent of n.

5. Sort a linked list using Lsort, where the list has n members.

   n log₂(n)

6. Push a value onto a stack of size n.

   Constant, independent of n.

Here is one solution.

    char* reverse(char *s)
    {
      int k;
      int slen = strlen(s);
      char* result = new char[slen + 1];

      for(k = 0; k < slen; k++) {
        result[slen - k - 1] = s[k];
      }
      result[slen] = '\0';
      return result;
    }
 

                          49
                         /  \
                        /    \
                      26      75
                     /  \       \
                    /    \       \                     
                  16      42      85
                 /  \
                /    \
              12      19 
  

After inserting 20 without doing rebalancing, you get

                          49
                         /  \
                        /    \
                      26      75
                     /  \       \
                    /    \       \                     
                  16      42      85
                 /  \
                /    \
              12      19 
                       \
                        \
                        20
  

                          49
                         /  \
                        /    \
                      19      75
                     /  \       \
                    /    \       \                     
                  16      26      85
                 /       / \
                /       /   \
              12       20    42
  

Presume that T contains no negative numbers. (This requirement is part of the contract.)

      struct TreeNode {
        int data;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x, TreeNode* L, TreeNode *R)
        {
          data = x;
          left = L;
          right = R;
        }
      };   
      typedef TreeNode* Tree;


  

Here is one solution.

      int largestEven(Tree T)
      {
        if(T == NULL) return -1;
        else {
          int x = largestEven(T->right);
          if(x >= 0) return x;
          else if(T->data % 2 == 0) return T->data;
          else return largestEven(T->left);
        }
      }
  

    Tree flip(Tree T)
    {
      if(T == NULL) return NULL;
      else return new TreeNode(T->data, flip(T->right), flip(T->left));
    }
 

This one is a little tricky. You have not been told that there is a copy constructor available, so you cannot assume there is one. That means making a copy using the assignment operator is not an option.

We need to get the front of the queue and remember it. Then we need to put it back into the queue, and repeatedly move things from the front of the queue to the back until the original front comes back to the front. But, since we don't know how many things are in the queue, we cannot just keep putting things at the back of the same queue, or we won't know when we are done.

One approach is to put things into another queue, and then back into the original queue.

  int peek(Queue q)
  {
    Queue other;
    int result = q.remove();

    // Make queue other be a copy of q.

    other.insert(result);
    while(!q.isEmpty()) other.insert(q.remove());

    // Now copy from other back into q.

    while(!other.isEmpty()) q.insert(other.remove());

    return result;
  }