Ecole Polytechnique de Tunisie 2010/2011 Ecole Polytechnique de Tunisie Compte
Ecole Polytechnique de Tunisie 2010/2011 Ecole Polytechnique de Tunisie Compte Rendu du T.P Informatique LES LISTES CHAINées Réalisé par : Chiheb BEN HAMMOUDA A.U : 2010-2011 1 Ecole Polytechnique de Tunisie 2010/2011 Exercice n°1: Polynômes On se propose dans cet exercice de manipuler des polynômes à une variable réelle X, ainsi on se charge de les lire, afficher, calculer l'image d'un réel donné, déterminer leurs degrés etc… Les polynômes à une variable peuvent être représentés par des listes de monômes, où chaque monôme est caractérisé par un exposant entier et un coefficient réel. exemple: P(x)=5x3-3x+7+2x4 #include<conio.h> #include<stdio.h> #include<malloc.h> #include<math.h> struct noeud{ float x; int e; struct noeud * suivant;}; typedef struct noeud listep; typedef listep* liste; Fonction lecture: liste adjq(float a,int n, liste polynome) {liste p; liste courant; p=(listep*)malloc(sizeof(listep)); p->x=a; p->e=n; p->suivant=NULL; if (!polynome) polynome=p; else {courant=poly; while (courant->suivant) courant=courant->suivant; courant->suivant=p; } return polynome; } liste lecture() {float a; int i; int b; liste p=NULL; do {printf("\n saisir le coefficient: "); scanf("%f",&a); printf("\n saisir l'exposant: "); scanf("%d",&i); 2 Ecole Polytechnique de Tunisie 2010/2011 p=adjq(a,i,p); printf("\n voulez vous ajouter autre coefficients: tapez 1 si oui,0 si non : "); scanf("%d",&b); } while(b); return p;} Fonction d’affichage: void affiche(liste p) {liste courant=p; while (courant->suivant!=NULL) { printf("%f*x^%d+",courant->x,courant->e); courant=courant->suivant;} printf("%f*x^%d",courant->x,courant->e); } Fonction qui calcule l'image d'un réel: double valeur(liste p,float x) {liste courant=p; float s=0; float y; while (courant) {y=courant->e; s=s+(courant->x)*pow(x,y); courant=courant->suivant;} return s;} Fonction qui calcule le degré d’un polynôme : int degre(liste p) {liste courant=p; int n; n=courant->e; while (courant) {if (n<courant->e) n=courtant->e; courant=courant->suivant;} return n; } typedef struct {float x; int e; }monome; Fonction qui multiplie le polynôme avec un monôme: liste foisx(liste p,monome m) {liste courant=p; while (courant) {courant->x=(courant->x)*(m.x); courant->e=(courant->e)+(m.e); courant=courant->suivant;} return p; } 3 Ecole Polytechnique de Tunisie 2010/2011 Fonction qui somme deux polynômes : liste somme(liste p,liste q) {liste pol=p; liste pil; char trouve; if (pol!=NULL) if (q!=NULL) { while (pol!=NULL) { pil=q; trouve=0; while (!trouve&&(pil!=NULL)) {if ((pol->e)==(pil->e)) {trouve=1; pol->x=pol->x+pil->x; } pil=pil->suivant; } pol=pol->suivant; } return p; } else return p; else return q; } Fonction qui dérive un polynôme: liste derive(liste p) {liste pol; pol=p; while(pol!=NULL) {if (pol->e==0) pol->x=0; else {pol->x=(pol->x)*(pol->e); pol->e=pol->e-1; } pol=pol->suivant; } return p; } Le programme principal : void main() {clrscr(); liste polynome; float b; monome m; liste p1; liste p2,p3; polynome=NULL; polynome=lecture(); liste p=polynome; printf("\n le polynome p est:\n P= "); 4 Ecole Polytechnique de Tunisie 2010/2011 affiche(polynome); printf("\n le degre de ce polynome est: %d.",degre(po)); printf("\n entrer un reel : "); scanf("%f",&b); printf("\n la valeur de p pour ce reel est: %f",valeur(po,b)); printf("\n entrer un monome: \n l'exposant: "); scanf("%d",&d.e); printf("\n le coefficient: "); scanf("%f",&m.x); p1=foisx(polynome,m); printf("\n le produit entre p et le monome est\n P1= "); affiche(p1); printf("\n entrer un nouveau polynome p2:\n "); p2=lecture(); printf("\n la polynome p2 est:\n P2="); affiche(p2); printf("\n la somme entre les polynome P2 et P est:\n P3= "); p3=somme(polynome,p2); affiche(p3); liste p4=derive(p); printf("\n le polynome est\n"); affiche(p); printf("\n le polynome derivé de P est: \nP4="); affiche(p4); getch(); } Exercice n°2: Tri par Fusion Le but de cet exercice est d'assurer le triage d'un polynôme de façon itérative de monôme de plus haut degré au plus bas degré. Ainsi la nécessité de programmer des fonctions capables de déterminer la longueur d'une liste donnée (un polynôme dans ce cas), de diviser une liste chaînée en deux moitiés de même longueur à un monôme près, de fusionner deux listes chaînées triées de façon à obtenir une liste trié. Cet exercice peut être considéré comme la suite de premier exercice, alors on va utiliser les fonctions définies dans l'exercice précédent comme l'adjonction en tête, la lecture, l'affichage etc… Fonction qui détermine la longueur d’une liste : int longueur(liste p) {liste courant=p; int i=0; while(courant) {i++; courant=courant->suivant; } return i; } Fonction qui permet de diviser une liste : void deviser(liste p,liste*lg,liste*ld) { 5 Ecole Polytechnique de Tunisie 2010/2011 liste po=p; int i=longue(p); int k,b; float a; for(k=1;k<=i/2;k++) {b=po->e; a=po->x; (*lg)=adjq(a,b,(*lg)); po=po->suivant; } for (k=(i/2)+1;k<=i;k++) {a=po->x; b=po->e; (*ld)=adjq(a,b,(*ld)); po=po->suivant; } Fonction qui permet de fusionner deux listes triées : liste fusion(liste first,liste second) {liste p=first; liste q=second; liste l,lead; if(p->expo>q->expo){l=p; p=p->suivant; l->suivant=q; } else{l=q; q=q->suivant; l->suivant=p; }; lead=l; while(p&&q){if(p->expo>q->expo){l->suivant=p; p=p->suivant; l=l->suivant; l->suivant=q; } else{l->suivant=q; q=q->suivant; l=l->suivant; l->suivant=p; } } return(lead); } Fonction itérative principale: liste trier(liste first) {liste second; if(longueur(first)>1){second=diviser(first); first=trier(first); second=trier(second); first=fusion(first,second); }; 6 Ecole Polytechnique de Tunisie 2010/2011 return(first); } 7 uploads/Litterature/ exercice-n.pdf
Documents similaires



