#include <stdio.h>
#include<stdlib.h>
#include <conio.h>

struct nodo
{ int ir;
 int jc;
 double aij;
 struct nodo *sgr;
 struct nodo *sgc;
};
typedef struct nodo NODO;
#define NNODO (NODO*)malloc(sizeof(NODO))
#define ISIN(x,a,b)(x<a?0:x>b?0:1)
#define IREN(pc,i)while(pr->ir!=i)pr=pr->sgr
#define JCOL(pc,j)while(pc->jc!=j)pc=pc->sgc
#define ZERO 0.0
/*Genera la matriz cero de n renglones por m columnas*/
NODO*MatCero(int n, int m)
{NODO *pm, *ip;
 int i;
 pm= NNODO;
 pm->ir=n; pm->jc=m; pm->aij=0.0; pm-> sgc=pm; pm->sgr=pm;
 for (i=0;i<m;i++)
 {ip=NNODO;
   ip->ir=0;
   ip->jc=m-i-1;
   ip-> sgc=pm->sgc;
   ip->sgr=ip;
   pm->sgc=ip;
 }
 for(i=0;i<n;i++)
 {ip=NNODO;
   ip->ir=n-i-1;
   ip->jc=0;
   ip-> sgr=pm->sgr;
   ip->sgc=ip;
   pm->sgr=ip;
 }
 return pm;
 }

NODO *InsNodo();

 /*Deposita en la entrada (i,j) de la matriz el valor x*/
 NODO *DepAij(NODO *pm, int i, int j, double x)
 {NODO *pr, *pra, *prb, *pc,*pca,*pcb;
  if(ISIN(i,0,(pm->ir-1))&& ISIN(j,0,(pm->jc-1)))
  {pr=pm->sgr;
   IREN(pr,i);
   pca=pr; pcb=pca->sgc;
   while(pcb!=pr&&j<pcb->jc)
   {pca=pcb;
    pcb=pcb->sgc;
   }
   if(pcb==pr||j>pcb->jc)return(InsNodo(pm,pca,i,j,x));
   if(x==0.0)
   {pca->sgc=pcb->sgc;//borra nodo en la lista renglon
   pc=pm->sgc;
   JCOL(pc,j);pra= pc; prb=pra->sgr;
   while(prb!=pcb)
   {pra=prb;
    prb=prb->sgr;
   }
   pra->sgr=prb->sgr;//borra nodo en la lista columna
   free(prb);
   return (NULL);
   }
  }
  else
  printf("Indice ilegal en la llamada de la funcion  de DepAij!\n");
  }
  NODO*InsNdc(NODO*pr,NODO*pn, int i)
  {pn->sgr=pr->sgr;
   pr->sgr=pn;
   return(pn);
  }
//Inserat nodo en la lista renglon y columna
NODO *InsNodo(NODO *pm,NODO *pn, int i, int j, double x)
{NODO *pr, *pc,*pra,*prb;
 pr=NNODO;
 pr->ir=i;pr->jc=j;pr->aij=x;
 pr->sgc=pn->sgc;
 pn->sgc=pr;
 pc=pm->sgc;
 JCOL(pc,j);
 pra=pc;prb=pra->sgr;
 while(prb!=pc&&i<prb->ir)
 {pra=prb;
  prb=prb->sgr;
 }
 return(InsNdc(pra,pr,i));
}
//Recupera el valor almacenado en la posicion (i,j) de la matriz
double RecAij(NODO *pm, int i, int j)
{NODO *pr, *pc;
if(ISIN(i,0,pm->ir-1)&&ISIN(j,0,pm->jc-1))
{pr=pm->sgr;
IREN(pr,i);
pc=pr->sgc;
while(pc!=pr)
{if(pc->jc==j)return (pc->aij);
 if(j<pc->jc)pc=pc->sgc;else return(ZERO);
 }
 return (ZERO);
 }
 else
 printf("Indice ilegal en la llamada de la funcion RecAij!\n");
 }
 //Imprime una matriz
 void PrtMat(NODO *pm)
 {NODO *pr, *pc;
  printf("%d\t%d\n", pm->ir, pm->jc);
  pr=pm->sgr;
  while (pr!=pm)
  {pc=pr->sgc;
  while(pc!=pr)
  {printf("%d\t%d\t%f\n", pc->ir, pc->jc, pc->aij);
   pc=pc->sgc;
   }
   pr=pr->sgr;
   }
 }


NODO *MatIdn(int n)
{int i;
NODO *pm;
pm=MatCero(n,n);
for(i=0;i<n;i++)
DepAij(pm,i,i,1.0);
return(pm);
}


NODO *SumaMat(NODO *pa,NODO *pb)
{NODO *ipra,*ipraa,*iprb,*iprbb,*pca,*pcb,*pcc,*pc,*pc1,*pc2,*pc3;
int i,j,n,m;
double suma=0.0;
char a[]="Dim A",b[]="Dim B",c[]="Dim C",d[]="Entrada Aij Mat A",e[]="Entrada Aij Mat B";
char g[]="A + B";
if(pa->ir==pb->ir && pa->jc==pb->jc)
{
pc=MatCero(pa->ir,pb->jc);
printf("%s\t%s\t%s\n",a,b,c);
printf("%d%d\t%d%d\t%d%d\n",pa->ir,pa->jc,pb->ir,pb->jc,pc->ir,pc->jc);
pc1=pa->sgr;
pc2=pb->sgr;
pc3=pc->sgr;
while (pc1!=pa && pc2!=pb)
{pca=pc1->sgc;
 pcb=pc2->sgc;
 pcc=pc3->sgc;

while (pca!=pc1 && pcb!=pc2)
{suma=pca->aij+pcb->aij;
printf("%d\t%d\t%f\t%s\n",pca->ir,pca->jc,pca->aij,d);
printf("%d\t%d\t%f\t%s\n",pcb->ir,pcb->jc,pcb->aij,e);
printf("%d\t%d\t%f\t%s\n",pcc->ir,pcc->jc,suma,g);
pca=pca->sgc;
pcb=pcb->sgc;
pcc=pcc->sgc;

}
pc1=pc1->sgr;
pc2=pc2->sgr;
pc3=pc3->sgr;
}
}
else if(pca->jc<pcb->jc)
{
DepAij(pc,pca->ir,pca->jc,pca->aij);
pca++;
}
else
{DepAij(pc,pcb->ir,pcb->jc,pcb->aij);
pcb++;
}
if (pca==pc1)
while (pc2!=pcb)
{
DepAij(pc,pcb->ir,pcb->jc,pcb->aij);
pcb++;
}
}

main()
{ NODO *pm,*pm2,*sum1,*sum2;
int i,c;
double *b,x[]={1,1,1};
clrscr();
sum1=MatIdn(3);
sum2=MatCero(3,3);
DepAij(sum2,0,0,4);
DepAij(sum2,1,1,4);
DepAij(sum2,2,2,4);


pm=SumaMat(sum1,sum2);
//PrtMat(pm);
exit(EXIT_SUCCESS);
getch();
}