时间戳

首页 > 解决方案 > 为什么我的 C 结构必须添加一个奇怪的 int 并且它会影响指针？

c - 为什么我的 C 结构必须添加一个奇怪的 int 并且它会影响指针？

问题描述

这是一个二叉树队列问题

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define NUM 10
typedef struct _node
{
   int value;


   struct _node *left;
   struct _node *right;
}TNode,*Tree;

在 q_node 中添加 *next 是我的目的，否则，我们需要在 Tree 节点结构中添加所以，为了不修改树的结构，我设计了一个 q_node 结构来包含它，我们可以使用定义命令来制作它作为一个模板。

typedef struct _q_node
{
  TNode *t_node;
  int length;
  struct _q_node *next;
}QNode;

typedef struct _Queue
{
   QNode *head;
   QNode *tail;
}Queue;

Queue* init_queue()
{
   Queue *queue=(Queue*)malloc(sizeof(Queue));
   queue->head = queue->tail = NULL;
   return queue;
}

int enQueue(Queue *pQueue,TNode *pTNode)
{

      QNode *pQNode = (QNode *)malloc(sizeof(QNode));
      pQNode->t_node = pTNode;
      if(pQueue->head == NULL)
      {//when it's empty
           pQueue->head = pQNode;
       pQueue->tail = pQNode;
      }
      else
      {
           pQueue->tail->next = pQNode;
       pQueue->tail = pQNode;
      }
}

QNode* deQueue(Queue *pQueue)
{
    if(pQueue->head == NULL)
    {
       return NULL;
    }

    QNode *deNode= pQueue->head;
    pQueue->head = pQueue->head->next;
        return deNode;
}

TNode* init_TNode(int value)
{
    TNode  *new_node = (TNode*)malloc(sizeof(TNode));
    new_node->value=value;
    new_node->left = new_node->right = NULL;
    return new_node;
}

//0:empty
int ifEmpty(Queue *pQueue)
{
   if(pQueue->head == NULL)
   {
     //printf("empty tree\n");
     return 0;
   }

   //printf("queue is not empty\n");
   return 1;
}


int insert_tree(Tree pTree,int pValue)
{

   //found NULL sub tree, then add to his father->left
   if(!pTree)
   {
      return 0;
   }
   TNode *tNode = init_TNode(pValue);
   if(tNode==NULL)
   {
       printf("create TNode error!\n");
       return 0;
   }


   if(pValue < pTree->value)
        if(insert_tree(pTree->left,pValue)==0)
        {
       //no left child any more,set a new left child to pTree
       pTree->left = tNode;
       printf("insert :%d\n",pValue);
    }
   if(pValue > pTree->value)
        if(insert_tree(pTree->right,pValue)==0)
        {
           pTree->right = tNode;
       printf("insert :%d\n",pValue);
        }
}



Tree creatTree()
{
    srand(time(NULL));
    Tree root = init_TNode(rand()%100);
    printf("root is %d\n",root->value);
    int i ;
    for(i=1;i<NUM;i++)
    {
        insert_tree(root,rand()%100);
    }
    printf("creat tree succuess!Tree heigh is:%d\n",get_tree_height(root));
    return root ;
}

int get_tree_height(Tree pRoot)
{

  if(!pRoot)
  {
    return 0;
  }

  int lh=0,rh=0;
  lh = get_tree_height(pRoot->left);
  rh = get_tree_height(pRoot->right);
  return (lh<rh)?(rh+1):(lh+1);
}

int breath_travel(Tree pRoot,Queue *pQueue)
{

   if(!pRoot)
   {
      return 0;
   }

   enQueue(pQueue,pRoot);
   printf("_______________________\n");
   printf("breath begin,enter root:\n");

   while(ifEmpty(pQueue)!=0)
   {
     QNode  *qNode  = deQueue(pQueue);

     //make suer every enQueue Node is not NULL
     if(qNode->t_node->left!=NULL)
       {enQueue(pQueue,qNode->t_node->left);}

      if(qNode->t_node->right!=NULL)
      {
          enQueue(pQueue,qNode->t_node->right);
      }

     //print the tree node value
     printf("%d ",qNode->t_node->value);
   }
   printf("\n-----------\nbreath end!\n-----------\n");

   return 1;
}
int main()
{
  Queue *queue=init_queue();
  int i;

  ifEmpty(queue);
  printf("insert node to queue\n");

  Tree root = creatTree();
  if(!root)
  {
    printf("create Tree failed!\n");
    return 0;
  }

  breath_travel(root,queue);
//  free(queue);
  return 0;
}

如果此版本可以在我的计算机上正常运行，我必须在开头的“_q_node”结构中添加一个未使用的 int “int length”，如果我不添加它，ifEmpty 函数无法找到正确的位置，如“pQueue->head = = 空"

为什么会这样？

标签： cpointers

解决方案

您的程序在insert_tree函数中存在错误。我在您的代码中添加了一些注释：

int insert_tree(Tree pTree,int pValue)
{

   //found NULL sub tree, then add to his father->left
   if(!pTree)
   {
      return 0;
   }
   TNode *tNode = init_TNode(pValue);
   if(tNode==NULL)
   {
       printf("create TNode error!\n");
       return 0;
   }

   if(pValue < pTree->value)
       if(insert_tree(pTree->left,pValue)==0)   // Here the return value is used
       {
           //no left child any more,set a new left child to pTree
           pTree->left = tNode;
           printf("insert :%d\n",pValue);
       }
   if(pValue > pTree->value)
       if(insert_tree(pTree->right,pValue)==0)   // Here the return value is used
       {
           pTree->right = tNode;
           printf("insert :%d\n",pValue);
       }

    // No return value here !!
}

正如您从我的评论中看到的那样，您错过了函数末尾的返回值。由于您在其他地方使用该返回值，因此您的程序使用了一些未初始化的返回值。这会使你的程序失败。

顺便说一句：enQueue也错过了返回值。

建议：始终以高警告级别编译代码，并将所有警告视为错误。换句话说 - 如果有警告，则应在运行代码之前对其进行修复。

如果您使用gccuse进行编译-Wall以获取所有警告

除此之外，我认为这个函数的逻辑有问题。它使用递归来查找插入新值的位置。在每个递归调用中，您使用创建一个新节点，TNode *tNode = init_TNode(pValue);但您仅在递归结束时使用它。换句话说，您似乎有内存泄漏。

此外，尚不清楚您如何/在何处处理pValue等于的情况pTree->value

顺便说一句：pValue对于整数来说是一个真正的坏名字，因为它p会让你认为它是一个指针。

推荐阅读