Нужна помощь в создании функции maxHeap - PullRequest
Новая
       42

Нужна помощь в создании функции maxHeap

0 голосов
/ 18 января 2019 

#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). Затем пользователь вводит слово, и программа отображает частоту набранного слова. Выше работает нормально, используя любой входной файл.

Однако у меня проблемы со следующими шагами задания:

После этого предполагается, что дерево дырок копируется в макси-кучу на основе частоты каждого слова. Куча должна быть создана с использованием массива с размером, равным элементам дерева. Каждая ячейка указанного массива должна содержать указатель, который указывает на узел в дереве двоичного поиска, чтобы мы могли по-прежнему иметь доступ к слову внутри и его частоте.

Затем пользователь вводит целое число, и программа печатает все слова, частота которых меньше числа, введенного пользователем. 

#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;
}

1 Ответ

0 голосов
/ 18 января 2019

Я и многие из нас допускаем простые ошибки. Используйте автоматизированные инструменты, необходимые для повышения эффективности кодирования.

Экономьте время, включайте все предупреждения компилятора или используйте лучший компилятор.

предупреждение: управление достигает конца не пустой функции [-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);
  }
}

Могут существовать другие проблемы.

...