在c中对动态数组进行排序
发布时间:2020-12-16 07:05:16 所属栏目:百科 来源:网络整理
导读:我正在尝试创建一个函数,以便使用“malloc”和“realloc”创建升序列表. 这是结构: struct sorted_dyn_array { int *array; int length; int capacity;}; 返回指向在堆上分配的sorted_dyn_array结构的指针 const int BUFFER_INIT_SIZE = 5;const int KEY_NO
我正在尝试创建一个函数,以便使用“malloc”和“realloc”创建升序列表.
这是结构: struct sorted_dyn_array { int *array; int length; int capacity; }; 返回指向在堆上分配的sorted_dyn_array结构的指针 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; } 免费记忆: 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; } 使用二进制搜索找到下一个数字的位置: 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); } 插入一个数字,如果它已经在列表中,则返回false.否则,在列表中插入一个数字,然后返回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; } 主功能: 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("%dn",next_item); free_arr(myarray); } } 但是,当我尝试扫描第二个数字时,它说 int arr_length(struct sorted_dyn_array * arr) { return arr->length; } 无效的访问内存.有人可以帮帮我吗?我花了整整一个下午,仍然无法找到出错的地方.提前致谢. 解决方法
在main循环结束时调用free_arr意味着第二次迭代在调用arr_length时在释放的内存上运行.
这导致了不确定的行为,但你很快就崩溃了.你在运行Windows调试版本吗? (这会将释放的内存设置为已知的“坏”值 – 0xFEEEFEEE – 以帮助您发现此类问题.) 这里的修复很简单 – 只需在循环外移动free_arr(myarray)调用即可. 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("%dn",next_item); } free_arr(myarray); } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |