C/Data Structure Algorithm/Tree
Содержание
Basics of a family tree
<source lang="cpp"> /* 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);
}
</source>
Basics of a family tree 2
<source lang="cpp">
- 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;
}
</source>
Displays a binary tree
<source lang="cpp"> /* 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);
}
</source>
Investigating the family
<source lang="cpp"> /* 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, ¤t); /* 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, ¤t); /* 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 */
}
}
}
</source>
