c - 需要帮助创建 maxHeap 函数

Question

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

typedef struct listNode {
  int id;
  struct listNode *next;
} ListNode;

typedef struct treeNode {

  char *word;
  char *key;
  int freq;
  ListNode *head;
  struct treeNode *left;
  struct treeNode *right;
} TreeNode;


TreeNode *insertItem(TreeNode *root, char *gword);
void printTreeInorder(TreeNode *v);
void searchforexist(TreeNode *root, char *key);
int searchItem(TreeNode *root, char *word);
void Heap(TreeNode *arr[],TreeNode *root, int i);
void maxheap(TreeNode *arr[],int k);
void freeNodes(TreeNode *root);

#define MAX 25
int main() {
  char in[MAX];

  char word[MAX];
  TreeNode *root = NULL;
  int comp;
  int f=0;
  int t=0;
  FILE *fp = fopen("input.txt", "r");

  memset(word, 0, MAX);
  if (fp != NULL) {
   
    while (fscanf(fp, "%24s \n", word) != EOF) {
      
      root = insertItem(root, word);//insert items
      t++;
      if (strcmp(word, "eof") == 0) break;
    }

    fclose(fp);
  }
  
  // User inputs word 
   printf("Give word");
   printf("\n");
   scanf("%s",in);
   comp=strcmp(in,"#");
  
  while(comp!=0)
  {
      printf("Give word");
     printf("\n");
     scanf("%s",in);
     comp=strcmp(in,"#");
     if(comp==1)
       break;
    
     f=searchItem(root,in);
     printf("%d",f);
     f=0;
     printf("\n");
  }
    TreeNode *arr[t];
    Heap(arr,root,t);// HEAPPPPPPPPPPPPPPPPPPPPPPPPPPPP

  printTreeInorder(root);
  printf("\n");

  freeNodes(root);
  return 0;
}

TreeNode *insertItem(TreeNode *root, char *gword) {
  TreeNode *v = root;
  TreeNode *pv = NULL;
  
  while (v != NULL) {
   
    pv = v;
    int comp = strcmp(gword, v->word);
    
    if (comp < 0) {
       
      v = v->left;
    } else if (comp > 0) {
      v = v->right;
     
    } else {
      char *word = v->word;
      searchforexist(root,v->word);
     
      return root;
    }
  }
 
 
  TreeNode *tmp = (TreeNode *)malloc(sizeof(TreeNode));
 
 
  tmp->word = strdup(gword);
  
  tmp->left = tmp->right = NULL;
  tmp->freq = 1;

  if (root != NULL) {
    if (strcmp(gword, pv->word) < 0) {
      pv->left = tmp;
    } else {
      pv->right = tmp;
    }
  } else
    root = tmp;


  return root;
}

void searchforexist(TreeNode *root, char *word) {
  if(root == NULL) {
    return;
  }

  int comp = strcmp(word, root->word);

  if(comp == 0) {
    root->freq++;
  } else {
    searchforexist(comp < 0 ? root->left : root->right , word);
  }

}



int searchItem(TreeNode *root, char *word)
{
 if(root == NULL) {
    return 0;
  }

  int comp = strcmp(word, root->word);

  if(comp == 0) {
    return root->freq;
  } else {
    searchItem(comp < 0 ? root->left : root->right , word);
  }

}

void Heap(TreeNode *arr[],TreeNode *root, int i)
{
int  k=0;
  while(k<i)
  {
  if(root==NULL){
    maxheap(arr,k);
  }
  
   arr[k]=root;
   k++;
   if (k=i){
      maxheap(arr,k);
      break;
   }
   
   Heap(arr,root->left,k);
   Heap(arr,root->right,k);
  }
}

void maxheap(TreeNode *arr[],int k)
{
   int i;
    int j;
   for (i = 0; i < k; i++)   
     {                 
      for (j = 0; j < k; j++)       
       {
           if(arr[i]->freq>arr[j]->freq)
             {
                TreeNode *tmp = arr[i];         
		arr[i] = arr[j];           
		arr[j] = tmp;        
	     }
      }
     }
    for (i = 0; i < k; i++)   
     {    
       printf("%s %d",arr[i]->word,arr[i]->freq);
    }
}

void printTreeInorder(TreeNode *v) 
{
    if (v==NULL) return;

    printf("(");
    printTreeInorder(v->left);
    printf(")");

    printf(" %.4s ", v->word);

    printf("(");
    printTreeInorder(v->right);
    printf(")");
}

void freeNodes(TreeNode *root) {
  if (root == NULL) {
    return;
  }
  freeNodes(root->left);
  freeNodes(root->right);

  if(root->word != NULL) free(root->word);
  if(root->key != NULL) free(root->key);
  free(root);
  return;
}

该程序读取文件并将所有字符串放入二叉搜索树。不添加重复词但频率计数器增加(searchforexist)。然后用户键入一个词，程序显示该词键入的频率。以上使用任何输入文件都可以正常工作。

但是我在接下来的作业步骤中遇到了问题:

然后根据每个单词的频率假设将洞树复制到最大堆中。必须使用大小等于树元素的数组创建堆。所述数组的每个单元格都必须包含一个指向二叉搜索树中节点的指针，以便我们仍然可以访问其中的单词及其频率。

然后用户输入一个 int 数字，程序打印出频率低于用户输入数字的所有单词。

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

typedef struct listNode {
  int id;
  struct listNode *next;
} ListNode;

typedef struct treeNode {

  char *word;
  char *key;
  int freq;
  ListNode *head;
  struct treeNode *left;
  struct treeNode *right;
} TreeNode;


TreeNode *insertItem(TreeNode *root, char *gword);
void printTreeInorder(TreeNode *v);
void searchforexist(TreeNode *root, char *key);
int searchItem(TreeNode *root, char *word);
void freeNodes(TreeNode *root);

#define MAX 25
int main() {
  char in[MAX];

  char word[MAX];
  TreeNode *root = NULL;
  int comp;
  int f=0;

  FILE *fp = fopen("input.txt", "r");

  memset(word, 0, MAX);
  if (fp != NULL) {

    while (fscanf(fp, "%24s \n", word) != EOF) {

      root = insertItem(root, word);//insert items

      if (strcmp(word, "eof") == 0) break;
    }

    fclose(fp);
  }

  // User inputs word 
   printf("Give word");
   printf("\n");
   scanf("%s",in);
   comp=strcmp(in,"#");

  while(comp!=0)
  {
      printf("Give word");
     printf("\n");
     scanf("%s",in);
     comp=strcmp(in,"#");
     if(comp==1)
       break;

     f=searchItem(root,in);
     printf("%d",f);
     f=0;
     printf("\n");
  }

   //heapcreating here 


  printTreeInorder(root);
  printf("\n");

  freeNodes(root);
  return 0;
}

TreeNode *insertItem(TreeNode *root, char *gword) {
  TreeNode *v = root;
  TreeNode *pv = NULL;

  while (v != NULL) {

    pv = v;
    int comp = strcmp(gword, v->word);

    if (comp < 0) {

      v = v->left;
    } else if (comp > 0) {
      v = v->right;

    } else {
      char *word = v->word;
      searchforexist(root,v->word);

      return root;
    }
  }


  TreeNode *tmp = (TreeNode *)malloc(sizeof(TreeNode));


  tmp->word = strdup(gword);

  tmp->left = tmp->right = NULL;
  tmp->freq = 1;

  if (root != NULL) {
    if (strcmp(gword, pv->word) < 0) {
      pv->left = tmp;
    } else {
      pv->right = tmp;
    }
  } else
    root = tmp;


  return root;
}

void searchforexist(TreeNode *root, char *word) {
  if(root == NULL) {
    return;
  }

  int comp = strcmp(word, root->word);

  if(comp == 0) {
    root->freq++;
  } else {
    searchforexist(comp < 0 ? root->left : root->right , word);
  }

}



int searchItem(TreeNode *root, char *word)
{
 if(root == NULL) {
    return 0;
  }

  int comp = strcmp(word, root->word);

  if(comp == 0) {
    return root->freq;
  } else {
    searchItem(comp < 0 ? root->left : root->right , word);
  }

}


void printTreeInorder(TreeNode *v) 
{
    if (v==NULL) return;

    printf("(");
    printTreeInorder(v->left);
    printf(")");

    printf(" %.4s ", v->word);

    printf("(");
    printTreeInorder(v->right);
    printf(")");
}

void freeNodes(TreeNode *root) {
  if (root == NULL) {
    return;
  }
  freeNodes(root->left);
  freeNodes(root->right);

  if(root->word != NULL) free(root->word);
  if(root->key != NULL) free(root->key);
  free(root);
  return;
}

Answer 1

我和我们中的许多人都会犯简单的错误。使用您拥有的自动化工具来提高编码效率。

节省时间，启用所有编译器警告 - 或者使用更好的编译器。

warning: control reaches end of non-void function [-Wreturn-type]

searchItem() 需要返回一个值。

int searchItem(TreeNode *root, char *word) {
  if (root == NULL) {
    return 0;
  }

  int comp = strcmp(word, root->word);

  if (comp == 0) {
    return root->freq;
  } else {

    // searchItem(comp < 0 ? root->left : root->right, word);
    return searchItem(comp < 0 ? root->left : root->right, word);
  }
}

可能存在其他问题。