Exercise 12-11 - CBD page 426 - Lone Leth Thomsen

/* Kelly & Pohl Exercise 12.11, p. 426  */
/*                                     */
/* Lone Leth Thomsen, 11. April 2003   */

#include <stdio.h>
#include <stdlib.h>

struct data {
	char name[10];
	int age;
	int weight;
};

typedef struct data DATA;

struct linked_list {
	DATA			    d;
	struct linked_list  *next;
};

typedef  struct linked_list  ELEMENT;
typedef ELEMENT *            LINK;

LINK cons(DATA d, LINK l){
	LINK new_cell;
	new_cell = (LINK)malloc(sizeof(ELEMENT));
	new_cell -> d = d;
	new_cell -> next = l;
	return new_cell;
};

LINK create_list(DATA arr[],int i){
	if (i == 0) return cons(arr[0],NULL); 
	else cons(arr[i],create_list(arr,i-1));
};

int count_r(LINK l,int age, int weight){
	if (l == NULL)
		return 0;
	else
	  if ((l ->age > age) && (l ->weight> weight)) return(1+ count_r(l->next, age, weight));
	  else return count_r(l->next, age, weight);
};

	struct data { char name[10]; int age; int weight; };
	define the required structure.

 

	typedef struct data DATA; struct linked_list { DATA d; struct linked_list *next; }; typedef struct linked_list ELEMENT; typedef ELEMENT * LINK;
	give the modified list.h definitions as on p. 407

 

	LINK cons(DATA d, LINK l){ LINK new_cell; new_cell = (LINK)malloc(sizeof(ELEMENT)); new_cell -> d = d; new_cell -> next = l; return new_cell; };
	define the helper function cons which given a data element creates a new cell and links it to the head of a list. First the necessary amount of memory space to hold the element is allocated using malloc, then the data element is added. Finally the next pointer is linked to the head of the old list. A pointer to the new list (new_cell) is returned.

 

LINK create_list(DATA arr[],int i){ if (i == 0) return cons(arr[0],NULL); else cons(arr[i],create_list(arr,i-1)); };

define the function create_list, that given an array of data elements and its size creates a linked list with the data elements. The function calls itself recursively, line 33 (the if statement) creates one cell with a NULL pointer (base case). (Now imagine building up the list one element at a time, starting with just one element). create_list starts at the "high" end of the array, runs through it recursively till it hits the first (0'th) element. Then the function creates cells as it "returns", starting with the lowest (building up from the base case).

 

int count_r(LINK l,int age, int weight){ if (l == NULL) return 0; else if ((l ->age > age) && (l ->weight> weight)) return(1+ count_r(l->next, age, weight)); else return count_r(l->next, age, weight); };

define a function count_r that recursively counts the number of elements in a linked list. If the list is empty, 0 is returned (nothing to count), else 1 is added to the result of calling the count_r function recursively on the tail of the list if the data element is over a certain age and weight, else 0 is indirectly added and a recursive call on the tail of the list is made. Line 41 checks that the age member is greater than a given age and also that the weight member is greater than a given weight. If this condition is not true, the count is not increased and the next element in the list is checked.