Structures linéaires - dil.univ-mrs.frgcolas/algo-licence/slides/structlin.pdf · Listes chainées. Déclaration du type listeen C (version 1). typedef struct maillon *Liste; struct

Structures linéaires

Stéphane Grandcolas

[email protected]

Structures linéaires – Stéphane Grandcolas – p. 1/51

Structures linéaires.

Pour représenter une collection d’objets, une famille, unesuite, un ensemble,. . .

Caractéristique : une fonction Successeur

tableaux : éléments contigus, le successeur est l’élémentsuivant en mémoire,

listes chainées : lien explicite vers le successeur (sonadresse).


Tableaux.

Déclaration :

int T[100];

int n;

Accès indexé :

T[i] est le (i + 1)ième élément de la suite.

les éléments de la suite sont T[0],T[1],...,T[n-1]

n éléments

T[1] T[2] T[n−2]T[n−1]T[0]


Tableaux.

Déclaration avec définition du type

#define TAILLE_MAX 1000

typedef int type_valeur;

typedef type_valeur tableau [TAILLE_MAX];

tableau ma_suite;

int taille;


Insertion dans un tableau.

v i +1 v i +2 vn

n −1

v1 v2 vn

n −1

n−i recopies

x

x

Insertion à une position donnée

v

Insertion après les autres éléments

i


Listes chainées.

Des maillons liés entres eux par un chaînage

VVV 1

tNULL2 3V 4

Chaque maillon contient l’adresse de son successeur

Habituellement on utilise des pointeurs.


Rappels pointeurs.

Un pointeur est une variable dont la valeur est une adresse

int v;

int * p; / * variable de type pointeur sur un int * /

...

v = 12; / * v vaut 12 * /

p = &v; / * la valeur de p est l’adresse où est

stockée la valeur de la variable v * /

/ * maintenant * p vaut 12 * /


Rappels pointeurs.

On peut aussi allouer de l’espace mémoire et faire pointer psur cet espace.

int * p;

p = malloc(sizeof(int)); / * allocation de l’espace pour

une valeur de type int. * /

assert (p != NULL); / * stoppe le programme

si l’allocation échoue. * /

* p = 12; / * écrit la valeur 12 à l’adresse * p * /


Listes chainées.

Déclaration du type liste en C (version 1).

typedef struct maillon * Liste;

struct maillon

{

type_valeur val;

Liste suiv;

};

déclaration d’une variable représentant une liste :

Liste ma_liste = NULL;


Listes chainées.

Déclaration du type liste en C (version 2).

typedef struct maillon Maillon;

struct maillon

{

type_valeur val;

Maillon * suiv;

};

déclaration d’une variable représentant une liste :

Maillon * ma_liste = NULL;


Fonction de création d’un nouveau maillon.

Liste nouveau_maillon (type_valeur val, Liste suiv)

{

Liste p;

p = malloc (sizeof(struct maillon));

assert(p != NULL);

p->val = val; / * équivalent à ( * p).val = val * /

p->suiv = suiv; / * équivalent à ( * p).suiv = suiv * /

return p;

}

Le nouveau maillon se retrouve en tête de la liste résultat.


Listes chainées.

L’allocation de chaque maillon séparément conduit à despositions en mémoire sans lien les unes avec les autres

3V NULL4VV 2

tete de liste

V 1

Le lien vers le successeur est explicite.


Insertion dans une liste.

x

i+2i+1ii−1 VVVV

prec p

A partir de l’adresse du maillon précédent prec .

Avec création d’un nouveau maillon :

prec->suiv = nouveau_maillon (x, prec->suiv) ;


Suppression dans une liste.

i−2 i+1VV iV

prec p

V i−1

A partir de l’adresse du maillon précédent prec .

prec->suiv = p->suiv ;


Piles et files.

structures de données (linéaires)

caractérisées par leur comportement (insertion/extraction)

Piles

dernier entré, premier sorti

exemple : pile d’assiettes

Files

premier entré, premier sorti

exemple : file d’attente


Structures linéaires : piles.

éléments de la pile

v6

v5

v3

v2

v1

v4

top

top : pointeur de sommet de pile.


Structures linéaires : piles.

Tableaux Listes

déclarations OBJET Pile[SIZE] ; LISTE PileL ;

OBJET *Top ;

initialisation Top = Pile ; PileL = NULL ;

pile vide ? (Top == Pile) (PileL == NULL)

empiler *Top++ = e ; PileL = Creer -Maillon(e,PileL) ;

dépiler Top = Top-1 ; p = PileL ;

e = *Top ; PileL = p–>suiv ;

(e = p–>val ; free(p) ;)


Structures linéaires : files.

fin

v1 v2 v3 v4 v5 v6 v7 v8 v9 v10

debut

debut : pointeur de début.

fin : pointeur de fin.


Structures linéaires : files.

Tableaux Listes

déclaration OBJET T[SIZE] ; LISTE debL, finL ;

int deb, fin ;

initialisation deb = fin = 0 ; debL = NULL ;

file vide ? (deb == fin) (debL == NULL)

enfiler T[fin] = e ; si (debL != NULL)

fin = (fin+1)%SIZE ; finL– >suiv=CreerMaillon(e,NULL) ;

si (fin+1)%SIZE != deb finL = finL– >suiv ;

sinon

debL = finL = CreerMaillon(e,NULL) ;

défiler e = T[deb] ; p = debL ;

deb = (deb+1)%SIZE ; debL = debL– >suiv ;

(e = p–>val ; free(p) ;)Structures linéaires – Stéphane Grandcolas – p. 19/51

Comparatif tableaux/listes chainées.

Tableaux Listes

Avantages accès direct au ieme élément pas de limitation de taille

simple et rapide espace utilisé proportionnelau nombre d’éléments

Inconvénients taille maximale fixée sur-encombrement pour lelien vers le suivant

obligation de recopie pour lestableaux triés

lourd et couteux


Comparatif tableaux/listes chainées.

Opération Tableau Tableau trié liste liste ordonnée

accès au ieme élément O(1) O(1) O(n) O(n)

insertion à une place donnée O(n) O(n) O(1) O(1)

recherche O(n) O(log2 n) O(n) O(n)

ajout d’un élément O(1) O(n) O(1) O(n)


Allocation dynamique des tableaux en C.

Définition (exemple avec un tableau d’entiers)

typedef int * TABINT ;

Déclarations

TABINT T ;int n ;

Allocation

T = malloc (size * sizeof(int)) ;assert( T != NULL ) ;


Allocation dynamique de matrices en C.

Définition (exemple avec une matrice d’entiers)

typedef int ** MATINT ;

Déclarations

TABINT M ;int nc, nl ;

Allocation

M = malloc (nl * sizeof(int *)) ;assert( M != NULL ) ;for (i = 0 ; i < nl ; i ++){

M[i] = malloc (nc * sizeof(int)) ;assert( M[i] != NULL ) ;

}


Structures linéaires : listes chainées spéciales.

⊲ maillon bidon : élimine le traitement spécifique du premier élément,

⊲ chainage double : simplifie la suppression,

⊲ listes circulaires : élimine le traitement spécifique du dernier élément.

liste

v1 v2 v3bidon


Structures linéaires : listes chainées spéciales.

⊲ maillon bidon : élimine le traitement spécifique du premier élément,

⊲ chainage double : simplifie la suppression,

⊲ listes circulaires : élimine le traitement spécifique du dernier élément.

liste suppression de p

v1 v2 v3bidon

suppression du maillon p :

p–>prec–>suiv = p–>suiv ;p–>suiv–>prec = p–>prec ;


Piles exemple : dérécursivation du tri rapide.

Function tri-rapide(T, g, d)

begin

if g < d thenm:= partition(T, g, d) ;tri-rapide(T, g, m-1) ;tri-rapide(T, m+1, d) ;

end

Deux appels récursifs.


Tri rapide.

11

13

1 5

3 6

7

9

14−13

10−13

0−13

10−12

12−1210−10

3−8

0−8

0−1

0−0 2−1 3−4 6−8

3−2 4−4 6−5 7−8

7−6 8−8

2

Exemple d’exécution de la fonction tri-rapide


Piles exemple : dérécursivation du tri rapide.


begin

if g < d thenm:= partition(T, g, d) ;tri-rapide(T, g, m-1) ;tri-rapide(T, m+1, d) ;

end

Aucun traitement n’est effectué après le deuxième appel récursif.


Tri rapide.


begin

while g < d dom:= partition(T, g, d) ;tri-rapide(T, g, m-1) ;g := m+1;

end

Elimination du deuxième appel récursif avec une boucle.


Tri rapide : version itérative.


beginVIDER(P) ;EMPILER(<g,d>, P) ;while not VIDE(P) do

<g,d> := DEPILER(P) ;if g < d then

m:= partition(T, g, d) ;EMPILER(<m+1,d>, P) ;EMPILER(<g,m-1>, P) ;

end

Version itérative avec une pile (la pile contient les bornes <g,d> ).


Documents

Structures linéaires - dil.univ-mrs.frgcolas/algo-licence/slides/structlin.pdf · Listes chainées. Déclaration du type listeen C (version 1). typedef struct maillon *Liste; struct