Zásobník

Priehradkové triedenie

Program   EXE

/* pripojenie potrebných hlavičkových súborov */
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>

/* symbolické konštanty */
#define K 5
#define N 7

typedef struct prvok {
  char cifry[K];      /* pole cifier daného čísla */
  struct prvok *dalsi;
} TPrvok;
--------------------------------------------------------------------------------------
void vloz(long cislo, TPrvok **v)
{
  int j;
  
  /* nový prvok */
  TPrvok *pom = (TPrvok*)malloc(sizeof(TPrvok));
  
  /* "rozbitie" čísla na cifry */
  for (j = K-1; j >= 0; j--) {     
     pom->cifry[j] = cislo % 10;  
     cislo = cislo / 10;
  }
 
  pom->dalsi = *v;
  *v = pom;        /* nový vrch zásobníka */
}
--------------------------------------------------------------------------------------
void presun(TPrvok **p1, TPrvok **p2) /* presun prvku z jedného zásobníka do iného */
{
  TPrvok *pom;

  pom = *p1;      
  *p1 = (*p1)->dalsi;  
  pom->dalsi = *p2;  
  *p2 = pom;   
}
--------------------------------------------------------------------------------------
void vstup(TPrvok **v) /* vytvorenie hlavného zásobníka */ 
{
  long cislo;
  int i;
 
  clrscr();
  printf("\nZadaj postupne  %d  najviac %d-cifernych prirodzenych cisel:\n", N, K);
  
  for (i = 1; i <= N; i++) {
    printf ("%d. cislo = ", i);
    scanf("%ld", &cislo);
    vloz(cislo, v);  /* vlož prvok do zásobníka */
  }
}
--------------------------------------------------------------------------------------
void vypis(TPrvok *p)
{
  int i, j;
 
  for (i = 1; i <= N; i++) { 
    printf("\n%d. cislo : ", i);
    for (j = 0; j < K; j++) printf("%d",p->cifry[j]);
    p = p->dalsi;
  }
}
--------------------------------------------------------------------------------------
void tried(TPrvok **v)
{
  TPrvok *priehradka[10]; /* pomocné zásobníky */
  int i, j;       

  /* vytvorenie prázdnych priehradok */
  for (i = 0; i < 10; i++) priehradka[i] = NULL;
  
  /* čísla majú K cifier, preto K prechodov */
  for(i = K-1; i >= 0; i--) {
    
    /* z hlavného zásobníka do priehradok */
    while (*v != NULL) presun(v, &priehradka[(*v)->cifry[i]]);
    
    /* z priehradok spä? do hlavného zásobníka */
    for (j = 0; j < 10; j++) {
       while (priehradka[j] != NULL) presun(&priehradka[j], v);
    }
  }
}
--------------------------------------------------------------------------------------
void main(void) /* hlavný program */
{
  TPrvok *vrch;

  /* vytvorenie prázdneho hlavného zásobníka */
  vrch = NULL; 

  /* načítanie vstupnej číselnej postupnosti */
  vstup(&vrch);
  clrscr();

  printf("\n\nPovodny zasobnik\n" );
  vypis(vrch);

  tried(&vrch);

  /* výstup */
  printf("\n\nUtriedeny zasobnik\n" );
  vypis(vrch);
  getch();
}