xishujuzhen.txt

写一个以十字链表为存储结构的稀疏矩阵相乘的程序。 (1) 采用三元组输入的形式

/*to operate two matrixs*/

#include"stdio.h"
#include"stdlib.h"
#include"conio.h"
#include"time.h"
#include"string.h"

/*to define the structure of matrix*/

typedef int elemtype;
typedef struct nodetype
{
  elemtype val;
  int row,col;
  struct nodetype *down,*right,*next;
}nodetype;

/*to initiate linklist*/

void initiate(int m,int n,nodetype *hm)
{
  nodetype *p,*q;
  int s,i;

  if(m>n)
    s=m;
  else
    s=n;
  hm->row=m;
  hm->col=n;
  hm->val=0;
  p=hm;
  for(i=0;i<s;i++)
  {
    q=(nodetype *)malloc(sizeof(nodetype));
    if(!q)
    {
      printf("Allocation Error!\n");
      exit(1);
    }
    q->row=0;
    q->col=0;
    q->right=q;
    q->down=q;
    q->val=i+1;
    q->next=q;
    p=q;
  }
  p->next=hm;
  return;
}

/*to link linklist*/
void link(int r,int c,int v,nodetype *hm)
{
  nodetype *p, *q,*head;
  p=(nodetype *)malloc(sizeof(nodetype));
  if(!p)
  {
    printf("Allocation Error!\n");
    exit(1);
  }
  p->row=r;
  p->col=c;
  p->val=v;
  head=hm->next;
  while((head->val!=r)&&(head!=hm))
    head=head->next;
  if(head==hm)
    printf("No this position!\n");
  else
  {
    q=head->right;
    while((q!=head)&&(q->col<c))
      q=q->right;
    p->right=q->right;
    q->right=p;
  }
  head=hm->next;
  while((head->val!=c)&&(head!=hm))
  head=head->next;
  if(head==hm)
    printf("No this position!\n");
  else
  {
    q=head->down;
    while((q!=head)&&(q->row<r))
    q=q->down;
    p->down=q->down;
    q->down=p;
  }
 return;
}

/*to get element*/

elemtype get(int r,int c,nodetype *hm)
{
  nodetype *p,*head;
  head=hm->next;
  while(head->val!=r)
    head=head->next;
  p=head->right;
  while((p!=head)&&(p->col!=c))
  p=p->right;
  if(p->col==c)
    return p->val;
  else
    return 0;
}

/*to create linklist*/
void create(int m,int n,nodetype *hm)
{
  int r,c,v,i;
  for(i=0;i<5;i++)
    printf("\n");
  printf("Please enter the value of element(row,col,val)\n");
  printf("enter 0 to end...\n");
  printf("\n\t\t\tenter r(row):");
  scanf("%d",&r);
  while(r!=0)
  {
    if(r>m||r<0)
    {
      printf("Input error!\n");
      getch();
      system("cls");
      for(i=0;i<5;i++)
        printf("\n");
      printf("Please enter the value of element(row,col,val)\n");
      printf("enter 0 to end...\n");
      printf("\n\t\t\tenter r(row):");
      scanf("%d",&r);
   }
   printf("\n\t\tenter c(col):");
   scanf("%d",&c);
   if(c>n||c<0)
   {
     printf("Inpuut error!\n");
     getch();
     system("cls");
     for(i=0;i<5;i++)
       printf("\n");
      printf("Please enter the value of element(row,col,val)\n");
      printf("\n\t\t\tenter r(row):%d\n",r);
      printf("\t\t\tenter c(col):");
      scanf("%d",&c);
    }
    printf("\t\t\tenter v(val):");
    scanf("%d",&v);
    link(r,c,v,hm);
    system("cls");
    for(i=0;i<5;i++)
      printf("\n");
    printf("Please enter the value of element(row,col,val)\n");
    printf("enter 0 to end...\n");
    printf("\n\t\t\tenter r(row);");
    scanf("%d",&r);
   }
   return;
 }

 /*to display the matrix*/

 void display(int x,int m,int n,nodetype *hm)
 {
   int i,j;
   for(i=1;i<=m;i++)
   {
     printf("\n");
     gotoxy(x,12+i);
     printf("|%d",get(i,1,hm));
     for(j=2;j<=n;j++)
       printf("\t%d",get(i,j,hm));
     printf("|");
   }
   return;
}

/*the multiplication of two matrixs*/
void multiply(int m,int n,nodetype *pre,nodetype *matrix1,nodetype *matrix2)
{
  int i,j,k,s;
  elemtype v;
  if(m>n)
    s=m;
  else
    s=n;
  for(i=1;i<=m;i++)
  {
    for(j=1;j<=n;j++)
    {
      v=0;
      for(k=0;k<=s;k++)
        v+=get(i,k,matrix1)*get(k,j,matrix2);
      if(v!=0)
        link(i,j,v,pre);
    }
   }
  return;
}

/*to display some information when you enter into my system*/

void information1()
{
    /*进入系统时的提示*/
 window(10,7,70,24);
 textbackground(3);
 textcolor(1);
 clrscr();
 cprintf("\r\n                 Thanks for using this system");
 cprintf("\r\n\r\n                 the operation of two matrixs system");
 cprintf("\r\n\n\n                    desgined by liudali");
 cprintf("\r\n                    student ID:  class: ");
 cprintf("\r\n                    telephone:");
 cprintf("\r\n\r\n\n        to know more:");
 cprintf("\r\n        only to communicate with others for further study");
 textcolor(128+4);
 cprintf("\r\n\r\n\r\n\n                 press any key to continue...               ");
 getch();
 return;
}
/*to display some information when you quit this system*/

void information2()
{
  window(10,7,70,24);
  textbackground(0);
  textcolor(1);
  system("cls");
  cprintf("\r\n\r\n            welcome to use this system again");
  cprintf("\r\n\r\n\r\n\r\n");
  return;
}

/*to move sursor*/

int dis(int n,int x,int y,int type)
{
  char key;
  int in_key,h,o_y,flag;

  o_y=y;
  gotoxy(x-2,y);
  printf("->");
  do
  {
    flag=0;
    key=getch();
    in_key=atoi(&key);
    for(h=0;h<n;h++)
      if(in_key==h+1)
      {
        gotoxy(x-2,y);
        printf(" ");
        y=o_y+h;
        if(y<o_y)
          y+=n;
        if((o_y+n)<=y)
          y-=n;
        gotoxy(x-2,y);
        printf("->");
        flag=1;
       }
     if(flag)
       continue;
     if(key==13)
       return(y-(o_y-1));
     if(key==0)
     {
       key=getch();
       switch(key)
       {
         case 72:y=y-1;
                 gotoxy(x-2,y+1);
                 printf(" ");
                 if(y<o_y)
                   y+=n;
                 gotoxy(x-2,y);
                 printf("->");
                 break;
         case 80:y+=1;
                 gotoxy(x-2,y-1);
                 printf(" ");
                 if((o_y+n)<=y)
                   y-=n;
                   gotoxy(x-2,y);
                   printf("->");
                   break;
         case 75:if(type)
                    return(n);
                  else
                    return(n+1);
        }
      }
     }while(1);
}

/*the main menu function*/

int menu(int x,int y)
{
  time_t lt;
  lt=time(NULL);
  textcolor(14);
  textbackground(1);
  gotoxy(5,2);textcolor(14);printf("=======================================================");
  gotoxy(13,5);textcolor(14);printf("        the operation of two matrixs                       ");
  gotoxy(5,8);textcolor(14);printf("========================================================");
  gotoxy(5,21);textcolor(14);printf("-------------------------------------------------------------------");
  gotoxy(8,22);
  textcolor(8);
  printf(ctime(&lt));
  gotoxy(50,22);
  printf("desgined by Minglu Pan");

  gotoxy(5,23);printf("--------------------------------------------------------------------");

  gotoxy(x,y);

  printf("[1]--[enter the matrix]");
  gotoxy(x,y+1);
  textcolor(1);
  printf("[2]--[operation of matrixs]");
  gotoxy(x,y+2);

  printf("[3]--[display matrix]");
  gotoxy(x,y+3);
  printf("[4]--[exit]");
  return (dis(4,x,y,1));
}

/* main function*/
void main()
{
  char m,n;
  int m1,n1,m2,n2,i,flag=0;
  nodetype *result,*table1,*table2;
  information1();
  window(1,1,80,25);
  table1=(nodetype *)malloc(sizeof(nodetype));
  if(!table1)
  {
    printf("Allocation error!\n");
    exit(1);
  }
  table2=(nodetype *)malloc(sizeof(nodetype));
  if(!table2)
  {
    printf("Allocation error!\n");
    exit(1);
  }
  result=(nodetype *)malloc(sizeof(nodetype));
  if(!result)
  {
    printf("Allocation error!\n");
    exit(1);
  }
  do
  {
    system("cls");
    n=menu(25,12);
    switch(n)
    {
      case 1:textcolor(15);
             system("cls");
             for(i=0;i<2;i++)
               printf("\n");
             printf("please enter the first matrix\n");
             printf("\nenter r(row): ");
             scanf("%d",&m1);
             printf("\nenter c(col):");
             scanf("%d",&n1);
             system("cls");
             initiate(m1,n1,table1);
             system("cls");
             create(m1,n1,table1);
             system("cls");
             for(i=0;i<5;i++)
               printf("\n");
             printf("please enter the second matrix\n");
             printf("\nenter r(row):");
             scanf("%d",&m2);
             printf("\nenter c(col):");
             scanf("%d",&n2);
             system("cls");
             while(n1!=m2)
             {
               printf("enter error!\n");
               printf("the col in the frist matrix and the row in the second matrix must be equal!\n");
               getch();
               system("cls");
               for(i=0;i<5;i++)
                 printf("\n");
               printf("please enter the second matrix\n");
               printf("\nenter r(row):");
               scanf("%d",&m2);
               printf("\nenter c(col):");
               scanf("%d",&n2);
             }
               initiate(m2,n2,table2);
               create(m2,n2,table2);
               flag=1;
               system("cls");
               break;
       case 2:textcolor(1);
              system("cls");
              if(flag==1)
              {
                for(i=0;i<8;i++)
                   printf("\n");
                printf("the multiplication of matrixs is:");
                initiate(m1,n2,result);
                display(1,m1,n1,table1);
                gotoxy(n1*9-4,m1/2+13);
                printf("X");
                display(n1*9,m2,n2,table2);
                gotoxy((n1+n2)*9-4,m1/2+13);
                printf("=");
                multiply(m1,n2,result,table1,table2);

                display((n1+n2)*9,m1,n2,result);
                getch();
              }
              else
              {
                printf("\n\n\n\n\n\n\n\n\t\t\tthe matrix is not exit!");
                getch();
              }
             break;

       }
     }while(n!=3);
   information2();
   return;
}