PROGRAMOWANIE – PRZYKŁADY
IDE C++ WinBGI C# Wpadki

Przykład C++

Porządkowanie pliku rekordów Argumenty programu Program wyświetlania pliku rekordów Program mieszania rekordów pliku Moduł porównywania łańcuchów Program sortowania pliku rekordów Poprzedni przykład Następny przykład Kontakt

Porządkowanie pliku rekordów

Jednym z ważniejszych zagadnień informaty­cznych jest porządko­wanie elementów zbioru zwane sorto­waniem. Polega ono na usta­wieniu elementów w okre­ślonym porządku w celu ułatwienia ich wyszuki­wania lub przeglą­dania w wygodnej kolejności. Zajmiemy się porządko­waniem pliku binarnego złożonego z rekordów zawiera­jących pola: imię osoby, jej nazwisko, płeć, data urodzenia, numer telefonu i adres e-mail. Struktura rekordów o nazwie Osoba jest zdefinio­wana w pliku osoby.h (zob. Tworzenie i edycja pliku rekordów). Kluczem sortowania pliku jest nazwisko+­imię+data urodzenia z uwzglę­dnieniem polskich znaków diakry­tycznych kodowanych w stan­dardzie CP852 i polskiego alfabetu uzupeł­nionego o litery Q, V i X.

W programie sortowania wszystkie rekordy pliku są wczytywane do uporządko­wanej listy jednokie­runkowej, a potem zapisywane z powrotem do pliku w kolejności ich występowania w liście. Dwa inne programy uzupeł­niające dotyczą wyświe­tlania rekordów opartego na przewijaniu ekranu oraz rozpra­szania (mieszania) rekordów – operacji odwrotnej do porządko­wania. Domyślnie wszystkie programy działają na pliku Osoby.dta o rekordach typu Osoba, ale w wierszu polecenia można podać inną nazwę pliku o takiej samej strukturze rekordów.

Argumenty programu

Najczęściej funkcję main definiuje się bez argumentów. Funkcja ta może jednak mieć dwa argumenty określa­jące liczbę parametrów wywo­łania programu w wierszu polecnia (zmienna typu int) i ich wartości (tablica łańcuchów znakowych typu char**). Zwycza­jowo argu­menty te nazywane są argcargv. Gdy program zaczyna działać, ich wartości otrzymuje od systemu operacyj­nego. Oto przykła­dowy program o takiej budowie funkcji głównej wypisu­jący wszystkie parametry wiersza polecenia, które go uruchomiło:

#include <iostream>

int main(int argc, char *argv[])
{
    for (int k = 0; k < argc; k++)
        std::cout << argv[k] << std::endl;
    return 0;
}

Jeśli np. wiersz polecenia ma postać:

    argprog Ala ma 28 lat.

to do uruchamianego przez niego programu argProg.exe przekazana zostaje liczba 5 i tablica pięciu łańcuchów:

    argprog
    Ala
    ma
    28
    lat.

Łańcuch o indeksie zero zawsze określa polecenie uruchamia­jące program. W przypadku Borland C++ zostaje ono uzupeł­nione do pełnej ścieżki dostępu i pełnej nazwy programu (rys.), co pozwala progra­mowi na uzyskanie infor­macji o sobie samym.

Parametry wywołania programu można również precyzować bezpo­średnio w środo­wisku programi­stycznym, wpisując je wszystkie z pomi­nięciem łańcucha o indeksie zero w stosownym oknie przywoły­wanym za pomocą polecenia:

Program wyświetlania pliku rekordów

Budowę programu konsolowego wyświetlającego rekordy typu Osoba pliku binarnego zaczynamy od zaprojekto­wania wyglądu ekranu. Przyjmiemy, że wiersze 1-2 służą do wyświe­tlenia nagłówka, w wierszach 3-23 są pokazywane rekordy pliku – po jednym w wierszu (liczba porządkowa od 1 wzwyż, nazwisko i imię osoby oraz numer telefonu i adres e-mail), a w wierszach 24-25 menu informu­jące, jak sterować programem (rys.). Linie poziome w nagłówku i menu ograni­czają część przewijaną ekranu, poprawiając tym samym estetykę wyświe­tlanego obrazu.

Liczbę wierszy ekranu określamy za pomocą stałej NE typu całko­witego, przez co program stanie się bardziej przej­rzysty, a ponadto będzie go łatwo dosto­sować do innego rozmiaru okna konsoli, gdy zajdzie taka potrzeba. Definiujemy też pięć zmiennych globalnych ułatwia­jących komuni­kację funkcji składo­wych programu z plikiem i pobranym z niego rekordem oraz określa­jących liczbę wszystkich rekordów pliku i precyzu­jących, które z nich są w danym momencie wyświe­tlane:

ifstream plik;                  // Plik rekordów
Osoba rec;                      // Aktualnie wczytany rekord
int n;                          // Liczba rekordów pliku
int p, k;                       // Nr pierwszego i ostatniego wyśw. rekordu

W tym miejscu należy zastanowić się nad strukturą programu. Rozsądnym wydaje się wyodręb­nienie trzech ważnych funkcji, które nazwiemy init, nextprev. Pierwsza zostanie wywołana w funkcji main tylko raz (bezpo­średnio po uzyskaniu liczby rekordów pliku i wypisaniu nagłówka) w celu wyświe­tlenia początko­wego fragmentu pliku i usta­wienia wartości początkowych zmiennych pk, zaś dwie pozostałe za każym razem, gdy użytko­wnik naciśnie strzałkę w dół (Dn) lub w górę (Up), by przewinąć ekran o jeden wiersz w górę lub w dół i pokazać inny fragment pliku przesu­nięty o jeden rekord w kierunku końca lub początku. Wszystkie trzy funkcje będą odwoływać się do pomocni­czych, prostych do sformuło­wania funkcji showmenu. Zadaniem funkcji show jest wyświe­tlenie liczby porządkowej przeka­zanej w argu­mencie i pól rekordu zapamię­tanego w zmiennej rec, a funkcji menu wyświe­tlenie menu informu­jącego o dostę­pnych klawiszach steru­jących. Funkcja init może wyglądać następu­jąco:

void init()
{
    p = 1;
    for (k = 0; k < NE - 4 && k < n; )
    {
        plik.read((char *)&rec, sizeof(rec));
        show(++k); cout << endl;
    }
    menu();
}

Przewijanie ekranu w funkcjach nextprev można zaprogra­mować, korzy­stając z funkcji dellineinsline dostę­pnych w biblio­tece conio (Borland C++) lub zdefinio­wanych w module obsługi konsoli bconio (MinGW C++ i Visual C++). Pierwsza usuwa wiersz, w którym znajduje się kursor, a druga wstawia w tym miejscu pusty wiersz. Dokła­dniej mówiąc, delline przesuwa o jedną pozycję w górę wszystkie wiersze położone poniżej kursora i czyści wiersz ostatni, natomiast insline przesuwa o jedną pozycję w dół wszystkie wiersze od kursora do wiersza przedosta­tniego, który zajmie miejsce ostatniego, i czyści wiersz, w którym ustawiony jest kursor.

Formułowanie funkcji next najlepiej rozpocząć od wyczyszczenia dwóch wierszy menu, by ich tekst nie przeszka­dzał przy przewi­janiu ekranu. Następnie trzeba usunąć wiersz o numerze 3 (przewinąć ekran o jedną pozycję w górę), a po wczytaniu rekordu o numerze k do bufora wyświetlić go. Niezwykle ważne jest, by w odpo­wiednim momencie zwiększyć wartości zmiennych pk o 1, ponieważ początek i koniec wyświe­tlanego fragmentu pliku zostaje przesu­nięty o jeden rekord w kierunku końca pliku. Na koniec należy wyświetlić menu. Zadanie to da się wyrazić następu­jąco:

void next()
{
    gotoxy(1, NE - 1); delline(); delline();
    gotoxy(1, 3); delline();
    p++;
    plik.seekg(k * sizeof(rec));
    plik.read((char *)&rec, sizeof(rec));
    gotoxy(1, NE - 2);
    show(++k);
    menu();
}

Funkcja prev jest podobna do poprzedniej. Różnice wynikają z odwro­tnego przesu­wania się wzdłuż pliku, o jeden rekord w kierunku początku zamiast w kierunku końca. Tym razem po usunięciu dwóch przedo­statnich wierszy ekran jest przewijany w dół poprzez wstawienie pustego wiersza o numerze 3, wartości zmiennych pk są zmniej­szane o 1, a wczytany z pliku do bufora rekord o numerze p–1 jest wyświe­tlany w nowym wierszu 3. Oto kod tej funkcji:

void prev()
{
    gotoxy(1, NE - 2); delline(); delline();
    gotoxy(1, 3); insline();
    p--;
    plik.seekg((p - 1) * sizeof(rec));
    plik.read((char *)&rec, sizeof(rec));
    show(p);
    k--;
    menu();
}

Należy zauważyć, że ostatni wiersz ekranu nie jest czyszczony, lecz w wyniku usunięcia dwóch wierszy powyżej niego i wstawienia nowego wiersza o numerze 3 zostaje przesunięty o jedno miejsce w górę i na koniec wypełniony ciągiem znaków '-' wyobraża­jącym linię poziomą nad tekstem menu.

Pełny program w C++ pobierający rekordy typu Osoba ze strumienia klasy ifstream skojarzo­nego z plikiem binarnym i wyświe­tlający je w postaci listy, którą przy większej liczbie rekordów można przewijać za pomocą klawiszy strzałek (góra, dół), jest przedsta­wiony na poniższym listingu. Nazwę pliku można podać w wierszu polecenia uruchamia­jącym program. Gdy jest pominięta, określa ją stała FileName o wartości Osoby.dta.

#include <fstream>
#include <iostream>
#include <iomanip>
#include <string>
#include "bconio.h"
#include "klaw2.h"
#include "osoby.h"

using namespace std;

char FileName[] = "Osoby.dta";  // Domyślna nazwa pliku

const int NE = 25;              // Liczba wierszy na ekranie

ifstream plik;                  // Plik rekordów
Osoba rec;                      // Aktualnie wczytany rekord
int n;                          // Liczba rekordów pliku
int p, k;                       // Nr pierwszego i ostatniego wyśw. rekordu

void show(int Lp)
{
    cout << setw(3) << Lp << ". " << rec.nazwisko << " " << rec.imie
         << setw(NA + IM + 3 - strlen(rec.nazwisko) - strlen(rec.imie)) << ""
         << rec.tel << setw(TE + 2 - strlen(rec.tel)) << "" << rec.email;
}

void menu()
{
    gotoxy(1, (n < NE - 4) ? n + 3 : NE - 1);
    cout << string(79, '-') << "\n Menu: ";
    if (p > 1) cout << "Up, ";
    if (k < n) cout << "Dn, ";
    cout << "Esc";
}

void init()
{
    p = 1;
    for (k = 0; k < NE - 4 && k < n; )
    {
        plik.read((char *)&rec, sizeof(rec));
        show(++k); cout << endl;
    }
    menu();
}

void next()
{
    gotoxy(1, NE - 1); delline(); delline();
    gotoxy(1, 3); delline();
    p++;
    plik.seekg(k * sizeof(rec));
    plik.read((char *)&rec, sizeof(rec));
    gotoxy(1, NE - 2);
    show(++k);
    menu();
}

void prev()
{
    gotoxy(1, NE - 2); delline(); delline();
    gotoxy(1, 3); insline();
    p--;
    plik.seekg((p - 1) * sizeof(rec));
    plik.read((char *)&rec, sizeof(rec));
    show(p);
    k--;
    menu();
}

int main(int argc, char *argv[])
{
    char *fname = (argc > 1) ? argv[1] : FileName;
    plik.open(fname, ios::binary);
    if (!plik)
    {
        cout << "Nieudane otwarcie pliku " << fname << endl;
        return 1;
    }
    plik.seekg(0, ios::end);
    n = int(plik.tellg() / sizeof(rec));
    plik.seekg(0);
    clrscr();
    cout << " Lp. Nazwisko i imię                      Nr telefonu"
            "    Adres e-mail\n" << string(79, '-') << endl;
    init();
    for (;;)
        switch (czytajZnak())
        {
            case K_UP:
                if (p > 1) prev();
                break;
            case K_DN:
                if (k < n) next();
                break;
            case K_ESC:
                plik.close();
                return 0;
        }
}

Uwaga. Wersja programu dla kompilatora Borland C++ nie korzysta z modułu bconio.

Program po otwarciu pliku wejściowego wyznacza liczbę jego rekordów, wyświetla nagłówek i listę początko­wych NE–4 rekordów (wszystkich, gdy ich liczba nie przekracza tej wartości) oraz menu (rys.), a następnie w nieskoń­czonej pętli pobiera znaki z klawia­tury i interpre­tuje je następu­jąco:

Program mieszania rekordów pliku

Pożądane jest, aby używany do testowania programu sortowania plik rekordów był nieuporząd­kowany. W celu uzyskania pliku o tej własności posłużymy się prostym programem rozprasza­jącym (miesza­jącym) rekordy in situ (w miejscu). Metoda polega na zamianie miejscami każdego rekordu pliku, od pierwszego do ostatniego, z innym, za każdym razem losowo wybranym rekordem tego pliku:

#include <fstream>
#include <cstdlib>
#include <ctime>
#include "osoby.h"

using namespace std;

char FileName[] = "Osoby.dta";

int main(int argc, char *argv[])
{
    char *fname = (argc > 1) ? argv[1] : FileName;
    fstream plik(fname, ios::in | ios::out | ios::binary);
    if (!plik) return 1;
    srand((unsigned)time(NULL));
    Osoba r1, r2;
    plik.seekg(0, ios::end);
    int i, j, n = int(plik.tellg() / sizeof(Osoba));
    for (i = 0; i < n; i++)
    {
        if ((j = rand() % n) == i) continue;
        plik.seekg(i * sizeof(Osoba));
        plik.read((char *)&r1, sizeof(Osoba));
        plik.seekg(j * sizeof(Osoba));
        plik.read((char *)&r2, sizeof(Osoba));
        plik.seekp(j * sizeof(Osoba));
        plik.write((char *)&r1, sizeof(Osoba));
        plik.seekp(i * sizeof(Osoba));
        plik.write((char *)&r2, sizeof(Osoba));
    }
    return 0;
}

Program w kolejnych krokach pętli for dla i od 0 do n–1, gdzie n jest liczbą wszystkich rekordów pliku, przestawia rekord o numerze i z rekordem o numerze j wyloso­wanym spośród liczb od 0 do n–1. W przypadku j=i instru­kcja continue (kontynuuj) przenosi wykonanie pętli do nastę­pnego kroku iteracyj­nego. Unika się w ten sposób zbędnego przesta­wiania rekordu z samym sobą.

Moduł porównywania łańcuchów

W programie sortowania pliku rekordów typu Osoba wymagane jest leksykogra­ficzne porówny­wanie łańcuchów znaków reprezen­tujących nazwiska i imiona. Poprawna funkcja porówny­wania łańcuchów powinna uwzglę­dniać polski alfabet i przyjęty standard kodowania polskich znaków diakryty­cznych, dlatego to nieco skompli­kowane zadanie jest zupełnie pomijane w podrę­cznikach programo­wania. Trzeba nadmienić, że funkcje strcmpstricmp (porówny­wanie łańcu­chów z rozróż­nianiem i bez rozróż­niania wielkości liter) z biblio­teki string są w rozpatry­wanym przypadku bezuży­teczne, a funkcja setlocale (ustawienia regio­nalne) sprawia wiele problemów, o czym można się przekonać, przeglą­dając zasoby interne­towe. W tej sytuacji rozsądnym wydaje się opraco­wanie własnej funkcji spełnia­jącej wymagania programu sortowania. Jej definicję umieścimy w module compl, którego plik nagłów­kowy ma postać:

// compl.h - Porównanie łańcuchów z uwzględnieniem polskich liter
// --------------------------------------------------------------
// cmpCP852 - porównuje dwa łańcuchy znaków s1 i s2,
//            utożsamiając małe i duże litery (kodowanie CP852)
// Wynik: ujemny dla s1 < s2, 0 dla s1 = s2, dodatni dla s1 > s2
// --------------------------------------------------------------

#ifndef H_COMPL
#define H_COMPL

int cmpCP852(char *s1, char *s2);

#endif // H_COMPL

Jak wiadomo, zbiór ASCII składa się ze 128 znaków, którym przypisane są kody liczbowe od 0 do 127. Duże i małe litery alfabetu angiel­skiego zajmują w nim dwa uporząd­kowane i spójne podzbiory: litera A ma kod 65, litera B – kod 66, litera C – kod 67 itd., a małe litery mają kody wyższe o 32 od kodów odpowia­dających im dużych liter. Niestety, nie istnieje jeden, powsze­chnie stosowany standard kodowania polskich znaków. Używana w oknie konsoli polskiej wersji Windows strona kodowa CP852 stano­wiąca rozsze­rzenie tabeli ASCII o kolejne 128 znaków o kodach od 128 do 255 zawiera polskie znaki diakry­tyczne, ale są one rozmieszczone chaoty­cznie, np. litera Ą ma kod 164, litera Ć – kod 143, litera ą – kod 165, litera ć – kod 134. Sprawą kluczową dla rozwią­zania problemu porówny­wania łańcuchów z polskimi znakami jest ustawienie wszystkich liter w kolej­ności alfabe­tycznej A, Ą, B, C, Ć itd., co odpo­wiada kolejności kodów 65, 164, 66, 67, 143 itd. Co więcej, małe litery utożsa­miane z dużymi powinny zajmować te same pozycje co duże.

Zagadnienie można łatwo rozwiązać, definiując 256-bajtową tablicę znaków, w której literom A i a odpowiada znak o kodzie 65, literom Ą i ą – znak o kodzie 66, literom B i b – znak o kodzie 67, literom C i c – znak o kodzie 68, literom Ć i ć – znak o kodzie 69 itd. Indeksami elementów tablicy są znaki tabeli CP852, a warto­ściami elementów znaki, których uporządko­wanie w przy­padku indeksów literowych jest zgodne z polskim alfabetem. Taki sposób rozwią­zania problemu leksykogra­ficznego porówny­wania łańcu­chów jest stoso­wany w drugiej części modułu compl:

#include "compl.h"

unsigned char C[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
    12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
    26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
    40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53,
    54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64,
    65, 67, 68, 70, 71, 73, 74, 75, 76, 77, 78,     // ABCDEFGHIJK
    79, 81, 82, 84, 86, 87, 88, 89, 91, 92, 93,     // LMNOPQRSTUV
    94, 95, 96, 97,                                 // WXYZ
    100, 101, 102, 103, 104, 105,                   // [\]^_`
    65, 67, 68, 70, 71, 73, 74, 75, 76, 77, 78,     // abcdefghijk
    79, 81, 82, 84, 86, 87, 88, 89, 91, 92, 93,     // lmnopqrstuv
    94, 95, 96, 97,                                 // wxyz
    123, 124, 125, 126, 127,
    128, 129, 130, 131, 132, 133,
    69,                                             // ć
    135,
    80,                                             // Ł
    137, 138, 139, 140,
    99,                                             // Ź
    142,
    69,                                             // Ć
    144, 145, 146, 147, 148, 149, 150,
    90, 90,                                         // Śś
    153, 154, 155, 156,
    80,                                             // Ł
    158, 159, 160, 161,
    85,                                             // ó
    163,
    66, 66,                                         // Ąą
    166, 167,
    72, 72,                                         // Ęę
    170,
    99,                                             // ź
    172, 173, 174, 175, 176, 177, 178, 179, 180,
    181, 182, 183, 184, 185, 186, 187, 188,
    98, 98,                                         // Żż
    191, 192, 193, 194, 195, 196, 197, 198, 199,
    200, 201, 202, 203, 204, 205, 206, 207, 208,
    209, 210, 211, 212, 213, 214, 215, 216, 217,
    218, 219, 220, 221, 222, 223,
    85,                                             // Ó
    225, 226,
    83, 83,                                         // Ńń
    229, 230, 231, 232, 233, 234, 235, 236, 237,
    238, 239, 240, 241, 242, 243, 244, 245, 246,
    247, 248, 249, 250, 251, 252, 253, 254, 255 };

int cmpCP852(char *s1, char *s2)
{
    while (C[*s1] == C[*s2])
    {
        if (*s1 == 0) return 0;
        s1++; s2++;
    }
    return C[*s1] - C[*s2];
}

Kody podzbiorów liter alfabetu angielskiego zostały w tablicy C poprze­suwane, by po uzupeł­nieniu dziewię­cioma polskimi znakami diakryty­cznymi powstał spójny podzbiór liter alfabetu polskiego. Konse­kwencją tego zabiegu było przesu­nięcie o 9 pozycji kodu sześciu znaków znajdu­jących się w tabeli ASCII bezpo­średnio za literą Z.

Funkcja cmpCP852 porównuje w pętli dwa ciągi znaków uzyskiwane za pomocą tablicy C z łań­cuchów s1s2. Pętla zostaje przerwana, gdy przetwo­rzone znaki są różne lub obydwa są równe zero. W pierwszym przypadku zwracaną wartość wyznacza się, odejmując je od siebie, w drugim zwracaną wartością jest zero. Tak więc funkcja zwraca wartość ujemną, równą zero lub dodatnią w zależności od tego, czy ciąg otrzy­many z łańcucha s1 jest leksykogra­ficznie mniejszy, równy lub większy niż ciąg otrzymany z łańcucha s2. Jej działanie można sprawdzić na prostym przykła­dzie wypisu­jącym dwie liczby całkowite:

char s1[] = "ko\x88" "ek";       // kołek
char s2[] = "kotek";
cout << stricmp(s1, s2) << endl;
cout << cmpCP852(s1, s2) << endl;

Niezależnie od kompilatora pierwsza liczba jest dodatnia, a druga ujemna. Oznacza to, że według funkcji stricmp łańcuch "kołek" jest większy, a według cmpCP852 mniejszy niż "kotek". Oczywiście w przy­padku polskiego porządku leksykogra­ficznego drugi wynik jest poprawny.

Program sortowania rekordów pliku

Plik rekordów typu Osoba ma być sortowany rosnąco według klucza nazwisko+­imię+data urodzenia z uwzglę­dnieniem kodowania znaków w stan­dardzie CP852 i polskiego alfabetu uzupeł­nionego o litery Q, V i X. Spraw­dzenie, jakie jest uporządko­wanie dwóch rekordów, można sformu­łować w postaci prostej funkcji:

int porownaj(Osoba &rec1, Osoba &rec2)
{
    int k = cmpCP852(rec1.nazwisko, rec2.nazwisko);
    if (k == 0) k = cmpCP852(rec1.imie, rec2.imie);
    if (k == 0) k = rec2.dtur.r - rec1.dtur.r;
    if (k == 0) k = rec2.dtur.m - rec1.dtur.m;
    if (k == 0) k = rec2.dtur.d - rec1.dtur.d;
    return k;
}

Funkcja porównuje klucze przekazanych jej przez referencję rekordów rec1rec2. Wynikiem tego porównania jest liczba całkowita wyraża­jąca jedną z trzech możliwych relacji:

Narzucającym się sposobem porządkowania pliku rekordów jest wczytanie ich do listy jednokie­runkowej uporządko­wanej, a potem zapis z powrotem do pliku w kolejności występo­wania w liście. Jest oczywiste, że metoda ta daje się zreali­zować, gdy dostępna pamięć komputera jest wystar­czająco pojemna, by zmieścić wszystkie elementy listy. Ich definicja i zmiennej określa­jącej początek wstępnie pustej listy może wyglądać następu­jąco:

struct Element
{
    Osoba rec;
    Element *nast;
} *lista = NULL;

Uporządkowanie listy uzyskuje się poprzez wstawianie wczyty­wanych z pliku rekordów w odpo­wiednie jej miejsce, które można znaleźć, przebie­gając sekwen­cyjnie elementy listy dwoma wskaźni­kami ab typu Element* w ten sposób, że element *a poprzedza element *b. Przeglą­danie elementów listy jest kontynu­owane dopóty, dopóki klucz wczyta­nego rekordu jest większy od klucza rekordu w elemen­cie *b, a gdy się skończy, nowy element *p z wczytanym rekordem jest wstawiany pomiędzy elementami *a*b (rys.).

Należy oczywiście przewidzieć skrajny przypadek, gdy w trakcie przeglą­dania listy osiągnięty został jej koniec, tj. gdy wskaźnik b ma wartość NULL. Wówczas nowy element jest wstawiany za elementem końcowym, a gdy lista jest pusta, staje się jej jedynym elementem. Funkcja wstawiania nowego elementu do listy może wyglądać następu­jąco:

void wstaw(Osoba &rec)
{
    Element *a = NULL, *b = lista, *p;
    while (b != NULL && porownaj(rec, b->rec) > 0)
        b = (a = b)->nast;
    (p = new Element)->rec = rec;
    p->nast = b;
    if (a != NULL)
        a->nast = p;
    else
        lista = p;
}

Wstępnie wartością zmiennej a jest wskaźnik pusty, a wartością b wskaźnik na początek listy. Odpowiada to sytuacji, w której element *p jest wstawiany na początku listy. Następnie wskaźniki ab są przesu­wane wzdłuż listy w celu znale­zienia właściwego miejsca wstawienia. Warunek kontynuacji pętli while składa się z dwóch czynników:

Po znalezieniu odpowiedniego miejsca element *p z wczy­tanym rekordem jest wstawiany do listy. Najpierw określa się, że jego następni­kiem jest *b (rys. powyżej z lewej). Następnie sprawdza się, czy element *p jest wstawiany za jakimś elementem listy, czy na jej początek. Decyduje o tym wskaźnik a. Jeżeli nie jest pusty, element *p jest wstawiany za elementem *a (rys. powyżej z prawej), a w przeciwnym razie na początek listy.

Pełny kod programu w C++ sortującego powyższą metodą plik rekordów jest przedsta­wiony na poniższym listingu. W programie występują trzy nierozpa­trywane wcześniej funkcje:

#include <fstream>
#include <iostream>
#include <string>
#include "osoby.h"
#include "compl.h"

using namespace std;

char FileName[] = "Osoby.dta";

struct Element
{
    Osoba rec;
    Element *nast;
} *lista = NULL;

int porownaj(Osoba &rec1, Osoba &rec2)
{
    int k = cmpCP852(rec1.nazwisko, rec2.nazwisko);
    if (k == 0) k = cmpCP852(rec1.imie, rec2.imie);
    if (k == 0) k = rec2.dtur.r - rec1.dtur.r;
    if (k == 0) k = rec2.dtur.m - rec1.dtur.m;
    if (k == 0) k = rec2.dtur.d - rec1.dtur.d;
    return k;
}

void wstaw(Osoba &rec)
{
    Element *a = NULL, *b = lista, *p;
    while (b != NULL && porownaj(rec, b->rec) > 0)
        b = (a = b)->nast;
    (p = new Element)->rec = rec;
    p->nast = b;
    if (a != NULL)
        a->nast = p;
    else
        lista = p;
}

bool utworzListe(char *fname)
{
    ifstream plik(fname, ios::binary);
    if (!plik) return false;
    Osoba rec;
    while (plik.read((char *)&rec, sizeof(Osoba)))
        wstaw(rec);
    return true;
}

bool zapiszListe(char *fname)
{
    ofstream plik(fname, ios::binary);
    if (!plik) return false;
    for (Element *p = lista; p != NULL; p = p->nast)
        plik.write((char *)&(p->rec), sizeof(Osoba));
    return true;
}

void zwolnijListe()
{
    Element *p;
    while (lista != NULL)
    {
        lista = (p = lista)->nast;
        delete p;
    }
}

int main(int argc, char *argv[])
{
    char *fname = (argc > 1) ? argv[1] : FileName;
    if (utworzListe(fname))
    {
        if (argc > 2) fname = argv[2];
        if (zapiszListe(fname))
            cout << "\nSortowanie zakończone\n";
        else
            cout << "\nNieudane utworznie pliku " << fname << endl;
    }
    else
        cout << "\nNieudane otwarcie pliku " << fname << endl;
    zwolnijListe();
    return 0;
}

W wierszu polecenia wywołującego program można podać dodatkowo jedną lub dwie nazwy pliku. Gdy nie podano żadnej, program porządkuje plik o domyślnej nazwie Osoby.dta, gdy jedną, porządkuje plik o tej nazwie, a gdy dwie, czyta plik o pierwszej nazwie i zapisuje wynik sortowania w pliku o drugiej nazwie.


Opracowanie przykładu: luty/marzec 2020