Lab 2: list_t

Objectives

To construct a (singly-linked) list library and then test by:
  1. initializing the list header
  2. reading a file of string and int pairs (stored in the provided data_t type)
  3. iterating through the list, printing each data_t type
  4. resetting the list so that the current pointer (iterator) points to the first list element
  5. iterating again through the list, printing each data_t type
  6. deleting the entire list ensuring that memory was freed

Assignment

  1. Use the singly-linked list interface (list.h) given below to write the list implementation (list.c).
    #include <assert.h>
    
    typedef struct link_type
    {
      struct link_type *next;       // next link in the list
      void             *data;       // data pointed to by link
    } link_t;
    
    // prototypes for link management functions
    link_t* link_init(void* data);
    
    typedef struct list_type
    { 
      link_t  *first;               // first link in the list
      link_t  *last;                // last link in the list
      link_t  *current;
    }  list_t;
    
    // prototypes for list management functions
    
    list_t* list_init(void);                // malloc new list header and init
    void    list_add(list_t*,void *);       // add an element to end of a list
    void    list_del_front_link(list_t*);   // delete front link
    void    list_del(list_t*);              // delete all list structures and items
    void    list_reset(list_t*);
    int     list_not_end(list_t*);
    int     list_next_link(list_t*);
    void    *list_get_data(list_t*);
    	
  2. You code should be such that the following main.c file works unaltered:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #include "list.h"
    
    #define NAME_LEN 16
    
    // a meaningless structure to put on the list
    
    typedef struct data_type
    {
      char e_name[NAME_LEN];    // data name
      int  e_id;                // data id code
    }  data_t;
    
    int main(int argc, char *argv[])
    {
            list_t  *elist;
            link_t  *elink;
            data_t  *eloc;
            char    name[NAME_LEN];
            int     num;
    
      // create new list
      elist = list_init();
    
      // read input file consisting of names and id codes adding entities to list
      while(scanf("%s %d", name, &num) == 2) {
        eloc = (data_t *)malloc(sizeof(data_t));
        strcpy(eloc->e_name, name);
        eloc->e_id = num;
        list_add(elist,(void *)eloc);
      }
    
      // now play it back
      list_reset(elist);
    
      printf("*** printing list\n");
    
      while(list_not_end(elist)) {
        eloc = (data_t *)list_get_data(elist);
        printf("%s %d \n",eloc->e_name,eloc->e_id);
        list_next_link(elist);
      }
    
      // try it again...
    
      printf("*** printing list again\n");
      list_reset(elist);
    
      while (list_not_end(elist)) {
        eloc = (data_t *)list_get_data(elist);
        printf("%s %d \n", eloc->e_name, eloc->e_id);
        list_next_link(elist);
      }
    
      // now free all list control structures and the data_t structures as well
    
      printf("*** deleting list\n");
      list_del(elist);
    
      // see if we trashed malloc's control structures
    
      printf("*** initializaing new list\n");
      elist = list_init();
    
      // nope ... see if we can delete an empty list
    
      printf("*** deleting list again\n");
      list_del(elist);
    
      // prove we survived
    
      printf("*** done\n");
    }
    	
  3. Sample input (a file):
    Mike    1234
    Bill    3212
    Sarah   1321
    John    1021
    Carol   3223
    Debbie  4231
    Gary    9321
    Ann     1231
    Dale    7231
    Lynn    8133
    Patty   9999
    	
  4. Running the program:
    	./main < listdata.txt
    	
  5. Sample output:
    *** printing list
    Mike 1234 
    Bill 3212 
    Sarah 1321 
    John 1021 
    Carol 3223 
    Debbie 4231 
    Gary 9321 
    Ann 1231 
    Dale 7231 
    Lynn 8133 
    Patty 9999 
    *** printing list again
    Mike 1234 
    Bill 3212 
    Sarah 1321 
    John 1021 
    Carol 3223 
    Debbie 4231 
    Gary 9321 
    Ann 1231 
    Dale 7231 
    Lynn 8133 
    Patty 9999 
    *** deleting list
    *** initializaing new list
    *** deleting list again
    *** done
    	

Turn in

Turn in all of your code, in one tar.gz archive of your lab02/ directory, including:
  1. A README file containing
    1. Course id--section no
    2. Name
    3. Lab description
    4. Brief solution description (e.g., program design, description of algorithm, etc., however appropriate).
    5. Lessons learned, identified interesting features of your program
    6. Any special usage instructions
  2. Makefile
  3. source code (.h headers and .c source)
  4. object code (do a make clean before tar)

How to hand in

See submit notes.