我从文件读取字符作为整数并将它们转换为数组中的字符串后,尝试在mergesort算法中比较字符串。我能够打印出字符串,但是当char[]数组传递给mergesort算法时,程序在合并排序的strcmp()步骤中的merge()步骤崩溃。

我测试发现临时的char[]数组未正确初始化,所以我认为问题是我没有将原始的char[]数组“ charr”传递给mergsort函数。

我不知道该怎么做。我从网上借用了mergesort算法,该算法适用于int数组,但是将int[]数组更改为char[]数组的简单更改不起作用。

如何获得要进行排序的char[]数组正确传递并在mergesort函数中初始化?

文本文件中的排列如下所示:

aa

阿阿巴

阿巴阿

阿巴阿

巴阿

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

int main(void) {

int arr[243][6];

//This is the array that I want to store my strings
char *charr[243][6];

int c, i = 0 , j = 0;
FILE *file;
file = fopen("permutations.txt", "r");
if (file) {
    while ((c = getc(file)) != EOF) {
        // we are reading each char in the string
        //every time we hit a new line char (\n = 10)
        //advance the array one, otherwise add the
        // char
        if (c != 10) {
            arr[i][j] = c;
            j++;
        }
        else {
            arr[i][j] = c;
            sprintf(charr[i], "%d%d%d%d%d%d", arr[i][0], arr[i][1],
                arr[i][2], arr[i][3], arr[i][4]);
            i++;
            j = 0;
        }
    }
    fclose(file);
}

if (strcmp(charr[0],charr[1]) < 0)
    printf("less\n");
else
   printf("other\n");

r_mergesort(charr,0,242);

for (int k = 0; k < 243; k++) {
    printf(charr[k]);
    for (int l = 0; l < 6; l++) {
        putchar(arr[k][l]);
    }
}
return 0;
}

/*l is for left index and r is right index of the sub-array*/
void r_mergesort (char arr[], int l, int r) {
    //base case
    if (l < r) {
        //divide
        int m = (l + r) /2;
        // recursively sort halves
        r_mergesort(arr, l, m);
        r_mergesort(arr, m + 1, r);
        // merge results
        merge(arr, l, m, r);
    }
}

void merge (char arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
    //  create temp arrays
    char left[n1], right[n2];
    // copy data to temp arrays
    for (i = 0; i < n1; i++) {
        left[i] = arr[l + i];
    }
    for (j = 0; j < n2; j++)
        right[j] = arr[m + 1 + j];
    // merge the temp arrays back into arr[]
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (strcmp(left[i], right[j]) < 0) {
            arr[k] = left[i];
            i++;
        }
        else {
            arr[k] = right[j];
            j++;
        }
        k++;
    }
    //copy the remaining elements of left[]
    while (i < n1) {
        arr[k] = left[i];
        i++;
        k++;
    }
    //copy the remaining elements of right[]
    while (i < n2) {
        arr[k] = right[j];
        j++;
        k++;
    }
}

最佳答案

如果像您描述的那样,面向字符的输入(例如getc)没有问题,例如您的permutations.txt包含每行一个可能的排列,那么使用面向行的输入将简化您的读取(我怀疑这是在哪里您的大部分问题都在于此)。因此,让我们正确阅读数据文件,作为解决问题的开始。

使用面向行的输入,您的主要功能是fgetsgetline。每个都有一些优点和缺点。由于您专门处理静态声明,因此我们在下面的示例中使用fgets

对于面向行的输入,要注意的一件事是,fgets会一直读取,直到遇到newline'\n')或指定的最大字符数(负1留给nul终止符)为止。在您的情况下,这意味着,如果您声明了charr[243][7]并且每行具有6个字符(加上'\n'总共为7个字符),那么如果您不增加自己的字符数就会遇到问题字符串大小加上一个附加字符,以允许'\n'作为每一行的一部分被读取(并为nul-terminator提供空间)。

基本上将要发生的是,您将告诉fgets最多读取7个字符,这意味着它将读取您所有的排列字符6,但在行末的'\n'未被读取。您对fgets的下一次调用将仅读取'\n'。要解决整个问题,只需声明charr[243][8] = {{0}};即可完整读取每一行。

您可能会说,“这听起来并不简单”-是的,我只是想确保并给出详尽的解释,以免您最终陷入阅读不到一整行的微妙问题中。当然,由于所有面向行的输入函数都读取并包含'\n'作为其读取的一部分,因此您将需要从存储在数组中的字符串中删除换行符。在解释之后,希望该示例可使阅读的内容更加清楚:

#include <stdio.h>
#include <string.h>

#define MAXR 243
#define MAXC 8

int main (int argc, char **argv) {

    char charr[MAXR][MAXC] = {{0}};
    FILE *fp = argc > 1 ? fopen (argv[1], "r") : stdin;
    size_t i = 0;

    if (!fp) {
        fprintf (stderr, "error: file open failed '%s'\n", argv[1]);
        return 1;
    }

    while (i < MAXR && fgets (charr[i], MAXC, fp))
    {
        /* get length, strip trailing newline */
        size_t len = strlen (charr[i]);
        if (charr[i][len-1] == '\n') charr[i][len-1] = 0;

        printf (" charr[%zu] : %s\n", i, charr[i]);

        i++;
    }
    if (fp != stdin) fclose (fp);

    return 0;
}


上面的代码简单地读取并打印(带有行索引)从作为程序的第一个参数的文件(如果未提供文件名,则从stdin)读取的每个排列。仅仅是为了确认您对permutations.txt文件的读取。

编译

gcc -Wall -Wextra -O3 -o bin/readperm readperm.c


测试输入(permutations.txt)

$ cat permutations.txt
123456
234561
345612
456123


输出量

$ ./bin/readperm permutations.txt
 charr[0] : 123456
 charr[1] : 234561
 charr[2] : 345612
 charr[3] : 456123


虽然fgetsgetline是用于行输入的主要工具,但我很少建议使用scanf函数系列,但如果您的permutations.txt文件与您描述的完全相同,则在以下情况下可以非常有效地使用fscanf这个案例。通常,选择格式字符串和适当的格式说明符可以使新C程序员适应。由于fscanf不需要阅读换行符,因此可以使用char charr[243][7] = {{0}};声明,而不必担心删除包含的newline。具体来说,您可以将上面的read循环替换为:

    while (i < MAXR && fscanf (fp, " %[^\n]%*c", charr[i]) == 1)
    {
        printf (" charr[%zu] : %s\n", i, charr[i]);

        i++;
    }


请注意格式说明符" %[^\n]%*c"的选择。开头space"之间的前导'%'将跳过第一个字符之前的任何空格。用作格式说明符%[^\n]的字符大小写表达式将读取直到但不包含newline的所有字符。分配抑制%*c将读取并丢弃'\n',而不会将其包括在字符串(或fscanf返回的匹配计数)中。

请注意,您可以简单地使用" %s"格式说明符并完成您的情况下的相同读取,但这将消除对格式字符串各部分的解释,这对于理解正确使用scanf系列至关重要功能。

最后,请注意上面使用return == 1的用法。 fscanf返回成功的转换次数(根据格式说明符)。因此,只要fscanf每次被转换为字符串时,您都希望继续读取。当它无法进行正确的转换时,您的读取循环会终止(您可以将return分配给变量,并在循环体内进行检查以确认EOF与读取错误)

让我知道您整理好permutations.txt的阅读内容后,在确认已解决问题之后,我们将继续处理您遇到的所有遗留问题。

07-24 09:46
查看更多