重新分配无效指针运行时错误
re-alloc Invalid Pointer runtime error
下面的代码合并了大小分别为 n1 和 n2 的 2 个排序数组 A 和 B。
合并输出需要存储在A.
（无需遍历整个代码）
疑问：在重新分配 A 时，出现 运行 次错误。为什么？
int* temp = (int*)realloc(A,sizeof(int)*(n1+n2));
if(temp != NULL) A = temp;
参考代码：
void putinend(int* num,int m,int n){
int i,j;
for(i=m-1,j=m+n-1;i>=0;i--)
num[j--] = num[i];
}
void merge(int* A, int n1, int* B, int n2) {
int* temp = (int*)realloc(A,sizeof(int)*(n1+n2));
if(temp != NULL) A = temp;
putinend(A,n1,n2);
int s1=n2,s2=0,i=0;
while(s1 < n1+n2 && s2 < n2){
if(A[s1] <= B[s2])
A[i++] = A[s1++];
else
A[i++] = B[s2++];
}
while(s1 < n1+n2)
A[i++] = A[s1++];
while(s2 < n2)
A[i++] = B[s2++];
printf("\n");
for(i=0;i<10;i++){
printf("%d ",A[i]);
}
}
int main() {
int *A = (int*)malloc(sizeof(int)*8);
int *B = (int*)malloc(sizeof(int)*2);
A[0]=1; A[1]=3; A[2] = 5; A[3] = 7; A[4] = 9; A[5] = 11; A[6] = 13; A[7] = 15;
B[0]=-2; B[1]=2;
int i;
merge(A,8,B,2);
printf("\n");
for(i=0;i<10;i++){
printf("%d ",A[i]);
}
return 0;
}
编辑：
我合并了下面给出的更正。
但返回的输出是
-2 1 2 3 5 7 9 11 13 15
0 3 5 7 9 11 13 15 0 17
为什么 A 在 main() 中从 merge() 返回之前和从 merge() 返回之后发生变化？
您在 堆栈 上分配的数组上调用 realloc()。 *alloc() 函数与 堆 一起使用。
来自man realloc：
Unless ptr is NULL, it must have been returned by an earlier call to
malloc(), calloc() or realloc().
替换
int A[8];
类似
int* A = malloc(8 * sizeof(int));
别忘了打电话给 free() if you need to.
这里是合并排序的算法：
注意看起来与发布的代码正在实现的完全不同。
注意：这是实现合并排序算法的递归方法
--归并排序--
合并排序基于分而治之的方法。它需要列表进行排序并将其划分
一半以创建两个未排序的列表。然后将两个未排序的列表排序并合并得到一个
排序列表。两个未排序的列表通过不断调用merge-sort算法进行排序；我们
最终得到一个已经排序的大小为 1 的列表。然后合并大小为 1 的两个列表。
算法：
这是一个分而治之的算法。其工作方式如下 –
- 将我们要排序的输入分成中间两部分。称它为左边部分
和右边部分。
示例：假设输入是 -10 32 45 -78 91 1 0 -16 那么左边的部分就是 -10 32 45 -
78 右边部分为 91 1 0 6.
- 分别对它们进行排序。注意这里sort并不是说用其他的
来排序
方法。我们递归地使用相同的函数。
- 然后合并两个排序的部分。
输入数组中元素的总数 (number_of_elements)。输入
数组（数组[number_of_elements]）。然后调用函数MergeSort()对输入数组进行排序。
MergeSort() 函数在 [left,right] 范围内对数组进行排序，即从左索引到右索引
包容。 Merge() 函数合并两个排序的部分。排序的部分将来自 [left, mid] 和
[中+1，右]。合并输出排序后的数组。
MergeSort() 函数：
它以数组、数组的最左边和最右边的索引作为参数。
数组的中间索引(mid)计算为(left + right)/2。检查是否（左
只有在离开时才需要排序
通过在左侧部分 MergeSort(array,left,mid) 和右侧再次调用 MergeSort() 函数
部分通过递归调用 MergeSort 函数作为 MergeSort(array,mid + 1, right)。最后合并
使用 Merge 函数的两个数组。
合并（）函数：
将要合并的数组、最左、中、最右索引取为
参数。需要一个临时数组（tempArray[right-left+1]）来存储新排序的部分。
临时数组的当前索引位置(pos)初始化为0.左边索引位置
(lpos) 被初始化为数组的左右索引位置 (rpos) 被初始化为 mid+1, of the array.
直到 lpos < 中和 rpos < 右
if(array[lpos] < array[rpos]), 即数组在lpos位置的值小于
的值
array 在位置 rpos，然后将 array[lpos]（数组左侧索引处的值）存储在 current
临时数组的索引位置(pos)，递增位置索引(pos)和left
1 的位置索引 (lpos)。tempArray[pos++] = array[lpos++]
否则，将数组[rpos]（数组右侧索引处的值）存储在
的当前索引位置（pos）
临时数组并增加位置索引（pos）和正确位置索引（rpos）
通过 1.tempArray[pos++] = array[rpos++]
Until (lpos <= mid) 即数组左边的元素被保留
tempArray[pos++] = array[lpos++],store array[lpos]（数组左边索引处的值）在
临时数组的当前索引位置（pos）并递增位置索引（pos）
并将位置索引 (lpos) 左移 1。
Until (rpos <= right) 即数组右边的元素是左边的
tempArray[pos++] = array[rpos++],store array[rpos] (数组右边索引处的值)在
临时数组的当前索引位置（pos）并递增位置索引（pos）
右位索引 (rpos) 加 1。
最后将排序后的数组复制回原数组
属性:
最佳情况——当数组已经排序 O(nlogn).
最坏情况——当数组倒序排序时 O(nlogn).
平均情况 – O(nlogn).
需要额外的 space，因此 space 数组的复杂度为 O(n)，链接的复杂度为 O(logn)
列表。
#include<stdio.h>
/*This is called Forward declaration of function */
void Merge(int * , int , int , int );
/* Logic: This is divide and conquer algorithm. This works as follows.
(1) Divide the input which we have to sort into two parts in the middle. Call it the left part
and right part.
Example: Say the input is -10 32 45 -78 91 1 0 -16 then the left part will be
-10 32 45 -78 and the right part will be 91 1 0 6.
(2) Sort Each of them seperately. Note that here sort does not mean to sort it using some other
method. We already wrote fucntion to sort it. Use the same.
(3) Then merge the two sorted parts.
*/
/*This function Sorts the array in the range [left,right].That is from index left to index right inclusive
*/
void MergeSort(int *array, int left, int right)
{
int mid = (left+right)/2;
/* We have to sort only when left<right because when left=right it is anyhow sorted*/
if(left<right)
{
/* Sort the left part */
MergeSort(array,left,mid);
/* Sort the right part */
MergeSort(array,mid+1,right);
/* Merge the two sorted parts */
Merge(array,left,mid,right);
}
}
/* Merge functions merges the two sorted parts. Sorted parts will be from [left, mid] and [mid+1, right].
*/
void Merge(int *array, int left, int mid, int right)
{
/*We need a Temporary array to store the new sorted part*/
int tempArray[right-left+1];
int pos=0,lpos = left,rpos = mid + 1;
while(lpos <= mid && rpos <= right)
{
if(array[lpos] < array[rpos])
{
tempArray[pos++] = array[lpos++];
}
else
{
tempArray[pos++] = array[rpos++];
}
}
while(lpos <= mid) tempArray[pos++] = array[lpos++];
while(rpos <= right)tempArray[pos++] = array[rpos++];
int iter;
/* Copy back the sorted array to the original array */
for(iter = 0;iter < pos; iter++)
{
array[iter+left] = tempArray[iter];
}
return;
}
int main()
{
int number_of_elements;
scanf("%d",&number_of_elements);
int array[number_of_elements];
int iter;
for(iter = 0;iter < number_of_elements;iter++)
{
scanf("%d",&array[iter]);
}
/* Calling this functions sorts the array */
MergeSort(array,0,number_of_elements-1);
for(iter = 0;iter < number_of_elements;iter++)
{
printf("%d ",array[iter]);
}
printf("\n");
return 0;
}
下面的代码合并了大小分别为 n1 和 n2 的 2 个排序数组 A 和 B。
合并输出需要存储在A.
（无需遍历整个代码）
疑问：在重新分配 A 时，出现 运行 次错误。为什么？
int* temp = (int*)realloc(A,sizeof(int)*(n1+n2));
if(temp != NULL) A = temp;
参考代码：
void putinend(int* num,int m,int n){
int i,j;
for(i=m-1,j=m+n-1;i>=0;i--)
num[j--] = num[i];
}
void merge(int* A, int n1, int* B, int n2) {
int* temp = (int*)realloc(A,sizeof(int)*(n1+n2));
if(temp != NULL) A = temp;
putinend(A,n1,n2);
int s1=n2,s2=0,i=0;
while(s1 < n1+n2 && s2 < n2){
if(A[s1] <= B[s2])
A[i++] = A[s1++];
else
A[i++] = B[s2++];
}
while(s1 < n1+n2)
A[i++] = A[s1++];
while(s2 < n2)
A[i++] = B[s2++];
printf("\n");
for(i=0;i<10;i++){
printf("%d ",A[i]);
}
}
int main() {
int *A = (int*)malloc(sizeof(int)*8);
int *B = (int*)malloc(sizeof(int)*2);
A[0]=1; A[1]=3; A[2] = 5; A[3] = 7; A[4] = 9; A[5] = 11; A[6] = 13; A[7] = 15;
B[0]=-2; B[1]=2;
int i;
merge(A,8,B,2);
printf("\n");
for(i=0;i<10;i++){
printf("%d ",A[i]);
}
return 0;
}
编辑： 我合并了下面给出的更正。 但返回的输出是
-2 1 2 3 5 7 9 11 13 15
0 3 5 7 9 11 13 15 0 17
为什么 A 在 main() 中从 merge() 返回之前和从 merge() 返回之后发生变化？
您在 堆栈 上分配的数组上调用 realloc()。 *alloc() 函数与 堆 一起使用。
来自man realloc：
Unless ptr is NULL, it must have been returned by an earlier call to malloc(), calloc() or realloc().
替换
int A[8];
类似
int* A = malloc(8 * sizeof(int));
别忘了打电话给 free() if you need to.
这里是合并排序的算法：
注意看起来与发布的代码正在实现的完全不同。
注意：这是实现合并排序算法的递归方法
--归并排序--
合并排序基于分而治之的方法。它需要列表进行排序并将其划分
一半以创建两个未排序的列表。然后将两个未排序的列表排序并合并得到一个
排序列表。两个未排序的列表通过不断调用merge-sort算法进行排序；我们
最终得到一个已经排序的大小为 1 的列表。然后合并大小为 1 的两个列表。
算法：
这是一个分而治之的算法。其工作方式如下 –
- 将我们要排序的输入分成中间两部分。称它为左边部分
和右边部分。
示例：假设输入是 -10 32 45 -78 91 1 0 -16 那么左边的部分就是 -10 32 45 -
78 右边部分为 91 1 0 6.
- 分别对它们进行排序。注意这里sort并不是说用其他的 来排序
方法。我们递归地使用相同的函数。
- 然后合并两个排序的部分。
输入数组中元素的总数 (number_of_elements)。输入
数组（数组[number_of_elements]）。然后调用函数MergeSort()对输入数组进行排序。
MergeSort() 函数在 [left,right] 范围内对数组进行排序，即从左索引到右索引
包容。 Merge() 函数合并两个排序的部分。排序的部分将来自 [left, mid] 和
[中+1，右]。合并输出排序后的数组。
MergeSort() 函数：
它以数组、数组的最左边和最右边的索引作为参数。
数组的中间索引(mid)计算为(left + right)/2。检查是否（左
只有在离开时才需要排序
通过在左侧部分 MergeSort(array,left,mid) 和右侧再次调用 MergeSort() 函数
部分通过递归调用 MergeSort 函数作为 MergeSort(array,mid + 1, right)。最后合并
使用 Merge 函数的两个数组。
合并（）函数：
将要合并的数组、最左、中、最右索引取为
参数。需要一个临时数组（tempArray[right-left+1]）来存储新排序的部分。
临时数组的当前索引位置(pos)初始化为0.左边索引位置
(lpos) 被初始化为数组的左右索引位置 (rpos) 被初始化为 mid+1, of the array.
直到 lpos < 中和 rpos < 右
if(array[lpos] < array[rpos]), 即数组在lpos位置的值小于
的值array 在位置 rpos，然后将 array[lpos]（数组左侧索引处的值）存储在 current
临时数组的索引位置(pos)，递增位置索引(pos)和left
1 的位置索引 (lpos)。tempArray[pos++] = array[lpos++]
否则，将数组[rpos]（数组右侧索引处的值）存储在
的当前索引位置（pos）临时数组并增加位置索引（pos）和正确位置索引（rpos）
通过 1.tempArray[pos++] = array[rpos++]
Until (lpos <= mid) 即数组左边的元素被保留
tempArray[pos++] = array[lpos++],store array[lpos]（数组左边索引处的值）在
临时数组的当前索引位置（pos）并递增位置索引（pos）
并将位置索引 (lpos) 左移 1。
Until (rpos <= right) 即数组右边的元素是左边的
tempArray[pos++] = array[rpos++],store array[rpos] (数组右边索引处的值)在
临时数组的当前索引位置（pos）并递增位置索引（pos）
右位索引 (rpos) 加 1。
最后将排序后的数组复制回原数组
属性:
最佳情况——当数组已经排序 O(nlogn).
最坏情况——当数组倒序排序时 O(nlogn).
平均情况 – O(nlogn).
需要额外的 space，因此 space 数组的复杂度为 O(n)，链接的复杂度为 O(logn)
列表。
#include<stdio.h>
/*This is called Forward declaration of function */
void Merge(int * , int , int , int );
/* Logic: This is divide and conquer algorithm. This works as follows.
(1) Divide the input which we have to sort into two parts in the middle. Call it the left part
and right part.
Example: Say the input is -10 32 45 -78 91 1 0 -16 then the left part will be
-10 32 45 -78 and the right part will be 91 1 0 6.
(2) Sort Each of them seperately. Note that here sort does not mean to sort it using some other
method. We already wrote fucntion to sort it. Use the same.
(3) Then merge the two sorted parts.
*/
/*This function Sorts the array in the range [left,right].That is from index left to index right inclusive
*/
void MergeSort(int *array, int left, int right)
{
int mid = (left+right)/2;
/* We have to sort only when left<right because when left=right it is anyhow sorted*/
if(left<right)
{
/* Sort the left part */
MergeSort(array,left,mid);
/* Sort the right part */
MergeSort(array,mid+1,right);
/* Merge the two sorted parts */
Merge(array,left,mid,right);
}
}
/* Merge functions merges the two sorted parts. Sorted parts will be from [left, mid] and [mid+1, right].
*/
void Merge(int *array, int left, int mid, int right)
{
/*We need a Temporary array to store the new sorted part*/
int tempArray[right-left+1];
int pos=0,lpos = left,rpos = mid + 1;
while(lpos <= mid && rpos <= right)
{
if(array[lpos] < array[rpos])
{
tempArray[pos++] = array[lpos++];
}
else
{
tempArray[pos++] = array[rpos++];
}
}
while(lpos <= mid) tempArray[pos++] = array[lpos++];
while(rpos <= right)tempArray[pos++] = array[rpos++];
int iter;
/* Copy back the sorted array to the original array */
for(iter = 0;iter < pos; iter++)
{
array[iter+left] = tempArray[iter];
}
return;
}
int main()
{
int number_of_elements;
scanf("%d",&number_of_elements);
int array[number_of_elements];
int iter;
for(iter = 0;iter < number_of_elements;iter++)
{
scanf("%d",&array[iter]);
}
/* Calling this functions sorts the array */
MergeSort(array,0,number_of_elements-1);
for(iter = 0;iter < number_of_elements;iter++)
{
printf("%d ",array[iter]);
}
printf("\n");
return 0;
}