長(zhǎng)整數(shù)的運(yùn)算算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告書

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

2、會(huì)如何把學(xué)到的知識(shí)用于解決實(shí)際問題，培養(yǎng)學(xué)生的動(dòng)手能力關(guān)鍵詞：雙循環(huán)鏈表；插入；刪除；長(zhǎng)整數(shù)加減前言利用雙向循環(huán)鏈表來實(shí)現(xiàn)對(duì)長(zhǎng)整數(shù)的存儲(chǔ)。每個(gè)節(jié)點(diǎn)只存儲(chǔ)四位十進(jìn)制數(shù)字，即不超過 9999 的非負(fù)整數(shù)。雙向鏈表有頭指針， 它的 data 值存儲(chǔ)長(zhǎng)整數(shù)的符號(hào)，1 為正， -1 為負(fù)， 0 代表長(zhǎng)整數(shù)為 0 ；它的 over 值存儲(chǔ)除頭節(jié)點(diǎn)外節(jié)點(diǎn)的個(gè)數(shù)。其他節(jié)點(diǎn)的 data 值存儲(chǔ)四位整數(shù)， over 存儲(chǔ)該四位整數(shù)溢出09999范圍的情況，一般 over>0 表示四位數(shù)超出 9999 ，over<0 表示四位數(shù)小于0 。選擇該數(shù)據(jù)結(jié)構(gòu)來完成長(zhǎng)整數(shù)的加減運(yùn)算是因?yàn)橐獙?duì)長(zhǎng)整數(shù)進(jìn)行運(yùn)算，需要

3、對(duì)長(zhǎng)整數(shù)進(jìn)行存儲(chǔ)，所以選擇用鏈表對(duì)長(zhǎng)整數(shù)存儲(chǔ)，又由于存儲(chǔ)的順序是從左到右，而運(yùn)算的順序則是從右到左，這樣位了操作方便選擇循環(huán)鏈表，在運(yùn)算過程中有進(jìn)位和借位的操作，所以最終選擇雙向循環(huán)鏈表的數(shù)據(jù)結(jié)構(gòu)。正文1. 采用類 c 語言定義相關(guān)的數(shù)據(jù)類型typedef struct DoubleNode /定義鏈表元素void InitNode(DLNode *head) /初始化鏈表int InsertNode(DLNode *head,int n,DataType x) /向鏈表第N 個(gè)位置插入元素Xint digit(int n) /判斷整數(shù)N 有幾位void PrintNode(DLNode *h

4、ead) /打印鏈表void DestroyNode(DLNode *head)/銷毀鏈表void add(DLNode *h1,DLNode *h2) /兩數(shù)相加void jian(DLNode *h1,DLNode *h2) /兩數(shù)相減int main() /入口函數(shù)2. 各模塊的偽碼算法1. 宏定義及鏈表定義 ：#define N 100typedef int DataType;typedef struct DoubleNode /定義鏈表元素 DataType data;struct DoubleNode *prior;struct DoubleNode *next; DLNode;v

5、oid InitNode(DLNode *head) /初始化鏈表每個(gè)節(jié)點(diǎn)只存儲(chǔ)四位十進(jìn)制數(shù)字，即不超過9999的非負(fù)整數(shù)。雙向鏈表有頭指針，它的 data 值存儲(chǔ)長(zhǎng)整數(shù)的符號(hào)， 1 為正， -1 為負(fù)， 0 代表長(zhǎng)整數(shù)為 0 ；2. 插入函數(shù)設(shè)計(jì)思路：int InsertNode(DLNode *head,int n,DataType x) /向鏈表第 N 個(gè)位置插入元素 X DLNode *p,*nt; int i=0;p=head->next;while(p!=head&&i<n)p=p->next; i+;if(i!=n)printf(" 插

6、入位置錯(cuò)誤 n");return 0;3. 加法函數(shù)設(shè)計(jì)思路 ：先將各位做加減， 然后根據(jù)所得長(zhǎng)整數(shù)正負(fù)和各結(jié)點(diǎn)data 值進(jìn)位或退位計(jì)算所得長(zhǎng)整數(shù)的值并輸出。void add(DLNode *h1,DLNode *h2) /兩數(shù)相加 DLNode *p1=h1->prior,*p2=h2->prior;while(p1!=h1&&p2!=h2) /每個(gè)鏈表元素相加 p1->data+=p2->data ; p1=p1->prior; p2=p2->prior; p1=h1->prior;while(p1!=h1->ne

7、xt) /處理鏈表元素 if(p1->data>=10000) p1->prior->data+=p1->data/10000;p1->data%=10000; if(p1->data<0) /處理負(fù)數(shù) if(h1->next!=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-&

8、gt;next->next->data%=10000; if(h1->data<=-10000) InsertNode(h1,0,h1->next->data/10000); h1->next->next->data%=-10000; PrintNode(h1); 4. 減法函數(shù)設(shè)計(jì)思路：void jian(DLNode *h1,DLNode *h2) /兩數(shù)相減 DLNode *p1=h1->prior,*p2=h2->prior;while(p1!=h1&&p2!=h2) /每個(gè)鏈表元素相減 p1->d

9、ata-=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->data<0) /處理負(fù)數(shù) if(h1->next!=0) p1->prior->data-=1; p1->data+=10000; p1=p1->prior; if(

10、h1->next->data>=10000) /處理最前面的數(shù) InsertNode(h1,0,h1->next->data/10000); h1->next->next->data%=10000; if(h1->data<=-10000) InsertNode(h1,0,h1->next->data/-10000); h1->next->next->data%=-10000; PrintNode(h1); 3. 函數(shù)的調(diào)用關(guān)系圖開始主函數(shù)建立運(yùn)算建立鏈表調(diào) 運(yùn)voidadd(DLNode調(diào)運(yùn)void*h

11、1,DLNode *h2)InitNode(DLNode *h1)主函數(shù)結(jié) 束4. 調(diào)試分析a、調(diào)試中遇到的問題及對(duì)問題的解決方法調(diào)試過程中的困難：在數(shù)據(jù)的運(yùn)算中，應(yīng)為是根據(jù)數(shù)的大小來選擇運(yùn)算的，所以過程相對(duì)比較繁瑣。而且對(duì)于雙向鏈表的兩個(gè)指針的定位以及鏈表的插入和刪除等操作花費(fèi)的較多的時(shí)間。在這查閱參照了大量的網(wǎng)絡(luò)資料。b 、算法的時(shí)間復(fù)雜度和空間復(fù)雜度由于鏈表采用雙向循環(huán)鏈表結(jié)構(gòu)，可以從鏈表兩頭操作，各種操作的算法時(shí)間復(fù)雜度比較合理，各函數(shù)以及確定鏈表中的結(jié)點(diǎn)位置都是O （n ）,n 為鏈表長(zhǎng)度。5. 測(cè)試結(jié)果a、輸入 0 和 0 做加法運(yùn)算，輸出“ 0 ”，結(jié)果如下圖：b 、輸入 234

12、5 ，6789 和-7654 ，3211 做減法運(yùn)算，輸出“ 1 ，0000 ，0000 ”，結(jié)果如下圖：c、 輸入 1 ，0000 ，0000 ，0000 和 9999 ，9999 做減法運(yùn)算， 輸出“9999 ，0000 ， 0001 ”，結(jié)果如下圖：d 、輸入 1 ，0001 ，0001 和 1 ，0001 ，0001 做減法運(yùn)算，輸出“ 0 ”，結(jié)果如下圖：e、 輸入 1,2345,6789和 9,8765,4321做加法運(yùn)算，結(jié)果如下圖：6. 源程序（帶注釋）#include<stdio.h>#include<string.h>#include<stdl

13、ib.h>#include<math.h>#define N 100typedef int DataType;typedef struct DoubleNode /定義鏈表元素 DataType data;struct DoubleNode *prior;struct DoubleNode *next; DLNode;void InitNode(DLNode *head) / 初始化鏈表if(*head=(DLNode*)malloc(sizeof(DLNode)=NULL)exit(1);(*head)->prior=*head;(*head)->next=*h

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

15、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",

16、p->data); /最前面的一個(gè)數(shù)進(jìn)行特殊處理,不用補(bǔ)零p=p->next;while(p!=head) /打印后面的數(shù)字 printf(",");if(p->data=0)printf("0000");p=p->next;continue;for(i=0;i<4-digit(p->data);i+) /printf("0");printf("%d",p->data);p=p->next;printf("n");void DestroyNode(

17、DLNode *head) DLNode *p,*p1;p=(*head)->next;while(p!=*head)補(bǔ)零 p1=p; p=p->next; free(p1);free(p);head=NULL;void add(DLNode *h1,DLNode *h2) /兩數(shù)相加 DLNode *p1=h1->prior,*p2=h2->prior;while(p1!=h1&&p2!=h2) /每個(gè)鏈表元素相加 p1->data+=p2->data ; p1=p1->prior; p2=p2->prior; p1=h1-&g

18、t;prior;while(p1!=h1->next) /處理鏈表元素 if(p1->data>=10000) p1->prior->data+=p1->data/10000;p1->data%=10000; if(p1->data<0) /處理負(fù)數(shù) if(h1->next!=0) p1->prior->data-=1;p1->data+=10000; p1=p1->prior; if(h1->next->data>=10000) /處理最前面的數(shù) InsertNode(h1,0,h1->

19、;next->data/10000); h1->next->next->data%=10000; if(h1->data<=-10000) InsertNode(h1,0,h1->next->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) /每個(gè)鏈

20、表元素相減 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->data<0) /處理負(fù)數(shù) if(h1->next!=0) p1->prior->data-=1; p1->data+=10000; p1=p1-

21、>prior; if(h1->next->data>=10000) /處理最前面的數(shù) InsertNode(h1,0,h1->next->data/10000); h1->next->next->data%=10000; if(h1->data<=-10000) InsertNode(h1,0,h1->next->data/-10000); h1->next->next->data%=-10000; PrintNode(h1); int main() /入口函數(shù)DLNode *head1,*head

22、2;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 用鏈表儲(chǔ)存for(j=0;j<10;j+)d1j=0;j=0;while(data1i!=

23、''&&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 用鏈表儲(chǔ)存for(j=0;j<10;j+)d2j=0; j=0;while(data2i!=''&&data2i!=',')d2j

24、+=data2i+;if(data2i=',') i+;if(data20='-') /處理正負(fù)數(shù)j=-(int)fabs(atoi(d2);else j=atoi(d2);InsertNode(head2,k+,j); printf(" 選擇加減法： 1- 加法， 2- 減法 n");scanf("%d",&xun);switch(xun)case 1:if(strlen(data1)>strlen(data2) /較長(zhǎng)的數(shù)作為被加數(shù)add(head1,head2);else add(head2,head1

25、);break;case 2:if(strlen(data1)>strlen(data2) /較長(zhǎng)的數(shù)作為被減數(shù)jian(head1,head2);else jian(head2,head1);break;default:break;DestroyNode(&head1);DestroyNode(&head2); return 0;總結(jié)關(guān)于實(shí)驗(yàn)本身的收獲是掌握了雙向鏈表，通過該題目的設(shè)計(jì)過程，可以加深理解線性表的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)，掌握線性表上基本運(yùn)算的實(shí)現(xiàn)，進(jìn)一步理解和熟練掌握課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)，學(xué)會(huì)如何把學(xué)到的知識(shí)用于解決實(shí)際問題，培養(yǎng)學(xué)生的動(dòng)手能力。而實(shí)驗(yàn)外的就是更好的利