#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。我正在搜索二叉树,每个节点都存储一个随机生成的char。这个char使用strcmp插入到树中以调整顺序。然后我必须按顺序打印树。代码没有编译并得到错误pNew返回NULL,但我使用strcpy确保不会发生这种情况。
1条答案
按热度按时间lp0sw83n1#
函数
BSTInit
中的此语句调用未定义的行为。
变量
NullItem
的声明如下也就是说,它的数据成员
msg
是一个空指针。因此,在函数
NEW
中,在调用字符串函数strlen
和strcpy
时使用了空指针函数
BSTInit
是冗余的,因为用静态存储持续时间声明的指针head
已经被初始化为空指针,并且最初它应该是空指针。在
main
中调用strcpy
也会调用undefined行为,因为您试图复制单个字符,而不将终止零字符
'\0'
作为字符串。同样由于
main
中for循环内的内存分配该程序产生大量内存泄漏。
请注意,当函数依赖于全局变量时,将指针
head
声明为文件范围变量是一个坏主意。