while (k<=n/2) { j=k+k; if (j<n && h[j]>h[j+1]) j++; /* zde změnit relace, */ if (r<=h[j]) break; /* chceme-li třídit vzestupně */ h[k]=h[j]; k=j; } h[k]=r;
} void heapsort(int h[], int n) { int k,t; for(k=n/2; k>=1;k--) halda(h,n,k); while(n>1) { t=h[1]; h[1]=h[n]; h[n]=t; halda(h,--n,1); } } int main() { int i,pocet; int pole[21]; int cislo; /* clrscr(); */ printf("Zadejte pocet cisel k setrideni:(max 20)\n"); scanf("%d",&pocet); for (i=1;i<=pocet;i++) { printf("Zadejte cislo do pole: \n"); scanf("%d",&cislo); pole[i] = cislo; } heapsort(pole,pocet); printf("Setridene pole: \n"); for (i=1;i<=pocet;i++) printf("%d\n",pole[i]); getch(); return(0); }
98 Algoritmy v jazyku C a C++
Ukázka elektronické knihy, UID: KOS182815
7.
eprezentace R aritmetického výrazu binárním stromem
Obrázek 7.1: Reprezentace aritmetického výrazu binárním stromem
Binární strom na obrázku 7.1 představuje aritmetický výraz ((47+15) * (16-12))/(3+1) Průchod stromem do hloubky poskytuje trojí možnost, jak zobrazit data ve vrcholech stromu: preorder, inorder a postorder (viz odstavec 6.4). Tyto tři způsoby odpovídají třem různým notacím pro aritmetické výrazy: 1. Infixová notace odpovídá zápisu, na jaký jsme zvyklí, tedy ((47+15) * (16-12)) / (3+1) 2. Postfixová notace, které se taky říká reverzní nebo polský zápis, je pro tento výraz 47 15 + 16 12 - * 3 1 + / Zajímavé je, že nepotřebujeme závorky, a přesto dokážeme výraz správně vyhodnotit. Tato notace se používala ve starších kalkulačkách. 3. Prefixová notace: / * + 47 15 – 16 12 + 3 1 Stojí za povšimnutí, že pořadí operandů je ve všech notacích stejné.
7.1 Vyhodnocení výrazu zadaného v postfixové notaci Program čte zleva doprava výraz v postfixové notaci, operandy ukládá do zásobníku. Přečte-li binární operátor, vyjme ze zásobníku dva operandy, provede operaci a výsledek uloží do zásobníku. U nekomutativních operací odčítání a dělení je číslo z vrcholu zásobníku pravým operandem, číslo vybrané jako druhé je levým operandem. Program předpokládá, že zadaný výraz v postfixové notaci je správný, kontrolují se jen některé možné chyby, zejména takové, které neumožňují pokračovat v analýze výrazu. Je použita funkce isdigit, která vrací nenulovou hodnotu (true), je-li
Reprezentace aritmetického výrazu binárním stromem 99
Ukázka elektronické knihy, UID: KOS182815
jejím argumentem číslice, funkce atof pro převod znakového řetězce na číslo v pohyblivé čárce a funkce strlen, která vrací délku znakového řetězce. Algoritmus má lineární časovou složitost, délka vstupního výrazu je omezena na 100 znaků, délka operandu může být max. 10 znaků, počet operátorů ve výrazu smí být nejvýše 20. /* Funkce pro realizaci kalkulačky s postfixovou notací */ #include <stdio.h> #include <conio.h> double Op[20]; /* zásobník pro operandy */ int sp; /* ukazovátko v zásobníku */ int main() { char radek[100]; char s[10]; double Op1,Op2; char c; int i,j,k,BylaTec; sp = 0; /* inicializace zásobníku */ for (i=1;i<100;i++) radek[i]=' '; for (j=1;j<10;j++) s[j]=0; printf("Zadejte výraz v postfixové notaci:\n"); j=strlen(gets(radek)); radek[j]='='; /* zarážka */ i=0; zac: while(radek[i]==' ') i++; c=radek[i]; if(c!='.' && !isdigit(c)) { /* operator */ if ((c!='=') && (sp<2)) { printf("nespravny vyraz\n"); getch(); return; } if (c!='=') { Op2=Op[--sp]; Op1=Op[--sp]; } switch (c) { case '+': Op[sp++]=Op1+Op2; break; case'-': Op[sp++]=Op1-Op2; break; case'/': if (Op2!=0) Op[sp++]=Op1/Op2; else
100 Algoritmy v jazyku C a C++
Ukázka elektronické knihy, UID: KOS182815