Trabajo2.cpp

/*
  Copyright (C) 2016  Katerine Muñoz Tello <[email protected]>
  This program is free software: you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.
  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.
  You should have received a copy of the GNU General Public License
  along with this program.  If not, see <http://www.gnu.org/licenses/>.
*** Nombre: Katerine Muñoz Tello.
*** Objetivo:  Una empresa quiere hacer un estudio de las palabras más 
    utilizadas en redes sociales, para ello analizo los mensajes escritos por 
    un grupo de sujetos, ahora que tiene los mensajes, lo contrata a Ud. Como 
    especialista para que:
      ·Liste las palabras utilizadas en orden alfabético, con la respectiva 
       frecuencia de aparición
      ·Muestre las palabras más y menos utilizadas
      ·Muestre la(s) palabras más cortas y la(s) más largas
      ·Elimine la letra que tenga menos palabras, si hay más de una elija la 
       que esta en un level más alto.
      ·Elimine una palabra, la que el usuario quiera.
      ·Algo más.
*** SO: Fedora 23.
*** IDE: Sublime Text.
*** Compilador: GNU Make 4.0
*/

#include <iostream>
#include <string.h>
#include <fstream>
#include <stdio.h>
#include <ctype.h>
using namespace std;

struct word{
  char wo[30];
  int freq;
  word *next;
};

struct tree{
  char le;
  word *w;
  tree *right;
  tree *left;
};

/*01*/tree *insert(tree *t, char le);
/*02*/char majorele(tree *t);
/*03*/tree *out(tree *t, char le);
/*04*/int  isintree(tree *t, char le);
/*05*/tree *fullout(tree *T, char le);
/*06*/char take_first_letter(char w[30]);
/*07*/int  isinword(char wo[30], word *w);
/*08*/word *increase_frequency(char wo[30], word *w);
/*09*/word *in_new(char wo[30], word *w);
/*10*/word *in(char wo[30], word *w);
/*11*/word *wordout(word *w, char wo[30]);
/*12*/int  getH_frequency(word *w);
/*13*/void higher_frequency(tree *t, int &i);
/*14*/void show_wordf(word *w, int i);
/*15*/void inshowf(tree *t, int i);
/*16*/void more_used(tree *t);
/*17*/int  getL_frequency(word *w);
/*18*/int  lower_frequency(tree *t, tree *aux, int i);
/*19*/void less_used(tree *t);
/*20*/tree *findtree(tree *t, char le);
/*21*/void byuser(tree *t, char wo[30]);
/*22*/int  sgetlength(word *w);
/*23*/int  shortestword(tree *t, tree *aux, int i);
/*24*/void show_wordl(word *w, int i);
/*25*/void inshowl(tree *t, int i);
/*26*/void lesslen(tree *t);
/*27*/int  lgetlength(word *w);
/*28*/int  longestword(tree *t, tree *aux, int i);
/*29*/void longlen(tree *t);
/*30*/int  wordcount(word *w);
/*31*/int  treewordcount(tree *t, tree *aux, int i);
/*32*/int  level(tree *t, char le, int n);
/*33*/char getletter(tree *t, tree *aux, int i, int n, char le);
/*34*/int  eraselessword(tree *t);
/*35*/void showwords(word *w);
/*36*/tree *lookfor(tree *t, char le);
/*37*/void change(char wo[30], char n, char y);
/*38*/void extra(tree *t);
/*39*/void showall(tree *t);
/*40*/void inorden(tree *t);
/*41*/void preorden(tree *t);
/*42*/void postorden(tree *t);
/*43*/void menu(tree *t);

// FUNCIONES
tree *insert(tree *t, char le){                                   /* 01.INSERTAR/CREAR NODO DEL ARBOL */
  if(t == NULL){
    t = new tree;
    if(!t){
      cout << "\t\tNO HAY SUFICIENTE MEMORIA." << endl;
      return t;
    }
    t->le = le;
    t->left = t->right = NULL;
  }else if(t->le < le){
    t->right = insert(t->right, le);
  }else if(t->le > le){
    t->left = insert(t->left, le);
  }else{
    cout << "\t\tEL ELEMENTO YA ESXISTE. \nNO PUEDE ESTAR REPETIDO." << endl;
  }
  return t;                                 
}

char majorele(tree *t){                                           /* 02.ENCUENTRA EL MAYOR NODO EN EL ARBOL */
  while(t->right){
    t = t->right;
  }
  return(t->le);                                         
} 

tree *out(tree *t, char le){                                      /* 03.ELIMINAR NODO DEL ARBOL */
  tree *aux;
  char major;

  if(t->le == le){
    if(t->left == NULL && t->right == NULL){
      delete t;
      return NULL;
    }else if(t->left == NULL){
      aux = t->right;
      delete t;
      return aux;
    }else{
      major = majorele(t->left);
      t->le = major;
      t->left = out(t->left, major);
    }
  }else if(t->le > le){
    t->left = out(t->left, le);
  }else{
    t->right = out(t->right, le);
  }
  return t;                                    
}

int isintree(tree *t, char le){                                   /* 04.RETORNA 1 SI LA LETRA ESTA EN EL ARBOL Y 0 SI NO */
  if(!t){
    return 0;
  }if(t->le == le){
    return 1;
  }if(t->le < le){
    return (isintree(t->right, le));
  }else{
    return (isintree(t->left, le));
  }
}

tree *fullout(tree *T, char le){                                  /* 05.ELIMINA TODO EL ARBOL */ 
  if(T && isintree(T, toupper(le)) == 1){
    T = out(T, le);
  }else{
    cout << "\t\tLA LETRA NO SE ENCUENTRA. \nNO PUEDE SER ELEMINADA." << endl;
  }
  return T;
}

char take_first_letter(char w[30]){                               /* 06.TOMA LA PRIMERA LETRA DE LA PALABRA Y LA TRANSFORMA EN MAYUSCULA */
  char l = toupper(w[0]);
  return l;                             
}

int isinword(char wo[30], word *w){                               /* 07.RETORNA 1 SI LA PALABRA SE ENCUENTRA EN LA LISTA Y 0 SI NO */
  word *aux;
  aux = w;
  int i = 0;
  wo[0] = tolower(wo[0]);

  while(aux){
    if(!strcmp(wo, aux->wo)){
      i = 1;
    }
    aux = aux->next;
  }

  return i;                             
}

word *increase_frequency(char wo[30], word *w){                   /* 08.AUMENTA EL CONTADOR DE UNA PALABRA */
  word *aux;
  aux = w;

  while(strcmp(wo, aux->wo) != 0){
    aux = aux->next;
  }

  aux->freq += 1;  
  return w;               
}

word *in_new(char wo[30], word *w){                               /* 09.CREA Y AGREGA A LA LISTA UNA NUEVA PALABRA */
  word *aux, *aux2, *aux3;
  wo[0] = tolower(wo[0]);

  aux = new word;
  strncpy(aux->wo, wo, 30);
  aux->freq = 1;
  aux->next = w;

  if(!w){
    w = aux;
  }else{
    aux2 = w;
    aux3 = aux;

    while(aux2){
      int i = 1;
      while(wo[i] == (aux2->wo)[i]){
        i++;
      }
      if(wo[i] > (aux2->wo)[i]){
        aux3 = aux2;
        aux2 = aux2->next;
        aux->next = aux2;
      }else{
        break;
      }
    }

    if(aux3 == aux){
      w = aux;
    }else{
      aux3->next = aux;
    }
  } 
  return w;                            
}

word *in(char wo[30], word *w){                                   /* 10.COMBINA LAS DOS FUNCIONES ANTERIORES */
  int i = isinword(wo, w);

  if(i){
    increase_frequency(wo, w);
  }
  else{
    w = in_new(wo, w);
  }   
  return w;                              
}

word *wordout(word *w, char wo[30]){                              /* 11.ELIMINA UNA PALABRA DE LA LISTA */
  word *aux, *aux2;
  if(w == NULL){
    cout << "\t\tLISTA VACIA." << endl;
  }else{
    aux = w;
    if(!strcmp(w->wo, wo)){
      w = w->next;
      delete aux;
    }else{
      do{
        aux2 = aux;
        aux = aux->next;
      }while(aux && strcmp(aux->wo, wo) != 0);
      if(aux){
        aux2->next = aux->next;
        delete aux;
      }else{
        cout << "\t\tLA PALABRA NO ESTA EN LA LISTA." << endl;
      }
    }
  }
  return w;                            
}

int getH_frequency(word *w){                                      /* 12.RETORNA LA FRECUENCIA MAS ALTA DE LA LISTA */
  word *aux;
  aux = w;
  int i = 0;

  while(aux){
    if(aux->freq > i){
      i = aux->freq;
    }
    aux = aux->next;
  }

  return i;
}

int higher_frequency(tree *t, tree *aux, int i){                  /* 13.OBTIENE LA FRECUENCIA DE LA PALABRA MAS REPETIDA DEL ARBOL*/
  if(t){
    higher_frequency(t->left, aux, i);
    higher_frequency(t->right, aux, i);
    int j = getH_frequency(t->w);
    if(j > i){
      i = j;
    }
  }

  if(aux == t){
    return i;
  }
}

void show_wordf(word *w, int i){                                  /* 14.MUESTRA UNA PALABRA SEGUN SU FRECUENCIA */
  word *aux;
  aux = w;

  while(aux){
    if(aux->freq == i){
      cout << "\t\t" << aux->wo << endl;
    }
    aux = aux->next;
  }
}

void inshowf(tree *t, int i){                                     /* 15.RECORRE EL ARBOL INORDEN PARA MOSTRAR LAS PALABRAS SEGUN FRECUENCIA */
  if(t){
    inshowf(t->left, i);
    show_wordf(t->w, i);
    inshowf(t->right, i);
  }
}

void more_used(tree *t){                                          /* 16.MUESTRA LA(S) PALABRA(S) MAS USADA(S) */
  int i = higher_frequency(t, t, 0);

  cout << "\tLas palabras que mas se repiten con " << i << " veces son:" << endl;
  inshowf(t, i);
}

int getL_frequency(word *w){                                      /* 17.RETORNA LA FRECUENCIA MAS BAJA DE LA LISTA */
  word *aux;
  aux = w;
  int i = getH_frequency(w);

  while(aux){
    if(aux->freq < i){
      i = aux->freq;
    }
    aux = aux->next;
  }

  return i;
}

int lower_frequency(tree *t, tree *aux, int i){                   /* 18.OBTIENE LA FRECUENCIA DE LA PALABRA MENOS REPETIDA DEL ARBOL */
  if(t){
    lower_frequency(t->left, aux, i);
    lower_frequency(t->right, aux, i);
    int j = getL_frequency(t->w);
    if(j < i){
      i = j;
    }
  }

  if(aux == t){
    return i;
  }
}

void less_used(tree *t){                                          /* 19.MUESTRA LA(S) PALABRA(S) MENOS USADA(S) */
  int i = lower_frequency(t, t, 10);

  cout << "\tLas palabras que menos se repiten con " << i << " veces son:" << endl;
  inshowf(t, i);
}

tree *findtree(tree *t, char le){                                 /* 20.RETORNA PUNTERO HACIA EL NODO DEL ARBOL CON LA LETRA BUSCADA */
  if(t->le == le){
    return t;
  }if(t->le < le){
    findtree(t->right, le);
  }else{
    findtree(t->left, le);
  }
}

void byuser(tree *t, char wo[30]){                                /* 21.ELIMINAR PALABRA ELEGIDA POR USUARIO */
  tree *taux; 
  word *waux;
  char le;

  le = take_first_letter(wo);
  taux = findtree(t, le);
  waux = taux->w;
  wo[0] = tolower(wo[0]);
  wordout(waux, wo);

  cout << "Se ha eliminado la palabra " << wo << endl; 
}

int sgetlength(word *w){                                          /* 22.OBTIENE EL LARGO DE LA PALABRA MAS CORTA */
  word *aux;
  aux = w;
  int i = strlen(aux->wo);

  while(aux){
    if(strlen(aux->wo) < i){
      i = strlen(aux->wo);
    }
    aux = aux->next;
  }

  return i;
}

int shortestword(tree *t, tree *aux, int i){                      /* 23.OBTIENE EL LARGO DE LA PALABRA MAS CORTA DEL ARBOL */
  if(t){
    shortestword(t->left, aux, i);
    shortestword(t->right, aux, i);
    int j = sgetlength(t->w);
    if(j < i){
      i = j;
    }
  }

  if(aux == t){
    return i;
  }
}

void show_wordl(word *w, int i){                                  /* 24.MUESTRA PALABRAS SEGUN SU LARGO */
  word *aux;
  aux = w;

  while(aux){
    if(strlen(aux->wo) == i){
      cout << "\t\t" << aux->wo << endl;
    }
    aux = aux->next;
  }
}

void inshowl(tree *t, int i){                                     /* 25.RECORRE EL ARBOL INORDEN PARA MOSTRAR LAS PALABRAS SEGUN LARGO */
  if(t){
    inshowl(t->left, i);
    show_wordl(t->w, i);
    inshowl(t->right, i);
  }
}

void lesslen(tree *t){                                            /* 26.MUESTRA LA(S) PALABRA(S) MAS CORTA(S) */
  int i = shortestword(t, t, 10);

  cout << "\tLas palabras mas cortas con " << i << " letras de largo son:" << endl; 
  inshowl(t, i);
}

int lgetlength(word *w){                                          /* 27.OBTIENE EL LARGO DE LA PALABRA MAS LARGA */
  word *aux;
  aux = w;
  int i = 0;

  while(aux){
    if(strlen(aux->wo) > i){
      i = strlen(aux->wo);
    }
    aux = aux->next;
  }
  return i;
}

int longestword(tree *t, tree *aux, int i){                       /* 28.OBTIENE EL LARGO DE LA PALABRA MAS LARGA DEL ARBOL */
  if(t){
    longestword(t->left, aux, i);
    longestword(t->right, aux, i);
    int j = lgetlength(t->w);
    if(j > i){
      i = j;
    }
  }

  if(aux == t){
    return i;
  }
}

void longlen(tree *t){                                            /* 29.MUESTRA LA(S) PALABRA(S) MAS LARGA(S) */
  int i = longestword(t, t, 0);

  cout << "\tLas palasbras mas largas con " << i << " letras de largo son: " << endl;
  inshowl(t, i);
}

int wordcount(word *w){                                           /* 30.CUENTA PALABRAS DE LA LISTA */
  word *aux;
  aux = w;
  int i = 0;

  while(aux){
    i++;
    aux = aux->next;
  }
  return i;
}

int treewordcount(tree *t, tree *aux, int i){                     /* 31.OBTIENE CUANTAS PALABRAS TIENE EL NODO CON MENOS PALABRAS */
  if(t){
    treewordcount(t->left, aux, i);
    treewordcount(t->right, aux, i);
    int j = wordcount(t->w);
    if(j < i){
      i = j;
    }
  }
  if(aux == t){
    return i;
  }
}

int level(tree *t, char le, int n){                               /* 32.RETORNA EL NIVEL DE UN NODO DEL ARBOL */
  if(t->le == le){
    return n;
  }if(t->le < le){
    n++;
    level(t->right, le, n);
  }else{
    n++;
    level(t->left, le, n);
  }
}

char getletter(tree *t, tree *aux, int i, int n, char le){        /* 33.RETORNA LA LETRA DE MAYOR NIVEL CON MENOS PALABRAS */
  if(t){
    getletter(t->left, aux, i, n, le);
    getletter(t->right, aux, i, n, le);
    if(wordcount(t->w) == i && level(t, le, 0) < n){
      n = level(t, le, 0);
      le = t->le;
    }
  }
  if(aux == t){
    return le;
  }
}

int eraselessword(tree *t){                                       /* 34.ELIMINA LETRA CON MENOS PALABRAS */
  int i = treewordcount(t, t, 10);
  char le = getletter(t, t, i, 10, 'A');
  out(t, le);
  cout << "Se ha eliminado la letra " << le << " con " << i << " palabras en total." << endl;
}

void showwords(word *w){                                          /* 35.MUESTRA TODAS LAS PALABRAS DE LA LISTA */
  word *aux = w;

  while(aux){
    cout << "\t\t" << aux->wo << endl;
    aux = aux->next;
  }
}

tree *lookfor(tree *t, char le){                                  /* 36.BUSCA UNA LETRA EN EL ARBOL Y RETORNA EL PUNTERO A SU LISTA */
  if(t->le == le){
    return (t);
  }if(t->le < le){
    lookfor(t->right, le);
  }else{
    lookfor(t->left, le);
  }
}

void change(char wo[30], char n, char y){                         /* 37.MUESTRA PALABRA CON LETRAS CAMBIADAS */
  for(int i=0; i < strlen(wo); i++){
    if(wo[i] == n){
      cout << y;
    }else{
      cout << wo[i];
    }
  }
  cout << "\n" << endl;
}

void extra(tree *t){                                              /* 38.FUNCION EXTRA (TOMA PALABRA(S) ELEGIDA(S) POR USUARIO Y LE CAMBIA UNA LETRA POR OTRA (TAMBIEN ELEGIDAS POR USUARIO)) */
  char le;
  cout << "\tElija la letra de donde quiere sacar la palabra (en MAYUSCULA):" << endl;
  cin  >> le;

  while(!isintree(t, le)){
    cout << "*** La letra ingresada no se encuentra en la base de datos.\n***Por favor ingrese otra (en MAYUSCULA):" << endl;
    cin  >> le;
  }

  tree *aux = lookfor(t, le);
  showwords(aux->w);

  int i;
  cout << "\tSi quiere cambiar todas las palabras, ingrese 1.\nAi desea elegir la palabra, ingrese 0:" << endl;
  cin  >> i;

  char n, y;
  if(i){
    cout << "\tIngrese la letra que quiere cambiar:" << endl;
    cin  >> n;
    cout << "\tIngrese la letra por la que quiere cambiar la anterior:" << endl;
    cin  >> y;

    word *waux = aux->w;
    while(waux){
      change(waux->wo, n, y);
      waux = waux->next;
    }
  }else{
    char wo[30];
    cout << "\tIngrese palabra elegida:" << endl;
    cin  >> wo;
    cout << "\tIngrese la letra que quiere cambiar:" << endl;
    cin  >> n;
    cout << "\tIngrese la letra por la que quiere cambiar la anterior:" << endl;
    cin  >> y;
    change(wo, n, y);
  }
}

void showall(tree *t){                                            /* 39.MUESTRA TODAS LAS LETRAS Y SUS RESPECTIVAS PALABRAS */
  if(t){
    showall(t->left);
    cout << "La letra " << t->le << " contiene las siguientes palabras: " << endl;
    showwords(t->w);
    showall(t->right);
  }
}

void inorden(tree *t){
  if(t){
    inorden(t->left);
    cout << t->le << "\t";
    inorden(t->right);
  }
}

void preorden(tree *t){
  if(t){
    cout << t->le << "\t";
    preorden(t->left);
    preorden(t->right);
  }
}

void postorden(tree *t){
  if(t){
    postorden(t->left);
    postorden(t->right);
    cout << t->le << "\t";
  }
}

void menu(tree *t){
  int op;
  tree *aux = NULL;
  do
  { 
    cout <<"\n*************************************MENU*************************************"<<endl;
    cout <<"\t 01. Mostrar palabras mas utilizadas."<<endl;
    cout <<"\t 02. Mostrar palabras menos utilizadas."<<endl;
    cout <<"\t 03. Mostrar palabras mas cortas."<<endl;
    cout <<"\t 04. Mostrar palabras mas largas."<<endl;
    cout <<"\t 05. Eliminar letra con menos palabras."<<endl;
    cout <<"\t 06. Eliminar palabra elegida por usuario."<<endl;
    cout <<"\t 07. [EXTRA] Mostrar el cambio de letras en una palabra elegida por\n\t     usuario."<<endl;
    cout <<"\t 08. Mostrar palabras segun letra."<<endl;
    cout <<"\t 09. Mostrar todas las palabras."<< endl;
    cout <<"\t 10. Inorden."<< endl;
    cout <<"\t 11. Preorden."<< endl;
    cout <<"\t 12. Postorden."<< endl;
    cout <<"\t 13. Salir."<< endl;
    cout <<"      Opcion:  ";
    cin >> op;
    switch(op){
      case 1 :
        more_used(t);
        break;
      case 2 :
        less_used(t);
        break;
      case 3 :
        lesslen(t);
        break;
      case 4:
        longlen(t);
        break;
      case 5:
        eraselessword(t);
        break;
      case 6:
        char wo[30];
        cout << "Ingresa la palabra que quieres eliminar:" << endl;
        cin  >> wo;
        byuser(t, wo);
        break;
      case 7:
        extra(t);
        break;
      case 8:
        char le;
        cout << "Ingresa la letra inicial (en mayuscula) de las palabras que deseas ver: " << endl;
        cin  >> le;
        aux = lookfor(t, le);
        showwords(aux->w);
        break;
      case 9:
        showall(t);
        break;
      case 10:
        inorden(t);
        break;
      case 11:
        preorden(t);
        break;
      case 12:
        postorden(t);
        break;
    }
 }while(op!=13);
}

int main(){
  char wo[30];
  ifstream f1;
  tree *t = NULL, *taux = NULL;
  word *w = NULL;

  f1.open("mensajes3.txt", ios::binary);
  f1.read((char *)(&wo),sizeof(30));

  while(!f1.eof()){
    char le = take_first_letter(wo);
    if(isintree(t, le)){
      taux = lookfor(t, le);
      taux->w = in(wo, taux->w);
    }else{
      t = insert(t, le);
      taux = lookfor(t, le);
      taux->w = in_new(wo, taux->w);  
    }
    f1.read((char *)(&wo),sizeof(30));
  }
  f1.close();

  menu(t);
  while(t){
    t = fullout(t, t->le);
  }
  return 0;
}

ERROR:
/tmp/ccQAHLqt.o: En la función main': trabajo2.cpp:(.text+0x187d): referencia ain(char_, word_)' sin definir
collect2: error: ld devolvió el estado de salida 1