Split double chained list with head

Asked

Viewed 887 times

2

I have a problem with the Divide function, where I am getting a list and want to return to the right and left part of the list. Can someone give me a hand with logic.

#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

struct celula {
    int num;
    struct celula * seg;
    struct celula * ant;
};

typedef struct celula Numero;



int gerarNumeros(int n);
int numeroDigitos(Numero * lst);
void geraSeed();
void geraLista(Numero *lst, int numeros);
void insereLista(Numero *lst, int num);
void imprimeLista(Numero * lst);
Numero * criaLista(int n);
Numero * DivideDireita(Numero *a, int n);


int main() {
    Numero * head_n1, * head_n2, * resposta ,* head1 ;
    int d;


    printf("Insira a quantidade de DIGITOS do seu numero binario\n");
    scanf("%i", &d);

    head_n1 = criaLista(1); 
    head_n2 = criaLista(1);
    head1 = criaLista(1);
    head2 = criaLista(1);
    printf("Criando os dois numeros... \n\n");

    geraLista(head_n1, d);
    geraLista(head_n2, d);

    imprimeLista(head_n1);

    printf("\n\n\n");

    head1 = DivideDireita(head_n1, d/2);
  //head2 = DivideEsquerda(head_n1,d/2);

    printf("\n Parte 1");
    printf("\n");
    imprimeLista(head1);  


    printf("\n Parte 2");

    printf("\n");
    //imprimeLista(head2);     
    printf("\n");
    getchar();

    return 0;

}


Numero * DivideDireita(Numero *a, int n)
 {
   Numero * novo;
   Numero * aux;
   aux= a->ant;
   novo = criaLista(1);

for(int i=0; i<n; i++)
{

    insereLista(novo,aux->num);
    aux = aux->ant;
}

return novo;
}


/*Retorna um numero com outro endereço*/

Numero * copia(Numero * a)
{

    Numero * nova, * aux;

    aux = a->ant;
    nova = criaLista(a->num); // cria nova cabeça igual a cabeça de a

    while(aux != a) { // percorre do final até o começo
        insereLista(nova, aux->num);
        aux = aux->ant;
    }
    return aux; // devolve a cabeça do numero copiado
}



int numeroDigitos(Numero * lst)
{
    Numero * aux;
    int i;

    i = 0;
    aux = lst->seg;
    while(aux != lst) {
        aux = aux->seg;
        i++;
    }
    return i;
}

/*Retorna um ponteiro para uma copia do numero*/
Numero *copiaNum(Numero *head) 
{
    Numero *aux = head->ant;
    Numero *copia = criaLista(0);
    while(aux != head){
        insereLista(copia, aux->num);
        aux = aux->ant;
    }
    return copia;
}



/*Gerar numeros entre 0 ou 1 se n=2*/
int gerarNumeros(int n){
    return rand() % n ;
}

void geraSeed() { /* gera uma seed para nova sequencia de numeros aleatorios */
    srand((unsigned)time(NULL));
}





void removeNumero(Numero * rm) { // desaloca a memória da célula indicada
    Numero * aux;

    if(rm->seg == rm) { // se a celula for a cabeça
        free(rm); // desaloca rm
    } else { 
        aux = rm->ant;
        aux->ant->seg = rm;
        rm->ant = aux->ant;
        free(aux); // desaloca aux
    }
}


void insereLista(Numero *lst, int num)
{
    Numero *novo;
    novo = (Numero*) malloc(sizeof(Numero));
    novo->num = num; //acessa nova e bota o endereço da pessoa1 lá dentro;

    if(lst->seg == lst) {
        novo->seg = lst;
        lst->seg = novo;
        novo->ant = lst;
        lst->ant = novo;
        return;
    }
    novo->seg = lst->seg;
    lst->seg = novo;
    novo->seg->ant = novo;
    novo->ant = lst;
}

void geraLista(Numero *numero, int numeros) 
{
    int i;
    i=0;
    while (i != numeros) { // deve ser colocado 256 digitos
        insereLista(numero, gerarNumeros(2)); //GERANDO NUMEROS DE 0-1 E GUARDANDO NA LISTA
        i++;
    }
}
/*Cria uma lista*/
Numero * criaLista(int n)
{
    Numero * head;
    head = (Numero *) malloc(sizeof(Numero));
    head->num = n;
    head->seg = head;
    return head;

}

/*Imprime a lista caso o primeiro numero tenha um -1 é porque*/
/*o numero é negativo                                        */
void  imprimeLista(Numero * lst)
{
    //int i;
    Numero * aux;
    aux = lst->seg;
    //i=0;
    /*Imprimir o sinal*/
    if(lst->num == -1)  {
        printf("-");
    }

    while(aux != lst)
    {
        printf("%i", aux->num);
        aux = aux->seg;
        //i++;

    }


}

EDIT CODE List to the left this returning to the contrary, I thought to make an insert at the end of the list because the function I implemented is inserting at the beginning, I want to optimize this without having to create a new function.

#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

struct celula {
    int num;
    struct celula * seg;
    struct celula * ant;
};

typedef struct celula Numero;



int gerarNumeros(int n);
int numeroDigitos(Numero * lst);
void geraSeed();
void geraLista(Numero *lst, int numeros);
void insereLista(Numero *lst, int num);
void imprimeLista(Numero * lst);
Numero * criaLista(int n);
Numero * DivideEsquerda(Numero *a, int n);
Numero * DivideDireita(Numero *a, int n);


int main() {
    Numero * head_n1, * head_n2, * resposta , *head1, *head2 ;
    int d;


    printf("Insira a quantidade de DIGITOS do seu numero binario\n");
    scanf("%i", &d);

    head_n1 = criaLista(1); 
    head_n2 = criaLista(1);
    head1 = criaLista(1);
    head2 = criaLista(1);
    printf("Criando os dois numeros... \n\n");

    geraLista(head_n1, d);
    geraLista(head_n2, d);

    imprimeLista(head_n1);

    printf("\n\n\n");

    head1 = DivideEsquerda(head_n1, d/2);
    head2 = DivideDireita(head_n1, d/2);

    printf("\n Parte 1");
    printf("\n");
    imprimeLista(head1);  

    printf("\n Parte 2");

    printf("\n");
    imprimeLista(head2);     
    printf("\n");
    getchar();

    return 0;

}


Numero * DivideEsquerda(Numero *a, int n)
{
Numero * esq;
Numero * aux;
aux= a->seg;
esq = criaLista(1);

for(int i=n; i>0; i--)
{
    insereListaFim(esq,aux->num);
    aux = aux->seg;

}
return esq;
}

Numero * DivideDireita(Numero *a, int n){
Numero * dir;
Numero * aux;
aux= a->ant;
dir = criaLista(1);

for(int i=0; i<n; i++)
{

    insereLista(dir,aux->num);
    aux = aux->ant;

}
return dir;
}

/*Retorna um numero com outro endereço*/

Numero * copia(Numero * a)
{

    Numero * nova, * aux;

    aux = a->ant;
    nova = criaLista(a->num); // cria nova cabeça igual a cabeça de a

    while(aux != a) { // percorre do final até o começo
        insereLista(nova, aux->num);
        aux = aux->ant;
    }
    return aux; // devolve a cabeça do numero copiado
}



int numeroDigitos(Numero * lst)
{
    Numero * aux;
    int i;

    i = 0;
    aux = lst->seg;
    while(aux != lst) {
        aux = aux->seg;
        i++;
    }
    return i;
}

/*Retorna um ponteiro para uma copia do numero*/
Numero *copiaNum(Numero *head) 
{
    Numero *aux = head->ant;
    Numero *copia = criaLista(0);
    while(aux != head){
        insereLista(copia, aux->num);
        aux = aux->ant;
    }
    return copia;
}



/*Gerar numeros entre 0 ou 1 se n=2*/
int gerarNumeros(int n){
    return rand() % n ;
}

void geraSeed() { /* gera uma seed para nova sequencia de numeros aleatorios */
    srand((unsigned)time(NULL));
}





void removeNumero(Numero * rm) { // desaloca a memória da célula indicada
    Numero * aux;

    if(rm->seg == rm) { // se a celula for a cabeça
        free(rm); // desaloca rm
    } else { 
        aux = rm->ant;
        aux->ant->seg = rm;
        rm->ant = aux->ant;
        free(aux); // desaloca aux
    }
}


void insereLista(Numero *lst, int num)
{
    Numero *novo;
    novo = (Numero*) malloc(sizeof(Numero));
    novo->num = num; //acessa nova e bota o endereço da pessoa1 lá dentro;

    if(lst->seg == lst) {
        novo->seg = lst;
        lst->seg = novo;
        novo->ant = lst;
        lst->ant = novo;
        return;
    }
    novo->seg = lst->seg;
    lst->seg = novo;
    novo->seg->ant = novo;
    novo->ant = lst;
}


void geraLista(Numero *numero, int numeros) 
{
    int i;
    i=0;
    while (i != numeros) { // deve ser colocado 256 digitos
        insereLista(numero, gerarNumeros(2)); //GERANDO NUMEROS DE 0-1 E GUARDANDO NA LISTA
        i++;
    }
}
/*Cria uma lista*/
Numero * criaLista(int n)
{
    Numero * head;
    head = (Numero *) malloc(sizeof(Numero));
    head->num = n;
    head->seg = head;
    return head;

}

/*Imprime a lista caso o primeiro numero tenha um -1 é porque*/
/*o numero é negativo                                        */
void  imprimeLista(Numero * lst)
{
    //int i;
    Numero * aux;
    aux = lst->seg;
    //i=0;
    /*Imprimir o sinal*/
    if(lst->num == -1)  {
        printf("-");
    }

    while(aux != lst)
    {
        printf("%i", aux->num);
        aux = aux->seg;
        //i++;

    }


}
c

  • The n of divide would be the bit Where would you split it into two lists ? But to have two lists the signature would have to be different and include the lists for the division, or return a structure consisting of 2 pointers of lists. These parts are not very clear

  • this n would be the size of digits that is d divided by 2 and the function that I’m trying to do is to return to half of the right and half of the left. List example end<->1<->1<->0<->1<->start return end<->0<->1<->start list and left list

  • void * Divide(Numero *a, int n) where these two halves will be in this function ?

  • I made an edit on the function I would like to return the two in the same function, I think return a pointer to the right part and one to the left part

  • This is C, there can only be one return value

  • Yes I forgot to update.

Show 1 more comment

2 answers

1

I only looked at the two functions that you quoted, so I know if you have something else to change, but in the right function it should be for(i=0; i < n; i++) and in the left one it should be for(i=n; i < (n*2)-1; i++), if n is the number of elements. That should split your list in half. The way you are doing the numbers will be the same in the two lists, in fact this way you put if the number of elements in the primary list is odd a number will be lost in this division, then choose one of the lists and treat this to q in case one end up with that number more, another thing I realized that q you leave pointers pointing pro nd, if your list is a circular list, then when creating it the head should be at the same time the previous and the next, if n is a circular list your pointers should point to NULL.

1

Follow your readjusted code from a doubly chained list. Just explain to me how you want to split the list. Based on what?

#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>

typedef struct nodo {
            int info;
            struct nodo *prox;
            struct nodo *ant;
} Nodo;

typedef struct {
    Nodo *primeiro;
} ListaDupla;

//Imprimir os elementos da lista na tela
void mostra(ListaDupla l){
     Nodo *p = l.primeiro;

     if (p != NULL) {
        while (p != NULL) {
            printf("%i ", p->info);
            p=p->prox;           
        }
    }
}

//Criar uma lista vazia
void cria(ListaDupla *lista) {
      lista->primeiro = NULL;
}

//Verificar se a lista á vazia
bool esta_vazia(ListaDupla l) {
    return l.primeiro == NULL;
}

//Aloca espaco de memoria para um novo nodo
Nodo *cria_nodo(int info) {
    Nodo * novo = (Nodo *)malloc(sizeof(Nodo));

    novo->info = info;
    novo->prox = NULL;
    novo->ant = NULL;
    return novo;
}

//Buscar um elemento qualquer na lista e retorná-lo (null se não encontrado)
Nodo *acha_elemento(ListaDupla *lista, int info) {
    Nodo *x = lista->primeiro;

    while (x != NULL && x->info != info) {
        x = x->prox;        
    }
    return x;
}

//Buscar o ultimo elemento
Nodo *acha_ultimo(ListaDupla *lista) {
    Nodo *x = lista->primeiro;

    if (x != NULL) {
        while (x->prox != NULL) {
            x = x->prox;
        }
        return x;
    }
    return NULL;
}

//Inserir um elemento no início da lista
void insere_inicio(ListaDupla *l, int i){
     Nodo *novo = cria_nodo(i);
     Nodo *p = l->primeiro, *anterior = NULL;

     while (p!=NULL && p->info < i) {
           anterior = p;
           p=p->prox;
     }
     novo->info=i;

     if (l->primeiro == NULL || anterior == NULL) { //lista vazia
       l->primeiro = novo;
     } else { // ou no inicio da lista
       anterior->prox = novo;
     }
     novo->prox = p;
     if (p != NULL) {//insere em lista vazia ou insere no final da lista
       p->ant=novo;
     }        
     novo->ant=anterior;     
}

//Inserir um elemento no fim da lista
void insere_fim(ListaDupla *lista, int info) {
    Nodo *ultimo = acha_ultimo(lista);

    if (ultimo != NULL) {
        Nodo *novo = cria_nodo(info);
        ultimo->prox = novo;
    } else {
        insere_inicio(lista, info);
    }   
}

//Retirar um elemento no final da lista
bool remove_fim(ListaDupla *lista) {
    if (!esta_vazia(*lista)) {
        Nodo *x = acha_ultimo(lista);

        if (x->ant == NULL && x->prox == NULL) { //unico elemento
            free(x);
            cria(lista);
        } else {
            Nodo *anterior = x->ant;

            anterior->prox = NULL;
            free(x);
        }
        return true;
    }
    return false;
}

//Retirar um elemento no inicio da lista
bool remove_inicio(ListaDupla *lista) { 
    if (!esta_vazia(*lista)) {
        Nodo *x = lista->primeiro;

        lista->primeiro = lista->primeiro->prox;
        lista->primeiro->ant = NULL;
        free(x);
        return true;
    }
    return false;
}

//Retirar um elemento qualquer da lista
bool remover(ListaDupla *l, int v) {
      Nodo *ant = NULL;
      Nodo *p = l->primeiro;

      while (p != NULL && p->info != v) {
            ant = p;
            p = p->prox;
      }
      if (p!=NULL) {         
         if (ant == NULL)
            l->primeiro=p->prox;
         else
            ant->prox=p->prox;
         free(p);
         return true;
      }
      return false;
}

/*Gerar numeros entre 0 ou 1 se n=2*/
int gerarNumeros(int n){
    return rand() % n ;
}

void geraSeed() { /* gera uma seed para nova sequencia de numeros aleatorios */
    srand((unsigned)time(NULL));
}

void geraLista(ListaDupla *numero, int numeros) 
{
    int i;
    i=0;
    while (i != numeros) { // deve ser colocado 256 digitos
        insere_fim(numero, gerarNumeros(2)); //GERANDO NUMEROS DE 0-1 E GUARDANDO NA LISTA
        i++;
    }
}

int main() {
    ListaDupla lista;//, lista_esq, lista_dir;
    int d;

    cria(&lista);
    printf("Insira a quantidade de DIGITOS do seu numero binario\n");
    scanf("%i", &d);
    printf("Criando o numero... \n\n");
    geraLista(&lista, d);
    mostra(lista);
    printf("\n\n\n");
    return 0;
}

  • i put the division code I made it looks like this working a detail only splits lists of even size.

  • What happens when the list has odd size?

  • I already arranged it is only you pass the value Ceil and floor that it divides.

  • Glad I could help. Hug

Browser other questions tagged c

You are not signed in. Login or sign up in order to post.