我正在嘗試為包含指向不同結構的指標的陣列撰寫一個通用的歸并排序。我現在編譯器沒有給出任何錯誤，但是排序函式還沒有給出正確的輸出。兩個結構體和兩個比較函式定義如下：
typedef struct Query {int day, rank;} Query;
typedef struct Event {int day, frame; char action;} Event;
int compEvents (const void *a, const void *b) {
return (*(Event**)a)->day - (*(Event**)b)->day;
}
int compQueries (const void *a, const void *b) {
return (*(Query**)a)->day - (*(Query**)b)->day;
}
如果我使用 qsort，一切正常并且輸出正確：
qsort (queries, size, sizeof(Query*), compQueries);
如果我對每種型別使用不同的合并排序，并且不使用比較函式，那么一切也都正常：
void queryMerge(Query **arr, int left, int mid, int right) {
Query **temp = newQueryArray(right-left 1);
int i = left, j = mid 1, t = 0;
while (i <= mid && j <= right) {
if (arr[i]->day < arr[j]->day) temp[t ] = arr[i ];
else temp[t ] = arr[j ];
}
while (i <= mid) temp[t ] = arr[i ];
while (j <= right) temp[t ] = arr[j ];
for (int i = left; i <= right; i ) arr[i] = temp[i-left];
free(temp);
}
void querySort(Query **arr, int left, int right) {
if (left < right) {
int mid = left (right - left)/2;
querySort(arr, left, mid);
querySort(arr, mid 1, right);
queryMerge(arr, left, mid, right);
}
}
void eventMerge(Event **arr, int left, int mid, int right) {
Event **temp = newEventArray(right-left 1);
int i = left, j = mid 1, t = 0;
while (i <= mid && j <= right) {
if (arr[i]->day < arr[j]->day) temp[t ] = arr[i ];
else temp[t ] = arr[j ];
}
while (i <= mid) temp[t ] = arr[i ];
while (j <= right) temp[t ] = arr[j ];
for (int i = left; i <= right; i ) arr[i] = temp[i-left];
free(temp);
}
void eventSort(Event **arr, int left, int right) {
if (left < right) {
int mid = left (right - left)/2;
eventSort(arr, left, mid);
eventSort(arr, mid 1, right);
eventMerge(arr, left, mid, right);
}
}
但是，如果我嘗試使用像 qsort 一樣適用于兩種型別的通用合并排序，它就無法正常作業，即使編譯器和 valgrind 沒有抱怨：
void merge(void *arr, int left, int mid, int right, int width, int (*comp)(const void*, const void*)) {
void *temp = malloc((right - left 1) * width);
int i = left, j = mid 1, t = 0;
while (i <= mid && j <= right) {
if (comp((char*)arr i*width, (char*)arr j*width)) {
memcpy((char*)temp t*width, (char*)arr i*width, width);
i ; t ;
} else {
memcpy((char*)temp t*width, (char*)arr j*width, width);
j ; t ;
}
}
while (i <= mid) {
memcpy((char*)temp t*width, (char*)arr i*width, width);
i ; t ;
}
while (j <= right) {
memcpy((char*)temp t*width, (char*)arr j*width, width);
j ; t ;
}
for (int i = left; i <= right; i ) {
memcpy((char*)arr i*width, (char*)temp (i - left)*width, width);
}
free(temp);
}
void mergeSort(void *arr, int left, int right, int width, int (*comp)(const void*, const void*)) {
if (left < right) {
int mid = left (right - left)/2;
mergeSort(arr, left, mid, width, comp);
mergeSort(arr, mid 1, right, width, comp);
merge(arr, left, mid, right, width, comp);
}
}
這是它的呼叫方式：
mergeSort(queries, 0, size-1, sizeof(Query*), compQueries);
我嘗試了不同的方法來使 void 指標正確，但我仍然不確定。有任何想法嗎？
uj5u.com熱心網友回復：
您對比較功能的使用已損壞：
if (comp((char*)arr i*width, (char*)arr j*width)))
是相同的
if (comp((char*)arr i*width, (char*)arr j*width)) != 0)
在你需要的時候
if (comp((char*)arr i*width, (char*)arr j*width)) < 0)
使用您的代碼，您將忽略哪個更大，但前提是它們相同。結果你根本不排序。
添加<0修復排序。
注意：您的特定函式使用正確的比較結果：
if (arr[i]->day < arr[j]->day)
uj5u.com熱心網友回復：
這是我的最終版本：
void merge(void *arr, int left, int mid, int right, int width, int (*comp)(const void*, const void*)) {
void *temp = safeMalloc((right - left 1) * width);
int i = left, j = mid 1, t = 0;
while (i <= mid && j <= right) {
if (comp((char*)arr i*width, (char*)arr j*width) < 0)
memcpy((char*)temp (t )*width, (char*)arr (i )*width, width);
else memcpy((char*)temp (t )*width, (char*)arr (j )*width, width);
}
memcpy((char*)temp t*width, (char*)arr i*width, (mid - i 1)*width);
memcpy((char*)temp t*width, (char*)arr j*width, (right - j 1)*width);
memcpy((char*)arr left*width, temp, (right - left 1)*width);
free(temp);
}
void mergeSort(void *arr, int left, int right, int width, int (*comp)(const void*, const void*)) {
if (left < right) {
int mid = left (right - left)/2;
mergeSort(arr, left, mid, width, comp);
mergeSort(arr, mid 1, right, width, comp);
merge(arr, left, mid, right, width, comp);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/537261.html
標籤：C指针结构体合并排序