c - 字符串 C 中打印的奇怪符号

Question

我是 C 编程的新手，但我想做的是使用数组创建 BST。这是我正在使用的 header 的代码:

bst.h

#ifndef ASSIGNMENT4_BST_H
#define ASSIGNMENT4_BST_H

// ====== this is in bst.h
#include "data.h"
typedef struct {Node *tree_nodes; unsigned char *is_free; int size;} BStree_struct;
typedef BStree_struct* BStree;
BStree bstree_ini(int size);
void bstree_insert(BStree bst, Key *key, int data);
void bstree_traversal(BStree bst);
void bstree_free(BStree bst);

#endif //ASSIGNMENT4_BST_H

数据.h

#ifndef ASSIGNMENT4_DATA_H
#define ASSIGNMENT4_DATA_H

typedef struct {char *name; int id;} Key;
typedef struct {Key *key; int data;} Node;
Key *key_construct(char *in_name, int in_id);
int key_comp(Key key1, Key key2);
void print_key(Key *key);
void print_node(Node node);

#endif //ASSIGNMENT4_DATA_H

这里是我的实际源文件的代码:

bst.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "bst.h"
// Input: ’size’: size of an array
// Output: a pointer of type BStree,
// i.e. a pointer to an allocated memory of BStree_struct type
// Effect: dynamically allocate memory of type BStree_struct
// allocate memory for a Node array of size+1 for member tree_nodes
// allocate memory for an unsigned char array of size+1 for member is_free
// set all entries of is_free to 1
// set member size to ’size’;

void bstree_insert_helper (BStree, Key *, int, int);

BStree bstree_ini(int size) {
    BStree bstree = (BStree*) malloc(sizeof(BStree));
    bstree->tree_nodes = (Node*) malloc(size+1 * sizeof(Node));
    bstree->is_free = (unsigned char *) malloc (size+1 * sizeof(unsigned char));
    memset (bstree->is_free, '1', size+1);
    for (int i = 0 ; i < size; i++){
//        printf("%c", bstree->is_free[i]);
    }
    return bstree;
}

// Input: ’bst’: a binary search tree
// ’key’: a pointer to Key
// ’data’: an integer
// Effect: ’data’ with ’key’ is inserted into ’bst’
// if ’key’ is already in ’bst’, do nothing
void bstree_insert(BStree bst, Key *key, int data) {
    bstree_insert_helper(bst, key, data, 1);
}

void bstree_insert_helper (BStree bst, Key *key, int data, int index){
    if (bst->is_free[index] == '1'){
        bst->tree_nodes[index].key = key;
        bst->tree_nodes[index].data = data;
        bst->is_free[index] = '0';
    } else {
        int value = key_comp(*key, *bst->tree_nodes[index].key);
        if (value < 0){
            int newIndex = 2*index;
            if (bst->is_free[newIndex] == '1'){
                bst->tree_nodes[newIndex].key = key;
                bst->tree_nodes[newIndex].data = data;
                bst->is_free[newIndex] = '0';
            } else {
                bstree_insert_helper(bst, key, data, newIndex);
            }
        } else if (value > 0){
            int newIndex = 2*index+1;
            if (bst->is_free[newIndex] == '1'){
                bst->tree_nodes[newIndex].key = key;
                bst->tree_nodes[newIndex].data = data;
                bst->is_free[newIndex] = '0';
            } else {
                bstree_insert_helper(bst, key, data, newIndex);
            }
        } else {
            puts("Key already exists... Aborting");
        }
    }
}

int main (){
    BStree bsTree = bstree_ini(10);
    bstree_insert_helper(bsTree, key_construct("Ilya", 1), 11, 1);
    bstree_insert_helper(bsTree, key_construct("Covin", 2), 12, 1);
    bstree_insert_helper(bsTree, key_construct("adolf", 3), 13, 1);
    bstree_insert_helper(bsTree, key_construct("henlo", 4), 14, 1);
    print_node(bsTree->tree_nodes[1]);
    return 0;
}

数据.c

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


// Input: ’in_name’: a string ends with ’\0’
// ’in_id’: an integer
// Output: a pointer of type pointer to Key,
// pointing to an allocated memory containing a Key
// Effect: dynamically allocate memory to hold a Key
// set Key’s id to be in_id
// dynamically allocate memory for the Key’s name
// so that name will contain what is in ’in_name’.
// Note: may use strdup()
Key *key_construct(char *in_name, int in_id) {
    Key *key = (Key*) malloc(sizeof(Key));
    key->name = strdup(in_name);
    key->id = in_id;
    return key;
}
// Input: ’key1’ and ’key2’ are two Keys
// Output: if return value < 0, then key1 < key2,
// if return value = 0, then key1 = key2,
// if return value > 0, then key1 > key2,
// Note: use strcmp() to compare key1.name and key2.name
// if key1.name = key2.name, then compare key1.id with key2.id
int key_comp(Key key1, Key key2) {
    int value = strcmp(key1.name, key2.name);
    if (value < 0 || value > 0){
        return value;
    } else {
        if (key1.id < key2.id){
            return -1;
        }else if (key1.id > key2.id){
            return 1;
        } else {
            return 0;
        }
    }
}

// Input: ’key’: a pointer to Key
// Effect: ( key->name key->id ) is printed
void print_key(Key *key) {
    char *name = key->name;
    int id = key->id;

    printf("%s, %i", name, id);
}

// Input: ’node’: a node
// Effect: node.key is printed and then the node.data is printed
void print_node(Node node) {
    printf("%s, %d \n", node.key->name, node.data);
}

问题是，当我在 bst.c 的 main 中运行 print_node 函数时，我希望它能够正确打印数组中索引 1、2、3 和 7 的 key.name 和数据。但是，索引 1 和 3 的 key.name 未正确打印。相反，如果我使用 print_node(bsTree->tree_nodes[1])，我会得到一堆看起来像这样的乱码 - 0+@]�, 11。我感觉这与我错误地为 data.c 中的键分配内存有关，但我无法弄清楚我到底做错了什么。

Answer 1

我认为错误在这里:

(size+1 * sizeof(Node))

在 BStree bstree_ini(int size) 中:

bstree->tree_nodes = (Node*) malloc(size+1 * sizeof(Node));
bstree->is_free = (unsigned char *) malloc (size+1 * sizeof(unsigned char));
memset (bstree->is_free, '1', size+1);

* 首先执行，然后是 +(就像在正常数学中一样)，参见 operator precedence ，表达式:

size+1 * sizeof(Node)

等于:

size + (1 * sizeof(Node))

这不是你想要的!

使用正确的大括号:

malloc((size + 1) * sizeof(Node));

或者使用calloc:

calloc(sizeof(Node), size + 1);

一些友好的通知:

• 漂亮的代码!
• 请don't cast the result of malloc .
• bstree->is_free 如果是 bool 类型会更清楚。如果它是 bstree->is_used 会更清楚(对我来说)，因为我可以预期它在新对象上被初始化为零，也很容易清除它 memset (bstree->is_used, 0, ...)。您只需将 '1' 和 '0' 分配给它，我发现 bool 值对于这个缩进更清晰，bstree->us_used[obj_num] = true; 将来你可能会选择一个位容器。