Merge sort em C

C

09/09/2020

Boa noite!

Estou implementando uma lista sequencial e preciso ordenar meu elementos, então coloquei o Merge sort para fazer isso, só que está dando um erro:

ListaSequencial.c: In function ‘merge’:
ListaSequencial.c:152:19: error: request for member ‘A’ in something not a structure or union
152 | l->A[comAux] = Aux->A[comAux-inicio];

Por favor, quem puder me ajudar, agradeço.

#include <stdio.h>
#include <stdlib.h>
#define MAX 50
#define ERRO -1
#define true 1
#define false 0

typedef int bool;

typedef int TIPOCHAVE;

typedef struct{
  TIPOCHAVE chave;
  // outros campos...
} REGISTRO;

typedef struct {
  REGISTRO A[MAX+1];
  int nroElem;
} LISTA;

/* Inicialização da lista sequencial (a lista já está criada e é apontada 
pelo endereço em l) */
void inicializarLista(LISTA* l){
  l->nroElem = 0;
} /* inicializarLista */

/* Exibição da lista sequencial */
void exibirLista(LISTA* l){
  int i;
  printf("Lista: " ");
  for (i=0; i < l->nroElem; i++)
    printf("%i ", l->A[i].chave); // só lembrando TIPOCHAVE = int
  printf(""\n");
} /* exibirLista */ 

/* Retornar o tamanho da lista (numero de elementos "validos") */
int tamanho(LISTA* l) {
  return l->nroElem;
} /* tamanho */

/* Retornar o tamanho em bytes da lista. Neste caso, isto nao depende do numero
   de elementos que estao sendo usados, pois a alocacao de memoria eh estatica.
   A priori, nao precisariamos do ponteiro para a lista, vamos utiliza-lo apenas
   porque teremos as mesmas funcoes para listas ligadas.   
*/
int tamanhoEmBytes(LISTA* l) {
  return sizeof(LISTA);
} /* tamanhoEmBytes */

/* Retornar a chave do primeiro elemento da lista sequencial (caso haja) e ERRO
   caso a lista esteja vazia */
TIPOCHAVE primeiroElem(LISTA* l){
  if(l->nroElem > 0) return l->A[0].chave;
  else return ERRO; // lista vazia
} /* primeiroElem */

/* Retornar a chave do ultimo elemento da lista sequencial (caso haja) e ERRO
   caso a lista esteja vazia */
TIPOCHAVE ultimoElem(LISTA* l) {
  if(l->nroElem > 0) return l->A[l->nroElem-1].chave;
  else return ERRO; // lista vazia
} /* ultimoElem */

/* Retornar a chave do elemento que está na posição n da LISTA. Lembre-se que as posicoes do
   arranjo A vao de 0 a MAX-1  */
TIPOCHAVE enesimoElem(LISTA* l, int n) {
  if( (n >= 0) && (n < l->nroElem)) return l->A[n].chave ;
  else return ERRO;
} /* enesimoElem */

/* Reinicializar a estrutura */
void reinicializarLista(LISTA* l) {
  l->nroElem = 0;
} /* reinicializarLista */

/* Inserção "direta" na iésima posição (posicao i do arranjo A).
   Funciona da mesma maneira de um insertionSort: deve-se deslocar todos os
   elementos a partir da iesima posicao e entao se insere o novo elemento. */
bool inserirElemLista(LISTA* l, REGISTRO reg, int i){
  int j;
  if ((l->nroElem >= MAX) || (i < 0) || (i > l->nroElem)) 
     return(false); // lista cheia ou índice inválido
  for (j = l->nroElem; j > i; j--) l->A[j] = l->A[j-1];
  l->A[i] = reg;
  l->nroElem++;
  return true;
} /* inserirElemLista */

/* Busca sequencial em lista ordenada ou não SEM SENTINELA */
int buscaSequencial(LISTA* l, TIPOCHAVE ch) {
  int i = 0;
  while (i < l->nroElem){
    if(ch == l->A[i].chave) return i; // achou
    else i++;
  }
  return ERRO; // não achou
} /* buscaSequencial */


/* Exclusão do elemento cuja chave seja igual a ch */
bool excluirElemLista(LISTA* l, TIPOCHAVE ch) { 
  int pos, j;
  pos = buscaSequencial(l,ch);
  if(pos == ERRO) return false; // não existe
  for(j = pos; j < l->nroElem-1; j++) l->A[j] = l->A[j+1];
  l->nroElem--;
  return true;
} /* excluirElemLista */


/* Busca sequencial em lista COM SENTINELA (vetor criado com MAX+1 posições) */
int buscaSentinela(LISTA* l, TIPOCHAVE ch) {
  int i = 0;
  l->A[l->nroElem].chave = ch; // sentinela
  while(l->A[i].chave != ch) i++;
  if (i > l->nroElem -1) return ERRO; // não achou
  else return i;
} /* buscaSentinela */

void merge(LISTA* l, int inicio, int meio, int fim) { //Intercalação.
int com1 = inicio, com2 = meio+1, comAux = 0, tam = fim-inicio+1;
int *Aux;

Aux = (int*) malloc(tam*sizeof(int));


while (com1 <= meio && com2 <= fim) {
if (l->A[com1].chave < l->A[com2].chave) { //Compara os dois vetores e guarda na variável r.
Aux[comAux] = l->A[com1].chave;
com1++; 

}else {
 Aux[comAux] = l->A[com2].chave;
 com2++;
}
comAux++;
}

 while(com1 <= meio){  //Caso ainda haja elementos na primeira metade
  Aux[comAux] = l->A[com1].chave;
  comAux++;
  com1++;
}
while(com2 <= fim) {   //Caso ainda haja elementos na segunda metade
 Aux[comAux] = l->A[com2].chave;
 comAux++;
 com2++;
    }

for(comAux = inicio; comAux <= fim; comAux++){ //Move os elementos de volta para o vetor original
l->A[comAux] = Aux->A[comAux-inicio];
    }
    
    free(Aux); //Limpa a memória.
}

//Código de ordenação, usando o conceito do MergeSort.
void ordenar(LISTA* l, int inicio, int fim) {

if (inicio < fim) { //Caso minha função seja menor que o fim.

int meio = ((inicio+fim)/2); //Divida meu conjunto em duas partes e o floor é para arredondar. 
ordenar(l,inicio,meio);
ordenar(l,meio+1,fim); //Chama a função para as duas metades. 
merge(l,inicio,meio,fim);//Unir as partes.
   }
}

int main(){
  LISTA lista;
  inicializarLista(&lista);
  exibirLista(&lista);
  printf("Numero de elementos na lista: %i.\n",tamanho(&lista));
  printf("Tamanho da lista (em bytes): %i.\n",tamanhoEmBytes(&lista));
  REGISTRO reg;
  reg.chave = 9;
  inserirElemLista(&lista,reg,0);
  exibirLista(&lista);
  reg.chave=3;
  inserirElemLista(&lista,reg,1);
  reg.chave=4;
  inserirElemLista(&lista,reg,2);
  reg.chave=1;
  inserirElemLista(&lista,reg,3);
  reg.chave=12;
  inserirElemLista(&lista,reg,2);
  exibirLista(&lista);
  printf("Numero de elementos na lista: %i.\n",tamanho(&lista));
  printf("Tamanho da lista (em bytes): %i.\n",tamanhoEmBytes(&lista));
  printf("Chave 4 encontrada na posicao: %i do arranjo A.\n",buscaSequencial(&lista,4));
  printf("Chave 4 encontrada na posicao: %i do arranjo A.\n",buscaSentinela(&lista,4));
  if (excluirElemLista(&lista,4)) printf("Exclusao bem sucedida: 4.\n");
  if (excluirElemLista(&lista,8)) printf("Exclusao bem sucedida: 8.\n");
  if (excluirElemLista(&lista,9)) printf("Exclusao bem sucedida: 9.\n");
  exibirLista(&lista);
  printf("Numero de elementos na lista: %i.\n",tamanho(&lista));
  printf("Tamanho da lista (em bytes): %i.\n",tamanhoEmBytes(&lista));
  reinicializarLista(&lista);
  exibirLista(&lista);
  printf("Numero de elementos na lista: %i.\n",tamanho(&lista));
  printf("Tamanho da lista (em bytes): %i.\n",tamanhoEmBytes(&lista));
  
  return 0;
}
Lucas

Lucas

Curtidas 0
POSTAR