Zásobník

Priehradkové triedenie

Program Spustiteľná verzia

/* 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();
}