Cuprins Limbajul C

Gandirea algoritmica
Structura unui program si a unei functii in C
Constructiile de bază ale limbajului C – Notiuni generale
Constructiile de baza ale limbajului C – Tipuri de date
Constructiile de baza ale limbajului C – Operatori
Structuri de date – Lista liniara simplu inlantuita
Structuri de date – Stiva (LIFO – Last In First Out)
Structuri de date – Coada (FIFO – First In First Out)
Instructiuni ale limbajului C
Pointeri – Operatori specifici, tablouri, functii
Pointeri – Tipuri structurate de date
Functii de biblioteca
Operatii cu fisiere
Calcul Matriceal – Produsul a doua matrici
Calcul Matriceal – Inversarea unei matrici
Calcul Matricial – Metoda lui Gauss
Metode de sortare – sortare ordinara
Metode de sortare – prin selectie (Selection sort)
Metode de sortare – insertie directa (Direct Insertion Sort)
Metode de sortare – insertie binara (Binary Insertion Sort)
Metode de sortare – insertie directa folosind o santinela
Metode de sortare – metoda bulelor (Bubble Sort)
Metode de sortare – sortare rapida (Quick Sort)
Metode de sortare – prin interclasare (Merge Sort)
Recursivitate (numar factorial, algoritmul lui Euclid recursiv, sirul lui Fibonacci)
Backtracking – permutarile
Backtracking – aranjamente
Backtracking – combinari
Backtracking – problema reginelor
Backtracking – problema labirintului
Backtracking – problema calului
Backtracking – problema mingii
Metoda Divide et Impera – Suma elementelor unui sir
Metoda Divide et Impera – Problema Turnurilor din Hanoi
Metoda Divide et Impera – Elementul maxim intr-un sir
Metoda Divide et Impera – Problema cautarii binare
Grafuri neorientate – parcurgerea in latime
Grafuri neorientate – parcurgerea in adancime
Grafuri neorientate – Drumuri intr-un graf
Grafuri neorientate – ponderate
Grafuri neorientate – hamiltonian
Grafuri neorientate – euleriene
Grafuri neorientate – implementarea unui graf utilizand matricea de adiacenta
Grafuri neorientate – implementarea unui graf utilizand pointeri
Grafuri neorientate – drumul optim intr-un graf

Grafuri neorientate – drumul optim intr-un graf

Una din problemele care apar foarte des în practică este găsirea drumului optim între două noduri ale unui graf.

Formalizarea problemei drumului optim este următoarea:

“Fiind dat un graf G = (X,U) şi o funcţie care asociază fiecărui arc o valoare reală, să se găsească, pentru o pereche dată de noduri, drumul (drumurile) de valoare optimă (minimă sau/şi maximă) între cele două noduri şi valoarea acestuia (acestora)”.

Valoarea unui drum este dată de suma valorilor arcelor care îl compun. Pentru problema drumului optim s-au elaborat mai multe categorii de algoritmi, după cum urmează:

Algoritmi prin calcul matricial (Bellman-Kalaba, I. Tomescu, Bellman-Schimbell)
Algoritmi prin ajustări succesive (Ford)
Algoritmi prin inducţie (Dantzig)
Algoritmi prin ordonare prealabilă a vârfurilor grafului
Algoritmi prin extindere selectivă (Dijkstra)

Grafuri neorientate – implementarea unui graf utilizand pointeri

Pentru a defini un graf utilizând pointeri, vom defini următoarele structuri:
typedef struct NODL
{
  //nodul adiacent indicat
  struct NODG *nod;
  //pointer spre următorul nod în lista de adiacenţe
  struct NODL *urml;
} nodl;

typedef struct NODG
{
  int cheie;
  … informaţii
  //începutul şi sfârşitul listei de adiacenţă
  struct NODL *inc_lista, *sfarsit_lista;
  //pointer spre următorul nod al grafului
  struct NODG *urmg;
} nodg;

//începutul şi sfârşitul listei de noduri din graf
struct nodg *incG, *sfG;

Grafuri neorientate – implementarea unui graf utilizand matricea de adiacenta


//definirea tipului nod
typedef TIP_NODG
{
  int cheie;
  ... informaţii
} tip_nodg;
ntip_nodg nod[Nmax];
//tabloul de noduri
//Nmax este numărul maxim de noduri
int arc[N max] [N max];
//matricea de adiacenţă

Adăugarea unui nod cu cheia key:
int i;
nod[N].cheie=key;
//adăugăm nodul N+1
for(i=0;i < = N;i++)   arc[i][N]=arc[N][i]=0; //iniţalizarea cu o a conexiunilor cu celelalte noduri N++; //incrementarea numărului de noduri Continue reading

Grafuri neorientate – euleriene

Fiind dat un graf neorientat, să se determine dacă este eulerian, iar dacă răspunsul este afirmativ, să se determine toate ciclurile euleriene care încep dintr-un nod dat.

Pentru a rezolva această problemă, vom parcurge următorii paşi:
• se determină dacă graful este conex
• se determină dacă fiecare nod are grad par


#include "stdio.h"
#include "conio.h"
int a[10][10],viz[10],n,m;
//parcurgere in adâncime
void df_r(int nod)
{
  int k;
  //afişăm nodul curent ca vizitat
  printf("%d ",nod);
  //marcăm nodul curent ca vizitat
  viz[nod]=1;
  //pentru fiecare nod k
  for(k=1;k < = n;k++)     //dacă există muchie între nodul curent şi nodul k şi nodul k nu a fost incă vizitat,     //apelăm funcţia recursivă de vizitare depth first df_r având ca parametru nodul k     if(a[nod][k] && !viz[k])       df_r(k); } Continue reading

Grafuri neorientate – hamiltonian

Se citeşte matricea de adiacenţă a unui graf. Să se determine dacă graful este hamiltonian.

Soluţie: vom folosi metoda backtracking, aplicată asupra unei stive în care vom păstra nodurile care compun lanţul. Vom porni de la primul nod şi vom putea adăuga în stivă doar un nod adiacent. De asemenea, nodul adăugat nu trebuie să se regăsească pe nivelurile anterioare. Dacă am atins în stivă numărul total de noduri iar nodul final este adiacent cu nodul iniţial, am găsit soluţia problemei.


#include "stdio.h"
#include "conio.h"
int stiva[100],n,m,k,nr_solutii,a[20][20];
int verifica()
{
  int i;
  if(k>1)
    //dacă a[st[k-1]][st[k]] este 0 returnăm 0
    if(!a[stiva[k-1]][stiva[k]])
       return 0;
    else
      //dacă a [stiva[k-1]][stiva [k]] este 1 căutam pe toate nivelurile
      //anterioare nivelului curent
      for(i=1;i < = k-1;i++)         //dacă nodul curent se găseşte pe unul din nivelurile         //anterioare returnăm 0         if(stiva[i] == stiva[k])           return 0;         //dacă stiva conţine toate nodurile grafului         if(k == n)           //iar ultimul nod nu este adiacent cu primul nod returnăm 0           if(!a[stiva[1]][stiva[k]])             return 0;   return 1; } Continue reading

Grafuri neorientate – ponderate

Într-un graf neorientat, fiecărei muchii i se poate asocia o pondere (un cost). Putem considera un graf neorientat fără ponderi ca fiind o particularizare a unui graf cu costuri, fiecare muchie având costul 1. Această pondere (sau cost) va exprima intensitatea relaţiei dintre 2 noduri ale grafului.

Reprezentarea unui astfel de graf G=(X,U) se face utilizând o matrice a ponderilor P(n,n) a cărei elemente se definesc astfel:
p(i,j) = 0 dacă i=j
p(i,j) = c(i,j) în cazul în care (i,j) este o muchie din U unde c(i,j) este costul muchiei (i,j)
P(i,j) = $latex \infty$ în restul cazurilor

Utilizarea grafurilor ponderate este des întâlnită în practică. Cel mai sugestiv exemplu este cel al unei reţele de oraşe, nodurile grafului reprezentând oraşele, muchiile reprezentând legăturile (şoselele) dintre oraşe iar costul lor este dat de distanţa dintre oraşe.

Să se scrie un program C care verifică dacă un graf este conex şi să se afişeze toate componentele sale conexe.


#include "stdio.h"
#include "conio.h"
int n,m,a[20][20],viz[20],nrc=0;
void viziteaza(int nod)
{
  int i;
  viz[nod]=nrc;
  for(i=1;i <= n;i++)     if(a[nod][i] == i && viz[i] == 0)       viziteaza(i); } void main() {   int nod,i,j,x,y;   printf("Introdu numărul de noduri:");   scanf("%d",&n);   printf("Introdu numărul de muchii:");   scanf("%d",&m);   for(i=1;i <= n;i++)     for(j=1;j <= n;j++)       a[i][j]=0;   printf("Introdu muchiile :\n");   for(i=1;i <= m;i++)   {     printf("De la nodul: ");     scanf("%d",&x);     printf("la nodul: ");     scanf("%d",&y);     a[x][y]=a[y][x]=1;   }   for(nod=1;nod <= n;nod++)     if(viz[nod] == 0)     {       nrc++;       viziteaza(nod);     }   if(nrc == 1)     printf("Graful este conex!\n");   else     printf("Graful nu este conex!\n");   printf("Componentele conexe sunt:\n");   for(i=1;i <= nrc;i++)   {     printf("Componenta %d:",i);       for(j=1;j <= n;j++)         if(viz[j] == i)           printf("%d ",j);     putchar("\n");   }   getch(); }

Grafuri neorientate – Drumuri intr-un graf

Matricea de adiacenţă A(n,n) a unui graf G=(X,U) evidenţiază drumurile de lungime 1 între oricare 2 noduri ale grafului.

Pentru a găsi drumurile de lungime 2 între 2 noduri ale unui graf se procedează astfel. Se consideră două noduri $latex x_{i}$ şi $latex x_{j} \in X$. Existenţa unui drum de lungime 2 între ele presupune existenţa unui nod $latex x_{k} \in X$, cu proprietatea că există atât arcul $latex \left ( x_{i},x_{k} \right )$ cât şi arcul $latex \left ( x_{i},x_{k} \right )$. Pentru a vedea dacă acest arc există, se poate lua pe rând fiecare nod al grafului şi verificăm dacă există sau nu ambele arce $latex \left (\left ( x_{i},x_{k} \right ) si \left ( x_{i},x_{k} \right ) \right )$. Aceasta este echivalent cu a verifica dacă în matricea de adiacenţă există vreun indice k astfel încât elementul k al liniei i şi elementul k al coloanei j să fie ambele egale cu 1. Acest lucru este echivalent cu a verifica dacă elementul de pe poziţia (i,j) din $latex A^{2}$ este diferit de 0. Numărul de drumuri de lungime 2 dintre $latex x_{i}$ şi $latex x_{j}$ este dat de valoarea elementului $latex A^{2} \left (i,j \right )$.

Generalizând, numărul de drumuri de lungime k dintre $latex x_{i}$ şi $latex x_{j}$ este dat de valoarea elementului $latex A^{2} \left (i,j \right )$.

Dacă între nodurile $latex x_{i}$ şi $latex x_{j}$ există un drum de lungime >= n atunci el va conţine un număr de noduri mai mare sau egal nu n+1 şi, cum în graf sunt doar n vârfuri, este clar că cel puţin unul, să zicem $latex x_{k}$, va apărea de două ori. Vom avea în acest caz un drum de la $latex x_{i}$ până la prima apariţie a lui $latex x_{k}$, şi un drum de la ultima apariţie a lui $latex x_{k}$ la $latex x_{j}$.Eliminând toate nodurile dintre prima apariţie a lui $latex x_{k}$, şi ultima apariţie a sa vom obţine un drum de la $latex x_{i}$ la $latex x_{j}$, în care $latex x_{k}$ apare o singură dată. Aplicând acest procedeu pentru toate nodurile care apar de mai multe ori pe drum, vom obţine un drum de la $latex x_{i}$ la $latex x_{j}$, în care fiecare nod apare o singură dată (deci un drum elementar), care are evident cel mult n-1 arce. În concluzie, dacă există vreun drum de la $latex x_{i}$ la $latex x_{j}$ atunci există şi un drum elementar şi, deci, va exista o putere a lui A, între $latex A^{1}$ şi $latex A^{n-1}$, în care poziţia (i,j) este diferită de 0. Pentru deciderea existenţei unui drum între oricare două noduri este suficientă, deci, calcularea doar a primelor n-1 puteri ale lui A.

Grafuri neorientate – parcurgerea in adancime

Implementarea parcurgerii în adâncime pentru un graf neorientat


#include
#include
int a[20][20],n,i,j;
void parc_adancime()
{
  int s[40],varf,k,nod,urm[20],viz[20],in;
  printf("Introduceti nodul iniţial de pornire= ");
  scanf("%d",&in);
  for (nod=1;nod <= n;nod++)   {     urm[nod]=0;     viz[nod]=0;   }   varf=1;   //şirul s va păstra ordinea de traversare în adâncime;   //introducem nodul de start în acest şir   s[varf]=in;   //marcăm nodul de pornire ca vizitat   viz[in]=1;   //afişăm nodul de start ca prim nod în traversarea în adâncime   printf("%d ",in);   while (varf >= 1)
  {
    //nod va fi nodul căruia îi mai căutăm succesori
    nod=s[varf];
    //k va conţine numărul nodului de unde reîncepem să
    // căutam succesori pentru nodul nod
    k=urm[nod]+1;
    while ((k <= n) && ((a[nod][k] == 0) || ((a[nod][k]==1)&&(viz[k]==1))))     {       k++;     urm[nod]=k;     }     if (k == n+1)       vârf--;     else     {       varf++;       s[varf]=k;       viz[k]=1;       printf("%d", s[varf]);     }   }   putchar("\n"); } void main() {   int m,i,j,x,y;   printf("Introduceti numărul de noduri n=");   scanf("%d",&n);   printf("Introduceti numărul de muchii m=");   scanf("%d",&m);   for(i=1;i <= n;i++)     for(j=1;j <= n;j++)       a[i][j]=0;   for(i=1;i <= m;i++)   {     printf("De la nodul:");     scanf("%d",&x);     printf("La nodul:");     scanf("%d",&y);     a[x][y]=a[y][x]=1;   }   parc_adancime();   getch(); }

Grafuri neorientate – parcurgerea in latime

Implementarea parcurgerii în lăţime pentru un graf neorientat


#include "stdio.h"
#include "conio.h"
int a[20][20],n;
void parc_latime()
{
  int c[20],p,u,v,viz[20],im,nod;
  printf("Dati nodul de pornire pentru parcurgere: ");
  scanf("5d",&in);
  for(nod=1;nod < = n; nod++)     viz[nod]=0;   p=1;u=1;   //traversarea începe cu nodul in; şirul c va păstra ordinea de traversare   c[1]=in;   //marcăm nodul in ca vizitat   viz[in]=1;   while(p <= u)   {     //vom căuta vecinii nodului v     v=c[p];     for(nod=1;nod <= n;nod++)       //dacă există muchie între nodul nod şi nodul v şi       //nodul nod nu a fost vizitat       if((a[v][nod]==1)&&(viz[nod]==0))       {         //incrementăm indicele şirului ce conţine traversarea         u++;         //punem nodul în şirul ce conţine traversarea         c[u]=nod;         //marcăm nodul ca vizitat         viz[nod]=1;       }       //vom căuta vecinii următorului nod din şirul ce conţine traversarea       p++;   }   for (ind=1;ind <= n;ind++)     printf("%d ",c[ind]);   putchar("\n"); } Continue reading