數(shù)據(jù)結(jié)構(gòu)試驗-系數(shù)矩陣

1、大連理工大學(xué)實驗預(yù)習(xí)報告學(xué)院（系）：電信專業(yè):電創(chuàng)班級:姓名：學(xué)號：組：實驗時間：實驗室：實驗臺：指導(dǎo)教師簽字：成績：實驗名稱Multiplicationofsparsematrices一、實驗?zāi)康暮鸵螅ㄒ唬嶒災(zāi)康模▍⒖嫉谒恼拢〨iventwosparsematrices,designanalgorithmandimplementitinClanguagebyusingcircularlylinkedlists.已知兩個系數(shù)矩陣，設(shè)計一個算法并用循環(huán)鏈表在C語言中實現(xiàn)。（二卜實驗要求Requirements:1） Usestream（file）toinputsparsematricesi

2、nsteadofconsoleI/O2） Analyzethetimecomplexityofyouralgorithm3） Submitthedocumentexplainingyouralgorithmaswellasthesourcecode.要求：1）用數(shù)據(jù)流（文件）來輸入稀疏矩陣而非鍵盤輸入。2）分析算法的時間復(fù)雜度。3）提交的文檔中說明你的算法和源代碼。二、實驗原理解題思路：N階矩陣A±B=Aij土B皿其中i和j三（0,N）。矩陣A的轉(zhuǎn)置為Aij與Aji的值交換?；玖鞒堂枋觯壕仃嚨募?，減和乘實際上就是數(shù)組的加，減和乘。加法和減法只需利用循環(huán)將數(shù)組的每個元素進行加減即可，

3、N階矩陣A士B=Aij士Bij其中i和j三（0,N）。而轉(zhuǎn)置即對稱交換數(shù)組中的元素，利用cji與aij相等，輸出數(shù)組c即可。大連理工大學(xué)實驗報告學(xué)院(系)：電信專業(yè):電創(chuàng)班級:1501姓名：陳曉牛津?qū)W號:201588011組:實驗時間：2017/4/18實驗室：實驗臺指導(dǎo)教師簽字：成績：實驗名稱Multiplicationofsparsematrices一、算法分析矩陣，其實就是一個二維數(shù)組，橫豎排列的，比如int56,就是一個矩陣，表示有5行6列。只有當(dāng)矩陣A的列數(shù)與矩陣B的行數(shù)相等時AXB才有意義。一個mxn的矩陣a(m,n)左乘一個n冷的矩陣b(n,p),會得到一個nixp的矩陣c(m,

4、p)。左乘：又稱前乘，就是乘在左邊(即乘號前),比如說,A左乘E即AE。在計算機中，一個矩陣實際上就是一個二維數(shù)組。一個m行n列的矩陣與一個n行p列的矩陣可以相乘，得到的結(jié)果是一個m行p列的矩陣，其中的第i行第j列位置上的數(shù)為第一個矩陣第i行上的n個數(shù)與第二個矩陣第j列上的n個數(shù)對應(yīng)相乘后所得的n個乘積之和。二、關(guān)鍵代碼及注釋FILE*fp;matrix_pointerhdnodeMAX_SIZE;/讀取文件中的矩陣structmatrix_nodematrix_pointerdown;matrix_pointerright;tagfieldtag;/定義矩陣三、運行結(jié)果997卜。Eb打lIB

5、lb工3Ws艙bMm3Hn3Mfej*:11-1366&JUMJ卜3-HdJ»3248卜0n弋而川IJRlHdII弧1加fiApuTl。陽111，1"。IHiOHpr守a»Tkj1于toconE.iEi.M.電K樗那:四、代碼#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<string.h>#include<math.h>#include<iostream>usingnamespacestd;#defineMA

6、X_SIZE50typedefenumhead,entrytagfield;typedefstructmatrix_node*matrix_pointer;structentry_nodeintrow;intcol;intvalue;structmatrix_nodematrix_pointerdown;matrix_pointerright;tagfieldtag;unionmatrix_pointernext;entry_nodeentry;u;FILE*fp;matrix_pointerhdnodeMAX_SIZE;matrix_pointernew_node(void)一一matrix

7、_pointertemp;temp=(matrix_pointer)malloc(sizeof(matrix_node);/if(IS_FULL)returntemp;)matrix_pointermread(void)(.intnum_rows,num_cols,num_terms,num_heads,i;introw,col,value,current_row;matrix_pointertemp,last,node;fscanf(fp,"%d%d%d”,&num_rows,&num_cols,&num_terms);num_heads=(num_rows

8、>num_cols)?num_rows:num_cols;node=new_node();node->tag=entry;node->u.entry.row=num_rows;node->u.entry.col=num_cols;if(!num_heads)node->right=node;else(for(i=0;i<num_heads;i+)(.temp=new_node();hdnodei=temp;hdnodei->tag=head;hdnodei->right=temp;hdnodei->u.next=temp;)current_

9、row=0;last=hdnode0;for(i=0;i<num_terms;i+)(./printf("Enterrow,columnandvalue:");fscanf(fp,"%d%d%d",&row,&col,&value);if(row>current_row)(.last->right=hdnodecurrent_row;current_row=row;last=hdnoderow;)temp=new_node();temp->tag=entry;temp->u.entry.row=row

10、;temp->u.entry.col=col;temp->u.entry.value=value;last->right=temp;last=temp;hdnodecol->u.next->down=temp;hdnodecol->u.next=temp;)last->right=hdnodecurrent_row;for(i=0;i<num_cols;i+)hdnodei->u.next->down=hdnodei;for(i=0;i<num_heads-1;i+)hdnodei->u.next=hdnodei+1;hd

11、nodenum_heads-1->u.next=node;node->right=hdnode0;)returnnode;)voidmwrite(matrix_pointernode).inti;matrix_pointertemp,head=node->right;printf("?:n");for(i=0;i<node->u.entry.row;i+)for(temp=head->right;temp!=head;temp=temp->right)printf("%d%d%dn",temp->u.ent

12、ry.row,temp->u.entry.col,temp->u.entry.value);head=head->u.next;)matrix_pointermmult(matrix_pointernode_1,matrix_pointernode_2,matrix_pointernode)intnum_heads,i,j;matrix_pointerp,q,temp,x,y,last;if(node_1->u.entry.col!=node_2->u.entry.row)printf("ERROR!");elsenode->u.entr

13、y.row=node_1->u.entry.row;node->u.entry.col=node_2->u.entry.col;num_heads=(node_2->u.entry.col>node_1->u.entry.row)?node_2->u.entry.col:node_1->u.entry.row;if(!num_heads)node->right=node;elsefor(i=0;i<num_heads;i+)temp=new_node();hdnodei=temp;hdnodei->tag=head;hdnode

14、i->right=temp;hdnodei->u.next=temp;x=node_1->right;for(i=0;i<node_1->u.entry.row;i+)last=hdnodei;y=node_2->right;for(j=0;j<node_2->u.entry.col;j+)temp=new_node();temp->tag=entry;temp->u.entry.row=0;temp->u.entry.col=0;temp->u.entry.value=0;for(p=x->right;p!=x;p

15、=p->right)for(q=y->down;q!=y;q=q->down)if(p->u.entry.col=q->u.entry.row)temp->u.entry.value+=p->u.entry.value*q->u.entry.value;)if(temp->u.entry.value!=0)/printf("%d",temp->u.entry.value);temp->u.entry.row=i;temp->u.entry.col=j;last->right=temp;last=t

16、emp;last->right=hdnodei;hdnodej->u.next->down=temp;hdnodej->u.next=temp;)elsefree(temp);y=y->u.next;)x=x->u.next;)for(i=0;i<node->u.entry.col;i+)hdnodei->u.next->down=hdnodei;for(i=0;i<num_heads-1;i+)hdnodei->u.next=hdnodei+1;hdnodenum_heads-1->u.next=node;node->right=hdnode0;)/returnnode;)returnnode;intmain()fp=fopen("1.txt","r");matrix_pointernode_1,node_2,node_3,node