C/Data Structure Algorithm/Tree — различия между версиями

Текущая версия на 10:22, 25 мая 2010

Содержание

1 Basics of a family tree
2 Basics of a family tree 2
3 Displays a binary tree
4 Investigating the family

Basics of a family tree

/*
Beginning C, Third Edition
 By Ivor Horton
 ISBN: 1-59059-253-0
 Published: Apr 2004
 Publisher: apress
*/
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
struct Family *get_person(void);    /* Prototype for input function */
char related(struct Family *pmember1, struct Family *pmember2);
char set_ancestry(struct Family *pmember1, struct Family *pmember2);
struct Date   
{
  int day;
  int month;
  int year;
};
struct Family                      /* Family structure declaration   */
{
  struct Date dob;
  char name[20];
  char father[20];
  char mother[20];
  struct Family *next;            /* Pointer to next structure      */
  struct Family *previous;        /* Pointer to previous structure  */
  struct Family *p_to_pa;         /* Pointer to father structure   */
  struct Family *p_to_ma;         /* Pointer to mother structure   */
};
void main()
{
   struct Family *first = NULL;    /* Pointer to first person        */
   struct Family *current = NULL;  /* Pointer to current person      */
   struct Family *last = NULL;     /* Pointer to previous person     */
   
   char more = "\0";               /* Test value for ending input    */
   for( ; ; )
   {
     printf("\nDo you want to enter details of a%s person (Y or N)? ", 
                                        first != NULL?"nother " : "" );
     scanf(" %c", &more);
     if(tolower(more) == "n") 
       break;
     current = get_person();
     if(first == NULL)
     {
       first = current;            /* Set pointer to first Family    */
       last = current;             /* Remember for next iteration    */
     }
     else
     {
       last->next = current;  /* Set next address for previous Family */  
       current->previous = last; /* Set previous address for current */
       last = current;           /* Remember for next iteration */             
     }
   }
   current = first;
   while(current->next != NULL)  /* Check for relation for each person in    */
   {                       /* the list up to second to last            */
     int parents = 0;      /* Declare parent count local to this block */
     last = current->next; /* Get the pointer to the next              */
     while(last != NULL)   /* This loop tests current person           */
     {                     /* against all the remainder in the list    */
       if(related(current, last))         /* Found a parent ?          */
         if(++parents == 2)   /* Yes, update count and check it        */
           break;             /* Exit inner loop if both parents found */
       last = last->next;     /* Get the address of the next           */
     } 
     current = current->next;   /* Next in the list to check             */
   }
   /* Now tell them what we know */
   /* Output Family data in correct order */
   current = first;
   while (current != NULL)  /* Output Family data in correct order  */
   {
     printf("\n%s was born %d/%d/%d, and has %s and %s as parents.",
                  current->name, current->dob.day, current->dob.month,
               current->dob. year, current->father,  current->mother);
     if(current->p_to_pa != NULL )
       printf("\n\t%s"s birth date is %d/%d/%d  ",
                current->father, current->p_to_pa->dob.day,
                               current->p_to_pa->dob.month, 
                               current->p_to_pa->dob.year);
     if(current->p_to_ma != NULL)
       printf("and %s"s birth date is %d/%d/%d.\n  ",
                current->mother, current->p_to_ma->dob.day,
                               current->p_to_ma->dob.month, 
                               current->p_to_ma->dob.year);
     current = current->next;  /* current points to next in list       */
   }
   /* Now free the memory */  
   current = first;
   while(current->next != NULL)
   {
     last = current;     /* Save pointer to enable memory to be freed */
     current = current->next; /* current points to next in list       */
     free(last);         /* Free memory for last                      */
   }
}
/*   Function to input data on Family members   */
struct Family *get_person(void)
{
   struct Family *temp;         /* Define temporary structure pointer */
   /* Allocate memory for a structure */
   temp = (struct Family*) malloc(sizeof(struct Family));
   printf("\nEnter the name of the person: ");
   scanf("%s", temp -> name );         /* Read the Family"s name */
   printf("\nEnter %s"s date of birth (day month year); ", temp->name);
   scanf("%d %d %d", &temp->dob.day, &temp->dob.month, &temp->dob.year);
   printf("\nWho is %s"s father? ", temp->name );
   scanf("%s", temp->father );        /* Get the father"s name */
 
   printf("\nWho is %s"s mother? ", temp -> name );
   scanf("%s", temp -> mother );      /* Get the mother"s name */
 
   temp->next = temp->previous = NULL; /* Set pointers to NULL */
   temp->p_to_pa = temp->p_to_ma = NULL;    /* Set pointers to NULL  */
   return temp;          /* Return address of Family structure */
}
char set_ancestry(struct Family *pmember1, struct Family *pmember2)
{
   if(strcmp(pmember1->father, pmember2->name) == 0)
   {
     pmember1->p_to_pa = pmember2;
     return 1;
   }
   if( strcmp(pmember1->mother, pmember2->name) == 0)
   {
     pmember1->p_to_ma = pmember2;
     return 1;
   }
   else
     return 0;
}
/* Fill in pointers for mother or father relationships */
char related (struct Family *pmember1, struct Family *pmember2)
{
   return set_ancestry(pmember1, pmember2) ||
                           set_ancestry(pmember2, pmember1);
}

Basics of a family tree 2

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
struct Cat *getCat(void);
struct Date
{
   int day;
   int month;
   int year;
};
struct Cat
{
   struct Date dob;
   char name[20];
   char father[20];
   char mother[20];
   struct Cat *next;
   struct Cat *previous;
};
int main()
{
   struct Cat *first = NULL;
   struct Cat *current = NULL;
   struct Cat *last = NULL;
   char more = "\0";
   int i =0;
   for(i =0;i<5 ;i++ )
   {
     current = getCat();
     if(first == NULL){
       first = current;
       last = current;
     }else {
       last->next = current;
       current->previous = last;
       last = current;
     }
   }
   while (current  != NULL)
   {
     printf("\n%s was born %d/%d/%d, and has %s and %s as parents.",
              current->name, current->dob.day, current->dob.month,
              current->dob. year, current->father,  current->mother );
     last = current;     /* Save pointer to enable memory to be freed */
     current = current->previous;  /* current points to previous list */
     free(last);
   }
}
struct Cat *getCat(void)
{
   struct Cat *temp;
   temp = (struct Cat*) malloc(sizeof(struct Cat));
   printf("\nEnter the name of the person: ");
   scanf("%s", temp -> name );
   printf("\nEnter %s"s date of birth (day month year); ", temp->name);
   scanf("%d %d %d", &temp->dob.day, &temp->dob.month, &temp->dob.year);
   printf("\nWho is %s"s father? ", temp->name );
   scanf("%s", temp->father );
   printf("\nWho is %s"s mother? ", temp -> name );
   scanf("%s", temp -> mother );
   temp->next = temp->previous = NULL;
   return temp;
}

Displays a binary tree

/*
C: The Complete Reference, 4th Ed. (Paperback)
by Herbert Schildt
ISBN: 0072121246
Publisher: McGraw-Hill Osborne Media; 4 edition (April 26, 2000)
*/
/* This program displays a binary tree. */
#include <stdlib.h>
#include <stdio.h>
struct tree {
  char info;
  struct tree *left;
  struct tree *right;
};
struct tree *root; /* first node in tree */
struct tree *stree(struct tree *root,
                   struct tree *r, char info);
void print_tree(struct tree *root, int l);
int main(void)
{
  char s[80];
  root = NULL;  /* initialize the root */
  do {
    printf("Enter a letter: ");
    gets(s);
    root = stree(root, root, *s);
  } while(*s);
  print_tree(root, 0);
  return 0;
}
struct tree *stree(
  struct tree *root,
  struct tree *r,
  char info)
{
  if(!r) {
    r = (struct tree *) malloc(sizeof(struct tree));
    if(!r) {
      printf("Out of Memory\n");
      exit(0);
    }
    r->left = NULL;
    r->right = NULL;
    r->info = info;
    if(!root) return r; /* first entry */
    if(info < root->info) root->left = r;
    else root->right = r;
    return r;
  }
  if(info < r->info)
    stree(r, r->left, info);
  else
    stree(r, r->right, info);
  return root;
}
void print_tree(struct tree *r, int l)
{
  int i;
  if(!r) return;
  print_tree(r->right, l+1);
  for(i=0; i<l; ++i) printf(" ");
  printf("%c\n", r->info);
  print_tree(r->left, l+1);
}

Investigating the family

/*
Beginning C, Third Edition
 By Ivor Horton
 ISBN: 1-59059-253-0
 Published: Apr 2004
 Publisher: apress
*/
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
char myfile[] = "C:\\myfile.bin"; /* Physical file name      */
FILE *pfile = NULL;               /* File pointer            */
struct Date                       /* Structure for a date    */
{
   int day;
   int month;
   int year;
};
typedef struct family        /* Family structure declaration */
{
   struct Date dob;
   char name[20];
   char pa_name[20];
   char ma_name[20];
}Family;
/* Function prototypes */
int get_person(Family *pfamily);       /* Input function           */
void show_person_data(void);           /* Output function          */
void get_parent_dob(Family *pfamily);  /* Function to find pa & ma */
void main()
{
   Family member;                      /* Stores a family structure */
   Family *pmember = &member;     /* Points to the family structure */
   if((pfile = fopen(myfile, "wb")) == NULL)
   {
     printf("\nUnable to open %s for writing.\n", myfile);
     abort();
   }
   while(get_person(pmember))           /* As long as we have input */
     fwrite(pmember, sizeof member, 1, pfile);  /*    write it away */
   fclose(pfile);                 /* Close the file now its written */
   show_person_data();            /* Show what we can find out      */
   if(remove(myfile))
     printf("\nUnable to delete %s.\n", myfile);
   else
     printf("\nDeleted %s OK.\n", myfile);
}
/* Function to input data on Family members */
int get_person( Family *temp)
{
   static char more = "\0";    /* Test value for ending input */
   printf("\nDo you want to enter details of a%s person (Y or N)? ",
                                       more != "\0"?"nother " : "" );
   scanf(" %c", &more);
   if(tolower(more) == "n") 
          return 0;
   printf("\nEnter the name of the person: ");
   scanf("%s", temp->name);         /* Read the Family"s name */
   printf("\nEnter %s"s date of birth (day month year); ", temp->name);
   scanf("%d %d %d", &temp->dob.day, &temp->dob.month, &temp->dob.year);
   printf("\nWho is %s"s father? ", temp->name);
   scanf("%s", temp->pa_name);      /* Get the father"s name  */
   printf("\nWho is %s"s mother? ", temp->name);
   scanf("%s", temp->ma_name);      /* Get the mother"s name  */
   return 1;
}
/* Function to output data on people on file   */
void show_person_data(void)
{
   Family member;             /* Structure to hold data from file  */
   Family *pmember = &member; /* Pointer to Family structure       */
   fpos_t current = 0;        /* File position                     */
   pfile = fopen(myfile, "rb"); /* Open file for binary read  */
   /* Read data on person */
   while(fread(pmember, sizeof member, 1, pfile))   
   {
     fgetpos(pfile, &current);  /* Save current position      */
     printf("\n\n%s"s father is %s, and mother is %s.",
              pmember->name, pmember->pa_name, pmember->ma_name);
     get_parent_dob(pmember);   /* Get parent data            */
     fsetpos(pfile, &current);  /* Position file to read next */
   }
    fclose(pfile);              /* Close the file             */
}
/* Function to find parents" dates of birth. */
void get_parent_dob(Family *pmember)
{
   Family testmem;             /* Stores a relative         */
   Family *ptestmem = &testmem; /* Pointer to the relative   */
   int num_found = 0;           /* Count of relatives found  */
   rewind(pfile);               /* Set file to the beginning */
   /* Get the stuff on a relative */
   while(fread(ptestmem, sizeof(Family), 1, pfile))
   {
     if(strcmp(pmember->pa_name, ptestmem->name) == 0)   /*Is it pa? */
     { /* We have found dear old dad */
       printf("\n Pa was born on %d/%d/%d.",
             ptestmem->dob.day, ptestmem->dob.month, ptestmem->dob.year);  
 
       if(++num_found == 2)    /* Increment parent count    */
         return;               /* We got both so go home    */
     }
     else
       if(strcmp(pmember->ma_name, ptestmem->name) == 0) /*Is it ma? */
       { /* We have found dear old ma */
         printf("\n Ma was born on %d/%d/%d.",
                ptestmem->dob.day, ptestmem->dob.month, ptestmem->dob.year);
         if(++num_found == 2)  /* Increment parent count    */
             return;           /* We got both so go home    */
       }
   }
}

C/Data Structure Algorithm/Tree — различия между версиями

Текущая версия на 10:22, 25 мая 2010

Содержание

Basics of a family tree

Basics of a family tree 2

Displays a binary tree

Investigating the family

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Ещё

Поиск

С

С++

Навигация

Инструменты

Текущая версия на 10:22, 25 мая 2010 (просмотреть исходный код) Admin (обсуждение \| вклад) м (1 версия: Импорт контента...)	Текущая версия на 10:22, 25 мая 2010 (просмотреть исходный код) Admin (обсуждение \| вклад) м (1 версия: Импорт контента...)
(нет различий)