Sorting in Double-chained List Circular in C

Question

Sorting in Double-chained List Circular in C

Navigation

#1 by (0 votes)

0

I need a little help here with Double-chained Circular List to solve a bigger problem.

I need to do a function that already inserts my elements in descending order. My code even works with entries that only need to be reversed. Ex: 1 2 3 4 5 6 , which exits 6 5 4 3 2 1 . The problem is with entries of type 6 3 9 8 ... Where do you think the problem is?

struct elemento{
  int altura;
  struct elemento *anterior;
  struct elemento *proximo;
 };
 typedef struct elemento Item;

typedef struct{
    int tamanhoLista;
    Item *primeiro;
    Item *ultimo;
}LCD_DE;

    void Inserir(LCD_DE *l){
    Item *novo = (Item*)malloc(sizeof(Item));

    scanf("%d",&novo->altura);

    if(l->tamanhoLista == 0){
        l->primeiro = novo;
        l->ultimo = novo;
        novo->anterior = novo;
        novo->proximo =  novo;
    }
    else{
        if(novo->altura >= l->primeiro->altura){  //antes do primeiro
            l->primeiro->anterior = novo;
            l->ultimo->proximo = novo;
            novo->anterior = l->ultimo;
            novo->proximo = l->primeiro;
            l->primeiro = novo;
        }
        else if(novo->altura < l->ultimo->proximo->altura){ //depois do ultimo
            l->ultimo->proximo = novo;
            l->primeiro->anterior = novo;
            novo->anterior = l->ultimo;
            novo->proximo = l->primeiro;
            l->ultimo = novo;
        }
        else{
            Item *i,*j,*k,*aux;
            for(i=l->primeiro;i!=l->primeiro;i=i->proximo){
                for(j=l->primeiro->proximo;j!=l->primeiro;j=j->proximo){
                    k=j->proximo;
                    if(novo->altura >= j->altura){
                        i->proximo = novo;
                        novo->anterior = i;
                        j->anterior = novo;
                        novo->proximo = j;
                    }
                    else if(novo->altura < j->altura){
                            j->proximo = novo;
                            novo->anterior = j;
                            k->anterior = novo;
                            novo->anterior = k;
                    }
                }

            }
        }
    }
     l->tamanhoLista++;
}

c lista lista-encadeada

asked by anonymous 02.10.2016 / 22:17

1 answer

Call activity after the thread is executed Querying multiple MySQL data

score 0 · Accepted Answer

I find it difficult to find this type of problem with pointers, I preferred to create a new example.

#include <stdlib.h>
#include <stdio.h>

typedef struct Item
{
   int height;
   struct Item* prev;
   struct Item* next;
} Item;

typedef struct
{
   int size;
   Item* first;
   Item* last;
} List;

static void insert(List *list, int height)
{
   printf("* ===\n");

   Item *newItem = (Item*)malloc(sizeof(Item));
   newItem->height = height;

   if (list->size == 0)
   {
      printf("* inserindo elemento %d em lista vazia\n", height);
      list->first = newItem;
      list->last = newItem;
      newItem->prev = newItem;
      newItem->next = newItem;
      list->size = 1;
      return;
   }

   if (height > list->first->height)
   {
      printf("* inserindo elemento %d antes do primeiro\n", height);
      list->first->prev = newItem;
      list->last->next = newItem;
      newItem->prev = list->last;
      newItem->next = list->first;
      list->first = newItem;
      list->size++;
      return;
   }

   if (height < list->last->height)
   {
      printf("* inserindo elemento %d depois do ultimo\n", height);
      list->last->next = newItem;
      list->first->prev = newItem;
      newItem->prev = list->last;
      newItem->next = list->first;
      list->last = newItem;
      list->size++;
      return;
   }

   printf("* inserindo elemento %d intermediario\n", height);
   Item* item = list->first;
   for (int i = 0; i < list->size; i++)
   {
      if (item->height < height)
         break;
      item = item->next;
   }

   item->prev->next = newItem;

   newItem->prev = item->prev;
   newItem->next = item;

   item->prev = newItem;

   list->size++;
}

static void print(List* list)
{
   printf("* ---\n");
   printf("* tamanho da lista: %d\n", list->size);
   Item* item = list->first;
   for (int i = 0; i < list->size; i++)
   {
      printf("* list[%d] = %d\n", i, item->height);
      item = item->next;
   }
}


int main(void)
{
   List list = { 0 };
   print(&list);

   insert(&list, 7);  // primeiro elemento
   print(&list);

   insert(&list, 2); // antes do primeiro elemento
   print(&list);

   insert(&list, 13); // depois do ultimo elemento
   print(&list);

   insert(&list, 9);  // elemento intermediario
   print(&list);
}

See link