Wybrane programy przykładowe z ćwiczeń

Wstęp do informatyki II (semestr letni)

Poniżej znajdą Państwo niektóre programy omawiane/tworzone/modyfikowane przez nas na ćwiczeniach. Nie jest to stricte materiał dydaktyczny - raczej coś w rodzaju "bloga z kodami", ot dla zgrubnej informacji, co było robione.

W trakcie ćwiczeń często będziemy modyfikowali te programy, lub wręcz pisali je od nowa (by były lepsze!)

Poniższe pliki źródłowe możesz pobierać, klikając w nazwę programu.

Ćwiczenia 14

c14-google.c

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4.  
  5. #define MAXIT 5000 /* liczba iteracji algorytmu PageRank */
  6. /* wskaĹşnik do pomocniczego wektora roboczego */
  7.  
  8. /* do reprezentacji grafu rzadkiego wykorzystamy tym razem macierz rzadką *//* macierz kwadratowa rzadka w formacie współrzędnych *//* liczba krawędzi, tj. liczba niezerowych elementów *//* liczba wierzchołków grafu, tj. wymiar macierzy *//* tablice wymiaru nnz *//* wyznacza normę sum_i |x_i| wektora x *//* wczytuje macierz rzadką z pliku formatu:
  9. n nnz
  10. I[0] J[0] V[0]
  11. I[1] J[1] V[1]
  12. I[2] J[2] V[2]
  13. ....
  14. I[nnz-1] J[nnz-1] V[nnz-1]
  15.  
  16. UWAGA: w tym formacie indeksy są numerowane od "1" 
  17. */
  18. {
  19. FILE *fp; /* plik z ktĂłrego czytamy macierz */
  20. SparseMx A; /* wczytywana macierz */"r");
  21. fscanf(fp, "%d%d", &A.n, &A.nnz);
  22.  
  23. /* znamy wymiary, wiec alokujemy niezbedne tablice *//* czytamy kolejne wartosci z pliku */"%d%d%lf\n"/* oblicza y = A*x; por. SparseMultSlow() *//* algorytm obliczania Ax w innej niz "standardowa" kolejnosci *//* ta funkcja jeszcze nie działa poprawnie; uzupełnij puste miejsce! */
  24. 	/* wskazówką jest postać głównej pętli! *//* zwraca A[i][j], gdzie A jest w formacie współrzędnych *//* y = A*x, ale BARDZO wolno; por. SparseMult() *//* indeksy w macierzy są od "1" *//* wyznacza wektor taki, ze w przyblizeniu A*p = p, stosujac metode potegowa 
  25. dla wektora startowego p; w trakcie iteracji wektor p jest nadpisywany przez lepsze przyblizenia *//* work = A*x; WERSJA SLIMACZA */
  26.  
  27. 	norm = VecNorm(work, N); /* p = work/norm(work) */#ifdef DEBUG
  28. //G = SparseRead("c14-lab.txt"); /* graf, w którym występują liście; tam algorytm może mieć problemy */
  29. G = SparseRead("c14-test.txt"/* pomocniczy wektor roboczy */"%e\n"#endif
  30.  

Ćwiczenia 4

c4-tree.c

  1. /*
  2. Wybrane procedury obsługi drzewa BST
  3.  
  4. 	- drukowanie zawartości:		PrintTree()
  5. 	- wyznaczanie wysokości:		HeightTree()
  6. 	- tworzenie drzewa o losowych kluczach:	InitBSTree()
  7. 	- sprawdzanie, czy jest BST: 		IsBSTree()
  8.  
  9. Przyjmujemy konwencję, że 
  10. 	prawe poddrzewo zawiera klucze większe
  11. 	lewe  poddrzewo zawiera klucze mniejsze
  12. od klucza w korzeniu.
  13.  
  14. Na potrzeby testowania kompilujemy
  15. 	gcc -DDEBUG -o c4-tree c4-tree.c
  16. */
  17.  
  18. #include "c4-tree.h"
  19.  
  20. /*********************************************************************//* drukuje drzewo binarne w porządku pre-order */" %d ""("")");
  21. 	}
  22. }
  23.  
  24. /*********************************************************************//* wysokość drzewa binarnego *//*********************************************************************//* 
  25. Tworzy (być może niezbalansowane) drzewo BST o "n" losowych kluczach 
  26.  
  27. UĹźywa 
  28.  
  29. 	- procedury AllocLeaf(), która tworzy nowy wierzchołek 
  30. 	o zadanym kluczu
  31.  
  32. 	- procedury InsertBSTree(), która tworzy nowy wierzchołek 
  33. 	i dołącza go jako liść we właściwym miejscu drzewa
  34.  
  35. Możesz poprawić tak, by nie wpadała w nieskończoną pętlę "while", gdy np. brakuje pamięci na nowe liście. Wystarczy ograniczyć liczbę ponawianych prób, ale można bardziej subtelnie (wymaga większych przeróbek).
  36. *//* wskaźnik do korzenia generowanego drzewa *//* Korzeń robimy na piechotę */
  37. 	{
  38. 		k = rand() % (2*max); /* losujemy liczbę *//* skoro udało się zrobić korzeń, to mamy 
  39. 		o jeden element mniej do wstawiania! */"wstawilem korzen: %d\n"/* wstawiamy kolejne wierzchołki */
  40. 	{
  41. 		k = rand() % (2*max); /* losujemy liczbę *//* wstawia i sprawdza, czy udalo się wstawić? */"wstawilem: %d\n", k);
  42. 			n--; /* jak udało się wstawić, to zmniejszamy licznik *//* przydziela pamięć na liść drzewa typu "tree";
  43. będziemy to robili kilka razy, więc dobrze mieć taką gotową procedurę
  44. Od razu inicjalizuje pole "key" na zadaną wartość "k"*//* inicjalizujemy liść *//* jeśli się uda, wstawia liść o kluczu "k" do NIEPUSTEGO drzewa BST "T" 
  45. tak, by zachować własność BST; 
  46. generalnie może prowadzić do drzewa niezrównoważonego;
  47. zwraca liczbę faktycznie wstawionych elementów (tzn. 0 lub 1); */
  48. {
  49. 	tree *v; /* nowy wierzchołek *//* ojciec bieżącego wierzchołka *//* szukamy istniejącego w drzewie liścia, 
  50. 	do którego możnaby go doczepić *//* nie wstawiamy kopii */
  51. 		}
  52. 		parentT = T;	/* ojciec dla następnego badanego węzła
  53. 				musimy go zapamietac, aby moc sie don 
  54. 				potem cofnac */
  55.  
  56. 		/* wybieramy nastepny badany węzeł *//* doszliśmy do końca drzewa, cofamy się do ojca;
  57. 	na mocy niepustości drzewa, parentT != NULL *//*********************************************************************//* zwraca logiczną wartość, czy drzewo ma własność BST
  58. Dodatkowo, jeśli drzewo JEST drzewem BST,
  59. 	max == maksymalny klucz w drzewie,
  60. 	min == minimalny klucz w drzewie
  61.  
  62. Algorytm: 
  63. 	1. sprawdzamy, czy lewe poddrzewo jest BST i jakie ma maksimum
  64. 	2. sprawdzamy, czy prawe poddrzewo jest BST i jakie ma minimum
  65. 	3. drzewo o korzeniu T jest BST, jeśli 
  66. 		- oba w/w poddrzewa były BST
  67. 		- klucz korzenia spełnia warunek:
  68. 		maksimum lewego poddrzewa <= klucz korzenia <= minimum prawego poddrzewa
  69. 	4. obliczamy maksymalny i minimalny klucz w całym drzewie biorąc 
  70. 	maksimum (minimum) z właściwego poddrzewa i klucza korzenia.
  71.  
  72. Zwróć uwagę, nasza funkcja IsBSTree musi zwracać TRZY wartości (czy jest BST, maksimum i minimum), dlatego dwie ostatnie są argumentami wywołania ze wskaźnikami!
  73.  
  74. Jak chcesz, popraw funkcję by zawsze zwracała max i min z całego drzewa, niezależnie od tego, czy ma ono własność BST, czy nie.
  75. *//* sprawdzamy lewe poddrzewo (o ile istnieje!) */
  76.  
  77. 			isBSTLeft = IsBSTree( T->left, 
  78. 				&maxleft, &minleft);
  79.  
  80. 			/* teraz wiemy, czy ono ma własność BST i dodatkowo
  81. 			znamy maksymalny i minimalny klucz w tym poddrzewie */
  82.  
  83. 			/* zatem maksymalny element w całym drzewie "T" musi być... */
  84. 			*max = MAX(maxleft,T->key);	
  85.  
  86. 			/* drzewo "T" ma własność BST, jeśli 
  87. 				1. jego lewe poddrzewo jest BST i DODATKOWO 
  88. 				2. klucz w wierzchołku "T" nie jest większy od
  89. 					 wszystkich z lewego poddrzewa, 
  90. 					 czyli od maksymalnego klucza 
  91. 					 z lewego poddrzewa 
  92. 			*//* powtarzamy analogiczny test dla prawego poddrzewa */#ifdef DEBUG
  93. "Wywolanie: %s N,\n\t gdzie N jest liczba wierzcholkow\n""\n""Drzewo ma wysokosc %d\n""BST: %d, %d %d\n"#endif
  94.  

c4-tree.h

  1. #include <stdlib.h>
  2. #include <stdio.h>
  3.  
  4. /* zawsze przydatne makra liczące MAX i MIN z dwóch liczb */
  5. #define MIN(X,Y) ((X) < (Y) ? (X) : (Y))
  6. #define MAX(X,Y) ((X) > (Y) ? (X) : (Y))
  7.  
  8. /* definicja typu drzewiastego *//* kilka stałych symbolicznych potrzebnych do obsługi procedury tworzenia drzewa */
  9. #define TREE_SUCCESS	 	0
  10. #define TREE_UNDEFINED_ERROR 	-1
  11. #define TREE_MEMORY_ERROR 	-2
  12. #define TREE_EXIST_ERROR 	-4
  13.  
  14. /* lista prototypĂłw funkcji definiowanych w c4-tree.c */

Ćwiczenia 2

c2-mx1.c

  1. #include <stdio.h>
  2. #include "c2-mx1.h"
  3. /* drukuje zadana macierz A wymiaru n */"%5.2f ""\n"/* wypelnia macierz A wymiaru n kolejnymi liczbami *//* alokuje pamiec na macierz A wymiaru n i zwraca wskaznik do niej */"Not enough free memory\n"/* mozesz poprawic te funkcje tak, by w przypadku braku pamieci zwracala NULL i wypisywala komunikat o bledzie (pamietaj, na stderr!)
  4. *//* usuwa z pamieci macierz A */
  5. 	free(A);
  6. }
  7.  
  8. #ifdef DEBUG
  9. #define N 4
  10. #endif
  11.  

c2-mx1.h

  1. #include <stdlib.h>

c2-mx2.c

  1. #include <stdio.h>
  2. #include "c2-mx2.h"
  3. /* drukuje zadana macierz A wymiaru nxm *//* wypelnia macierz A wymiaru nxm kolejnymi liczbami *//* alokuje pamiec na macierz A wymiaru nxm i zwraca wskaznik do niej *//* mozesz poprawic te funkcje tak, by w przypadku braku pamieci
  4. na ktorykolwiek z elementow:
  5. 	- usuwala dotychczas zarezerwowane wiersze
  6. 	- usuwala pamiec przydzielona na A
  7. 	- zwracala NULL
  8. Czy da sie w tym celu skorzystac z delete_mx_2d?
  9. *//* usuwa z pamieci macierz A o n wierszach *//*******************DIRTY TRICK***********************//*
  10. * NIE UZYWAJ!
  11. * drukuje zadana macierz A (statycznie alokowana) wymiaru nxm 
  12. */"%5.2f ""\n");
  13. 	}
  14. }
  15. /******************* end of DIRTY TRICK***********************/
  16.  
  17. #ifdef DEBUG
  18. #define N 4
  19. #define M 3
  20. /* dynamicznie *//* statycznie */#endif
  21.  

c2-mx2.h

  1. #include "c2-mx1.h"

c2-testmx.c

  1. #include "c2-mx2.h" /* uwaga: automatycznie dolacza c1-mx1.h */
  2.  
  3. #define N 9
  4. #define M 8
  5. /* test dla macierzy 1d: X jest statyczna *//* test dla macierzy 1d: Y jest dynamiczna *//* test dla macierzy 2d: Z jest dynamiczna */

c2-Makefile

  1. # przed uzyciem, zmien nazwe tego pliku na "Makefile"
  2. # lub uzywaj go poleceniem 
  3. #	make -f c2-Makefile testmx
  4.  
  5. CC = gcc
  6. OBJ = c2-testmx.o c2-mx1.o c2-mx2.o
  7. INC = c2-mx1.h c2-mx2.h
  8.  
  9. testmx: $(OBJ)
  10. 	$(CC) -o $@ $(OBJ)
  11.  
  12. %.o: %.c $(INC) Makefile
  13. 	$(CC) -c $< 
  14.  
  15. clean:
  16. 	rm -f $(OBJ) textmx
  17.  

Ćwiczenia 1

c1-mx1.c

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include "c1-mx1.h"
  4. /* drukuje zadana macierz A wymiaru n */"%5.2f ""\n"/* wypelnia macierz A wymiaru n kolejnymi liczbami */#ifdef DEBUG
  5. #define N 4
  6. #endif
  7.  

c1-mx1.h

  1.  

c1-mx2.c

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include "c1-mx2.h"
  4. /* drukuje zadana macierz A wymiaru nxm */"%5.2f ""\n"/* wypelnia macierz A wymiaru nxm kolejnymi liczbami *//* alokuje pamiec na macierz A wymiaru nxm i zwraca wskaznik do niej *//* mozesz poprawic te funkcje tak, by w przypadku braku pamieci:
  5. 	- usuwala dotychczas zarezerwowane wiersze
  6. 	- usuwala pamiec przydzielona na A
  7. 	- zwracala NULL
  8. *//* usuwa z pamieci macierz A o n wierszach */#ifdef DEBUG
  9. #define N 4
  10. #define M 3
  11. #endif
  12.  

c1-mx2.h

  1.  

c1-testmx.c

  1. #include "c1-mx1.h"
  2.  
  3. #define N 9
  4. /* test dla macierzy 1d: X */

c14-google.c

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4.  
  5. #define MAXIT 5000 /* liczba iteracji algorytmu PageRank */
  6. /* wskaĹşnik do pomocniczego wektora roboczego */
  7.  
  8. /* do reprezentacji grafu rzadkiego wykorzystamy tym razem macierz rzadką *//* macierz kwadratowa rzadka w formacie współrzędnych *//* liczba krawędzi, tj. liczba niezerowych elementów *//* liczba wierzchołków grafu, tj. wymiar macierzy *//* tablice wymiaru nnz *//* wyznacza normę sum_i |x_i| wektora x *//* wczytuje macierz rzadką z pliku formatu:
  9. n nnz
  10. I[0] J[0] V[0]
  11. I[1] J[1] V[1]
  12. I[2] J[2] V[2]
  13. ....
  14. I[nnz-1] J[nnz-1] V[nnz-1]
  15.  
  16. UWAGA: w tym formacie indeksy są numerowane od "1" 
  17. */
  18. {
  19. FILE *fp; /* plik z ktĂłrego czytamy macierz */
  20. SparseMx A; /* wczytywana macierz */"r");
  21. fscanf(fp, "%d%d", &A.n, &A.nnz);
  22.  
  23. /* znamy wymiary, wiec alokujemy niezbedne tablice *//* czytamy kolejne wartosci z pliku */"%d%d%lf\n"/* oblicza y = A*x; por. SparseMultSlow() *//* algorytm obliczania Ax w innej niz "standardowa" kolejnosci *//* ta funkcja jeszcze nie działa poprawnie; uzupełnij puste miejsce! */
  24. 	/* wskazówką jest postać głównej pętli! *//* zwraca A[i][j], gdzie A jest w formacie współrzędnych *//* y = A*x, ale BARDZO wolno; por. SparseMult() *//* indeksy w macierzy są od "1" *//* wyznacza wektor taki, ze w przyblizeniu A*p = p, stosujac metode potegowa 
  25. dla wektora startowego p; w trakcie iteracji wektor p jest nadpisywany przez lepsze przyblizenia *//* work = A*x; WERSJA SLIMACZA */
  26.  
  27. 	norm = VecNorm(work, N); /* p = work/norm(work) */#ifdef DEBUG
  28. //G = SparseRead("c14-lab.txt"); /* graf, w którym występują liście; tam algorytm może mieć problemy */
  29. G = SparseRead("c14-test.txt"/* pomocniczy wektor roboczy */"%e\n"#endif
  30.  

c1-Makefile

  1. # przed uzyciem, zmien nazwe tego pliku na "Makefile"
  2.  
  3. CC = gcc
  4. OBJ = c1-testmx.o c1-mx1.o c1-mx2.o
  5. INC = c1-mx1.h c1-mx2.h
  6.  
  7. testmx: $(OBJ)
  8. 	$(CC) -o $@ $(OBJ)
  9.  
  10. %.o: %.c $(INC) Makefile
  11. 	$(CC) -c $< 
  12.  
  13. clean:
  14. 	rm -f $(OBJ) textmx
  15.  
Piotr Krzyżanowski | Aktualizacja: 02.03.2019, 23:18:45.