字符串排序与归并排序

Question

我正在尝试使用归并排序算法对字符串进行排序。这是我的相关代码：

void sortCities(EXPEDITION *expedition, int expeditionNumber)
{
    int i;
    int j;
    char **tmp;
    tmp = (char**)malloc((expeditionNumber) * sizeof(char*));
    for (i = 0; i < expeditionNumber; i++) {
        tmp[i] = (char*)malloc(15 * sizeof(char));
    }
    for (i = 0, j = 0; i < expeditionNumber; i++, j++) {
        tmp[j] = expedition[i].city;
    }
    for (i = 0; i < expeditionNumber; i++) {
        printf("%s\n", tmp[i]);
    }
    mergeSort(tmp, 0, expeditionNumber);
    for (i = 0; i < expeditionNumber; i++) {
        printf("%s\n", tmp[i]);
    }
}

void mergeSort(char** array, int first, int last)
{
    int middle;
    if (first < last) {
        middle = (first + last) / 2;
        mergeSort(array, first, middle);
        mergeSort(array, middle + 1, last);
        merge(array, first, middle + 1, middle, last);
    }
}

void merge(char** array, int first1, int first2, int last1, int last2)
{
    int i;
    int j;
    int k;
    char **newArray;
    newArray = (char**)malloc((last2 - first1 + 1) * sizeof(char*));
    for (i = 0; i < last2 - first1 + 1; i++) {
        newArray[i] = (char*)malloc(15 * sizeof(char));
    }
    j = first2;
    i = first1;
    k = 0;
    while (i < last1 && j < last2) {
        if (strcmp(array[i], array[j]) > 0) {
            strcpy(newArray[k++], array[j++]);
        }
        else {
            strcpy(newArray[k++], array[i++]);
        }
    }
    if (i < last1) {
        while (i < last1) {
            strcpy(newArray[k++], array[i++]);
        }
    }
    if (j < last2) {
        while (j < last2) {
            strcpy(newArray[k++], array[j++]);
        }
    }
    for (i = first1, j = 0; i < last2; i++, j++) {
        strcpy(array[i], newArray[j]);
    }
}

问题是 tmp 返回空值给 sortCities 函数。在将它发送到 mergeSort 之前，我检查了 tmp 的内容，我看到它复制正确（来自 expedition.city）。可能是什么原因？

编辑：我通过写 "array[i] = newArray[j];" insead "strcpy(array[i], newArray[j])" 来处理这个问题。但是现在它不能正确排序。我想我应该使用“<=”而不是“<”，但这次它停止执行是因为我猜是指针数组的限制。

Answer 1

我只是使用了普通的字符矩阵 (char[][N]) 而不是指针矩阵并且它起作用了。这是我的新代码：

void merge(char array[100][15],int first1,int first2,int last1,int last2){
int i;
int j;
int k;
char **newArray;
newArray=(char **)malloc((last2-first1+1)*sizeof(char *));
for(i=0;i<last2-first1+1;i++){
    newArray[i]=(char *)malloc(15*sizeof(char));
}
j=first2; 
i=first1; 
k=0;
while(i<=last1 && j<=last2){

    if(strcmp(array[i],array[j])>0){ 
        strcpy(newArray[k++], array[j++]);
    }
    else{
        strcpy(newArray[k++], array[i++]);
    }
}

while(i<=last1){            
    strcpy(newArray[k++], array[i++]);
}

while(j<=last2){
    strcpy(newArray[k++], array[j++]);
}

for(i=first1,j=0;j<k;i++,j++){
    strcpy(array[i], newArray[j]);
}

}

void mergeSort(char array[100][15],int first,int last){ 
int middle;
if(first<last){
    middle=(first+last)/2;
    mergeSort(array,first,middle);
    mergeSort(array,middle+1,last);
    merge(array,first,middle+1,middle,last); 
}

}

void sortCities(EXPEDITION *expedition, int expeditionNumber){
int i;
int j;
char tmp[100][15];

for(i=0,j=0;i<expeditionNumber;i++,j++){
    strcpy(tmp[j],expedition[i].city);
}

mergeSort(tmp,0,expeditionNumber);
for(i=0;i<expeditionNumber;i++){
    printf("%s\n",tmp[i]);
}

}

字符串排序与归并排序

String Sort With Merge Sort

c

string

merge

mergesort