MATRICE CREUSE

#include "\MyGraph.cpp"

struct Noeud
{
	int l,c,v;
	struct Noeud *suivL,*suivC;
};

class MatriceCreuse
{
	public:
		MatriceCreuse (int MaxL, int MaxC);
		~MatriceCreuse();
		void Assigner (int ligne, int colonne, int valeur);
		int  Extraire (int ligne, int colonne);
		void Lire     ();
		void Ecrire   (int Ld, int Lf, int Cd, int Cf);
		MatriceCreuse operator + (MatriceCreuse M1);
		int NbLignes()   { return MaxL; }
		int NbColonnes() { return MaxC; }
	private:
		int MaxL, MaxC;
		struct Noeud * VPL[1000], * VPC[1000];
};

void AffichageMatrice(MatriceCreuse M)
{
	int PosX=4,PosY=3;
	int Ld,Lf,Cd,Cf;
	if(M.NbLignes()<21) Lf=M.NbLignes() ; else Lf=20;
	if(M.NbColonnes()<15) Cf=M.NbColonnes() ; else Cf=14;
	gotoxy(PosX,PosY);
	M.Ecrire(1,Lf,1,Cf);
	textcolor(0);
	textbackground(15);
	if(M.NbLignes()>20){gotoxy(79,22);cprintf("%c",25);}
	if(M.NbColonnes()>14){gotoxy(77,1);cprintf("%c",16);}
	PosX=8;
	int NumC=1, NumL=1;
	gotoxy(PosX,PosY);
	char c1='!';
	do
	{
		gotoxy(10,23);
		cout <<setw(4)<<NumL<<":"<<setw(4)<<NumC;
		if(PosX>73) PosX=73;
		if(PosY>22) PosY=22;
		gotoxy(PosX,PosY);
		c1=getch();
		if(c1==71)      //HOME
		{
			PosX=8;
			NumC=1;
		}
		else
		if(c1==72)      //FLECHE HAUT
		{
			if(PosY>3 && NumL<=20) PosY--;
			if(NumL>1 ) NumL--;
		}
		else
		if(c1==73)      //EXTREMITE HAUT
		{
			PosY=3;
			NumL=1;
		}
		else
		if(c1==75)      //FLECHE GAUCHE
		{
			if(PosX>8 &&NumC<=14) PosX-=5;
			if(NumC>1) NumC--;
		}
		else
		if(c1==77)      //FLECHE DROIT
		{
			if( PosX < 5*M.NbColonnes()) PosX+=5;
			if( NumC < M.NbColonnes()) NumC++;
		}
		else
		if(c1==79)      //FIN
		{
			PosX=(M.NbColonnes()*5)+3;
			NumC=M.NbColonnes();
		}
		else
		if(c1==80)      //FLECHE BAS
		{
			if( PosY < M.NbLignes()+2) PosY++;
			if( NumL < M.NbLignes()) NumL++;
		}
		else
		if(c1==81)      //EXTREMITE BAS
		{
			PosY=M.NbLignes()+2;
			NumL=M.NbLignes();
		}
		gotoxy(4,3);
		if(NumL>20) Ld=NumL-19;else Ld=1;
		if(M.NbLignes()<=20) Lf=M.NbLignes(); else Lf=Ld+19;
		if(NumC>14) Cd=NumC-13;else Cd=1;
		if(M.NbColonnes()<=14) Cf=M.NbColonnes(); else Cf=Cd+13;
		textcolor(0);
		textbackground(15);
		gotoxy(79,3);cprintf(" ");
		gotoxy(79,22);cprintf(" ");
		gotoxy(3,1);cprintf(" ");
		gotoxy(77,1);cprintf(" ");
		M.Ecrire(Ld,Lf,Cd,Cf);
		if(NumL>20) {gotoxy(79,3);cprintf("%c",24);}
		if(M.NbLignes()>20 && NumL<M.NbLignes()){gotoxy(79,22);cprintf("%c",25);}
		if(NumC>14 ) {gotoxy(3,1);cprintf("%c",17);}
		if(M.NbColonnes()>14 && NumC<M.NbColonnes()){gotoxy(77,1);cprintf("%c",16);}
		gotoxy(PosX,PosY);
	}
	while(c1!=27);
}

void Cadre()
{
	textbackground(15);textcolor(0);
	clrscr();printf("\n");
	printf("  ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ»\n");
	for( int i=0;i<20;i++)
	printf("  º                                                                         º\n");
	printf("  ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍͼ\n");
	textbackground(0);textcolor(15);gotoxy(3,24);
}

MatriceCreuse::MatriceCreuse(int ML, int MC)
{
	MaxL=ML;MaxC=MC;
	for(int l=1;l<=MaxL;l++) {VPL[l]=NULL;}
	for(int c=1;c<=MaxC;c++) {VPC[c]=NULL;}
}
MatriceCreuse::~MatriceCreuse()
{
	/*struct Noeud *n=NULL,*ns=NULL;
	for(int l=1;l<=this->NbLignes();l++)
	{
	n=VPL[l];
	ns=n->suivL;
	while(n)
		{
		delete n;
		n=ns;
		ns=ns->suivL;
		}
	delete n;delete ns;
	} */
	for(int l=1;l<=this->NbLignes();l++)   {VPL[l]=NULL ;}
	for(int c=1;c<=this->NbColonnes();c++) {VPC[c]=NULL ;}
}

void MatriceCreuse::Assigner(int l, int c, int v)
{
	struct Noeud *nouv , *courant,*prec;
	nouv =(struct Noeud *)malloc (sizeof(struct Noeud));
/*	courant =(struct Noeud *)malloc (sizeof(struct Noeud));
	prec =(struct Noeud *)malloc (sizeof(struct Noeud));
*/	if(v) {nouv->l=l;nouv->c=c;nouv->v=v;nouv->suivL=NULL;nouv->suivC=NULL;}
	/*INSERTION DANS LA LIGNE L*/
	courant = VPL[l];
	while(courant && (courant->c< c))
	{
	  prec=courant;
	  courant=courant->suivL;
	}
	if (v)
	{
	  nouv->suivL=courant;
	  if (courant==VPL[l]) VPL[l]=nouv;else	prec->suivL=nouv;
	}
	else
	{
	  if(courant==VPL[l]) VPL[l]=courant->suivL; else prec->suivL=courant->suivL;
	}
	/*INSERTION DANS LA COLONNE C*/
	courant=VPC[c];
	while(courant && (courant->l < l))
	{
	  prec=courant;
	  courant=courant->suivC;
	}
	if (v)
	{
	  nouv->suivC=courant;
	  if (courant==VPC[c]) VPC[c]=nouv; else prec->suivC=nouv;
	}
	else
	{
	  if(courant==VPC[c]) VPC[c]=courant->suivC; else prec->suivC=courant->suivC;
	}
}
int MatriceCreuse::Extraire( int l, int c )
{
	struct Noeud *Ln;
	int trouve=0;
	Ln=VPL[l];
	while(Ln && trouve==0)
	{
		if (Ln->c==c) {trouve =1;return Ln->v;}
		else if(Ln->c > c) return 0;
		else Ln=Ln->suivL;
	}
	if (trouve==0) return 0;
}

void MatriceCreuse::Lire()
{
	for(int l=0; l<MaxL ;l++)
		for(int c=0; c<MaxC ; c++)
			Extraire(l,c);
}

void MatriceCreuse::Ecrire(int Ld, int Lf, int Cd, int Cf)
{
	struct Noeud *ln;
	int elt,posY=3;
	int ll,cc;
	for(ll=Ld; ll<=Lf; ll++)
	{
		gotoxy(4,posY++);
		for(cc=Cd; cc<=Cf; cc++)
		{
			int e=Extraire(ll,cc);
			cout <<setw(5)<<e;
		}
		printf("\n");
	}
}

MatriceCreuse MatriceCreuse::operator + (MatriceCreuse M1)
{
	int v1=0,v2=0;
	MatriceCreuse MR(this->NbLignes(),this->NbColonnes());
	for (int l=1;l<=this->NbLignes();l++)
		for (int c=1;c<=this->NbColonnes();c++)
		{
			v1=this->Extraire(l,c);
			v2=M1.Extraire(l,c);
			if (v1+v2) MR.Assigner(l,c,v1+v2);
		}
	return MR;
}

MatriceCreuse Multiplication(MatriceCreuse &m )
{
	int l,c,e=0;
	do
	{
		setfillstyle(1,0);
		bar(20,335,610,460);
		settextstyle(SMALL_FONT,0,5);
		outtextxy(230,350,"Dimension de la 2Šme matrice :");
		settextstyle(SMALL_FONT,0,5);
		outtextxy(450,363,"Nombre de lignes :");
		outtextxy(440,378,"Nombre de colonnes :");
		line(520,368,525,368);
		gotoxy(66,23);scanf("%d",&l);
		setcolor(1); line(520,368,525,368);
		setcolor(15);line(520,384,525,384);
		gotoxy(66,24);scanf("%d",&c);
		if(l!=m.NbColonnes())
		{
			bar(20,335,610,460);
			int vl=m.NbLignes();
			int vc=m.NbColonnes();
			outtextxy(330,390,"Reprenez! le nombre de lignes de la 2Šme matrice ");
			outtextxy(330,410,"est diff‚rent du nombre de colonnes de la 1Šre matrice:");
			char*d;
			outtextxy(320,430,itoa(vl,d,10));
			outtextxy(340,430,"X");
			outtextxy(360,430,itoa(vc,d,10));
			getch();
		}
	}
	while(l!=m.NbColonnes());
	MatriceCreuse M2(l,c);
	setfillstyle(1,0);
	bar(20,335,610,460);
	settextstyle(SMALL_FONT,0,5);
	outtextxy(300,350,"Assigner un ‚lement pour la 2Šme matrice ?(O/N)");
	char r;
	r=getch();
	while(r==111)
	{
		int il,ic,iv;
		setfillstyle(1,0);
		bar(20,335,610,460);
		settextstyle(SMALL_FONT,0,5);
		outtextxy(458,348,"Ligne :");
		outtextxy(450,363,"Colonne :");
		outtextxy(454,378,"Valeur :");
		do
		{ line(488,353,493,353);gotoxy(62,22);
		scanf("%d",&il);
		if(il<1||il>m.NbLignes())
		{
		setfillstyle(1,0);
		bar(488,335,625,353);
		}
		}while(il<1||il>m.NbLignes());
		setcolor(1); line(488,353,493,353);
		setcolor(15);line(488,369,493,369);
		do
		{ line(488,369,493,369);gotoxy(62,23);
		scanf("%d",&ic);
		if(ic<1||ic>m.NbColonnes())
		{
		setfillstyle(1,0);
		bar(488,351,625,369);
		}
		}while(ic<1||ic>m.NbColonnes());
		setcolor(1); line(488,369,493,369);
		setcolor(15);line(488,387,493,387);
		gotoxy(62,24);scanf("%d",&iv);
		if (iv) M2.Assigner(il,ic,iv);
		settextstyle(SMALL_FONT,0,5);
		outtextxy(300,410,"Assigner autre ‚l‚ment ?(O/N)");
		r=getch();
	}
	MatriceCreuse MatRes(m.NbLignes(),M2.NbColonnes());
	for (l=1;l<=MatRes.NbLignes();l++)
		for (c=1;c<=MatRes.NbColonnes();c++)
		{
			e=0;
			for (int k=1;k<=M2.NbLignes();k++)
			{
			e=e+(m.Extraire(l,k)*M2.Extraire(k,c));
			}
			if (e) MatRes.Assigner(l,c,e);
		}
	closegraph();
	clrscr();
	Cadre();
	cprintf("Fleche Gauche %c Fleche Haut %c  Fleche Bas %c Fleche Droit %c Esc pour sortir ",17,24,25,16);
	gotoxy(23,1);
	cprintf("Resultat de la multiplication : Matrice %d X %d",MatRes.NbLignes(),MatRes.NbColonnes());
	AffichageMatrice(MatRes);
	return MatRes;
}

int main(void)
{
   Dekhla();
   int MxL, MxC;
   settextstyle(SMALL_FONT,0,6);
   outtextxy(200,320,"Dimension de la matrice creuse :");
   outtextxy(201,320,"Dimension de la matrice creuse :");
   settextstyle(SMALL_FONT,0,5);
   outtextxy(450,363,"Nombre de lignes :");
   outtextxy(440,378,"Nombre de colonnes :");
   do
   { line(520,368,525,368);gotoxy(66,23);
   scanf("%d",&MxL);
   if(MxL<1||MxL>1000)
	{
	 setfillstyle(1,0);
	 bar(520,350,630,368);
	}
   }while(MxL<1||MxL>1000);
   setcolor(1); line(520,368,525,368);
   setcolor(15);line(520,384,525,384);
   do
   { line(520,384,525,384);gotoxy(66,24);
   scanf("%d",&MxC);
   if(MxC<1||MxC>1000)
	{
	 setfillstyle(1,0);
	 bar(520,366,630,384);
	}
   }while(MxC<1||MxC>1000);
   MatriceCreuse M(MxL,MxC);
   char c='!';
   Graphisme();
   int val=1;
   Twichia(pos);
   while (val==1)
   {
	setfillstyle(1,0);
	bar(150,180,450,380);
	Twichia(pos);
	MenuGrise();
	MenuSurbrillant(pos);
	c= getch();
	if (c==13)
	{
		switch(pos)
		{
			case 1:
			{
				int il,ic,iv;
				setfillstyle(1,0);
				bar(20,140,610,460);
				BAR();
				settextstyle(SMALL_FONT,0,6);
				outtextxy(140,320,"Assigner un ‚lement");
				outtextxy(141,320,"Assigner un ‚lement");
				settextstyle(SMALL_FONT,0,5);
				outtextxy(458,348,"Ligne :");
				outtextxy(450,363,"Colonne :");
				outtextxy(454,378,"Valeur :");
				do
				{ line(488,353,493,353);gotoxy(62,22);
				scanf("%d",&il);
				if(il<1||il>M.NbLignes())
				{
				setfillstyle(1,0);
				bar(488,335,625,353);
				}
				}while(il<1||il>M.NbLignes());
				setcolor(1); line(488,353,493,353);
				setcolor(15);line(488,369,493,369);
				do
				{ line(488,369,493,369);gotoxy(62,23);
				scanf("%d",&ic);
				if(ic<1||ic>M.NbColonnes())
				{
				setfillstyle(1,0);
				bar(488,351,625,369);
				}
				}while(ic<1||ic>M.NbColonnes());
				setcolor(1); line(488,369,493,369);
				setcolor(15);line(488,387,493,387);
				gotoxy(62,24);scanf("%d",&iv);
				M.Assigner(il,ic,iv);
				Graphisme();
				break;
			}
			case 2:
			{
				int il,ic,iv;
				setfillstyle(1,0);
				bar(20,140,610,460);
				BAR();
				settextstyle(SMALL_FONT,0,6);
				outtextxy(140,320,"Extraire un ‚lement");
				outtextxy(141,320,"Extraire un ‚lement");
				settextstyle(SMALL_FONT,0,5);
				outtextxy(458,348,"Ligne :");
				outtextxy(450,363,"Colonne :");
				do
				{ line(488,353,493,353);gotoxy(62,22);
				scanf("%d",&il);
				if(il<1||il>M.NbLignes())
				{
				setfillstyle(1,0);
				bar(488,335,625,353);
				}
				}while(il<1||il>M.NbLignes());
				setcolor(1); line(488,353,493,353);
				setcolor(15);line(488,369,493,369);
				do
				{ line(488,369,493,369);gotoxy(62,23);
				scanf("%d",&ic);
				if(ic<1||ic>M.NbColonnes())
				{
				setfillstyle(1,0);
				bar(488,351,625,369);
				}
				}while(ic<1||ic>M.NbColonnes());
				setcolor(1); line(488,369,493,369);
				setcolor(15);
				int e=M.Extraire(il,ic);
				char *s;
				gotoxy(50,24);
				outtextxy(430,390,"La valeur est :");
				outtextxy(500,390,itoa(e,s,10));
				getch();
				Graphisme();
				break;
			}
			case 3:
			{
				closegraph();
				Cadre();
				cprintf("Fleche Gauche %c Fleche Haut %c  Fleche Bas %c Fleche Droit %c Esc pour sortir ",17,24,25,16);
				gotoxy(32,1);
				cprintf("Matrice %d X %d",M.NbLignes(),M.NbColonnes());
				AffichageMatrice(M);
				InitGraph();Graphisme();
				break;
			}
			case 4:
			{
				setfillstyle(1,0);
				bar(20,140,610,460);
				BAR();
				settextstyle(SMALL_FONT,0,6);
				outtextxy(120,320,"Addition matricielle");
				outtextxy(121,320,"Addition matricielle");
				MatriceCreuse M1(M.NbLignes(),M.NbColonnes());
				settextstyle(SMALL_FONT,0,5);
				outtextxy(300,350,"Assigner un ‚lement pour la 2Šme matrice ?(O/N)");
				char r;
				r=getch();
				while(r==111)
				{
					int il,ic,iv;
					setfillstyle(1,0);
					bar(20,335,610,460);
					settextstyle(SMALL_FONT,0,5);
					outtextxy(458,348,"Ligne :");
					outtextxy(450,363,"Colonne :");
					outtextxy(454,378,"Valeur :");
					do
					{ line(488,353,493,353);gotoxy(62,22);
					scanf("%d",&il);
					if(il<1||il>M.NbLignes())
					{
					setfillstyle(1,0);
					bar(488,335,625,353);
					}
					}while(il<1||il>M.NbLignes());
					setcolor(1); line(488,353,493,353);
					setcolor(15);line(488,369,493,369);
					do
					{ line(488,369,493,369);gotoxy(62,23);
					scanf("%d",&ic);
					if(ic<1||ic>M.NbColonnes())
					{
					setfillstyle(1,0);
					bar(488,351,625,369);
					}
					}while(ic<1||ic>M.NbColonnes());
					setcolor(1); line(488,369,493,369);
					setcolor(15);line(488,387,493,387);
					gotoxy(62,24);scanf("%d",&iv);
					M1.Assigner(il,ic,iv);
					settextstyle(SMALL_FONT,0,5);
					outtextxy(300,410,"Assigner autre ‚l‚ment ?(O/N)");
					r=getch();
				}
				M=M+M1;
				closegraph();
				Cadre();
				cprintf("Fleche Gauche %c Fleche Haut %c  Fleche Bas %c Fleche Droit %c Esc pour sortir ",17,24,25,16);
				gotoxy(25,1);
				cprintf("Resultat de l'addition : Matrice %d X %d",M.NbLignes(),M.NbColonnes());
				AffichageMatrice(M);
				InitGraph();Graphisme();
				break;
			}
			case 5:
			{
				setfillstyle(1,0);
				bar(20,140,610,460);
				BAR();
				settextstyle(SMALL_FONT,0,6);
				outtextxy(140,320,"Multiplication matricielle");
				outtextxy(141,320,"Multiplication matricielle");
				Multiplication(M);
				InitGraph();Graphisme();
				break;
			}
			case 6:
			{
				exit(-1);
				break;
			}
		}
	}
	else if (c==72)
	{
		if (pos>1) pos--; else pos=6;
	}
	else if (c==80)
	{
		if (pos<6) pos++; else pos=1;
	}
   }
   closegraph();
   return 0;
}