長整數(shù)的運算算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告書

1、實踐教學(xué)蘭州理工大學(xué)軟件學(xué)院2013 年春季學(xué)期算法與數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計題 目： 長整數(shù)的運算 專業(yè)班級： 軟件二班 姓 名： 齊 祥 榮 學(xué) 號： 12700244 指導(dǎo)教師： 王 連 相 成 績：目錄摘 要 1前 言 2正 文 31. 采用類 C 語言定義相關(guān)的數(shù)據(jù)類型 32. 各模塊的偽碼算法 33. 函數(shù)的調(diào)用關(guān)系圖 74. 調(diào)試分析 85. 測試結(jié)果 86. 源程序（帶注釋） 9總 結(jié) 19參考文獻 20致 謝 21附件 部分源程序代碼 22摘要數(shù)據(jù)結(jié)構(gòu)該設(shè)計要求學(xué)生設(shè)計程序，實現(xiàn)兩個任意長的整數(shù)求和及差的運算問題。通 過該題目的設(shè)計過程，可以加深理解線性表的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)，掌握

2、線性表 上基本運算的實現(xiàn)，進一步理解和熟練掌握課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)，學(xué)會如 何把學(xué)到的知識用于解決實際問題，培養(yǎng)學(xué)生的動手能力關(guān)鍵詞：雙循環(huán)鏈表；插入；刪除；長整數(shù)加減利用雙向循環(huán)鏈表來實現(xiàn)對長整數(shù)的存儲。每個節(jié)點只存儲四位十進制數(shù)字， 即不超過 9999 的非負(fù)整數(shù)。雙向鏈表有頭指針， 它的 data 值存儲長整數(shù)的符號， 1 為正， -1 為負(fù)， 0 代表長整數(shù)為 0 ；它的 over 值存儲除頭節(jié)點外節(jié)點的個數(shù)。 其他節(jié)點的 data 值存儲四位整數(shù)， over 存儲該四位整數(shù)溢出 09999 范圍的情 況，一般 over0 表示四位數(shù)超出 9999 ，overnext;while(

3、p!=head&inext; i+;if(i!=n)printf( 插入位置錯誤 n);return 0;3. 加法函數(shù)設(shè)計思路 ：先將各位做加減， 然后根據(jù)所得長整數(shù)正負(fù)和各結(jié)點 data 值進位或退位計算 所得長整數(shù)的值并輸出。void add(DLNode *h1,DLNode *h2) /兩數(shù)相加 DLNode *p1=h1-prior,*p2=h2-prior;while(p1!=h1&p2!=h2) / 每個鏈表元素相加 p1-data+=p2-data ;p1=p1-prior; p2=p2-prior; p1=h1-prior;while(p1!=h1-next) / 處理鏈表

4、元素 if(p1-data=10000) p1-prior-data+=p1-data/10000;p1-data%=10000; if(p1-datanext!=0) p1-prior-data-=1;p1-data+=10000; p1=p1-prior; if(h1-next-data=10000) / 處理最前面的數(shù) InsertNode(h1,0,h1-next-data/10000);h1-next-next-data%=10000; if(h1-datanext-data/10000);h1-next-next-data%=-10000; PrintNode(h1); 4. 減法

5、函數(shù)設(shè)計思路：void jian(DLNode *h1,DLNode *h2) /兩數(shù)相減 DLNode *p1=h1-prior,*p2=h2-prior;while(p1!=h1&p2!=h2) /每個鏈表元素相減 p1-data-=p2-data ;p1=p1-prior;p2=p2-prior; p1=h1-prior;while(p1!=h1-next) / 處理鏈表元素 if(p1-data=10000) p1-prior-data+=p1-data/10000;p1-data%=10000; if(p1-datanext!=0) p1-prior-data-=1;p1-data+

6、=10000; p1=p1-prior; if(h1-next-data=10000) / 處理最前面的數(shù) InsertNode(h1,0,h1-next-data/10000);h1-next-next-data%=10000; if(h1-datanext-data/-10000); h1-next-next-data%=-10000; PrintNode(h1); 3. 函數(shù)的調(diào)用關(guān)系圖4. 調(diào)試分析a、調(diào)試中遇到的問題及對問題的解決方法調(diào)試過程中的困難：在數(shù)據(jù)的運算中，應(yīng)為是根據(jù)數(shù)的大小來選擇運算的，所以過程相對比較繁 瑣。而且對于雙向鏈表的兩個指針的定位以及鏈表的插入和刪除等操作花費

7、的較 多的時間。在這查閱參照了大量的網(wǎng)絡(luò)資料。b、算法的時間復(fù)雜度和空間復(fù)雜度 由于鏈表采用雙向循環(huán)鏈表結(jié)構(gòu)，可以從鏈表兩頭操作，各種操作的算法時 間復(fù)雜度比較合理，各函數(shù)以及確定鏈表中的結(jié)點位置都是O （n）,n 為鏈表長度。5. 測試結(jié)果a、輸入 0和 0 做加法運算，輸出“ 0”，結(jié)果如下圖：b、 輸入 2345 ，6789 和-7654 ，3211 做減法運算，輸出“1，0000 ，0000 ”， 結(jié)果如下圖：c、輸入 1 ，0000 ，0000 ，0000 和 9999 ，9999 做減法運算， 輸出“9999 ，0000 ， 0001 ”，結(jié)果如下圖：d、輸入 1，0001 ，00

8、01 和1，0001 ，0001 做減法運算，輸出“ 0”，結(jié)果如下圖：e、輸入 1,2345,6789 和 9,8765,4321 做加法運算，結(jié)果如下圖：6. 源程序(帶注釋)#include#include#include#include#define N 100 typedef int DataType;typedef struct DoubleNode /定義鏈表元素 DataType data;struct DoubleNode *prior;struct DoubleNode *next; DLNode;void InitNode(DLNode *head) / 初始化鏈表 if

9、(*head=(DLNode*)malloc(sizeof(DLNode)=NULL)exit(1);(*head)-prior=*head;(*head)-next=*head;int InsertNode(DLNode *head,int n,DataType x) / 向鏈表第 N 個位置插入 元素 X DLNode *p,*nt;int i=0;p=head-next;while(p!=head&inext; i+;if(i!=n)printf( 插入位置錯誤 n);return 0;if(nt=(DLNode *)malloc(sizeof(DLNode)=NULL)exit(1);

10、nt-data=x;nt-prior=p-prior;nt-prior-next=nt;nt-next=p;p-prior=nt;return 1;int digit(int n) /判斷整數(shù) N 有幾位int i;for(i=1;n/=10,i+)if(n/10=0)return i;void PrintNode(DLNode *head) / 打印鏈表 DLNode *p=head-next;int i;while(p-data=0) / 去掉前面的一串 0 p=p-next;if(p=head) printf(0n);return;printf(%d,p-data); / 最前面的一個數(shù)

11、進行特殊處理 ,不用補零p=p-next;while(p!=head) / 打印后面的數(shù)字 printf(,);if(p-data=0)printf(0000);p=p-next;continue;for(i=0;idata);i+) /補零printf(0);printf(%d,p-data);p=p-next;printf(n);void DestroyNode(DLNode *head) DLNode *p,*p1; p=(*head)-next;while(p!=*head) p1=p;p=p-next;free(p1);free(p);head=NULL;void add(DLNod

12、e *h1,DLNode *h2) / 兩數(shù)相加 DLNode *p1=h1-prior,*p2=h2-prior;while(p1!=h1&p2!=h2) /每個鏈表元素相加 p1-data+=p2-data ;p1=p1-prior; p2=p2-prior; p1=h1-prior;while(p1!=h1-next) /處理鏈表元素 if(p1-data=10000) p1-prior-data+=p1-data/10000;p1-data%=10000; if(p1-datanext!=0) p1-prior-data-=1;p1-data+=10000; 處理最前面的數(shù) p1=p1

13、-prior; if(h1-next-data=10000) / InsertNode(h1,0,h1-next-data/10000);h1-next-next-data%=10000; if(h1-datanext-data/10000);h1-next-next-data%=-10000; PrintNode(h1); void jian(DLNode *h2,DLNode *h1) /兩數(shù)相減 DLNode *p1=h1-prior,*p2=h2-prior;while(p1!=h1&p2!=h2) /每個鏈表元素相減 p1-data-=p2-data ;p1=p1-prior;p2=

14、p2-prior; p1=h1-prior;while(p1!=h1-next) /處理鏈表元素 if(p1-data=10000) p1-prior-data+=p1-data/10000;p1-data%=10000; if(p1-datanext!=0) p1-prior-data-=1;p1-data+=10000; p1=p1-prior; if(h1-next-data=10000) / 處理最前面的數(shù) InsertNode(h1,0,h1-next-data/10000); h1-next-next-data%=10000; if(h1-datanext-data/-10000)

15、;h1-next-next-data%=-10000; PrintNode(h1); int main() / 入口函數(shù)DLNode *head1,*head2;char data1N,data2N;char d110,d210;int i,j,k;int xun;InitNode(&head1);InitNode(&head2);while(1) printf( 輸入數(shù)據(jù)： n);scanf(%s %s,data1,data2);InitNode(&head1);InitNode(&head2);i=0;k=0;while(data1i!=;) / 將數(shù) 1 用鏈表儲存 for(j=0;j1

16、0;j+)d1j=0;j=0;while(data1i!=;&data1i!=,)d1j+=data1i+;if(data1i=,)i+;if(data10=-) / 處理正負(fù)數(shù)j=-(int)fabs(atoi(d1);else j=atoi(d1);InsertNode(head1,k+,j);i=0;k=0;while(data2i!=;) / 將數(shù) 2 用鏈表儲存 for(j=0;jstrlen(data2) /add(head1,head2);else add(head2,head1);break;case 2:if(strlen(data1)strlen(data2) /jian(

17、head1,head2);else jian(head2,head1);break;default:break;DestroyNode(&head1);DestroyNode(&head2); return 0;關(guān)于實驗本身的收獲是掌握了雙向鏈表， 通過該題目的設(shè)計過程，可以加深 理解線性表的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)，掌握線性表上基本運算的實現(xiàn)，進一步理 解和熟練掌握課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)， 學(xué)會如何把學(xué)到的知識用于解決實 際問題，培養(yǎng)學(xué)生的動手能力。 而實驗外的就是更好的利用了網(wǎng)路資源，通過網(wǎng) 絡(luò)的搜索引擎等。 加深了自己在這方面知識的補充。 并且在于同學(xué)交流中分析了彼此 算法的優(yōu)劣程度。我覺得

18、這是本次實驗最大的收獲。參考文獻1 嚴(yán)蔚敏，吳偉民 .數(shù)據(jù)結(jié)構(gòu)（ C 語言版） .清華大學(xué)出版社 .2 嚴(yán)蔚敏，吳偉民 .數(shù)據(jù)結(jié)構(gòu)題集（ C 語言版）. 清華大學(xué)出版社 .3 DATA STRUCTURE WITH C+ . William Ford,William Topp . 清華大學(xué)出版社（影印版） .4 譚浩強 . c 語言程序設(shè)計 . 清華大學(xué)出版社 .5 數(shù)據(jù)結(jié)構(gòu)與算法分析（ Java 版） , A Practical Introduction to Data Structures and Algorithm Analysis Java Edition Clifford A. Shaffer , 張銘,劉曉丹譯 電子工業(yè)出版社 2001 年1 月致謝首先，我要感謝我的算法與數(shù)據(jù)結(jié)構(gòu)及課程設(shè)計老師王連相老師，謝謝 王老師對我的諄諄教導(dǎo)，讓我懂得了算法與數(shù)據(jù)結(jié)構(gòu)的理論知識，為我做課 程設(shè)計奠定了理論基礎(chǔ)。另外，感謝王老師在我做課程設(shè)計的過程中給我提出的 寶貴意見和建議，我根據(jù)王老師的建議對我的程序進行了改