Makefile pentru C

Exemplu de makefile:

build:
gcc [nume_fisiere] -o [nume_fis_exe]

clean:
rm [nume_fis_exe]
rm -f *~ core

Hash tables

Urmatorul program creeaza o structura de date Hash - o structura care asociaza unei anumite chei (indicele vectorului Hash[]) o lista de vectori de elemente (ale unei multimi), avand cardinalul card. Lista este simplu-inlantuita.
Se mai verifica si daca o anumita multime A poate fi acoperita de multimi de un anumit cardinal din Hash table.

#include "stdio.h"
#include "stdlib.h"

typedef struct lista {
int * elem;
int card;
struct lista *leg;
} * Hash;

void insert (int * multime,int card, Hash * L) {
Hash ins = (Hash)malloc(sizeof(struct lista));
ins->elem = multime;
ins->leg = NULL;
ins->card = card;
if (*L == NULL) {
*L = ins; return ; }
else {
Hash aux = *L;
while (aux->leg !=NULL)
aux= aux->leg;

aux->leg = ins; }
}

void printvect (int * v,int n) {

int i;
for(i=0;i < n;i++)
printf( "%d ", v[i]);
printf("\n");
}


void afisare (Hash h, int i) {

Hash aux;
if (h != NULL) {
aux = h;
printf("h[%d] = \n",i);
while (aux != NULL)
{
printvect(aux->elem,aux->card);
aux = aux->leg;
}
}
}

int exista (Hash h, int elem) {

if(h==NULL)
return 0;
Hash aux = h;
int ok =0;
while (aux) {
int c = aux->card, i;
for(i=0; i < c ; i++)
if (aux->elem[i]==elem) ok = 1;
if(ok ==1)
return 1;
aux = aux->leg;
}
return 0;

}

int main() {

Hash *h;
FILE * f = fopen("in", "r");
int n,i;
fscanf(f, "%d", &n);
h = (Hash *)malloc (n*sizeof(struct lista));
for(i=0; i < n ; i++)
h[i]= NULL;
while(!feof(f)) {
int m;
fscanf(f, "%d", &m);
int * v = (int *)malloc(m*sizeof(int));
for(i=0; i < m ;i++)
fscanf(f,"%d", &v[i]);
insert (v,m, &h[m]);
}
for(i=0; i < n ; i++)
afisare(h[i],i);

// multimea A de cardinal k poate fi acoperita de multimi de card. p din Hash table?
printf("\n\n");

FILE * ff = fopen ("in2", "r");
int *A, k,p;
fscanf(ff,"%d", &k);
A = (int *)malloc(k*sizeof(int));
for(i=0; i < k ;i++)
fscanf(ff,"%d", &A[i]);
fscanf(ff,"%d", &p);
int ok = 1;
for(i=0; i < k && ok; i++)
if(!exista(h[p], A[i]))
ok = 0;
if (ok==1) {
printf("da\n");
afisare(h[p],p);
}
else printf("nu\n");

return 0;
}

Functii in Haskell

allEqual a b c =
if a == b && a == c && b == c then True
else False

allDifferent a b c =
if a /= b && a /= c && b /= c then True
else False

howManyEqual a b c
| allEqual a b c = 3
| allDifferent a b c = 0
| otherwise = 2

-- calculeaza sirul fibonacci
fibonacci n
| n == 0 = 1
| n == 1 = 1
| otherwise = fibonacci(n -1) + fibonacci(n - 2)

-- creeaza o pereche ordonata
orderTuple a b
| a > b =(b, a)
| otherwise = (a, b)

-- daca un element apartine listei
member x [] = False
member x (h:t) =
if (h == x) then True
else member x t

-- produs cartezian a doua liste
cartProd a b = [(x,y) | x<-a, y<-b]

-- applies f to every element of list l and returns the new list
functie x = x+2
mapp f [a] = [f a]
mapp f (a:l) =
(f a):(mapp f l)

-- returns a list containing only the elements from list l, satisfying the predicate p
predicat x = x > 2
filterr p (a:l) =
if (p a) then a:(filter p l)
else filter p l

{- reduces a list to a value, going from left to right: applies f to the seed and the first list element,
then applies f to the result and the second element etc -}
f x y= x+y
foldleft f seed [] = seed
foldleft f seed l =
seed + foldleft f (head l) (tail l)

{- computes the sum of list elements, using foldleft -}
sumList l = foldleft f 0 l

{- reduces a list to a value, going from right to left: first computation is (f last_element seed) -}
foldright f elem [] = elem
foldright f seed l =
foldright f (head l) (tail l) + seed

{- returns the number of occurences of val in a, b, c -}
valOccurs val a b c
| a==val = 1+(valOccurs val (1-a) b c)
| b==val = 1+(valOccurs val a (1-b) c)
| c==val = 1+(valOccurs val a b (1-c))
| otherwise = 0

{- returns an ordered triple based on a, b, c -}
orderTriple a b c =
if (a<=b && b<=c) then (a,b,c)
else if (b<=a && a<=c) then (b,a,c)
else if (a<=c && c<=b) then (a,c,b)
else if(b<=c && c<=a) then (b,c,a)
else if (c<=a && a<=b) then (c,a,b)
else (c,b,a)

{- returns the minimum in a list -}
minim a b =
if (a < b) then a
else b
minVal (a:[]) = a
minVal (a:l) =
minim a (minVal l)

{- returns True if all list elements are equal -}
allEq [a] = True
allEq (a:l) =
if (a/= (head l)) then False
else allEq l

{- returns True if list is sorted ascending -}
ascOrd [a] = True
ascOrd (a:l) =
if (a > (head l)) then False
else ascOrd l

{- returns True if list p is a prefix of list l -}
startsWith [] lista = True
startsWith lista [] = False
startsWith p l =
if ((head p) /= (head l)) then False
else startsWith (tail p) (tail l)

{- removes the prefix p from list l -}
del p l =
if (p==[] && l /= []) then l
else del (tail p) (tail l)

{- substitutes all occurences of element old with element new in the list l -}
subst old new [] = []
subst old new (a:l) =
if (a == old) then new:(subst old new l)
else a:(subst old new l)

Tipuri de date in Haskell

-- tipul nr naturale

data Natural =
Zero |
Succ Natural
deriving Show

--fct pt predecesor
prede (Succ n) = n

-- egalitate
equal Zero Zero = True
equal (Succ n) Zero = False
equal Zero (Succ n) = False
equal m n =
if equal (prede m) (prede n)== True then True
else False

-- aduna 2 nr naturale
add n Zero = n
add m n =
Succ (add m (prede n))

-- diferenta a doua nr
subs n Zero = n
subs m n =
if (equal m n) then Zero
else prede (subs m ( prede n))

-- a mai mare ca b
gt (Succ n) Zero = True
gt Zero (Succ n) = False
gt m n =
if equal m n then False
else gt m n

-- a mai mic ca b
lt (Succ n) Zero = False
lt Zero (Succ n) = True
lt m n =
if equal m n then False
else lt m n

-- inmultire
mult n Zero = Zero
mult Zero n = Zero
mult (Succ n) (Succ Zero) = (Succ n)
mult (Succ Zero) (Succ n) = (Succ n)
mult m n =
add (mult (prede m) n) n


-- tipul List

data List a =
Empty |
Cons a (List a)
deriving Show

-- lungimea unei liste
lung Empty = 0
lung (Cons x lista) = 1 + lung lista

-- concatenare
conc Empty l = l
conc (Cons x lista) l =
Cons x (conc lista l)


-- tipul Tree, arbore binar de cautare

data Tree a =
Null |
Frunza a |
Nod (Tree a) a (Tree a)
deriving Show

-- inserare intr-un arbore binar
insert t Null = Frunza t
insert t (Frunza a) =
if (t < a) then Nod (Frunza t) a Null
else Nod Null a (Frunza t)
insert x (Nod left t right) =
if (x < t) then Nod (insert x left) t right
else Nod left t (insert x right)

-- construieste un arbore binar de cautare pornind de la o lista
constr Empty = Null
constr (Cons a lista) =
insert a (constr lista)

-- numara elem din arbore
numar Null = 0
numar (Frunza a) = 1
numar (Nod left x right) = 1 + numar left + numar right

-- adancimea arborelui
maxim a b =
if (a < b) then b
else a

adan Null = 0
adan (Frunza x) = 1
adan (Nod left x right) = 1 + maxim (adan left) (adan right)

-- o lista cu elem din arborele parcurs inordine - SRD (lista sortata)
srd (Frunza a) = Cons a Empty
srd Null = Empty
srd (Nod left a right) =
conc (srd left) (Cons a (srd right))

DFS si sortare topologica

Parcurgerea in adancime (Depth-First Search - DFS) porneste de la un nod dat (nod de start), care este marcat ca fiind in curs de procesare. Se alege primul vecin nevizitat al acestui nod, se marcheaza si acesta ca fiind in curs de procesare, apoi si pentru acest vecin se cauta primul vecin nevizitat, si asa mai departe. In momentul in care nodul curent nu mai are vecini nevizitati, se marcheaza ca fiind deja procesat si se revine la nodul anterior. Pentru acest nod se cauta primul vecin nevizitat. Algoritmul se repeta pana cand toate nodurile grafului au fost procesate. In urma aplicarii algoritmului DFS asupra fiecarei componente conexe a grafului, se obtine pentru fiecare dintre acestea cate un arbore de acoperire (prin eliminarea muchiilor pe care nu le folosim la parcurgere). Pentru a putea reconstitui acest arbore, pastram pentru fiecare nod dat identitatea parintelui sau.
Pentru fiecare nod se vor retine: timpul descoperirii, timpul finalizarii, parintele si culoarea.
Algoritmul de explorare DFS nu este nici complet (cautare pe un subarbore infinit) nici optimal (nu gaseste nodul cu adancimea minima).

Dandu-se un graf orientat aciclic, sortarea topologica realizeaza o aranjare liniara nodurilor in functie de muchiile dintre ele. Orientarea muchiilor corespunde unei relatii de ordine de la nodul sursa catre cel destinatie. Astfel, daca (u,v) este una dintre muchiile grafului, u trebuie sa apara inaintea lui v in insiruire. Daca graful ar fi ciclic, nu ar putea exista o astfel de insiruire (nu se poate stabili o ordine intre nodurile care alcatuiesc un ciclu).
Sunt doi algoritmi cunoscuti pentru sortarea topologica: algoritmul bazat pe DFS (parcurgere DFS pentru determinarea timpilor si sortare descrescatoare in functie de timpul de finalizare) un alt algoritm este cel descris de Kahn.

Programul de mai jos realizeaza o parcurgere DFS si o sortare topologica bazata pe aceasta a unui graf citit dintr-un fisier (dat ca liste de adiacenta).


#include "stdio.h"
#include "stdlib.h"
#include "assert.h"

struct Nod
{
int val;
int nrVecini;
int * vecini;
int culoare;
int parinte;
int tDescoperire;
int tFinal;
};

int n;
struct Nod * graf;

/* citeste lista de adiacenta din fisier */
void readData()
{
FILE * f;
int i, j;

f = fopen( "in2.txt","r" );
assert( f );

fscanf( f, "%d", &n );
graf = ( struct Nod * ) malloc ( n * sizeof( struct Nod ) );

for ( i = 0; i < n; ++i ) {
graf[i].val = i;
fscanf( f, "%d", &graf[i].nrVecini );
graf[i].vecini = ( int * ) malloc ( graf[i].nrVecini * sizeof ( int ) );
for ( j = 0; j < graf[i].nrVecini; ++j )
fscanf( f, "%d", &graf[i].vecini[j] );
graf[i].parinte = -1;
graf[i].culoare = 0;
graf[i].tDescoperire = -1;
graf[i].tFinal = -1;
}
fclose( f );
}

/* afisarea timpilor din alg DFS*/
void printTimpi()
{
int i;
printf( "\n" );
for ( i = 0; i < n; ++i )
printf ( "Nod %d: descoperit la t=%d, explorat la t=%d \n", i, graf[i].tDescoperire, graf[i].tFinal );
printf( "\n" );
}

int timp = 0;

/* parcurgere DFS a grafului */
void explorare(int u) {

graf[u].tDescoperire = timp++;
graf[u].culoare = 1;
int j;
for(j = 0 ; j < graf[u].nrVecini ; j++) {
int x = graf[u].vecini[j];
if(graf[x].culoare ==0) {
graf[x].parinte = u;
explorare(x);
}
}
graf[u].culoare = 2;
graf[u].tFinal = timp++;

}

void DFS ()
{
int i;
for (i=0; i < n ; i++)
if(graf[i].culoare == 0)
explorare(i);
}



/* sortare topologica */
void topSort()
{
int ok = 0,i,j;
struct Nod aux;
while (ok == 0) {
ok = 1;
for(i=0; i < n-1;i++)
if(graf[i].tFinal < graf[i+1].tFinal) {
ok = 0; aux = graf[i]; graf[i]=graf[i+1]; graf[i+1]=aux; }
}
}

int main(void){
int i;

//incarca graful din fisier
readData();

//parcurgere BFS
DFS();

//afisarea timpilor
printTimpi();

//sortare topologica
topSort();
printf( "Sortare topologoca: " );
for ( i = 0; i < n; ++i )
printf ( "%d ", graf[i].val );
printf("\n");

for( i = 0; i < graf[i].nrVecini; ++i )
free(graf[i].vecini);
free(graf);
return 0;
}