ANSI C

Laboratorium 5

Binarna reprezentacja liczb całkowitych

Wszystkie wartości liczbowe są we współczesnych komputerach pamiętane w postaci dwójkowej, zwanej też postacią binarną (system dwójkowy został wybrany ze względów technologicznych). Liczba całkowita ze znakiem typu int jest zapisywana na 32 bitach (4 bajty), przy czym najbardziej znaczący bit determinuje znak liczby (kodowanie w systemie U2).

W systemie tym występują tylko dwie cyfry: 0 i 1. Gdy liczbę zapiszemy binarnie, to pozycja każdej cyfry jest związana z określoną potęgą 2: ostatnia pozycja to jedności czyli 2⁰ (najmniej znaczący bit), przedostatnia to dwójki czyli 2¹, przedprzedostatnia to czwórki czyli 2², itd. Niech dana będzie liczba b. Liczbę tą można zapisać za pomocą k cyfr dwójkowych (dla odpowiednio dobranego parametru k):
    b = (b_k-1b_k-2...b₁b₀)
Wówczas wartość liczby b można wyznaczyć w następujący sposób:
    b = ∑_i=0^k-1(b_i·2ⁱ)
W przypadku gdy liczba b jest typu int, to jej wartość wylicza się następująco:
    b = -b₃₁·2³¹+∑_i=0³⁰(b_i·2ⁱ)

Laboratorium 5 - czwartek 16:15,

1. (0.8 pkt.)
   Napisz program, który wczyta ze standardowego wejścia liczbę całkowitą a następnie wypisze ją na standardowym wyjściu w postaci binarnej (wypisz wszystkie 32 bity zaczynając od najbardziej znaczącego).
   Uwaga! Zdefiniuj funkcję czytajbit(), która odczyta z zadanej liczby wartość zadanego bitu. W funkcji tej zastosuj operator przesunięć bitowych << albo >>. Wykorzystaj tę funkcję w swoim programie.
2. (0.8 pkt.)
   Napisz program, który wczyta ze standardowego wejścia liczbę naturalną n a następnie wyliczy i wypisze na standardowym wyjściu ile w tej liczbie jest zer/jedynek wiodących (w zależności od znaku liczby).
   Uwaga! Można ale nie trzeba zastosować strategię "dziel i zwyciężaj" w rozwiązaniu tego zadania.
3. (1.0 pkt.)
   Napisz program, który wczyta ze standardowego wejścia liczbę całkowitą n≥1 a następnie wyliczy i wypisze na standardowym wyjściu wartość ⌈log₂ n⌉. Do wyliczenia logarytmu ⌈log₂ n⌉ zdefiniuj osobną funkcję.
   Uwaga! Nie używaj w swoim programie żadnych funkcji pomocniczych.

Laboratorium 5 - czwartek 18:15,

1. (0.8 pkt.)
   Napisz program, który wczyta ze standardowego wejścia liczbę całkowitą a następnie wypisze ją na standardowym wyjściu w postaci binarnej (wypisz wszystkie 32 bity zaczynając od najbardziej znaczącego).
   Uwaga! Zdefiniuj funkcję czytajbit(), która odczyta z zadanej liczby wartość zadanego bitu. W funkcji tej zastosuj operator przesunięć bitowych << albo >>. Wykorzystaj tę funkcję w swoim programie.
2. (0.8 pkt.)
   Napisz program, który wczyta ze standardowego wejścia liczbę naturalną n a następnie wyliczy i wypisze na standardowym wyjściu ile w tej liczbie jest zer/jedynek wiodących (w zależności od znaku liczby).
   Uwaga! Można ale nie trzeba zastosować strategię "dziel i zwyciężaj" w rozwiązaniu tego zadania.
3. (1.0 pkt.)
   Napisz program, który wczyta ze standardowego wejścia liczbę całkowitą n≥1 a następnie wyliczy i wypisze na standardowym wyjściu wartość ⌊log₂ n⌋. Do wyliczenia logarytmu ⌊log₂ n⌋ zdefiniuj osobną funkcję.
   Uwaga! Nie używaj w swoim programie żadnych funkcji pomocniczych.

Zadanie domowe 5 - czwartek,

1. (1.0 pkt.)
   Napisz program, który wczyta ze standardowego wejścia liczbę całkowitą n i odwróci w niej wszystkie bity (najmniej znaczący bit zamieni z najbardziej znaczącym itd).
   Uwaga! Program ma wypisać najpierw pierwotną wartość liczby n w postaci dziesiętnej i dwójkowej (wszystkie bity) a potem w taki sam sposób nową wartość po transformacji.
2. (1.4 pkt.)
   Napisz program, który wczyta ze standardowego wejścia liczbę całkowitą n oraz s i przesunie cyklicznie wszystkie bity n o s pozycji w prawo.
   Wskazówka! Gdy przesuwamy liczbę o jedną pozycję w prawo, to bit z pozycji 0 zostanie przeniesiony na pozycję 1, bit z pozycji 1 zostanie przeniesiony na pozycję 2, itd, a bit najbardziej znaczący zostanie przeniesiony na pozycję 0. Gdy s<0 to tak, jakbyśmy ją przesuwali w lewo.
   Uwaga! Program ma wypisać najpierw pierwotną wartość liczby n w postaci dwójkowej (wszystkie bity) a potem w taki sam sposób nową wartość po przesunięciu o s pozycji.
   Uwaga! Zdefiniuj funkcje ustawbit() i zerujbit(), która wpisze do zadanej liczby na zadanej pozycji bit o wartości odpowiednio 1 albo 0. Wykorzystaj tę funkcję w swoim programie.

Laboratorium 6

Podział programu na pliki nagłówkowe i źródłowe

Każdy program powinien składać się z trzech plików: pliku źródłowego z funkcją main(), pliku nagłówkowego z deklaracjami funkcji pomocniczych oraz pliku źródłowego z ich definicjami.

Laboratorium 6 - czwartek 16:15,

1. (1.0 pkt.)
   Napisz program, który wczyta liczbę rzeczywistą x>0 i liczbę całkowitą k>1 a następnie stablicuje wartości p_i dla i=0...k-1 określone następującym wzorem rekurencyjnym:
         p₀ = 1
         p_i = (x/p_i-1+p_i-1)/2 : i>0
   Na zakończenie program powinien wypisać pierwiastek kwadratowy z x (użyj funkcji sqrt() z biblioteki standardowej do wyznaczenia pierwiastka) i dalej w dwóch kolumnach następujące zestawienie: w pierwszej kolumnie wartości p_i a w drugiej różnicę pomiędzy p_i a pierwiastkiem kwadratowym z x z dokładnością do 12 miejsc po kropce dziesiętnej.
   Uwaga! Program należy zabezpieczyć przed podaniem błędnych danych.
   Uwaga! Tablica z wyliczonymi wartościami p_i powinna być automatycznie utworzona na stosie i zawierać dokładnie k komórek.
   Uwaga! Zdefiniuj funkcję ciag() do wypełnienia komórek zadanej tablicy wartościami określonymi we wzorze.
2. (1.4 pkt.)
   Napisz program, który wczyta ze standardowego wejścia liczby całkowite n>0 i z>1 a następnie utworzy automatyczną n-elementową tablicę liczb typu int i wypełni ją losowymi wartościami z zakresu od 1 do z. Wyznacz wartość minimalną spośród liczb zapisanych w tej tablicy, położenie tej liczby (indeks w tablicy pod którym można ją znaleźć) oraz oblicz średnią arytmetyczną ze wszystkich liczb w tablicy.
   Uwaga! Zdefiniuj funkcję losuj(), która zwróci losową wartość całkowitą z zadanego zakresu. Twoja funkcja powinna korzystać z generatora liczb pseudolosowych i losować wartości z rozkładem jednostajnym.
   Uwaga! Zdefiniuj funkcję minimum() do wyznaczania pozycji najmniejszej wartości w zadanej tablicy.
   Uwaga! Zdefiniuj funkcję srednia() do obliczania średniej arytmetycznej z liczb zapisanych w zadanej tablicy.

Laboratorium 6 - czwartek 18:15,

1. (1.0 pkt.)
   Napisz program, który wczyta liczbę rzeczywistą x>0 i liczbę całkowitą k>1 a następnie stablicuje wartości p_i dla i=0...k-1 określone następującym wzorem rekurencyjnym:
         p₀ = 1
         p_i = (x/p_i-1²+2p_i-1)/3 : i>0
   Na zakończenie program powinien wypisać pierwiastek sześcienny z x (użyj funkcji pow() z biblioteki standardowej do wyznaczenia pierwiastka) i dalej w dwóch kolumnach następujące zestawienie: w pierwszej kolumnie wartości p_i a w drugiej różnicę pomiędzy p_i a pierwiastkiem kwadratowym z x z dokładnością do 12 miejsc po kropce dziesiętnej.
   Uwaga! Program należy zabezpieczyć przed podaniem błędnych danych.
   Uwaga! Tablica z wyliczonymi wartościami p_i powinna być automatycznie utworzona na stosie i zawierać dokładnie k komórek.
   Uwaga! Zdefiniuj funkcję ciag() do wypełnienia komórek zadanej tablicy wartościami określonymi we wzorze.
2. (1.4 pkt.)
   Napisz program, który wczyta ze standardowego wejścia liczby całkowite n>0 i z≥1 a następnie utworzy automatyczną n-elementową tablicę liczb typu int i wypełni ją losowymi wartościami z zakresu od -z do z. Wyznacz wartość maksymalną spośród liczb zapisanych w tej tablicy, położenie tej liczby (indeks w tablicy pod którym można ją znaleźć) oraz oblicz średnią arytmetyczną ze wszystkich liczb w tablicy.
   Uwaga! Zdefiniuj funkcję losuj(), która zwróci losową wartość całkowitą z zadanego zakresu. Twoja funkcja powinna korzystać z generatora liczb pseudolosowych i losować wartości z rozkładem jednostajnym.
   Uwaga! Zdefiniuj funkcję maksimum() do wyznaczania pozycji najmniejszej wartości w zadanej tablicy.
   Uwaga! Zdefiniuj funkcję srednia() do obliczania średniej arytmetycznej z liczb zapisanych w zadanej tablicy.
   Uwaga! Podziel program na pliki nagłówkowe i źródłowe.

Zadanie domowe 6 - czwartek,

1. (0.4 pkt.)
   Napisz program, który wczytuje liczbę całkowitą reprezentującą rok. Program ma sprawdzić czy podany rok jest przestępny w obowiązującym obecnie kalendarzu gregoriańskim i wypisać odpowiedni komunikat.
   Uwaga! Do testowania przestępności zdefiniuj osobną funkcję, która zwróci 1 gdy rok jest przestępny albo 0 gdy jest zwykły:
       int przestepny (int rok);
   Wyjaśnienie! Kalendarz gregoriański opracował Aloysius Lillus zgodnie z zaleceniami soboru trydenckiego. Kalendarz ten został wprowadzony na mocy bulli papieża Grzegorza XIII z dnia 24 lutego 1582 roku. Nowy kalendarz obowiązywał od 4 października 1582 roku zamiast kalendarza juliańskiego. Celem reformy kalendarza juliańskiego było przywrócenie zgodności pomiędzy kalendarzem a porami roku, czyli zniwelowanie opóźnienia w stosunku do roku zwrotnikowego, narosłego od roku 46 p.n.e. oraz zapobieżenie jego powstawaniu na przyszłość. Kalendarz juliański spóźniał się 1 dzień na 128 lat w stosunku do roku zwrotnikowego. Aby usunąć nienadążanie roku kalendarzowego w kalendarzu juliańskim za rokiem astronomicznym usunięto z kalendarza 10 dni, od 5 do 14 października 1582 roku i nieznacznie zmieniono zasady wyznaczania lat przestępnych. Wprowadzona korekta nie dotyczyła całości opóźnienia narosłego od 46 p.n.e, lecz tylko jego części - przywrócono mianowicie kalendarz do stanu, w jakim był w czasie soboru nicejskiego w roku 325 n.e. Ma to ten skutek, że termin przesilenia zimowego wypada u nas 21 grudnia, podczas gdy w czasach Cezara przypadał na 24 grudnia.
   Lata w kalendarzu gregoriańskim dzielą się na zwyczajne (365 dób) i przestępne (366 dób); rok dzieli się na 12 miesięcy o długości 30 albo 31 dni (z wyjątkiem lutego, który w roku zwykłym ma 28, a przestępnym 29 dni). Latami przestępnymi są lata podzielne przez 4 z wyjątkiem tych które dzielą się przez 100 a nie dzielą się przez 400. Średnia długość roku gregoriańskiego wynosi 365.2425 doby (co skutkuje błędem 1 dnia na każde 2620 lat).
2. (0.4 pkt.) (kontynuacja poprzedniego zadania)
   Napisz program, który wczytuje dwie liczby całkowite reprezentujące kolejno miesiąc i rok. Program ma sprawdzić i wypisać ile dni ma zadany miesiąc (luty ma różną liczbę dni w zależności od roku).
   Uwaga! Program należy zabezpieczyć przed podaniem błędnych danych.
   Uwaga! Skorzystaj z dwuwymiarowej tablicy, w której są zapisane liczby dni w poszczególnych miesiącach, osobno dla lat zwykłych i przestępnych:
       int dni_w_miesiacu[2][13];
   Do tablicy tej powinieneś się odwoływać w nastepujacy sposób:
       dni_w_miesiacu[przestepny(rok)][mies]
3. (0.6 pkt.) (kontynuacja poprzedniego zadania)
   Napisz program, który wczytuje datę w postaci trzech liczb całkowitych reprezentujących kolejno dzień, miesiąc i rok. Program ma sprawdzić czy podana data jest prawidłowa (miesiąc z zakresu 1...12, dzień z zakresu 1...28/29/30/31) i wypisać odpowiedni komunikat. Należy również wziąć pod uwagę fakt, że pierwszym dniem w kalendarzu gregoriańskim jest 15 października 1582 roku.
   Uwaga! Do sprawdzenia poprawności daty zdefiniuj osobną funkcję, która odpowie wartością 1 gdy data jest poprawna albo wartością 0 w przeciwnym przypadku:
       int poprawna (int dz, int mies, int rok);
4. (1.2 pkt.) (kontynuacja poprzedniego zadania)
   Napisz program, który wczytuje datę w postaci trzech liczb całkowitych reprezentujących kolejno dzień, miesiąc i rok. Program ma wyliczyć i wypisać jaki to dzień tygodnia.
   Uwaga! Program należy zabezpieczyć przed podaniem błędnych danych.
   Uwaga! W swoim programie zaimplementuj funkcję wyliczającą ile dni upłynęło od wirtualnej daty 1 stycznia 1 roku:
       int od1roku (int dz, int mies, int rok);
   Funkcja ta powinna wykonywać obliczenia bez używania pętli czy rekurencji.

Laboratorium 7

Wskaźniki i tablice

We wszystkich definiowanych przez ciebie funkcjach posługuj się wskaźnikami, przesunięciami wskaźników, porównywaniem wskaźników, ich różnicą, operatorem wyłuskania itp, ale nie wykorzystuj operatora indeksowania o ile to nie jest konieczne!

Laboratorium 7 - czwartek 16:15,

1. (1.0 pkt.)
   Zdefiniuj funkcję obliczającą długość ciągu znakowego (liczba znaków w ciągu z pominęciem symbolu kończącego '\0') oraz funkcję odwracającą znaki w ciągu znakowym (zamiana pierwszego znaku z ostatnim, drugiego z przedostatnim, itd):
         int dlugosc (char *p);
         void odwroc (char *p);
   Funkcja dlugosc() powinna używać tylko jednego pomocniczego wskaźnika a funkcja odwroc() jednego wskaźnika i jednej zmiennej znakowej!
   Uzupełnienie! Napisz program testujący twoje funkcje, który wczyta ze standardowego wejścia linię tekstu, następnie obliczy i wypisze na standardowe wyjście jego długość a potem odwróci go w miejscu i wypisze po odwróceniu.
2. (1.2 pkt.)
   Zdefiniuj funkcję zamieniającą wartości w dwóch komórkach typu int oraz funkcję sortującą dane typu int zapisane w tablicy (zaimplementuj sortowanie bąbelkowe):
         void zamien (int *p, int *q);
         void sortuj (int t[], int n);
   Funkcja zamien() powinna używać tylko jednej zmiennej całkowitoliczbowej a funkcja sortuj() tylko dwóch wskaźników!
   Uzupełnienie! Napisz program testujący twoje funkcje, który wczyta ze standardowego wejścia liczby całkowite n>0 i z>1 a następnie utworzy automatyczną n-elementową tablicę liczb typu int, wypełni ją losowymi wartościami z zakresu od -z do z a potem posortuje dane zapisane w tej tablicy. Twój program powinien wypisać zawartość tablicy przed sortowaniem i po tej czynności.

Laboratorium 7 - czwartek 18:15,

1. (1.0 pkt.)
   Zdefiniuj funkcję obliczającą długość ciągu znakowego (liczba znaków w ciągu z pominęciem symbolu kończącego '\0') oraz funkcję porównującą leksykograficznie dwa ciągi znakowe (porównuj kolejne znaki aż do napotkania pierwszej różnicy):
         int dlugosc (char *p);
         int porownaj (char *p, char *q);
   Funkcja dlugosc() powinna używać tylko jednego pomocniczego wskaźnika a funkcja porownaj() żadnych dodatkowych zmiennych!
   Uzupełnienie! Napisz program testujący twoje funkcje, który wczyta ze standardowego wejścia dwie linie tekstu, następnie obliczy i wypisze na standardowe wyjście ich długości a potem porówna oba ciągi leksykograficznie i wypisze je w kolejności alfabetycznej.
2. (1.2 pkt.)
   Zdefiniuj funkcję zamieniającą wartości w dwóch komórkach typu int oraz funkcję sortującą dane typu int zapisane w tablicy (zaimplementuj sortowanie przez zamianę):
         void zamien (int *p, int *q);
         void sortuj (int t[], int n);
   Funkcja zamien() powinna używać tylko jednej zmiennej całkowitoliczbowej a funkcja sortuj() tylko dwóch wskaźników!
   Uzupełnienie! Napisz program testujący twoje funkcje, który wczyta ze standardowego wejścia liczby całkowite n>0 i z>1 a następnie utworzy automatyczną n-elementową tablicę liczb typu int, wypełni ją losowymi wartościami z zakresu od 1 do z a potem posortuje dane zapisane w tej tablicy. Twój program powinien wypisać zawartość tablicy przed sortowaniem i po tej czynności.

Zadanie domowe 7 - czwartek,

1. (0.8 pkt.)
   Napisz program, który dla parametrów n>0 i 1≤z≤9 zadanych poprzez argumenty wywołania programu, utworzy automatyczną n-elementową tablicę liczb typu int, wypełni ją losowymi wartościami z zakresu od -10^z do 10^z a potem posortuje dane zapisane w tej tablicy. Twój program powinien wypisać zawartość tablicy przed sortowaniem i po tej czynności.
   Uwaga! Do sortowania wykorzystaj funkcję qsort() z biblioteki standardowej.
2. (1.0 pkt.)
   Napisz program, który posortuje leksykograficznie argumenty wywołania programu i wypisze je uporządkowane na standardowym wyjściu.
   Uwaga! Do sortowania wykorzystaj funkcję qsort() z biblioteki standardowej.
   Uwaga! Do porównywania napisów wykorzystaj funkcję strcmp() z biblioteki standardowej.
3. (1.0 pkt.)
   Napisz program, który liczby całkowite z zakresu od 1 do 999 zadane poprzez argumenty wywołania programu wypisze na standadowym wyjściu w postaci słownej w języku polskim (można pominąć polskie litery diakrytyczne).
   Uwaga! Wykorzystaj w swoim programie tablice wskaźników do napisów:
         char *jednosci[]={"", "jeden", "dwa", ..., "dziewietnascie"};
         char *dziesiatki[]={"", "dziesiec", "dwadziescia", ..., "dziewiecdziesiat"};
         char *setki[]={"", "sto", "dwiescie", ..., "dziewiecset"};
   Uwaga! Do przekształcenia napisu z liczbą na wartość typu int wykorzystaj funkcję atoi() z biblioteki standardowej.

Laboratorium 8

Struktury, unie i pola bitowe

W każdym programie zdefiniuj w zakresie globalnym nowy typ danych, który jest strukturą lub unią. Wykorzystaj instrukcję typedef.

Laboratorium 8 - czwartek 16:15,

1. (0.4 pkt.)
   Zdefiniuj strukturę z polami bitowymi do zapamiętywania daty (5 bitów na dzień, 4 bity na miesiąc i 12 bitów na rok). Napisz też funkcję, która podane wartości typu unsigned int reprezentujące określoną datę upakuje do pola bitowego:
         data upakuj (int d, int m, int r);
   Następnie napisz krótki program testowy, który odczytuje z parametrów wywołania programu jakąć datę, upakowuje ją do pola bitowego, a potem wypisuje na standardowym wyjściu wartość każdego z pól.
2. (1.0 pkt.) (kontynuacja poprzedniego zadania)
   Zdefiniuj strukturę opisująca studenta: imię, nazwisko, data urodzenia (skorzystaj ze struktury zdefiniowanej w poprzednim zadaniu), numer indeksu itp. Następnie napisz program, który dla wczyta ze standardowego wejścia liczbę całkowitą n>0, potem utworzy automatyczną n-elementową tablicę struktur i wczyta do niej informacje o n studentach. Po wczytaniu danych program ma posortować struktury w tablicy ze względu na nazwisko i imię, wykorzystując funkcję qsort() z biblioteki standardowej, a na końcu ma wypisać posortowane informacje na standardowym wyjściu.
3. (0.6 pkt.)
   Zdefiniuj unię, która będzie zawierała pole typu int oraz pole będące tablicą znakową char[sizeof(int)]. Następnie napisz krótki program testowy korzystający z tej unii w celu sprawdzenia, czy liczby na twoim komputerze są zapisywane w systemie little-endian czy big-endian.

Laboratorium 8 - czwartek 18:15,

1. (0.4 pkt.)
   Zdefiniuj strukturę z polami bitowymi do zapamiętywania godziny (5 bitów na gzodziny, 6 bitów na minuty i 6 bitów na sekundy). Napisz też funkcję, która podane wartości typu unsigned int reprezentujące określoną godzinę upakuje do pola bitowego:
         godzina upakuj (int g, int m, int s);
   Następnie napisz krótki program testowy, który odczytuje z parametrów wywołania programu jakąć godzinę, upakowuje ją do pola bitowego, a potem wypisuje na standardowym wyjściu wartość każdego z pól.
2. (1.0 pkt.) (kontynuacja poprzedniego zadania)
   Zdefiniuj strukturę opisująca rozmowę telefoniczną: numer z którym była rozmowa, kto dzwonił (wybieranie połączenia czy odbiór), godzina połączenia (skorzystaj ze struktury zdefiniowanej w poprzednim zadaniu), czas trwania połączenia itp. Następnie napisz program, który dla wczyta ze standardowego wejścia liczbę całkowitą n>0, potem utworzy automatyczną n-elementową tablicę struktur i wczyta do niej informacje o n prowadzonych rozmowach telefonicznych. Po wczytaniu danych program ma posortować struktury w tablicy ze względu na godzinę połączenia, wykorzystując funkcję qsort() z biblioteki standardowej, a na końcu ma wypisać posortowane informacje na standardowym wyjściu.
3. (0.6 pkt.)
   Zdefiniuj unię, która będzie zawierała pole typu int oraz pole będące tablicą znakową char[sizeof(int)]. Następnie napisz krótki program testowy korzystający z tej unii w celu sprawdzenia, czy liczby na twoim komputerze są zapisywane w systemie little-endian czy big-endian.

Zadanie domowe 8 - czwartek,

1. (1.0 pkt.)
   Zdefiniuj unię, która będzie zawierała pole bitowe typu int oraz pole typufloat. Następnie napisz krótki program testowy korzystający z tej unii w celu sprawdzenia, jak jest zapisywana liczba rzeczywista w standardzie IEEE-754 (23 najmniej znaczące bity to mantysa, potem jest 8 bitów cechy i 1 najbardziej znaczący bit to znak). Wypisz znak wprowadzonej liczby, jej cechę w postaci dziesiętnej i mantysę w postaci dwójkowej znormalizowanej.
   Uwaga! Wartość cechy oblicza się w taki sposób, że od odczytanej 8-bitowej wartości z pola cechy odejmujemy 127 (dostaniemy więc liczbę z zakresu od -127 do 128).
   Uwaga! Mantysa to liczba stałopozycyjna z przedziału [1,2) ale w 23-bitowym polu mantysy pamiętana jest tylko część ułamkowa.
2. (2.0 pkt.)
   Napisz program, który wczyta książkę telefoniczną a potem ciąg pytań dotyczący tej książki.
   Najpierw czytaj liczbę wpisów do ksiązki telefonicznej n>0, a potem utwórz automatyczną n-elementową tablicę struktur z wpisami do ksiązki. Struktura z wpisem powinna zawierać dwa pola: nazwę osoby/instytucji i numer telefonu.
   Dalej wczytaj kolejno n wpisów do tej tablicy. Następnie utwórz dwie n-elementowe tablice wskaźników do struktur z wpisami (początkowo i-te pole wskazuje na i-tą strukturę w tablicy z wpisami) a potem posortuj te tablice za pomocą funkcji qsort() z biblioteki standardowej w taki sposób, że pierwsza tablica będzie zawierała wskaźniki uporządkowane względem nazwy we wpisie a druga względem telefonu.
   Na koniec wczytuj w pętli (aż do zamknięcia strumienia) zapytania o telefon (podana jest nazwa) albo o nazwę (podany jest telefon) i w odpowiedzi wypisuj drugą część informacji.
   Uwaga! Wyszukiwanie realizuj w oparciu o tablice wskaźników. Napisz w tym celu oddzielne funkcje implementujące rekurencyjny algorytm wyszukiwania binarnego.

Laboratorium 9

Zarządzanie pamięcią wolną (stertą)

Każdy program podziel logicznie na krótkie procedury realizujące proste zadania (oddziel komunikację z użytkownikiem od obliczeń). Programy mają też być podzielone na pliki źródłowe i nagłówkowe. Pamiętaj aby zawsze na końcu programu zwolnić przydzieloną wcześniej pamięć ze sterty.

Laboratorium 9 - czwartek 16:15,

1. (1.0 pkt.)
   Napisz program, który wczyta dwie dodatnie liczby całkowite N i Z, a następnie wygeneruje N losowych liczb ze zbioru {0,1,...,Z-1} z rozkładem jednostajnym. Liczby te należy umieścić w dynamicznie utworzonej tablicy rozmiaru N. W drugiej tablicy rozmiaru Z, również dynamicznie utworzonej, należy zapamiętać ile razy poszczególne wartości występują w pierwszej tablicy. Program ma najpierw wypisać wszystkie wylosowane liczby z pierwszej tablicy (w jednym wierszu pooddzielane znakiem spacji) a potem korzystając z drugiej tablicy wypisać te same wartości w kolejności niemalejącej (też w jednym wierszu). Twój program powinien na końcu zwolnić przydzieloną pamięć.
2. (1.0 pkt.)
   W pliku nagłówkowym zdefiniuj strukturę reprezentującą węzeł listy jednokierunkowej struct Element, w której będzie pole nast wskazujące na następny element na liście oraz pole wartosc przechowujące pewną wartość typu TYP (nazwę TYP zdefiniuj za pomocą dyrektywy #define):
         struct Element
         {
               struct Element *nast;
               TYP wartosc;
         };
   Oprócz struktury zadeklaruj również funkcje wstawNaPocz() (wstawienie nowego elementu na początek listy), wstawNaKon() (wstawienie nowego elementu na koniec listy), ile() (policzenie ile jest elementów na liście) oraz wypisz() (wypisanie kolejno wszystkich wartości zapamiętanych w liście). Pierwszym argumentem tych funkcji powinien być wskaźnik na początek listy. Dalej, w oddzielnym pliku źródłowym zdefiniuj wymienione funkcje (zaimplementuj je iteracyjnie). Napisz też krótki program testujący zaprogramowaną przez Ciebie listę.

Laboratorium 9 - czwartek 18:15,

1. (1.0 pkt.)
   Napisz program, który wczyta dodatnią liczbę całkowitą N, a następnie wygeneruje losowo N-elementową permutację (wymieszany ciąg liczb od 0 do N-1); zadbaj o to, by każda permutacja mogła być wylosowana z jednakowym prawdopodobieństwem. Wygenerowaną permutację należy zapamiętać w dynamicznie utworzonej tablicy. Program ma najpierw wypisać wylosowaną permutację (wszystkie liczby w jednym wierszu pooddzielane znakiem spacji) a potem wypisać wszystkie cykle z których składa się ta permutacja (każdy w osobnym wierszu). Twój program powinien na końcu zwolnić przydzieloną pamięć.
2. (1.0 pkt.)
   W pliku nagłówkowym zdefiniuj strukturę reprezentującą węzeł listy jednokierunkowej struct Element, w której będzie pole nast wskazujące na następny element na liście oraz pole wartosc przechowujące pewną wartość typu TYP (nazwę TYP zdefiniuj za pomocą dyrektywy #define):
         struct Element
         {
               struct Element *nast;
               TYP wartosc;
         };
   Oprócz struktury zadeklaruj również funkcje wstaw() (wstawienie nowego elementu do listy w takim miejscu aby zachowany był porządek niemalejący), ile() (policzenie ile jest elementów na liście) oraz wypisz() (wypisanie kolejno wszystkich wartości zapamiętanych w liście). Pierwszym argumentem tych funkcji powinien być wskaźnik na początek listy. Dalej, w oddzielnym pliku źródłowym zdefiniuj wymienione funkcje (zaimplementuj je iteracyjnie). Napisz też krótki program testujący zaprogramowaną przez Ciebie listę.

Zadanie domowe 9 - czwartek,

1. (1.2 pkt.)
   W pliku nagłówkowym zdefiniuj strukturę reprezentującą węzeł drzewa binarnych poszukiwań struct Element, w której będą pola lewe i prawe wskazujące odpowiednio na lewe i prawe poddrzewo zaczepione w danym węźle oraz pole wartosc przechowujące pewną wartość typu TYP (nazwę TYP zdefiniuj za pomocą dyrektywy #define):
         struct Element
         {
               struct Element *lewe, *prawe;
               TYP wartosc;
         };
   Oprócz struktury zadeklaruj również funkcje wstaw() (wstawienie nowego elementu do drzewa), ile() (policzenie ile jest elementów w drzewie) oraz wypisz() (wypisanie kolejno wszystkich wartości zapamiętanych w drzewie w porządku inorder). Pierwszym argumentem tych funkcji powinien być wskaźnik na korzeń drzewa (lub poddrzewa). Dalej, w oddzielnym pliku źródłowym zdefiniuj wymienione funkcje (zaimplementuj je rekurencyjnie).
   Uwaga! W oddzielnym pliku źródłowym napisz program testujący działanie zdefiniowanej przez Ciebie struktury danych. Testowanie ma się odbywać w sposób interakcyjny, a więc program ma realizować wydawane na konsoli polecenia.
   Wyjaśnienie! Drzewo binarnych poszukiwań (w skrócie BST, z angielskiego Binary Search Tree) to dynamiczna struktura danych w postaci drzewa binarnego stosowana do implementacji zbiorów uporządkowanych. Drzewo BST składa się z węzłów połączonych wskaźnikami. W każdym z węzłów drzewa przechowywany jest unikatowy. Wartość klucza jest zawsze nie mniejsza niż wartości wszystkich kluczy z lewego poddrzewa i nie większa niż wartości wszystkich kluczy z prawego poddrzewa.
2. (0.8 pkt.) (kontynuacja poprzedniego zadania)
   Do poprzedniego zadania dopisz funkcje usun_min() (usunięcie elementu minimalnego z drzewa), usun_max() (usunięcie elementu maksymalnego z drzewa) i usun() (usunięcie z drzewa elementu o podanej wartości).
   Uwaga! Zmodyfikuj program testowy, tak aby uzwględniał dodane funkcje.
3. (1.0 pkt.) (kontynuacja poprzedniego zadania)
   Do poprzedniego zadania dopisz funkcję drukuj() (wyświetlenie struktury drzewa wraz z wartościami w węzłach). Przykładowe wywołanie tej funkcji w programie testującym może wygenerować następujący wynik dla drzewa BST z wartością 37 w korzeniu:
            +--*11
            |  +--*13
         +--*17
         |  +--*23
         *37
         +--*43
            |  +--*47
            +--*53
               +--*57
   Uwaga! Zmodyfikuj program testowy, tak aby uzwględniał dodaną funkcję.

Laboratorium 10

Operacje na plikach

Programując te zadania zawsze sprwdzaj w programie czy udało się otworzyć plik a na końcu po przeczytaniu/zapisaniu danych zamknij go.

Laboratorium 10 - czwartek 16:15,

1. (1.0 pkt.)
   Napisz program, który wypisze zawartość pliku tekstowego, o ile podany plik istnieje, na standardowym wyjściu. Nazwę pliku przekaż do programu poprzez parametry wywołania. Plik należy napierw otworzyć do czytania, potem przeczytać linia po linii a na końcu zamknąć go. Twój program ma obcinać białe znaki na początku i na końcu każdej linii oraz pomijać przy wypisywaniu liniie puste.
2. (1.0 pkt.)
   Napisz program, który zapisze w pliku tekstowym kolejne liczby z trójkąta Pascala aż do wyczerpania zakresu liczb typu long long:
         P_0,0 = 1
         P_n,0 = P_n,n = 1 dla n>0
         P_n,k = P_n-1,k-1 + P_n-1,k dla 0>k>n
   Nazwę pliku przekaż do programu poprzez parametry wywołania. Każdy wiersz trójkąta Pascala zapisz w oddzielnej linii, a poszczególne liczby w obrębie wiersza poodzielaj pojedynczą spacją. Plik należy napierw otworzyć do pisania, potem zapisać w nim wspomniany trójkąt a na końcu zamknąć go.

Laboratorium 10 - czwartek 18:15,

1. (1.0 pkt.)
   Napisz program, który wypisze zawartość pliku tekstowego, o ile podany plik istnieje, na standardowym wyjściu. Nazwę pliku przekaż do programu poprzez parametry wywołania. Plik należy napierw otworzyć do czytania, potem przeczytać linia po linii a na końcu zamknąć go. Twój program ma przycinać długie linie do 24 znaków (ignorować pozostałe w tej linii znaki) oraz pomijać przy wypisywaniu liniie puste.
2. (1.0 pkt.)
   Napisz program, który zapisze w pliku tekstowym kolejne liczby ciągu Fibonacciego aż do wyczerpania zakresu liczb typu long long:
         F₀ = 0
         F₁ = 1
         F_n = F_n-1 + F_n-2 dla n≥2
   Nazwę pliku przekaż do programu poprzez parametry wywołania. Każdą liczbę zapisz w oddzielnej linii. Plik należy napierw otworzyć do pisania, potem zapisać w nim wspomniany ciąg a na końcu zamknąć go.

Zadanie domowe 10 - czwartek,

1. (1.2 pkt.)
   W tekstowym pliku z danymi jest zapisanych N liczb rzeczywistych a₀, a₁, ..., a_N-1. Zawartość pliku z danymi jest następująca: w pierwszej linii jest zapisana liczba całkowita N≥1 a w kolejnych liniach pooddzielane białymi znakami wartości rzeczywiste a₀, a₁, ..., a_N-1. Należy te liczby najpierw odczytać, zapamiętując je w dynamicznie zaalokowanej tablicy typu double [] a potem zapisać je do pliku binarnego (bez wartości N na początku) i zwolnić przydzieloną wcześniej pamięć. Nazwy plików przekaż poprzez parametry wywołania programu.
   Wskazówka! Posłuż się funkcjami fscanf() i fwrite().
2. (0.8 pkt.) (kontynuacja poprzedniego zadania)
   W binarnym pliku z danymi jest zapisane są liczby typu double. Określ ile tych liczb jest zapisanych w pliku, zaalokuj tablicę o takim rozmiarze na stercie i wczytaj je tam. Następnie policz i wypisz na standardowym wyjściu średnią arytmetyczną i geometryczną z tych wartości. Na końcu zwolnij przydzieloną pamięć. Nazwę pliku przekaż poprzez parametry wywołania programu.
   Wskazówka! Posłuż się funkcją fread().
3. (1.0 pkt.)
   Napisz program, który porówna ze sobą zawartości dwóch plików z dokładnością do białych znaków w obrębie linii. Po napotkaniu pierwszej różnicy program powinien wypisać numer wiersza i numer pozycji w wierszu, w którym występuje różnica, po czym przerwać dalsze porównywanie. Nazwy plików przekaż poprzez parametry wywołania programu.
   Uwaga! Sprawdź, czy program wywołano z prawidłową liczbą argumentów oraz czy podane nazwy są nazwami istniejących plików w lokalnym systemie.

Laboratorium dodatkowe

Zadania różne

Każdy program podziel logicznie na krótkie procedury realizujące proste zadania (oddziel komunikację z użytkownikiem od obliczeń). Programy mają być podzielone na pliki źródłowe i nagłówkowe.

Zadania dodatkowe - czwartek,

1. (1.4 pkt.)
   Napisz program, który przeszuka plik poszukując w nim zadanego słowa. Nazwa pliku i słowo (lub kilka słów) mają być podawane jako argumenty wywołania programu. Program powinien wypisać wszystkie wiersze zawierające zadane słowo (co najmniej jedno jeśli było podanych więcej słów).
   Uwaga! Sprawdź, czy program wywołano z prawidłową liczbą argumentów oraz czy podana nazwa pliku jest nazwą istniejącego pliku w lokalnym systemie.
2. (1.6 pkt.)
   Napisz program, który zaszyfruje/odszyfruje podany plik za pomocą okeślonego klucza. Nazwa pliku i klucz mają być przekazane do programu poprzez argumenty wywołania. Szyfrowanie powinno cyklicznie "przykładać" klucz do danych w pliku i odpowiednio modyfikować jego zawartość. Na parach kolejnych znaków pliku i klucza wykonuj operację XOR (^); kiedy zabraknie liter klucza, należy zacząć ponownie od jego początku. Metodę szyfrowania tekstu zadanym kluczem zaprogramuj jako oddzielną funkcję.
   Uwaga! Sprawdź, czy program wywołano z prawidłową liczbą argumentów oraz czy podana nazwa pliku jest nazwą istniejącego pliku w lokalnym systemie.
3. (2.0 pkt.)
   Zaprogramuj jako oddzielne funkcje dwie metody sortowania danych zapisanych w tablicy: sortowanie bąbelkowe (bubble-sort) oraz sortowanie przez scalanie (merge-sort). Następnie przetestuj działanie tych metod na losowych danych o rozmiarach kolejno: 10, 100, 1000 i 10000. Dokonaj pomiaru czasu działania obu algorytmów na takich samych danych (czas zmierz w programie) i wypisz odpowiednie uzyskanych wyników.

Projekt

Tematy zadań projektowych

kalkulator onp

Zaprogramuj klakulator, który będzie obliczał wyrażenia zapisane w notacji postfiksowej (odwrotna notacja polska). Do obliczeń wykorzystaj kolejkę i stos zaimplementowane na liście jednokierunkowej. Twój program powinien umożliwiać zapamiętywanie wartości obliczonych wyrażeń za pomoca zmiennych. Należy sprwdzać poprawność danych.

formatowanie programów

Napisz program do formatowania programów napisanych w języku ANSI C. Program program zapisany w pliku należy odczytać i sformatować zgodnie z notacją węgierską, zapisując wyniki na standardowym wyjściu. Twój program powinien też usuwać wszystkie komentarze.

drzewa zrównoważone

Zaprogramuj słownikową strukturę danych jako drzewo AVL albo RBT. Na strukturze tej powinieneś wykonywać operacje słownikowe i umożliwiać schematyczne drukowanie struktury drzewa.

kompresja plików

Napisz program, który będzie umożliwiał kompresję i dekompresję plików zgodnie z algorytmem Huffmana (możesz też użyć algorytmu LZ77 albo LZ78).

sudoku

Napisz program, który będzie rozwiązywał łamigłówkę sudoku (program ma prawidłowo wypełnić zadaną planszę). Grę trzeba rozwiązywać na wszystkich poziomach trudności. Gdy rozwiązanie jest sprzeczne albo wieloznaczne, należy o tym poinformować specjalnym komunikatem. Planszę należy wczytać z pliku.

inne tematy należy uzgadniać ze mną indywidualnie...

Uwagi ogólne

• Temat projektu student wybiera samodzielnie spośród zamieszczonych na powyższym wykazie. Należy jednak pamiętać, że do jednego projektu może być przypisanych co najwyżej 3 studentów w grupie. Można także zgłaszać swoje propozycje.
• Szczegóły dotyczące zakresu prac powinny być uzgodnione ze mną jeszcze przed Nowym Rokiem.
• Projekty mają być wykonane samodzielnie.
• Program trzeba rozsądnie podzielić na pliki nagłówkowe i źródłowe.
• Do projektu należy dołączyć dokumentację w postaci komentarza na początku pliku. W dokumentacji należy umieścić:
  1. imię i nazwisko (numer indeksu) autora;
  2. opis metody rozwiązania problemu;
  3. opis używanych struktur danych;
  4. bibliografię (ksiązki, czasopisma, artykuły, linki w internecie).
• Termin oddawania projektów upływa 15 stycznia 2009 r.

Przydział zadań projektowych

grupa czwartkowa 16-18

1. A.Bal. (220989): kompresja plików
2. L.Fra. (221013): sudoku
3. P.Gaj. (221016): kalkulator onp
4. M.Kac. (221034): kalkulator onp
5. K.Kub. (221056): kalkulator onp
6. B.Skr. (221112): kompresja plików
7. P.Sob. (221116): sudoku
8. K.Str. (221122): sudoku
9. P.Urb. (221134): kompresja plików

grupa czwartkowa 18-20

1. G.Łoś. (221063): drzewa zrównoważone
2. R.Łuk. (221064): sudoku
3. K.Sma. (221115): kompresja plików
4. P.Stę. (221120): kompresja plików
5. M.Zię. (221144): kalkulator onp

Ranking

Punkty z laboratoriów

• grupa czwartkowa 16-18
• grupa czwartkowa 18-20

powrót na początek strony