Change signature and parameters of some functions

0

I'm creating a program that inverts the non-vowel sequences of a word represented by a list that is simply chained, without head, and without sentinel. That is, each node in the list has a letter field. My work is to invert the non-vowel sequences (spaces, consonants, and scores) from this list without modifying the original list.

The algorithm itself is ready and working. My problem is in how to transform functions of type LISTA* into functions of type NO* and what are the implications of this change.

Typedefs:

// elemento da lista
typedef struct estr {
    char letra;
    struct estr *prox;
} NO;

typedef struct {
    NO *inicio;
} LISTA;

Functions to change:

//precisa ser do tipo NO*, bem como deve receber NO*
LISTA* clonarLista(LISTA* l){
  LISTA* resp = malloc(sizeof(LISTA));

  NO *corrente = l->inicio;
  NO *anterior = NULL; //utilizar um nó anterior para ligar os vários elementos

  while(corrente){ //agora com corrente em vez de l
    NO *novo = (NO *) malloc(sizeof(NO));
    novo->letra = corrente->letra;
    novo->prox = NULL;

    if (anterior == NULL){ //se é o primeiro fica no inicio da nova lista
        resp->inicio = novo;
    }
    else { //se não é o primeiro liga o anterior a este pelo prox
        anterior->prox = corrente;
    }

    anterior = novo;
    corrente = corrente->prox;
  }

  return resp;
}

void inverter(LISTA* resp){

    NO* atual = resp->inicio;

    /*redefinir a lista para começar vazia, sendo que o ponteiro atual ainda
    aponta para os seus elementos*/
    resp->inicio = NULL;

    while (atual != NULL){ //enquanto houver nós
        NO* corrente = atual; //guardar nó corrente
        atual = atual->prox; //avançar nó atual


        corrente->prox = resp->inicio; //fazer o prox do corrente ser o 1 da lista invertida
        resp->inicio = corrente; //o inicio passa a ser este ultimo nó
    }
}

//precisa ser do tipo NO*, bem como deve receber NO*
void decodificar(LISTA* resp) {
    NO* pNv = NULL; // Primeira não-vogal encontrada.
    NO* ultNv = NULL; // Última não-vogal encontrada.

    NO* atual = resp->inicio; // Ponteiro para percorrer a lista.

    NO* anterior = NULL;

    /* Laço para percorrer toda lista. */
    while (atual != NULL) {


        /* Enquanto atual apontar para uma não-vogal. */
        if (verificaSequencia(atual)) {
            /* Salva o primeiro caso encontrado de não-vogal. */
            pNv = atual;


            /* Procura na lista o último caso de não-vogal. */
            while (atual->prox != NULL && verificaSequencia(atual->prox)) {
                atual = atual->prox;
            }

            /* Quando a próxima letra for uma vogal, então foi atingido o fim da sequência de não-vogais. */
            ultNv = atual;

            /* Se existir uma sequência de não-vogais, ou seja, pNv e ultNv não apontarem para o mesmo elemento, então a troca de posições deve ser efetuada. */
            if (pNv != ultNv) {
                /* Chama uma função recursiva para efetuar a troca de posições sem precisar criar uma nova lista. */

                NO* proximoOriginal = ultNv->prox;

                inverterNvs(pNv->prox, pNv, ultNv);

                pNv->prox = proximoOriginal;

                if (anterior == NULL){
                    resp->inicio = ultNv;
                }
                else {
                    anterior->prox = ultNv;
                }

                atual = pNv;
            }
        }

        /* Move para o próximo elemento. */
        anterior = atual;
        atual = atual->prox;
    }
}

The program should work for calls of the type:

NO* teste = null;
teste = decodificar(p);

Full program: link

    
asked by anonymous 13.09.2017 / 01:36

1 answer

1
  

What are the implications of this change?

The implications are few. In fact most of the pure lists implemented in C use only the structure that represents the node:

typedef struct estr {
    char letra;
    struct estr *prox;
} NO;

Having a structure that represents the list itself facilitates in other things such as:

  • Know the size of the structure by adding a field for the size itself
  • Have a pointer to the tail of the list also, which makes the addition to the tail with a cost of O (1)
  • Easy to change the initial node (something you already have in your code)

A list structure with size and pointer to tail would look like this:

typedef struct {
    NO *inicio;
    NO *fim;
    size_t tamanho;
} LISTA;

As in your case only has the pointer to the start it becomes similar to using NO directly. The biggest difference comes in the code that changes the initial node of the list.

  

how to transform LIST-type functions into functions of type NO *?

If there are no changes to the initial node the exchange is direct replacing resp->inicio with inicio . When there are these changes there are two ways to do it:

Passing pointer to pointer

Exemplifying in function inverter :

void inverter(NO** inicio){ //agora NO** inicio

    NO* atual = *inicio; //de resp->inicio para *inicio
    *inicio = NULL; //de resp->inicio para *inicio

    while (atual != NULL){
        NO* corrente = atual;
        atual = atual->prox;

        corrente->prox = resp->inicio;
        *inicio = corrente; //de resp->inicio para *inicio
    }
}

Note that the function was declared as void inverter(NO** inicio) instead of void inverter(NO* inicio) as it had suggested. This makes it possible to change the pointer inicio within the function directly, through the pointed value, with *inicio = ... .

The changes have almost been summarized as changing% from% to% with%.

Returning the new pointer

Another way to do this is to return the new resp->inicio at the end of the function instead of trying to change it:

NO* inverter(NO* inicio){ //agora já não é void e sim NO*, e recebe NO* em vez de NO**

    NO* atual = inicio;
    inicio = NULL; //de resp->inicio para inicio

    while (atual != NULL){ 
        NO* corrente = atual; 
        atual = atual->prox; 

        corrente->prox = resp->inicio;
        inicio = corrente; //de resp->inicio para inicio
    }

    return inicio; //retornar o novo inicio
}

In this latter solution it is important to say that *inicio does not change the pointer of inicio or another place where the function was called, and only the local pointer of the function. This is why it is necessary to return this in the end.

    
13.09.2017 / 03:12