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

可編輯版/一、需求分析[問題描述]設(shè)計一個程序?qū)崿F(xiàn)兩個任意長的整數(shù)求和運算。[基本要求]利用雙向循環(huán)鏈表實現(xiàn)長整數(shù)的存儲,每個結(jié)點含一個整型變量。任何整型變量的范圍是：-〔215-1~〔215-1。輸入和輸出形式：按中國對于長整數(shù)的表示習(xí)慣,每四位一組,組間用逗號隔開。[測試數(shù)據(jù)]〔10；0；應(yīng)輸出"0”?！?–2345,6789；-7654,3211；應(yīng)輸出"-1,0000,0000”。〔3–9999,9999；1,0000,0000,0000；應(yīng)輸出"9999,0000,0001”?！?1,0001,0001；-1,0001,0001；應(yīng)輸出"0”。〔51,0001,0001；-1,0001,0000；應(yīng)輸出"1”。二、設(shè)計1.設(shè)計思想〔1存儲結(jié)構(gòu)：循環(huán)雙向鏈表〔2主要算法基本思想：1、每個結(jié)點中可以存放的最大整數(shù)為215-1=32767,才能保證兩數(shù)相加不會溢出。但若這樣存,即相當(dāng)于按32768進制數(shù)存,在十進制數(shù)與32768進制數(shù)之間的轉(zhuǎn)換十分不方便。故可以在每個結(jié)點中僅存十進制數(shù)4位,即不超過9999的非負(fù)整數(shù),整個鏈表視為萬進制數(shù)。2、可以利用頭結(jié)點數(shù)據(jù)域的符號代表長整數(shù)的符號。用其絕對值表示元素結(jié)點數(shù)目。相加過程中不要破壞兩個操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡化程序結(jié)構(gòu)的一種方法。不能給長整數(shù)位數(shù)規(guī)定上限。2.設(shè)計表示〔1函數(shù)調(diào)用關(guān)系圖：〔2函數(shù)接口規(guī)格說明：結(jié)構(gòu)體：structdl_node{ intx; dl_node*pre; dl_node*next;};初始化：voidlist_init<dl_node**h>插入元素：voidlist_insert<dl_node*h,intx>輸出鏈表：voidprin<dl_node*h>實現(xiàn)相加：voidlist_add<dl_node*h1,dl_node*h2>實現(xiàn)相減：voidlist_sub<dl_node*h1,dl_node*h2>3.詳細(xì)設(shè)計〔1輸入兩個數(shù),用鏈表來存儲。鏈表的頭結(jié)點的數(shù)據(jù)的值為1時,表示的是輸入的數(shù)非負(fù)；為-1時表示輸入的數(shù)是負(fù)數(shù)。

〔2在創(chuàng)建鏈表時,讓高位在鏈表的尾部,低位在鏈表的頭部?！?在做加法時,先判斷兩個數(shù)的符號是否相同,如果相同,在根據(jù)加數(shù)的符號,決定和數(shù)的符號,取兩個數(shù)的絕對值做加法,但是的處理進位?！?如果異號,用一函數(shù)來判斷和的符號,判斷異號的兩個數(shù)相加和的符號,當(dāng)兩個數(shù)的長度不相等時,取較長數(shù)的符號作為和的符號,否則比兩個數(shù)的大小,再決定和的符號?！?異號的兩個數(shù)想加時,先去兩個數(shù)的絕對值,用較大的數(shù)減去較小的數(shù),差作為和的絕對值。如果相應(yīng)的位夠減時,直接做減法,否則借位,但是要注意被借位的值是否為零,如果為零,則繼續(xù)借位?！?輸出最終結(jié)果,輸出數(shù)時,要去掉大數(shù)最前面的零,直到數(shù)的首位不是零時為止。在輸出地位的數(shù)時,有可能某些單元的數(shù)低于四位,必須要在四位數(shù)的高位補零,即四位一個單元輸出?？杖碧幱昧阊a齊。三、調(diào)試分析〔1經(jīng)過不斷的的DEBUG,不斷的輸出看結(jié)果調(diào)試,最終成功〔2經(jīng)驗和體會：通過這次學(xué)習(xí),讓我認(rèn)識到自己在學(xué)習(xí)上的諸多不足。從剛拿到題目到完成整個編程,從理論到實踐,雖然學(xué)到很多的的東西,但是也因為自己知識的不足,不能考慮周全,完全成功的完成此次課程設(shè)計。在認(rèn)識自己的不足后,我便開始認(rèn)真復(fù)習(xí)書本知識,同時與動手能力強的同學(xué)互相交流,讓自己學(xué)到了很多平時上課過程中學(xué)不到的東西。通過這次課程設(shè)計,我深刻的認(rèn)識到,理論知識需要與實踐結(jié)合,才能真正領(lǐng)悟所學(xué)知識。同時我發(fā)現(xiàn),我現(xiàn)在的動手能力不強,所以還要繼續(xù)努力。同時還要學(xué)會獨立思考,才能真正的編出屬于我自己的程序。通過這次實習(xí),敦促我將過去學(xué)習(xí)過的知識進行了溫習(xí),知識只有多鞏固,才能真正的理解與領(lǐng)悟。不論這次課程設(shè)計是否完全成功,我相信它對我的影響還是很大的。這會敦促我在下次課程設(shè)計中,能更好地完成設(shè)計任務(wù)。為自己加油！四、用戶手冊輸入兩整數(shù),從低位起,每四位用逗號隔開,按從高到低位依次輸入,以分號結(jié)束此書的輸入；五、運行結(jié)果運行環(huán)境：code::blocks六、源代碼#include<cstdio>#include<cstring>#include<string>#include<malloc.h>#include<iostream>#include<cstdlib>#include<cmath>usingnamespacestd;//定義一個結(jié)構(gòu)體structdl_node{ intx; dl_node*pre; dl_node*next;};//結(jié)點的初始化voidlist_init<dl_node**h>{ *h=<dl_node*>malloc<sizeof<dl_node>>; <*h>->x=0; <*h>->pre=*h; <*h>->next=*h;}//插入一個元素,循環(huán)雙向鏈表voidlist_insert<dl_node*h,intx>{ 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;}//打印輸出voidprin<dl_node*h>{ //cout<<h->x<<endl; dl_node*p; p=h->next; if<p==h>//如果頭結(jié)點為空,則直接輸出0 { puts<"0">;return; } cout<<p->x; p=p->next; while<p!=h>//循環(huán)雙向鏈表一直往右找,直到找到頭結(jié)點為止 { printf<",%04d",p->x>;//%04d為對齊方式,當(dāng)一個結(jié)點值不足4位則補齊 p=p->next; } //cout<<p->x; puts<"">;}//元素值相加,已處理好h1比h2的長度大于等于h1的長度//最后結(jié)果保存在h1〔即長串中voidlist_add<dl_node*h1,dl_node*h2>{ dl_node*p=h1->pre,*q=h2->pre; inte=0; while<q!=h2> //每次相加,如果有進位則保存到e變量中 { inttmp=p->x+q->x+e; if<tmp>9999> { p->x=tmp%10000; e=tmp/10000; } else p->x=tmp; p=p->pre; q=q->pre; } //p=p->pre;//當(dāng)h1長度大于h2的時候,還要對未相加的部分進行操作 while<p!=h1> { inttmp=p->x+e; if<tmp>9999> { p->x=tmp%10000; e=tmp/10000; } elsep->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; }}//元素值相減方法同相加類似//最后結(jié)果保存在h1〔即長串中voidlist_sub<dl_node*h1,dl_node*h2>{ dl_node*p=h1->pre,*q=h2->pre;//此處flag的值即位借位的值,借位的值為0或者為1,因為減0無關(guān)緊要 intflag=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=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->pre->next=p->next; p->next->pre=p->pre; p=h1->next; }}intmain<>{//freopen<"大數(shù)求和.txt","r",stdin>; while<1> { puts<"">; charc; inta; dl_node*h1,*h2; list_init<&h1>;//輸入元素,直到讀入";"則停止輸入第一個鏈表值 while<1> { //cout<<"asdfa"; scanf<"%d%c",&a,&c>; //cout<<c<<endl; list_insert<h1,a>; if<c==';'>break; }//如果第一個元素小于0,則取正值,并在頭結(jié)點當(dāng)中保存信息 if<h1->next->x<0> { h1->x=-h1->x; h1->next->x=-h1->next->x; } //prin<h1>; list_init<&h2>; intr=0;//相同方法輸入第二個鏈表,碰到";"則停止,并且讀到文件結(jié)束 while<1> { if<scanf<"%d%c",&a,&c>==EOF>{r=1;break;} list_insert<h2,a>; if<c==';'>break; } //cout<<r<<endl;//如果第一個元素小于0,則取正值,并在頭結(jié)點當(dāng)中保存信息 if<h2->next->x<0> { h2->x=-h2->x; h2->next->x=-h2->next->x; }//h1_num和h2_num分別表示長度 inth1_num=h1->x,h2_num=h2->x;//把長的放到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四種情況如果h1等于h2也有四種情況*///其實在此處,可以縮減為6種情況,但為了方便,寫了8種//如果他們的長度不相等,即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ù) elseif<h1_num<0&&h2_num<0> { list_add<h1,h2>; cout<<"-"; prin<h1>; continue; }//如果h1為正而h2為負(fù) elseif<h1_num>0&&h2_num<0> { list_sub<h1,h2>; prin<h1>; continue; }//如果h1為負(fù)而h2為正 elseif<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; }//如果都為負(fù)數(shù) elseif<h1_num<0&&h2_num<0> { list_add<h1,h2>; cout<<"-"; prin<h1>; continue; }//如果h1為正而h2為負(fù) elseif<h1_num>0&&h2_num<0> {//這種情況,如果h1最高結(jié)點元素大于h2的最高元素,那么交換鏈表 if<h1->next->x<h2->next->x> { dl_node*tmp=h1; h1=h2; h2=tmp; //h1_num=h1->x,h2_num=h2->x; //prin<h1>; //prin<h2>;//這種情況得先輸出一個負(fù)號 cout<<"-"; }//交換之后加法還是一樣 list_sub<h1,h2>; prin<h1>; con