main.c 15.3 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/******************************************************************************
 *                               C PROGRAMMING                                *
 *                    BASIC EXERCISES - EXAMPLE SOLUTIONS                     *
 *                                                                            *
 *      Task_6.15:  Ancestor Table                                            *
 *      Author:     Dominik Widhalm                                           *
 *      Email:      dominik.widhalm@technikum-wien.at                         *
 *      Date:       2017-09-04                                                *
 *                                                                            *
 ******************************************************************************/


/***** INCLUDES ***************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


/***** MACROS *****************************************************************/
// Maximum length of strings
#define STRING_MAX 20
// Maximum depth of the ancestor tree
#define TREE_MAX_DEPTH 5


/***** TYPEDEFS ***************************************************************/
/* Enumeration type for function return values */
typedef enum {SUCCESS, FAILED} retval_t;
/* Enumeration type for adding type */
typedef enum {SUBJECT, FATHER, MOTHER} addtype_t;
/* Structure for a tree element */
typedef struct person {
    /* Kekule number */
    int kekule;
    /* Person's first name */
    char firstname[STRING_MAX];
    /* Person's family name */
    char familyname[STRING_MAX];
    /* Pointer to the father element */
    struct person *father;
    /* Pointer to the mother element */
    struct person *mother;
} person_t;


/***** FUNCTION PROTOTYPES ****************************************************/
person_t *person_new (addtype_t type, person_t *child);
retval_t person_add_parents (person_t *child);
retval_t person_add_level (person_t *subject);
int person_get_depth (person_t *subject);
void person_print_level (person_t *subject, int level);
void person_print_tree (person_t *subject);
void person_free (person_t *node);


/***** LOCAL FUNCTIONS ********************************************************/
/******************************************************************************
 *      person_new                                                            *
 *      @brief Function to create a new person.                               *
 *                                                                            *
 *      This function creates a new person element, queries his/her name and  *
 *      returns the element's address.                                        *
 *                                                                            *
 *      @return                 Pointer to the new element                    *
 ******************************************************************************/
person_t *person_new (addtype_t type, person_t *child) {
    /* Allocate memory for the new element */
    person_t* new = (person_t*)malloc(sizeof(person_t));
    /* Check if malloc was successful */
    if (new == NULL) {
        /* Memory could not be allocated */
        return NULL;
    }
    /* Temporary string for user query */
    char query[STRING_MAX];
    /* User query text depends on type of new element */
    switch(type) {
        case SUBJECT:
            sprintf(query,"the subject");
            break;
        case FATHER:
            sprintf(query,"%s's father",child->firstname);
            break;
        case MOTHER:
            sprintf(query,"%s's mother",child->firstname);
            break;
    }
    /* Ask the user to enter the person's first name */
    printf("Please enter %s's first name: ",query);
    /* Read in the user's input */
91
    fgets(new->firstname,STRING_MAX,stdin);
92
93
    /* Remove trailing newline */
    strtok(new->firstname,"\n");
94
95
96
    /* Ask the user to enter the person's family name */
    printf("Please enter %s's family name: ",query);
    /* Read in the user's input */
97
    fgets(new->familyname,STRING_MAX,stdin);
98
99
    /* Remove trailing newline */
    strtok(new->familyname,"\n");
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
    /* Initially set its Kekule number to 0 */
    new->kekule = 0;
    /* Initially set its parent pointers to NULL */
    new->father = NULL;
    new->mother = NULL;
    /* Return the address of the new element */
    return new;
}


/******************************************************************************
 *      person_add_parents                                                    *
 *      @brief Function to add/create the parents of a given person.          *
 *                                                                            *
 *      This function adds/creates the parent elements of a given person.     *
 *      Thereby also the Kekule numbers are calculated and added.             *
 *                                                                            *
 *      @param child            Pointer to the child element                  *
 *      @retval SUCCESS         Parents were successfully added               *
 *      @retval FAILED          Parents could not be added                    *
 ******************************************************************************/
retval_t person_add_parents (person_t *child) {
    /* Check if the child has a valid address */
    if (child == NULL) {
        /* No valid child available */
        return FAILED;
    }
    
    /* Create the child's father */
    child->father = person_new(FATHER,child);
    /* Check if the element was successfully created */
    if (child->father == NULL) {
        /* Father element could not be created */
        return FAILED;
    }
    /* Calculate the father's Kekule number */
    child->father->kekule = child->kekule * 2;
    
    /* Print a separating space */
    printf("\n");
    
    /* Create the child's mother */
    child->mother = person_new(MOTHER,child);
    /* Check if the element was successfully created */
    if (child->mother == NULL) {
        /* Mother element could not be created */
        return FAILED;
    }
    /* Calculate the mother's Kekule number */
    child->mother->kekule = child->kekule * 2 + 1;
    
    /* Parents were successfully added */
    return SUCCESS;
}


/******************************************************************************
 *      person_add_level                                                      *
 *      @brief Function to add a new level of ancestors.                      *
 *                                                                            *
 *      This function adds/creates an entire level of ancestors. To do so, it *
 *      recursively traverses the current tree and adds parents to each leaf  *
 *      node.                                                                 *
 *                                                                            *
 *      @param subject          Pointer to the subject (first) element        *
 *      @retval SUCCESS         Level was successfully added                  *
 *      @retval FAILED          Level could not be added                      *
 ******************************************************************************/
retval_t person_add_level (person_t *subject) {
    /* Check if given subject has a valid address */
    if (subject == NULL) {
        /* No valid subject available */
        return FAILED;
    }
    /* Check if current node is already a leaf node (determined by mother pointer) */
    if (subject->mother == NULL) {
        /* Print a separating space */
        printf("\n");
        /* (Try to) add parents to this leaf node */
        return person_add_parents(subject);
    } else {
        /* Temporary retval variable */
        retval_t father, mother;
        /* (Try to) add new level recursively */
        father = person_add_level(subject->father);
        mother = person_add_level(subject->mother);
        /* Return the return values */
        if ((father == SUCCESS) && (mother == SUCCESS)) {
            /* Adding was successfull */
            return SUCCESS;
        } else {
            /* Adding failed */
            return FAILED;
        }
    }
}


/******************************************************************************
 *      person_get_depth                                                      *
 *      @brief Function to determine the current depth of the tree.           *
 *                                                                            *
 *      This function calculates and returns the current depth of the tree.   *
 *                                                                            *
 *      @param subject          Pointer to the subject (first) element        *
 *      @return                 Current depth of the tree (min = 1)           *
 ******************************************************************************/
int person_get_depth (person_t *subject) {
    /* Temporary variable for the depth */
    int temp = 1;
    /* Temporary pointer to traverse the tree */
    person_t* curr = subject;
    /* Go down the tree (use father's sides) */
    while (curr->father != NULL) {
        /* Increase depth counter */
        temp++;
        /* Go to the next level */
        curr = curr->father;
    }
    /* Return the obtained depth */
    return temp;
}


/******************************************************************************
 *      erson_print_level                                                     *
 *      @brief Function to print all elements of a given level.               *
 *                                                                            *
 *      This function prints all elements of a given level of depth.          *
 *                                                                            *
 *      @param subject          Pointer to the subject (first) element        *
 ******************************************************************************/
void person_print_level (person_t *subject, int level) {
    /* Check if given subject has a valid address */
    if (subject == NULL) {
        return;
    }
    /* Check if desired level has been reached */
    if (level == 1) {
        /* Print the current element's data */
        printf("%02d - %s %s\n",subject->kekule,subject->firstname,subject->familyname);
    /* Continue recursively until desired level is reached */
    } else if (level > 1) {
        /* Call function with the father's side */
        person_print_level(subject->father,(level-1));
        /* Call function with the mothers's side */
        person_print_level(subject->mother,(level-1));
    }
    /* A void function has nothing to return */
    return;
}


/******************************************************************************
 *      person_print_tree                                                     *
 *      @brief Function to print the current ancestor tree recursively.       *
 *                                                                            *
 *      This function prints the current ancestor tree in list form where the *
 *      elements are defined by their Kekule number                           *
 *                                                                            *
 *      @param subject          Pointer to the subject (first) element        *
 ******************************************************************************/
void person_print_tree (person_t *subject) {
    /* Check if subject node is valid */
    if (subject == NULL) {
        /* No more nodes */
        return;
    }
    /* Print the table header */
    printf("\n========== ANCESTOR TABLE ==========\n");
    /* Get the depth of the current tree */
    int depth = person_get_depth(subject);
    /* Print the tree level by level */
    for (int i=1; i<=depth; i++) {
        /* Print generation */
        printf("Generation %d:\n",(i-1));
        /* Print all elements of current level */
        person_print_level(subject,i);
        /* Add a newline if it is not the last level */
        if (i<depth) {
            printf("\n");
        }
    }
    printf("====================================\n\n");
    /* A void function has nothing to return */
    return;
}


/******************************************************************************
 *      person_free                                                           *
 *      @brief Function to free the memory of the tree recursively.           *
 *                                                                            *
 *      This function traverses the tree and frees the memory of all nodes    *
 *      contained recursively.                                                *
 *                                                                            *
 *      @param node             Pointer to the current node                   *
 ******************************************************************************/
void person_free (person_t *node) {
    /* Check if current node is already a NULL pointer */
    if (node == NULL) {
        /* Nothing to be done here */
        return;
    }
    /* Recursively free the memory of the parents */
    person_free(node->father);
    person_free(node->mother);
    /* Now free the memory of the current node */
    free(node);
    /* A void function has nothing to return */
    return;
}


/***** MAIN ROUTINE ***********************************************************/
int main (void) {
    /*** Local Variables ***/
    char input='n';
    int depth;
    /* Create the subject node */
    person_t *subject = person_new(SUBJECT,NULL);
    /* Check if the subject node could be created */
    if (subject == NULL) {
        /* Subject node could not be created */
        printf("\nERROR: Could not create subject node!\n");
    } else {
        /* First element (subject) has kekule number = 1 */
        subject->kekule = 1;
        /* Add new levels as long as the user wants to */
        do {
            /* Print the current tree */
            person_print_tree(subject);
            /* Get the current depth of the tree */
            depth = person_get_depth(subject);
            /* Check if maximum depth is not reached yet */
            if (depth >= TREE_MAX_DEPTH) {
                /* Maximum depth has been reached */
                input = 'n';
            } else {
                /* Ask the user if he/she wants to add a new level of parents */
                printf("Do you want to add a new level (y/n): ");
                /* Read in the user's response */
342
                scanf(" %c%*c",&input);
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
                /* Check if user wants to add a new level */
                if (input == 'y') {
                    /* (Try to) add a new level of ancestors */
                    if (person_add_level(subject) == FAILED) {
                        /* New level of ancestors could not be created */
                        printf("\nERROR: Could not create new level of ancestors!\n");
                    }
                }
            }
        } while (input == 'y');
    }
    
    /* Free the allocated memory recursively */
    person_free(subject);
    
    /* Notify the user about the termination of the program */
    printf("\nThe program will now be terminated...\n");
    
    return 0;                           /* Return with Success (0)            */
}
/******************************************************************************/