Change signature and parameters of some functions

Question

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

The algorithm itself is already up and running. My problem is in how to transform type functions LISTA* in functions of the type NO*and what are the implications of that change.

Typedefs:

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

typedef struct {
    NO *inicio;
} LISTA;

Functions to be changed:

//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 like:

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

Full programme: https://repl.it/KrQg/5

Answer 1

what are the implications of this change ?

The implications are few. In fact much of the pure lists implemented in C use only the structure representing the node:

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

Having a structure that represents the list itself facilitates other things like:

• Know the size of the structure by adding a field for the size to it
• Have a pointer to the tail of the list as well, which makes the addition to the tail with a cost of O(1)
• Ease in changing the initial node (something you already use in your code)

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

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

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

how to transform LISTA* functions into NO-type functions* ?

If there are no changes to the initial node the exchange is directly overriding resp->inicio for inicio. When there are such changes there are two ways to do:

Passing pointer to pointer

Exemplifying in the 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 has been declared as void inverter(NO** inicio) instead of void inverter(NO* inicio) as I had suggested. This makes it possible to change the pointer inicio within the function directly, through the pointed value, with *inicio = ... .

The amendments were almost to change resp->inicio for *inicio.

Returning the new pointer

Another way to do it is to return the new 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 last solution it is important to say that inicio = NULL; does not change the pointer of main or another location where the function was called, and only the local function pointer. This is why it is necessary to return this at the end.