數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)說(shuō)明書

1、* 實(shí)踐教學(xué)實(shí)踐教學(xué) * 大學(xué)大學(xué) 計(jì)算機(jī)與通信學(xué)院 2015 年春季學(xué)期 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 課程設(shè)計(jì)課程設(shè)計(jì) 題 目： 集合運(yùn)算問題 遞歸替換問題 跳馬問題 長(zhǎng)整數(shù)運(yùn)算問題 專業(yè)班級(jí)：計(jì)算機(jī)科學(xué)與技術(shù)四班 姓 名： * 學(xué) 號(hào)： 指導(dǎo)教師： 成 績(jī)： 目目 錄錄 摘摘 要要.3 一、一、集合運(yùn)算問題集合運(yùn)算問題.4 1.采用類語(yǔ)言定義相關(guān)的數(shù)據(jù)類型.4 2.算法設(shè)計(jì).4 3.函數(shù)的調(diào)用關(guān)系圖.7 4.調(diào)試分析.8 5.測(cè)試結(jié)果.9 6.源程序（帶注釋）.10 二、二、跳馬問題跳馬問題.13 1.采用類語(yǔ)言定義相關(guān)的數(shù)據(jù)類型.13 2.算法設(shè)計(jì).13 3.函數(shù)的調(diào)用關(guān)系圖.14 4

2、.調(diào)試分析.15 5.測(cè)試結(jié)果.15 6.源程序（帶注釋）.16 三、三、長(zhǎng)整數(shù)運(yùn)算問題長(zhǎng)整數(shù)運(yùn)算問題.18 1.采用類語(yǔ)言定義相關(guān)的數(shù)據(jù)結(jié)構(gòu).18 2.算法設(shè)計(jì).18 3.函數(shù)的調(diào)用關(guān)系圖.18 4.調(diào)試分析.19 5.測(cè)試結(jié)果.20 6.源程序（帶注釋）.20 四、四、遞歸替換問題遞歸替換問題.24 1.采用類語(yǔ)言定義相關(guān)的數(shù)據(jù)類型.24 2.算法設(shè)計(jì).24 3.函數(shù)的調(diào)用關(guān)系圖.25 4.調(diào)試分析.25 5.測(cè)試結(jié)果.26 6.源程序（帶注釋）.26 總總 結(jié)結(jié).29 參考文獻(xiàn)參考文獻(xiàn).30 致致 謝謝.31 3 摘摘 要要 在此次的課程設(shè)計(jì)中，我所完成的項(xiàng)目主要有四個(gè)。分別是：(1)集

3、合運(yùn)算問 題。設(shè)計(jì)一個(gè)程序，實(shí)現(xiàn)兩個(gè)集合的交集、并集、差集、顯示輸出等，要求結(jié)果 集合中的元素不重復(fù)；實(shí)現(xiàn)一個(gè)集合的冪集的求解；（2）遞歸替換問題。編寫 程序，擴(kuò)展 c/c+源文件中的#include 指令（以遞歸的方式） 。請(qǐng)以文件名的內(nèi)容 替換形如括號(hào)內(nèi)的代碼行(#include“filename” ） ；（3）跳馬問題。要求在 64 個(gè)國(guó) 際棋盤格子，任意位置放一個(gè)馬，如何不重復(fù)地把格子走完。 （4）長(zhǎng)整數(shù)運(yùn)算問 題。設(shè)計(jì)程序，實(shí)現(xiàn)兩個(gè)任意長(zhǎng)的整數(shù)的相加、減、乘運(yùn)算問題。 這些程序主要功能是加深我們對(duì)算法與數(shù)據(jù)結(jié)構(gòu)中存儲(chǔ)，線性表和棧的理解。 讓我們對(duì)算法與數(shù)據(jù)結(jié)構(gòu)有個(gè)更深刻的認(rèn)識(shí)。 關(guān)鍵

4、字：關(guān)鍵字：集合運(yùn)算、遞歸替換、長(zhǎng)整數(shù)、跳馬 4 一、一、 集合運(yùn)算問題集合運(yùn)算問題 設(shè)計(jì)一個(gè)程序，實(shí)現(xiàn)兩個(gè)集合的交集、并集、差集、顯示輸出等，要求結(jié)果 集合中的元素不重復(fù)；實(shí)現(xiàn)一個(gè)集合的冪集的求解。 1.1. 采用類語(yǔ)言定義相關(guān)的數(shù)據(jù)類型采用類語(yǔ)言定義相關(guān)的數(shù)據(jù)類型 定義一個(gè)單鏈表作為實(shí)現(xiàn)該問題的數(shù)據(jù)結(jié)構(gòu)。創(chuàng)建的鏈表都是由一個(gè)個(gè)結(jié)點(diǎn) 組成，由于結(jié)點(diǎn)的不同，組成的鏈表也不同。由于每一個(gè)結(jié)點(diǎn)有一個(gè)數(shù)據(jù)域和一 個(gè)指針域，所以可以將結(jié)點(diǎn)結(jié)構(gòu)體定義為 typedef struct lnode /定義結(jié)構(gòu)體指針類型 char data; struct lnode *next; *pointer; 定義一

5、個(gè)結(jié)構(gòu)體來(lái)實(shí)現(xiàn)數(shù)組的動(dòng)態(tài)過(guò)程，用來(lái)求冪集，只在求冪集函數(shù)內(nèi)使 用。 typedef int elemtype; typedef struct/定義一個(gè)結(jié)構(gòu)體來(lái)實(shí)現(xiàn)數(shù)組的動(dòng)態(tài)過(guò)程 elemtype *elem;/指針，指向一個(gè) elemtype 類型的指針 int length;/定義數(shù)組的長(zhǎng)度 int listsize;/定義數(shù)組的初始規(guī)模 sqlist;/定義程序中所使用的數(shù)據(jù)結(jié)構(gòu)為線性表 2.2. 算法設(shè)計(jì)算法設(shè)計(jì) 1.求并集算法求并集算法。把集合 head1 的元素復(fù)制到并集集合 head3 中,然后比較 head2 與 head1，將集合 head2 中在集合 head1 中沒有的元素

6、在插入到并集集合 head3 中。 void and(pointer head1,pointer head2,pointer head3)/定義集合并集函數(shù) pointer p1,p2,p3; 5 p1=head1-next; while(p1!=null)/先把集合 head1 中的所有元素賦給集合 head3 p3=(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)/檢查集合 h

7、ead2 中的元素是否與集合 head1 中的元素相等 p1=head1-next; while(p1!=null) 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;/下一個(gè)元素 2.求交集算法求交集算法。循環(huán)使集合 head1 中一個(gè)元素與集合集合head2 中所有元素比較，將 集合 head1 與集合

8、 head2 中相等的元素插入到交集集合 head3 中。 void or(pointer head1,pointer head2,pointer head3)/定義集合交集函數(shù) pointer p1,p2,p3; p1=head1-next; while(p1!=null)/循環(huán)使集合 head1 中一個(gè)元素與集合 head2 中所有元素比 較 p2=head2-next; while(p2!=null) if(p2!=null) p3-data=p1-data; 6 p3-next=head3-next; head3-next=p3; p1=p1-next;/下一個(gè)元素 3.求差集算法。求

9、差集算法。循環(huán)使集合 head1 中一個(gè)元素與集合 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 中一個(gè)元素與集合 head2 中所有元素比 較 p2=head2-next; while(p2!=null) if(p2=null)/head2 中元素不與 head1

10、中任何元素相等，將 head2 中此 元素插入到并集集合 head3 中 p3=(pointer)malloc(sizeof(struct lnode); p3-data=p1-data; p3-next=head3-next; head3-next=p3; p1=p1-next;/下一個(gè)元素 4.求冪集算法求冪集算法。i 的初始化值為 1，先判斷 i 是否大于 a 的長(zhǎng)度，若大于則輸出 b，否則取 a 中的第 i 個(gè)位置的值，取 b 的長(zhǎng)度 k，將 a 中第 i 個(gè)位置的值插入到 b 中 k 后面，把 i 加 1 在次執(zhí)行本程序當(dāng) ilenth(a)時(shí)遞歸結(jié)束。 void getpowers

11、et(int i,sqlist a,sqlist if(ia.length)/即是所有的值都被走完了一遍，生成了集合的一個(gè)子集， 因此遞歸結(jié)束 output(b);/輸出一個(gè)子集 else 7 x=getelem(a,i);/從 a 表中第 i 位置返回元素值并賦給 x k=b.length;/b 表的長(zhǎng)度賦給 k listinsert(b,k+1,x);/在 b 表第 k+1 位置插入 x getpowerset(i+1,a,b);/遞歸調(diào)用函數(shù) listdelete(b,k+1,x);/在 b 表第 k+1 位置刪除 x getpowerset(i+1,a,b);/遞歸調(diào)用函數(shù) 3.3.

12、函數(shù)的調(diào)用關(guān)系圖函數(shù)的調(diào)用關(guān)系圖 程序主要使用四個(gè)函數(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ù)，通過(guò)輸出函數(shù)輸出 相應(yīng)的結(jié)果（冪集函數(shù)除外） ，如下圖所示： 開開始始 進(jìn)進(jìn)入入主主函函數(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ù) 輸輸入入相相

13、應(yīng)應(yīng)運(yùn)運(yùn)算算對(duì)對(duì)應(yīng)應(yīng)的的數(shù)數(shù)字字 進(jìn)進(jìn)行行相相應(yīng)應(yīng)的的運(yùn)運(yùn)算算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 r s se et t( () ) 調(diào)調(diào)用用排排序序函函 數(shù)數(shù)s so or rt t( () ) 調(diào)調(diào)用用輸輸出出函函數(shù)數(shù) p po op p( () ) e ex xi it t( (0 0) ) 退退出出 8

14、圖 1.函數(shù)調(diào)用關(guān)系圖 4.4. 調(diào)試分析調(diào)試分析 a. 調(diào)試中遇到的問題及問題的解決方法調(diào)試中遇到的問題及問題的解決方法 （1）由于對(duì)集合的兩種運(yùn)算的算法推敲不足，在鏈表類型及其尾指針的設(shè)置 時(shí)出現(xiàn)錯(cuò)誤，導(dǎo)致程序低效。 剛開始時(shí)曾忽略了一些變量參數(shù)的標(biāo)識(shí)” struct lnode *next; *pointer; typedef int elemtype; typedef struct/定義一個(gè)結(jié)構(gòu)體來(lái)實(shí)現(xiàn)數(shù)組的動(dòng)態(tài)過(guò)程 elemtype *elem;/指針，指向一個(gè) elemtype 類型的指針 int length;/定義數(shù)組的長(zhǎng)度 int listsize;/定義數(shù)組的初始規(guī)模 sq

15、list;/定義程序中所使用的數(shù)據(jù)結(jié)構(gòu)為線性表 void getpowerset(int i,sqlist a,sqlist if(ia.length)/即是所有的值都被走完了一遍，生成了集合的一個(gè)子集，因此 遞歸結(jié)束 11 output(b);/輸出一個(gè)子集 else x=getelem(a,i);/從 a 表中第 i 位置返回元素值并賦給 x k=b.length;/b 表的長(zhǎng)度賦給 k listinsert(b,k+1,x);/在 b 表第 k+1 位置插入 x getpowerset(i+1,a,b);/遞歸調(diào)用函數(shù) listdelete(b,k+1,x);/在 b 表第 k+1 位置

16、刪除 x getpowerset(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; while(p!=null)/后續(xù)元素與第一個(gè)元素進(jìn)行比較 r=p-next; q=head; while(q-next!=null p-next=q-next; q-next=p; p=r; void or(pointer head1,pointer head2,pointer head3)/定義集合交集函數(shù) pointer p1,p2

17、,p3; p1=head1-next; while(p1!=null)/循環(huán)使集合 head1 中一個(gè)元素與集合 head2 中所有元素比 較 p2=head2-next; while(p2!=null) if(p2!=null) p3-data=p1-data; p3-next=head3-next; 12 head3-next=p3; p1=p1-next;/下一個(gè)元素 void and(pointer head1,pointer head2,pointer head3)/定義集合并集函數(shù) pointer p1,p2,p3; p1=head1-next; while(p1!=null)/先

18、把集合 head1 中的所有元素賦給集合 head3 p3=(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) if(p1=null)/head2 中元素不與 head1 中任何元素相等，將 head2 中此 元素插入到并集集合 head3 中 p3=(p

19、ointer)malloc(sizeof(struct lnode); p3-data=p2-data; p3-next=head3-next; head3-next=p3; p2=p2-next;/下一個(gè)元素 void differ(pointer head1,pointer head2,pointer head3) /定義集合差集函數(shù) pointer p1,p2,p3; p1=head1-next; while(p1!=null)/循環(huán)使集合 head1 中一個(gè)元素與集合 head2 中所有元素比 較 p2=head2-next; while(p2!=null) 13 if(p2=null

20、)/head1 中元素不與 head2 中任何元素相等，將 head1 中此 元素插入到差集集合 head3 中 p3=(pointer)malloc(sizeof(struct lnode); p3-data=p1-data; p3-next=head3-next; head3-next=p3; p1=p1-next;/下一個(gè)元素 二、二、 跳馬問題跳馬問題 設(shè)計(jì)一個(gè)程序，要求在 64 個(gè)國(guó)際象棋格子，任意位置放置一個(gè)馬，如何不 重復(fù)地把格子走完。 1.1. 采用類語(yǔ)言定義相關(guān)的數(shù)據(jù)類型采用類語(yǔ)言定義相關(guān)的數(shù)據(jù)類型 本程序使用的數(shù)據(jù)結(jié)構(gòu)是棧，利用順序棧來(lái)實(shí)現(xiàn)。 typedef struct

21、int x;/表示橫坐標(biāo) int y;/表示縱坐標(biāo) int direction;/表示移動(dòng)方向 horsepoint; horsepoint chesspathmaxlen;/模擬路徑棧 int count;/入棧結(jié)點(diǎn)個(gè)數(shù) int chessboardmaxnummaxnum;/標(biāo)志棋盤數(shù)組 14 2.2. 算法設(shè)計(jì)算法設(shè)計(jì) 從給出的初始位置開始判斷，按照順時(shí)針順序，每次產(chǎn)生一個(gè)新的路點(diǎn)，并 驗(yàn)證此路點(diǎn)的可用性，需要考慮的是當(dāng)前路點(diǎn)是否超出棋盤范圍和此路點(diǎn)是否已 經(jīng)走過(guò)。如果新路點(diǎn)可用，則入棧，并執(zhí)行下一步，重復(fù)進(jìn)行如上步驟，每次按 照已走路點(diǎn)的位置生成新路點(diǎn)。如果一個(gè)路點(diǎn)的可擴(kuò)展路點(diǎn)數(shù)為 0

22、，進(jìn)行回溯， 直到找到一個(gè)馬能踏遍棋盤的行走路線并輸出。 /計(jì)算路徑的函數(shù) void calcpoint(horsepoint hh) horsepoint nposition; horsepoint *pposition; initial();/調(diào)用初始化函數(shù) pposition=/調(diào)用輸入起始點(diǎn)函數(shù) pushstack(*pposition); while(!(count=0|count=maxlen)/當(dāng)路徑棧不空或不滿時(shí) pposition=/指針指向棧 nposition=getnewpoint(pposition);/產(chǎn)生新結(jié)點(diǎn) if(pposition-direction!=in

23、validdir)/可以往下走 chesspathcount-1.direction=pposition-direction; pushstack(nposition); else popstack(); 3.3. 函數(shù)的調(diào)用關(guān)系圖函數(shù)的調(diào)用關(guān)系圖 本程序通過(guò)主函數(shù) main()來(lái)調(diào)用已寫好的輸入起始坐標(biāo)函數(shù) getinitpoint()、 計(jì)算路徑函數(shù) calcpoint()、運(yùn)行結(jié)果輸出函數(shù) printchess()等幾個(gè)函數(shù)，函數(shù)調(diào)用 關(guān)系圖如下所示： 15 開開始始 主主函函數(shù)數(shù)m ma ai in n( () ) 輸輸入入起起始始坐坐標(biāo)標(biāo) g ge et ti in ni it tp

24、 po oi in nt t( () ) 計(jì)計(jì)算算路路徑徑函函數(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)生生新新結(jié)結(jié)點(diǎn)點(diǎn) g ge et tn ne ew wp po oi in nt t( () ) 該該結(jié)結(jié)點(diǎn)點(diǎn)的的下下一一方方 向向結(jié)結(jié)點(diǎn)點(diǎn)是是否否為為空空 否否 入入棧棧函函數(shù)數(shù) p pu us sh hs st ta ac ck k（） 出出棧棧函函數(shù)數(shù) p po op ps st ta ac

25、 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)試中遇到的問題及對(duì)問題的解決方法調(diào)試中遇到的問題及對(duì)問題的解決方法 （1） 測(cè)試時(shí)出現(xiàn)了遍歷序列不正確的問題，序列的前一部分正確，后一部分不 正確，經(jīng)過(guò)調(diào)試，發(fā)現(xiàn)在存儲(chǔ)遍歷序列的過(guò)程中用來(lái)控制點(diǎn)數(shù)組元素的變 量出現(xiàn)了問題，修改后，問題則順利解決。 （2） 測(cè)試時(shí)輸出的結(jié)果形式不是 8*8 的矩陣圖，經(jīng)同學(xué)幫助檢查后發(fā)現(xiàn)輸出函 數(shù)中輸出語(yǔ)句未加空格，修改后，問題順利解決。 b.算法的時(shí)間復(fù)雜度和空間復(fù)雜度算法的時(shí)間復(fù)雜度和空間復(fù)

26、雜度 算法的時(shí)間復(fù)雜度為 o（n） ； 空間復(fù)雜度為 o(n)。 16 5.5. 測(cè)試結(jié)果測(cè)試結(jié)果 設(shè)輸入起始坐標(biāo)為（0,0） ，則測(cè)試結(jié)果如下圖所示： 圖 5.跳馬測(cè)試結(jié)果圖 6.6. 源程序（帶注釋）源程序（帶注釋） #include #include #define maxnum 8 /橫縱格數(shù)最大值 #define invaliddir -1/無(wú)路可走情況 #define maxlen 64/棋盤總格數(shù) #define maxdir 8/下步可以走的方向 typedef struct int x;/表示橫坐標(biāo) int y;/表示縱坐標(biāo) int direction;/表示移動(dòng)方向 hor

27、sepoint; horsepoint chesspathmaxlen;/模擬路徑棧 int count;/入棧結(jié)點(diǎn)個(gè)數(shù) 17 int chessboardmaxnummaxnum;/標(biāo)志棋盤數(shù)組 horsepoint getnewpoint(horsepoint *parent)/產(chǎn)生新結(jié)點(diǎn)函數(shù) int i; horsepoint newpoint; int tryxmaxdir=1,2,2,1,-1,-2,-2,-1;/能走的 8 個(gè)方向的坐標(biāo)增量 int tryymaxdir=-2,-1,1,2,2,1,-1,-2; newpoint.direction=invaliddir;/新結(jié)點(diǎn)可

28、走方向初始化 parent-direction=parent-direction+;/上一結(jié)點(diǎn)能走的方向 for(i=parent-direction;ix+tryxi;/試探新結(jié)點(diǎn)的可走方向 newpoint.y=parent-y+tryyi; if(newpoint.x=0/上一結(jié)點(diǎn)可走方向 chessboardnewpoint.xnewpoint.y=1;/標(biāo)記已走過(guò) return newpoint; parent-direction=invaliddir; return newpoint; void calcpoint(horsepoint hh)/計(jì)算路徑的函數(shù) horsepoint

29、 nposition; horsepoint *pposition; initial();/調(diào)用初始化函數(shù) pposition=/調(diào)用輸入起始點(diǎn)函數(shù) pushstack(*pposition); while(!(count=0|count=maxlen)/當(dāng)路徑棧不空或不滿時(shí) pposition=/指針指向棧 nposition=getnewpoint(pposition);/產(chǎn)生新結(jié)點(diǎn) if(pposition-direction!=invaliddir)/可以往下走 chesspathcount-1.direction=pposition-direction; pushstack(npos

30、ition);/入棧函數(shù) else popstack();/出棧函數(shù) 18 int main(int argc,char*argv)/主函數(shù) horsepoint h; h=getinitpoint();/輸入起始點(diǎn) calcpoint(h); printchess(); return 0; 三、三、 長(zhǎng)整數(shù)運(yùn)算問題長(zhǎng)整數(shù)運(yùn)算問題 設(shè)計(jì)程序，實(shí)現(xiàn)兩個(gè)任意長(zhǎng)的整數(shù)的加、減、乘運(yùn)算問題。 1.1. 采用類語(yǔ)言定義相關(guān)的數(shù)據(jù)結(jié)構(gòu)采用類語(yǔ)言定義相關(guān)的數(shù)據(jù)結(jié)構(gòu) 本程序使用的數(shù)據(jù)結(jié)構(gòu)是串，利用順序串來(lái)實(shí)現(xiàn)的。 typedef char datatype; datatype amaxlen=0;/用來(lái)存儲(chǔ)第

31、一個(gè)數(shù)的整形數(shù)組 datatype bmaxlen=0;/用來(lái)存儲(chǔ)第二個(gè)數(shù)的整形數(shù)組 datatype c3*maxlen=0/;用來(lái)存儲(chǔ)兩數(shù)運(yùn)算后結(jié)果的數(shù)組 19 2.2. 算法設(shè)計(jì)算法設(shè)計(jì) 1.加法運(yùn)算算法。加法運(yùn)算算法。計(jì)算長(zhǎng)整數(shù)加法時(shí)，采用數(shù)學(xué)中列豎式的方法，從個(gè)位（即字 符串的最后一個(gè)字符）開始逐位相加，超過(guò)或達(dá)到 10 則進(jìn)位，同時(shí)將該位計(jì)算 結(jié)果存到另一個(gè)字符串中，直至加完長(zhǎng)整數(shù)的所有位為止。 2.減法運(yùn)算算法。減法運(yùn)算算法。計(jì)算長(zhǎng)整數(shù)減法時(shí)，首先調(diào)用庫(kù)函數(shù) strcmp 判斷這兩個(gè)長(zhǎng)整數(shù) 是否相等，如果相等則結(jié)果為 0，否則用 compare 函數(shù)判斷被減數(shù)和減數(shù)的大小 關(guān)系，

32、進(jìn)而確定結(jié)果為正數(shù)還是負(fù)數(shù)，然后對(duì)齊位依次進(jìn)行減法，不夠減則向前 借位，直至求出每一位減法之后的結(jié)果。 3.乘法運(yùn)算算法。乘法運(yùn)算算法。計(jì)算長(zhǎng)整數(shù)乘法時(shí)，首先讓乘數(shù)的每一位都和被乘數(shù)進(jìn)行乘法 運(yùn)算，兩個(gè)乘數(shù)之積與進(jìn)位相加作為當(dāng)前乘積，求得當(dāng)前位的同時(shí)獲取進(jìn)位值， 進(jìn)而實(shí)現(xiàn)長(zhǎng)整數(shù)的乘法運(yùn)算。 3.3. 函數(shù)的調(diào)用關(guān)系圖函數(shù)的調(diào)用關(guān)系圖 本程序主要定義了三個(gè)函數(shù)： 加法函數(shù)：additionint( )； 減法函數(shù)：subtrationint( )； 乘法函數(shù)：multiplicationint( )； 程序通過(guò)主函數(shù)調(diào)用已寫好的加法、減法、乘法運(yùn)算函數(shù)，然后通過(guò)輸出函 數(shù) puts( )輸出相應(yīng)

33、的運(yùn)算結(jié)果，函數(shù)調(diào)用關(guān)系圖如下所示： 20 開開始始 輸輸入入兩兩個(gè)個(gè)長(zhǎng)長(zhǎng)整整數(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( () ) 輸輸出出結(jié)結(jié)果果 p pu ut ts s( () ) 結(jié)結(jié)束束 圖 6.函數(shù)關(guān)系調(diào)用圖 4.4. 調(diào)試分

34、析調(diào)試分析 a.調(diào)試中遇到的問題及對(duì)問題的解決方法調(diào)試中遇到的問題及對(duì)問題的解決方法 在調(diào)試是出現(xiàn) strlen、strcmp 等字符串處理的相關(guān)函數(shù)無(wú)法調(diào)用，經(jīng)檢查 發(fā)現(xiàn)頭文件中忘記添加包含字符串處理函數(shù)的頭文件“#include string.h” ，添 加后，問題得到解決。 b.算法的時(shí)間復(fù)雜度和空間復(fù)雜度算法的時(shí)間復(fù)雜度和空間復(fù)雜度 設(shè)兩個(gè)數(shù)的長(zhǎng)度分別為 n、m. 1.求和算法：時(shí)間復(fù)雜度為 o(n)(n=m)，空間復(fù)雜度為 o(n+m)； 2.求差算法：時(shí)間復(fù)雜度為 o(n)(n=m)。 21 5.5. 測(cè)試結(jié)果測(cè)試結(jié)果 設(shè)測(cè)試時(shí)輸入兩個(gè)長(zhǎng)整數(shù)分別為 22222222 和 44444

35、444444，測(cè)試結(jié)果如下圖 所示： 圖 7.長(zhǎng)整數(shù)運(yùn)算測(cè)試圖 6.6. 源程序（帶注釋）源程序（帶注釋） #include #include #include #define maxnum 200 #define maxlen maxnum typedef char datatype; void additionint(datatype *augend,datatype *addend,datatype *sum)/加法運(yùn)算 int caugmaxlen=0;/用來(lái)存儲(chǔ)被加數(shù)的整型數(shù)組 int caddmaxlen=0;/用來(lái)存儲(chǔ)加數(shù)的整型數(shù)組 int csummaxlen=0;/用來(lái)存儲(chǔ)兩

36、數(shù)之和的整型數(shù)組 int carry=0;/進(jìn)位 int s=0;/兩數(shù)之和 int lenaug=strlen(augend),lenadd=strlen(addend);/被加數(shù)和加數(shù)字符串的長(zhǎng)度 int lenmin=lenauglenadd?lenaug:lenadd;/兩個(gè)加數(shù)的長(zhǎng)度中較小值 int i,j; for(i=0;ilenaug;i+)/逆序復(fù)制加數(shù)和被加數(shù)到整型數(shù)組（加法運(yùn)算是從低位 開始的） caugi=augendlenaug-1-i-0; for(i=0;ilenadd;i+) caddi=addendlenadd-1-i-0; for(i=0;ilenmin;i

37、+)/加法運(yùn)算過(guò)程 s=caugi+caddi+carry;/兩個(gè)加數(shù)之和與進(jìn)位的和作為當(dāng)前位的值 22 csumi=s%10;/存儲(chǔ)當(dāng)前位 carry=s/10;/獲取進(jìn)位 while(ilenaug)/處理加數(shù)或被加數(shù)超出長(zhǎng)度 lenmin 的部分 s=caugi+carry; csumi=s%10; carry=s/10; i+; while(i0)/處理最后一個(gè)進(jìn)位 csumi+=carry; for(j=0;ji;j+)/逆序存儲(chǔ)兩數(shù)之和到字符串 sum sumj=csumi-1-j+0; sumi=0; void subtrationint(datatype *minuend,da

38、tatype *subtrahend,datatype *difference) /減法運(yùn)算 int len,lenm,lens,lenmin,i,j,k; int flag;/記錄結(jié)果是正數(shù)還是負(fù)數(shù) int cmmaxlen=0;/用來(lái)存儲(chǔ)被減數(shù)的整型數(shù)組 int csmaxlen=0;/用來(lái)存儲(chǔ)減數(shù)的整型數(shù)組 int cdmaxlen=0;/用來(lái)存儲(chǔ)兩數(shù)之差的整型數(shù)組 if(strcmp(minuend,subtrahend)=0)/如果兩數(shù)相等，則返回 0 strcpy(difference,0); return; lenm=strlen(minuend),lens=strlen(sub

39、trahend);/被減數(shù)和減數(shù)的字符串長(zhǎng)度 lenmin=lenm0)/逆序復(fù)制減數(shù)和被減數(shù)到整型數(shù)組（減法 運(yùn)算是從低位開始的） ，保證 cm 大于 cs flag=0;/被減數(shù)大于減數(shù)，結(jié)果為正數(shù) for(i=0;ilenm;i+) cmi=minuendlenm-1-i-0; for(i=0;ilens;i+) 23 csi=subtrahendlens-1-i-0; else flag=1;/被減數(shù)小于減數(shù)，結(jié)果為負(fù)數(shù)，此時(shí)要用 subtrahend-minuend for(i=0;ilenm;i+) csi=minuendlenm-1-i-0; for(i=0;ilens;i+)

40、cmi=subtrahendlens-1-i-0; for(i=0;i=csi)/被減數(shù)大于減數(shù)，直接相減 cdi=cmi-csi; else cdi=cmi+10-csi; -cmi+1; len=lenmlens?lenm:lens; while(i=0) cdi=cmi; else cdi=cmi+10; -cmi+1; i+; while(cdi-1=0) i-; j=0; if(flag=1)/如果被減數(shù)小于減數(shù)，則返回一個(gè)負(fù)數(shù) differencej+=-; for(k=i-1;k=0;k-,j+)/逆序存儲(chǔ)兩數(shù)之差到字符串 difference differencej=cdk+0

41、; differencej=0; void multiplicationint(datatype *multiplicand,datatype *multiplier,datatype *product)/乘法運(yùn)算 24 int cdmaxlen=0;/用來(lái)存儲(chǔ)被乘數(shù)的整型數(shù)組 int crmaxlen=0;/用來(lái)存儲(chǔ)乘數(shù)的整型數(shù)組 int cpmaxlen=0;/用來(lái)存儲(chǔ)兩數(shù)乘積的整型數(shù)組 datatype tcpmaxlen=;/用來(lái)存儲(chǔ)兩數(shù)乘積的整型數(shù)組 int lend=strlen(multiplicand),lenr=strlen(multiplier);/被乘數(shù)和乘數(shù)的字符串的長(zhǎng)

42、 度 int i,j,k; int carry;/進(jìn)位 int mul=0;/兩數(shù)乘積 for(i=0;ilend;i+)/逆序復(fù)制乘數(shù)和被乘數(shù)到整型數(shù)組（乘法運(yùn)算是從低位開 始的） cdi=multiplicandlend-1-i-0; for(i=0;ilenr;i+) cri=multiplierlenr-1-i-0; strcpy(product,0);/先使 product 的值為 0 for(i=0;ilenr;i+)/乘法運(yùn)算過(guò)程 carry=0;/進(jìn)位 for(j=0;j0)/獲取最后一個(gè)進(jìn)位 cpj+=carry; while(cpj-1=0)/去掉多余的 0 -j; for

43、(k=0;kj;k+)/逆序復(fù)制當(dāng)前位的乘積 tp 到字符串 tcp tcpk=cpj-1-k+0; for(j=0;ji;j+)/注意各位數(shù)得到的結(jié)果應(yīng)相應(yīng)左移 tcpk+=0; tcpk=0; additionint(product,tcp,product);/對(duì)字符串進(jìn)行加法運(yùn)算 25 四、四、 遞歸替換問題遞歸替換問題 設(shè)計(jì)一個(gè)程序，擴(kuò)展 c/c+源文件中的#include 指令（以遞歸的方式） 。請(qǐng)以 文件名的內(nèi)容替換形如下面的代碼行： #include“filename” 1.1. 采用類語(yǔ)言定義相關(guān)的數(shù)據(jù)類型采用類語(yǔ)言定義相關(guān)的數(shù)據(jù)類型 本程序創(chuàng)建了一個(gè)數(shù)據(jù)結(jié)構(gòu)體，使文件的讀寫更

44、方便。該結(jié)構(gòu)體如下： typedef struct char datamax; /數(shù)據(jù)項(xiàng) char1; 2.2. 算法設(shè)計(jì)算法設(shè)計(jì) 模擬 c/c+預(yù)處理程序的功能，打開源文件后，先檢查每一行的第一個(gè)字符 是否是”#“，如果不是，則原樣輸出這一行；如果是，則處理預(yù)處理指令，先 把”#“后緊跟的預(yù)處理指令解析出來(lái)，如果是 include，則提取后面的文件名， 打開文件，再遞歸調(diào)用這個(gè)預(yù)處理函數(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=

45、bi.data19-0; switch(flag) /帶選擇的遞歸調(diào)用 case 1:print(filename1.c,1);break; case 2:print(filename2.c,2);break; case 3:print(filename3.c,3);break; default:break; 26 3.3. 函數(shù)的調(diào)用關(guān)系圖函數(shù)的調(diào)用關(guān)系圖 本程序主要定義了以下幾個(gè)程序： 代碼錄入函數(shù)：input()； 遞歸函數(shù)：print()。 該程序通過(guò)主函數(shù)調(diào)用已寫好的遞歸函、代碼錄入等函數(shù)，具體函數(shù)的調(diào)用 關(guān)系圖如下所示： 開開始始 創(chuàng)創(chuàng)建建三三個(gè)個(gè)文文件件用用來(lái)來(lái) 存存儲(chǔ)儲(chǔ)預(yù)預(yù)編編

46、譯譯文文件件 i in np pu ut t( () ) 創(chuàng)創(chuàng)建建要要編編譯譯的的文文件件 通通過(guò)過(guò)遞遞歸歸算算法法實(shí)實(shí) 現(xiàn)現(xiàn)文文件件的的預(yù)預(yù)編編譯譯 p pr ri in nt t( () ) 保保存存結(jié)結(jié)果果，輸輸出出結(jié)結(jié)果果 結(jié)結(jié)束束 圖 8.函數(shù)關(guān)系調(diào)用圖 4.4. 調(diào)試分析調(diào)試分析 a. 調(diào)試中遇到的問題及對(duì)問題的解決方法調(diào)試中遇到的問題及對(duì)問題的解決方法 在調(diào)試時(shí)，程序?qū)?print()函數(shù)調(diào)用出現(xiàn)錯(cuò)誤，文件的打開與關(guān)閉操作也總是 出現(xiàn)錯(cuò)誤，經(jīng)檢查后，翻閱書籍和上網(wǎng)搜索發(fā)現(xiàn)，原來(lái)程序中文件的打開函數(shù) fopen 和關(guān)閉函數(shù) fclose 前少加了 f，經(jīng)改正后，問題得到解決。 b.

47、 算法的時(shí)間復(fù)雜度和空間復(fù)雜度算法的時(shí)間復(fù)雜度和空間復(fù)雜度 時(shí)間復(fù)雜度為 o(n2)，空間復(fù)雜度為 o(n)。 27 5.5. 測(cè)試結(jié)果測(cè)試結(jié)果 遞歸替換編譯結(jié)果如下圖所示： 圖 9.遞歸替換測(cè)試結(jié)果圖 6.6. 源程序（帶注釋）源程序（帶注釋） # include # include # include #include #define max 100 typedef struct /創(chuàng)建結(jié)構(gòu)體，讓文件的讀寫方便 char datamax; /數(shù)據(jù)項(xiàng) char1; print(char chmax,int n) /遞歸函數(shù) file *fp,*fp1; char smax; /s，存儲(chǔ)#后面的 include char1 bmax; /b,文件中內(nèi)容在 內(nèi)存中的存儲(chǔ)位置 int i=0,k,d=0,j,flag; /switch 參數(shù)，用于確 認(rèn)調(diào)用函數(shù)的參數(shù) 28 if(fp=fopen(ch,rb+)=null) printf(文件打開失??！n); exit(0); while(!feof(fp) fread( i+; if