问题编写合并排序与C指针 [英] Issues writing merge sort with pointers in c
问题描述
我试图写的指针合并排序方案，并且它是靠近工作良好，但存在着在输出有一些0，而不是一些有序数组的数量的问题。
有关c您必须写一个txt文件 prova.txt ，其中有数组，线路一个号码测试$ C $。例如：
prova.txt：
4
7
2
9
1
45
87
在运行code，我期望的输出
0：1
1：2
2：4
3:7
4：9
5：45
6：87
但我得到
0：1
1：0
2：0
3：0
4：0
5：0
6：2
此外，在那里，你可以给我提高我的code什么建议吗？
的#include＆LT;＆stdio.h中GT;为int *合并（INT左[]，诠释权[]，INT N）{
为int * ordinato，I = 0，J = 0;
ordinato =的malloc（sizeof的（INT）* N）;
而（I + J＆LT; N）{
如果（左[1] - 右[J]）{
*（ordinato + I + J）=左[I]
我++;
}其他{
*（ordinato + I + J）=右[J]。
J ++;
}
}
返回ordinato;
}为int *归并为（int * daOrd，INT N）{
INT K = 0，*左，右*，* ordinato;
ordinato =的malloc（sizeof的（INT）* N）;
左= malloc的（的sizeof（int）的*（N / 2））;
右= malloc的（的sizeof（int）的*（N-（正/ 2）））;
如果（正2）{
ordinato = daOrd;
}其他{
对于（K = 0; K＆LT; N / 2; k ++）
*（左+ K）= *（daOrd + K）;
对于（K = N / 2; K＆LT; N; k ++）
*（右+ K - （N / 2））= *（daOrd + K）; 左=归并排序（左，N / 2）;
右=归并（右，N-（N / 2））;
ordinato =合并（左，右，N）;
}
返回ordinato;
}主要（）{
FILE *输入;
输入= FOPEN（prova.txt，R）;
如果的printf（Errore）（输入！）; INT TOT = 100000; //为n最大值 INT *阵列;
阵列=的malloc（sizeof的（INT）* TOT）;
INT指数之= 0;
而（！的fscanf（输入％D（阵列+指数之））= EOF）指数之++; 为int * ORD =归并（数组，指数之）; 时int k;
对于（K = 0; K＆LT;指数之; k ++）的printf（％d个：％d个\\ N，K *（ORD + K））;
残培（）;
fclose函数（输入）;
}
首先，当你忽略错误的程序只编译/链接。添加的#include＆LT;文件stdlib.h＆GT; 为的malloc ，并删除残培，因为它是没有必要在这个例子中调用。另外，你的主函数为1的隐含的返回int和2缺少的回报。
您在计划合并步骤失败 - 你不考虑当阵列中的一个先于另一个耗尽会发生什么。目前编程'只是不断的阅读和抓斗无论是背后的离开或右键阵列，这是最常见的是零。
你想要的是只比较而既不向左或向右耗尽，然后只需添加剩余价值，是这样的：
的#include＆LT;＆stdlib.h中GT;
＃包括LT＆;＆stdio.h中GT;无效合并（const int的*左，const int的*权，为int * RES，INT N）{
INT I = 0，J = 0;
而（（ⅰ＆下; N / 2）及及（J＆所述N - （N / 2）））{
如果（左[1] - 右[J]）{
RES [I + J] =左[I]
我++;
}其他{
RES [I + J] =右[J]。
J ++;
}
}
而（ⅰ＆下; N / 2）{
RES [I + J] =左[I]
我++;
}
而（J＆下; N-（正/ 2））{
RES [I + J] =右[J]。
J ++;
} 返回水库;
}无效_mergeSort（INT *值，为int *不谈，INT N）{
如果（正2）{
返回;
}
_mergeSort（值，除了中，n / 2）;
_mergeSort（值+ N / 2，除+ N / 2，N-（正/ 2））;
合并（值，值+ N / 2，抛开，N）;
的memcpy（值之外，N *的sizeof（INT））;
}无效归并为（int *价值观，诠释N）{
为int *预留=的malloc（sizeof的（INT）* N）;
_mergeSort（值，放在一边，N）;
免费（预留）;
}诠释主（）{
FILE *输入;
输入= FOPEN（prova.txt，R）;
如果（！输入）{
fprintf中（标准错误，无法打开文件）;
返回1;
} INT maximum_n = 100000;
为int *阵列=的malloc（sizeof的（INT）* maximum_n）;
诠释计数;
为（计数= 0; COUNT＆LT; maximum_n;计数++）{
如果（的fscanf（输入％D（阵列+计数））== EOF）{
打破;
}
}
归并排序（数组数）; 对于（INT K = 0; K＆LT;计数; k ++）{
的printf（％d个：％d个\\ N，K，阵[K]）;
}
返回0;
}
需要注意的是，只有一个的malloc 里面归并通话了。
I'm trying to write a merge sort program with pointers, and it is near to working good, but there is the problem that in the output there are some '0' instead of some of the numbers of the sorted array.
For testing the code you have to write a txt file prova.txt in which there is the array, one number for line. For example:
prova.txt:
4
7
2
9
1
45
87
When running the code, I expect the output
0: 1
1: 2
2: 4
3: 7
4: 9
5: 45
6: 87
but I get
0: 1
1: 0
2: 0
3: 0
4: 0
5: 0
6: 2
Moreover, are there any advice that you can give me for improving my code?
#include <stdio.h>
int *merge(int left[], int right[], int n){
int *ordinato, i=0, j=0;
ordinato = malloc(sizeof(int)*n);
while(i+j < n){
if(left[i] < right[j]){
*(ordinato+i+j) = left[i];
i++;
}else{
*(ordinato+i+j) = right[j];
j++;
}
}
return ordinato;
}
int *mergeSort(int *daOrd, int n){
int k = 0, *left, *right, *ordinato;
ordinato = malloc(sizeof(int)*n);
left = malloc(sizeof(int)*(n/2));
right = malloc(sizeof(int)*(n-(n/2)));
if (n<2){
ordinato = daOrd;
}else{
for(k=0; k<n/2; k++)
*(left + k) = *(daOrd + k);
for(k=n/2; k<n; k++)
*(right + k -(n/2)) = *(daOrd + k);
left = mergeSort(left, n/2);
right = mergeSort(right, n-(n/2));
ordinato = merge(left, right, n);
}
return ordinato;
}
main(){
FILE *input;
input = fopen("prova.txt", "r");
if(!input) printf("Errore");
int tot = 100000;//is the maximum n
int *array;
array = malloc(sizeof(int)*tot);
int indice = 0;
while(fscanf(input,"%d", (array + indice)) != EOF) indice++;
int *ord = mergeSort(array, indice);
int k;
for(k=0; k<indice; k++) printf("%d: %d \n",k, *(ord+k));
getch();
fclose(input);
}
First of all, your program only compiles/links when you ignore errors. Add #include <stdlib.h> for malloc, and remove the getch invocation as it's not needed for this example. Also, your main function is 1. implicitely returning int and 2. missing that return.
Your program fails in the merge step - you don't consider what happens when one of the arrays runs out before the other. The current progam just keeps on reading and grabs whatever is behind the left or right array, which is most often a zero.
What you want is to compare only while neither left or right is exhausted, and then just add the remaining values, like this:
#include <stdlib.h>
#include <stdio.h>
void merge(const int* left, const int* right, int* res, int n) {
int i=0, j=0;
while ((i < n/2) && (j < n - (n/2))) {
if (left[i] < right[j]) {
res[i+j] = left[i];
i++;
} else {
res[i+j] = right[j];
j++;
}
}
while (i < n/2) {
res[i+j] = left[i];
i++;
}
while (j < n-(n/2)) {
res[i+j] = right[j];
j++;
}
return res;
}
void _mergeSort(int* values, int* aside, int n) {
if (n < 2) {
return;
}
_mergeSort(values, aside, n/2);
_mergeSort(values+n/2, aside+n/2, n-(n/2));
merge(values, values + n/2, aside, n);
memcpy(values, aside, n * sizeof(int));
}
void mergeSort(int* values, int n) {
int* aside = malloc(sizeof(int) * n);
_mergeSort(values, aside, n);
free(aside);
}
int main() {
FILE *input;
input = fopen("prova.txt", "r");
if (!input) {
fprintf(stderr, "Could not open file");
return 1;
}
int maximum_n = 100000;
int *array = malloc(sizeof(int)*maximum_n);
int count;
for (count = 0;count < maximum_n;count++) {
if (fscanf(input, "%d", (array + count)) == EOF) {
break;
}
}
mergeSort(array, count);
for(int k=0; k < count; k++) {
printf("%d: %d \n", k, array[k]);
}
return 0;
}
Note that there is only one malloc call inside mergeSort now.
这篇关于问题编写合并排序与C指针的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
