數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)長(zhǎng)整數(shù)運(yùn)算

1、 一、需求分析【問(wèn)題描述】設(shè)計(jì)一個(gè)程序?qū)崿F(xiàn)兩個(gè)任意長(zhǎng)的整數(shù)求和運(yùn)算?！净疽蟆坷秒p向循環(huán)鏈表實(shí)現(xiàn)長(zhǎng)整數(shù)的存儲(chǔ)，每個(gè)結(jié)點(diǎn)含一個(gè)整型變量。任何整型變量的范圍是：-（215-1）（215-1）。輸入和輸出形式： 按中國(guó)對(duì)于長(zhǎng)整數(shù)的表示習(xí)慣，每四位一組，組間用逗號(hào)隔開?！緶y(cè)試數(shù)據(jù)】 （1）0；0；應(yīng)輸出“0”。 （2）2345，6789；-7654，3211；應(yīng)輸出“-1，0000，0000”。 （3）9999，9999；1，0000，0000，0000；應(yīng)輸出“9999，0000，0001”。 （4）1，0001，0001；-1，0001，0001；應(yīng)輸出“0”。 （5）1，0001，0001；

2、-1，0001，0000；應(yīng)輸出“1”。二、設(shè)計(jì)1. 設(shè)計(jì)思想（1）存儲(chǔ)結(jié)構(gòu)：循環(huán)雙向鏈表（2）主要算法基本思想：1、每個(gè)結(jié)點(diǎn)中可以存放的最大整數(shù)為215-1=32767，才能保證兩數(shù)相加不會(huì)溢出。但若這樣存，即相當(dāng)于按32768進(jìn)制數(shù)存，在十進(jìn)制數(shù)與32768進(jìn)制數(shù)之間的轉(zhuǎn)換十分不方便。故可以在每個(gè)結(jié)點(diǎn)中僅存十進(jìn) 制數(shù)4位，即不超過(guò)9999的非負(fù)整數(shù)，整個(gè)鏈表視為萬(wàn)進(jìn)制數(shù)。 2、可以利用頭結(jié)點(diǎn)數(shù)據(jù)域的符號(hào)代表長(zhǎng)整數(shù)的符號(hào)。用其絕對(duì)值表示元素結(jié)點(diǎn)數(shù)目。相加過(guò)程中不要破壞兩個(gè)操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡(jiǎn)化程序結(jié)構(gòu)的一種方法。不能給長(zhǎng)整數(shù)位數(shù)規(guī)定上限。2. 設(shè)計(jì)表示 （1）函數(shù)調(diào)

3、用關(guān)系圖：（2）函數(shù)接口規(guī)格說(shuō)明：結(jié)構(gòu)體：struct dl_nodeint 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)實(shí)現(xiàn)相加：void list_add(dl_node *h1,dl_node *h2)實(shí)現(xiàn)相減：void list_sub(dl_node *h1,dl_node *h2)3. 詳細(xì)設(shè)計(jì)（1）輸入兩個(gè)數(shù)，用鏈表來(lái)存儲(chǔ)。鏈表的頭結(jié)點(diǎn)的數(shù)據(jù)的值為1時(shí)，表示的是輸入的數(shù)非負(fù)；

4、為-1時(shí)表示輸入的數(shù)是負(fù)數(shù)。（2）在創(chuàng)建鏈表時(shí)，讓高位在鏈表的尾部，低位在鏈表的頭部。（3）在做加法時(shí)，先判斷兩個(gè)數(shù)的符號(hào)是否相同，如果相同，在根據(jù)加數(shù)的符號(hào)，決定和數(shù)的符號(hào)，取兩個(gè)數(shù)的絕對(duì)值做加法，但是的處理進(jìn)位。（4）如果異號(hào)，用一函數(shù)來(lái)判斷和的符號(hào)，判斷異號(hào)的兩個(gè)數(shù)相加和的符號(hào)，當(dāng)兩個(gè)數(shù)的長(zhǎng)度不相等時(shí)，取較長(zhǎng)數(shù)的符號(hào)作為和的符號(hào)，否則比兩個(gè)數(shù)的大小，再?zèng)Q定和的符號(hào)。（5）異號(hào)的兩個(gè)數(shù)想加時(shí)，先去兩個(gè)數(shù)的絕對(duì)值，用較大的數(shù)減去較小的數(shù)，差作為和的絕對(duì)值。如果相應(yīng)的位夠減時(shí)，直接做減法，否則借位，但是要注意被借位的值是否為零，如果為零，則繼續(xù)借位。（6）輸出最終結(jié)果，輸出數(shù)時(shí)，要去掉大數(shù)最前

5、面的零，直到數(shù)的首位不是零時(shí)為止。在輸出地位的數(shù)時(shí)，有可能某些單元的數(shù)低于四位，必須要在四位數(shù)的高位補(bǔ)零，即四位一個(gè)單元輸出?？杖碧幱昧阊a(bǔ)齊。三、調(diào)試分析（1）經(jīng)過(guò)不斷的的DEBUG，不斷的輸出看結(jié)果調(diào)試，最終成功（2）經(jīng)驗(yàn)和體會(huì)：通過(guò)這次學(xué)習(xí)，讓我認(rèn)識(shí)到自己在學(xué)習(xí)上的諸多不足。從剛拿到題目到完成整個(gè)編程，從理論到實(shí)踐，雖然學(xué)到很多的的東西，但是也因?yàn)樽约褐R(shí)的不足，不能考慮周全，完全成功的完成此次課程設(shè)計(jì)。在認(rèn)識(shí)自己的不足后，我便開始認(rèn)真復(fù)習(xí)書本知識(shí)，同時(shí)與動(dòng)手能力強(qiáng)的同學(xué)互相交流，讓自己學(xué)到了很多平時(shí)上課過(guò)程中學(xué)不到的東西。通過(guò)這次課程設(shè)計(jì)，我深刻的認(rèn)識(shí)到，理論知識(shí)需要與實(shí)踐結(jié)合，才能真正

6、領(lǐng)悟所學(xué)知識(shí)。同時(shí)我發(fā)現(xiàn)，我現(xiàn)在的動(dòng)手能力不強(qiáng)，所以還要繼續(xù)努力。同時(shí)還要學(xué)會(huì)獨(dú)立思考，才能真正的編出屬于我自己的程序。通過(guò)這次實(shí)習(xí)，敦促我將過(guò)去學(xué)習(xí)過(guò)的知識(shí)進(jìn)行了溫習(xí)，知識(shí)只有多鞏固，才能真正的理解與領(lǐng)悟。不論這次課程設(shè)計(jì)是否完全成功，我相信它對(duì)我的影響還是很大的。這會(huì)敦促我在下次課程設(shè)計(jì)中，能更好地完成設(shè)計(jì)任務(wù)。為自己加油！四、用戶手冊(cè)輸入兩整數(shù)，從低位起，每四位用逗號(hào)隔開，按從高到低位依次輸入，以分號(hào)結(jié)束此書的輸入；五、運(yùn)行結(jié)果 運(yùn)行環(huán)境：code:blocks六、源代碼#include<cstdio>#include<cstring>#include<st

7、ring>#include<malloc.h>#include<iostream>#include<cstdlib>#include<cmath>using namespace std;/ 定義一個(gè)結(jié)構(gòu)體struct dl_nodeint x;dl_node *pre;dl_node *next;/結(jié)點(diǎn)的初始化void list_init(dl_node * h)*h=(dl_node *)malloc(sizeof(dl_node);(*h)->x=0;(*h)->pre=*h;(*h)->next=*h;/插入一個(gè)元素

8、，循環(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 *h)/cout<<h->x<<endl;dl_node *p;p=h->next;if(p=h) /如果頭結(jié)點(diǎn)為空，則直接輸出0puts("0");r

9、eturn;cout<<p->x;p=p->next;while(p!=h) /循環(huán)雙向鏈表一直往右找，直到找到頭結(jié)點(diǎn)為止printf(",%04d",p->x); /%04d為對(duì)齊方式，當(dāng)一個(gè)結(jié)點(diǎn)值不足4位則補(bǔ)齊p=p->next;/cout<<p->x;puts("");/元素值相加，已處理好h1比h2的長(zhǎng)度大于等于h1的長(zhǎng)度/最后結(jié)果保存在h1（即長(zhǎng)串中）void list_add(dl_node *h1,dl_node *h2)dl_node *p=h1->pre,*q=h2->p

10、re;int e=0;while(q!=h2)/每次相加，如果有進(jìn)位則保存到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;/當(dāng)h1長(zhǎng)度大于h2的時(shí)候，還要對(duì)未相加的部分進(jìn)行操作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=h

11、1->next;/如果最高位得到的結(jié)果還有進(jìn)位，那么就要再創(chuàng)建一個(gè)結(jié)點(diǎn)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;/元素值相減 方法同相加類似/最后結(jié)果保存在h1（即長(zhǎng)串中）void list_sub(dl_node *h1,dl_node *h2)dl_node *p=h1->pre,*q=h2->pre;/此處flag的值即位借位的值，借位的值為0或者為1，

12、因?yàn)闇p0無(wú)關(guān)緊要int flag=0;while(q!=h2)if(p->x-flag>=q->x)p->x-=q->x+flag;flag=0;elsep->x=p->x+10000-q->x-flag;/p->pre->x-;flag=1;p=p->pre;q=q->pre;/p=p->pre;/cout<<p->x<<endl;/同樣的，如果h1的長(zhǎng)度大于h2的長(zhǎng)度，那么對(duì)剩下的操作while(p!=h1)if(p->x-flag<0)p->x=p->x+1

13、0000-flag;flag=1;elsep->x=p->x-flag;flag=0;p=p->pre;/cout<<p->x<<endl;/如果最高位為0的話，那么就要?jiǎng)h除最高位的結(jié)點(diǎn)了p=h1->next;while(p->x=0)p->pre->next=p->next;p->next->pre=p->pre;p=h1->next;int main() / freopen("大數(shù)求和.txt","r",stdin);while(1)puts(&qu

14、ot;");char c;int a;dl_node *h1,*h2;list_init(&h1);/輸入元素，直到讀入 " ; "則停止輸入第一個(gè)鏈表值while(1) /cout<<"asdfa"scanf("%d%c",&a,&c);/cout<<c<<endl;list_insert(h1,a);if(c='') break;/如果第一個(gè)元素小于0，則取正值，并在頭結(jié)點(diǎn)當(dāng)中保存信息if(h1->next->x<0)h1-&g

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

16、next->x<0)h2->x=-h2->x;h2->next->x=-h2->next->x;/ h1_num和h2_num分別表示長(zhǎng)度int h1_num=h1->x,h2_num=h2->x;/把長(zhǎng)的放到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<

17、;<endl;/*此處為重點(diǎn)部分，分為兩個(gè)部分，如果h1大于h2四種情況 如果h1等于h2也有四種情況*/其實(shí)在此處，可以縮減為6種情況，但為了方便，寫了8種/如果他們的長(zhǎng)度不相等，即h1大于 h2了if(abs(h1_num)!=abs(h2_num)/如果都為正數(shù)if(h1_num>0&&h2_num>0)/prin(h1);list_add(h1,h2);prin(h1);continue;/如果都為負(fù)數(shù)else if(h1_num<0&&h2_num<0)list_add(h1,h2);cout<<"-

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