I'm trying to create a function in order to create a ascending order list by using "malloc" and "realloc".
Here is the structure:
struct sorted_dyn_array {
int *array;
int length;
int capacity;
};
returns a pointer to a sorted_dyn_array structure, allocated on the heap
const int BUFFER_INIT_SIZE = 5;
const int KEY_NOT_FOUND = -1;
struct sorted_dyn_array *arr_create(void) {
struct sorted_dyn_array *new_arr = malloc(sizeof (struct sorted_dyn_array));
new_arr->array = malloc(sizeof (int) * BUFFER_INIT_SIZE);
new_arr->length = 0;
new_arr->capacity = 5;
return new_arr;
}
free memory:
void free_arr(struct sorted_dyn_array *arr) {
free(arr->buffer);
free(arr);
}
int arr_length(struct sorted_dyn_array * arr) {
return arr->length;
}
int arr_capacity(struct sorted_dyn_array *arr) {
return arr->capacity;
}
using binary search find the position for the next number:
int find_pos(int item, int arr[], int len) {
int low = 0;
int high = len-1;
if (arr[0] >= item) {
return 0;
}
if(arr[0] < item) {
return KEY_NOT_FOUND;
}
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == item) {
return mid;
} else if (arr[mid] < item) {
low = mid + 1;
} else {
high = mid - 1;
}
if(arr[high] < item) {
return high;
}
}
return KEY_NOT_FOUND;
}
int arr_find_successor(struct sorted_dyn_array *arr, int k) {
int len = arr_length(arr);
return find_pos(k,arr->buffer,len);
}
insert a number, if it is already in the list, return false. Otherwise, insert a number into the list then return true
bool arr_insert(struct sorted_dyn_array *arr, int k) {
int pos = arr_find_successor(arr,k);
if(arr_length(arr) == arr_capacity(arr)) {
arr->capacity *= 2;
arr->array = realloc(arr->buffer, sizeof(int) * arr->capacity);// realloc if the length exceed the capacity
}
if (pos == KEY_NOT_FOUND) {// If the number is greater than all the number in array,put it at the end
int l = arr->length;
arr->array[l] = k;
arr->length++;
}
if (pos != KEY_NOT_FOUND){
for (int c = arr->length - 1; c >= pos; c--)
arr->array[c+1] = array->array[c];
arr->array[pos] = k;
arr->length++;
}
return true;
}
Main function:
int main () {
struct sorted_dyn_array *myarray = arr_create();
int next = 0;
while (scanf("%d",&next) == 1) {
int next_item = next;
arr_insert(myarray, next_item);
printf("%d\n",next_item);
free_arr(myarray);
}
}
However, when I try to scanf the second number it says
int arr_length(struct sorted_dyn_array * arr) {
return arr->length;
}
invalid access memory. Can somebody help me out? I spend like a whole afternoon and still cant find where goes wrong. Thanks in advance.
arr_create()should beBUFFER_INIT_SIZE.arr[0]infind_posis undefined behavior when the array is empty.find_pos: it's a fundamental property of integers that eitherarr[0] >= itemorarr[0] < itemis true. Thewhileloop is never reached.