Code:/********************************************** ** @copyright reserved by the author **author:-----------Xuxuelong **data:-------------20009/12/26 **IDE:--------------visual c++ 6.0 **major:------------08-CS-software engineering **email address:[email protected] **attention:--------if you find a bug in the **------------------operation ,just email me! **********************************************/ #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <windows.h> #define OK 1 #define ERROR 0 typedef struct list {//node structure int row;//row subscript int colum;//colum subscript int value;//value of the node struct list *right;//the next element have the same row struct list *down;//the next element have the same colum }node,*element; typedef struct link {//cross list structure int row_size;//row size of the matrix int colum_size;//colum size of the matrix int non_zero_amount;//the number of non zero element element *rhead;//the base of the row element *chead;//the base of the colum }crosslist; /********function definition********/ int init_matrix(crosslist &one) {//initialization one.row_size=0; one.colum_size=0; one.non_zero_amount=0; one.rhead=NULL; one.chead=NULL; return OK; }//init_matrix int creat_matrix(crosslist &one) {//assignment int i;//as count in the loop element news,temp; /*input row size ,colum size and non zero amount*/ printf("Input the row size of the matrix:"); scanf("%d",&one.row_size); printf("Input the colum size of the matrix:"); scanf("%d",&one.colum_size); printf("Input the non zero amount of the matrix:"); scanf("%d",&one.non_zero_amount); /*allocate memory and the first memory not use*/ one.rhead=(element*)malloc(sizeof(element)*(one.row_size+1)); assert(one.rhead!=NULL);//assert have space one.chead=(element*)malloc(sizeof(element)*(one.colum_size+1)); assert(one.chead!=NULL); /*set all the pointer to NULL*/ for(i=1;i<=one.row_size;i++) one.rhead[i]=NULL; for(i=1;i<=one.colum_size;i++) one.chead[i]=NULL; printf("/**************************************/\n"); /*assignment*/ for(i=1;i<=one.non_zero_amount;i++) {//insert all non zero elements /*creat a new node and assign value to it*/ news=(element)malloc(sizeof(node)); assert(news!=NULL); do {//insure the row script is valid printf("Input the script of the row:"); scanf("%d",&news->row); }while(news->row>one.row_size); do {//insure the colum script is valid printf("Input the script of the colum:"); scanf("%d",&news->colum); }while(news->colum>one.colum_size); printf("Input the value of the node:"); scanf("%d",&news->value); /*insert the node to the rear of the list*/ /*row link*/ if(!one.rhead[news->row]) {//if there's no node in the row news->right=NULL; one.rhead[news->row]=news; } else { for(temp=one.rhead[news->row];temp->right!=NULL;temp=temp->right) NULL; news->right=temp->right; temp->right=news; } /*colum link*/ if(!one.chead[news->colum]) { news->down=NULL; one.chead[news->colum]=news; } else { for(temp=one.chead[news->colum];temp->down!=NULL;temp=temp->down) NULL; news->down=temp->down; temp->down=news; } printf("/**************************************/\n"); }//for return OK; }//creat_matrix int print_matrix(crosslist &one) {//print out the info of matrix one element temp; int count; for(count=1;count<=one.row_size;count++) { if(!one.rhead[count]) continue; else { for(temp=one.rhead[count];temp!=NULL;temp=temp->right) { printf("\t\t%d\t\t\t%d\t\t\t%d\n",temp->row,temp->colum,temp->value); printf("\t\t-------------------------------------------------\n"); Sleep(500); } }//else }//for return OK; }//print_matrix int add_matrix(crosslist one,crosslist two,crosslist &three) {//add matrix one and two then get three /*assert the two matrices are valid to add*/ assert(one.row_size==two.row_size&&one.colum_size==two.colum_size); int i,j;//as count in the loop element insert;//nodes to insert element pone,ptwo; element prow;//the last node of a row element *pcolum;//array that contains the last node of every colum /*assignment*/ three.row_size=one.row_size; three.colum_size=one.colum_size; three.non_zero_amount=0; /*allocate memroy*/ three.rhead=(element*)malloc(sizeof(element)*(three.row_size+1)); assert(three.rhead!=NULL); three.chead=(element*)malloc(sizeof(element)*(three.colum_size+1)); assert(three.chead!=NULL); pcolum=(element*)malloc(sizeof(element)*(three.colum_size+1)); assert(pcolum!=NULL); /*initialization*/ for(i=1;i<=three.row_size;i++) three.rhead[i]=NULL; for(i=1;i<=three.colum_size;i++) three.chead[i]=NULL; for(i=1;i<=three.colum_size;i++) pcolum[i]=NULL; /*start addition in row order*/ for(i=1;i<=one.row_size;i++) { pone=one.rhead[i]; ptwo=two.rhead[i]; while(pone!=NULL&&ptwo!=NULL) {//both have nodes in the same row if(pone->colum<ptwo->colum) {//node in one's colum is smaller insert=(element)malloc(sizeof(node)); assert(insert!=NULL); /*assignment*/ insert->row=i; insert->colum=pone->colum; insert->value=pone->value; insert->right=NULL; /*pointer to the next one*/ pone=pone->right; /*the non zero number of three increment*/ three.non_zero_amount++; } else if(pone->colum>ptwo->colum) {//node in two is smaller insert=(element)malloc(sizeof(node)); assert(insert!=NULL); insert->row=i; insert->colum=ptwo->colum; insert->value=ptwo->value; insert->right=NULL; ptwo=ptwo->right; three.non_zero_amount++; } else if(pone->value+ptwo->value!=0) {//the result of the addition is nonzero insert=(element)malloc(sizeof(node)); assert(insert!=NULL); insert->row=i; insert->colum=ptwo->colum; insert->value=pone->value+ptwo->value; insert->right=NULL; pone=pone->right; ptwo=ptwo->right; three.non_zero_amount++; } else {//the addition is zero pone=pone->right; ptwo=ptwo->right; continue; } /*insert into three and link row*/ if(three.rhead[i]==NULL) three.rhead[i]=prow=insert; else { prow->right=insert; prow=insert; } /*colum link*/ if(three.chead[insert->colum]==NULL) three.chead[insert->colum]=pcolum[insert->colum]=insert; else { pcolum[insert->colum]->down=insert; pcolum[insert->colum]=insert; } }//while /*insert the other nodes in one*/ while(pone!=NULL) { insert=(element)malloc(sizeof(node)); assert(insert!=NULL); insert->row=i; insert->colum=pone->colum; insert->value=pone->value; insert->right=NULL; pone=pone->right; three.non_zero_amount++; /*row link*/ if(three.rhead[i]==NULL) three.rhead[i]=prow=insert; else { prow->right=insert; prow=insert; } /*colum link */ if(three.chead[insert->colum]==NULL) three.chead[insert->colum]=pcolum[insert->colum]=insert; else { pcolum[insert->colum]->down=insert; pcolum[insert->colum]=insert; } }//while /*insert the other nodes in two*/ while(ptwo!=NULL) { insert=(element)malloc(sizeof(node)); assert(insert!=NULL); insert->row=i; insert->colum=ptwo->colum; insert->value=ptwo->value; insert->right=NULL; ptwo=ptwo->right; three.non_zero_amount++; /*row link*/ if(three.rhead[i]==NULL) three.rhead[i]=prow=insert; else { prow->right=insert; prow=insert; } /*colum link */ if(three.chead[insert->colum]==NULL) three.chead[insert->colum]=pcolum[insert->colum]=insert; else { pcolum[insert->colum]->down=insert; pcolum[insert->colum]=insert; } }//while }//for three.non_zero_amount=three.non_zero_amount; for(j=1;j<=three.colum_size;j++) {//set the nonzero pcolum to null if(pcolum[j]!=NULL) pcolum[j]->down=NULL; } /*free pcolum's memory*/ free(pcolum); return OK; }//add_matrix int multi_matrix(crosslist one,crosslist two,crosslist &three) {//multiply crosslist one and two and the result put in three /*assert the two matrices are valid to multiply*/ assert(one.colum_size==two.row_size); int i,j;//as count in the loop int value;//temp total value element insert;//the node to insert into three element pone,ptwo;//use in traverse the node in one and two element prow,pcolum;//mark the last row and colum node /*assignment*/ three.row_size=one.row_size; three.colum_size=two.colum_size; three.non_zero_amount=0; /*allocate memroy*/ three.rhead=(element*)malloc(sizeof(element)*(three.row_size+1)); assert(three.rhead!=NULL); three.chead=(element*)malloc(sizeof(element)*(three.colum_size+1)); assert(three.chead!=NULL); /*initialization*/ for(i=1;i<=three.row_size;i++) three.rhead[i]=NULL; for(i=1;i<=three.colum_size;i++) three.chead[i]=NULL; /*start multiplication*/ for(i=1;i<=one.row_size;i++) {//traverse every row of nodes of one for(j=1;j<=two.colum_size;j++) {//traverse every colum of nodes of two pone=one.rhead[i]; ptwo=two.chead[j]; value=0; while(pone!=NULL&&ptwo!=NULL) {//row and colum are not empty if(pone->colum==ptwo->row) {//is valid to multiply value+=pone->value*ptwo->value; pone=pone->right;//to the next node node in same row ptwo=ptwo->down;//point to the next node in same colum while(pone!=NULL&&ptwo!=NULL) {//for the emtire row and colum if(pone->colum==ptwo->row) { value+=pone->value*ptwo->value; pone=pone->right; ptwo=ptwo->down; } else if(pone->colum>ptwo->row) { ptwo=ptwo->down; continue; } else { pone=pone->right; continue; } }//while if(value==0) break; insert=(element)malloc(sizeof(node)); assert(insert!=NULL); insert->row=i; insert->colum=j; insert->value=value; insert->right=NULL; insert->down=NULL; three.non_zero_amount++; /*insert into c and row link*/ if(three.rhead[i]==NULL) three.rhead[i]=prow=insert; else { prow->right=insert; prow=insert; } /*colum link*/ if(three.chead[j]==NULL) three.chead[j]=pcolum=insert; else { pcolum->down=insert; pcolum=insert; } }//if (colum==row) else if(pone->colum>ptwo->row) { ptwo=ptwo->down; continue; } else { pone=pone->right; continue; } }//while }//inner for }//outter for return OK; }//multi_matrix int trans_matrix(crosslist &one) {//just print the matrix in colum order element temp; for(int count=1;count<=one.colum_size;count++) {//print in colum order if(!one.chead[count]) continue; else {//traverse the elements in one for(temp=one.chead[count];temp!=NULL;temp=temp->down) {//the row script equal to the colum script printf("\t\t%d\t\t\t%d\t\t\t%d\n",temp->colum,temp->row,temp->value); printf("\t\t-------------------------------------------------\n"); Sleep(1000); } }//else }//for return OK; }//trans_matrix /*****the main function*****/ /*****the main function*****/ int main(void) { /*declare three matrix*/ crosslist one,two,three; int choice;//as a mark of selection char flag;//selection mark while(OK) { system("cls"); system("color a4"); system("mode con cols=80 lines=400"); system("title #Crosslist To Deal With Sparse Matrix#"); printf("\t@*************************************************************@\n"); putchar('\n'); printf("\t\t %c---Sparse-Matrix's--Application-System---%c\n",2,2); putchar('\n'); printf("\t@*************************************************************@\n"); printf("\t$*************************************************************$\n"); printf("\t\t %c----------------Functions----------------%c\n",2,2); putchar('\n'); printf("\t\t %c-----------------------------------------%c\n",2,2); printf("\t\t %c <1>sparse--matrix---addition %c\n",2,2); printf("\t\t %c-----------------------------------------%c\n",2,2); printf("\t\t %c <2>sparse--matrix---multiplication %c\n",2,2); printf("\t\t %c-----------------------------------------%c\n",2,2); printf("\t\t %c <3>sparse--matrix---transposition %c\n",2,2); printf("\t\t %c-----------------------------------------%c\n",2,2); printf("\t\t %c <4>exit-----quit--the--system %c\n",2,2); printf("\t\t %c-----------------------------------------%c\n",2,2); putchar('\n'); printf("\t\t %c-----------Crosslist Row First-----------%c\n",2,2); printf("\t$*************************************************************$\n"); printf("\t\t!!Tips:if you want to break just press Ctrl +C\n"); printf("\t$*************************************************************$\n"); printf("Please choose a choice :(1--4)\n"); fflush(stdin); printf("Your choice is:"); scanf("%d",&choice); switch(choice) { case 1: printf("\t<addition>\n"); putchar('\n'); printf("\t<Initialization>\n"); init_matrix(one); putchar('\n'); printf("\t<Creat the first matrix>\n"); creat_matrix(one); putchar('\n'); printf("Print the first matrix\n"); printf("\t\tRow\t\t\tColum\t\t\tValue\n"); printf("\t\t-------------------------------------------------\n"); print_matrix(one); printf("\t<Initialization>\n"); init_matrix(two); putchar('\n'); printf("\t<Creat the second matrix>\n"); creat_matrix(two); putchar('\n'); printf("Print the second matrix\n"); printf("\t\tRow\t\t\tColum\t\t\tValue\n"); printf("\t\t-------------------------------------------------\n"); print_matrix(two); /*add the two matrix*/ printf("Add the two matrix\n"); init_matrix(three); putchar('\n'); add_matrix(one,two,three); printf("The result is below:\n"); Sleep(1000); print_matrix(three); system("pause"); break; case 2: printf("\t<multiplication>\n"); putchar('\n'); printf("\t<Initialization>\n"); init_matrix(one); putchar('\n'); printf("\t<Creat the first matrix>\n"); creat_matrix(one); putchar('\n'); printf("Print the first matrix\n"); printf("\t\tRow\t\t\tColum\t\t\tValue\n"); printf("\t\t-------------------------------------------------\n"); print_matrix(one); printf("\t<Initialization>\n"); init_matrix(two); putchar('\n'); printf("\t<Creat the second matrix>\n"); creat_matrix(two); putchar('\n'); printf("Print the second matrix\n"); printf("\t\tRow\t\t\tColum\t\t\tValue\n"); printf("\t\t-------------------------------------------------\n"); print_matrix(two); /*multiply the two matrix*/ printf("Multiply the two matrix\n"); init_matrix(three); multi_matrix(one,two,three); printf("The result is below:\n"); Sleep(1000); print_matrix(three); system("pause"); break; case 3: printf("\t<transposation>\n"); printf("\n"); printf("\t<Initialization>\n"); init_matrix(one); putchar('\n'); printf("\t<Creat the matrix>\n"); creat_matrix(one); printf("Print the matrix:\n"); printf("\t\tRow\t\t\tColum\t\t\tValue\n"); printf("\t\t-------------------------------------------------\n"); print_matrix(one); /*transpase the matrix*/ printf("Transpase the matrix\n"); putchar('\n'); printf("The result is below:\n"); Sleep(1000); trans_matrix(one); system("pause"); break; case 4: printf("Are you sure to quit the system<Y/N>?\n"); fflush(stdin); scanf("%c",&flag); if(flag=='y'||flag=='Y'||flag=='\n') { printf("\t\t%c-------%c-------%c-------%c-------%c\n",2,2,2,2,2); putchar('\n'); printf("\t\t(^_^)Thanks For Using This!(^_^)\n"); putchar('\n'); printf("\t\t%c-------%c-------%c-------%c-------%c\n",2,2,2,2,2); putchar('\n'); Sleep(2000); exit(OK); } else { printf(" continue \n"); Sleep(2000); } break; default:printf("Please input a valid choice from 1 to 4!\n"); Sleep(2000); break; }//switch }//while return OK; }
