c - C 中的字典，使用列表和 26 个头

Question

我正在尝试用 C 编写一本字典。我虽然喜欢这样:

• 制作 26 个小列表，每个列表对应一个头[第一个字母]，所以我将有头[A/a]、头[B/b] 等等...

• 打印列表。现在我正在尝试插入元素，但我不知道我在这段代码中做错了什么:

  struct g_node{//declaration of a list
     char *info; // represents the value/text
     int counterWord;
     struct g_node *next; // represents the link
  };
  
  
  
  void push_word_begining(int initial, struct g_node *heads[initial], char *word){
  
      struct g_node *new_element = malloc(sizeof(struct g_node));
  
     strcpy(new_element->info, word);//put the word in the list
     new_element->next = heads[initial]->next; 
     heads[initial]->next = new_element; // make the link
  
  }
  
  void print_words( int initial, struct g_node *heads[initial]){//prints the list
     struct g_node *iterator = heads[initial];
  
     printf("\n List: ");
     while (iterator->next != NULL) {
             printf("%s ", iterator->next->info);
             iterator = iterator->next;
     }
  }
  
  
  int main()
  {
      int indexHeads;
  
      struct g_node *heads[26];
  
      for( indexHeads = 0; indexHeads < 26; indexHeads++){
              heads[indexHeads] = malloc(sizeof(struct g_node));
              heads[indexHeads]->next = NULL;
      }
  
      char *text = "Jim wants to be a programmer";
      char *token = strtok(text, " ");
      int initial;
  
      while( token != 0){
              initial = token[0];
              push_word_begining(initial, &heads[initial], token);
              token = strtok('\0', " ");
      }
  
      print_words(initial, &heads[initial]);
  
  
  return 0;
  }
  

Answer 1

您可以使用调试器更轻松地分析它，这直接揭示了第一个问题:

# compile:
$ gcc -O0 -g3 -std=c11 -Wall -Wextra -pedantic -osimpledict simpledict.c
$ gdb ./simpledict
GNU gdb (Debian 7.7.1+dfsg-5) 7.7.1
[...]
(gdb) r
Starting program: /mnt/storage/felix/stackoverflow/simpledict/simpledict 

Program received signal SIGSEGV, Segmentation fault.
strtok () at ../sysdeps/x86_64/strtok.S:186
186 ../sysdeps/x86_64/strtok.S: Datei oder Verzeichnis nicht gefunden.
(gdb) bt
#0  strtok () at ../sysdeps/x86_64/strtok.S:186
#1  0x000000000040073a in main () at simpledict.c:46
(gdb) 

因此，对 strtok() 的调用会导致崩溃。这是因为您为 strtok() 提供了一个指向字符串常量的指针，尽管字符串常量在 C 中属于 char * 类型，但它们是只读(并且 strtok() 尝试通过插入 0 字节来更改它所处理的字符串)。

所以，改变

char *text = "Jim wants to be a programmer";

给你一个指向字符串常量的指针

char text[] = "Jim wants to be a programmer";

这样，您就有了一个可写的 char 数组，它只是从一个字符串常量初始化。

下一个测试:

(gdb) r
Starting program: /mnt/storage/felix/stackoverflow/simpledict/simpledict 

Program received signal SIGSEGV, Segmentation fault.
__strcpy_sse2 () at ../sysdeps/x86_64/multiarch/../strcpy.S:135
135 ../sysdeps/x86_64/multiarch/../strcpy.S: Datei oder Verzeichnis nicht gefunden.
(gdb) bt
#0  __strcpy_sse2 () at ../sysdeps/x86_64/multiarch/../strcpy.S:135
#1  0x000000000040061d in push_word_begining (initial=74, 
    heads=0x7fffffffe040, word=0x7fffffffddd0 "Jim") at simpledict.c:17
#2  0x00000000004007b2 in main () at simpledict.c:51
(gdb) up
#1  0x000000000040061d in push_word_begining (initial=74, 
    heads=0x7fffffffe040, word=0x7fffffffddd0 "Jim") at simpledict.c:17
17     strcpy(new_element->info, word);//put the word in the list
(gdb) p *new_element
$1 = {
  info = 0x0, 
  counterWord = 0, 
  next = 0x0
}
(gdb) 

正如你在这里看到的，new_element->info是0(或者:NULL)，一个无效的指针，你仍然尝试在那里复制一些数据。

您首先必须为您的内容分配内存:

struct g_node *new_element = malloc(sizeof(struct g_node));

new_element->info = malloc(strlen(word) + 1);// allocate memory
strcpy(new_element->info, word);//put the word in the list
new_element->next = heads[initial]->next; 
heads[initial]->next = new_element; // make the link

下一次测试，下一次崩溃:

(gdb) r
Starting program: /mnt/storage/felix/stackoverflow/simpledict/simpledict 

Program received signal SIGSEGV, Segmentation fault.
0x0000000000400696 in push_word_begining (initial=74, heads=0x7fffffffe040, 
    word=0x7fffffffddd0 "Jim") at simpledict.c:19
19     new_element->next = heads[initial]->next; 
(gdb) p *heads
$1 = (struct g_node *) 0x7fffffffe46f
(gdb) p **heads
$2 = {
  info = 0x732f746e6d2f3d5f <error: Cannot access memory at address 0x732f746e6d2f3d5f>, 
  counterWord = 1634889588, 
  next = 0x6174732f78696c65
}
(gdb) 

这里有些地方非常不对。您的 initial 参数是 74(我认为它应该在 0 和 25 之间？)，并且您的 *heads 指向一些垃圾位置，远在你的数组之外。

好吧，我可以看到错误:

        initial = token[0];
        push_word_begining(initial, &heads[initial], token);

token[0] 将是您第一个字符的 ascii 值，这绝对不是您想要的。

添加一些代码来实际计算正确的数组索引

        initial = token[0];
        if (initial >= 'a' && initial <= 'z') initial -= 'a';
        else if (initial >= 'A' && initial <= 'Z') initial -= 'A';
        else break; // not a letter, can't store this in your scheme
        push_word_begining(initial, &heads[initial], token);

它仍然在崩溃，我跳过了 gdb 输出，因为它不是那么明显。首先让我们“清理”你的函数原型(prototype)。而不是

void push_word_begining(int initial, struct g_node *heads[initial], char *word)

(原型(prototype)中的“初始”索引器没有任何意义)，只写:

void push_word_begining(int initial, struct g_node **heads, char *word)

这种形式明确表示您将获得一个指向一个指针的指针

您调用此函数

push_word_begining(initial, &heads[initial], token);

因此，您已经将指针传递给单个数组成员。不过，在这个函数中，你有这样的代码

new_element->next = heads[initial]->next;
heads[initial]->next = new_element; // make the link

再次应用索引。这没有多大意义，在这种情况下，这些索引只会加起来。像这样修复它:

new_element->next = (*heads)->next;
(*heads)->next = new_element; // make the link

突然间您发现您甚至不需要您的初始参数!

同样的错误出现在您的 print_words() 函数中。改变

struct g_node *iterator = heads[initial];

到

struct g_node *iterator = *heads;

现在，您的程序不会再崩溃了。仍然只打印

List: programmer

因为您只将最后写入的列表传递给它。

试试这个:

for (indexHeads = 0; indexHeads < 26; ++indexHeads)
{
    print_words(&heads[indexHeads]);
}
puts(""); // newline at the end

现在输出看起来像这样:

List: a
List: be
List:
List:
List:
List:
List:
List:
List:
List: Jim
List:
List:
List:
List:
List:
List: programmer
List:
List:
List:
List: to
List:
List:
List: wants
List:
List:
List:

作为引用，下面是已应用修复的代码:

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

struct g_node{//declaration of a list
   char *info; // represents the value/text
   int counterWord;
   struct g_node *next; // represents the link
};



void push_word_begining(struct g_node **heads, char *word){

    struct g_node *new_element = malloc(sizeof(struct g_node));

    new_element->info = malloc(strlen(word) + 1);// allocate memory    
   strcpy(new_element->info, word);//put the word in the list
   new_element->next = (*heads)->next; 
   (*heads)->next = new_element; // make the link

}

void print_words(struct g_node **heads){//prints the list
   struct g_node *iterator = *heads;

   printf("\n List: ");
   while (iterator->next != NULL) {
           printf("%s ", iterator->next->info);
           iterator = iterator->next;
   }
}


int main()
{
    int indexHeads;

    struct g_node *heads[26];

    for( indexHeads = 0; indexHeads < 26; indexHeads++){
            heads[indexHeads] = malloc(sizeof(struct g_node));
            heads[indexHeads]->next = NULL;
    }

    char text[] = "Jim wants to be a programmer";
    char *token = strtok(text, " ");
    int initial;

    while( token != 0){
            initial = token[0];
            initial = token[0];
            if (initial >= 'a' && initial <= 'z') initial -= 'a';
            else if (initial >= 'A' && initial <= 'Z') initial -= 'A';
            else break; // not a letter, can't store this in your scheme
            push_word_begining(&heads[initial], token);
            token = strtok(0, " ");
    }

    for (indexHeads = 0; indexHeads < 26; ++indexHeads)
    {
        print_words(&heads[indexHeads]);
    }
    puts("");


return 0;
}

还有很多事情要做，例如测试多个具有相同首字母的单词，完成后释放内存等。

并且，尝试学习如何使用调试器，它会对你有很大帮助。