3. Jednosmerný lineárny zoznam

3.8  Problém - Súčet veľkých prirodzených čísel

   Napíšte program, ktorý umožní sčítať dve ľubovoľne veľké prirodzené čísla, ktoré môžete načítať aj zo vstupného súboru. Výstupom programu bude výpis súčtu na obrazovku.

Riešenie

Možno ste si práve pomysleli: "Sčitať dve prirodzené čísla predsa nie je žiadny problém!" To skutočne nie je, pokiaľ nepotrebujeme sčítať také dve prirozené čísla, ktoré sú väčšie ako maximálna možná hodnota použitého údajového typu (napr. long), prípadne oba sčítance síce sú s dovoleného rozsahu, avšak príslušný súčet už nie.

Chceme sčítať dve čísla, ktorých počet cifier nie je vopred známy ani ničím obmedzený (azda len kapacitou pamäte :-) Preto využijeme pri riešení dynamickú údajovú štruktúru a veľké prirodzené číslo budeme reprezentovať linárnym zoznamom svojich číslic.

Tento lineárny zoznam bude tvorený prvkami typu TUzol :

typedef struct uzol {
   int cifra;
   struct uzol *dalsi;
} TUzol;

Pre potreby sčítania je vhodné použiť takú orientáciu zoznamu, aby na jeho začiatku bola číslica najnižšieho rádu. Čísla načítame cifru po cifre zo vstupných textových súborov, pričom každú novú cifru pridáme na začiatok príslušného zoznamu - to znamená, že cifry budú v zozname uložené v opačnom poradí ako na vstupe.

Ak by na vstupe boli čísla:

A = 1234567890
B =  904246128

vytvorené zoznamy budú vyzerať takto:



Pri sčítovaní čísel využijeme bežný postup známy zo základnej školy:



Na zapamätanie prenosu z nižšieho do vyššieho rádu budeme potrebovať pomocnú premennú.

Zoznam, v prvkoch ktorého si uložíme číslice výsledného súčtu, vytvárame postupne pri sčitovaní. Vzhľadom na to, že pri sčitovaní postupujeme od najnižšieho rádu a každú ďalšiu získanú cifru súčtu pridáme na začiatok zoznamu, po skončení výpočtu budú cifry výsledku v "správnom" poradí.

Nesmieme tiež zabudnúť na to, že čísla nemusia mať rovnaký počet cifier!

Číslice súčtu budú na konci uložené v lineárnom zozname:



Stačí už len vypísať prvky zoznamu na obrazovku.

[Program]