0

Suppose there are n ducks floating on the pond in a circle. The pond is also home for an alligator with a fondness for ducks. Beginning at the 1st position, the alligator counts around the circle and eats every mth duck (the circle closing as ducks are eaten). For example, the eaten order when n=8, m = 4 is

5 1 6 3 2 4 8 7


The fifth duck is the first on the menu, the first duck is second, etc. Write a program which prints out the order of disappearance of the ducks given n (number of ducks) and m (inteval to the next duck to be eaten) to the screen. At least one blank must separate each number. The values of m and n are to be entered from the keyboard via standard input. You should use malloc to create the space for the m ducks.

clist.c

#include "clist.h"
#include "globals.h"
#include <stdio.h>
#include "clist.h"
#include <stdlib.h>







status allocate_node(clist *p_L , generic_ptr data)  {


  clist L = (clist) malloc(sizeof(node));

  if (L == NULL) return ERROR;

  *p_L = L;
  
  DATA(L) = data;
  NEXT(L) = NULL;
  return OK;

}


void free_node(clist *p_L) {

  free(*p_L);
  *p_L = NULL;

}

















status init_circ_list(clist *p_L){

  *p_L = NULL ; 

  return OK ; 
}

bool empty_circ_list(clist L){

  return (L == NULL ) ? TRUE : FALSE ; 

}

status circ_insert(clist *p_L , generic_ptr  data   ){

  clist L ; 

  if(allocate_node(&L,data) == ERROR) 
    return ERROR ; 

  if(empty_circ_list(*p_L) == TRUE){

    NEXT(L) = L ; 
    *p_L = L ; 
  }else{
    NEXT(L) = NEXT(*p_L) ; 
    NEXT(*p_L) = L ; 
  } 


  return OK ; 

}
 

status circ_append(clist *p_L , generic_ptr data){ 

  if(circ_insert(p_L,data) == ERROR)
    return ERROR ; 

    *p_L = NEXT(*p_L) ; 




  return OK ; 
}



    
status circ_delete(clist *p_L , generic_ptr *p_data){

  if(empty_circ_list(*p_L))
    return ERROR ; 

  *p_data = (generic_ptr)DATA(NEXT(*p_L)) ;

  return circ_delete_node(p_L , *p_L) ; 
}

status circ_delete_node(clist *p_L , clist node ){

  clist L ; 

  if(empty_circ_list(*p_L) == TRUE  )
    return ERROR ; 

  if(node == NEXT(node))


    *p_L = NULL ; 

  else{ 
    for(L = NEXT(*p_L) ; L != *p_L && NEXT(L) != node  ; L = NEXT(L) ) ; 
    if (NEXT(L) != node) 
      return ERROR ; 
    NEXT(L) = NEXT(node) ; 

    if( node == *p_L ) 

      *p_L = L ; 
  }

  free_node(&node) ; 

  return OK ; 

}
 

clist circ_list_iterator( clist L, clist lastreturn ){
  if( lastreturn == NULL ) return (L) ? NEXT(L) : NULL;
  else 
    return (lastreturn == L) ? NULL : NEXT(lastreturn);
}

int circ_length( clist L ){
  clist lastreturn;
  int length;
  
  length = 0;
  lastreturn = NULL;
  while((lastreturn = circ_list_iterator(L, lastreturn)) != NULL)
    length++;
  return length;
}

clist nth_node( clist L, int number ){
  clist tmp;
  if( empty_circ_list(L) == TRUE ) return NULL;
  if( number == -1 ) return L;
  tmp = L;
  do{
    tmp = NEXT(tmp);
    number--;
  } while( number > 0 && tmp != L );
 
  return( number != 0 ) ? NULL : tmp;
}

status circ_traverse( clist L, status (*p_func_f)() ){
  clist tmp;
  if( empty_circ_list(L) == TRUE ) return OK;
  tmp = L;
  do{
    tmp = NEXT(tmp);
    if( (*p_func_f)(DATA(tmp)) == ERROR) return ERROR;
  } while( tmp != L );
  
  return OK;
}

clist.h

#ifndef _circular
#define _circular




#include "globals.h"


typedef struct node node , *clist ; 

struct node{

	generic_ptr datapointer ; 
	clist next ; 
};

extern status init_circ_list(clist *p_L);
extern bool empty_circ_list(clist L);
extern status circ_insert(clist *p_L , generic_ptr  data );
extern status circ_append(clist *p_L , generic_ptr data) ; 
extern status circ_delete(clist *p_L , generic_ptr *p_data);
extern status circ_delete_node(clist *p_L , clist node );
extern clist circ_list_iterator( clist L, clist lastreturn ) ; 
extern clist nth_node( clist L, int number );
extern status circ_traverse( clist L, status (*p_func_f)() ) ;












#endif

ducksinterface.c

#include "globals.h"
#include "clist.h"
#include <stdlib.h>

status circ_append_duck( clist *p_L , int n){

	int *t_ptr = (int *)malloc(sizeof(int) ) ;
	
	if( t_ptr == NULL ) return ERROR ; 

	*t_ptr = n ; 


	if( circ_append(p_L,(generic_ptr)t_ptr) == ERROR ) {free(t_ptr ) ; return ERROR ; } 

	


	return OK ; 

}

ducksinterface.h

#ifndef _ducksinterface
#define _ducksinterface

#include "globals.h"
#include "clist.h"

extern status circ_append_duck( clist *p_L , int n) ; 

#endif

globals.h

#ifndef _globals 

#define _globals 



#define DATA( L ) ( ( L ) -> datapointer ) 

#define NEXT( L ) ( ( L ) -> next ) 


typedef enum { OK, ERROR } status ; 
typedef enum { FALSE = 0 , TRUE=1 } bool ;  
typedef void *generic_ptr ; 

#endif

main.c

#include <stdio.h> 
#include <stdlib.h> 
#include "clist.h" 
#include "globals.h"
#include "ducksinterface.h"

status write_node( generic_ptr n){

printf(" %d ", *(int * )n ) ;
  return OK ;

}





clist getnextduck( clist ducks , clist nextduck ){


clist next ; 

next = circ_list_iterator(ducks,nextduck) ; 

if(next == NULL){
	return circ_list_iterator(ducks,nextduck ) ;

}


return next ; 
}



int main( int argc , char *argv[] ){

int n , m , i , num ; 

clist ducks , before , nextduck = NULL ; 

do printf("input n and m: ") ; while(scanf("%d %d",&n ,&m ) != 2 ) ; 

init_circ_list(&ducks) ; 

for( i = 1 ;  i <= n ; i++) circ_append_duck(&ducks , i ) ; 

printf("\nThe circular list is: ") ; 
circ_traverse(ducks,write_node) ; printf("\n") ; 

nextduck = getnextduck(ducks , NULL ) ; 

printf("The alligator ate the ducks int the following order: ") ; 

while(!empty_circ_list(ducks)){ 

for( i = 1 ; i < m ; i++ ) nextduck = getnextduck( ducks , nextduck ) ; 

before = nextduck ; 
nextduck = getnextduck(ducks , nextduck) ; 
write_node( DATA(nextduck)) ; 

circ_delete_node(&ducks , nextduck) ; 

nextduck = before ; 

} 

printf("\n") ; 
return 0 ; 
}

I put 8 and 4 and keep getting segmentation fault i think i did something wrong in the main file but im not sure

1
Contributor
1
Reply
3
Views
6 Years
Discussion Span
Last Post by rockerjhr
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.