API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Dec 5th, 2016
52
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 22.62 KB | None | 0 0
raw download clone embed print report
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3.  
  4. /**************************************************************************************************************************************************/
  5. /**************************************************************************************************************************************************/
  6. /**************************************************************************************************************************************************/
  7. /**************************************************************************************************************************************************/
  8. /*LES TRIES PAR TABLEAU*/
  9. /*---------------------*/
  10.  
  11.  
  12.  
  13.  
  14.  
  15. /**************************************************************************************************************
  16. /***************************************TRIE à BULLE*********************************************
  17. */
  18. // fonction echange qui echange deux variable x et y
  19. /*
  20. LES ENTREES : x ,y des pointeur de deux valeur
  21. LES SORTIES : les deux valeur x ,y echanger
  22. */
  23. void echanger(int *x ,int *y)
  24. {
  25. int p ;
  26. p =*x;
  27. *x = *y;
  28. *y = p;
  29. }//fin echange
  30.  
  31. // la fonction qui trie avec la methode trie à bulle
  32. /*
  33. LES ENTREES : n :la taille du talbeau
  34. tab :Le tableau qui contient les valeur
  35. LES SORTIES: le tableau avec des valeur triees
  36. */
  37. void trie_a_bulle_tableau (int n,int tab[n])
  38. {
  39. int i1,i2;
  40. int a_permute = 1; //on l'initialise pour qu il puisse entrer dans la boucle
  41. for( i1 = 0 ; (i1<n-1) && (a_permute == 1);i1++)
  42. { //on intialise a_permute par FAUX
  43. a_permute = 0;
  44. for(i2=n-1;i2>=i1+1;i2--)
  45. {
  46. //on echange si l'element à i2 est inferieur à l'lement à i2 - 1
  47. if(tab[i2] <tab[i2-1]) {
  48. echanger(&tab[i2] ,&tab[i2 - 1]);
  49. a_permute = 1;//donc on a fait une permutation
  50. } //fin if
  51. }//fin for_i2
  52. }//fin for_i1
  53. }//fin trie_a_bulle
  54.  
  55.  
  56. /**************************************************************************************************************
  57. /***************************************TRIE PAR INSERTION********************************************
  58. */
  59. //la fonction qui trie avec la methode d'inseriton
  60. /*
  61. LES ENTREES : n :la taille du talbeau
  62. tab :Le tableau qui contient les valeur
  63. LES SORTIES: le tableau avec des valeur triees
  64. */
  65. void trie_par_insertion_tableau (int n,int tab[n])
  66. {
  67. int i1,i2;
  68. for( i1 = 1 ;i1<n;i1++)
  69. {
  70. i2 = i1;
  71. while ( tab[i2] <tab[i2-1] && i2>0 )
  72. {
  73. echanger(&tab[i2] ,&tab[i2 - 1]);
  74. i2--;//on decremente
  75.  
  76. } //fin if
  77. }//fin for_i1
  78. }//fin trie_par_insertion
  79.  
  80. /**************************************************************************************************************
  81. /***************************************TRIE PAR SELECTION*****************************************************
  82. */
  83. //la fonction qui trie avec la methode de la selection
  84. /*
  85. LES ENTREES : n :la taille du talbeau
  86. tab :Le tableau qui contient les valeur
  87. LES SORTIES: le tableau avec des valeur triees
  88. */
  89. void trie_par_selection_tableau (int n,int tab[n])
  90. {
  91. int i1,i2;
  92. int indice_pivot;
  93. for(i1 = 0 ; i1<n-1 ;i1++)
  94. {
  95. indice_pivot = i1; // on affect le nv indice
  96. for(i2 = i1+1 ; i2<n ;i2++)
  97. {
  98. if(tab[indice_pivot]>tab[i2]) //si l"element a indice_pivot est sup a l'elemnt a l indice i2
  99. indice_pivot = i2;
  100. }//fin for_i2
  101. if(i1!=indice_pivot) // si l'indice trouve est different de l'indice de debut
  102. echanger(&tab[indice_pivot],&tab[i1]); // on echange
  103. }//fin for_i1
  104. }//fin trie_par_selection_tableau
  105.  
  106.  
  107. /**************************************************************************************************************
  108. /*******************************************TRIE RAPIDE*************************************************
  109. */
  110. //calcul de la median entre les element x,y et z (l'element milieu)
  111. /*
  112. LES ENTREES : x,y,z des valeur
  113. LES SORTIES : la median des valeur deja entrees(x,y,z)
  114. */
  115. int median(int x,int y,int z)
  116. {
  117. if((x<y && y<z) || (z<y && y<x)) return y;
  118. if((y<x && x<z) || (z<x && x<y)) return x;
  119. return z;
  120. }//
  121. // la fonction qui decoupe une liste d'element en 2
  122. /*
  123. LES ENTREES : n :la taille du talbeau
  124. tab :Le tableau qui contient les valeur
  125. debut :ou on commence
  126. fin :la postion de la derniere valeur
  127. LES SORTIES: le tableau avec des valeur triees
  128. */
  129. int partition(int n,int tab[n],int debut,int fin)
  130. {
  131. int pivot = median( tab[debut], tab[fin] , tab[(fin-debut)/2]);
  132. int i = debut;
  133. int j = fin;
  134. while(1) // on repete tant que les element a l'interieur sont vrai
  135. {
  136. while(tab[i]<pivot && i<=fin){ i++;} // si l'element à i et inferieur a pivot donc on increment i
  137. while(tab[j]>pivot && j>=0){ j--;} // si l'element à j et superieur a pivot donc on decrement j
  138. if(i<j) {
  139.  
  140. echanger(&tab[i],&tab[j]); // on echange (i) <-> (j)
  141. if(tab[i]== pivot) i++; // si (i) == pivot on incremente i
  142. if(tab[j]== pivot) j--; // si (j) == pivot on decrement j
  143. }//fin if
  144. else return j; // si i>=j on retourn j
  145. }
  146.  
  147. }//fin partition
  148.  
  149. //La fonction qui trie avec la methode Rapide
  150. /*
  151. LES ENTREES : n :la taille du talbeau
  152. tab :Le tableau qui contient les valeur
  153. debut :ou on a la premiers valeur
  154. fin :on on a la derniere valeur
  155. LES SORTIES: le tableau avec des valeur triees
  156. */
  157. void trie_rapide_tableau2(int n,int tab[n],int debut,int fin)
  158. {
  159. if(debut>=fin) return;
  160. int p = partition(n,tab,debut,fin); //on partionne notre tableau
  161. trie_rapide_tableau2(n,tab,debut,p-1); //on trie la partie a gauche
  162. trie_rapide_tableau2(n,tab,p+1,fin);//on trie la partie a droite
  163.  
  164.  
  165. }//fin trie_rapide_tableau2
  166.  
  167. // fonction mere
  168. /*
  169. LES ENTREES : n :la taille du talbeau
  170. tab :Le tableau qui contient les valeur
  171. LES SORTIES: le tableau avec des valeur triees
  172. */
  173. void trie_rapide_tableau(int n ,int tab[n])
  174. {
  175. trie_rapide_tableau2(n,tab,0,n -1);
  176. }//fin trie_rapide_tableau
  177.  
  178.  
  179.  
  180. /**************************************************************************************************************
  181. /*******************************************TRIE PAR EXTRACTION>>>>>>>>>(Methode de tournoi)*******************/
  182. //la fonction qui retoune le min avec la methode du tournoi
  183. int tournoi_tableau(int n,int tab,int fin)
  184. {
  185. int nombre_element =
  186. }
  187.  
  188. //la fonction qui trie le tableau par la methode de tournoi
  189. void trie_par_extraction_tournoi_tableau(int n,int tab[n])
  190. {
  191.  
  192. }//end trie_par_extraction_tournoi_tableau
  193.  
  194.  
  195.  
  196.  
  197. /**************************************************************************************************************
  198. /*******************************************TRIE PAR EXTRACTION>>>>>>>>>(Methode de heapsort)*******************/
  199.  
  200.  
  201. //la fonction descente cherche on descendant dans l'arbre le min
  202. /*
  203.  
  204. LES ENTREES : n :la taille du tableau
  205. tab :le tableau contennant les valeur
  206. taille :ou on a le dernier element
  207. nd :le noeud actuel
  208. LES SORTIES : le minimum des fils
  209. */
  210. int descente_tableau(int n,int tab[n],int taille,int nd)
  211. {
  212.  
  213. if((nd*2+1)>taille) return tab[nd]; // si le noeud n'a aucun fils
  214.  
  215. if((nd*2+1)==taille) // si le noeud a un seul fils (fils gauche)
  216. {
  217. int fils_gauche = descente_tableau(n,tab,taille,nd*2+1);
  218. if( fils_gauche< tab[nd] ) // si le fils et plus petit que le noeud on echange
  219. echanger(&tab[nd],&tab[nd*2+1]) ;
  220.  
  221. }
  222. else // si le noeud a les 2 fils
  223. {
  224. int fils_gauche = descente_tableau(n,tab,taille,nd*2+1);
  225. int fils_droite = descente_tableau(n,tab,taille,nd*2+2);
  226. if(fils_droite<=fils_gauche && fils_droite<tab[nd]) //si le fils droite est plus petit ou egal on echange
  227. echanger(&tab[nd],&tab[nd*2+2]);
  228. else if(fils_gauche<fils_droite && fils_gauche<tab[nd]) //sinon si le fils gauche et plus petit on echange
  229. echanger(&tab[nd],&tab[nd*2+1]);
  230. //sinon on ne fait rien
  231. }
  232.  
  233. //on retourne la valeur du noeud
  234. return tab[nd];
  235.  
  236. }//fin descente_tableau11
  237.  
  238.  
  239. //la fonction qui trie le tableau par la methode de tournoi
  240. /*
  241. LES ENTREES : n :La taille du tableau
  242. tab : le tableau qui contient les element
  243. LES SORTIES : le tableau tries
  244. */
  245. void trie_par_extraction_heapsort_tableau(int n,int tab[n])
  246. {
  247. int i ,j;
  248. for(i=n-1;i>=0;i--)
  249. {
  250. descente_tableau(n,tab,i,0);
  251. echanger(&tab[0],&tab[i]);
  252. }
  253. }//end trie_par_extraction_tournoi_tableau
  254.  
  255.  
  256.  
  257.  
  258.  
  259.  
  260.  
  261.  
  262.  
  263.  
  264.  
  265.  
  266.  
  267.  
  268.  
  269.  
  270.  
  271.  
  272. /**************************************************************************************************************************************************/
  273. /**************************************************************************************************************************************************/
  274. /**************************************************************************************************************************************************/
  275. /**************************************************************************************************************************************************/
  276. /*LES TRIES PAR POINTEUR*/
  277. /*---------------------*/
  278.  
  279.  
  280.  
  281. /*LES STRUCTURES DE DEONNEES*/
  282. //LISTE
  283. typedef struct cel
  284. {
  285. int element;
  286. struct cel* suivant;
  287. }liste;
  288.  
  289.  
  290. // ARBRE
  291. typedef struct nd
  292. {
  293. struct nd* fg;
  294. struct nd* fd;
  295. int element;
  296. }arbre;
  297.  
  298. //cette fonction trnasforme un tableau en une liste
  299. liste *tableau_en_liste(int n,int tab[n])
  300. {
  301. int i;
  302. liste *l = NULL;
  303. liste *p = NULL;
  304. for(i=0;i<n;i++)
  305. {
  306. if(i==0) //premiere iteration
  307. {
  308. p = l = (liste *)malloc(sizeof(liste));
  309. l->element = tab[i];
  310. l->suivant = NULL;
  311. continue;
  312. }//fin if
  313. l->suivant= (liste *)malloc(sizeof(liste));
  314. l->suivant->element = tab[i];
  315. l->suivant->suivant = NULL;
  316. l = l->suivant;
  317.  
  318. }//fin for
  319.  
  320. return p;
  321. }//fin tableau_en_liste
  322.  
  323. //cette fonction tronsforme une liste en tableau
  324. int *liste_en_tableau(liste *l)
  325. {
  326. liste *p = l;
  327. int i =0;
  328. int *tab = (int *)malloc(sizeof(int));
  329. while(p)
  330. {
  331. if(i==0) //premier iteartion
  332. {
  333. tab = (int *)malloc(sizeof(int));
  334. *tab = p->element;
  335. }
  336. else
  337. {
  338. tab = (int *)realloc(tab,(i+1)*sizeof(int));
  339. *(tab+i) = p->element;
  340. }
  341. p = p->suivant;
  342. i++;
  343.  
  344. }//fin while
  345. return tab;
  346. }//fin liste_en_tableau
  347.  
  348. /****************************************************************************************/
  349. /************************************TRIE A BULLE***************************************/
  350. //la fonction qui trie la liste avec la methode de trie à bulle
  351. /*
  352. LES ENTEES : l pointeur de la liste
  353. LES SORTIEES : la liste trier
  354. */
  355. void trie_a_bulle_pointeur(liste *l)
  356. {
  357. liste *p = l,
  358. *ps = NULL;
  359. while(p) //tant qu il y a des element
  360. {
  361. ps = p->suivant;
  362. while(ps) //tant qu il y a un suivant
  363. {
  364. if(p->element > ps->element)
  365. echanger(&p->element,&ps->element);
  366. ps = ps->suivant;
  367.  
  368. }//fin while ps
  369. p = p->suivant;
  370. }//fin while ^p
  371. }//fin trie_a_bulle_pointeur
  372.  
  373.  
  374. /*********************************************************************************************/
  375. /************************************TRIE PAR INSERTION***************************************/
  376. //la fonction qui trie avec la methode d'insertion
  377. /*
  378. LES ENTEES : l pointeur de la liste
  379. LES SORTIEES : la liste trier
  380. */
  381. void trie_par_insertion_pointeur(liste *l)
  382. {
  383. liste *p = l;
  384. liste *listeur ;
  385. while(p) //tant qu il y a des element
  386. {
  387. listeur = l;
  388. while(listeur!=p) //tant que listeur n est pas arrivé a lelement
  389. {
  390. if(listeur->element > p->element) //si listeur est superier a l'lement a p en echange
  391. echanger(&p->element,&listeur->element);
  392. listeur = listeur->suivant; //listeur suivant
  393. }//fin while ps
  394. p = p->suivant; //p suivant
  395. }//fin while p
  396. }//fin trie_par_insertion_pointeur
  397.  
  398.  
  399.  
  400. /*********************************************************************************************/
  401. /************************************TRIE PAR SELECTION***************************************/
  402. //la fonction qui trie avec la methode de selection
  403. /*
  404. LES ENTEES : l pointeur de la liste
  405. LES SORTIEES : la liste trier
  406. */
  407. void trie_par_selection_pointeur(liste *l)
  408. {
  409. liste *p = l;
  410. liste *ps;
  411. liste *choisit;
  412. while(p)//tant que l'lement existe
  413. {
  414. ps = p->suivant;
  415. choisit = p;
  416. while(ps)//tant que suivant existe
  417. {
  418. if(choisit->element > ps->element) //qi choisit > ps
  419. choisit = ps;//on choisit le nouveau element
  420. ps = ps->suivant; // ps suivant
  421.  
  422. }//fin while ps
  423. echanger(&p->element,&choisit->element); //echange p et choisit
  424. p = p->suivant; //p suivant
  425. }//fin while p
  426. }//fin trie_par_selection_pointeur
  427.  
  428.  
  429.  
  430. /*********************************************************************************************/
  431. /************************************TRIE RAPIDE*********************************************/
  432.  
  433.  
  434. // la fonction qui partionne une liste et donne la liste gauche
  435. /*
  436. LES ENTREES : l : la liste principale
  437. LES SORTIES lg : la liste qui contiendra les element inferieur a pivot
  438.  
  439. */
  440. liste *partition_liste_gauche(liste *l)
  441. {
  442. liste *p =l;
  443. liste *pivot = l;
  444. liste *ll;
  445. liste *lg =NULL ;
  446. while(p)
  447. {
  448. // if(p->element < pivot->element)
  449. if((p->element <= pivot->element) && (p!=pivot))
  450. {
  451. liste *ll = (liste *)malloc(sizeof(liste));
  452. ll->element = p->element;
  453. ll->suivant = lg;
  454. lg = ll;
  455.  
  456. }//fin if
  457. p = p->suivant;
  458.  
  459. }//fin while p
  460. return lg;
  461. }//fin partition_liste
  462.  
  463. // la fonction qui partionne une liste et donne la liste droite
  464. /*
  465. LES ENTREES : l : la liste principale
  466. LES SORTIES
  467. ld : la liste qui contiendra les element inferieur a pivot
  468. */
  469. liste *partition_liste_droite(liste *l)
  470. {
  471. liste *p =l;
  472. liste *pivot = l;
  473. liste *ll;
  474. liste *ld =NULL ;
  475. while(p)
  476. {
  477. if(p->element > pivot->element)
  478. {
  479. liste *ll = (liste *)malloc(sizeof(liste));
  480. ll->element = p->element;
  481. ll->suivant = ld;
  482. ld = ll;
  483.  
  484. }//fin if
  485. p = p->suivant;
  486.  
  487. }//fin while p
  488. return ld;
  489. }//fin partition_liste
  490.  
  491.  
  492. //la fonction qui relie deux liste
  493. /*
  494. LES ENTREES : lg la liste a gauche
  495. ld la liste a droite
  496. LES SORTIES : une liste conbine lg->>ld
  497. */
  498. liste *relier(liste *lg,liste *pivot,liste *ld)
  499. {
  500. liste *p = lg;
  501. if(lg)
  502. {
  503. while(p->suivant)
  504. p = p->suivant;
  505.  
  506. p->suivant = pivot;
  507. pivot->suivant = ld;
  508. return lg;
  509. }
  510. pivot->suivant = ld;
  511. return pivot;
  512.  
  513. }//fin relier
  514.  
  515. //la fonction qui trie une liste avec la methode quicksort
  516. /*
  517. LES ENTEES : l pointeur de la liste
  518. LES SORTIEES : la liste trier
  519. */
  520. liste *trie_rapide_pointeur(liste *l)
  521. {
  522. if(l==NULL) return l;
  523. if(l->suivant == NULL) return l;
  524.  
  525. liste *lg = partition_liste_gauche(l);
  526. liste *ld = partition_liste_droite(l);
  527.  
  528. lg =trie_rapide_pointeur(lg);
  529. ld =trie_rapide_pointeur(ld);
  530.  
  531. l = relier(lg,l,ld);
  532. return l;
  533. }//fin trie_rapide_pointeur
  534.  
  535.  
  536.  
  537.  
  538.  
  539. /*************************************************************************************************/
  540. /************************************TRIE EXTRACTION*********************************************/
  541.  
  542. //CETTE fonction verifie une position donnees est ce qu il est dans l'arbre
  543. /*
  544. LES ENTREES : position :la position actuel
  545. position_rechercher : la position rechercher
  546. LES SORTIES : true (1) si la position est dans le ss arbre false(0) sinon
  547. */
  548. int dans_arbre(int position,int position_rechercher)
  549. {
  550. if(position_rechercher<position) return 0;
  551. if(position == position_rechercher) return 1;
  552. return dans_ss_arbre_gauche(position,position_rechercher) + dans_ss_arbre_droite(position,position_rechercher);
  553. }//fin dans_arbre
  554.  
  555. //verifier si l'eemnt est dans le ss arbre gauche
  556. /*
  557. LES ENTREES : position :la position actuel
  558. position_rechercher : la position rechercher
  559. LES SORTIES : true (1) si la position est dans le ss arbre gauche false(0) sinon
  560. */
  561. int dans_ss_arbre_gauche(int position,int position_rechercher)
  562. {
  563. if(2*position == position_rechercher ) return 1;
  564. return dans_arbre(2*position,position_rechercher);
  565. }//fin dans_ss_arbre_gauche
  566.  
  567.  
  568. //verifier si l'element est dans le ss arbre droite
  569. /*
  570. LES ENTREES : position :la position actuel
  571. position_rechercher : la position rechercher
  572. LES SORTIES : true (1) si la position est dans le ss arbre doite false(0) sinon
  573. */
  574. int dans_ss_arbre_droite(int position,int position_rechercher)
  575. {
  576. if((2*position+1) == position_rechercher ) return 1;
  577. return dans_arbre(2*position+1,position_rechercher);
  578. }//fin dans_ss_arbre_gauche
  579.  
  580.  
  581. //insertion dans l'arbre avec la position donnee dans la liste
  582. /*
  583. LES ENTREES : a : notre arbre
  584. l : l'element qu on veut inserer
  585. pr : la position ou on veut inserer notre element
  586. posi : la position actuel
  587. LES SORTIES : notre arbre avec l'element qui est insere
  588. */
  589. arbre *inserer_arbre(arbre* a,liste *l,int pr,int posi)
  590. {
  591. if(pr==posi)
  592. {
  593. arbre *ap = (arbre *)malloc(sizeof(arbre));
  594. ap->element = l->element;
  595. ap->fd = ap->fg = NULL;
  596. return ap;
  597. }//fin p==1
  598.  
  599. if(dans_ss_arbre_gauche(posi,pr))
  600. {
  601. a->fg = inserer_arbre(a->fg,l,pr,2*posi);
  602. }
  603. if(dans_ss_arbre_droite(posi,pr))
  604. {
  605. a->fd = inserer_arbre(a->fd,l,pr,2*posi+1);
  606. }
  607. return a;
  608. }
  609.  
  610.  
  611.  
  612. //la foction qui construit l arbre a partir d une liste
  613. /*
  614. LES ENTREES : l : la liste qui contient les elements
  615. LES SORTIES : l'arbre construit avec les elements de la liste
  616. */
  617. arbre *liste_en_arbre(liste *l)
  618. {
  619. arbre *a = NULL;
  620. liste *p = l;
  621. int i=1;
  622. while(p)
  623. {
  624. a = inserer_arbre(a,p,i++,1);
  625. p = p->suivant;
  626. }//fin while
  627.  
  628. return a;
  629. }//fin liste_en_arbre
  630.  
  631. //la fonction descente organise l'arbre de tel sorte que le l'element au sommet doit etre supperier a ces fils
  632. /*
  633. LES ENTREES : a : l arbre qu on va descendre
  634. position : la position actuel
  635. fin : ou doit termine
  636. LES SORTIES : true (1) si la position est dans le ss arbre gauche false(0) sinon
  637. */
  638. arbre *descente_pointeur(arbre *a,int position,int fin)
  639. {
  640. //le cas si le noeud n'a aucun fils
  641. if((a->fd == NULL) && (a->fg == NULL)) return a;
  642. //le cas ou le noeud est le dernier element
  643. if(position==fin) return a;
  644. //si aucun de ses fils est en mesure de le traiter
  645. if((position*2)>fin) return a;
  646. //le cas ou le noeud n'a pas d'element droite
  647. //si on peut traiter le fils gauche
  648. if((position*2+1)>fin )
  649. {
  650. //si le fils gauche est apres le dernier element on doit pas le traiter
  651. // donc on le retourne
  652. if(position*2>fin) return a;
  653. //sinon on lui fait le mm traitemeent descente
  654. a->fg = descente_pointeur(a->fg,2*position,fin);
  655. //on test si le fils gauche est inferieur a l'element du noeud
  656. //si oui on l echange
  657. if((a->fg->element) < a->element)
  658. echanger(&(a->fg->element),&a->element);
  659. //apres le traitement on retourne
  660. return a;
  661.  
  662. }
  663.  
  664.  
  665. //les deux fils existe
  666.  
  667.  
  668.  
  669.  
  670. //on traite le fils gauche
  671. a->fg = descente_pointeur(a->fg,2*position,fin);
  672. //on traite le fils droite
  673. a->fd = descente_pointeur(a->fd,2*position+1,fin);
  674. int vfg = a->fg->element;
  675. int vfd = a->fd->element;
  676. // on compare
  677. if(vfg<vfd)
  678. {
  679. if(vfg < a->element)
  680. echanger(&a->fg->element,&a->element);
  681. }
  682.  
  683. else
  684. if(vfd < a->element) echanger(&a->fd->element,&a->element);
  685. //on retourne notre noeud
  686. return a;
  687.  
  688.  
  689. }// fin descente_pointeur
  690.  
  691. //cette fonctient recupere un noeud a partir d une position donnes
  692. /*
  693. LES ENTREES : a : notre arbre
  694. position : la position qu on veut recuperer
  695. pa : la position actuel
  696. LES SORTIES : notre noeud
  697. */
  698. arbre *element_arbre(arbre *a,int position,int pa)
  699. {
  700. if(pa == position) return a;
  701. if(dans_ss_arbre_gauche(pa,position)) return element_arbre(a->fg,position,pa*2);
  702. if(dans_ss_arbre_droite(pa,position)) return element_arbre(a->fd,position,pa*2+1);
  703. }//fin element_arbre
  704.  
  705.  
  706.  
  707.  
  708. //la sous la fonction qui trie avec la methode d'extraction
  709. /*
  710. LES ENTREES :a : l'arbree a : traiter
  711. l : la liste des element
  712. position : la position actuel dans la liste
  713. sortie :notre arbre trier
  714. */
  715. arbre *trie_par_extraction_heapsort_pointeur_ss(arbre *a,liste *l,int position)
  716. {
  717. if(l==NULL) return a;
  718. a=trie_par_extraction_heapsort_pointeur_ss(a,l->suivant,position+1);
  719. a=descente_pointeur(a,1,position);
  720.  
  721. echanger(&a->element,&element_arbre(a,position,1)->element);
  722. return a;
  723. }//fin trie_par_extraction_heapsort_tableau_sous
  724.  
  725.  
  726.  
  727. //arbre en liste
  728. /*
  729. LES ENTREES : a :arbre
  730. l : la liste
  731. LES SORTIES : la liste
  732. */
  733. liste *arbre_en_liste(arbre *a,liste *l)
  734. {
  735. liste *p=l;
  736. liste *ln = NULL;
  737. int i=1;
  738. arbre *element;
  739. while(p)
  740. {
  741. element = element_arbre(a,i++,1);
  742. liste *pp =(liste *)malloc(sizeof(liste));
  743. pp->element = element->element;
  744. pp->suivant = ln;
  745. ln = pp;
  746. p = p->suivant;
  747. }
  748. return ln;
  749. }//fin arbre_en_liste
  750.  
  751.  
  752.  
  753. //la la fonction qui trie avec la methode d'extraction
  754. /*
  755. LES ENTREES : l : la liste des element
  756. sortie :notre arbre trier sous forme d une liste
  757. */
  758. liste *trie_par_extraction_heapsort_pointeur(liste *l)
  759. {
  760. arbre *a=liste_en_arbre(l);
  761. a = trie_par_extraction_heapsort_pointeur_ss(a,l,1);
  762. return (liste *)arbre_en_liste(a,l);
  763. }//fin trie_par_extraction_heapsort_pointeur
  764.  
  765.  
  766.  
  767.  
  768.  
  769.  
  770.  
  771.  
  772.  
  773.  
  774.  
  775.  
  776. /************************************************************************************************************************************************/
  777. /************************************************************************************************************************************************/
  778. /************************************************************************************************************************************************/
  779. /************************************************************************************************************************************************/
  780. /************************************************************************************************************************************************/
  781. /******************************************************************* MAIN *********************************************************************/
  782.  
  783.  
  784.  
  785.  
  786.  
  787.  
  788.  
  789.  
  790.  
  791.  
  792.  
  793.  
  794.  
  795.  
  796. int main(int arg ,char** args)
  797. {
  798. int n=5;
  799. int i,tab[5] = {14,15,14,12,12};
  800. // liste *l = tableau_en_liste(n,tab);
  801. // l= trie_par_extraction_heapsort_pointeur(l);
  802. // int *tab1 = liste_en_tableau(l);
  803. trie_rapide_tableau(n,tab);
  804. for(i = 0 ;i<n;i++) printf("\t%d",tab[i]); printf("\n");
  805.  
  806.  
  807. system("PAUSE");
  808. return 0;
  809. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!