/* DYNAMIC MEMORY */ /* ⚠️ Work in progress Go to main function (line: ) and use different functions to change elements. Some examples are already given; remove them if you like. ✔️ Available functions you can use: add( str_var, element ) insert( str_var, element, position ) delete_at( str_var , position ); delete_el( str_var, element); delete_all_el( str_var , element); print_memo( str_var ) ℹ️ Note: First element of these functions is always pointer to a structure variable. In OOP languages these functions would be methods and structure variable would be an object. The methods call would look like this: object.add( element ) 📑 Also I tried to divide this code in segments visually (since SoloLearn does not support files). In each segment there's: Location (name of the file where the code is stored) and little description. For example, you'll find: // header_1.h // Every c file contains this header 📄 Files: line: header_1.h line: main.c line: main_functions.c line: search_sort.c line: inner_functions.c line: helpful_functions.c ⚠️ Sometimes, structure member 'sorted' will return false even though the list is sorted. That's because if you call function add() which is O(1) time complexity (unless size needs to be increased and all elements have to be copied) then in order to make member 'sorted' always correct we would need to check if the array is sorted, which would make it O(n). Anyway, if sorted = true, then that's always correct. So, if sorted = false, it could be sorted or not. if sorted = true then it is sorted 100%. Actually this could be fixed by comparing nearest elements, without affecting performance (make it still O(1)). Maybe I'll try to do it. 📝 Notes to myself - Couldn't use remove as a function, apparently it is used in some library. Check it deeply and also c++ namespaces - If there are multiple same elements then delete_el() will delete one of those elements, if it is not sorted list then the element with the lowest index will be deleted. If it is sorted, then it depends on binary search. - delete_all_el() is not quiet nice. Try to find more general case, without special case. Here's an example with a problem: list: 42, 42 size = 2 Call function delete_all_el(42); for (int i = 0, i < size; i++) remove first 42 decrease size by 1 Now list is: 42 and size is = 1 That's fine, but look at the next iteration: i = 1, i < 1 false, so it doesn't delete last element. That's why I checked last element as a special case. Works, but not satisfied with the solution. Edit: Solution found */ // 📄 header_1.h // Every c file contains this header // --------------------------------------- #include #include #include #include #define ASCENDING 1 #define DESCENDING 0 typedef struct { int* p_el; int block_size; int el_num; bool sorted; } DyMemo; // main functions void initialize_memo(DyMemo*); void add(DyMemo*, int); void insert(DyMemo*, int, int); void delete_at(DyMemo*, int); void delete_el(DyMemo*, int); void delete_all_el(DyMemo*, int); int reserve(DyMemo*, int); // search & sort functions int linear_search(DyMemo*, int); int binary_search(DyMemo*, int); void insertion_sort(DyMemo*, int); void quick_sort(DyMemo*, int); // functions used by main functions void check_size(DyMemo*); void increase_size(DyMemo*); void right_shift(DyMemo*, int); void left_shift(DyMemo*, int); bool has_multiple_el(DyMemo*); bool is_sorted(DyMemo*); bool is_sorted_asc(DyMemo*); bool is_sorted_des(DyMemo*); int binary_search_asc(DyMemo*, int); int binary_search_des(DyMemo*, int); void swap(int*, int*); void quick_sort_asc(int*, int); void quick_sort_des(int*, int); void quick_check_sorted(DyMemo*); void check_pos(DyMemo*, int); void insertion_sort_asc(DyMemo*); void insertion_sort_des(DyMemo*); // helpful functions void print_memo(DyMemo*); void print_sorted(DyMemo*); void shuffle(DyMemo*); // shuffle // --------------------------------------- // 📄 main.c // C main function // --------------------------------------- int main() { srand(time(NULL)); DyMemo memo; initialize_memo(&memo); // reserve(&memo, 100); add(&memo, 42); print_memo(&memo); add(&memo, 4); add(&memo, 32); print_memo(&memo); add(&memo, 96); add(&memo, 5); add(&memo, 72); print_memo(&memo); insert(&memo, 1024, 3); insert(&memo, 30, 0); insert(&memo, 36, 0); print_memo(&memo); // printf(" ----%p \n\n", &(memo.p_el[0])); linear_search(&memo, 72); linear_search(&memo, 36); linear_search(&memo, 7000); insertion_sort(&memo, DESCENDING); print_memo(&memo); insertion_sort(&memo, ASCENDING); print_memo(&memo); print_sorted(&memo); delete_at(&memo, 1); print_memo(&memo); binary_search(&memo, 96); insertion_sort(&memo, DESCENDING ); print_memo(&memo); binary_search(&memo, 1024); delete_el(&memo, 72); print_memo(&memo); delete_el(&memo, 9999); add(&memo, 42); add(&memo, 42); add(&memo, 42); insert(&memo, 42, 3); print_memo(&memo); delete_all_el(&memo, 42); print_memo(&memo); quick_sort(&memo, ASCENDING); print_memo(&memo); quick_sort(&memo, DESCENDING); print_memo(&memo); quick_sort(&memo, 3); shuffle(&memo); print_memo(&memo); reserve(&memo, 100); print_memo(&memo); // printf("----%p ", &(memo.p_el[0])); return 0; } // --------------------------------------- // 📄 main_functions.c // Initialize members of a structure variable // --------------------------------------- void initialize_memo(DyMemo* p_memo) { p_memo->block_size = 0; p_memo->p_el = (int*)malloc(p_memo->block_size * sizeof(int)); p_memo->el_num = 0; p_memo->sorted = false; } // --------------------------------------- // 📄 main_functions.c // Main functions: add, insert, delete (with variations) // --------------------------------------- void add(DyMemo* p_memo, int el) { reserve(p_memo, p_memo->el_num + 1); // check_size(p_memo); p_memo->p_el[p_memo->el_num] = el; p_memo->el_num++; quick_check_sorted(p_memo); } void insert(DyMemo* p_memo, int el, int pos) { reserve(p_memo, p_memo->el_num + 1); check_pos(p_memo, pos); // check_size(p_memo); right_shift(p_memo, pos); p_memo->p_el[pos] = el; p_memo->el_num++; quick_check_sorted(p_memo); } void delete_at(DyMemo* p_memo, int pos) { check_pos(p_memo, pos); left_shift(p_memo, pos); (p_memo->el_num)--; quick_check_sorted(p_memo); } void delete_el(DyMemo* p_memo, int el) { int pos = p_memo->sorted? binary_search(p_memo, el) : linear_search(p_memo, el); if (pos == -1) return; left_shift(p_memo, pos); (p_memo->el_num)--; quick_check_sorted(p_memo); } void delete_all_el(DyMemo* p_memo, int el) { for (int i = 0; i < p_memo->el_num; i++) { if (p_memo->p_el[i] == el) { left_shift(p_memo, i); (p_memo->el_num)--; i--; quick_check_sorted(p_memo); } } } int reserve(DyMemo* p_memo, int block_size) { int* p_el; // do we need a reallocation? if (p_memo->block_size < block_size) { // calculate new block size p_memo->block_size *= 2; if (p_memo->block_size < block_size) p_memo->block_size = block_size; p_el = (int*) realloc(p_memo->p_el, p_memo->block_size * sizeof(int)); } else { // nothing to do return 0; } if (p_el == NULL) { printf("Not possible to increase memory!"); return -1; } p_memo->p_el = p_el; return 0; } // --------------------------------------- // 📄 search_sort.c // Search and sort algorithms implementations // --------------------------------------- int linear_search(DyMemo* p_memo, int el) { if (p_memo->el_num == 0) { printf("Empty list.\n\n"); return -1; } for (int i = 0; i < p_memo->el_num; i++) { if (p_memo->p_el[i] == el) { printf("Element %d is at position %d\n\n", el, i); return i; } } printf("Element %d does not exist\n\n", el); return -1; } int binary_search(DyMemo* p_memo, int el) { if (p_memo->el_num == 0) { printf("Empty list.\n\n"); return -1; } if (p_memo->p_el[0] < p_memo->p_el[p_memo->el_num-1]) return binary_search_asc(p_memo, el); return binary_search_des(p_memo, el); } void insertion_sort(DyMemo* p_memo, int order) { if (order == ASCENDING) { insertion_sort_asc(p_memo); p_memo->sorted = true; } else if (order == DESCENDING) { insertion_sort_des(p_memo); p_memo->sorted = true; } else printf("Second argument should be eather ASCENDING or DESCENDING\n\n"); } void insertion_sort_asc(DyMemo* p_memo) { int current = 0; int pos = 0; for (int i = 0; i < (p_memo->el_num - 1); i++) { current = p_memo->p_el[i+1]; pos = i; while (pos >= 0 && p_memo->p_el[pos] > current) { p_memo->p_el[pos+1] = p_memo->p_el[pos]; pos--; } p_memo->p_el[pos+1] = current; } } void insertion_sort_des(DyMemo* p_memo) { int current = 0; int pos = 0; for (int i = 0; i < (p_memo->el_num - 1); i++) { current = p_memo->p_el[i+1]; pos = i; while (pos >= 0 && p_memo->p_el[pos] < current) { p_memo->p_el[pos+1] = p_memo->p_el[pos]; pos--; } p_memo->p_el[pos+1] = current; } } void quick_sort(DyMemo* p_memo, int order) { if (order == ASCENDING) { quick_sort_asc(p_memo->p_el, p_memo->el_num); p_memo->sorted = true; } else if (order == DESCENDING) { quick_sort_des(p_memo->p_el, p_memo->el_num); p_memo->sorted = true; } else printf("Second argument should be eather ASCENDING or DESCENDING\n\n"); } void quick_sort_asc(int* p_el, int size) { if (0 >= size) return; int rand_indx = rand() % size; swap(&(p_el[rand_indx]), &(p_el[size - 1])); int piv_pos = 0; for (int i = 0; i < size - 1; i++) { if (p_el[i] <= p_el[size - 1]) { swap(&p_el[i], &p_el[piv_pos]); piv_pos++; } } swap(&p_el[size - 1], &p_el[piv_pos]); quick_sort_asc(p_el, piv_pos++); quick_sort_asc(p_el + piv_pos, size - piv_pos); } void quick_sort_des(int* p_el, int size) { if (0 >= size) return; int rand_indx = rand() % size; swap(&(p_el[rand_indx]), &(p_el[size - 1])); int piv_pos = 0; for (int i = 0; i < size - 1; i++) { if (p_el[i] >= p_el[size - 1]) { swap(&p_el[i], &p_el[piv_pos]); piv_pos++; } } swap(&p_el[size - 1], &p_el[piv_pos]); quick_sort_des(p_el, piv_pos++); quick_sort_des(p_el + piv_pos, size - piv_pos); } // --------------------------------------- // 📄 inner_functions.c // Functions that shouldn't be visible for users. They're used inside other main functions (add, insert, sort...) // --------------------------------------- void check_size(DyMemo* p_memo) { if (p_memo->block_size == p_memo->el_num) increase_size(p_memo); } void increase_size(DyMemo* p_memo) { int* p_new; p_memo->block_size *= 2; p_new = (int*)realloc(p_memo->p_el, p_memo->block_size * sizeof(int)); if (p_new == NULL) { printf("Not possible to increase memory!"); free(p_memo->p_el); exit(EXIT_FAILURE); } p_memo->p_el = p_new; } void right_shift(DyMemo* p_memo, int pos) { for (int i = p_memo->el_num; i > pos; i--) { p_memo->p_el[i] = p_memo->p_el[i-1]; } } void left_shift(DyMemo* p_memo, int pos) { for (int i = pos; i < p_memo->el_num - 1; i++) { p_memo->p_el[i] = p_memo->p_el[i+1]; } } bool is_sorted(DyMemo* p_memo) { return ( has_multiple_el(p_memo) && ( is_sorted_asc(p_memo) || is_sorted_des(p_memo) ) ); } bool has_multiple_el(DyMemo* p_memo) { return p_memo->el_num > 1; } bool is_sorted_asc(DyMemo* p_memo) { for (int i = 0; i < (p_memo->el_num) - 1; i++) { if (p_memo->p_el[i] > p_memo->p_el[i+1]) return false; } return true; } bool is_sorted_des(DyMemo* p_memo) { for (int i = 0; i < (p_memo->el_num) - 1; i++) { if (p_memo->p_el[i] < p_memo->p_el[i+1]) return false; } return true; } int binary_search_asc(DyMemo* p_memo, int el) { int low = 0; int high = p_memo->el_num - 1; int mid = 0; while (low <= high) { mid = (high - low) / 2 + low; if (p_memo->p_el[mid] == el) { printf("Element %d is at position %d\n\n", el, mid); return mid; } else if (p_memo->p_el[mid] < el) low = mid + 1; else high = mid - 1; } printf("Element %d does not exist\n\n", el); return -1; } int binary_search_des(DyMemo* p_memo, int el) { int low = 0; int high = p_memo->el_num - 1; int mid = 0; while (low <= high) { mid = (high - low) / 2 + low; if (p_memo->p_el[mid] == el) { printf("Element %d is at position %d\n\n", el, mid); return mid; } else if (p_memo->p_el[mid] > el) low = mid + 1; else high = mid - 1; } printf("Element %d does not exist\n\n", el); return -1; } void quick_check_sorted(DyMemo* p_memo) { if (has_multiple_el(p_memo)) p_memo->sorted = false; else p_memo->sorted = true; } void check_pos(DyMemo* p_memo, int pos) { if (pos >= p_memo->el_num || pos < 0) { printf("Invalid index"); return; } } void swap(int* p_a, int* p_b) { int temp = *p_a; *p_a = *p_b; *p_b = temp; } // --------------------------------------- // 📄 helpful_functions.c // Useful optional functions. // --------------------------------------- void print_memo(DyMemo* p_memo) { for (int i = 0; i < p_memo->el_num; i++) printf("%d ", p_memo->p_el[i]); printf("\nNumber of elements: %d \nMemory space on heap %lu bytes, holds %d integers\nSorted: %s\n\n", p_memo->el_num, (p_memo->block_size) * sizeof(int), p_memo->block_size, p_memo->sorted?"true":"false"); } void print_sorted(DyMemo* p_memo) { printf("Memory is%s sorted\n\n", p_memo->sorted?"":" NOT"); } void shuffle(DyMemo* p_memo) { int rand_indx = 0; for (int i = 0; i < p_memo->el_num; i++) { rand_indx = rand() % p_memo->el_num; swap(&(p_memo->p_el[i]), &(p_memo->p_el[rand_indx])); } } // --------------------------------------- /* --------------------------------------- This is an implementation of Dynamic Memory. There are 4 variables that are used to create a dynamic memory: pointer to integer ◽p_el that holds the address of the first element in the block. integer ◽block_size - how many integers block can hold at the given time. integer ◽el_num is the number of elements created in the block. bool ◽sorted gives true if array is sorted, otherwise false. To initialize members of a structure variable, function ◽initialize_memo() is used. There are 3+2 basic functionalities: ◽add( element ) ◽insert( element, position ) ◽delete() with different variations ◽sort ◽search Inside these basic functions there are other functions that shouldn't be diractly accessible to users. right_shift() left_shift() Also, there are "Helpful Functions", they're optional, less important: ◽print_memo() ◽shuffle() Functions: ◽ Callable by users: void initialize_memo(DyMemo*) ◽ Arguments: pointer to the structure variable of type DyMemo. ◽ Goal: Creates memory in heap ◽ Not Callable by users: ◽ Test Functions: --------------------------------------- */

Dynamic Memory ◽◽◽◽