Notes

stive
#include <stdio.h>
#include <stdlib.h>
#include "stive.h"


void init_stack(t_stiva *s, int init_size)
{
s->data=(int *)malloc(init_size*sizeof(int));
s->top=0;
}
void free_stack(t_stiva *s)
{
free(s->data);
s->data=NULL;
s->top=-1;
}
int stack_empty(t_stiva s)
{
if(s.top==0)
return 1;
else return 0;
}
void print_stack(t_stiva s)
{
for(int i=1;i<=s.top;i++)
printf("%d ", s.data[i]);
}
void PUSH(t_stiva *s, int e)
{
s->top++;
s->data[s->top]=e;
}
int POP(t_stiva *s)
{
int e;
if(stack_empty(*s))
{
printf("Stiva e goalan");
return -1;
}
else
{
e=s->data[s->top];
s->data[s->top]=0;
s->top--;
return e;
}
}
#ifndef STIVE_H_INCLUDED
#define STIVE_H_INCLUDED

typedef struct stack {
int top;
int* data;
} t_stiva;

void init_stack(t_stiva *s, int init_size);
void free_stack(t_stiva *s);
int stack_empty(t_stiva s);
void print_stack(t_stiva s);
void PUSH(t_stiva *s, int e);
int POP(t_stiva *s);

#endif // STIVE_H_INCLUDED
#include <stdio.h>
#include <stdlib.h>
#include "stive.h"

int main()
{
t_stiva s;
int e=-1;
init_stack(&s,20);
while(e!=0)
{
printf("ne= ");scanf("%d", &e);
PUSH(&s, e);
print_stack(s);
}
while(!stack_empty(s))
{
POP(&s);
printf("n");
print_stack(s);

}
free_stack(&s);
return 0;
}

hash_table
#include <stdio.h>
#include <stdlib.h>
#include "table.h"
int main()
{
int t[50],m,k,j,a,b,c;
printf("m= "); scanf("%d", &m);
printf("a= "); scanf("%d", &a);
printf("b= "); scanf("%d", &b);
printf("c= "); scanf("%d", &c);
Hash_init(t,m);
printf("Dati numere pana la citirea lui 0: n");
scanf("%d",&k);
while(k!=0)
{
j=Hash_insert(t,a,b,c, k, m);
printf("Cheia inserata la locatia %d n", j);
scanf("%d", &k);
}
Hash_print(t,m);

printf("n Cautare cheie: n");
scanf("%d",&k);
j=Hash_search(t,a,b,c,k,m);
if(j>-1)
printf("Cheia gasita la locatia %d n", j);
else
printf("Cheia nu a fost gasita");

printf("n Stergere cheie: ");
scanf("%d", &k);
j=Hash_delete(t,a,b,c,k,m);
if(j>-1)
{
printf("Cheia stearsa de la locatia %d n", j);
Hash_print(t,m);
}
else printf("Cheia nu a fost stearsa");
return 0;
}
#ifndef ADRESAREDESCHISA_H_INCLUDED
#define ADRESAREDESCHISA_H_INCLUDED

void Hash_init(int t[], int m);
int Hash_prim(int k, int m);
int Hash_probef(int k, int a, int b, int c, int i, int m);
int Hash_ecuatie(int x, int a, int b, int c, int m);
int Hash_insert(int t[], int a, int b, int c, int k, int m);
int Hash_search(int t[], int a, int b, int c, int k, int m);
int Hash_delete(int t[], int a, int b, int c, int k, int m);
void Hash_print(int t[], int m);

#endif // ADRESAREDESCHISA_H_INCLUDED
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "table.h"

void Hash_init(int t[], int m)
{
int i;
for(i=0;i<m;i++)
t[i]=-1;
}
void Hash_print(int t[], int m)
{
for(int i=0;i<m;i++)
printf("%d ", t[i]);
}
/*int Hash_prim(int k, int m)
{
return k%m;
}
int Hash_probef(int k, int i, int m)
{
return (Hash_prim(k,m)+i)%m;
}*/
int Hash_ecuatie(int k, int a, int b, int c, int m)
{
return (a*k*k+b*k+c)%m;
}
int Hash_probef(int k, int a, int b, int c, int i, int m)
{
return (Hash_ecuatie(k, a, b, c, m)+i)%m;
}
int Hash_insert(int t[], int a, int b, int c, int k, int m)
{
int i=0, j;
do{
j=Hash_probef(k,a,b,c,i,m);
if(t[j]==-1)
{
t[j]=k;
return j;
}
else i++;
}while(i!=m);
return -1;
}
int Hash_search(int t[], int a, int b, int c, int k, int m)
{
int i=0, j;
do
{
j=Hash_probef(k,a,b,c,i,m);
if(t[j]==k)
return j;
i++;
}while(i!=m&&t[j]!= -1);
return -1;
}
int Hash_delete(int t[], int a, int b, int c, int k, int m)
{
int j;
j=Hash_search(t,a,b,c,k,m);
if(j>-1)
{
t[j]=-1;
return j;
}
else return -1;
}
arbore
#include <stdio.h>
#include <stdlib.h>
#include "arbore.h"

int main()
{
t_arbore *t; int x;
t_nod *n, *r, *s;
printf("Nodul radacina cu cheia x= n");
scanf("%d", &x);
r=make_root(&t,x);
printf("Introduceti chei pentru noduri pana la valoarea 0: n");
printf("x= ");
scanf("%d", &x);
while(x!=0)
{
n=create_node(x);
tree_insert(&t,n);
printf("x= ");
scanf("%d", &x);
}
printf("IN-order walk: ");
inorder_walk(r);
printf("n");
printf("PRE-order walk: ");
preorder_walk(r);
printf("n");
printf("POST-order walk: ");
postorder_walk(r);
printf("n");
printf("Cautare nod cu cheia: ");
scanf("%d", &x);
n=tree_search(r,x);
if(n!=NULL)
printf("Nodul cu cheia %d a fost gasit", x);
else printf("Nodul nu a fost gasit");
printf("Sterge nod cu cheia: ");
scanf("%d, &x");
n=tree_search(r,x);
if(n!=NULL)
{
tree_delete(t,n
printf("Nod sters! n");
inorder_walk(r);

}
else printf("Nod negasit");
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include "arbore.h"

int make_root(t_arbore *a, int x)
{
a->root=(t_nod*)malloc(sizeof(t_nod));
a->root->key=x;
a->root->left=NULL;
a->root->right=NULL;
a->root->parent=NULL;
return a->root;
}

int create_node(int x)
{
t_nod *n;
n=(t_nod*)malloc(sizeof(t_nod));
n->key=x;
n->left=NULL;
n->right=NULL;
n->parent=NULL;
return n;
}
void tree_insert(t_arbore *a, t_nod *n)
{

t_nod *x; t_nod *y;
y=NULL;
x=a->root;
while(x!=NULL)
{
y=x;
if(n->key<x->key)
x=x->left;
else
x=x->right;
}
n->parent=y;
if(y==NULL)
a->root=n;
else if(n->key<y->key)
y->left=n;
else y->right=n;
}
void postorder_walk(t_nod *root)
{
if(root!=NULL)
{
postorder_walk(root->left);
postorder_walk(root->right);
printf("%d ", root->key);
}
}
void inorder_walk(t_nod *root)
{
if(root!=NULL)
{
inorder_walk(root->left);
printf("%d ", root->key);
inorder_walk(root->right);
}
}
void preorder_walk(t_nod *root)
{
if(root!=NULL)
{
printf("%d ", root->key);
preorder_walk(root->left);
preorder_walk(root->right);
}
}
void tree_search(t_nod a, int k)
{
if(n==NULL || k=n->key)
return n;
if(k < n->key)
return tree_search(n->left, k);
else
return tree_search((n->right, k);
}
int tree_min(t_nod *n)
{
while(n->left != NULL)
n=n->left;
return n;
}
int tree_max(t_nod *n)
{
while(n->right != NULL)
n=n->right;
return n;
}
void transplant(t_arbore *a, t_nod *u, t_nod *v)
{
if(u.parent==NULL)
a->root=v;
else if(u==u->parent->left)
u->parent->left=v;
else
u->parent->right=v;
if(v!=NULL)
v->parent=u->parent;
}

void tree_delete(t_arbore *a, t_nod *n)
{
t_nod *y;
if(n->left==NULL)
transplant(a,n,n->right);
else if(n->right==NULL)
transplant(a,n,n->left);
else
{
y=tree_min(n->right);
if(y->parent != n)
{
transplant(a,y, y->right)
y->right=n->right;
y->right->parent=y;
}
transplant(a,n,y);
y->left=n->left;
y->left->parent=y;
}
}
#ifndef ARBORCAUTARE_H_INCLUDED
#define ARBORCAUTARE_H_INCLUDED

typedef struct nod_arb
{
int key;
struct nod_arb *left, *right, *parent;
} t_nod;

typedef struct
{
t_nod *root;
}t_arbore;

int make_root(t_arbore *a, int x);
int create_node(int x);
void postorder_walk(t_nod *root);
void inorder_walk(t_nod *root);
void preorder_walk(t_nod *root);
int tree_min(t_nod n);
int tree_max(t_nod n);
int tree_succesor(t_nod n);
void tree_insert(t_arbore *a, t_nod *n);
void transplant(t_arbore *a, t_nod *u, t_nod *v);
void tree_search(t_nod n, int k);
void tree_delete(t_arbore *a, t_nod *n);


#endif // ARBORCAUTARE_H_INCLUDED



kruskal
#include<stdio.h>
#include<limits.h>
#include<stdlib.h>
typedef struct nod_lista
{
int d,f,cheie;
struct nod_lista *next, *prev;
}t_nod_lista;
typedef struct
{
t_nod_lista *head;
}t_lista;
typedef struct
{
t_nod_lista *src,*dest;
int weight;
}t_edge;
t_lista g[100];
t_edge edges[100];
t_edge a[100];
void makenull(t_lista *l)
{
l->head=(t_nod_lista *)malloc(sizeof(t_nod_lista));
l->head->next=NULL;
l->head->prev=NULL;
}

void init_lista(t_lista g[], int n)
{
int i;
for(i=1;i<=n;i++)
makenull(&g[i]);
}
void list_insert(t_lista *g, t_nod_lista *x)
{
if (x==NULL)
return;
x->next=g->head->next;
if(g->head->next!=NULL)
g->head->next->prev=x;
g->head->next=x;
x->prev=g->head;
}
void insert_vecini(t_lista g[], int n, int ns, t_edge edges[], int *k)
{
t_nod_lista *nod;
t_edge e;
int nv=-1;
int w;
printf("Nod sursa %d: n",ns);
g[ns].head->cheie=ns;
printf("Dati vecinii nodului sursa:n ");
while(nv!=0)
{
printf("Vecin cu %d: ",ns);
scanf("%d",&nv);
if(nv>0 && nv<=n && nv!=ns)
{
nod=(t_nod_lista *)malloc(sizeof(t_nod_lista));
nod->cheie=nv;
list_insert(&g[ns],nod);
printf("Introduceti weight pt arcul %d-%d: ",ns,nv);
scanf("%d",&w);
e.weight=w;
e.src=g[ns].head;
e.dest=nod;
(*k)++;
edges[*k]=e;
}
}

}
void print_lista(t_lista g[], int n)
{
t_nod_lista *nod;
int i;
for(i=1;i<=n;i++)
{
nod=g[i].head->next;
printf("n%d: ",i);
while(nod!=NULL)
{
printf("%3d",nod->cheie);
nod=nod->next;
}
}
}
int partition(t_edge *g, int p, int r)
{
int i,j,x;
t_edge aux;
x=g[r].weight;
i=p-1;
for(j=p;j<=r-1;j++)
{
if(g[j].weight<=x)
{
i++;
aux=g[i];
g[i]=g[j];
g[j]=aux;
}
}
aux=g[i+1];
g[i+1]=g[r];
g[r]=aux;
return i+1;

}
void quicksort(t_edge *g, int p, int r)
{
int q=0;
if(p<r)
{
q=partition(g,p,r);
quicksort(g,p,q-1);
quicksort(g,q+1,r);
}
}
void make_set(t_nod_lista *x)
{
x->prev=x;
x->d=0;
}
t_nod_lista *find_set(t_nod_lista *x)
{
if(x!=x->prev)
x->prev=find_set(x->prev);
return x->prev;
}
void link(t_nod_lista *x, t_nod_lista *y)
{
if(x->d>y->d)
y->prev=x;
else
{
x->prev=y;
if(x->d==y->d)
y->d=y->d+1;
}

}
void uniune(t_nod_lista *x, t_nod_lista *y)
{
link(find_set(x),find_set(y));
}
void mst_kruskal(t_lista g[], t_edge edges[] ,int n)
{
int i;
int nrel=0;
for(i=1;i<=n;i++)
make_set(g[i].head);
quicksort(edges,1,n);
for(i=1;i<=n;i++)
{
if(find_set(edges[i].dest)!=find_set(edges[i].src))
{
a[nrel++]=edges[i];
uniune(edges[i].src,edges[i].dest);
}
}
for(i=1;i<=nrel;i++)
printf("%3d",a[i]);

}
void main(void)
{
int n,i;

t_edge arc;
int k=0;
printf("dati numarul de noduri: ");
scanf("%d",&n);
init_lista(g,n);
for(i=1;i<=n;i++)
{
insert_vecini(g,n,i,edges,&k);
//k++;
//edges[k]=arc;
}
printf("Lista adiacenta: ");
print_lista(g,n);
printf("nKruskal:n");
mst_kruskal(g,edges,n);
}



rosu cu negru
#include <stdio.h>
#include <stdlib.h>

typedef struct rb_node
{
enum {red, black } color;
int key;
struct rb_node *left,
*right,
*parent;
} t_rb_node;
typedef struct
{
t_rb_node *root;
} t_rb_arbore;

int make_root(t_rb_arbore *a,int key)
{
t_rb_node *root;
a->root=malloc(sizeof *root);
a->root->key=key;
a->root->left=NULL;
a->root->right=NULL;
a->root->parent=NULL;
a->root->color=black;

return a->root;
}
int create_node(int key)
{
t_rb_node *node;
node=(t_rb_arbore*)malloc(sizeof(t_rb_node));
node->key=key;
node->left=NULL;
node->right=NULL;
node->parent=NULL;
node->color=black;
return node;
}

void inorder_walk(t_rb_node *root)
{
if(root != NULL)
{
inorder_walk(root->left);
printf("%d",root->key);
if (root->color=black)
printf("[b]");
else
printf("[r]");
}
inorder_walk(root->right);
}
int tree_search(t_rb_node *n, int key)
{
if( n==NULL)
if(key=n->key)
return n;
if (key < n->key)
return tree_search(n->left, key);
else
return tree_search(n->right, key);

}


void rb_insert(t_rb_arbore *a, t_rb_node *z)
{
t_rb_node *y=NULL;
t_rb_node *x=a->root;
while(x!=NULL)
{
y=x;
if(z->key < x->key)
x=x->left;
else
x=x->right;
}
z->parent=y;
if(y=NULL)
{
a->root=z;
}
else if (z->key < y->key)
y->left=z;
else
{
y->right=z;
}


z->left=NULL;
z->right=NULL;
z->color=red;
rb_insert_fixup(a,z);




}
void rb_insert_fixup(t_rb_arbore *a,t_rb_node *z)
{ t_rb_node *y;

while((z->parent!=NULL)&&(z->parent->color==red))
{
if(z->parent==z->parent->parent->left)
{
y=z->parent->parent->right;
if((y!=NULL)&&(y->color==red))
{
z->parent->color=black;
y->color=black;
z->parent->parent->color=red;
z=z->parent->parent;
}
else
{
if(z==z->parent->right)
{
z=z->parent;
left_rotate(a,z);
}
z->parent->color=black;
z->parent->parent->color=red;
right_rotate(a,z->parent->parent);
}
}
else


{
y=z->parent->parent->left;
if((y!=NULL)&&(y->color==red))
{
z->parent->color=black;
y->color=black;
z->parent->parent->color=red;
z=z->parent->parent;
}
else
{
if(z==z->parent->left)
{
z=z->parent;
right_rotate(a,z);
}
z->parent->color=black;
z->parent->parent->color=red;
left_rotate(a,z->parent->parent);
}
}
}
a->root->color=black;
}

void left_rotate(t_rb_arbore *a, t_rb_node *x)
{
t_rb_node *y;
y=x->right;
x->right=y->left;
if(y->left != NULL)
y->left->parent=x;
y->parent=x->parent;
if(x->parent=NULL)
a->root=y;
else if(x=x->parent->left)
x->parent->left=y;
else
x->parent->right=y;
y->left=x;
x->parent=y;
}

int main()
{
t_rb_arbore a;
t_rb_node r;
t_rb_node n;
int x;
printf("ROOT=");
scanf("%d", &x);
make_root(&a, x);
printf("introduceti x pana la citirea lui n");
printf("x=");
scanf("%d", &x);
while(x!=0)
{
n=create_node(x);
rb_insert(&a,x);
printf("x=");
scanf("%d", &x);

}
printf("In-order walk: ");
inorder_walk(x);
printf("n");
printf("Cauta un nod cu cheia x= ");
scanf("%d", &x);
n=tree_search(&a, x);
if(n!=NULL)
printf("nodul cu cheia %(n->key) gasit");
else
printf("nodul nu a fost gasit")


return 0;

}
int main()
{

t_rb_arbore a;
t_rb_node *n;
int x;
printf("root=");
scanf("%d",&x);
make_root(&a,x);
printf("Introduceti x pana la citirea 0n");
printf("x=");
scanf("%d",&x);
while(x!=0)
{
n=create_node(x);
rb_insert(&a,n);
printf("x=");
scanf("%d",&x);
}
printf("Nodul care se insereaza este:");
scanf("%d",&x);

if(x!=0)
{
n=create_node(x);
rb_insert(&a,n);
}
return 0;
}




belman si djdjd
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
typedef struct nod_lista
{
enum {white, gray,black} color;
int d,f;
int key;
struct nod_lista *prev,*next;
}t_nod_lista;
typedef struct
{
t_nod_lista *head;
}t_lista;
typedef struct
{
t_nod_lista *src,*dest;
int weight;
}t_edge;
void MAKENULL(t_lista *L)
{
L->head=(t_nod_lista*)malloc(sizeof(t_nod_lista));
L->head->next=NULL;
L->head->prev=NULL;
}
t_nod_lista* LIST_SEARCH(t_lista L, int k)
{
t_nod_lista *x=L.head;

while((x!=NULL)&&(x->key!=k))
x=x->next;
return x;
}
void LIST_DELETE(t_lista *L,t_nod_lista *x)
{
if (x==NULL) return;
if(x->prev!=NULL) x->prev->next=x->next;
else L->head=x->next;
if(x->next!=NULL) x->next->prev=x->prev;
}

void LIST_FREE(t_lista *L)
{
t_nod_lista* x=L->head->next;
while(x)
{
LIST_DELETE(L,x);
free(x);
x=L->head->next;
}

}
void LIST_INSERT(t_lista *L,t_nod_lista *x)
{
if(x==NULL) return;
x->next=L->head->next;
if(L->head->next!=NULL)
L->head->next->prev=x;
L->head->next=x;
x->prev=L->head;
}
void LIST_PRINT(t_lista L)
{
t_nod_lista *x;
x=L.head->next;
if(x==NULL)
printf("Lista vida!n");
for(;x;x=x->next) printf("%3d",x->key);
}







t_edge insert_vecini(t_lista g[],int n,int ns, t_edge edge[], int *k)
{
t_nod_lista *nod;
t_edge e;
int w,nv;

printf("Nod sursa %dn",ns);
g[ns].head->key=ns;
printf("Dati vecinii nodului sursa:n");
do
{
printf("Vecin cu %d: ",ns);
scanf("%d",&nv);
if((nv>0) && (nv<=n)&&(nv!=ns))
{
nod=(t_nod_lista*)malloc(sizeof(t_nod_lista));
nod->key=nv;
LIST_INSERT(&g[ns],nod);
printf("Introduceti weight pt arcul %d-%d: ",ns,nv);
scanf("%d",&w);
e.weight=w;
e.src=g[ns].head;
e.dest=nod;
(*k)++;
edge[*k]=e;
}
}
while(nv>0);
return e;
}
void init_lista(t_lista g[],int n)
{
int i;
for(i=1;i<=n;i++)
MAKENULL(&g[i]);
}
void print_lista(t_lista g[],int n)
{
t_nod_lista *nod;
int i;
for(i=1;i<=n;i++)
{
nod=g[i].head->next;
printf("n%d ",i);
while(nod!=NULL)
{
printf("%d",nod->key);
nod=nod->next;
}
printf("n");
}
}




void initialize_single_source(t_lista g[],t_nod_lista *s,int n)
{
int i;
t_nod_lista *v;
for(i=1;i<=n;i++)
{ v=g[i].head;
v->d=INT_MAX;
v->prev=NULL;
}
s->d=0;

}
void relax(t_nod_lista *u, t_nod_lista*v,int w)
{
if((v->d)>(u->d+w))
{
v->d=u->d+w;
printf("Nod nou %d:n",v->key);
v->prev=u;
}

}
int bellman_ford(t_lista g[],t_edge w[],int s, int n,int r)
{
int i,j;
t_nod_lista *ns;
ns=g[s].head;
initialize_single_source(g,ns,n);
for(i=1;i<=n;i++)
for(j=1;j<=r;j++)
relax(g[w[j].src->key].head,g[w[j].dest->key].head,w[j].weight);
for(i=1;i<=r;i++)
if((g[w[i].dest->key].head->d)>(g[w[i].src->key].head->d+w[i].weight))
return 0;
return 1;
}
void print_path(t_lista g[],t_nod_lista *s, t_nod_lista *v)
{
if(v==s)
printf("%d",s->key);
else
if(v->prev==NULL)
printf("Nu exista cale!");
else
{
print_path(g,s,v->prev);
printf("%d ",v->key);
}
}
t_nod_lista * extract_min(t_nod_lista *q[],int n)
{
int i,j,min=INT_MAX;
t_nod_lista *u;
for(i=1;i<=n;i++)

if(q[i]->d<min)
{
min=q[i]->d;
u=q[i];
j=i;
}

for(i=j;i<n;i++)
q[i]=q[i+1];
return u;


}
int get_weight (t_edge w[], t_nod_lista *u,t_nod_lista*v, int nr_arce)
{
int i;
for(i=1;i<=nr_arce;i++)
if((w[i].src->key==u->key)&&(w[i].dest->key==v->key))
return w[i].weight;
return 0;
}
void relax_d(t_nod_lista *u, t_nod_lista*v,int w,t_nod_lista *q[], int n)
{
int i;
if((v->d)>(u->d+w))//distanta sin nodul sursa>suma din nodul destinatie si
{
v->d=u->d+w;
for(i=1;i<=n;i++)
if(q[i]->key==v->key)
q[i]->d=u->d+w;
printf("Nod nou %d:n",v->key);
v->prev=u;
}
}

void dijkstra(t_lista g[],t_edge w[],int s,int n,int nr_arce)//ss-sirul solutiilor, l-nr noduri
{
t_nod_lista *ss[100],*q[100],*u,*v,*ns;
int i, weight=0,l=0;
ns=g[s].head;
initialize_single_source(g,ns,n);
for(i=1;i<=n;i++)
q[i]=g[i].head;
while(n>0) //cat tim mai am noduri in coada
{
u=extract_min(q,n);//returneaza nodul cu d minim
n--;
l++;
ss[l]=u;
v=g[u->key].head;
while(v!=NULL)
{
weight=get_weight(w,u,v,nr_arce);
relax_d(g[u->key].head,g[v->key].head,weight,q,n);
v=v->next;
}
}
printf("Dijkstra: ");
for(i=1;i<=l;i++)
printf("%d",ss[i]->key);
}
int main(void)
{
t_lista g[100];
int k=0,n,i,s;

t_edge edges[100];
printf("Nr noduri=");
scanf("%d",&n);
init_lista(g,n);

for(i=1;i<=n;i++)
{
insert_vecini(g,n,i,edges,&k);
}
printf("Arcele:");
for(i=1;i<=k;i++)
printf("%d -%d (%d)n:",edges[i].src->key,edges[i].dest->key,edges[i].weight);
printf("Nod pornire:");
scanf("%d",&s);
i=bellman_ford(g,edges,s,n,k);
//printf("%d",i);
print_path(g,g[s].head,g[n].head);
dijkstra(g,edges,s,n,k);
return 0;

}