數(shù)據(jù)結(jié)構(gòu)課程設計長整數(shù)運算

1、、需求分析問題描述】設計一個程序?qū)崿F(xiàn)兩個任意長的整數(shù)求和運算【基本要求】 利用雙向循環(huán)鏈表實現(xiàn)長整數(shù)的存儲，每個結(jié)點含一個整型變量。任何整型變量的范圍是： -(215-1)(215-1)。輸入和輸出形式： 按中國對于 長整數(shù)的表示習慣，每四位一組，組間用逗號隔開。測試數(shù)據(jù)】(1) 0；0；應輸出“ 0”。(2) -345, 6789; -7654, 3211;應輸出“ -1, 0000, 0000”。(3) £999, 9999; 1, 0000, 0000, 0000;應輸出 “9999 0000, 0001”。(4) 1, 0001, 0001; -1, 0001, 0001;應

2、輸出“ 0”。(5) 1, 0001, 0001; -1, 0001, 0000;應輸出“ 1”。二、設計1. 設計思想( 1 )存儲結(jié)構(gòu)：循環(huán)雙向鏈表( 2)主要算法基本思想：1 、每個結(jié)點中可以存放的最大整數(shù)為 215-1=32767,才能保證兩數(shù)相加 不會溢出。但若這樣存,即相當于按 32768進制數(shù)存,在十進制數(shù)與 32768 進制數(shù)之間的轉(zhuǎn)換十分不方便。故可以在每個結(jié)點中僅存十進 制數(shù) 4 位, 即不超過 9999的非負整數(shù),整個鏈表視為萬進制數(shù)。2、可以利用頭結(jié)點數(shù)據(jù)域的符號代表長整數(shù)的符號。用其絕對值表示 元素結(jié)點數(shù)目。相加過程中不要破壞兩個操作數(shù)鏈表。兩操作數(shù)的頭指針存 于指針

3、數(shù)組中是簡化程序結(jié)構(gòu)的一種方法。不能給長整數(shù)位數(shù)規(guī)定上限。2. 設計表示( 1 )函數(shù)調(diào)用關(guān)系圖：( 2)函數(shù)接口規(guī)格說明：結(jié)構(gòu)體： struct dl_node int x; dl_node *pre;dl_node *next;初始化：void list_init(dl_node * h)插入元素：void list_insert(dl_node *h,int x)輸出鏈表：void prin(dl_node *h)實現(xiàn)相加：void list_add(dl_node *h1,dl_node *h2)實現(xiàn)相減：void list_sub(dl_node *h1,dl_node *h2)3.

4、 詳細設計（1）輸入兩個數(shù)，用鏈表來存儲。鏈表的頭結(jié)點的數(shù)據(jù)的值為1 時，表示的是輸入的數(shù)非負；為 -1 時表示輸入的數(shù)是負數(shù)。（ 2）在創(chuàng)建鏈表時，讓高位在鏈表的尾部，低位在鏈表的頭部。（3）在做加法時，先判斷兩個數(shù)的符號是否相同，如果相同，在根據(jù)加數(shù)的符 號，決定和數(shù)的符號，取兩個數(shù)的絕對值做加法，但是的處理進位。（4）如果異號，用一函數(shù)來判斷和的符號，判斷異號的兩個數(shù)相加和的符號， 當兩個數(shù)的長度不相等時， 取較長數(shù)的符號作為和的符號， 否則比兩個數(shù)的大小， 再決定和的符號。（5）異號的兩個數(shù)想加時，先去兩個數(shù)的絕對值，用較大的數(shù)減去較小的數(shù)， 差作為和的絕對值。如果相應的位夠減時，直接

5、做減法，否則借位，但是要注意 被借位的值是否為零，如果為零，則繼續(xù)借位。（6）輸出最終結(jié)果，輸出數(shù)時，要去掉大數(shù)最前面的零，直到數(shù)的首位不是零 時為止。 在輸出地位的數(shù)時， 有可能某些單元的數(shù)低于四位， 必須要在四位數(shù)的 高位補零，即四位一個單元輸出?？杖碧幱昧阊a齊。三、調(diào)試分析（ 1）經(jīng)過不斷的的 DEBUG ，不斷的輸出看結(jié)果調(diào)試，最終成功（ 2）經(jīng)驗和體會：通過這次學習， 讓我認識到自己在學習上的諸多不足。 從剛拿到題目到完成 整個編程，從理論到實踐， 雖然學到很多的的東西， 但是也因為自己知識的不足， 不能考慮周全， 完全成功的完成此次課程設計。 在認識自己的不足后， 我便開始 認真復

6、習書本知識， 同時與動手能力強的同學互相交流， 讓自己學到了很多平時 上課過程中學不到的東西。通過這次課程設計， 我深刻的認識到， 理論知識需要與實踐結(jié)合， 才能真正 領悟所學知識。同時我發(fā)現(xiàn)，我現(xiàn)在的動手能力不強，所以還要繼續(xù)努力。同時 還要學會獨立思考，才能真正的編出屬于我自己的程序。通過這次實習，敦促我將過去學習過的知識進行了溫習，知識只有多鞏固， 才能真正的理解與領悟。不論這次課程設計是否完全成功， 我相信它對我的影響還是很大的。 這會敦 促我在下次課程設計中，能更好地完成設計任務。為自己加油！四、用戶手冊 輸入兩整數(shù)，從低位起，每四位用逗號隔開，按從高到低位依次輸入，以分 號結(jié)束此書

7、的輸入；五、運行結(jié)果運行環(huán)境： code:blocks六、源代碼#include<cstdio>#include<cstring>#include<string>#include<malloc.h> #include<iostream>#include<cstdlib> #include<cmath> using namespace std;/ 定義一個結(jié)構(gòu)體 struct dl_node int x;dl_node *pre;dl_node *next;/結(jié)點的初始化 void list_init(dl_no

8、de * h)*h=(dl_node *)malloc(sizeof(dl_node); (*h)->x=0;(*h)->pre=*h; (*h)->next=*h;/插入一個元素，循環(huán)雙向鏈表 void list_insert(dl_node *h,int x) h->x+;dl_node *s;s=(dl_node *)malloc(sizeof(dl_node); s->x=x;s->pre=h->pre; h->pre->next=s;s->next=h; h->pre=s;/打印輸出void prin(dl_node

9、*h)/cout<<h->x<<endl;dl_node *p;p=h->next;if(p=h) /如果頭結(jié)點為空，則直接輸出 0puts("0");return;cout<<p->x;p=p->next;while(p!=h) /循環(huán)雙向鏈表一直往右找，直到找到頭結(jié)點為止 printf(",%04d",p->x); /%04d 為對齊方式，當一個結(jié)點值不足 4位則補齊 p=p->next;/cout<<p->x;puts("");/元素值相加

10、，已處理好hl比h2的長度大于等于hl的長度/最后結(jié)果保存在hl (即長串中)void list_add(dl_node *h1,dl_node *h2)dl_node *p=h1->pre,*q=h2->pre;int e=0;while(q!=h2)/每次相加，如果有進位則保存到 e 變量中int tmp=p->x+q->x+e; if(tmp>9999) p->x=tmp%10000; e=tmp/10000;elsep->x=tmp;p=p->pre;q=q->pre;/p=p->pre;/當hl長度大于h2的時候，還要對未相

11、加的部分進行操作 while(p!=h1)int tmp=p->x+e; if(tmp>9999) p->x=tmp%10000; e=tmp/10000;else p->x=tmp; p=p->pre; p=h1->next;/如果最高位得到的結(jié)果還有進位，那么就要再創(chuàng)建一個結(jié)點 if(e!=0)dl_node *s;s=(dl_node *)malloc(sizeof(dl_node); s->x=e;s->pre=p->pre; p->pre->next=s; s->next=p; p->pre=s;/元素值相

12、減 方法同相加類似/最后結(jié)果保存在hl (即長串中)void list_sub(dl_node *h1,dl_node *h2) dl_node *p=h1->pre,*q=h2->pre;此處flag的值即位借位的值，借位的值為 0或者為1,因為減0無關(guān)緊要 int flag=0;while(q!=h2)if(p->x-flag>=q->x)p->x-=q->x+flag;flag=0;else p->x=p->x+10000-q->x-flag; /p->pre->x-; flag=1; p=p->pre; q=

13、q->pre; /p=p->pre; /cout<<p->x<<endl;/同樣的，如果 h1 的長度大于 h2 的長度，那么對剩下的操作 while(p!=h1)if(p->x-flag<0) p->x=p->x+10000-flag; flag=1;else p->x=p->x-flag; flag=0; p=p->pre;/cout<<p->x<<endl;/如果最高位為 0 的話，那么就要刪除最高位的結(jié)點了 p=h1->next;while(p->x=0) p-

14、>pre->next=p->next; p->next->pre=p->pre; p=h1->next;int main()/ freopen("大數(shù)求和.txt","r",stdin);while(1)puts("");char c;int a;dl_node *h1,*h2;list_init(&h1); /輸入元素，直到讀入" ; " 則停止輸入第一個鏈表值while(1)/cout<<"asdfa" scanf("%

15、d%c",&a,&c); /cout<<c<<endl;list_insert(h1,a); if(c='') break; /如果第一個元素小于 0，則取正值，并在頭結(jié)點當中保存信息 if(h1->next->x<0) h1->x=-h1->x; h1->next->x=-h1->next->x;/prin(h1); list_init(&h2);int r=0;/相同方法輸入第二個鏈表，碰到" ; "則停止，并且讀到文件結(jié)束while(1) i

16、f(scanf("%d%c",&a,&c)=EOF) r=1;break; list_insert(h2,a);if(c='')break;/cout<<r<<endl;/如果第一個元素小于 0，則取正值，并在頭結(jié)點當中保存信息 if(h2->next->x<0) h2->x=-h2->x; h2->next->x=-h2->next->x;/ h1_num 和 h2_num 分別表示長度int h1_num=h1->x,h2_num=h2->x;/把長

17、的放到 h1 里面，是為了后面的加減操作更順利 if(abs(h1_num)<abs(h2_num)dl_node *tmp=h1; h1=h2;h2=tmp;h1_num=h1->x,h2_num=h2->x; /cout<<h1_num<<" "<<h2_num<<endl;/*此處為重點部分，分為兩個部分，如果 h1 大于 h2 四種情況 如果hl等于h2也有四種情況*/其實在此處，可以縮減為 6 種情況，但為了方便，寫了 8種如果他們的長度不相等，即hl大于h2 了 if(abs(h1_num)!=a

18、bs(h2_num) /如果都為正數(shù)if(h1_num>0&&h2_num>0)/prin(h1);list_add(h1,h2);prin(h1); continue;/如果都為負數(shù)else if(h1_num<0&&h2_num<0) list_add(h1,h2);cout<<"-"prin(h1); continue;/如果 h1 為正而 h2 為負else if(h1_num>0&&h2_num<0)list_sub(h1,h2);prin(h1); continue;/如果 h1 為負而 h2 為正else if(h1_num<0&&h2_num>0)cout<<"-" list_sub(h1,h2); prin(h1);/否則，如果他們長度都相等的話：else/如果都為正數(shù)if(h1_num>0&&h2_num>0) list_add(h1,h2); prin(h1); continue;/如果都為負數(shù)else if(h1_num<0&&h2_num<0) list_add(h1,h2); cout<