小贝子编程

c-我的程序只能使用malloc()来分配内存几次



我写了一个二进制搜索树来存储一些排序的单词。按照惯例，每次有新词出现时，我都会为二进制树分配新的内存块。但是，奇怪的是，我只能为二进制搜索树分配两次新内存，这意味着在第一次和第二次

这是我的代码：

inputWord.c

/* I pass in the firstNode, and the word I wanna store, and its quantity as argument*/
int inputWord(BSTnode* Node,char* word,int num){
    BSTnode* ptr=Node;           //ptr was defined to track the location of the node.
    while(1){
        if(stricmp(word,ptr->data)>0){
                 /*If the current node already have a rightchild then ptr move to it, and do comparison again*/
            if(ptr->rightchild!=NULL){
                ptr=ptr->rightchild;
                printf("Moving to another (right) node now!!n");
                continue;            
            }
               /*If the current node have no rightchild, then make a new one for it and store the word and its quantity*/
            else{
                ptr->rightchild=malloc(sizeof(BSTnode));
                if(!(ptr->rightchild))
                    return 1;
                ptr=ptr->rightchild;
                ptr->rightchild=NULL;
                ptr->leftchild=NULL;
                strcpy(ptr->data,word);
                ptr->num=num;
                break;
            }
        }
        else if(stricmp(word,ptr->data)<0){
                    /*it's all the same as the rightchild part*/
            if(ptr->leftchild!=NULL){
                ptr=ptr->leftchild;
                continue;
            }
            else{
                ptr->leftchild=malloc(sizeof(BSTnode));
                if(!(ptr->leftchild))
                    return 1;
                ptr=ptr->leftchild;
                ptr->leftchild=NULL;
                ptr->rightchild=NULL;
                strcpy(ptr->data,word);
                ptr->num=num;
                break;
            }
        }
            /*If the word have already been stored in the tree, print out this message*/
        else{
            fprintf(stdout,"It is exactly the same word!!n");
            return 0;
        }
    }
    return 0;
}

我在上面做了一些必要的评论，以帮助你理解我的意图。希望这会有所帮助。

正如你所看到的，这个函数非常简单明了。它确实适用于前两次调用。但当调用第三次时，它崩溃了！！（总是第三次）。

所以我做了一些测试。现在我很确定它在线路上崩溃了

ptr->leftchild=malloc(sizeof(BSTnode));

（明确firstNode的数据是用""初始化比较的。我首先输入单词"The"，第二个输入"Project"，第三个输入"Gutenberg"。BSTnode的结构是

typedef struct BSTnode{
    char data[20];
    struct BSTnode* leftchild;   
    struct BSTnode* rightchild;  
    int num;
}BSTnode;

)

下面列出了我如何进行测试。（这是相同的代码，只是有一些额外的print语句用于测试）

int inputWord(BSTnode* Node,char* word,int num){
  printf("Enter inputWord() successfully!!n");
    BSTnode* ptr=Node;
    while(1){
        if(stricmp(word,ptr->data)>0){
            if(ptr->rightchild!=NULL){
                ptr=ptr->rightchild;
                printf("Moving to another (right) node now!!n");
                continue;
            }
            else{
                printf("I need a new rightchild!!n");
                ptr->rightchild=malloc(sizeof(BSTnode));
                printf("New rightchild created successfully!!n");
                if(!(ptr->rightchild))
                    return 1;
                ptr=ptr->rightchild;
                ptr->rightchild=NULL;
                ptr->leftchild=NULL;
                printf("......In line 27 now!!n");
                strcpy(ptr->data,word);
                printf("Copied successfully!!!..In line 29 now!!n");
                ptr->num=num;
                fprintf(stdout,"New data '%s' successfully inserted into a new (right) node at %p (value of pointer)n",word,ptr);
                break;
            }
        }
        else if(stricmp(word,ptr->data)<0){
            if(ptr->leftchild!=NULL){
                ptr=ptr->leftchild;
        printf("Moving to another (left) node now!!n");
                continue;
            }
            else{
                printf("I need a new left child!!!n");
                ptr->leftchild=malloc(sizeof(BSTnode));
                printf("New leftchild created successfully!!n");
                if(!(ptr->leftchild))
                    return 1;
                ptr=ptr->leftchild;
                ptr->leftchild=NULL;
                ptr->rightchild=NULL;
                printf("......In line 47 now!!n");
                strcpy(ptr->data,word);
                printf("Copied successfully!!!..In line 51 now!!n");
                ptr->num=num;
        fprintf(stdout,"New data '%s' successfully inserted into a new (left) node at %p (value of pointer)n",word,ptr);
                break;
            }
        }
        else{
            fprintf(stdout,"Nothing else to insert!!n");
            return 0;
        }
    }
    return 0;
}

正如您所看到的，通过一些print语句告诉我去过哪里，我可以确定程序在哪里崩溃。

知道为什么它总是在第三次崩溃吗？

#######################################################################3

main.c

#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<stdbool.h>
#include "wordCount.h"
void prompt(BSTnode*,FILE*);
char arr[20]={0};
int main()
{
    BSTnode* firstNode=malloc(sizeof(BSTnode));
    firstNode->leftchild=NULL;
    firstNode->rightchild=NULL;
    strcpy(firstNode->data,"");
    firstNode->num=0;
    FILE* fs=fopen("testfile.txt","r");
    if(!fs){
        printf("Failed to open fiel!!n");
        return 2;
    }
    while(1){
        if(ferror(fs))
            perror("there is a error in fs in the beginning of while loop!n");
        prompt(firstNode,fs);
    }
        return 0;
}
void prompt(BSTnode* Node,FILE* fs){
    int i=0;     
    printf("Please selectn1.find and input a word into the binary treen2.print only one datan3.Exitn");
    if(scanf("%d",&i)!=1){
        printf("scanf failed!!nplease input a valid number!!n");
        //fflush(stdin);
        return;
    }
    getchar();
    switch(i){
        case 1:
            {
                memset(arr,'',20);        //since the "arr" is used to hold the newWord founded and returned, it should be clear first every time
                char* newWord=findWord(fs);       
                int totalNumberOfTheWord=wordCount(fs,newWord);
                inputWord(Node,newWord,totalNumberOfTheWord);                   
                break;
            }
        case 2:
            printOneNode(Node);
            break;
        case 3:
            exit(0);
        default:
            printf("Please input a valid number!(1-3)");
    }
}

此外，wordCount.h:

#ifndef WORDCOUNT_H
#define WORDCOUNT_H
#include<stdlib.h>
#include<stdio.h>

typedef struct BSTnode{
    char data[20];
    struct BSTnode* leftchild;    //if less than, put it on the left
    struct BSTnode* rightchild;   //if greater than, on the right
    int num;
}BSTnode;
int inputWord(BSTnode*,char*,int);
char* findWord(FILE*);
int wordCount(FILE*,char*);
int printOneNode(BSTnode*);

#endif

功能prompt()用于提示用户决定是否继续单词搜索。

#####################################################################3

完整源代码：

wordCount.c

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include "wordCount.h"

int wordCount(FILE* fs,char* word)
{
      int num=0;
      rewind(fs);
        size_t n1=sizeof(word);
        size_t n2=strlen(word);
    char* buff=malloc(n1) ;        
        if(buff==NULL)
            return 1;
        memset(buff,'',n1);
                /* I count the word by moving byte by byte and do comparison*/      
    if (fs != NULL) {                             
        if (n2 == fread(buff, 1,n2, fs)) {       
            do {                                   
                if (strnicmp(buff,word,n2) == 0) 
                    num++;                       
                memmove(buff, buff+1,n2-1);           
            } while (1 == fread(buff+n2-1, 1, 1, fs)); 
                                     // I think I might optimize 
                                                 // this using KMP algorithm
                }
    }
        free(buff);
        return num;
}

findWord.c

#include<string.h>
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include "wordCount.h"
extern char arr[20];
char* findWord(FILE* fs)
{
      static long pos=0;
      fseek(fs,pos,SEEK_SET);
        if(ferror(fs)){
            perror("fseek() failed!!!n");
            fprintf(stderr,"fseek() failed in file %sn",__FILE__);
            exit(EXIT_FAILURE);
        }
        char chr[1]={0};
        bool flag1=false;
        bool flag2=false;
        while((1==fread(chr,1,1,fs))&&(!(flag1==false&&flag2==true))){
                                        // This would make the findword() function
                                        // find only a single word once
            if(chr[0]!=32){
                strncat(arr,chr,1);
                flag2=true;
                flag1=true;
            }
            else
                flag1=false;
        }
  /*the key method that I use to find a new word is that I use two 'bool' flags: flag1 and flag2. 
  *Only when the "arr" is filled only with character, not a single space, will the flag1 be false and flag2 be true, thus breaking the while loop*/ 
        pos=ftell(fs)-1;  
                          //maybe everytime you use "fseek()", "ftell()", the
                                            //file-position will move one byte ahead. 
        return arr;
    }

printOneNode.c

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include"wordCount.h"
int printOneNode(BSTnode* Node){
    BSTnode* ptr=Node;
    while(1){
        printf("Select which side of node do you want to print now(l/r)?(q for quit) ");
        char a;
        getchar();       //this is used to consume the newline character left
        //fflush(stdin);
        if(scanf("%c",&a)!=1){
            printf("scanf failed!!");
            return 1;
        }
        switch(a){
            case 'l':
                {
                    if(ptr->leftchild!=NULL){
                        ptr=ptr->leftchild;
                        printf("t%sn",ptr->data);
                    }
                    else
                        printf("There is no more leftchildn");
                    break;
                }
            case 'r':
                {
                    if(ptr->rightchild!=NULL){
                        ptr=ptr->rightchild;
                        printf("t%sn",ptr->data);
                    }
                    else
                        printf("There is no more rightchild!n");
                    break;
                }
            case 'q':
                return 0;
            default:
                return 0;
        }
    }
}

函数findWord()用于查找要插入的新词。例如，如果在textfile.txt中有字符串This is a lovely place...，则findWord()将首先找出单词This，然后第二个是is，然后第三个是a，等等。（这就是为什么我将pos定义为静态变量以跟踪位置的原因。）

函数wordCount()用于计算findWord()返回的单词在testfile.txt中出现的次数。

功能printOneNode()用于根据用户意愿打印出单个节点的数据。我设计了这个函数，但还没有使用，这意味着在prompt()函数中，我总是选择"在二进制搜索树中查找并输入一个新词"）。所以这可能不是导致我的程序"偶尔"崩溃的原因。

总之，我的日常工作是：

  1. 提示用户询问是否查找并插入新词（始终为"是"）
  2. 使用findWord()在testfile.txt中查找一个新词
  3. 使用wordCount()计数
  4. 使用inputWord()将其插入二进制搜索树

重复一遍。

我不能为了让这个程序更容易理解而把它缩小，因为它必须找到一个单词并计数插入它。但在某种程度上，你可以忽略printOneNode()函数。

关于testfile.txt，我已经在评论区发布了下面的链接。感谢

edit：这是对我上一篇文章（见下文）的修改，详细介绍了在这段代码中发现的更严重的问题。

在wordCount中存在缓冲区溢出缓冲区溢出为UB。

  • 您正在为buff分配n1字节。碰巧，您知道这是多少字节吗？也许你应该检查一下，然后自己回答：你能在那个对象中存储多少字节
  • 然后尝试将n2字节读取到buff中。n1和n2哪个更大？你看了吗？如果你试图把24个鸡蛋装进一个只能装12个的纸箱里，会发生什么

我认为这里的问题是你不理解sizeof运算符；这不是一个函数。。。相反，它是一个与&address-of和-negation运算符非常相似的运算符，只是sizeof对表达式的类型进行运算（或用表达式表示）；它评估该类型对象的大小。

为了澄清，在下面的代码片段中，n1就是sizeof (char *)，这可能不是您想要的。

int wordCount(FILE* fs,char* word)
{
    int num=0;
    rewind(fs);
    size_t n1=sizeof(word);
    size_t n2=strlen(word);
    char* buff=malloc(n1);

inputWord似乎是在word指向字符串的印象下操作的，但该值似乎来自程序中的findWord，它不需要生成字符串（因为它使用strncat）更多未定义的行为！这令人惊讶吗？

上一个答案：

首先，这段代码甚至没有编译。prompt中inputWord(Node,newWord,totalNumberOfTheWord)后面缺少一个分号。也许您没有注意到错误，并且您正在运行一个过时的二进制文件，而我们没有它的源代码？

其次，即使要编译此代码，也有许多未定义行为的实例，例如：

  • 当malloc返回NULL并且您尝试修改NULL指向的对象时，会出现空指针取消引用。例如CCD_ 52之后紧接着CCD_。也许您可以这样声明firstNode：BSTnode firstNode = { 0 };，并使用&firstNode创建一个指向它的指针。。。毕竟，您确实应该选择最合适的存储持续时间，而不是每次都默认为malloc。在这一点上，我强烈建议将您的分配逻辑与数据结构逻辑分离；如果您需要进一步的阐述，请考虑scanf是如何设计的
  • fflush(stdin);。每当您第一次使用某个功能时，您应该始终仔细阅读并理解手册。。。这不仅仅是为了深入了解你应该如何设计你的功能。如果在使用fflush之前阅读并完全理解本fflush手册，则您永远不会使用此有问题的代码。考虑使用类似scanf("%*[^n]"); getchar();的东西来代替它
  • 在一些地方，您使用的是%p格式指令，该指令需要一个void *指针作为相应的参数。然而，您提供的相应参数的类型是struct BSTnode *。根据fprintf手册，"如果任何参数不是相应转换规范的正确类型，则行为是未定义的。"

即使您没有修复这些未定义的行为，当您提供伪函数来代替findWord和wordCount时，这些代码也可能会在您的系统上运行。然而，它不需要在所有系统上以相同的方式工作，这意味着对你来说，崩溃可能发生在我们没有崩溃的地方。解决这些问题。

这些问题表明，您的findWord和wordCount函数也不一定可靠和万无一失；它们可能在一种设置中为您工作，而在另一种设置下为您失败，或者更糟的是，也许它们也过时了！您应该通过在它们的位置提供伪函数来验证问题所在。毕竟，这是创建MCVE过程的一部分，这样你的问题就不会结束。

不，我对这个问题不感兴趣，因为它的质量非常差；正如我之前提到的，这个问题依赖于正确编译语法错误的代码，所以我们无法重现您看到的结果。即使我们纠正了语法错误，我们也必须填空（这是你的工作），这会给任何可能的答案带来不确定性。关于这个问题，我唯一感兴趣的是让它关闭的过程。

相关内容

  • 没有找到相关文章

最新更新


热门标签：

javascript python java c# php android html jquery c++ css ios sql mysql arrays asp.net json python-3.x ruby-on-rails .net sql-server django objective-c excel regex ruby linux ajax iphone xml vba spring asp.net-mvc database wordpress string postgresql wpf windows xcode bash git oracle list vb.net multithreading eclipse algorithm macos powershell visual-studio image forms numpy scala function api selenium