crosslist to cope with sparse matrix

This is a discussion on crosslist to cope with sparse matrix within the C Programming forums, part of the General Programming Boards category; Code: /********************************************** ** @copyright reserved by the author **author:-----------Xuxuelong **data:-------------20009/12/26 **IDE:--------------visual c++ 6.0 **major:------------08-CS-software engineering **email address:----xuxuelong0214@126.com **attention:--------if you find ...

  1. #1
    Registered User
    Join Date
    Nov 2009
    Location
    wuhan ,hubei ,china
    Posts
    7

    crosslist to cope with sparse matrix

    Code:
     /**********************************************
    **		@copyright reserved by the author
    **author:-----------Xuxuelong
    **data:-------------20009/12/26
    **IDE:--------------visual c++ 6.0
    **major:------------08-CS-software engineering
    **email address:----xuxuelong0214@126.com
    **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;
    }

  2. #2
    Registered User
    Join Date
    Nov 2009
    Location
    wuhan ,hubei ,china
    Posts
    7
    please develop my code!

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    We don't develop your code. You have the wrong idea of what we do.

    If you have a specific problem with your program, we try to help you fix it.

    And we don't work through email. This is a forum. Using email defeats the whole purpose of having a forum.

    Good luck with your program, Kiss.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C - access violation
    By uber in forum C Programming
    Replies: 2
    Last Post: 07-08-2009, 02:30 PM
  2. Genrate sparse matrix - C99
    By anirban in forum C Programming
    Replies: 0
    Last Post: 06-11-2008, 12:44 AM
  3. Matrix Help
    By HelpmeMark in forum C++ Programming
    Replies: 27
    Last Post: 03-06-2008, 05:57 PM
  4. What is a matrix's purpose in OpenGL
    By jimboob in forum Game Programming
    Replies: 5
    Last Post: 11-14-2004, 12:19 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21