稀疏矩陣鏈表實現(xiàn)——原創(chuàng)

1、大連理工大學實驗報告學院（系）： 專業(yè)： 班級： 姓 名： 學號： 組： _ 實驗時間： 實驗室： 實驗臺： 實驗名稱1、 實驗目的和要求Given two sparse matrices, design an algorithm to accomplish multiplication of sparse matrices, and implement it in C language by using circularly linked lists.Requirements:1) Use stream (file) to input sparse matrices instead of c

2、onsole I/O2) Analyze the time complexity of your algorithm3) Submit the document explaining your algorithm as well as the source code. 2、 實驗原理和內容headnodeentrynode1、 存儲結構： 在循環(huán)鏈表中，矩陣的每個非零元素對應著一個含有五個域的結點，這五個域分別為該非零元素在稀疏矩陣中的行號、列號、元素的數(shù)值以及兩個指針，其中一個指針指向同一列的下一個非零元素的結點，另一個指針指向同一行的右邊一個非零元素的結點。 循環(huán)結構：將每行的非零元素結點

3、鏈接成循環(huán)鏈表，又將每列的非零元素結點鏈接成循環(huán)鏈表，就構成了十字形的鏈接結構。 頭結點：對于每行、每列的循環(huán)鏈表都有一個空表頭結點hdnodei，以利于元素的插入和刪除運算。這些空表頭結點的行號、列號都標成零，以便和其它結點相區(qū)別。整個十字鏈表有一個總的空表頭結點node，在一般結點標以行號、列號之處，此結點是標出矩陣的行數(shù)m和列數(shù)n。有一個指針指向這個總的空表頭結點。 因各列、各行的空表頭結點中的行號和列號都是零，且每列空表頭結點只用到向下指針，每行空表頭結點只用到向右指針，故可將這組空表頭結點合用。 由于數(shù)值域也沒有用，可將空表頭結點的數(shù)值域改為一個指針域，將各個空表頭結點也鏈接成一個循

4、環(huán)鏈表。 e.g.稀疏矩陣M及其對應的十字鏈表如圖所示。2、 基本思想： 矩陣A與矩陣B相乘時，首先要保證A的列數(shù)與B的行數(shù)相等，矩陣的第i行與矩陣B的第j列相乘求和結果將存儲在矩陣C的ij位置上，而且第i行的第k個元素與對應的第j列的第k個元素才可以相乘。這樣A中的每個非零元素將與B中每個非零元素比較上述條件是否成立，進行矩陣乘法操作。3、 主要儀器設備Visual studio編程環(huán)境4、 實驗步驟與操作方法矩陣乘法流程圖頭結點設置 /構建循環(huán)鏈表框架，即頭結點的個數(shù)，和next指針的初始化 x=node_1->right for(i=0;i<node_1->u.entr

5、y.row;i+)/矩陣A每一行遍歷last=hdnodei;y=node_2->right; for(j=0;j<node_2->u.entry.col;j+) /矩陣B每一列遍歷，每進行一次循環(huán)產生一個新的結點 產生C的一個元素for(p=x->right;p!=x;p=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.

6、entry.value; temp->u.entry.value!=0 設置結點指針/頭結點的nextfree(temp) /相乘求和為0temp結點的righty=y->u.next;/B下一列x=x->u.next;/A下一行其他指針設置輸入輸出調用教材中mread、mwrite函數(shù)5、 實驗數(shù)據記錄和處理MATLAB中的結果：A= (1,4) -3 (1,5) -20 (2,5) 33B= (1,1) 33 (3,1) 35 (1,2) 4 (2,2) 15 (4,2) -9 (2,3) -5 (3,3) 13 (5,3) -4 (3,4) 28 (4,4) -12 (

7、4,5) 6 (5,5) 32C= (1,2) 27 (1,3) 80 (1,4) 36 (1,5) -658 (2,3) -132 (2,5) 10566、 實驗結果與分析運行的結果與預期值相符程序時間復雜度的分析：由于A中的每一個元素都會與B中的元素比較是否滿足相乘條件，因此設A中非零元素個數(shù)為num1，B中非零元素個數(shù)為num2，則時間復雜度為O（num1*num2)7、 討論、建議、質疑 在程序debug期間，運行結果總是與預期不符，檢查發(fā)現(xiàn)循環(huán)終止條件，例如 for(p=x->right;p!=x;p=p->right)這一循環(huán)，我起初寫成for(p=x->righ

8、t;p!=null;p=p->right)，這就忘了循環(huán)鏈表的意義，對于循環(huán)鏈表中的某一個結點，p對它進行p=p->right操作，最后會指向它自身，并不會指向空null。 程序優(yōu)化：先計算temp->u.entry.value，如果不等于0，則產生一個新的結點存儲該值，這樣就避免釋放temp的存儲空間了。 算法中設置了一個last結點，用于結點指針的設置，方便了很多。此外hdnodej->u.next->down=temp;hdnodej->u.next=temp;這兩個語句也很巧妙，用于down指針的設置，起到過渡的作用。 在此次實驗中我也熟悉了文件的操

9、作，學會如何用文件輸入數(shù)據，第一次使用文件輸入數(shù)據，相比鍵盤輸入要方便很多。 最重要的還是理解了鏈表這一數(shù)據結構，明白了鏈表是如何存儲數(shù)據，如何實現(xiàn)它的功能。附錄：程序#include <stdio.h>#include <stdlib.h>#include <malloc.h>#include <string.h>#include <math.h>using namespace std;#define MAX_SIZE 50typedef enum head,entry tagfield;typedef struct matrix_

10、node *matrix_pointer;typedef struct entry_node int row; int col; int value;typedef struct matrix_node matrix_pointer down; matrix_pointer right; tagfield tag; union matrix_pointer next; entry_node entry; u;matrix_pointer hdnodeMAX_SIZE;matrix_pointer new_node(void) matrix_pointer temp; temp=(matrix_

11、pointer)malloc(sizeof(matrix_node); /if(IS_FULL) return temp;matrix_pointer mread(void) int num_rows,num_cols,num_terms,num_heads,i; int row,col,value,current_row; matrix_pointer temp,last,node; printf("nEnter the number of rows,columns and number of nonzero terms:n"); scanf("%d%d%d&q

12、uot;,&num_rows,&num_cols,&num_terms); num_heads=(num_rows>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;

13、hdnodei->tag=head; hdnodei->right=temp; hdnodei->u.next=temp; current_row=0; last=hdnode0; for(i=0;i<num_terms;i+) / printf("Enter row,column and value:"); scanf("%d%d%d",&row,&col,&value); if(row>current_row) last->right=hdnodecurrent_row; current_r

14、ow=row; last=hdnoderow; temp=new_node(); temp->tag=entry; temp->u.entry.row=row; 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+) hd

15、nodei->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; return node;void mwrite(matrix_pointer node) int i; matrix_pointer temp,head=node->right; printf("The matrix by row,column,and value:nn&quo

16、t;); for(i=0;i<node->u.entry.row;i+) for(temp=head->right;temp!=head;temp=temp->right) printf("%d %d %dn",temp->u.entry.row,temp->u.entry.col,temp->u.entry.value); head=head->u.next; matrix_pointer mmult(matrix_pointer node_1,matrix_pointer node_2,matrix_pointer nod

17、e) int num_heads,i,j; matrix_pointer p,q,temp,x,y,last; if(node_1->u.entry.col!=node_2->u.entry.row) printf("ERROR!"); else node->u.entry.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-&g

18、t;u.entry.col:node_1->u.entry.row; 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; x=node_1->right; for(i=0;i<node_1->u.entry.row;i+) last=hdnodei; y=node_2->right

19、; 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=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.e