1、數(shù)據(jù)結(jié)構(gòu)作業(yè)報告n矩陣的n次方運算報告折半查找報告姓名：江海強班級：070921班學(xué)號：07092007上機時間：2010-9-29報告時間：2010-9-10摘要1.實驗?zāi)康谋緦嶒炛饕亲屛覀兞私夂瘮?shù)的調(diào)用與返回，理解遞歸函數(shù)的執(zhí)行過程，學(xué)會利用遞歸函數(shù)解決實際問題。2.實驗方法本程序利用全局數(shù)組變量bnn來統(tǒng)籌整個程序，有一個主函數(shù)和一個子函數(shù)，其中子函數(shù)為矩陣換算的函數(shù)，也作為遞歸函數(shù)。而遞歸就是本程序的主要實驗方法。本程序也定義了一個全局指針變量*mid，也是有一個主函數(shù)和一個子函數(shù)，其中子函數(shù)為折半查找的函數(shù)，也作為遞歸函數(shù)。而遞歸也就是本程序的主要實驗方法。3.實驗結(jié)果由運行出來的

2、結(jié)果可以看出，即使為一次方，此矩陣運算的結(jié)果與實際運算得到的結(jié)果完全是一樣，所以此程序是正確的，成功的。由運行出來的結(jié)果可以看出，折半查找所找到的數(shù)的位置經(jīng)過驗證也是正確、無誤的。即使輸入要查找的數(shù)不在數(shù)組中，則程序會輸出error來說明查找失敗。故此程序也是正確的，成功的。注：這兩個程序是用c語言編輯完成的。其中代表的是n矩陣的n次方運算的程序設(shè)計，代表的是折半查找的程序設(shè)計，如果沒有特別說明，以下的都是代表這樣的意思。內(nèi)容一問題重述給出一個n階矩陣a，利用遞歸編程快速計算矩陣a的n次冪給出一組按從小到大排序的數(shù)組，利用遞歸編程實現(xiàn)折半查找，查找出所要求查找的數(shù)所在的位置 二算法描述這兩個程

3、序除了運用一些條件語句，判斷語句之外，主要運用了遞歸算法。本程序中的子函數(shù)的復(fù)雜度為o(n2+n2+n3),即為o(n3)，而遞歸算法運用了子函數(shù)n-1次，所以復(fù)雜度為(n-1)o(n3)。本程序中折半查找的平均查找長度為asl，要考慮到是否查找成功，則開始輸入n階矩陣ann結(jié)束調(diào)用子函數(shù)jzhs（）輸出運用for循環(huán)計算矩陣相乘再自身調(diào)用子函數(shù)jzhs（）再調(diào)用直到調(diào)用了子函數(shù)n-1次為止再運用for循環(huán)計算矩陣相乘結(jié)束輸出開始直到調(diào)用到*mid=key或者key不存在數(shù)組中輸入數(shù)組an和所要查找的數(shù)key自身調(diào)用子函數(shù)search(a,key,lo,(mid-)自身調(diào)用子函數(shù)search(

4、a,key,(mid+),hi)調(diào)用子函數(shù)seach（） 是 *midkey?否運用for語句賦值*mid，比較*mid與key的大小先不討論*mid=key 三變量說明全局變量n代表的是矩陣為n階，全局變量n代表的是n階矩陣的n次方，而ann則代表的是n階矩陣。全局變量n代表的是數(shù)組an的個數(shù)，key是所要查找的數(shù)，*lo、*hi和*mid分別代表數(shù)組的頭、尾和中間指針，并且隨著運算而變化。四函數(shù)與思路說明本程序分為一個主函數(shù)和一個子函數(shù)，其中子函數(shù)為jzhs()子函數(shù)。其中jzhs()子函數(shù)將主函數(shù)中調(diào)入的n階矩陣，通過三個for循環(huán)，計算出n階矩陣的二次方。再將得出的矩陣和原來的矩陣自身

5、調(diào)用，輸入到j(luò)zhs()子函數(shù)中，即得到n階矩陣的三次方，利用這樣的遞歸進行運算直到算出矩陣的n次方為止。本程序也分為一個主函數(shù)和一個子函數(shù)，其中子函數(shù)為seach()子函數(shù)。其中seach()子函數(shù)將主函數(shù)調(diào)入的數(shù)組，通過指針指向數(shù)組的頭和尾，求出*mid指向中間數(shù)組。若*midkey，則調(diào)用自身函數(shù)search(a,key,lo,(mid-)，直到查找到所要查的數(shù)或者要查找的數(shù)不在數(shù)組中為止。：1.第一次運行結(jié)果:從小到大排序好的數(shù)列為:1 2 3 4 5 6 7 8 9要查找的數(shù)是:4查找到的數(shù)是:4其存儲位置為:0012ff602.第二次運行結(jié)果:從小到大排序好的數(shù)列為:1 2 3 4

6、 5 6 7 8 9要查找的數(shù)是:9查找到的數(shù)是:9其存儲位置為:0012ff743.第三次運行結(jié)果:從小到大排序好的數(shù)列為:1 2 3 4 5 6 7 8 9要查找的數(shù)是:11error 五程序執(zhí)行結(jié)果：1.第一次運行結(jié)果：輸入的3階矩陣為:1 1 11 1 11 1 13階矩陣的4次冪的矩陣為:27 27 2727 27 2727 27 272.第二次運行結(jié)果:輸入的3階矩陣為:1 0 00 1 00 0 13階矩陣的4次冪的矩陣為:1 0 00 1 00 0 13.第三次運行結(jié)果:輸入的3階矩陣為:1 2 34 5 67 8 93階矩陣的1次冪的矩陣為:1 2 34 5 67 8 9六結(jié)

7、論由上面的運行結(jié)果可以看出，矩陣運算結(jié)果是正確的，折半查找也是正確的。在矩陣運算程序中，只要在全局變量n，n修改一下數(shù)據(jù)就可以改變矩陣的階數(shù)和次方數(shù)，同樣的，在折半查找中，改變數(shù)組的個數(shù)可以通過改變?nèi)肿兞縩,這樣子會方便許多。七編程中遇到的問題以及解決方法在編程過程中，剛開始對矩陣的相乘不太熟悉，導(dǎo)致一些小錯誤，后來自己歸納矩陣相乘的規(guī)律很快就解決了這個問題。當(dāng)編好程序，運行成功，也遇上了一個問題，就是當(dāng)n=1時，即矩陣為一次矩陣，不用運算，反而輸出錯誤。后來在原來的程序上增加了幾條語句，調(diào)試幾次就通過了。在剛剛開始的編程過程中，我把輸出放在了子函數(shù)處，導(dǎo)致輸出結(jié)果好幾次，后來引入了全局指針

8、*mid變量，把輸出語句放回主函數(shù)處，從而解決了問題。編好程序之后，才發(fā)現(xiàn)沒有把查找失敗的情況算進去，后來就把子函數(shù)由void型修改為int型，通過return 1來說明查找成功，輸出儲存地址，return 0來說明查找失敗。八附錄：#include#define n 3#define n 4void jzhs(int xnn,int ynn,int z);int bnn=0;void main()int i,j,ann;printf(輸入的%d階矩陣為:n,n);for(i=0;in;i+)for(j=0;jn;j+)scanf(%d,&aij); for(i=0;in;i+)for(j=0

9、;jn;j+)bij=aij;jzhs(a,a,n);printf(%d階矩陣的%d次冪的矩陣為:n,n,n);for(i=0;in;i+)for(j=0;jn;j+)printf(%dt,bij);printf(n);void jzhs(int xnn,int ynn,int z)int i,j,k,cnn,tnn;if(z=1) ;elsefor(i=0;in;i+)for(j=0;jn;j+)cij=yij; tij=xij; for(i=0;in;i+) for(j=0;jn;j+)bij=0;z-; for(i=0;in;i+) for(j=0;jn;j+) for(k=0;kn;k

10、+) bij+=tik*ykj; jzhs(b,c,z);：#include #define n 9int search(int x,int key,int *p,int *q);int *mid=0;void main()int i,t,key,an; printf(從小到大排序好的數(shù)列為:n);for(i=0;in;i+) scanf(%d,&ai); printf(要查找的數(shù)是:);scanf(%d,&key); int *lo=&a0,*hi=&an-1;t=search(a,key,lo,hi);if(t=1)printf(查找到的數(shù)是:%dn其存儲位置為:%pn,*mid,mid);if(t=0)printf(errorn);int search(int a,int