分配字符指针的问题

Question

#pragma once
#define _CRT_SECURE_NO_WARNINGS

typedef struct Item
{
    char* msg;
} Item;

typedef struct TreeNode* link;
//typedef struct BSTNode* link;

struct TreeNode {
    Item msg; // the data
    link pLeft; // left subtree
    link pRight; // right subtree
};

link root;

link NEW(Item item, link left, link right);
void Delete(link p);
void BSTInit(void);
Item BSTSearch(link h, char* szSearchKey);
Item Search(char* szKey);
link BSTInsert(link h, Item item);
void Insert(Item item);
int count(link h);
int height(link h);
void BSTPrint(link h);\

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



static link head;
static Item NullItem = { NULL };


link NEW(Item item, link left, link right) {
    link pNew = (link)malloc(sizeof(*pNew));
    pNew->msg.msg = (char*)malloc(strlen(item.msg) + 1);
    strcpy(pNew->msg.msg, item.msg);
    pNew->pLeft = left;
    pNew->pRight = right;
    return(pNew);
}

void Delete(link p) {
    if (p == NULL) 
        return;
    Delete(p->pLeft); // recursively free left subtree
    Delete(p->pRight); // recursively free right subtree
    free(p); // free current node
}

void BSTInit(void) {
    head = NEW(NullItem, NULL, NULL); // initializing empty tree
}

Item BSTSearch(link h, char* szSearchKey) {
    int rc;
    if (h == NULL) return(NullItem); // Got to end & not found
    rc = strcmp(szSearchKey, h->msg.msg);
    if (rc == 0) return(h->msg);// Found it
    if (rc < 0) return(BSTSearch(h->pLeft, szSearchKey));
    else return(BSTSearch(h->pRight, szSearchKey));
}

Item Search(char* szKey) 
{ 
    return(BSTSearch(head, szKey)); 
}

link BSTInsert(link h, Item item) {
    int rc;
    if (h == NULL) return(NEW(item, NULL, NULL)); // insert pt
    rc = strcmp(item.msg, h->msg.msg); // Go left or right? // issue with this line
    if (rc < 0) {
        h->pLeft = BSTInsert(h->pLeft, item);
    }
    else {
        h->pRight = BSTInsert(h->pRight, item);
    }
    return(h); // pointer to (new/existing) child
}

void Insert(Item item)
{
    head = BSTInsert(head, item);
}


int count(link h) {
    if (h == NULL) return(0);
    return(count(h->pLeft) + count(h->pRight) + 1);
}

int height(link h) {
    int iLeftH, iRightH;
    if (h == NULL) 
        return(-1);
    iLeftH = height(h->pLeft);
    iRightH = height(h->pRight);
    if (iLeftH > iRightH) {
        return(iLeftH + 1);
    }
    else {
        return(iRightH + 1);
    }
}

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#include"Tree.h"
#include"RandomChar.h"



int main()
{
    srand((unsigned)time(NULL));
    int rand_num = rand() % (20 + 1 - 11) + 11;  // random amount of times letters generated
   
    BSTInit();


    for (int i = 0; i < rand_num; i++)
    {
        char newChar = RandomChar();
        Item newItem;
        newItem.msg = malloc(sizeof(char) * 2);  // allocate memory for the character and the null terminator
        strcpy(newItem.msg, &newChar);  // copy the character to the allocated memory
        Insert(newItem);
    }

    printf("Printing tree in alphabetical order...\n");
    BSTPrint(root);
    Delete(root);

    return 0;
}

NEW 函数有问题，因为 char 没有分配并返回 NULL。我正在使用存储随机生成的字符的每个节点搜索二叉树。使用 strcmp 调整顺序将此 char 插入到树中。比我必须按那个顺序打印树。代码未编译并收到返回 NULL 的错误 pNew，但我正在使用 strcpy 来确保这不会发生。

Answer 1

函数内的这条语句

BSTInit

head = NEW(NullItem, NULL, NULL);

调用未定义的行为。

变量

NullItem

声明为

static Item NullItem = { NULL };

就是它的数据成员

msg

是一个空指针。

所以在函数

NEW

中，在字符串函数

strlen

和

strcpy

的调用中使用了空指针

pNew->msg.msg = (char*)malloc(strlen(item.msg) + 1);
strcpy(pNew->msg.msg, item.msg);

函数

BSTInit

是多余的，因为用静态存储持续时间声明的指针

head

已经被初始化为一个空指针，并且最初它应该是一个空指针。

而

strcpy

在

main

中的调用

char newChar = RandomChar();
//...
strcpy(newItem.msg, &newChar)

还调用未定义的行为，因为您试图复制单个字符而不跟随终止零字符

'\0'

作为字符串。

也是由于

main

中 for 循环内的内存分配

for (int i = 0; i < rand_num; i++)
{
    char newChar = RandomChar();
    Item newItem;
    newItem.msg = malloc(sizeof(char) * 2); 
    //...

程序产生大量内存泄漏。

注意将指针

head

声明为文件范围变量和函数依赖于全局变量时是个坏主意。