Cours d'Algorithmique-Programmation 2e partie (IAP2 ...
24
pages
Breton
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
24
pages
Breton
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Cours d’Algorithmique-Programmation
e2 partie (IAP2): programmation imp´erative et
structures de donn´ees simples
Compl´ements sur les tableaux + Pointeurs en C
Sandrine Blazy
er` e- 1 ann´ee
7 novembre 2007
e
S.Blazy (ENSIIE) Cours d’Algorithmique-Programmation 2 partie (IAP2):7pnovembrogramm reation2007imp´erat 1i/ve24et structures de donn´ees simples 1 Tris par s´election
Matrices
Le type pointeur sur ´el´ement
Pointeurs et arguments
argc et argv
e
S.Blazy (ENSIIE) Cours d’Algorithmique-Programmation 2 partie (IAP2):7pnovembrogramm reation2007imp´erat 2i/ve24et structures de donn´ees simples Tri par s´election
Principe
On cherche le plus petit ´el´ement du vecteur et on l’´echange avec le
premier ´el´ement puis on trie le reste.
Plus pr´ecis´ement et it´erativement, `a la i-`eme ´etape du tri d’un vecteur de
longueur n, on cherche l’indice j du plus petit ´el´ement du sous-vecteur
d’indice compris entre i et n−1 et on ´echange cet ´el´ement avec l’´el´ement
d’indice i. L’´echange n’est effectivement r´ealis´e que si ce plus petit
´el´ement n’est pas d´ej`a en i.
e
S.Blazy (ENSIIE) Cours d’Algorithmique-Programmation 2 partie (IAP2):7pnovembrogramm reation2007imp´erat 3i/ve24et structures de donn´ees simples Tri par s´election
Interfaces
/∗ Interface
indice min sous vecteur: vecteur−> int
post calcule l’indice du plus petit ´el´ement du vecteur
∗/
/∗ Interface
tri selection: vecteur−> vecteur
post trie le tableau dans l’ordre croissant
∗/
e
S.Blazy (ENSIIE) Cours ...
Voir
e2 partie (IAP2): programmation imp´erative et
structures de donn´ees simples
Compl´ements sur les tableaux + Pointeurs en C
Sandrine Blazy
er` e- 1 ann´ee
7 novembre 2007
e
S.Blazy (ENSIIE) Cours d’Algorithmique-Programmation 2 partie (IAP2):7pnovembrogramm reation2007imp´erat 1i/ve24et structures de donn´ees simples 1 Tris par s´election
Matrices
Le type pointeur sur ´el´ement
Pointeurs et arguments
argc et argv
e
S.Blazy (ENSIIE) Cours d’Algorithmique-Programmation 2 partie (IAP2):7pnovembrogramm reation2007imp´erat 2i/ve24et structures de donn´ees simples Tri par s´election
Principe
On cherche le plus petit ´el´ement du vecteur et on l’´echange avec le
premier ´el´ement puis on trie le reste.
Plus pr´ecis´ement et it´erativement, `a la i-`eme ´etape du tri d’un vecteur de
longueur n, on cherche l’indice j du plus petit ´el´ement du sous-vecteur
d’indice compris entre i et n−1 et on ´echange cet ´el´ement avec l’´el´ement
d’indice i. L’´echange n’est effectivement r´ealis´e que si ce plus petit
´el´ement n’est pas d´ej`a en i.
e
S.Blazy (ENSIIE) Cours d’Algorithmique-Programmation 2 partie (IAP2):7pnovembrogramm reation2007imp´erat 3i/ve24et structures de donn´ees simples Tri par s´election
Interfaces
/∗ Interface
indice min sous vecteur: vecteur−> int
post calcule l’indice du plus petit ´el´ement du vecteur
∗/
/∗ Interface
tri selection: vecteur−> vecteur
post trie le tableau dans l’ordre croissant
∗/
e
S.Blazy (ENSIIE) Cours ...
Cours d’Algorithmique-Programmation 2 e partie(IAP2):programmationimp´erativeet structuresdedonne´essimples
Sandrine Blazy
Compl´ementssurlestableaux+PointeursenC
7 novembre 2007
` - 1 ere anne´e
essimples7novemb
Letypepointeursur´el´ement
Pointeurs et arguments
argc et argv
1 Tris par selection ´
Matrices
Siqhmitorlg’AsduroC)EIISNE(yzalB.2epitnomaamorrgeuP-
Pluspre´cise´mentetit´erativement,a`la i -e`me´etapedutrid’unvecteurde longueur n , on cherche l’indice j dupluspetit´ele´mentdusous-vecteur d’indice compris entre i et n − 1eton´echangecete´le´mentavecl’e´l´ement d’indice i .L’e´changen’esteffectivementre´alise´quesicepluspetit ´ele´mentn’estpasde´j`aen i .
Oncherchelepluspetite´l´ementduvecteuretonl’e´changeavecle premiere´l´ementpuisontrielereste.
42/37002erbmeursd’AlgNSIIE)CoeuP-orrgrotimhqip2emaamontiTpari´erstcelPnoicnirepi.Blazy(ES
/ ∗ Interface tri selection : vecteur − > vecteur post t r i e le tableau dans l ’ordre croissant ∗ /
/ ∗ Interface indice min sous vecteur : vecteur − > int postcalculel’indicedupluspetite´l´ementduvecteur ∗ /
472/2e00rTpielecars´Intetionsecafrpe2noitresductun´eeedonsrtSla.B(EzyIINShmique-Programma)EoCrudsA’glroti
let rec supprimer e l = match l with | [ ] − > [ ] | x : : l ’ − > i f x=e then l ’ else x : : ( supprimer e l ’ ) ; ;
let rec indice min sous vecteur l = match l with | [ ] − > failwith ”indice min sous vecteur : l i s t e vide” | [x] − > x | x : : l ’ − > min x (indice min sous vecteur l ’ ) ; ;
l ’ ) ; ;
let rec tri selection l = match l with | [ ] − > [ ] | − > let m = indice min sous vecteur l in letl’=supprimermlinm::(tris´election
42
Triparse´lection d’une liste, en Caml
vembs7no075/re20Programmation2ep’dlAogirhtimuq-ey(azSIEN)CIErsoulB.S
int indice min sous vecteur( int t [ ] , int imin = debut; int i ; for ( i = debut+1; i < =fin;i++) { i f (t [ i ] < t [ imin]) imin = i ; } return imin ; }
42/670sies´ennnos7lempurtctsedodruse
int debut,
int fin ) {
S.Blazy(lA’dsruoC)EIISNEogPre-qumithrigo2npetaoiarmmpirT´sraelectiond’untablae,uneC
Tripars´election:bilan
Contrairementauxfonctionsdetridelistesquiretournentunelistetri´ee, les fonctions de tri de vecteurs agissent par effet de bord : elles modifient levecteurquileurestpass´eenargumenteta`lafindutraitement,ce vecteuresttrie´.Onditqu’ellestravaillent en place .
Comparaison :laversionsurlesvecteursestconsid´erablementplussimple. Eneffet,nousnousrestreignonsauxe´le´mentsautresquelepluspetit simplementenincre´mentantl’indice i apr`esavoire´change´lepluspetit ´el´ementavecceluid’indice i alors que pour les listes, il nous faut parcourir a`nouveaulalistepourallersupprimercepluspetit´el´ement.
ispmel7sonevbmerdeesurctes´enndourtspeoi2nargotammuqimrP-egoAlthriou)Cd’rs(yNEISEI.SlBza
Letypepointeursure´l´ement
Pointeurs et arguments
argc et argv
Trispars´election
2 Matrices
tstcuresurdode´ennsies2npelA’dsruoimhtirogogPre-quioatmmraNEISEIC).SlBza(y
int main (void) { int ma matrice [NB LIG] [NB COL] ; for ( i=0; i < NBLIG;i++) for ( j=0; j < NBCOL;j++) ma matrice [ i ] [ j ] = i+j ;
#define NB LIG 10 #define NB COL 20
0/24
Matrices n × p De´finition
n lignes, p colonnes → untableaua` n lignes,chaquelignee´tantun tableau (vecteur) de p e´l´ements.
Matrice = tableau de dimension 2.
bre20071n7semevosseelpmiedsdn´onuctrretu
Remarque : on aurait pu omettre 4, mais pas 5.
Lesvaleurssontrang´eesligneparligne.
Matrices Initialisation
sseelpmin7semevo
int t [4][5] = { { 0,1,2,3,4 } , { 10,11,12,13,14 } , { 20,21,22,23,24 } , { 30,31,32,33,34 } , } ;
alyzE(SNSB.’AsdorlgE)IIurCoorP-margmhtieuqi
