Structuri de date – Stiva (LIFO – Last In First Out)

O stivă (în engleză stack) este o structură de tip LIFO (Last In First Out = ultimul intrat primul ieşit) şi este un caz particular al listei liniare în care toate inserările (depunerile -în engleză push) şi ştergerile (sau extragerile -în engleză pop) (în general orice acces) sunt făcute la unul din capetele listei, numit vârful stivei. Acest nod poate fi citit, poate fi şters sau în faţa lui se poate insera un nou nod care devine cap de stivă.

Implementarea unei structuri de date de tip stivă utilizând un tablou unidimensional se poate face astfel:

#include "stdio.h"
#include "stdlib.h"
#define STCKSIZE 50
//prototipul funcţiei de depunere în stivă
void push(int i);
//prototipul funcţiei de extragere din stivă
int pop(void);
//variabile globale; în tabloul stack simulăm stiva
int *pi, *tos, stack[STCKSIZE];
Continue reading

Structuri de date – Lista liniara simplu inlantuita

O listă liniară (numită şi listă înlănţuită -”Linked List”) este o colecţie de n>=o elemente x[1], … x[n] toate de un tip oarecare, numite noduri între care există o relaţie de ordine determinată de poziţia lor relativă. Ea este deci o mulţime eşalonată de elemente de acelaşi tip având un număr arbitrar de elemente. Numărul n al nodurilor se numeşte lungimea listei. Dacă n=o, lista este vidă. Dacă n>=i, x[1] este primul nod iar x[n] este ultimul nod. Pentru 1Continue reading

Constructiile de baza ale limbajului C – Operatori

Un operator este un simbol care indică compilatorului necesitatea execuţiei unei operaţii matematice sau logice.

Operatori aritmetici

Operator Semnificație Exemplu
++ Incrementare b++ (creste valoarea lui b cu 1)
* Înmulțire a*b
/ Împărțire a/b
% Restul impărțirii întregi a%b (152%100 = 52)
Scădere a-b
+ Adunare a+b

Operatorii de incrementare/decrementare pot să apară în formă prefixată sau postfixată. în forma prefixată putem avea ++v sau —v iar în forma postfixată putem avea v++ sau v—. Diferenţa dintre cele două forme apare atunci când aceşti doi operatori apar într-o expresie de atribuire. Atunci când operatorul de incrementare/decrementare precede variabila, atunci se incrementează/decrementează variabila înainte de a o utiliza în atribuire. Invers, dacă operatorul de incrementare/decrementare urmează variabilei, atunci se incrementează/decrementează variabila după utilizarea ei în atribuire.
Continue reading

Constructiile de baza ale limbajului C – Tipuri de date

Un tip de date reprezintă mulţimea valorilor pe care le pot lua variabilele într-un limbaj de programare.

În C avem tipuri de date predefinite fundamentale (de bază) (tipurile aritmetice întregi şi reale şi tipul caracter) şi tipuri de date derivate, pornind de la tipurile fundamentale. Se consideră că în C există 5 tipuri de date de bază: caracter (char), întreg (int), în virgulă mobilă (float), în virgulă mobilă dublă precizie (double) şi tipul nedefinit (void). Dimensiunea şi domeniul de valori a acestor tipuri de date pot să varieze în funcţie de tipul procesorului şi compilatorul C utilizat. în toate implementările de C, un caracter ocupă întotdeauna un octet. Un întreg va ocupa în general doi octeţi, dar pentru a asigura portabilitatea unui program, acolo unde este nevoie de a cunoaşte spaţiul ocupat de un tip de date, se va utiliza operatorul sizeof.
Continue reading

Constructiile de bază ale limbajului C – Notiuni generale

Caracterele
La scrierea programelor C se foloseşte un subset al setului de caractere al codului ASCII. Aceste coduri sunt în intervalul [0,127] şi se împart în mai multe categorii:
• negrafice (de control); au coduri în intervalul [0,32). Aici se încadrează şi caracterul Del având codul ASCII 127
• caracterul spaţiu având codul ASCII 32
• caractere grafice în intervalul (32,127), aici intrând literele mari având codul ASCII în intervalul [65,96], literele mici [97,122], cifrele [48,57] şi caracterele speciale

Identificatorii
Un identificator este o succesiune de litere şi eventual cifre care începe cu o literă (mică, mare) sau cu caracterul de subliniere. Standardul ANSI C precizează că identificatorii pot avea orice lungime dar nu toate caracterele vor fi obligatoriu semnificative. Dacă identificatorul este implicat într-un proces de editare de legături externe, se iau în considerare cel puţin 6 caractere. în caz contrat, vor fi semnificative cel puţin 31 de caractere.
Exemplu de identificatori: x, asb9, pace_in_cosmos, _, _cifra
Nu pot fi identificatori: 9a, a+b, %w, salut!
Continue reading

Structura unui program si a unei functii in C

Limbajul C este un limbaj de programare procedural, operaţiile fiind grupate în blocuri de instrucţiuni delimitate de o pereche de acolade { }. La rândul lor, blocurile sunt grupate în una sau mai multe funcţii. O funcţie C este un modul care grupează în interiorul unei perechi de acolade un set desperaţii codificate sub forma unor instrucţiuni.

Deci conceptul de bază în C este cel de funcţie. Fiecare funcţie poate accepta parametri de intrare la apel şi poate returna o valoare la revenire. Fiecare funcţie are un nume precedat de un cuvânt cheie care desemnează tipul funcţiei (tipul valorii returnate de funcţie). Numele funcţiei este urmat de o pereche de paranteze rotunde între care se specifică tipul şi numele parametrilor funcţiei. Parantezele sunt necesare chiar dacă nu există parametri.

în limbajul C nu este permisă definirea unei funcţii în interiorul altei funcţii, lucru care este permis în limbajul Pascal. în limbajul C, toate funcţiile trebuie definite în mod independent.

Un program C se compune din una sau mai multe funcţii, dintre care una este funcţia principală. Fiecare funcţie are un nume propriu, cu excepţia funcţiei principale care se numeşte main. Orice program trebuie să aibă o funcţie main iar execuţia programului începe cu prima instrucţiune din această funcţie.
Continue reading

Gandirea algoritmica

Problema căutării
Există şi cazul care, pentru o aceeaşi problem putem prezenta două soluţii, în care una este mai rapidă ca alta. De pildă, fie un şir de numere natural oarecare, de exemplu 4,2,10,1,8,15,7. Vream să testăm dacă un număr dat (să zicem numărul 8) se află în această secvenţă sau nu.

O astfel de căutare, prin parcurgerea de a stânga la dreapta a întregii secvenţe de numere, până se găseşte numărul dorit sau se epuiează toate elementele din secvenţă, se numeşte căutarea secvenţială. Dacă avem un şir S de n elemente (notat S[i..n]), atunci căutarea secvenţială a lui x în S se descrie prin:

Căutare_secventială(x,S[1. .n]) înseamnă
Început
  Fie elemental_curent = primul_element;
  Atăt timp cât (elemental_curent <> x) si (poziţia elementului current <= poziţia ultimului element (n)) execută   Început     Dacă elemental_curent = x atunci mesaj ("găsit")     Altfel treci la următorul element   Sfârşit Sfârşit.

Continue reading