| CATEGORII DOCUMENTE |
Tablouri. Tehnici de sortare.
Tablourile in limbajul C sunt variabile cu indici. Pot fi de doua categorii, tablouri unidimensionale (vectori) sau multidimensionale. La nivel abstract, un tablou unidimensional se poate defini ca o lista ordonata de n valori de acelasi tip: x1,x2, . ,xn. Fiecare pozitie i din cadrul tabloului contine elementul xi, respectiv o valoare de tipul specificat.
Declararea unui tablou unidimensional in limbajul C se face astfel:
<tip> NumeTablou [NumarElemente];
Unde <tip> este tipul de date al elementelor tabloului, NumarElemente este un numar natural sau o constanta cu valoare intreaga pozitiva prin care se precizeaza numarul elementelor din tablou, NumeTablou este un identificator prin care este denumit vectorul.
Referirea unui element al tabloului se foloseste numele tabloului si indicele corespunzator. Spre exemplu: int x[100];
Pentru a referi elementul de pe pozitia i vom scrie x[i-1], dat fiind faptul ca primul element al sirului este x[0].
Tablourilor li se asociaza locatii de memorie consecutive, de aceeasi lungime in care sunt stocate valorile fiecarui element.
Observatie: numele tabloului (spre ex. x) este o variabila a carei valoare este adresa de memorie a primului element din sir (pointer).
Declararea tablourilor n-dimensionale:
<tip> NumeTablou [N1] [N2] .[Nn];
Unde N1, N2 . Nn reprezinta numarul de elemente pe fiecare dimensiune.
Referirea unui element al tabloului multidimensional se face prin identificatorul tabloului (numele) si specificarea pozitiei pe fiecare dimensiune:
NumeTablou [i1] [i2] .[in].
Exemplu:
int A[20] [30];
//declararea unei matrice (tablou bi-dimensional) de 20 linii si 30 coloane.
Primul element al tabloului bidimensional declarat mai sus este A[0][0], iar numele tabloului contine adresa primului element memorat.
Observatie: Numele unui tablou in C este de fapt un pointer, avind ca valoare adresa primului sau element. La transmiterea vectorilor ca parametrii ai unor functii se va tine cont de acest aspect.
Exemplu:
int T[100]; //tablou de 100 intregi
Numele tabloului, T - reprezinta adresa primului element al sau, respectiv, adresa lui T[0].
Tablourile sunt structuri de date:
compuse: sunt formate din mai multe elemente (de acelasi fel)
ordonate: exista o relatie de ordine data de pozitia elementelor in tablou
omogene: toate elementele unui tablou au acelasi tip
Tablourile unidimensionale vor fi denumite in continuare vectori.
Pointeri si tablouri. Operatii cu pointeri
Intre tablouri si variabilele pointer exista o stransa legatura: numele unui tablou este un pointer, fiind de fapt adresa primului element al tabloului respectiv:
Exemplu:
int tab[100];
//tab - este adresa elementului t[0]
Observatie: Deoarece memoria alocata unui tablou este o zona contigua, respectiv, elementele tabloului sunt grupate, cunoscand adresa primului element, printr-o operatie elementara se poate accesa oricare alt element al tabloului.
Operatii cu pointeri:
Asupra pointerilor se pot efectua urmatoarele operatii:
incrementare/decrementare
adunarea/scadere cu un intreg
diferenta a doi pointeri
Fie declaratia urmatoare:
<tip> *p; //p este un pointer la tipul <tip>
Efectul operatiilor de incrementare/decrementare este urmatorul:
p++ si ++p echivalent cu: p=p+dim
p-- si --p echivalent cu: p=p-dim
unde: dim reprezinta dimensiunea exprimata in octeti a unei variabile de tipul <tip>
Exemplu
int *p;
p++;
//p se mareste cu 2, deoarece o variabila de tipul int se memoreaza pe 2 octeti
Adunarea si scaderea unui intreg
Fie: <tip> *p;
int k;
Expresiile: p+k, p-k sunt expresii valide in limbajul C, avand semnificatiile urmatoare:
p+k - reprezinta o adresa de memorie; valoarea p+k este egala cu valoarea lui p marita cu k*dim , unde dim- dimensiunea exprimata in octeti a tipului <tip>
p-k - are valoarea p micsorata cu k*dim , unde dim- dimensiunea exprimata in octeti a tipului <tip>
Accesarea elementelor unui tablou poate fi facuta si prin operatii cu variabile pointer:
Exemplu
int tab[100]; //tablou de 100 intregi
int i;
(tab) - adresa primului element tab[0]
(tab+1) - adresa celui de-al doilea element tab[1]
(tab+i) - reprezinta adresa celui de-al (i-1) -lea element al tabloului, respectiv este adresa elementului tab[i]
*(tab+i) - reprezinta valoarea elementului tab[i]
Diferenta a doi pointeri:
Doua variabile de tip pointer prin care se refera elementele aceluiasi tablou pot fi scazute. Fie tabloul tab si doi pointeri p si q care adreseaza elementele tab[i] si tab[j]. Diferenta p-q este un numar intreg k, reprezintand numarul de elemente care desparte cele doua adrese. Aceasta dimensiune se poate determina prin calculul elementar: k=(j-i).
Intre adresele p si q se afla un numar de (j-i) elemente, respectiv, (j-i)*dim octeti, unde dim - dimensiunea necesara reprezentarii unui element al tabloului.
Siruri de caractere
Operatiile cu siruri de caractere se efectueaza prin apelul unor functii de biblioteca specifice. Prototipurile functiilor care manipuleaza siruri de caractere se afla in fisierul antet string.h.
Orice sir de caractere se va pastra intr-o zona de memorie contigua. Ne reamintim ca unei variabile de tipul char ii este necesara o zona de memorie de 1 octet, pentru retinerea codului numeric corespunzator (reprezentarea interna). Un sir de caractere, declarat ca tablou unidimensional de tip char va ocupa o zona de n octeti terminata printr-un octet suplimentar cu valoarea '0' - caracterul nul, prin care s-a marcat terminarea sirului.
Ex: char sir[20];
Folosind relatia dintre tablouri si pointeri, putem utiliza in programe declaratii de forma:
char *psir;
Accesarea caracterelor din compunerea sirului va fi posibila prin variabile indexate sau prin operatii cu pointeri:
sir[0] sau *psir - codul numeric (ASCII) al primului caracter din sir
sir[1] sau *(psir) - codul numeric al celui de-al doilea caracter din sir
sir sau psir - adresa primului caracter
sir+1 sau psir+1 - adresa celui de-al doilea caracter din sir
Pentru manipularea sirurilor de caractere, biblioteca standard string.h pune la dispozitie functii speciale dedicate operatiilor specifice.
Lungime unui sir de caractere
Lungimea unui sir de caractere este definita prin numarul caracterelor care intra in compunerea sirului. Functia standard strlen este utila in determinarea lungimii unui sir de caractere:
unsigned strlen(const char *s)
Exemplu
char const *psir = "text"
unsigned l;
l= strlen(psir); // lui l i se va atribui 4
//numarul de caractere, excluzand marcatorul NULL)
Copierea unui sir de caractere
este operatia prin care un sir de caractere sursa este copiat intr-o alta zona de memorie atasata unui alt sir de caractere destinatie
functia specifica este: strcpy
char * strcpy(char *destinatie, const char *sursa
Functia are ca efect copierea tuturor caracterelor in zona de memorie referita de destinatie din zona de memorie referita de sursa. (inclusiv caracterul NULL)
Funtia strcpy returneaza la revenire adresa de inceput a zonei in care s-a copiat sirul (pointer-ul destinatie)
Exemplu: Interschimbarea a doua siruri de caractere:
void schimb(char a[20],char b[20])
Concatenarea a doua siruri de caractere
Se realizeaza prin apelul functiei strcat:
char * strcat(char *destinatie,const char *sursa
Apelul functiei are ca efect copierea sirului de la adresa sursa in zona de memorie imediat urmatoare sirului de la adresa destinatie. La revenire, functia returneaza adresa destinatie.
Compararea a doua siruri de caractere
Operatia de comparare a doua siruri presupune verificarea codurilor ASCII ale caracterelor din compunerea sirurilor. Compararea sirurilor de caractere este o operatie utila in probleme care cer ordonarea lexicografica a unor secvente de text.
char * strcmp(const char *sir1,const char *sir2
Functia strcmp returneaza:
valoare negativa, daca sir1<sir2
0, dac a sir1=sir2
valoare pozitiva, daca sir1>sir2
Exemplu: Program de generare a parolelor. Pentru un cuvant dat, parola va fi obtinuta prin scrierea de la dreapta la stanga a caracterelor de pe pozitiile impare.
#include <stdio.h>
#include <string.h>
void main()
pass[n]=NULL;
printf('parola este %s',pass);
Operatiile specifice cu vectori sunt:
parcurgerea
a. pentru accesarea si/sau modificarea elementelor (citirea si afisarea)
b. pentru numararea elementelor ce verifica o conditie
cautarea secventiala
minimul/maximul dintr-un vector
inserarea si stergerea unui element pe o pozitie data
concatenarea a doi vectori
interclasarea a doi vectori
sortarea
a. sortarea prin selectie
b. sortarea prin numarare
c. sortarea prin metoda bulelor (prin interschimbare)
Alte variante de sortare vor fi descrise in capitolele dedicate metodelor de programare (ex. sortarea rapida si sortarea prin interclasare)
1. Parcurgerea tablourilor
//Parcurgerea tablourilor -citirea si afisarea unui vector
void citire_tablou(int t[], int *n)
void afisare_tablou(int t[], int n)
int tablou[30];
int dim_tablou10;
citire_tablou(tablou, &dim_tablou);
//apelul functiei de citire tablou
afisare_tablou(tablou, dim_tablou);
//apelul functiei de afisare tablou
Legatura dintre pointeri si tablouri influenteaza maniera de transmitere a tablourilor ca parametri unei functii. Oferim o alta varianta de functie care citeste un tablou unidimensional, in care se folosesc expresii cu pointeri, iar parametrul formal este declarat ca pointer:
void citire_tablou_II(int *pt, int *n)
//Parcurgerea tablourilor -numararea elementelor ce verifica o conditie data
int numara_pozitive(int t[], int n)
2. Cautarea secventiala
- operatia de cautare presupune parcurgerea element cu element a vectorului, in ordinea data de indecsi
//Cautarea : determinarea pozitiei pe care se afla valoarea cautata
int cauta_cheie(int t[], int n, int cheie)
3. Determinarea minimului/maximului dintr-un vector
Principiul este urmatorul:
se presupune ca elementul de pe prima pozitie din vector este minimul
se parcurge vectorul element cu element (de la a 2-a pozitie, pana la ultima), comparandu-se minimul presupus cu valoarea curenta din vector
daca elementul curent este mai mic decat minimul presupus, se va actualiza valoarea minimului, in caz contrar se trece la urmatorul element fara a altera minimul presupus
Pentru determinarea maximului procedeul este similar, modificandu-se doar operatorul logic utilizat in conditia de actualizare a maximului presupus.
Algoritmul descris in pseudocod pentru determinarea minimului dintr-un vector x1,x2,,xn este urmatorul:
Algoritm Minim este
Citeste: x1,x2,,xn, n //vectorul x de n elemente; dimensiunea n
Fie min=x1
Pentru i de la 2 la n //se parcurge vectorul
Daca xi<min atunci
min=xi
SfDaca
SfPentru
Tipareste min
SfAlgoritm
// codul sursa C corespunzator algoritmului descris
//se citesc in prealabil dimensiunea si elementele vectorului x
int x[100];
int i, min, n;
citire_tablou(x,&n);
min=t[0];
for(i=0;i<n;i++)
if (x[i]<min0)
min=x[i];
printf("Minimul este:%d", min);
4. Inserarea/stergerea unui element
Inserarea unui element nou pe o pozitie k in vector presupune efectuarea urmatoarelor operatii:
marirea dimensiunii vectorului cu 1.
mutarea cu o pozitie la dreapta a tuturor elementelor situate pe pozitiile mai mari decat k
inserarea propriu-zisa a noului element pe pozitia k.
Stergerea elementului de pe pozitia k presupune operatiile urmatoare:
mutarea la stanga cu o pozitie a tuturor elementelor situate la dreapta pozitiei k
micsorarea dimensiunii vectorului cu 1
5. Concatenarea a doi vectori
Rezultatul concatenarii a doi vectori de dimensiune n1, respectiv n2, este un al treilea vector de dimensiune n1+n2, format prin copierea elementelor primului vector urmata de copierea elementelor celui de-al doilea vector. Concatenarea este o operatie simpla fapt pentru care vor lasa ca exercitiu definirea unei functii C care realizeaza aceasta operatie.
Observatie: operatia de concatenarea difera semnificativ de operatia de interclasare.
6. Interclasarea a doi vectori
Interclasarea este procedeul prin care, pornind de la doua secvente ordonate de elemente se formeaza o secventa care contine toate elementele primelor doua si este ordonata.
Operatia de interclasare se aplica asupra a doi vectori sortati rezultand un al treilea vector cu proprietatile:
contine toate elementele vectorilor initiali
este ordonat
Fie X si Y doi vectori ordonati crescator, de dimensiune n, respectiv m:
x[1],x[2],,x[n]
y[1],y[2],,y[m]
Se doreste obtinerea vectorului ordonat z: z[1],z[2],,z[p], format din toate elementele celor doi vectori de intrare.
Principiul este de a completa element cu element vectorul rezultat Z, prin copierea elementelor vectorilor X si Y pastrand relatia de ordine. Interclasarea se realizeaza prin executarea urmatoarelor etape:
Cat timp mai exista elemente de parcurs in ambii vectori: X,Y, acestia se parcurg secvential:
a. Se compara elementele curente ale celor doi vectori X si Y, si cel mai mic dintre acestea se copiaza in vectorul Z
Daca au mai ramas elemente neparcurse in vectorul X, se vor copia in Z
Daca au mai ramas elemente neparcurse in vectorul Y, se vor copia in Z
Parcurgerea vectorilor X,Y,Z presupune utilizarea a trei variabile cursor cu semnificatia pozitiei curente in vectorul corespunzator:
Fie i - cursorul care indica pozitia curenta in vectorul X
Fie j - cursorul care indica pozitia curenta in vectorul Y
Fie k - cursorul care indica pozitia curenta in vectorul Z
Algoritmul Interclasare este:
Citeste n, x[1],x[2],,x[n]
Citeste m, y[1],y[2],,y[m]
Fie i=1,j=1 //pozitiile de start in vectorii de intrare
Fie k=1 //pozitia de start in vectorul rezultat
Cattimp(i<=n si j<=m)
Daca x[i]<y[j] atunci
z[k]=x[i]
k=k+1 //trecere la urmatoarea pozitie in vectorul Z
i=i+1//trecere la urmatoarea pozitie in vectorul X
Altfel
z[k]=y[j]
k=k+1 //trecere la urmatoarea pozitie in vectorul Z
j=j+1//trecere la urmatoarea pozitie in vectorul Y
SfDaca
SfCattimp
Daca i<n atunci //au mai ramas elemente in vectorul X
Pentru w de la i la n //se copiaza elementele ramase in X
z[k]=x[w]
k=k+1
SfPentru
SfDaca
Daca j<m atunci //au mai ramas elemente in vectorul Y
Pentru w de la j la m //se copiaza elementele ramase in Y
z[k]=y[w]
k=k+1
SfPentru
SfDaca
p=k-1 // sau p=n+m
Tipareste z[1],z[2],,z[p]
SfAlgoritm //Interclasare
TABLOURI n-DIMENSIONALE
Adesea, este necesara prelucrarea datelor structurate in tablouri multidimensionale. Un caz particular este cel al tablourilor bidimensionale, cunoscute sub denumirea de matrice. Structura de matrice este reprezentata in matematica prin:
Toate elementele unei matrice sunt de acelasi tip si dimensiunile matricei se refera la numarul de linii (m) si de coloane (n). In limbajul C, declararea unei structuri de tablou bi-dimensional se face prin constructia:
tipElement NumeTablou [linii] [coloane], unde:
tipElement este tipul de dat[ al elementelor
linii si coloane - specifica dimensiunea memoriei alocate tabloului identificat prin NumeTablou
Un tablou bidimensional este reprezentat intr-o succesiune de locatii de memorie referite prin acelasi identificator (NumeTablou). Fiecare element al tabloului este referit prin pozitia sa in cadrul sirului. Pozitia este precizata prin doua numere pozitive (indecsi), care reprezinta cele doua dimensiuni (linie si coloana).
Prin declaratia tipElement NumeTablou [linii] [coloane] s-au alocat in memorie un numar de octeti egal cu linii*coloane*sizeof(tipElement), necesari memorarii elementelor acestei structuri de date. Zona de memorie rezervata tabloului este contigua.
Numele tabloului este adresa primului element memorat, accesat prin constructia: NumeTablou[0][0], astfel incit in prelucrarile tablourilor, in mod uzual se considera numerotarea liniilor si a coloanelor incepand de la 0.
Accesarea elementului de pe linia i, coloana j se face prin constructia NumeTablou[i][j]. Ne reamintim ca sintaxa NumeTablou[i] este echivalenta unei operatii cu pointeri exprimata prin expresia: NumeTablou+i. Intr-o maniera similara, expresia NumeTablou[i][j] poate fi exprimata printr-o operatie cu pointeri: NumeTablou+i+j.
Citirea elementelor unei matrice este posibila prin citirea pe rind a fiecarui element din compunerea sa. In acest sens se vor parcurge multimile indecsilor de linie si coloana prin doua instructiuni repetitive (ciclice) imbricate. Codul C de mai jos are ca efect citirea unei matrice de numere intregi:
int mat[10][10];
int i,j;
printf("nIntroduceti nr. de linii ");scanf("%d",&m);
printf("nIntroduceti nr. de coloane ");scanf("%d",&n);
for(i=0; i<m; i++)
for(j=0; j<n; j++)
Afisarea valorilor unei matrici (in formatul uzual) este descrisa prin secventa urmatoare :
printf("n Matricea este: ");
for(i=0; i<m; i++)
In programele de prelucrare a matricelor este utila implementarea functiilor corespunzatoare operatiilor de intrare -iesire cu aceste structuri: citirea unei matrice, afisarea unei matrice. Functiile respective vor avea ca parametri atat dimensiunile tabloului (numarul de linii si coloane) dar si adresa primului element (numele tabloului). Parcurgerea in cadrul functiilor a tablourilor cu ajutorul indecsilor ascunde in fapt un calcul de adrese: cunoasterea adresei de inceput a zonei de memorie alocate tabloului permite accesarea tuturor elementelor sale.
In privinta parametrilor formali, antetul functiei de citire poate fi exprimat:
void citire (tipElement NumeTablou[Mmaxim][Nmaxim], int linii, int coloane)
Exemplu: Programul urmator determina suma si produsul a doua matrici:
#include <stdio.h>
#include <conio.h>
#define DimMax 10 //numarul maxim de elemente
//pe linii si coloane
void afisare_matrice(int n,int m,int a[DimMax][DimMax])
}
void citire_matrice(int *n,int *m,int a[DimMax][DimMax])
printf('n');
}
void suma(int n,int m, int a[DimMax][DimMax],
int b[DimMax][DimMax], int c[DimMax][DimMax])
void produs(int n,int m,int p, int a[DimMax][DimMax],
int b[DimMax][DimMax],int c[DimMax][DimMax])
}
void main()
ALGORITMI DE SORTARE
Sortarea reprezinta procedeul prin care o multime de elemente este aranjata dupa o relatie de ordine data.
Sortarea prin selectie
Fie x1,x2,,xn un vector de n elemente.
Principiul este acela de a considera subvectorul xi,.,xn si de a determina minimul din aceasta secventa, urmand ca minimul rezultat sa se interschimbe cu elementul xi. Procedeul se va repeta pentru oricare i=1,.,n-1.
Algoritm SortareSelectie este:
Citeste n, x1,x2,,xn
Pentru i de la 1 la n-1
//determina pozitia si valoarea minimului subvectorului xi,.,xn
pozmin=i
min=xi
Pentru j de la i+1 la n
Daca xj <min atunci
pozmin=j
min=xj
SfDaca
sfPentru
//interschimbare xi cu min
xpozmin=xi
xi=min
SfPentru
SfAlgoritm
Exemplu
/*program care citeste un vector de numere intregi,
ordoneaza elementele vectorului prin metoda sortarii prin selectie
si tipareste vectorul ordonat */
#include <stdio.h>
void citireSir(int x[],int *n)
void tiparireSir(int x[],int n)
void SSort(int x[],int n)
//interschimb cu x[i]
x[poz]=x[i];
x[i]=aux;
}
void main()
Sortarea prin insertie
Fie x1,x2,,xn un vector de n elemente
Principiul acestei tehnici este acela de a privi tabloul ca fiind impartit in doua subtablouri: x1,,xi-1 si xi,,xn. Se presupune ca primul subtablou este deja ordonat si se urmareste inserarea elementului xi in subtabloul ordonat astfel incat dupa efectuarea insertiei subtabloul rezultat sa ramana ordonat. Acest procedeu se va continua privind tabloul initial ca doua subtablouri : x1,,xi si xi+1,,xn. Cunoscand ca primul subtablou este deja ordonat (ne-am asigurat de acest lucru la operatia de inserare precedenta), se va continua cu inserarea elementului xi+1 in x1,,xi si obtinerea subtabloului ordonat x1,,xi+2. Procedura se repeta pana cand nu mai sunt elemente de inserat in subtabloul stang.
Inserarea unui element oarecare xi presupune determinarea pozitiei in care va fi depus. Aceasta se rezuma la parcurgerea subtabloului in care se va face inserarea, de la stanga la dreapta, si determinarea primul element xk care este mai mare decat xi. In acel moment k devine pozitia pe care va fi depus xi. Parcurgerea subtabloului se poate face si in sens invers, de la dreapta la stanga, insa in acest caz se va determina k - pozitia primului element xk care verifica conditia ca este mai mic decat xi.
Prima impartire a tabloului este in punctul i=2, ceea ce produce un subvector format din doar elementul x1 si subvectorul x2,,xn. Se poate observa ca primul subtablou este deja ordonat.
Algoritm SortareInsertie este:
Citeste n, x1,x2,,xn
Pentru i de la 2 la n
//inserez elementul xi in subvectorul stang
x0=xi
j=i-1
Cattimp (xj>x0)
xj+1=xj
j=j-1
SfCattimp
xj+1=x0
SfPentru
SfAlgoritm
Exemplu: Functia urmatoare realizeaza sortarea prin insertie a unui vector.
void SInsert(int x[],int n)
// k+1 reprezinta pozitia pe care se insereaza aux
x[k+1]=aux;
}
Sortarea prin interschimbare (BubbleSort )
Metoda sortarii prin interschimbare consta in parcurgerea repetata a vectorului si compararea pe rand a perechilor de elemente consecutive urmata de interschimbarea valorilor acestora in situatia in care relatia de ordine dorita nu este verificata.
La fiecare parcurgere se va presupune ca vectorul este ordonat (marcarea acestei presupuneri se face printr-un cod), insa la determinarea unei perechi de elemente consecutive care necesita interschimbare, presupunerea este anulata.
Algoritmul se va termina in conditiile in care la o parcurgere anterioara, completa a vectorului, presupunerea s-a dovedit adevarata.
Algoritm SortareInterschimbare este
//ordonare crescatoare dupa valorile elementelor
Citeste n, x1,x2,,xn
Repeta
Ordonat=Adevarat
Pentru i de la 1 la n-1
Daca xi>xi+1 atunci
Cheama Interschimbare(xi,xi+1)
Ordonat=fals
SfDaca
SfPentru
Panacand (Ordonat=Adevarat)
SfAlgoritm
Exemplu: Functia urmatoare realizeaza sortarea prin interschimbare a unui vector.
void SBubble(int x[],int n)
}
}while (cod!=0);
Probleme propuse spre rezolvare:
Se da o matrice cu numere intregi, de n linii si m coloane. Sa se determine numarul elementelor pozitive din compunerea matricei.
Se da un tablou bidimensional de numere intregi organizat in n linii si n coloane (matrice patratica). Sa se ordoneze crescator elementele de pe diagonala principala a matricei.
Fiind data o matrice A de n linii si coloane, formata din numere reale, sa se construiasca o matrice B de n linii si m+1 coloane, ale carei prime m coloane sunt copiate din matricea A si ultima coloana este formata din valorile sumelor elementelor de pe fiecare linie a matricei A.
Sa se determine inversa unei matrice.
Determinati cel mai mic numar pozitiv al unui vector de n numere intregi.
|
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 2771
Importanta: 
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved
