合并排序一个结构 [英] Merge sorting a struct
问题描述
＃包括LT＆;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;
typedef结构{点
浮动轴[2];
INT ID;
}分;的typedef枚举{
SortById，
SortByXAxis
} SortType;分* fill_Array（字符*文件名，INT *长）;
无效Print_set（点*集，诠释NUMBER_OF_POINTS）;
无效归并排序（点*集，INT低，诠释高，INT NUMBER_OF_POINTS，SortType排序）;
无效的合并（点*集，INT低，诠释中间，诠释高，诠释NUMBER_OF_POINTS，SortType排序）;INT主（INT ARGC，CHAR *的argv []）
{
INT长;
分*阵列;
阵列= fill_Array（的argv [1]，＆安培;长度）;
Print_set（数组长度）;
的printf（\\ n \\ n）;
归并排序（数组，0，长度，长度，SortById）;
Print_set（数组长度）;
返回0;
}
分* fill_Array（字符*文件名，INT *长）
{
INT I;
分*阵列;
FILE *文件=的fopen（文件名，R）; 如果（文件== NULL）
{
返回NULL;
} 的fscanf（文件％D，长度）;
阵列=的malloc（sizeof运算（点）*长）; 对于（i = 0; I＆LT; *长度;我+ +）
{
的fscanf（文件，％D％F％F，及（阵列+ I） - 和SEQ ID，及（阵列+ I） - ＆GT;轴[0]，及（阵列+ I） - ＆GT;轴[1]）;
}
FCLOSE（文件）; 返回数组;
}无效Print_set（点*集，诠释NUMBER_OF_POINTS）
{
INT I; 对于（i = 0; I＆LT; NUMBER_OF_POINTS;我++）
{
的printf（％d个％F％F \\ N（集+ I） - GT; ID（套+ I） - GT;轴[0]，（套+ I） - GT;轴[1]）;
}
}无效归并排序（点*集，INT低，诠释高，INT NUMBER_OF_POINTS，SortType排序）
{
INT MID1; 如果（（高至低）＆GT; = 1）
{
MID1 =（低+高）/ 2; 归并排序（集，低，MID1，NUMBER_OF_POINTS，排序）;
归并排序（集，MID1 + 1，高，NUMBER_OF_POINTS，排序）;
合并（套，低，MID1，高，NUMBER_OF_POINTS，排序）; }}
无效的合并（点*集，INT低，诠释中间，诠释高，诠释NUMBER_OF_POINTS，SortType排序）
{
INT leftIndex =低;
INT rightIndex =中间;
INT combinedIndex =低;
点tempArray [NUMBER_OF_POINTS]
INT I; 而（leftIndex＆LT; =中间＆放大器;＆安培; rightIndex＆LT; =高）
{
如果（设置[leftIndex] .ID＆LT; =设置[rightIndex] .ID）
{
tempArray [combinedIndex ++] =设置[leftIndex ++];
}
其他
tempArray [combinedIndex ++] =设置[rightIndex ++];
} 如果（leftIndex ==中间+ 1）的
{
而（rightIndex＆LT; =高）
{
tempArray [combinedIndex ++] =设置[rightIndex ++];
}
}
其他
{
而（leftIndex＆LT; =中）
{
tempArray [combinedIndex ++] =设置[leftIndex ++];
}
} 对于（i =低; I＆LT;高;我++）
{
设置[I] = tempArray [I]
}
}
我想使用自定义的合并排序功能的输入文件执行合并排序。合并排序功能，但没有工作，并打印出楼下，首块被打印出来，以确保的fscanf是一切正确读，第二个是打印合并功能运行后的实际输入文件。该功能是复制一些值，并且也不排序他们，我找不到在code中的错误。请注意，枚举将被用来无论是IDS还是第一个浮点值，我只是试图让合并排序之前，我用它来无论是IDS还是那些值排序工作排序。
1 13.000000 7.000000
13 14.000000 6.000000
95 7.000000 13.000000
39 0.000000 20.000000
78 10.000000 10.000000
68 3.000000 17.000000
32 6.000000 14.000000
10 19.000000 1.000000
0 18.000000 2.000000
45 17.000000 3.000000
92 4.000000 16.000000
29 5.000000 15.000000
85 8.000000 12.000000
79 15.000000 5.000000
12 16.000000 4.000000
32 1.000000 19.000000
77 9.000000 11.000000
52 12.000000 8.000000
80 11.000000 9.000000
31 2.000000 18.000000
1 13.000000 7.000000
13 14.000000 6.000000
68 3.000000 17.000000
0 18.000000 2.000000
10 19.000000 1.000000
0 18.000000 2.000000
0 18.000000 2.000000
92 4.000000 16.000000
92 4.000000 16.000000
29 5.000000 15.000000
32 1.000000 19.000000
52 12.000000 8.000000
77 9.000000 11.000000
79 15.000000 5.000000
12 16.000000 4.000000
32 1.000000 19.000000
32 1.000000 19.000000
80 11.000000 9.000000
95 7.000000 13.000000
95 7.000000 13.000000
您似乎已经变得混淆了你的边界指数的意义。考虑功能的初始调用归并（）：
归并（数组，0，长度，长度，SortById）;
您传递的参数相同的值高和 NUMBER_OF_POINTS ，这是好的，但它意味着高重新presents一个的独家的上界的排序范围的指数。在归并（）的实施，但是，似乎面向的参数高重新present一个的包容的约束。
这种混乱继续与你的合并（）的功能，这可能是罪魁祸首这里。通过采取传递的中间值作为右子阵列的开始索引，似乎在期待的中点为的独家的上限左子阵列的，但目前的归并排序（）实施传递一个的包括的上限。在另一方面，一些由执行索引比较合并（）是适当仅中是包括的上限，该子数组。
总之，你有一个懵懵懂懂。该算法的基本轮廓看起来不错，但你需要确定（并记录自己），你的函数的参数重新present，并协调与您的实现细节。如果我是你，我会采取半开放再presentation所有的时间间隔，使下界总是包容，和上界总是排斥。除其他事项外，具有的优点是每个中点值可以同样正确PTED作为（不包括）之间$ P $上限其子阵列的左半的或作为（含）下界右半
#include<stdio.h>
#include<stdlib.h>
typedef struct points{
float axis[2];
int id;
}Points;
typedef enum{
SortById,
SortByXAxis
}SortType;
Points* fill_Array(char* filename, int* length);
void Print_set(Points* set, int number_of_points);
void mergesort(Points* set, int low, int high, int number_of_points,SortType sort);
void merge(Points* set, int low, int middle, int high, int number_of_points,SortType sort);
int main(int argc, char* argv[])
{
int length;
Points *array;
array=fill_Array(argv[1],&length);
Print_set(array,length);
printf("\n\n");
mergesort(array,0,length,length,SortById);
Print_set(array,length);
return 0;
}
Points* fill_Array(char* filename,int* length)
{
int i;
Points* array;
FILE* file=fopen(filename,"r");
if(file == NULL)
{
return NULL;
}
fscanf(file,"%d",length);
array=malloc(sizeof(Points)* *length);
for(i = 0; i < *length; i++)
{
fscanf(file,"%d %f %f", &(array+i)->id,&(array+i)->axis[0],&(array+i)->axis[1]);
}
fclose(file);
return array;
}
void Print_set(Points *set, int number_of_points)
{
int i;
for(i = 0; i < number_of_points; i++)
{
printf("%d %f %f\n",(set+i)->id,(set+i)->axis[0],(set+i)->axis[1]);
}
}
void mergesort(Points* set,int low,int high,int number_of_points, SortType sort)
{
int mid1;
if((high-low)>=1)
{
mid1 = (low+high)/2;
mergesort(set, low, mid1, number_of_points, sort);
mergesort(set, mid1+1, high, number_of_points, sort);
merge(set, low, mid1, high, number_of_points, sort);
}
}
void merge(Points* set, int low, int middle, int high, int number_of_points, SortType sort)
{
int leftIndex=low;
int rightIndex=middle;
int combinedIndex = low;
Points tempArray[number_of_points];
int i;
while(leftIndex <= middle && rightIndex<= high)
{
if(set[leftIndex].id <= set[rightIndex].id)
{
tempArray[combinedIndex++] = set[leftIndex++];
}
else
tempArray[combinedIndex++] = set[rightIndex++];
}
if(leftIndex == middle+1)
{
while(rightIndex <= high)
{
tempArray[combinedIndex++] = set[rightIndex++];
}
}
else
{
while(leftIndex <= middle)
{
tempArray[combinedIndex++] = set[leftIndex++];
}
}
for( i = low; i < high; i++)
{
set[i] = tempArray[i];
}
}
I am trying to perform a merge sort on an input file using a custom merge sort function. The merge sort functions however are not working and print out down below, the first block being the actual input file printed out to make sure fscanf is reading in everything correctly and the second being the printing after the merge functions are run. The functions are duplicating some of the values and are not sorting them either and I cannot find the mistake in the code. Note that the enum will be used to sort either the ids or the first float values I am just trying to get the merge sort to work before I use it to sort either the ids or those values.
1 13.000000 7.000000
13 14.000000 6.000000
95 7.000000 13.000000
39 0.000000 20.000000
78 10.000000 10.000000
68 3.000000 17.000000
32 6.000000 14.000000
10 19.000000 1.000000
0 18.000000 2.000000
45 17.000000 3.000000
92 4.000000 16.000000
29 5.000000 15.000000
85 8.000000 12.000000
79 15.000000 5.000000
12 16.000000 4.000000
32 1.000000 19.000000
77 9.000000 11.000000
52 12.000000 8.000000
80 11.000000 9.000000
31 2.000000 18.000000
1 13.000000 7.000000
13 14.000000 6.000000
68 3.000000 17.000000
0 18.000000 2.000000
10 19.000000 1.000000
0 18.000000 2.000000
0 18.000000 2.000000
92 4.000000 16.000000
92 4.000000 16.000000
29 5.000000 15.000000
32 1.000000 19.000000
52 12.000000 8.000000
77 9.000000 11.000000
79 15.000000 5.000000
12 16.000000 4.000000
32 1.000000 19.000000
32 1.000000 19.000000
80 11.000000 9.000000
95 7.000000 13.000000
95 7.000000 13.000000
You appear to have gotten confused about the meaning of your boundary indices. Consider the initial call to function mergesort():
mergesort(array,0,length,length,SortById);
You pass the same value for arguments high and number_of_points, which is fine, but it implies that high represents an exclusive upper bound on the indices of the sort range. The mergesort() implementation, however, seems geared for argument high to represent an inclusive bound.
The confusion continues with your merge() function, which is probably the main culprit here. By taking the passed midpoint value as the start index of the right sub-array, it seems to be expecting the midpoint as an exclusive upper bound of the left sub-array, but the current mergesort() implementation passes an inclusive upper bound. On the other hand, some of the index comparisons performed by merge() are appropriate only if middle is an inclusive upper bound of the subarray.
In short, you have a muddle. The basic outline of the algorithm looks fine, but you need to decide (and document for yourself) what your function parameters represent, and reconcile your implementation details with that. Were I you, I would adopt half-open representation for all intervals, so that lower bounds are always inclusive, and upper bounds always exclusive. Among other things, that has the advantage that each midpoint value can be interpreted equally correctly as the (exclusive) upper bound of the left half of its subarray or as the (inclusive) lower bound of the right half.
这篇关于合并排序一个结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
