main.c 13.9 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
/******************************************************************************
 *                               C PROGRAMMING                                *
 *                    BASIC EXERCISES - EXAMPLE SOLUTIONS                     *
 *                                                                            *
 *      Task_6.07:  Adaptive Gratification List                               *
 *      Author:     Dominik Widhalm                                           *
 *      Email:      dominik.widhalm@technikum-wien.at                         *
 *      Date:       2017-08-20                                                *
 *                                                                            *
 ******************************************************************************/


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


/***** MACROS *****************************************************************/
// Maximum length of strings
#define STRING_MAX 20
// Maximum number of elements
#define ELEMENTS_MAX 25


/***** TYPEDEFS ***************************************************************/
/* Struct type for the single linked list */
typedef struct element {
        // Actual value
        int value;
        // Number of accesses
        int accesses;
        // Pointer to next element
        struct element *next;
    } element_t;


/***** FUNCTION PROTOTYPES ****************************************************/
int get_random_number (void);
void list_add_element (element_t **head);
void list_access_element (element_t **head, int value);
void list_sort (element_t** head);
void list_print (element_t* head, int index);


/***** LOCAL FUNCTIONS ********************************************************/
/******************************************************************************
 *      get_random_number                                                     *
 *      @brief Function to get a random number between 0 and 99.              *
 *                                                                            *
 *      This function returns a random number in the range between 0 and 99.  *
 *                                                                            *
 *      @return                 Random number between 0 and 99                *
 ******************************************************************************/
int get_random_number (void) {
    /* Return a random number between 0 and 99 */
    return (rand()%100);
}


/******************************************************************************
 *      list_add_element                                                      *
 *      @brief Function to add a new element to the list.                     *
 *                                                                            *
 *      This function adds a new element to the list and fills the element    *
 *      with a random value and sets its number of accesses initially to 0.   *
 *                                                                            *
 *      @param head             Pointer to pointer to the first list element  *
 ******************************************************************************/
void list_add_element (element_t **head) {
    /* Temporary variable to mark if value is already available */
    int free_value;
    /* Random value to be filled in new element */
    int number;
75
76
77
78
79
80
81
82
83
84
85
86
    /* Temporary pointer to iterate over the list */
    element_t* curr = *head;
    /* Allocate memory for the new person */
    element_t* new = (element_t*)malloc(sizeof(element_t));
    
    /* Check if memory allocation was successful */
    if (new == NULL) {
        /* Memory allocation failed */
        printf("Cannot allocate memory!\n");
        /* Return to caller */
        return;
    }
87
88
89
90
91
92
93
94
95
96
97
98
99
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
    
    /** Fill new element with information **/
    /* Until a free number was returned ... */
    do {
        /* Initially assume a free number */
        free_value = 1;
        /* Get a random value for this number */
        number = get_random_number();
        /* Check if this number is already in use */
        while (curr != NULL) {
            /* Check if value of current element equals random value */
            if (curr->value == number) {
                /* Value already in use */
                free_value = 0;
                /* Value already in use, jump to end of loop */
                break;
            } else {
                /* Continue with next element */
                curr = curr->next;
            }
        }
    } while (free_value != 1);
    /* Set value of new element to previously obtained random number */
    new->value = number;
    /* Set the access counter initially to 0 */
    new->accesses = 0;
    
    /** Actually add element to the list **/
    /* Set next pointer of new element to NULL */
    new->next = NULL;
    /* Check if list is empty */
    if (*head == NULL) {
        /* Set head to the given element */
        *head = new;
    } else {
        /* Use curr pointer to search for the last element */
        curr = *head;
        /* Search for the last element */
        while (curr->next != NULL) {
            curr = curr->next;
        }
        /* Append new element to the last element */
        curr->next = new;
    }
    
    /* A void function has nothing to return */
    return;
}


/******************************************************************************
 *      llist_access_element                                                  *
 *      @brief Function to access an element of the list.                     *
 *                                                                            *
 *      This function "accesses" an given element of the list by increasing   *
 *      its access count by 1. If a value not contained in the list is given  *
 *      nothing happens.                                                      *
 *                                                                            *
 *      @param head             Pointer to pointer to the first list element  *
 ******************************************************************************/
void list_access_element (element_t **head, int value) {
    /* Static variable to count the number of accesses */
    static int count = 0;
    element_t* curr = *head;        // Pointer to current element
    
    /* Iterate over list and look for the given value */
    while (curr != NULL) {
        /* Check if value of current element equals given value */
        if (curr->value == value) {
            /* Value found -- "access" it */
            curr->accesses++;
            /* Increase number of valid accesses */
            count++;
            /* Value already found, jump to end of loop */
            break;
        } else {
            /* Continue with next element */
            curr = curr->next;
        }
    }
    /* Check if there had already been 10 valid accesses */
    if (count > 9) {
        /* Reset count to 0 */
        count = 0;
        /* Sort current list */
        list_sort(head);
    }
    /* A void function has nothing to return */
    return;
}


/******************************************************************************
 *      list_sort                                                             *
 *      @brief Function to sort the current list.                             *
 *                                                                            *
 *      This function sorts the current list according to the gratification   *
 *      principle with the access counts stored in the structure.             *
 *                                                                            *
 *      @param head             Pointer to pointer to the first list element  *
 ******************************************************************************/
void list_sort (element_t** head) {
    
    /** TODO: bug in this function -- sometimes infinity loop, sometimes elements disappear **************/
    /** If bug is found, also correct it in task 6.04 !!! */
    
    /* Temporary variables */
    int swapped;                    // Remembers if there had been a swap or not
    element_t* curr = *head;        // Pointer to current element
    element_t* prev;                // Pointer to previous element
    element_t* temp;                // Temporary helper pointer
    /* Check if the list is long enough to be sorted */
    if ((curr == NULL) || (curr->next == NULL)) {
        /* List is not long enough for sorting */
        return;
    }
    /* Repeat sorting as long as there are swaps */
    do {
        /* Reset swapped to 0 */
        swapped = 0;
        /* Reset curr & prev to head */
        curr = *head;
        prev = *head;
        /* Iterate over the entire list */
        while (curr->next != NULL) {
            /* Check if entries need to be swapped */
            if (curr->accesses < curr->next->accesses) {
                /* Check if current element is the head (first) element */
                if (*head == curr) {
                    /* Swap elements */
                    *head = curr->next;
                    curr->next = (*head)->next; 
                    (*head)->next = curr;
                    /* Correct curr & prev pointer */
                    curr = prev;
                    prev = *head;
                } else {
                    /* Swap elements */
                    prev->next = curr->next;
                    curr->next = curr->next->next;
                    prev->next->next = curr;
                    /* Correct curr & prev pointer */
                    temp = curr;
                    curr = prev;
                    prev = temp;
                }
                /* Remember that there have been a swap */
                swapped = 1;
                /* Continue with next iteration over the entire loop */
                break;
            /* When not checking the first element */
            } else if (*head != curr) {
                /* Increment previous pointer */
                prev = prev->next;
            }
            /* Continue with next element */
            curr = curr->next;
        }
    } while (swapped == 1);
    
    /* A void function has nothing to return */
    return;
}


/******************************************************************************
 *      list_print                                                            *
 *      @brief Function to print the current list.                            *
 *                                                                            *
 *      This function prints the current list (recursively).                  *
 *                                                                            *
 *      @param head             Pointer to the first list element             *
 ******************************************************************************/
void list_print (element_t* head, int index) {
    /* Before first element print header */
    if (index == 1) {
        printf("\nList of numbers:\n");
    }
    /* Print list recursively */
    if (head != NULL) {
        /* Print current element */
        printf("%2d. Value: %2d (accesses %03d)\n",index,head->value,head->accesses);
        /* Call function with next element */
        list_print(head->next,++index);
    } else {
        /* End list with an additional newline */
        printf("\n");
    }
    /* A void function has nothing to return */
    return;
}


/***** MAIN ROUTINE ***********************************************************/
int main (void) {
    /*** Local Variables ***/
    char input[STRING_MAX];
    int elements=0;
    int number=0;
    int is_number=0;
287
288
    element_t *head = NULL;
    element_t *tmp = NULL;
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
    
    /* Initialize the random function with the current system time */
    srand((unsigned int)time(NULL));
    
    /* Ask for user input at least once */
    do {
        /* Ask the user to input the number of elements to be created */
        printf("Please enter the number of elements to be created (max: %d): ",ELEMENTS_MAX);
        /* Read in the user's input */
        scanf("%d",&elements);
        /* Check input for validity */
        if (elements > ELEMENTS_MAX) {
            /* Notifiy the user about invalid input */
            printf("The given number is to big!\n\n");
        } else if (elements <= 0) {
            /* Notifiy the user about invalid input */
            printf("The given number is to small!\n\n");
        }
    /* Repeat if input is invalid */
    } while ((elements > ELEMENTS_MAX) || (elements <= 0));
    
    /* Fill the list with the given number of elements */
    for (int i=0; i<elements; i++) {
        /* Add a new element to the list */
        list_add_element(&head);
    }
    
    /* Repeat as long as valid inputs are given (at least once) */
    do {
        list_print(head,1);
        /* Ask the user to input a number */
        printf("Please enter one of the numbers shown above: ");
        /* Read in the user's input as string */
        scanf("%s",input);
        /* Check if string contains a number */
        if (sscanf(input,"%d",&number) == 0) {
            /* No number found */
            is_number = 0;
        } else {
            /* A number was entered */
            is_number = 1;
            /* Access this number */
            list_access_element(&head,number);
        }
    /* Stop if recent input was not a number */
    } while (is_number == 1);
    
336
337
338
339
340
341
342
343
344
345
    /* Release the allocated memory */
    while (head != NULL) {
        /* Save pointer to current element */
        tmp = head;
        /* Set head to the next element */
        head = tmp->next;
        /* Free memory of current element */
        free(tmp);
    }
    
346
347
348
349
350
351
    /* Notify the user about the termination of the program */
    printf("\nThe program will now be terminated...\n");
    
    return 0;                           /* Return with Success (0)            */
}
/******************************************************************************/