Structuri de date și algoritmi

Curs
7.3/10 (4 voturi)
Domeniu: Cibernetică
Conține 1 fișier: pdf
Pagini : 35 în total
Cuvinte : 10100
Mărime: 427.09KB (arhivat)
Cost: Gratis

Extras din document

Înainte de a elabora un algoritm, trebuie să ne gândim la modul în care reprezentăm datele. Structurile fundamentale de date cu care se poate opera sunt: fişier, tablou, listă, graf, arbore. În acest capitol ne vom ocupa de liste, arbori şi grafuri, întrucât primele două (tablou, fişier) au fost studiate anterior. O listă este o colecţie de elemente de informaţie (noduri) aranjate într-o anumită ordine. Lungimea unei liste este dată de numărul de noduri din listă. Structura listei trebuie să ne permită să determinăm eficient care este primul/ultimul nod în structură şi care este predecesorul/succesorul unui nod dat. Cea mai simplă listă este lista liniară. Un alt tip de listă este cea circulară, în care, după ultimul nod, urmează primul, deci fiecare nod are succesor şi predecesor.

Operaţiile curente care se fac în liste sunt: inserarea unui nod, ştergerea (extragerea) unui nod, concatenarea unor liste, numărarea elementelor unei liste etc. Implementarea unei liste se poate face in principal în două moduri.

Primul, constă în implementarea secvenţială, adică în locaţii succesive de memorie, conform ordinii nodurilor din listă, care conţin informaţia dorită. Avantajul acestei tehnici este accesul rapid la predecesorul/succesorul unui nod, inclusiv găsirea rapidă a primului/ultimului nod. Dezavantajele sunt inserarea/ştergerea relativ complicată a unui nod şi faptul că, în general, nu se foloseşte întreaga memorie alocată listei.

Cel de-al doilea, implementarea înlănţuită. în care fiecare nod conţine două părţi: informatia propriu-zisă şi adresa nodului următor. Alocarea memoriei fiecărui nod se poate face în mod dinamic, în timpul rulării programului. Accesul la un nod necesită parcurgerea tuturor predecesorilor săi, ceea ce poate lua ceva mai mult timp. Inserarea/ştergerea unui nod este în schimb foarte rapidă. Se poate construi o listă dublu înlănţuită, care conţine două adrese în loc de una, astfel încat un nod să conţină pe lânăa adresa nodului următor şi adresa nodului anterior.

Listele implementate înlănţuit pot fi reprezentate cel mai simplu prin tablouri. În acest caz, adresele sunt de fapt indici de tablou. O alternativă este să folosim tablouri paralele: să memoram informaţiile fiecărui nod într-un tablou INFO[n], iar adresele (indicii) nodurilor succesoare într-un tablou SUCC[n]. Indicele primului nod din listă (fie că este de tip coadă sau stivă) va fi păstrat într-o variabilă. Acest mod de reprezentare este simplu dar apare o problemă, şi anume cea a gestionării locaţiilor libere. O soluţie este să reprezentăm locaţiile libere tot sub forma unei liste înlănţuite. Atunci, ştergerea unui nod din listă implică inserarea sa într-o listă cu locaţii libere, iar inserarea unui nod în listă implică ştergerea sa din lista cu locaţii libere. Este interesant de remarcat că, pentru implementarea listei de locaţii libere, putem folosi aceleaşi tablouri, dar avem nevoie de o alta variabilă, care să conţină indicele primei locaţii libere din VAL şi LINK, în timp ce variabila cealaltă, iniţială, va conţine adresa primei locaţii din lista propriu-zisă.

Vom exemplifica în continuare două tipuri de liste foarte des folosite, şi anume coada şi stiva, considerând implementarea ce utilizează alocarea statică (tablouri).

O stivă (stack) este o listă liniară cu proprietatea că operaţiile de inserare/extragere a nodurilor se fac în/din coada listei, motiv pentru care stivele se mai numesc şi liste LIFO (Last In First Out). Cel mai natural mod de reprezentare pentru o stivă este implementarea secvenţială într-un tablou S[n], unde n este numarul maxim de noduri. Primul nod va fi memorat în S[0], al doilea în S[1], iar ultimul în S[n-1]; sp este o variabila care conţine adresa (indicele) ultimului nod inserat. Iniţial, cand stiva este vidă, avem sp = -1 (sau poate fi 0). Iată funcţiile de inserare, extragere a unui nod, precum şi cele de afişare şi de semnalare a situaţiilor extreme (stivă goală sau stivă plină).

/* stivatab.c - operatii cu o stiva realizata static intr-un tablou;

operatii disponibile: inserare, extragere, afisare cap stiva,

afisare stiva, afisare pointer la varful stivei */

6

#include <stdio.h>

#include <conio.h>

#define MaxS 10

typedef int ElTip; // ElTip - definire tip element din stiva

typedef struct {

ElTip elem [MaxS];// spatiu pentru elem. stivei

int sp;

/* index/ referinta la varful stivei (stack pointer) */

} TStiva, *AStiva;

void eroare (char *meserr){

printf("%sn", meserr);

}

void InitStiva (AStiva rs){

/* initializare stiva, sp nu refera un element (stiva goala) */

rs->sp=-1;

}

int StivaGoala (AStiva rs){

return (rs->sp == -1);

}

int StivaPlina (AStiva rs){

/* stiva este plina, index=MaxS-1, indice maxim,

nu se mai pot introduce elemente in stiva */

return (rs->sp == MaxS-1);

}

void Push (AStiva rs, ElTip el){

/* introduce element in stiva, daca nu este plina */

if (StivaPlina (rs))

eroare ("Stiva Plina !!!");

else {rs->sp=rs->sp+1;

rs->elem[rs->sp]=el;

}

}

ElTip Pop (AStiva rs){

/* extrage element din stiva, daca nu este goala */

ElTip e;

if (StivaGoala (rs))

{eroare ("Stiva Goala !!!");

return 0;

}

else

{e=rs->elem[rs->sp];

rs->sp=rs->sp-1;

return e;

}

}

ElTip CapStiva (AStiva rs){

if (StivaGoala (rs))

{eroare ("Stiva Goala !!!");

return 0;

Preview document

Structuri de date și algoritmi - Pagina 1
Structuri de date și algoritmi - Pagina 2
Structuri de date și algoritmi - Pagina 3
Structuri de date și algoritmi - Pagina 4
Structuri de date și algoritmi - Pagina 5
Structuri de date și algoritmi - Pagina 6
Structuri de date și algoritmi - Pagina 7
Structuri de date și algoritmi - Pagina 8
Structuri de date și algoritmi - Pagina 9
Structuri de date și algoritmi - Pagina 10
Structuri de date și algoritmi - Pagina 11
Structuri de date și algoritmi - Pagina 12
Structuri de date și algoritmi - Pagina 13
Structuri de date și algoritmi - Pagina 14
Structuri de date și algoritmi - Pagina 15
Structuri de date și algoritmi - Pagina 16
Structuri de date și algoritmi - Pagina 17
Structuri de date și algoritmi - Pagina 18
Structuri de date și algoritmi - Pagina 19
Structuri de date și algoritmi - Pagina 20
Structuri de date și algoritmi - Pagina 21
Structuri de date și algoritmi - Pagina 22
Structuri de date și algoritmi - Pagina 23
Structuri de date și algoritmi - Pagina 24
Structuri de date și algoritmi - Pagina 25
Structuri de date și algoritmi - Pagina 26
Structuri de date și algoritmi - Pagina 27
Structuri de date și algoritmi - Pagina 28
Structuri de date și algoritmi - Pagina 29
Structuri de date și algoritmi - Pagina 30
Structuri de date și algoritmi - Pagina 31
Structuri de date și algoritmi - Pagina 32
Structuri de date și algoritmi - Pagina 33
Structuri de date și algoritmi - Pagina 34
Structuri de date și algoritmi - Pagina 35

Conținut arhivă zip

  • Structuri de date si algoritmi.pdf

Alții au mai descărcat și

Testarea alpha

Ce este testarea alpha? Testarea Alpha este una dintre cele mai comune strategii de testare software utilizate în dezvoltarea de software. Este...

Programare evolutiva si algoritmi genetici

Introducere Ideea de a aplica principiile darwiniste ale evolutiei in rezolvarea automata a problemelor (Problem Solving - PS) dateaza din anii...

Analiza informational - decizionala - Departamentul de web developer

. Cunoașterea generală a mecanismului economic Studiul de caz reprezinta o analiza informational - decizionala a sistemului reprezentat prin...

GVMD

DEPOZITE DE DATE Un depozit de date furnizează o sursă integrată şi centralizată de date, separată de sistemul tranzacţional, care conţine datele...

Teoria recursiilor

Problema 1. Numere Fibonacci. Să se alcatuiască un Program în C++ pentru a determina numerele Fibonacci atit recursiv cît și nerecursiv. #include...

Ai nevoie de altceva?