數(shù)據(jù)結(jié)構(gòu)
課程設(shè)計(jì)報(bào)告
設(shè)計(jì)題目：
n維矩陣乘法：A
B－1
專
業(yè)
計(jì)算機(jī)科學(xué)與技術(shù)
班
級(jí)
計(jì)本
學(xué)
生
學(xué)
號(hào)
指導(dǎo)教師
起止時(shí)間
2007.X.3-2007.X.11
學(xué)年第I
學(xué)期
一、具體任務(wù)
功能：
設(shè)計(jì)一個(gè)矩陣相乘的程序，首先從鍵盤輸入兩個(gè)矩陣a，b的內(nèi)容，并輸出兩個(gè)矩陣，輸出ab－1結(jié)果。
分步實(shí)施：
1.初步完成總體設(shè)計(jì)，搭好框架，確定人機(jī)對(duì)話的界面，確定函數(shù)個(gè)數(shù)；
2.完成最低要求：建立一個(gè)文件，可完成2維矩陣的情況；
3.進(jìn)一步要求：通過鍵盤輸入維數(shù)n。有興趣的同學(xué)可以自己擴(kuò)充系統(tǒng)功能。
要求：
1.界面友好，函數(shù)功能要?jiǎng)澐趾?/p>
2.總體設(shè)計(jì)應(yīng)畫一流程圖
3.程序要加必要的注釋
4.要提供程序測(cè)試方案
5.程序一定要經(jīng)得起測(cè)試，寧可功能少一些，也要能運(yùn)行起來，不能運(yùn)行的程序是沒有價(jià)值的。
二、軟件環(huán)境
Microsoft
Visual
C++
6.0
三、問題的需求分析
程序以二維數(shù)組作為矩陣的存儲(chǔ)結(jié)構(gòu)，通過鍵盤輸入矩陣維數(shù)n，動(dòng)態(tài)分配內(nèi)存空間，創(chuàng)建n維矩陣。矩陣建立后再通過鍵盤輸入矩陣的各個(gè)元素值；也可以通過文件讀入矩陣的各項(xiàng)數(shù)據(jù)（維數(shù)及各元素值）。
當(dāng)要對(duì)矩陣作進(jìn)一步操作（A*B或A*B^(-1)）時(shí)，先判斷內(nèi)存中是否已經(jīng)有相關(guān)的數(shù)據(jù)存在，若還未有數(shù)據(jù)存在則提示用戶先輸入相關(guān)數(shù)據(jù)。
當(dāng)要對(duì)矩陣進(jìn)行求逆時(shí)，先利用矩陣可逆的充要條件：|A|
!=
0
判斷矩陣是否可逆，若矩陣的行列式
|A|
=
=
0
則提示該矩陣為不可逆的；若
|A|
!=0
則求其逆矩陣，并在終端顯示其逆矩陣。
四、算法設(shè)計(jì)思想及流程圖
1．抽象數(shù)據(jù)類型
ADT
MatrixMulti{
數(shù)據(jù)對(duì)象：D
=
{a(I,j)|i
=
1,2,3,…,n;j
=
1,2,…,n;a(i,j)∈ElemSet,n為矩陣維數(shù)}
數(shù)據(jù)關(guān)系:
R
=
{Row,Col}
Row
=
{
<=
i
<=
n,1
<=
j
<=
n-1}
Col
=
{
<=
i
<=
n-1,1
<=
j
<=
n}
基本操作:
Swap(&a,&b);
初始條件：記錄a,b已存在。
操作結(jié)果：交換記錄a,b的值。
CreateMatrix(n);
操作結(jié)果：創(chuàng)建n維矩陣，返回該矩陣。
Input(&M);
初始條件：矩陣M已存在。
操作結(jié)果：從終端讀入矩陣M的各個(gè)元素值。
Print(&M)
初始條件：矩陣M已存在。
操作結(jié)果：在終端顯示矩陣M的各個(gè)元素值。
ReadFromFile();
操作結(jié)果：從文件讀入矩陣的相關(guān)數(shù)據(jù)。
Menu_Select();
操作結(jié)果：返回菜單選項(xiàng)。
MultMatrix(&M1,&M2,&R);
初始條件：矩陣M1，M2，R已存在。
操作結(jié)果：矩陣M1，M2作乘法運(yùn)算，結(jié)果放在R中。
DinV(&M,&V);
初始條件：矩陣M，V已存在。
操作結(jié)果：求矩陣M的逆矩陣,結(jié)果放入矩陣V中。
MatrixDeterm(&M,n);
初始條件：矩陣M已存在。
操作結(jié)果：求矩陣M的行列式的值。
}
ADT
MatrixMulti
2．矩陣求逆算法設(shè)計(jì)思想
算法采用高斯-約旦法（全選主元）求逆，主要思想如下：
首先，對(duì)于k從0到n-1作如下幾步：
①
從第k行、第k列開始的右下角子陣中選取絕對(duì)值最大的元素，并記住此元素所在的行號(hào)與列號(hào)，再通過行交換和列交換將它交換到主元素位置上。這一步稱為全選主元。
②
主元求倒：M(k,k)
=
/
M(k,k)
③
M(k,j)
=
M(k,j)
*
M(k,k)；j
=
0,1,…,n-1;j
!=
k
④
M(i,j)
=
M(i,j)
–
M(i,k)
*
M(k,j)；i,j
=
0,1,…,n-1;i,j!=k
⑤
M(i,k)
=
M(i,k)
*
M(k,k)，i
=
0,1…,n-1；i
!=
k
最后，根據(jù)在全選主元過程中所記錄的行、列交換的信息進(jìn)行恢復(fù)，恢復(fù)原則如下：
在全選主元過程中，先交換的行（列）后進(jìn)行恢復(fù)；原來的行（列）交換用列（行）交換來恢復(fù)。
3.矩陣行列式求值運(yùn)算算法設(shè)計(jì)思想
利用行列式的性質(zhì)：行列式等于它的任一行（列）各元素與其對(duì)應(yīng)的代數(shù)余子式乘積，即
D
=
∑a(i,k)*A(i,k)
;
k
=
1,2,…,n;
D
=
∑a(k,j)*A(k,j)
;
k
=
1,2,…,n;
再利用函數(shù)的遞歸調(diào)用法實(shí)現(xiàn)求其值。
4．各函數(shù)間的調(diào)用關(guān)系
Main()
ReadFromFile()
DinV()
Swap
()
Print()
Menu_Select()
MatrixDeterm()
CreateMatrix()
MultMatrix()
Input()
5.流程圖
否
否
是
否
是
是
否
是
否
否
是
開始
switch(Menu_Select())
case
1:
case
3:
case
2:
n
0
?
是
輸入矩陣維數(shù)n
輸入矩陣A,B
輸出矩陣維數(shù)n
system(“pause”);
通過鍵盤輸入需對(duì)哪個(gè)矩陣求逆,求出相應(yīng)該的逆陣,并顯示求得的逆陣system(“pause”);若矩陣不可逆則返回主菜單
case
4:
R=A*B并顯示矩陣R
system(“pause”);
case
5:
是
否
是
R=A*B^(-1)顯示矩陣R
system(“pause”);若B不可逆,則返回主菜單
case
6:
從指定文件中讀入矩陣數(shù)據(jù)
case
0:
exit(0);
結(jié)果
否
五、源代碼
#include
#include
#include
#include
#include
#include
#define
YES
#define
NO
0
typedef
float
ElemType;
ElemType
**A;
//矩陣A
ElemType
**B;
//矩陣B
ElemType
**R;
//矩陣R,用于存放運(yùn)算結(jié)果
ElemType
**V;
//矩陣V,存放逆矩陣
int
n=0;
//矩陣維數(shù)
int
flag=-1;
//標(biāo)記
void
swap(ElemType
*a,ElemType
*b)
//交換記錄a,b的值
{
ElemType
c;
c=*a;
*a=*b;
*b=c;
}
ElemType
**CreateMatrix(int
n)
//創(chuàng)建n維矩陣,返回該矩陣
{
int
i,j;
ElemType
**M;
M
=
(ElemType
**)malloc(sizeof(ElemType
*)*n);
if(M
==
NULL)
exit(1);
for(i=0;i { *(M+i) = (ElemType *)malloc(sizeof(ElemType)*n); for(j=0;j *(*(M+i)+j) = 0; } return M; } ElemType MatrixDeterm(ElemType **M,int n) /*遞歸法求n維矩陣行列式的值,返回運(yùn)算結(jié)果*/ { int i,j,k,l,s; ElemType **T1; ElemType **T2; T1=CreateMatrix(n); T2=CreateMatrix(n); ElemType u; ElemType value=0; //運(yùn)算結(jié)果 for(i=0;i { for(j=0;j { T1[i][j]=M[i][j]; T2[i][j]=M[i][j]; } } if(n==2) //若為2維矩陣,則直接運(yùn)算并返回運(yùn)算結(jié)果 { value=T2[0][0]*T2[1][1]-T2[0][1]*T2[1][0]; return value; } else { for(j=0;j //將矩陣的行列式以第一行展開 { u=T1[0][j]; for(i=1,l=0;i //求矩陣行列式的余子式M(0,j) { for(k=0,s=0;k { if(k==j) continue; else { T2[l][s]=T1[i][k]; s++; } } l++; } value=value+u*((int)pow(-1,j))*MatrixDeterm(T2,n-1); /*行列式等于某一行的各個(gè)元素與其代數(shù)余子式的乘積之和*/ } return value; } } int DinV(ElemType **M,ElemType **V) /*全選主元法求矩陣M的逆矩陣,結(jié)果存入矩陣V中*/ { int i,j,k; ElemType d; ElemType u; int *JS,*IS; JS=(int *)malloc(sizeof(int)*n); IS=(int *)malloc(sizeof(int)*n); u=MatrixDeterm(M,n); //返回矩陣A的行列式值 if(u==0) return -1; for(i=0;i for(j=0;j V[i][j]=M[i][j]; for(k=0;k { d=0; for(i=k;i //找出矩陣M從M[k][k]開始絕對(duì)值最大的元素 { for(j=k;j { if(fabs(V[i][j])>d) { d=fabs(V[i][j]); //d記錄絕對(duì)值最大的元素的值 /*把絕對(duì)值最大的元素在數(shù)組中的行、列坐標(biāo)分別存入IS[K],JS[K]*/ IS[k]=i; JS[k]=j; } } } if(d+1.0 == 1.0) return 0; //所有元素都為0 if(IS[k] != k) /*若絕對(duì)值最大的元素不在第k行,則將矩陣IS[K]行的元素與k行的元素相交換*/ for(j=0;j swap(&V[k][j],&V[IS[k]][j]); if(JS[k]!=k) /*若絕對(duì)值最大的元素不在第k列,則將矩陣JS[K]列的元素與k列的元素相交換*/ for(i=0;i swap(&V[i][k],&V[i][JS[k]]); V[k][k]=1/V[k][k]; //絕對(duì)值最大的元素求倒 for(j=0;j /*矩陣M第k行除元素M[k][k]本身外都乘以M[k][k]*/ if(j!=k) V[k][j]=V[k][j]*V[k][k]; for(i=0;i /*矩陣除第k行的所有元素與第k列的所有元素外,都拿本身減去M[i][k]*M[k][j],其中i,j為元素本身在矩陣的位置坐標(biāo)*/ if(i!=k) for(j=0;j if(j!=k) V[i][j]=V[i][j]-V[i][k]*V[k][j]; for(i=0;i /*矩陣M第k列除元素M[k][k]本身外都乘以-M[k][k]*/ if(i!=k) V[i][k]=-V[i][k]*V[k][k]; } for(k=n-1;k>=0;k--) /*根據(jù)上面記錄的行IS[k],列JS[k]信息恢復(fù)元素*/ { for(j=0;j if(JS[k]!=k) swap(&V[k][j],&V[JS[k]][j]); for(i=0;i if(IS[k]!=k) swap(&V[i][k],&V[i][IS[k]]); } free(IS); free(JS); return 0; } void MultMatrix(ElemType **M1,ElemType **M2,ElemType **R) /*矩陣M1乘M2 結(jié)果存入矩陣R*/ { int i,j,k; for(i=0;i { for(j=0;j { R[i][j]=0; } } for(i=0;i { for(j=0;j { for(k=0;k { R[i][j]=R[i][j]+M1[i][k]*M2[k][j]; } } } } void Input(ElemType **M) //輸入矩陣M的各個(gè)元素值 { int i,j; char str[10]; char c=＇A＇; if(flag==1) c=＇B＇; system(“cls“); printf(“＼n＼n輸入矩陣%c(%d*%d)＼n“,c,n,n); for(i=0;i { for(j=0;j { scanf(“%f“,*(M+i)+j); } } flag=1; gets(str); //吸收多余的字符 } void Print(ElemType **M) //顯示矩陣M的各個(gè)元素值 { int i,j; printf(“＼t“); for(i=0;i { for(j=0;j { printf(“ %.3f“,M[i][j]); } puts(““); printf(“＼t＼t“); } } int Menu_Select() { char c; do{ system(“cls“); puts(“＼t＼t*************n維矩陣乘法器*************“); puts(“＼t＼t| 1.通過鍵盤輸入各項(xiàng)數(shù)據(jù) |“); puts(“＼t＼t| 2.顯示矩陣A,B |“); puts(“＼t＼t| 3.矩陣求逆,并顯示逆矩陣 |“); puts(“＼t＼t| 4.求矩陣運(yùn)算A*B,并顯示運(yùn)算結(jié)果 |“); puts(“＼t＼t| 5.求矩陣運(yùn)算A*B^(-1),并顯示運(yùn)算結(jié)果|“); puts(“＼t＼t| 6.從文件讀入矩陣A,B與維數(shù)n |“); puts(“＼t＼t| 0.退出 |“); puts(“＼t＼t***************************************“); printf(“＼t＼t請(qǐng)選擇(0-6):“); c=getchar(); }while(c<＇0＇||c>＇6＇); return (c-＇0＇); } void ReadFromFile() //從指定文件讀入矩陣的維數(shù)及矩陣各元素的值 { int i,j; FILE *fp; if((fp=fopen(“tx.txt“,“r“))==NULL) { puts(“無法打開文件！!“); system(“pause“); exit(0); } fscanf(fp,“%d“,&n); //讀入矩陣維數(shù) A=CreateMatrix(n); //創(chuàng)建矩陣A B V R B=CreateMatrix(n); V=CreateMatrix(n); R=CreateMatrix(n); for(i=0;i //讀入矩陣A { for(j=0;j { fscanf(fp,“%f“,&A[i][j]); } } for(i=0;i //讀入矩陣A { for(j=0;j { fscanf(fp,“%f“,&B[i][j]); } } puts(“＼n＼n讀文件成功“); fclose(fp); flag=1; } int main() { int i; char c,h; char str[10]; for(;;) { switch(Menu_Select()) { case 1: flag=-1; for(;;) { system(“cls“); printf(“＼n＼n＼t矩陣維數(shù)n:“); scanf(“%d“,&n); gets(str); if(n>0) break; else { printf(“＼n＼t輸入有誤,請(qǐng)重新輸入!＼n“); puts(““); system(“pause“); } } A=CreateMatrix(n); B=CreateMatrix(n); V=CreateMatrix(n); R=CreateMatrix(n); Input(A); Input(B); break; case 2: system(“cls“); if(flag==-1) { puts(“＼n＼n＼t不存在任何矩陣數(shù)據(jù),請(qǐng)先輸入數(shù)據(jù)“); system(“pause“); break; } puts(“＼n“); printf(“＼tA = “); Print(A); puts(“＼n“); printf(“＼tB = “); Print(B); puts(““); system(“pause“); break; case 3: system(“cls“); if(flag==-1) { puts(“＼n＼n＼t不存在任何矩陣數(shù)據(jù),請(qǐng)先輸入數(shù)據(jù)“); system(“pause“); break; } for(;;) { printf(“＼n＼n＼t輸入需要求逆的矩陣(A/B):“); h=getchar(); c=getchar(); //h=getchar(); if(c==＇A＇||c==＇a＇) { i=DinV(A,V); if(i==-1) { puts(“＼n＼n＼t矩陣A的行列式等于0,不可逆!“); system(“pause“); break; } printf(“＼tA = “); Print(A); puts(“＼n“); printf(“A^(-1) = “); Print(V); puts(““); system(“pause“); break; } else if(c==＇B＇||c==＇b＇) { i=DinV(B,V); if(i==-1) { puts(“＼n＼n＼t矩陣B的行列式等于0,不可逆!“); system(“pause“); break; } printf(“＼tB = “); Print(B); puts(“＼n“); printf(“B^(-1) = “); Print(V); puts(““); system(“pause“); break; } else puts(“＼n＼n＼t輸入有誤,請(qǐng)重新輸入!＼n“); } break; case 4: system(“cls“); if(flag==-1) { puts(“＼n＼n＼t不存在任何矩陣數(shù)據(jù),請(qǐng)先輸入數(shù)據(jù)“); system(“pause“); break; } MultMatrix(A,B,R); printf(“＼n＼n＼tA*B = “); Print(R); puts(““); system(“pause“); break; case 5: system(“cls“); if(flag==-1) { puts(“＼n＼n＼t不存在任何矩陣數(shù)據(jù),請(qǐng)先輸入數(shù)據(jù)“); system(“pause“); break; } i=DinV(B,V); if(i==-1) { puts(“＼n＼n＼t矩陣B的行列式等于0,不可逆!“); system(“pause“); break; } MultMatrix(A,V,R); printf(“＼n＼nA*B^(-1) = “); Print(R); puts(““); system(“pause“); break; case 6: system(“cls“); ReadFromFile(); puts(““); system(“pause“); break; case 0: puts(“＼t＼t正常退出“); exit(0); break; } } return 0; } 六、運(yùn)行結(jié)果 1．主界面： 2．輸入6，回車，從文本文件tx.txt中讀入矩陣數(shù)據(jù)： 3．回車，回到主菜單界面；輸入2回車，顯示從文件讀入的矩陣數(shù)據(jù)： 4．回車，回到主菜單界面；輸入3回車，對(duì)指定矩陣求逆：（由于這里矩陣A是不可逆的，因此僅以矩陣B為例） 5．回車，回到主菜單界面；輸入4回車，求矩陣運(yùn)算A*B： 6．回車回到主菜單界面，輸入5回車，求A*B^(-1)的值： 7．回車回到主菜單界面，輸入0回車，退出程序；如果需要自定矩陣維數(shù)及各元素值，請(qǐng)利用主菜單里的1號(hào)功能自行輸入數(shù)據(jù)，再進(jìn)行以上幾種運(yùn)算操作。 七、收獲及體會(huì) 通過這次課程設(shè)計(jì)，讓我再次復(fù)習(xí)了線性代數(shù)里矩陣的相關(guān)知識(shí)，比如n維矩陣的求逆、矩陣可逆的充分必要條件（|A| ！= 0）、矩陣與矩陣的乘法運(yùn)算、行列式求值方法等。同樣的，還讓我復(fù)習(xí)了大量C語言里有關(guān)數(shù)組的一些重要概念，比如多維數(shù)組的動(dòng)態(tài)分配問題、數(shù)組與指針的關(guān)系等。 記得在這個(gè)學(xué)期新開設(shè)的單片機(jī)基礎(chǔ)課上，吳濤老師曾多次強(qiáng)調(diào)，讓我們一定要經(jīng)常鍛煉自己的編程能力，他常對(duì)我們說：“編程是思維的體操?！北M管我在這方面的能力 和實(shí)力非常得有限，也遠(yuǎn)遠(yuǎn)不及班上的其他同學(xué)，但我通過這次課程設(shè)計(jì)充分體會(huì)到了這句話的精華。 電腦程序作為人體大腦思維的延伸，程序的功能也會(huì)因?yàn)榇竽X思維的不斷完善而變得更加強(qiáng)大，所以我決定今后要加強(qiáng)在這方面的鍛煉和學(xué)習(xí)，以此來激勵(lì)自己不斷前進(jìn)！ 八、參考文獻(xiàn) 《數(shù)據(jù)結(jié)構(gòu)（C語言版）》 嚴(yán)蔚敏，吳偉民 編著 清華大學(xué)出版社 《C語言程序設(shè)計(jì)》 洪維恩 編著 中國鐵道出版社 《C語言程序設(shè)計(jì)教程》 譚浩強(qiáng) 張基溫 唐永炎 編著 高等教育出版社 《工程數(shù)學(xué)——線性代數(shù) 第四版》 同濟(jì)大學(xué)應(yīng)用數(shù)學(xué)系 編 高等教育出版社 計(jì)本 2007-12
點(diǎn)擊咨詢