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

一、需求分析【問(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)隔開(kāi)?！緶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；-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)用關(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ù)；為-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ù)最前面的零，直到數(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í)自己的不足后，我便開(kāi)始認(rèn)真復(fù)習(xí)書(shū)本知識(shí)，同時(shí)與動(dòng)手能力強(qiáng)的同學(xué)互相交流，讓自己學(xué)到了很多平時(shí)上課過(guò)程中學(xué)不到的東西。通過(guò)這次課程設(shè)計(jì)，我深刻的認(rèn)識(shí)到，理論知識(shí)需要與實(shí)踐結(jié)合，才能真正領(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)隔開(kāi)，按從高到低位依次輸入，以分號(hào)結(jié)束此書(shū)的輸入；五、運(yùn)行結(jié)果 運(yùn)行環(huán)境：code:blocks六、源代碼#include#include#include#include#include#include#includeusing 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è)元素，循環(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)/coutxnext;if(p=h) /如果頭結(jié)點(diǎn)為空，則直接輸出0puts(0);return;coutx;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;/coutx;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-pre;int e=0;while(q!=h2)/每次相加，如果有進(jìn)位則保存到e變量中int tmp=p-x+q-x+e;if(tmp9999)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(tmp9999)p-x=tmp%10000;e=tmp/10000;else p-x=tmp;p=p-pre;p=h1-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，因?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;/coutxx-flagx=p-x+10000-flag;flag=1;elsep-x=p-x-flag;flag=0;p=p-pre;/coutxnext;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();char c;int a;dl_node *h1,*h2;list_init(&h1);/輸入元素，直到讀入 ; 則停止輸入第一個(gè)鏈表值while(1) /coutasdfa;scanf(%d%c,&a,&c);/coutcnext-xx=-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;/coutrnext-xx=-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)x,h2_num=h2-x;/couth1_num h2_num0&h2_num0)/prin(h1);list_add(h1,h2);prin(h1);continue;/如果都為負(fù)數(shù)else if(h1_num0&h2_num0)list_add(h1,h2);cout0&h2_num0)list_sub(h1,h2);prin(h1);continue;/如果h1為負(fù)而h2為正else if(h1_num0)cout0&h2_num0)list_add(h1,h2);prin(h1);continue;/如果都為負(fù)數(shù)else if(h1_num0&h2_num0)list_add(h1,h2);cout0&h2_numnext-xnext-x)dl_node *tmp=h1;h1=h2;h2=tmp;/h1_num=h1-x,h2_num=h2-x;/prin(h1);/prin(h2);/這種情況得先輸出一個(gè)負(fù)號(hào)cout-;/交換之后加法還是一樣list