3

可能只是 C 新手的另一个愚蠢的指针问题。不过想不出来这个。似乎我的堆栈帧以某种方式损坏了。该作业似乎几乎无关紧要，但它是一个相当基本的 I/O 练习。尝试通过单次读取读取结构数组（不能使用高级 I/O 函数，例如 fread()）。

#include "A2_Phase2.h"

void read_directory(Cdir directory[], int cnt) 
{
    int fd;
    char filename[] = "RandomStructDir.bin";

    fd = open(filename, O_RDONLY, S_IRWXU);
    if (fd < 0)
        perror(strcat(filename, " failed to open."));

    if (read(fd, &(directory[0].code[0]), sizeof(Cdir) * cnt) < 0) {
        perror(strcat(filename, " could not be accessed."));
    }

    close(fd);
}

int binary_search(Cdir directory[], char *key, int l, int r) {

    int mid = (int) r / 2;

    if (strncmp(key, directory[mid].code, 3) < 0)
        return binary_search(directory, key, l, mid - 1);
    else if (strncmp(key, directory[mid].code, 3) > 0)
        return binary_search(directory, key, mid + 1, r);
    else
        return mid;
}

int main(int argc, char *argv[]) 
{
    int COUNTRY_COUNT = atoi(argv[1]);
    printf("%d", COUNTRY_COUNT);

    Cdir *directory = (Cdir *) malloc(sizeof(Cdir) * COUNTRY_COUNT);
    read_directory(directory, COUNTRY_COUNT);
    binary_search(directory, "ZWE", 0, 238);
    free(directory);
}

我通过 GDB 收到此错误：

Program received signal SIGSEGV, Segmentation fault.
0x0000000000400940 in binary_search (
    directory=<error reading variable: Cannot access memory at address 0x7fffff7feff8>, 
    key=<error reading variable: Cannot access memory at address 0x7fffff7feff0>, l=<error reading variable: Cannot access memory at address 0x7fffff7fefec>, 
    r=<error reading variable: Cannot access memory at address 0x7fffff7fefe8>)
    at A2_Phase2.c:19
19  int binary_search(Cdir directory[], char *key, int l, int r) {

谢谢！

4

4 回答 4

5 
int COUNTRY_COUNT = atoi(argv[1]);

读取国家的数量作为程序的参数，但您稍后硬编码假设这是>= 238您调用时的假设

binary_search(directory, "ZWE", 0, 238);

你能试一下吗

binary_search(directory, "ZWE", 0, COUNTRY_COUNT-1);

反而？您的函数中还有一些错误binary_search可以重写为

int binary_search(Cdir directory[], const char *key, int l, int r)
{
    int mid = (r + l) / 2;
    int cmp = strncmp(key, directory[mid].code, 3);
    if (l >= r) {
        if (cmp == 0)
            return l;
        return -1;
    }
    if (cmp < 0) 
        return binary_search(directory, key, l, mid - 1);
    else if (cmp > 0)
        return binary_search(directory, key, mid + 1, r);
    else
        return mid;
}

主要变化是

  • 计算mid考虑到l以及r
  • （正如基里连科所指出的）认识到它可能找不到匹配项。在这种情况下返回 -1
  • 减少调用次数strcmp。非常小，但它使代码对我来说更清晰，并且会提高搜索性能

不太重要的是，有一些文体问题使您的代码难以阅读

  • 函数内部大量不必要的空白
  • COUNTRY_COUNT对变量使用大写字母（例如）是不常见的。所有大写通常非正式地保留给使用小写或驼峰式的变量定义
于 2013-01-23T16:41:01.400 回答
1 
int mid = (int) r / 2;

真的吗？我想你会发现这不是中间点。此外，正如在别处指出的那样，如果未找到该值，则不存在终止情况。您需要考虑递归将如何适用于不同的输入，包括无效输入。

我会这样做：

int binary_search(Cdir directory[], char *key, int l, int r)
{
    int mid = (l+r) / 2;
    int c = strncmp(key, directory[mid].code, 3);

    if(c == 0) return mid;
    if(l>=r) return -1;

    if (c < 0)
        return binary_search(directory, key, l, mid - 1);

    return binary_search(directory, key, mid + 1, r);
}

还有这个：

char filename[] = "RandomStructDir.bin";

fd = open(filename, O_RDONLY, S_IRWXU);
if (fd < 0)
    perror(strcat(filename, " failed to open."));

filename[]是堆栈上的固定长度数组。当发生错误时，您尝试连接到它。这可能只会导致更严重的错误，因为它是未定义的行为 - 你正在破坏堆栈。

于 2013-01-23T16:53:31.873 回答
0

在您的递归函数中，如果没有匹配的元素，我看不到任何终止情况。

于 2013-01-23T16:41:39.650 回答
0

我的堆栈帧已损坏

看起来很像您声明了一个对于堆栈来说太大的变量。代替

int largeArray[1000][1000];

将其声明为指针

int *largeArray[1000][1000];

当然，代码的更改是必要的。

于 2016-06-15T08:18:24.643 回答