Data Structure List Solutions

#include <stdio.h>

#include <malloc.h>
#include "/home/comp320/public_html/2005/assignments/support/320bool.h"

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

/*******************
* List Constructors
*******************/
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;
}

/*******************
* List Predicates
*******************/
bool
is_empty(List list)
{
return (list == NULL);
}

bool
is_cons(List list)
{
return (list != NULL);
}

The gadget spec URL could not be found
/*******************

* List Selectors
*******************/
int
cons_first(List list)
{
if (is_cons(list))
return list->first;
else {
/* Must be an empty list. */
fprintf(stderr,"Can't take the first of an empty list.\n");
exit(1);
}
}

List
cons_rest(List list)
{
if (is_cons(list))
return list->rest;
else {
/* Must be an empty list. */
fprintf(stderr,"Can't take the rest of an empty list.\n");
exit(1);
}
}


/*******************
* List Destructor
*******************/

/* Free an entire list.
* Assume there are no other pointers to anywhere in the list.
*/
void
free_list(list)
{
if (list != NULL) {
free_list(cons_rest(list));
free(list);
}
}


/*******************
* List Functions
*******************/

/* Returns a new list that is the reverse of the input list, appended
* at the front of the previously accumulated list.
*/
List
reverse_help(List list,
List accum)
{
if (is_empty(list)) {
return accum;
}
else {
return reverse_help(cons_rest(list),make_cons(cons_first(list),accum));
}
}

/* Returns a new list that is the reverse of the input list.
*/
List
reverse(List list)
{
return reverse_help(list,make_empty());
}

/* Prints the elements of input list to standard output.
* The elements are separated by spaces, and terminated by
* a space and newline.
*/
void
print_list(List list)
{
List temp_list;

for (temp_list = list;
!is_empty(temp_list);
temp_list = cons_rest(temp_list)) {
printf("%d ",cons_first(temp_list));
}
putchar('\n');
}


/*******************
* Main function to print the reversed sample list.
*******************/
int
main(void)
{
List list = make_cons(3,make_cons(7,make_cons(9,make_cons(2,make_cons(8,make_empty())))));
List revlist = reverse(list);

printf("The reverse of ");
print_list(list);
printf("\nis ");
print_list(revlist);
putchar('\n');

free_list(list);
free_list(revlist);

return 0; /* no error */
}


A Part Of Thiyagaraaj Websites
Comments