1

我正在尝试在二叉搜索树中插入一个节点，但遇到了一个小问题。

#include "stdafx.h"
#include <string.h>
#include <stdlib.h>


typedef struct Node{
    char name[100];
    struct Node *pGauche;
    struct Node *pDroit;
}Node;

void getName(char[]);
void copy(Node **, Node *,char[]);
void menu(Node **);
void add(Node **);
void search(char[],Node**, Node **,Node **);
void print(Node **);
void inOrder(Node *);

void main(void)
{
    Node *root = NULL;
    menu(&root);
    system("pause");
}

void menu(Node **root)
{
    for (int i=0;i<10;i++)
    {
        add(root);
    }
    print(root);
}

void add(Node **root)
{
    char name[100];
    getName(name);
    Node *p = NULL;
    Node *savep = NULL;
    search(name,root,&p,&savep);
    copy(root,savep,name);
}

void search(char name[],Node **root, Node **p, Node **savep)
{
    *p = *root;

    while ((p == NULL) && (strcmp((*p)->name,name) != 0))
    {
        *savep = *p;

        if (strcmp(name,(*p)->name) < 0)
            *p = (*p)->pGauche;
        else
            *p = (*p)->pDroit;
    }

}

void getName(char name[])
{
    printf("What name do you want to add\n");
    scanf("%s",name);
    fflush(stdin);

}

void copy(Node **root, Node *savep, char name[])
{
    Node *newp = (Node *) malloc(sizeof(Node*));
    newp->pDroit = NULL;
    newp->pGauche = NULL;

    strcpy(newp->name,name);
    printf("%s",newp->name);


    if (*root == NULL)
        *root = newp;
    else
    {
        if (strcmp(name,savep->name) < 0) 
            savep->pGauche = newp;
        else
            savep->pDroit = newp;
    }
    free(newp);
}

void print(Node ** root)
{
    Node *p = *root;
    inOrder(p);
}

void inOrder(Node *p)
{
    if (p != NULL)
    {
        inOrder(p->pGauche);
        printf("%s\n",p->name);
        inOrder(p->pDroit);
    }
}

我知道有一些非常奇怪的功能和无用的功能，但这只是一个稍微大一点的学校项目的“测试”，所以它会及时变得有用，现在我只想让二叉树工作！

所以基本上问题是我在输入第二个名字后得到一个“访问冲突读取位置”......我猜是在做strcmp时，但我真的不确定：/

如果有人可以帮助我运行它，我真的很高兴:)

4

2 回答 2

3

有几件事可以帮助您入门。我没有深入研究它，因此您可能需要继续深入研究更多问题，但修复这些问题只是为了让您开始：

在此代码中search()：

    while ((p == NULL) && (strcmp((*p)->name,name) != 0))

该p参数永远不会为 NULL。因此，永远不会进入 while 循环。这意味着它savep不会被设置为任何值，并且在您调用函数时为copy()NULL add()。然后该copy()函数取消引用无效的指针引用，这导致了您观察到的问题。

您实际上想测试是否*p为NOT NULL。这使您可以合法地取消引用它。

    while ((*p != NULL) && (strcmp((*p)->name,name) != 0))

其次，正如所hmjd确定的，您没有为内部节点分配足够的内存copy()。

    Node *newp = (Node *) malloc(sizeof(Node*));

您只为一个指针分配了足够的内存，而不是为整个节点分配了足够的内存。此外，您不应该在 C 中编码时强制转换返回值malloc()（它会隐藏在最坏情况下可能导致崩溃的错误）。

    Node *newp = malloc(sizeof(Node));

第三，您需要保留为节点分配的内存，而不是在将其插入末尾后立即释放它们copy()：

    // I need this memory for my tree!
    //free(newp);

如果您free()像以前一样调用，那么您tree将指向已释放的内存，并且访问它们会导致未定义的行为。

一件小事：您不应该这样做fflush(stdin)，因为fflush()仅适用于输出流。

于 2013-05-10T22:13:21.370 回答
3

这是不正确的：

while ((p == NULL) && (strcmp((*p)->name,name) != 0))

并将导致NULL指针被取消引用，这是未定义的行为。改成：

while (*p && strcmp((*p)->name,name) != 0)

这是不正确的：

Node *newp = (Node *) malloc(sizeof(Node*));

因为它只为 a 分配了足够的空间Node*，所以当它需要分配 a 时Node。改成：

Node *newp = malloc(sizeof(*newp));

并且不要free()在以后需要的相同功能中使用它。意味着列表具有悬空指针free()并且取消引用一个是未定义的行为，并且可能是访问冲突的原因。Node

笔记：

fflush(stdin);

是未定义的行为。从fflush()参考页面：

使输出文件流与文件的实际内容同步。如果给定的流是输入类型，那么函数的行为是未定义的。

于 2013-05-10T22:11:57.190 回答