數(shù)據(jù)結構設計說明書1

1、*實踐教學實踐教學*大學大學計算機與通信學院2015 年春季學期數(shù)據(jù)結構與算法數(shù)據(jù)結構與算法 課程設計課程設計題 目： 集合運算問題 遞歸替換問題 跳馬問題 長整數(shù)運算問題 專業(yè)班級：計算機科學與技術四班姓 名： * 學 號： 指導教師： 成 績： 目目 錄錄摘摘 要要.3一、一、集合運算問題集合運算問題.41.采用類語言定義相關的數(shù)據(jù)類型.42.算法設計.43.函數(shù)的調(diào)用關系圖.74.調(diào)試分析.85.測試結果.96.源程序（帶注釋）.10二、二、跳馬問題跳馬問題.131.采用類語言定義相關的數(shù)據(jù)類型.132.算法設計.133.函數(shù)的調(diào)用關系圖.144.調(diào)試分析.155.測試結果.156.源程

2、序（帶注釋）.16三、三、長整數(shù)運算問題長整數(shù)運算問題.181.采用類語言定義相關的數(shù)據(jù)結構.182.算法設計.183.函數(shù)的調(diào)用關系圖.184.調(diào)試分析.195.測試結果.206.源程序（帶注釋）.20四、四、遞歸替換問題遞歸替換問題.241.采用類語言定義相關的數(shù)據(jù)類型.242.算法設計.243.函數(shù)的調(diào)用關系圖.254.調(diào)試分析.255.測試結果.266.源程序（帶注釋）.26總總 結結.29參考文獻參考文獻.30致致 謝謝.313摘摘 要要在此次的課程設計中，我所完成的項目主要有四個。分別是：(1)集合運算問題。設計一個程序，實現(xiàn)兩個集合的交集、并集、差集、顯示輸出等，要求結果集合中的

3、元素不重復；實現(xiàn)一個集合的冪集的求解；（2）遞歸替換問題。編寫程序，擴展 C/C+源文件中的#include 指令（以遞歸的方式） 。請以文件名的內(nèi)容替換形如括號內(nèi)的代碼行(#include“filename” ） ；（3）跳馬問題。要求在 64 個國際棋盤格子，任意位置放一個馬，如何不重復地把格子走完。 （4）長整數(shù)運算問題。設計程序，實現(xiàn)兩個任意長的整數(shù)的相加、減、乘運算問題。這些程序主要功能是加深我們對算法與數(shù)據(jù)結構中存儲，線性表和棧的理解。讓我們對算法與數(shù)據(jù)結構有個更深刻的認識。關鍵字：關鍵字：集合運算、遞歸替換、長整數(shù)、跳馬4一、一、 集合運算問題集合運算問題設計一個程序，實現(xiàn)兩個集

4、合的交集、并集、差集、顯示輸出等，要求結果集合中的元素不重復；實現(xiàn)一個集合的冪集的求解。1.1. 采用類語言定義相關的數(shù)據(jù)類型采用類語言定義相關的數(shù)據(jù)類型定義一個單鏈表作為實現(xiàn)該問題的數(shù)據(jù)結構。創(chuàng)建的鏈表都是由一個個結點組成，由于結點的不同，組成的鏈表也不同。由于每一個結點有一個數(shù)據(jù)域和一個指針域，所以可以將結點結構體定義為 typedef struct LNode /定義結構體指針類型char data;struct LNode *next;*pointer;定義一個結構體來實現(xiàn)數(shù)組的動態(tài)過程，用來求冪集，只在求冪集函數(shù)內(nèi)使用。typedef int Elemtype;typedef str

5、uct/定義一個結構體來實現(xiàn)數(shù)組的動態(tài)過程Elemtype *elem;/指針，指向一個 Elemtype 類型的指針int length;/定義數(shù)組的長度int listsize;/定義數(shù)組的初始規(guī)模SqList;/定義程序中所使用的數(shù)據(jù)結構為線性表2.2. 算法設計算法設計1.求并集算法求并集算法。把集合 head1 的元素復制到并集集合 head3 中,然后比較 head2與 head1，將集合 head2 中在集合 head1 中沒有的元素在插入到并集集合 head3中。void and(pointer head1,pointer head2,pointer head3)/定義集合并集

6、函數(shù) pointer p1,p2,p3;5p1=head1-next;while(p1!=NULL)/先把集合 head1 中的所有元素賦給集合 head3p3=(pointer)malloc(sizeof(struct LNode);p3-data=p1-data;p3-next=head3-next;head3-next=p3;p1=p1-next;p2=head2-next;while(p2!=NULL)/檢查集合 head2 中的元素是否與集合 head1 中的元素相等p1=head1-next;while(p1!=NULL)&(p1-data!=p2-data)p1=p1-n

7、ext;if(p1=NULL)/head2 中元素不與 head1 中任何元素相等，將 head2 中此元素插入到并集集合 head3 中p3=(pointer)malloc(sizeof(struct LNode);p3-data=p2-data;p3-next=head3-next;head3-next=p3;p2=p2-next;/下一個元素2.求交集算法求交集算法。循環(huán)使集合 head1 中一個元素與集合集合head2 中所有元素比較，將集合 head1 與集合 head2 中相等的元素插入到交集集合 head3 中。void or(pointer head1,pointer head

8、2,pointer head3)/定義集合交集函數(shù) pointer p1,p2,p3;p1=head1-next;while(p1!=NULL)/循環(huán)使集合 head1 中一個元素與集合 head2 中所有元素比較p2=head2-next;while(p2!=NULL)&(p2-data!=p1-data)p2=p2-next;if(p2!=NULL)&(p2-data=p1-data)/若集合 head1 與集合 head2 存在相等的元素，則將該元素插入到交集集合 head3 中p3=(pointer)malloc(sizeof(struct LNode);p3-data

9、=p1-data;6p3-next=head3-next;head3-next=p3;p1=p1-next;/下一個元素3.求差集算法。求差集算法。循環(huán)使集合 head1 中一個元素與集合 head2 中所有元素比較, 將集合 head1 中不與 head2 中任何元素相等元素插入到差集集合 head3 中。void differ(pointer head1,pointer head2,pointer head3) /定義集合差集函數(shù) pointer p1,p2,p3;p1=head1-next;while(p1!=NULL)/循環(huán)使集合 head1 中一個元素與集合 head2 中所有元素比

10、較p2=head2-next;while(p2!=NULL)&(p2-data!=p1-data)p2=p2-next;if(p2=NULL)/head2 中元素不與 head1 中任何元素相等，將 head2 中此元素插入到并集集合 head3 中p3=(pointer)malloc(sizeof(struct LNode);p3-data=p1-data;p3-next=head3-next;head3-next=p3;p1=p1-next;/下一個元素4.求冪集算法求冪集算法。i 的初始化值為 1，先判斷 i 是否大于 A 的長度，若大于則輸出B，否則取 A 中的第 i 個位置的

11、值，取 B 的長度 k，將 A 中第 i 個位置的值插入到B 中 k 后面，把 i 加 1 在次執(zhí)行本程序當 ilenth(A)時遞歸結束。void GetPowerSet(int i,SqList A,SqList &B)/得到冪集的函數(shù)int x,k;if(iA.length)/即是所有的值都被走完了一遍，生成了集合的一個子集，因此遞歸結束Output(B);/輸出一個子集else7x=GetElem(A,i);/從 A 表中第 i 位置返回元素值并賦給 xk=B.length;/B 表的長度賦給 kListInsert(B,k+1,x);/在 B 表第 k+1 位置插入 xGet

12、PowerSet(i+1,A,B);/遞歸調(diào)用函數(shù)ListDelete(B,k+1,x);/在 B 表第 k+1 位置刪除 xGetPowerSet(i+1,A,B);/遞歸調(diào)用函數(shù)3.3. 函數(shù)的調(diào)用關系圖函數(shù)的調(diào)用關系圖程序主要使用四個函數(shù)：1.or(head1,head2,head3) 求交集函數(shù)；2.add(head1,head2,head3) 求并集函數(shù)；3.differ(head1,head2,head3) 求差集函數(shù)；4.GetPowerSet(1,A,B) 求冪集函數(shù)。主函數(shù)分別調(diào)用已寫好的交集、并集、差集及冪集函數(shù)，通過輸出函數(shù)輸出相應的結果（冪集函數(shù)除外） ，如下圖所示：開

13、開始始進進入入主主函函數(shù)數(shù)m ma ai in n( () )創(chuàng)創(chuàng)建建集集合合，調(diào)調(diào)用用r re ea ad dd da at ta a( () )函函數(shù)數(shù)輸輸入入相相應應運運算算對對應應的的數(shù)數(shù)字字進進行行相相應應的的運運算算s sw wi it tc ch h( () )調(diào)調(diào)用用交交集集函函數(shù)數(shù)o or r( () )調(diào)調(diào)用用并并集集函函數(shù)數(shù)a ad dd d( () )調(diào)調(diào)用用差差集集函函數(shù)數(shù)d di if ff fe er r( () )調(diào)調(diào)用用冪冪集集函函數(shù)數(shù)G Ge et tP Po ow we er rS Se et t( () )調(diào)調(diào)用用排排序序函函數(shù)數(shù)S So or rt t

14、( () )調(diào)調(diào)用用輸輸出出函函數(shù)數(shù)P Po op p( () )e ex xi it t( (0 0) )退退出出8 圖 1.函數(shù)調(diào)用關系圖4.4. 調(diào)試分析調(diào)試分析a. 調(diào)試中遇到的問題及問題的解決方法調(diào)試中遇到的問題及問題的解決方法（1）由于對集合的兩種運算的算法推敲不足，在鏈表類型及其尾指針的設置時出現(xiàn)錯誤，導致程序低效。 剛開始時曾忽略了一些變量參數(shù)的標識”&” ，使調(diào)試程序浪費時間不少。今后應重視確定參數(shù)的變量和賦值屬性的區(qū)分和標識。（2）開始時輸入集合后，程序只能進行一次運算，后來加入 switch 語句,成功解決了這一難題。 （3）起初在調(diào)用求求并集函數(shù)時，并未新建一鏈

15、表，在原鏈表上進行修改，導致原鏈表的 data 改變，隨之調(diào)用的求差集函數(shù)輸不出正確結果，通過在每個函數(shù)中新建一鏈表并返回輸出，很好地解決了問題。 （4）對鏈表中為 NULL 的結點要特別注意不能對其進行刪除等操作。b. 算法的時間復雜度和空間復雜度算法的時間復雜度和空間復雜度設集合 A 的長度為 n,集合 B 的長度為 m。1.求交集算法：時間復雜度是 O(n*n*m)(n=m)，空間大小是鏈表的長度n+m；2.求并集算法：時間復雜度是 O(n*m)，空間大小是鏈表的長度 n+n+m；3.求差集算法：時間復雜度是 O(n*m)，空間大小是鏈表的長度 n+n+m；4.求冪集算法：時間復雜度是

16、O（n2） ，空間大小是鏈表的長度 n。95.5. 測試結果測試結果設輸入集合 A=1,3,4,5,7,9，集合 B=1,2,4,6,8,9，冪集運算集合A=1，2,3，運行結果如下所示：1.根據(jù)提示輸入兩個集合，分別以回車鍵結束，如下圖所示： 圖 2.輸入集合測試圖2.輸入相應的運算對應的數(shù)字分別進行相應的運算，輸入 0 退出，如下圖所示：10圖 3.集合運算測試圖6.6. 源程序（帶注釋）源程序（帶注釋）#include#include#include#define LIST_INIT_SIZE 100typedef struct LNode /定義結構體指針類型char data;str

17、uct LNode *next;*pointer;typedef int Elemtype;typedef struct/定義一個結構體來實現(xiàn)數(shù)組的動態(tài)過程Elemtype *elem;/指針，指向一個 Elemtype 類型的指針int length;/定義數(shù)組的長度int listsize;/定義數(shù)組的初始規(guī)模SqList;/定義程序中所使用的數(shù)據(jù)結構為線性表void GetPowerSet(int i,SqList A,SqList &B)/得到冪集的函數(shù)int x,k;if(iA.length)/即是所有的值都被走完了一遍，生成了集合的一個子集，因此遞歸結束11Output(B

18、);/輸出一個子集elsex=GetElem(A,i);/從 A 表中第 i 位置返回元素值并賦給 xk=B.length;/B 表的長度賦給 kListInsert(B,k+1,x);/在 B 表第 k+1 位置插入 xGetPowerSet(i+1,A,B);/遞歸調(diào)用函數(shù)ListDelete(B,k+1,x);/在 B 表第 k+1 位置刪除 xGetPowerSet(i+1,A,B);/遞歸調(diào)用函數(shù)void Sort(pointer head)/建立有序鏈表 pointer p=head-next,q,r; if(p!=NULL) r=p-next; p-next=NULL; p=r;

19、 while(p!=NULL)/后續(xù)元素與第一個元素進行比較 r=p-next; q=head; while(q-next!=NULL&q-next-datadata) q=q-next; p-next=q-next; q-next=p; p=r; void or(pointer head1,pointer head2,pointer head3)/定義集合交集函數(shù) pointer p1,p2,p3;p1=head1-next;while(p1!=NULL)/循環(huán)使集合 head1 中一個元素與集合 head2 中所有元素比較p2=head2-next;while(p2!=NULL)&

20、amp;(p2-data!=p1-data)p2=p2-next;if(p2!=NULL)&(p2-data=p1-data)/若集合 head1 與集合 head2 存在相等的元素，則將該元素插入到交集集合 head3 中p3=(pointer)malloc(sizeof(struct LNode);p3-data=p1-data;p3-next=head3-next;12head3-next=p3;p1=p1-next;/下一個元素void and(pointer head1,pointer head2,pointer head3)/定義集合并集函數(shù) pointer p1,p2,p

21、3;p1=head1-next;while(p1!=NULL)/先把集合 head1 中的所有元素賦給集合 head3p3=(pointer)malloc(sizeof(struct LNode);p3-data=p1-data;p3-next=head3-next;head3-next=p3;p1=p1-next;p2=head2-next;while(p2!=NULL)/檢查集合 head2 中的元素是否與集合 head1 中的元素相等p1=head1-next;while(p1!=NULL)&(p1-data!=p2-data)p1=p1-next;if(p1=NULL)/hea

22、d2 中元素不與 head1 中任何元素相等，將 head2 中此元素插入到并集集合 head3 中p3=(pointer)malloc(sizeof(struct LNode);p3-data=p2-data;p3-next=head3-next;head3-next=p3;p2=p2-next;/下一個元素void differ(pointer head1,pointer head2,pointer head3) /定義集合差集函數(shù) pointer p1,p2,p3;p1=head1-next;while(p1!=NULL)/循環(huán)使集合 head1 中一個元素與集合 head2 中所有元素

23、比較p2=head2-next;while(p2!=NULL)&(p2-data!=p1-data)p2=p2-next;13if(p2=NULL)/head1 中元素不與 head2 中任何元素相等，將 head1 中此元素插入到差集集合 head3 中p3=(pointer)malloc(sizeof(struct LNode);p3-data=p1-data;p3-next=head3-next;head3-next=p3;p1=p1-next;/下一個元素二、二、 跳馬問題跳馬問題設計一個程序，要求在 64 個國際象棋格子，任意位置放置一個馬，如何不重復地把格子走完。1.1.

24、采用類語言定義相關的數(shù)據(jù)類型采用類語言定義相關的數(shù)據(jù)類型本程序使用的數(shù)據(jù)結構是棧，利用順序棧來實現(xiàn)。typedef structint x;/表示橫坐標int y;/表示縱坐標int direction;/表示移動方向HorsePoint;HorsePoint ChessPathMAXLEN;/模擬路徑棧 int count;/入棧結點個數(shù)int ChessBoardMAXNUMMAXNUM;/標志棋盤數(shù)組142.2. 算法設計算法設計從給出的初始位置開始判斷，按照順時針順序，每次產(chǎn)生一個新的路點，并驗證此路點的可用性，需要考慮的是當前路點是否超出棋盤范圍和此路點是否已經(jīng)走過。如果新路點可用，

25、則入棧，并執(zhí)行下一步，重復進行如上步驟，每次按照已走路點的位置生成新路點。如果一個路點的可擴展路點數(shù)為 0，進行回溯，直到找到一個馬能踏遍棋盤的行走路線并輸出。/計算路徑的函數(shù)void CalcPoint(HorsePoint hh) HorsePoint nposition;HorsePoint *pposition;Initial();/調(diào)用初始化函數(shù)pposition=&hh;/調(diào)用輸入起始點函數(shù)PushStack(*pposition);while(!(count=0|count=MAXLEN)/當路徑棧不空或不滿時pposition=&ChessPathcount-1

26、;/指針指向棧nposition=GetNewPoint(pposition);/產(chǎn)生新結點if(pposition-direction!=INVALIDDIR)/可以往下走ChessPathcount-1.direction=pposition-direction;PushStack(nposition);elsePopStack();3.3. 函數(shù)的調(diào)用關系圖函數(shù)的調(diào)用關系圖本程序通過主函數(shù) main()來調(diào)用已寫好的輸入起始坐標函數(shù) GetInitPoint()、計算路徑函數(shù) CalcPoint()、運行結果輸出函數(shù) PrintChess()等幾個函數(shù)，函數(shù)調(diào)用關系圖如下所示：15 開開

27、始始主主函函數(shù)數(shù)m ma ai in n( () )輸輸入入起起始始坐坐標標G Ge et tI In ni it tP Po oi in nt t( () )計計算算路路徑徑函函數(shù)數(shù)C Ca al lc cP Po oi in nt t( () )數(shù)數(shù)組組初初始始化化I In ni it ti ia al l( () )C Co ou un nt t= = =M MA AX XL LE EN N否否產(chǎn)產(chǎn)生生新新結結點點G Ge et tN Ne ew wP Po oi in nt t( () )該該結結點點的的下下一一方方向向結結點點是是否否為為空空否否入入棧棧函函數(shù)數(shù)P Pu us sh

28、hS St ta ac ck k（）出出棧棧函函數(shù)數(shù)P Po op pS St ta ac ck k（）是是輸輸出出函函數(shù)數(shù)P Pr ri in nt tC Ch he es ss s（）是是圖 4.函數(shù)調(diào)用流程圖4.4. 調(diào)試分析調(diào)試分析a.調(diào)試中遇到的問題及對問題的解決方法調(diào)試中遇到的問題及對問題的解決方法（1） 測試時出現(xiàn)了遍歷序列不正確的問題，序列的前一部分正確，后一部分不正確，經(jīng)過調(diào)試，發(fā)現(xiàn)在存儲遍歷序列的過程中用來控制點數(shù)組元素的變量出現(xiàn)了問題，修改后，問題則順利解決。（2） 測試時輸出的結果形式不是 8*8 的矩陣圖，經(jīng)同學幫助檢查后發(fā)現(xiàn)輸出函數(shù)中輸出語句未加空格，修改后，問題順

29、利解決。b.算法的時間復雜度和空間復雜度算法的時間復雜度和空間復雜度算法的時間復雜度為 O（n） ；空間復雜度為 O(n)。165.5. 測試結果測試結果設輸入起始坐標為（0,0） ，則測試結果如下圖所示：圖 5.跳馬測試結果圖6.6. 源程序（帶注釋）源程序（帶注釋）#include #include #define MAXNUM 8 /橫縱格數(shù)最大值#define INVALIDDIR -1/無路可走情況#define MAXLEN 64/棋盤總格數(shù)#define MAXDIR 8/下步可以走的方向typedef structint x;/表示橫坐標int y;/表示縱坐標int dire

30、ction;/表示移動方向HorsePoint;HorsePoint ChessPathMAXLEN;/模擬路徑棧 int count;/入棧結點個數(shù)17int ChessBoardMAXNUMMAXNUM;/標志棋盤數(shù)組HorsePoint GetNewPoint(HorsePoint *parent)/產(chǎn)生新結點函數(shù)int i;HorsePoint newpoint;int tryxMAXDIR=1,2,2,1,-1,-2,-2,-1;/能走的 8 個方向的坐標增量int tryyMAXDIR=-2,-1,1,2,2,1,-1,-2;newpoint.direction=INVALIDDI

31、R;/新結點可走方向初始化parent-direction=parent-direction+;/上一結點能走的方向for(i=parent-direction;ix+tryxi;/試探新結點的可走方向newpoint.y=parent-y+tryyi;if(newpoint.x=0&newpoint.y=0&ChessBoardnewpoint.xnewpoint.y=0)parent-direction=i;/上一結點可走方向ChessBoardnewpoint.xnewpoint.y=1;/標記已走過return newpoint;parent-direction=INV

32、ALIDDIR;return newpoint;void CalcPoint(HorsePoint hh)/計算路徑的函數(shù)HorsePoint nposition;HorsePoint *pposition;Initial();/調(diào)用初始化函數(shù)pposition=&hh;/調(diào)用輸入起始點函數(shù)PushStack(*pposition);while(!(count=0|count=MAXLEN)/當路徑棧不空或不滿時pposition=&ChessPathcount-1;/指針指向棧nposition=GetNewPoint(pposition);/產(chǎn)生新結點if(ppositio

33、n-direction!=INVALIDDIR)/可以往下走ChessPathcount-1.direction=pposition-direction;PushStack(nposition);/入棧函數(shù)elsePopStack();/出棧函數(shù)18int main(int argc,char*argv)/主函數(shù)HorsePoint h;h=GetInitPoint();/輸入起始點CalcPoint(h);PrintChess();return 0;三、三、 長整數(shù)運算問題長整數(shù)運算問題設計程序，實現(xiàn)兩個任意長的整數(shù)的加、減、乘運算問題。1.1. 采用類語言定義相關的數(shù)據(jù)結構采用類語言定義相

34、關的數(shù)據(jù)結構本程序使用的數(shù)據(jù)結構是串，利用順序串來實現(xiàn)的。typedef char DataType;DataType aMAXLEN=0;/用來存儲第一個數(shù)的整形數(shù)組DataType bMAXLEN=0;/用來存儲第二個數(shù)的整形數(shù)組DataType c3*MAXLEN=0/;用來存儲兩數(shù)運算后結果的數(shù)組192.2. 算法設計算法設計1.加法運算算法。加法運算算法。計算長整數(shù)加法時，采用數(shù)學中列豎式的方法，從個位（即字符串的最后一個字符）開始逐位相加，超過或達到 10 則進位，同時將該位計算結果存到另一個字符串中，直至加完長整數(shù)的所有位為止。2.減法運算算法。減法運算算法。計算長整數(shù)減法時，首

35、先調(diào)用庫函數(shù) strcmp 判斷這兩個長整數(shù)是否相等，如果相等則結果為 0，否則用 Compare 函數(shù)判斷被減數(shù)和減數(shù)的大小關系，進而確定結果為正數(shù)還是負數(shù)，然后對齊位依次進行減法，不夠減則向前借位，直至求出每一位減法之后的結果。3.乘法運算算法。乘法運算算法。計算長整數(shù)乘法時，首先讓乘數(shù)的每一位都和被乘數(shù)進行乘法運算，兩個乘數(shù)之積與進位相加作為當前乘積，求得當前位的同時獲取進位值，進而實現(xiàn)長整數(shù)的乘法運算。3.3. 函數(shù)的調(diào)用關系圖函數(shù)的調(diào)用關系圖本程序主要定義了三個函數(shù)：加法函數(shù)：AdditionInt( )；減法函數(shù)：SubtrationInt( )；乘法函數(shù)：Multiplicati

36、onInt( )；程序通過主函數(shù)調(diào)用已寫好的加法、減法、乘法運算函數(shù)，然后通過輸出函數(shù) puts( )輸出相應的運算結果，函數(shù)調(diào)用關系圖如下所示：20開開始始輸輸入入兩兩個個長長整整數(shù)數(shù)g ge et ts s( () )調(diào)調(diào)用用減減法法函函數(shù)數(shù)S Su ub bt tr ra at ti io on nI In nt t( () )調(diào)調(diào)用用乘乘法法函函數(shù)數(shù)M Mu ul lt ti ip pl li ic ca an nt ti io on nI In nt t( () )調(diào)調(diào)用用加加法法函函數(shù)數(shù)A Ad dd di it ti io on nI In nt t( () )輸輸出出結結果果p

37、 pu ut ts s( () )結結束束圖 6.函數(shù)關系調(diào)用圖4.4. 調(diào)試分析調(diào)試分析a.調(diào)試中遇到的問題及對問題的解決方法調(diào)試中遇到的問題及對問題的解決方法在調(diào)試是出現(xiàn) strlen、strcmp 等字符串處理的相關函數(shù)無法調(diào)用，經(jīng)檢查發(fā)現(xiàn)頭文件中忘記添加包含字符串處理函數(shù)的頭文件“#include string.h” ，添加后，問題得到解決。b.算法的時間復雜度和空間復雜度算法的時間復雜度和空間復雜度設兩個數(shù)的長度分別為 n、m.1.求和算法：時間復雜度為 O(n)(n=m)，空間復雜度為 O(n+m)；2.求差算法：時間復雜度為 O(n)(n=m)。215.5. 測試結果測試結果設測

38、試時輸入兩個長整數(shù)分別為 22222222 和 44444444444，測試結果如下圖所示：圖 7.長整數(shù)運算測試圖6.6. 源程序（帶注釋）源程序（帶注釋）#include #include#include#define MAXNUM 200#define MAXLEN MAXNUMtypedef char DataType;void AdditionInt(DataType *augend,DataType *addend,DataType *sum)/加法運算int caugMAXLEN=0;/用來存儲被加數(shù)的整型數(shù)組int caddMAXLEN=0;/用來存儲加數(shù)的整型數(shù)組int cs

39、umMAXLEN=0;/用來存儲兩數(shù)之和的整型數(shù)組int carry=0;/進位int s=0;/兩數(shù)之和int lenaug=strlen(augend),lenadd=strlen(addend);/被加數(shù)和加數(shù)字符串的長度int lenmin=lenauglenadd?lenaug:lenadd;/兩個加數(shù)的長度中較小值int i,j;for(i=0;ilenaug;i+)/逆序復制加數(shù)和被加數(shù)到整型數(shù)組（加法運算是從低位開始的）caugi=augendlenaug-1-i-0;for(i=0;ilenadd;i+)caddi=addendlenadd-1-i-0;for(i=0;ile

40、nmin;i+)/加法運算過程s=caugi+caddi+carry;/兩個加數(shù)之和與進位的和作為當前位的值22csumi=s%10;/存儲當前位carry=s/10;/獲取進位while(ilenaug)/處理加數(shù)或被加數(shù)超出長度 lenmin 的部分s=caugi+carry;csumi=s%10;carry=s/10;i+;while(i0)/處理最后一個進位csumi+=carry;for(j=0;ji;j+)/逆序存儲兩數(shù)之和到字符串 sumsumj=csumi-1-j+0;sumi=0;void SubtrationInt(DataType *minuend,DataType *s

41、ubtrahend,DataType *difference)/減法運算int len,lenm,lens,lenmin,i,j,k;int flag;/記錄結果是正數(shù)還是負數(shù)int cmMAXLEN=0;/用來存儲被減數(shù)的整型數(shù)組int csMAXLEN=0;/用來存儲減數(shù)的整型數(shù)組 int cdMAXLEN=0;/用來存儲兩數(shù)之差的整型數(shù)組if(strcmp(minuend,subtrahend)=0)/如果兩數(shù)相等，則返回 0strcpy(difference,0);return;lenm=strlen(minuend),lens=strlen(subtrahend);/被減數(shù)和減數(shù)的字

42、符串長度lenmin=lenm0)/逆序復制減數(shù)和被減數(shù)到整型數(shù)組（減法運算是從低位開始的） ，保證 cm 大于 csflag=0;/被減數(shù)大于減數(shù)，結果為正數(shù)for(i=0;ilenm;i+)cmi=minuendlenm-1-i-0;for(i=0;ilens;i+)23csi=subtrahendlens-1-i-0;elseflag=1;/被減數(shù)小于減數(shù)，結果為負數(shù)，此時要用 subtrahend-minuendfor(i=0;ilenm;i+)csi=minuendlenm-1-i-0;for(i=0;ilens;i+)cmi=subtrahendlens-1-i-0;for(i=0

43、;i=csi)/被減數(shù)大于減數(shù)，直接相減cdi=cmi-csi;elsecdi=cmi+10-csi;-cmi+1;len=lenmlens?lenm:lens;while(i=0)cdi=cmi;elsecdi=cmi+10;-cmi+1;i+;while(cdi-1=0)i-;j=0;if(flag=1)/如果被減數(shù)小于減數(shù)，則返回一個負數(shù)differencej+=-;for(k=i-1;k=0;k-,j+)/逆序存儲兩數(shù)之差到字符串 differencedifferencej=cdk+0;differencej=0;void MultiplicationInt(DataType *mul

44、tiplicand,DataType *multiplier,DataType *product)/乘法運算24 int cdMAXLEN=0;/用來存儲被乘數(shù)的整型數(shù)組int crMAXLEN=0;/用來存儲乘數(shù)的整型數(shù)組 int cpMAXLEN=0;/用來存儲兩數(shù)乘積的整型數(shù)組DataType tcpMAXLEN=;/用來存儲兩數(shù)乘積的整型數(shù)組int lend=strlen(multiplicand),lenr=strlen(multiplier);/被乘數(shù)和乘數(shù)的字符串的長度int i,j,k;int carry;/進位int mul=0;/兩數(shù)乘積for(i=0;ilend;i+)/

45、逆序復制乘數(shù)和被乘數(shù)到整型數(shù)組（乘法運算是從低位開始的）cdi=multiplicandlend-1-i-0;for(i=0;ilenr;i+)cri=multiplierlenr-1-i-0;strcpy(product,0);/先使 product 的值為 0for(i=0;ilenr;i+)/乘法運算過程carry=0;/進位for(j=0;j0)/獲取最后一個進位cpj+=carry;while(cpj-1=0)/去掉多余的 0-j;for(k=0;kj;k+)/逆序復制當前位的乘積 tp 到字符串 tcptcpk=cpj-1-k+0;for(j=0;ji;j+)/注意各位數(shù)得到的結果

46、應相應左移tcpk+=0;tcpk=0;AdditionInt(product,tcp,product);/對字符串進行加法運算25四、四、 遞歸替換問題遞歸替換問題設計一個程序，擴展 C/C+源文件中的#include 指令（以遞歸的方式） 。請以文件名的內(nèi)容替換形如下面的代碼行： #include“filename”1.1. 采用類語言定義相關的數(shù)據(jù)類型采用類語言定義相關的數(shù)據(jù)類型本程序創(chuàng)建了一個數(shù)據(jù)結構體，使文件的讀寫更方便。該結構體如下：typedef struct char dataMAX; /數(shù)據(jù)項char1;2.2. 算法設計算法設計模擬 C/C+預處理程序的功能，打開源文件后，

47、先檢查每一行的第一個字符是否是”#“，如果不是，則原樣輸出這一行；如果是，則處理預處理指令，先把”#“后緊跟的預處理指令解析出來，如果是 include，則提取后面的文件名，打開文件，再遞歸調(diào)用這個預處理函數(shù)就行了。if(bi.data0=#) /發(fā)現(xiàn) include，遞歸調(diào)用print for(j=2;j9;j+) sd=bi.dataj; d+; if(strcmp(s,include)=0) flag=bi.data19-0; switch(flag) /帶選擇的遞歸調(diào)用 case 1:print(filename1.c,1);break; case 2:print(filename2.

48、c,2);break; case 3:print(filename3.c,3);break; default:break; 263.3. 函數(shù)的調(diào)用關系圖函數(shù)的調(diào)用關系圖本程序主要定義了以下幾個程序：代碼錄入函數(shù)：input()；遞歸函數(shù)：print()。該程序通過主函數(shù)調(diào)用已寫好的遞歸函、代碼錄入等函數(shù)，具體函數(shù)的調(diào)用關系圖如下所示： 開開始始創(chuàng)創(chuàng)建建三三個個文文件件用用來來存存儲儲預預編編譯譯文文件件I In np pu ut t( () )創(chuàng)創(chuàng)建建要要編編譯譯的的文文件件通通過過遞遞歸歸算算法法實實現(xiàn)現(xiàn)文文件件的的預預編編譯譯p pr ri in nt t( () ) 保保存存結結果果，

49、輸輸出出結結果果結結束束圖 8.函數(shù)關系調(diào)用圖4.4. 調(diào)試分析調(diào)試分析a. 調(diào)試中遇到的問題及對問題的解決方法調(diào)試中遇到的問題及對問題的解決方法在調(diào)試時，程序?qū)?print()函數(shù)調(diào)用出現(xiàn)錯誤，文件的打開與關閉操作也總是出現(xiàn)錯誤，經(jīng)檢查后，翻閱書籍和上網(wǎng)搜索發(fā)現(xiàn)，原來程序中文件的打開函數(shù)fopen 和關閉函數(shù) fclose 前少加了 f，經(jīng)改正后，問題得到解決。b. 算法的時間復雜度和空間復雜度算法的時間復雜度和空間復雜度時間復雜度為 O(n2)，空間復雜度為 O(n)。275.5. 測試結果測試結果遞歸替換編譯結果如下圖所示：圖 9.遞歸替換測試結果圖6.6. 源程序（帶注釋）源程序（帶注

50、釋）# include # include # include #include#define MAX 100typedef struct /創(chuàng)建結構體，讓文件的讀寫方便 char dataMAX; /數(shù)據(jù)項char1;print(char chMAX,int n) /遞歸函數(shù) FILE *fp,*fp1; char sMAX; /s，存儲#后面的include char1 bMAX; /b,文件中內(nèi)容在內(nèi)存中的存儲位置 int i=0,k,d=0,j,flag; /switch 參數(shù)，用于確認調(diào)用函數(shù)的參數(shù)28 if(fp=fopen(ch,rb+)=NULL) printf(文件打開失??！n); ex