Mergesort C中的字符串数组

Question

我正在尝试对从标准输入中输入的字符串数组实施合并排序，而在错误之处茫然无措。目前，我正面临细分错误。我应该如何修改我的代码？

main()
{
    char temp;
    int i = 0;
    char Strings[NUM][LEN];


    printf("Please enter %d strings, one per line:\n", NUM);
    for(i; i<25; i++){
        fgets(&Strings[i][0], LEN,stdin);
    }


    i=0;
    puts("\nHere are the strings in the order you entered:");
    for (i; i<25; i++){
        printf("%s\n",Strings[i]);
    }

    mergesort(Strings,NUM);

    i=0;
    puts("\nHere are the strings in alphabetical order");
    for (i; i<25; i++){
        printf("%s\n",Strings[i]);
    }
}

int mergesort(char list[NUM][LEN], int length) // First part
{
    mergesort_r(0, length, list);
    return 0;
}

int mergesort_r(int left, int right, char list[NUM][LEN]) // Overloaded portion
{
    if (right - left <= 1)
    {
        return 0;
    }


    int left_start  = left;
    int left_end    = (left+right)/2;
    int right_start = left_end;
    int right_end   = right;


    mergesort_r( left_start, left_end, list);

    mergesort_r( right_start, right_end, list);


    merge(list, left_start, left_end, right_start, right_end);
}

int merge(char list[NUM][LEN], int left_start, int left_end, int right_start, int      right_end)
{

    int left_length = left_end - left_start;
    int right_length = right_end - right_start;


    char *left_half[left_length];
    char *right_half[right_length];

    int r = 0;
    int l = 0;
    int i = 0;


    for (i = left_start; i < left_end; i++, l++)
    {
        strcpy(left_half[l], list[i]);
    }


    for (i = right_start; i < right_end; i++, r++)
    {
        strcpy(right_half[r], list[i]);
    }


    for ( i = left_start, r = 0, l = 0; l < left_length && r < right_length; i++)
    {
        if ( strcmp(left_half[l], right_half[r])<0 ) 
        { strcpy(list[i], left_half[l++]); }
        else { strcpy(list[i], right_half[r++]); }
    }


    for ( ; l < left_length; i++, l++) { strcpy(list[i], left_half[l]); }
    for ( ; r < right_length; i++, r++) { strcpy(list[i], right_half[r]); }
    return 0;
}

我不确定这是否是我错误地传递了数组，或者是我什至没有正确执行交换。我对此不知所措，可以使用一些建议。

Answer 1

应该是

char left_half[left_length][LEN];
char right_half[right_length][LEN];

Answer 2

#include<stdio.h>
#include<stdlib.h>
#include<string.h> //To use the string functions like strcmp and strcpy

#define MAX 10  // This is the default size of every string 

void Merge(char* arr[],int low,int mid,int high) //Merging the Array Function
{
    int nL= mid-low+1;
    int nR= high-mid;

    char** L=malloc(sizeof(char *)*nL);
    char** R=malloc(sizeof(char *)*nR);
    int i;
    for(i=0;i<nL;i++)
    {
        L[i]=malloc(sizeof(arr[low+i]));
        strcpy(L[i],arr[low+i]);
    }
    for(i=0;i<nR;i++)
    {
        R[i]=malloc(sizeof(arr[mid+i+1]));
        strcpy(R[i],arr[mid+i+1]);
    }
    int j=0,k;
    i=0;
    k=low;
    while(i<nL&&j<nR)
    {
        if(strcmp(L[i],R[j])<0)strcpy(arr[k++],L[i++]);
        else strcpy(arr[k++],R[j++]);
    }
    while(i<nL)strcpy(arr[k++],L[i++]);
    while(j<nR)strcpy(arr[k++],R[j++]);

}


void MergeSort(char* arr[],int low,int high) //Main MergeSort function
{
    if(low<high)
    {
        int mid=(low+high)/2;
        MergeSort(arr,low,mid);
        MergeSort(arr,mid+1,high);
        Merge(arr,low,mid,high);
    }
}


int main()
{
    printf("\nEnter the size of the array desired: ");
    int size;  //This is the String array size
    scanf("%d",&size);

    char** arr= malloc(sizeof(char *)* size); //Creating required string array
    printf("\nEnter the strings of the array: ");

    int i;
    for(i=0;i<size;i++)
    {
        arr[i]=malloc(sizeof(char)*MAX);
        printf("\nEnter String: ");
        scanf("%s",arr[i]);
    }
    MergeSort(arr,0,size-1);
    printf("\nThe Sorted Array is: ");
    for(i=0;i<size;i++)printf("%s ->",arr[i]);
    return 0;

}

这是针对同一问题的有效解决方案。希望能帮助到你！干杯! ：）

Answer 3

您的这种解决方案可能会因长时间输入或重复执行而导致内存错误。您需要释放分配的内存，或者首先不要动态分配它。

后者是一个更简单的选择。您可以做的是在手工查找字符串数组中最长的字符串的长度，并将其作为参数传递给合并排序和合并函数。

假设长度为LEN。

然后代替为L和R数组动态分配内存，只需将其声明为：

char L [nL] [LEN]和char R [nR] [LEN]。

这可能需要稍大的堆栈内存，但可以避免程序崩溃。