inverteSubconjuntos.c

/*Diseñe e implemente una función que reciba una lista enlazada e invierta grupos de k nodos
adyacentes.
Por ejemplo
Si la lista es 1-2-3-4-5-6 y k=2 la lista debe ser 2-1-4-3-6-5
Si la lista es 6-1-9-4-2-5-8-3-0-7 y k=2 la lista será: 1-6-4-9-5-2-3-8-7-0
Si la lista es 6-1-9-4-2-5-8-3-0-7 y k=3 la lista será: 9-1-6-5-2-4-0-3-8-7
- El lenguaje de programación a utilizar es C
- Evite utilizar variables globales.
- El uso de estructuras FIFO o LIFO quedan a criterio del programador.
- Lenguaje de programación libre (c/Java).
- El programa debe organizado en funciones o métodos.
- La cantidad de elementos es indefinida.
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<windows.h>
#define N 6

struct nodo {
  int dato;
  struct nodo *sig;
};

struct nodop {
  int dato;
  struct nodop *ant;
};

int cuentaNodos(struct nodo *inicio) {
  struct nodo *aux;
  int contador = 0;
  aux = inicio;
  while (aux != NULL) {
    contador++;
    aux = aux->sig;
  }
  return contador;
}

struct nodo *crearNodo(int dato) {
  struct nodo *aux;
  aux = (struct nodo *)malloc(sizeof(struct nodo));
  aux->dato = dato;
  aux->sig = NULL;
  return aux;
}

struct nodop *crearNodoP(int dato) {
    struct nodop *aux;
    aux = (struct nodop *)malloc(sizeof(struct nodop));
    aux->dato = dato;
    aux->ant = NULL;
    return aux;
  }

struct nodop *push(struct nodop *tope,int dato) {
  struct nodop *aux;
  aux = crearNodoP(dato);
  if(tope == NULL)
    tope = aux;
  else {
    aux->ant = tope;
    tope = aux;
  }
  return tope;
}

void insertar(struct nodo **inicio, int dato) {
  struct nodo *p,*q = NULL,*aux;
  aux = crearNodo(dato);
  p = *inicio;
  while (p != NULL) {
    q = p;
    p = p->sig;
  }
  if(q == NULL)
    *inicio = aux;
  else
    q->sig = aux;
}

int pop(struct nodop **tope) {
  int valor = 0;
  struct nodop *aux;
  aux = *tope;
  valor = aux->dato;
  *tope = (*tope)->ant;
  free(aux);
  return valor;
}

int remover(struct nodo **inicio) {
  int valor = 0;
  struct nodo *aux;
  aux = *inicio;
  valor = aux->dato;
  *inicio = (*inicio)->sig;
  free(aux);
  return valor;
}

void mostrar(struct nodo *inicio) {
  struct nodo *aux;
  if(!inicio)
    printf("\nVacia!");
  else {
    aux = inicio;
    while (aux != NULL) {
      printf("%d - ", aux->dato);
      aux =  aux->sig;
    }
    getch();
  }
}

void mostrarP(struct nodop *tope) {
  struct nodop *aux;
  if(!tope)
    printf("\nVacia!");
  else {
    aux = tope;
    while (aux != NULL) {
      printf("\n%d", aux->dato);
      aux =  aux->ant;
    }
    getch();
  }
}

void generaLista(struct nodo **inicio) {
  int i = 0;
  for (i = 0; i < N; i++) {
    insertar(inicio,rand()%50);
  }
}

int main() {
  int sub = 0,nodos = 0,valor = 0, k = 0, cont = 0;
  struct nodo *inicio = NULL;
  struct nodo *inicio2 = NULL;
  struct nodop *tope = NULL;
  generaLista(&inicio);
  nodos = cuentaNodos(inicio);
  printf("\n\nLista original: \n");
  mostrar(inicio);
  printf("\nNodos: %d",nodos);
  printf("\nIngrese el valor de k: ");
  scanf("%d",&k);
  printf("\nNumero de subgrupos de: %d",nodos/k);
  if(nodos%k != 0) {
    while (sub < (nodos/k)) {
      cont = 0;
      while(cont < k) {
        valor = remover(&inicio);
        tope = push(tope,valor);
        cont++;
      }
      cont = 0;
      while (cont < k) {
        valor = pop(&tope);
        insertar(&inicio2,valor);
        cont++;
      }
      sub++;
    }
    insertar(&inicio2,remover(&inicio));
  }
  else {
    while (sub < (nodos/k)) {
      cont = 0;
      while(cont < k) {
        valor = remover(&inicio);
        tope = push(tope,valor);
        cont++;
      }
      cont = 0;
      while (cont < k) {
        valor = pop(&tope);
        insertar(&inicio2,valor);
        cont++;
      }
      sub++;
    }
  }
  printf("\nResultado: \n");
  mostrar(inicio2);
  return 0;
}