1、課程設計任務書學院信息科學與工程專業通信工程學生姓名學號設計題目靜態查 卜找類模板的1勺設計與實現內容及要求:在非數值運算問題中，數據存儲量一般很大，為了在大量信息中找到某些 值，就需要用到查找技術?；诰€性表的查找具體可分為順序查找，折半查找 和分塊查找。折半查找又分為遞歸和非遞歸兩類。要求采用 C+語言，建立一維數組數據結構的模板類，使一維數組中的數 據元素可以是 char, int, float 等多種數據類型，并對數組元素進行靜態查找。主 要完成如下功能：（1）實現數組數據的輸入和輸出；（2）對數組進行順序查找；（3）對有序數組進行折半查找（遞歸算法）；（4）對有序數組進行折半查找（非

2、遞歸算法）；（5） 將每種查找功能作為類的成員函數實現，編寫主函數測試上述查找 功能。進度安排:第 17 周：分析題目，查閱課題相關資料，進行類設計、算法設計;第 18 周：程序的設計、調試與實現；第 19 周：程序測試與分析，撰寫課程設計報告，進行答辯驗收。指導教師（簽字）：學院院長（簽字）年月日年月日1 需求分析-0 - 2 算法基本原理-0 -3 類設計 - 2 -4 詳細設計 - 2 -4.1 類的接口設計 -2-4.2 類的實現- 4 -4.3 主函數設計 - 85 DOS 界面程序運行結果及分析 - 9 -5.1 程序運行結果 -9-5.2 運行結果分析 -116 基于 MFC 的

3、圖形界面程序開發 - 11 -6.1 基于 MFC 的圖形界面程序設計 -116.2 程序測試 -146.3 MFC 程序編寫總結 - 157 參考文獻 - 15 -1 需求分析（1）查找運算在實際生活中使用頻率高，如帳戶查詢、訂票查詢及股市查 詢等，一些實時查詢系統的效率也格外重要。（2）假定被查找的對象是由一組結點（元素）組成的表或文件，而每個結 點則由若干個數據項組成。所謂的查找，即給定一個待查數據值，在表的指定 數據項中查找等于待查數據值的結點。若找到，則查找成功，返回該結點的信 息或該結點在表中的位置；否則查找失敗，返回相關提示信息。（3）靜態查找表查找方式包括順序查找、折半查找（遞

4、歸和非遞歸）。2 算法基本原理1 順序查找在查找的存儲方式中，順序表是最簡單的一種。建立在其上的順序查找是從 表的一端開始，順序掃描，依次將掃描到的元素和待查數值比較。若當前元素 的數據值與待查數據值相等，則查找成功；若掃描結束后，仍未找到數據值等 于待查數據值的元素，則查找失敗。順序查找實例如下圖：*順序表的順序查找 *當前順序表如下：0 1 2 3 471 68 74 17 20 請輸入要查找的元素： 74 查找經過如下： 第一趟順序查找的結果為：0 1 2 3 471 68 74 17 20T第二趟順序查找的結果為：0 1 2 3 471 68 74 17 20T第三趟順序查找的結果為：

5、 0 1 2 3 4 71 68 74 17 20查找結果：你要查找的元素 74 是第 3 個元素2 折半查找（1）非遞歸折半查找折半查找是一種效率較高的查找方法，但要求作用于有序順序表。其基本 思想是：最初把整個有序順序表作為查找區域，每次用待查數據值與查找區域 中間元素比較，分以下三種情況處理：如果待查數據值等于中間元素，則查找 成功；如果待查數據值小于中間元素，則繼續在前半區域查找；如果待查數據 值大于中間元素，則繼續在后半區域查找。查找過程中，每次與中間元素比較，就可以確定查找是否成功。如不成 功，則當前查找區域縮小一半，這樣查找區域逐漸縮小。如果查找區域最終縮 小到不存在，則表示查找

6、不到這個數據。非遞歸折半查找實例：當前有序順序表如下：0 1 2 3 4 5 69 18 26 27 29 32 40 請輸入要查找的元素： 26 查找經過如下：第 1 趟折半查找結果為：0 1 2 3 4 5 69 18 26 27 29 32 40T第 2 趟折半查找結果為：0 1 2 3 4 5 69 18 26 27 29 32 40T第 3 趟折半查找結果為：0 1 2 3 4 5 69 18 26 27 29 32 40T查找結果：你要查找的元素 26 是第 3 個元素（2）遞歸折半查找3 類設計從上面的算法分析可以看到，本設計面臨的計算問題的關鍵是矩陣運算。 可以定義一個矩陣類

7、Matrix 作為基類，然后由矩陣類派生出線性方程組類 Linequ。矩陣類*非遞歸折半查找*Matrix 只處理 n 溝類型的方陣，方陣用一個一維數組來存放， 矩陣類 Matrix 的數據成員包括數組的首地址和n,矩陣類 Matrix 的功能有設置矩陣的值 SetMatrix （）和顯示矩陣 PrintM （）等。從問題的需要來看,線性方程組類 Linequ 的數據除了由矩陣類 Matrix 繼承 過來用于存放系數矩陣 A 的成員外,還應該包括存放解向量 x 和方程右端向量 b 的數組首地址。線性方程組類 Linequ 的主要操作有設置 SetLinequ（ ）、顯示 PrintL（ ）、求

8、解 Solve（ ）及輸出方程的解 showX （ ）?？梢酝ㄟ^定義線性 方程組類 Linequ 的新增成員函數來實現這些針對方程組求解的功能。矩陣類 Matrix 和線性方程組類 Linequ 的組成及相互關系如圖 1 所示。圖1 Matrix類和Linequ類的派生關系的UML圖形表示在線性方程組的求解過程中，在線性方程組類Linequ 的成員函數 Solve 中需要訪問基類矩陣類 Matrix 的數據成員,利用公有繼承方式派生,同時將 Matrix 類中的數據成員的訪問控制設置為保護類型。這樣，經過公有派生之 后，基類的保護成員在派生類中依然是保護成員，可以被派生類的成員函數訪 問。4

9、詳細設計整個程序分為三個獨立的文檔， Linequ.h 文件中包括矩陣類 Matrix 和線性 方程組類 Linequ 的聲明， Linequ.cpp 文件中包括這兩個類的成員函數實現文 件； ma in.cpp 文件包括程序的主函數，主函數中定義了一個類Linequ 的對象，通過這個對象求解一個四元線性方程組。4.1類的接口設計/Linequ.h 文件，實現類的聲明#include #include using n amespace stdclass Matrix/基類 Matrix 聲明public:/外部接口Matrix(int dims=2)。/構造函數Matrix ()。/析構函數v

10、oid SetMatrix (double *rmax)。 /矩陣賦初值。class Linequ:public Matrix/公有派生類 Linequ 聲明。經過公有派生， Linequ 類獲得了除構造函數、析構函數之外的 Matrix 類的全部成員，由于基類的成員是公有和保護類型，因此在派生類中的成員函數 中，基類繼承來的成員全部可以訪問，而對于建立 Linequ 類對象的外部模塊來 講，基類的保護成員是無法訪問的。通過保護訪問類型和公有的繼承方式，實 現了基類 Matrix 的數據的有效共享和可靠保護。在程序中，方程的系數矩陣、 解以及右端項全部采用了動態內存分配技術，這些工作都是在基類

11、、派生類的構造函數中完成，它們的清理工作在析構函數中完成。void PrintM （）。protected:int index。double* MatrixA 。/顯示矩陣/方陣的行數 /矩陣存放數組首地址public:Linequ（int dims=2）。Linequ（）。void SetLinequ （double *a, double *b） 。 voidPrintL （） int Solve（）。void ShowX （）private:double *sums。/外部接口/構造函數/析構函數/方程賦值double *solu。/顯示方程/全選主元高斯消去法求解方程/顯示方程的解/私有

12、數據/方程右端項/方程的解4.2類的實現/Linequ.cpp 文件，類實現#include linequ.h/包含類的聲明頭文件/Matrix 類的實現void Matrix:SetMatrix (double *rmatr)/ 設置矩陣for (int i=0。iindex*index。i+)MatrixAi=rmatri 。/矩陣成員賦初值Matrix:Matrix ( int dims)/矩陣 Matrix 類的構造函數index=dims。/矩陣行數賦值MatrixA=new doubleindex*index 。/動態內存分配Matrix:Matrix ()/矩陣 Matrix 類

13、的析構函數delete MatrixA 。/內存釋放void Matrix:PrintM ()/顯示矩陣元素coutThe Matrix is:endl 。for (int i=0。 iindex。 i+)for (int j=0。 jindex。 j+) cout* (MatrixA+i*index+j ) 。coutendl。/派生類 Linequ 的實現Linequ:Linequ (int dims) :Matrix (dims)/派生類 Linequ 的構造函數/使用參數調用基類構造函數sums=new doubledims。/動態內存分配solu=new doubledims。Lin

14、equ:Linequ ()/派生類 Linequ 的析構函數delete sums。/釋放內存delete solu。void Linequ:SetLinequ( double *a,double *b)/ 設置線性方程組SetMatrix (a)。/調用基類函數for (int i=0。iindex。i+)sumsi=bi 。void Linequ:PrintL () /顯示線性方程組coutThe line equation is:endl。for (int i=0。 iindex。 i+)for (int j=0。 jindex。 j+)cout* (MatrixA+i*index+j

15、) 。cout sumsiendl 。void Linequ:ShowX ()/輸出方程組的解coutThe result is:endl 。for (int i=0。 iindex。 i+)coutXi=soluiendl。int Li n equ:Solve ( )/全選主元高斯法求解方程int *js,l,k,i,j,is,p,q 。double d,t。double *MatrixB 。 /聲明局部矩陣 MatrixBMatrixB=new doubleindex*index 。/將矩陣 MatrixA 賦值給 MatrixB for (i=0。iindex*index。i+)Matr

16、ixBi=MatrixAi 。js=new intindex 。/分配動態內存l=1。for ( k=0。 k=index-2。 k+)/消去過程d=0.0。for ( i=k 。 i=index-1。 i+ )/選取主元素for ( j=k 。 jd) d=t 。 jsk=j 。 is=i。 if ( d+1.0=1.0)/主元素為零l=0。else/主元素交換if( jsk!=k )for( i=0。 i=index-1 。 i+)p=i*index+k 。 q=i*index+jsk 。t=MatrixBp 。MatrixBp=MatrixBqMatrixBq=t 。if( is!=k)

17、for( j=k 。 j=index-1。 j+ )p=k*index+j 。q=is*index+j 。t=MatrixBp 。 MatrixBp=MatrixBq 。MatrixBq=t 。t=sumsk 。 sumsk=sumsis。 sumsis=t。if (l=0 )/若主元素為零，求解失敗deletejs。coutfailendl 。return 0。d=MatrixBk*index+k 。/歸一化計算for (j=k+1 。 j=index-1 。 j+ )p=k*index+j 。MatrixBp=MatrixBp/d 。sumsk=sumsk/d。for (i=k+1 。 i

18、=index-1 。 i+ )/消去計算for (j=k+1。jv=index-1。j+)p=index*i+j 。MatrixBp=MatrixBp-MatrixBi*index+k*MatrixBk*index+j 。sumsi=sumsi-MatrixBi*index+k*sumsk 。d=MatrixB (index-1)*index+index-1 。if(fabs(d)+1.0=1.0)delete js。coutfail=0。-)t=0.0。for ( j=i+1 。 j=0。 k- )if( jsk!=k )t=soluk 。 soluk=solujsk 。 solujsk=t

19、 。delete js。return 1。在類的成員函數實現過程中， 派生類的構造函數使用參數調用了基類的構 造函數，為矩陣動態分配了內存空間。而派生類的析構函數同樣也調用了基類 的析構函數，只是整個調用過程中完全是由系統內部完成?；惖谋Ｗo數據成 員，經過公有派生之后，在派生類中是以保護成員的身份出現的，派生類的成 員函數可以自由地進行訪問。全選主元高斯消去法求解函數返回值為整數，正常完成之后，返回值為 1，非正常結束后，返回值為0，根據函數的返回值，就可以判斷求解過程的完成情況。4.3主函數設計/main.cpp 主函數#include linequ.h int main（）/主函數dou

20、ble a=0.2368,0.2471,0.2568,1.2671,0.1968,0.2071,1.2168,0.2271,0.1581,1.1675,0.1768,0.1871,1.1161,0.1254,0.1397,0.1490。double b4= 1.8471,1.7471,1.6471,1.5471。/ 方程右端項Linequ equ1（4）。 /定義一個四元方程組對象 return 1。在程序的主函數部分，選擇了一個四元方程組作為一個實際例子來驗證算 法。方程組的系數及右端項數據都使用一維數組來存儲。 首先定義一個四元方 程組對象 equl，在定義過程中調用派生類的構造函數，通過

21、派生類的構造函 數，又調用了基類的構造函數，對進一步求解動態分配了內存。接著給方程組 的系數和右端項賦初值，把我們選定的方程組輸入到新定義的方程組對象 equ1 中。對象成員函數 PrintL 、Solve 和ShowX 分別完成了輸出方程組、求解方程 組和輸出求解結果的任務。5 DOS 界面程序運行結果及分析5.1程序運行結果程序運行結果如圖 2 所示圖2程序運行結果從圖 2 中可以看出，程序能夠實現全選主元高斯消去法對于線性方程組的 求解，/系數矩陣equ1.SetLinequ（ a,b）。equ1.PrintL（）。if （equ1.Solve（）equ1.ShowX（）。elsecou

22、tFailendl/設置方程組/輸出方程組/求解方程組/輸出方程組的解/求解失敗但是，對于求解結果的正確性問題卻無法獲知，為了能夠驗證求解結果 的正確性，考慮將求解結果 x 帶入原方程 Ax=b 中，如果滿足原方程，即說明 求解結果是正確的，否則，說明求解存在問題，需對程序進行進一步調試分 析。為此，考慮在 Linequ 類中增加測試函數 Test，用以驗證求解結果的正確 性。void Linequ:test()/求解結果驗證函數double *b2。b2=new doubleindex。for (int i=0。iindex。i+)將解 solu 帶入原方程求出新的右端項 b2b2i=0 。

23、for (int j=0。 jindex。 j+) b2i=b2i+MatrixAi*index+j*soluj 。for (i=0。 iindex。 i+) /輸出新的右端項coutb2i 。coutendl。在主函數 main 中增加語句：equ1.test()。/驗證求解結果經過驗證的程序運行結果如圖 3 所示。圖3程序運行結果的驗證從圖 3 中可以看出，方程組求解驗證的右端項結果與原右端項結果完全一 致，這說明了方程組求解的正確性。5.2運行結果分析整個程序中的矩陣存儲采用的是一維數組和動態內存分配方式?；愂菍ｉT處理矩陣的類，公有派生類 Linequ 是針對線性方程組而設計 的，除了

24、繼承基類的基本特征之外，結合問題的實際需要，增加了很多線性方 程組所特有的成員，使基類 Matrix 進一步具體化、特殊化，達到對問題的有效 描述和處理。程序的訪問控制也是根據問題的需要而設計的。基類的數據成員的存儲、 維護著矩陣數據，這正是派生類方程組的系數矩陣，使派生類解方程成員函數 必須訪問的。利用保護成員特征，將基類數據成員的訪問控制屬性設置為保護 型，在公有派生類Linequ 中就可以訪問到基類繼承下來的保護成員；而對于類 外的其余模塊，這些數據無法訪問。這樣，就在數據的共享與隱藏之間尋找到 一個比較恰當的結合點。在派生過程中，基類的構造函數和析構函數無法繼承下來，因此在派生類 中需

25、要添加構造函數、析構函數來完成派生類的初始化和最后清理工作。派生 類的構造函數通過調用基類的構造函數來對基類數據進行初始化，本設計中， 派生類 Linequ 的構造函數調用了基類 Matrix 的構造函數并傳遞必須的初始化參 數。派生類的析構函數調用基類的構造函數，共同完成清理任務。6 基于 MFC 的圖形界面程序開發MFC 的圖形界面程序設計可在上述類設計的基礎上進行改造， MFC 的圖形 界面程序與 DOS 界面程序的主要不同點是： MFC 圖形界面程序與 DOS 界面程 序的輸入輸出方式不同，DOS 界面程序采用字符交互式實現數據輸入輸出，主 要通過 cin,cout 等 I/O 流實現

26、，而 MFC 的圖形程序界面采用標準 Windows 窗 口和控件實現輸入輸出，因此必須在 MFC 類的框架下加入上面所設計的矩陣和 方程組類,并通過圖形界面的輸入輸出改造來完成。6.1基于MFC的圖形界面程序設計（1）界面設計首先在 VC 中建立 MFC AppWizard（exe）工程，名稱為 GuassLineGUI, 并在向導的 Step1 中選擇 Dialog based,即建立基于對話框的應用程序，如下圖 45 所示。F 面是編寫代碼的重要階段，可以借鑒在設計基于DOS 界面的控制臺應用圖4建立MFC AppWizard(exe)工程圖5建立基于對話框的應用程序將對話框資源中的默認

27、對話框利用工具箱改造成如下界面，如圖6 所示。圖6方程組求解程序界面設計圖 6 所示的界面中包含了 3 個 Static Text 控件，3 個 Button 控件，和 24 個Edit Box 控件，控件的基本信息列表如下表 1 所示表1控件基本信息控件類別控件ID控件Caption說明Static TextIDC_STATIC系數矩陣A方程組右端項b解XBott onIDC BUTTON Read讀入數據IDC BUTTON CALC計算求解IDC BUTTON Exit退出Edit BoxIDC_EDIT_A00 IDC_EDIT_A33矩陣A的16個元素IDC EDIT bO IDC

28、EDIT b3向量b的4個兀素IDC EDIT XO IDC EDIT X3解X的4個元素（2）代碼設計為了能夠將對話框界面上的控件能夠與代碼聯系起來，需要為24 個 EditBox 控件建立 Member Variables,按 Ctrl+w 鍵進入 MFC ClassWizard 界面，選擇Member Variables 選項卡，可顯示成員變量設置界面，如圖7 所示。圖7成員變量設置界面通過該界面設置與 24 個 Edit Box 控件對應的成員變量，具體如表 2 所示表2控件基本信息控件ID成員變量類型成員變量名稱IDC EDIT A00 IDC EDIT A33doublem A00

29、m A33IDC EDIT b0 IDC EDIT b3doublem b0m b3IDC EDIT X0 IDC EDIT X3doublem X0m X3程序的代碼，并將其作必要的改寫，具體改寫的步驟與內容如下。1將 Linequ.h 文 件 和 Linequ.cpp 文 件 合 并 成 一 個 文 件 ， 重 新 命名 為Linequ.h，并將其加入 MFC 工程。2修改 Linequ.h 文件具體包括：將顯示矩陣 PrintM ()函數和顯示方程 PrintL ()函數注釋掉，因為在圖形界面的程序上已經不需要連個函數承擔輸出功能了； 將輸出方程組的解 ShowX() 函數加入參數 do

30、uble x 變成 ShowX( double x )，以實現將所求的解輸出至參數 x 中，并最終完成在對 話框界面上的顯示；將全選主元高斯法求解函數 Solve() 中的兩處 cout 語句去掉，因為 不需要也不能夠使用 cout 流實現輸出。3在 對 話 框 類 的 實 現 文 件 GuassLineGUIDlg.cpp 中 加 入 #includeLinequ.h ，以實現在該文件中可使用 Linequ 類。4在 GuassLineGUIDlg.cpp 文件中 加入 以下全局 變量 的定 義， 以實現GuassLineGUIDlg 類和 Linequ 類之間的通信，具體代碼如下：doub

31、le a=/系數矩陣0.2368,0.2471,0.2568,1.2671,0.1968,0.2071,1.2168,0.2271,0.1581,1.1675,0.1768,0.1871,1.1161,0.1254,0.1397,0.1490。double b4= 1.8471,1.7471,1.6471,1.5471。/方程右端項double *X 。/存放方程組的解5編寫讀入數據按鈕的消息處理函數，實現將矩陣和右端項的數據刷新到界面上，具體代碼如下：void CGuassLineGUIDlg:OnBUTTONRead()/ TODO: Add your control notificati

32、on handler code herem_A00=a0 。 m_A01=a1 。 m_A02=a2 。 m_A03=a3 。m_A10=a5 。 m_A11=a6 。 m_A12=a7 。 m_A13=a8 。 m_A20=a9 。m_A21=a10 。 m_A22=a11 。 m_A23=a12 。 m_A30=a13 。m_A31=a14 。 m_A32=a15 。 m_A33=a16 。 m_b0=b0 。 m_b1=b1 。m_b2=b2 。 m_b3=b3 。UpdateData（FALSE）o退出按鈕比較簡單，代碼如下：void CGuassLineGUIDlg:OnBUTTONExit （）/ TODO: Add your control notification handler code here OnOK（）。6.2程序測試運行程序后，首先出現的界面如圖 8 所示。圖8程序初始運行界面單擊讀入數據按鈕后，可將系數矩陣 A 和方程組右端項 b 的數據在界面上編寫計算求解按鈕的消息處理函數，實現將方程求解，具體代碼如下:void CGuassLineGUIDlg:OnButtonCalc （）/