Data Structure List

Lists

Recall the traditional list code snippets, as given in class:

The list type: 

     
struct AList {
        int             first;
        struct AList *  rest;
     };
     typedef  struct AList *  List;

My style of hiding the fact that List is pointer is based on what you're familiar with from Scheme and Java. Others prefer something like typedef struct AList Cons; In your own code, you may do what you wish.

To create a list: 

     
List make_empty()
     {
        return NULL;
     }

     List make_cons(int first, List rest)
     {
        List  list = (List) malloc(sizeof(struct AList));
        if (list == NULL) {
           fprintf(stderr,"Out of memory.\n");
           exit(1);
        }

        list->first = first;
        list->rest  = rest;
        return list;
     }

To access a list: 

    
 List  list = ...;

     if (list == NULL) {
        ...
     }
     else {
         ...list->first ... list->rest ...
     }

Better yet, you could package such code in accessor functions, as you've seen in COMP 212, and as in the exercises below.


Exercise

  1. List access details should be packaged into predicate and selector functions. Write functions of the following types. Use any appropriate error-checking. The following function names are just suggestions, but should be self-explanatory. 

              #include <stdbool.h>


              bool  is_empty(List);
              bool  is_cons(List);
              int   cons_first(List);
              List  cons_rest(List);

  2. Using these constructors, write code to create one specific list, such as the following: 

              3 7 9 2 8

  3. Write a function (using the constructors, predicates, and selectors) which returns the reversal of an arbitrary List. For simplicity, use the functional accumulator-based strategy described in COMP 210.

  4. Write a function which prints an arbitrary value of type List.

  5. Combine these pieces into a whole program to compute and print the reversal of the example list.

  6. free all malloc-ed data. (This is good practice even at the end of a program, since you might be using a faulty OS which doesn't release all your process' data upon process termination.)

Solutions Here

A Part Of Thiyagaraaj Websites
Comments