main.c 13.9 KB
 Dominik Widhalm committed Aug 20, 2017 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 #include #include /***** 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; `````` Dominik Widhalm committed Aug 28, 2017 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; } `````` Dominik Widhalm committed Aug 20, 2017 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; `````` Dominik Widhalm committed Aug 21, 2017 287 288 `````` element_t *head = NULL; element_t *tmp = NULL; `````` Dominik Widhalm committed Aug 20, 2017 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; inext; /* Free memory of current element */ free(tmp); } `````` Dominik Widhalm committed Aug 20, 2017 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) */ } /******************************************************************************/``````