c - 使用动态数组按字典顺序对输入进行排序

Question

我尝试编写一个从键盘读取单个符号的程序。如果它们不存在，则应将它们存储在数组中。

之后，对所有标志进行排序并打印所有已经出现的标志。

编辑:如果输入的符号已经存在，则不添加。该数组应仅包含唯一元素。

该数组以 0 的大小开始，并且在新字符到达时每次满时都应将其容量加倍。

不幸的是，它似乎无法正常工作。如果我通过调试器查看，值似乎一个接一个地存储，但一旦第二个符号到达，程序就会在 print/qsort 中崩溃。

我是不是在配置上做错了什么？

此外，如果您有其他改进此代码的建议，请告诉我。

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

void reserve_space(char **c, int *capacity);
void print_signs(char **signs, const int max_size);
int cmp(void const *lhs, void const *rhs);

// allocates factor 2 of the current capacity
void reserve_space(char **c, int *capacity) {
    char *new_c;

    if (*capacity == 0) {       // allocate the first time
        *capacity = 1;
        *c = malloc(sizeof(char) * ((*capacity)));
    } else {
        *capacity *= 2;     // double the new capacity
        new_c = realloc(*c, sizeof(char) * (*capacity));
        *c = new_c;
    }
    return;
}

void print_signs(char **signs, const int sz) {
    int i = 0;

    for (i = 0; i < sz; ++i) {
        printf("%i %c\n", *signs[i], *signs[i]);            // crash in read after array has 2 signs???
    }
    printf("\n");
}

int cmp(void const *lhs, void const *rhs) {
    char left = *((char *)lhs);
    char right = *((char *)rhs);

    if (left < right) return -1;
    if (left > right) return  1;

    return 0;  /* left == right */
}

int main() {
    int capacity = 0;       // allocated space 
    int sz = 0;             // space currently "filled" with signs
    char *signs = 0;

    char ch = 0;
    int pos = 0;

    while ((ch = getc(stdin)) != EOF) {
        int pos = 0;

        if (sz == capacity)
            reserve_space(&signs, &capacity);

        for (pos = 0; pos < sz; ++pos) {
            if (signs[pos] == ch)
                continue;   /* indicating element exists already */
        }

        if (pos == capacity - 1)    // -1 because last sign must be terminating '\0'
            reserve_space(&signs, &capacity);

        signs[pos] = ch;    //adding new sign at pos of "old" \0
        ++sz;
        ++pos;
        signs[pos] = '\0';  //adding new terminating \0

        qsort(&signs, sz - 1, sizeof(char), cmp);

        print_signs(&signs, sz);
    }
    getchar();
}

Answer 1

print_sign 中有一个错误:* 和 [] 之间的优先顺序是 *signs[i ] 被解析为 *(signs[i]) 而不是您假设的 (*signs)[i]。

这是更正后的版本:

void print_signs(char **signs, const int sz) {
    int i = 0;

    for (i = 0; i < sz; ++i) {
        printf("%i %c\n", (*signs)[i], (*signs)[i]);
    }
    printf("\n");
}

实际上没有理由将指针的地址传递给这个函数。可以简化为:

void print_signs(char *signs, const int sz) {
    int i = 0;

    for (i = 0; i < sz; ++i) {
        printf("%i %c\n", signs[i], signs[i]);
    }
    printf("\n");
}

并调用为 print_signs(signs, sz);

您的代码中还有许多其他问题:

• ch 应定义为 int。

• 查找循环中的 continue 语句没有实际意义，您应该将循环写成

  for (pos = 0; pos < sz; ++pos) {
      if (signs[pos] != ch)
          break;   /* indicating element exists already */
  }
  if (pos < sz)
      continue;
  

• 如果 main 函数

，其余部分有 1 个错误
• 比较功能也坏了。

这是更正后的版本:

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

void reserve_space(char **c, int *capacity);
void print_signs(const char *signs, int max_size);
int cmp(void const *lhs, void const *rhs);

// allocates factor 2 of the current capacity
void reserve_space(char **c, int *capacity) {
    if (*capacity == 0) {   // allocate the first time
        *capacity = 1;
        *c = malloc(sizeof(char) * ((*capacity)));
    } else {
        *capacity *= 2;     // double the new capacity
        *c = realloc(*c, sizeof(char) * (*capacity));
    }
}

void print_signs(const char *signs, int sz) {
    int i = 0;

    for (i = 0; i < sz; ++i) {
        printf("%i %c\n", signs[i], signs[i]);
    }
    printf("\n");
}

int cmp(void const *lhs, void const *rhs) {
    unsigned char left = *(const unsigned char *)lhs;
    unsigned char right = *(const unsigned char *)rhs;

    if (left < right) return -1;
    if (left > right) return  1;
    return 0;  /* left == right */
}

int main() {
    int sz = 0;             // space currently "filled" with signs
    int capacity = 0;       // allocated space 
    char *signs = NULL;
    int ch;

    while ((ch = getc(stdin)) != EOF) {
        int pos = 0;

        for (pos = 0; pos < sz; ++pos) {
            if (signs[pos] == ch)
                break;
        }
        if (pos < sz)
            continue;  // character is already in the array

        if (sz == capacity)
            reserve_space(&signs, &capacity);

        signs[sz] = ch;    // append the sign in the array
        sz++;
        // '\0' terminator is not needed as array is not used as a string
    }
    qsort(signs, sz, sizeof(char), cmp);
    print_signs(signs, sz);
    free(signs);

    getchar();
    return 0;
}