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

一、需求分析【問題描述】設(shè)計一個程序?qū)崿F(xiàn)兩個任意長的整數(shù)求和運算?！净疽蟆坷秒p向循環(huán)鏈表實現(xiàn)長整數(shù)的存儲，每個結(jié)點含一個整型變量。任何整型變量的范圍是：-（215-1）（215-1）。輸入和輸出形式： 按中國對于長整數(shù)的表示習(xí)慣，每四位一組，組間用逗號隔開。【測試數(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è)計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的非負整數(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)體：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)實現(xiàn)相加：void list_add(dl_node *h1,dl_node *h2)實現(xiàn)相減：void list_sub(dl_node *h1,dl_node *h2)3. 詳細設(shè)計（1）輸入兩個數(shù)，用鏈表來存儲。鏈表的頭結(jié)點的數(shù)據(jù)的值為1時，表示的是輸入的數(shù)非負；為-1時表示輸入的數(shù)是負數(shù)。（2）在創(chuàng)建鏈表時，讓高位在鏈表的尾部，低位在鏈表的頭部。（3）在做加法時，先判斷兩個數(shù)的符號是否相同，如果相同，在根據(jù)加數(shù)的符號，決定和數(shù)的符號，取兩個數(shù)的絕對值做加法，但是的處理進位。（4）如果異號，用一函數(shù)來判斷和的符號，判斷異號的兩個數(shù)相加和的符號，當(dāng)兩個數(shù)的長度不相等時，取較長數(shù)的符號作為和的符號，否則比兩個數(shù)的大小，再決定和的符號。（5）異號的兩個數(shù)想加時，先去兩個數(shù)的絕對值，用較大的數(shù)減去較小的數(shù)，差作為和的絕對值。如果相應(yīng)的位夠減時，直接做減法，否則借位，但是要注意被借位的值是否為零，如果為零，則繼續(xù)借位。（6）輸出最終結(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#include#include#include#include#include#includeusing namespace std;/ 定義一個結(jié)構(gòu)體struct dl_nodeint x;dl_node *pre;dl_node *next;/結(jié)點的初始化void list_init(dl_node * 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 *h)/coutxnext;if(p=h) /如果頭結(jié)點為空，則直接輸出0puts(0);return;coutx;p=p-next;while(p!=h) /循環(huán)雙向鏈表一直往右找，直到找到頭結(jié)點為止printf(,%04d,p-x); /%04d為對齊方式，當(dāng)一個結(jié)點值不足4位則補齊p=p-next;/coutx;puts();/元素值相加，已處理好h1比h2的長度大于等于h1的長度/最后結(jié)果保存在h1（即長串中）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(tmp9999)p-x=tmp%10000;e=tmp/10000;elsep-x=tmp;p=p-pre;q=q-pre;/p=p-pre;/當(dāng)h1長度大于h2的時候，還要對未相加的部分進行操作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é)果還有進位，那么就要再創(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（即長串中）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;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);/輸入元素，直到讀入 ; 則停止輸入第一個鏈表值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;/相同方法輸入第二個鏈表，碰到 ; 則停止，并且讀到文件結(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分別表示長度int h1_num=h1-x,h2_num=h2-x;/把長的放到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;/如果都為負數(shù)else if(h1_num0&h2_num0)list_add(h1,h2);cout0&h2_num0)list_sub(h1,h2);prin(h1);continue;/如果h1為負而h2為正else if(h1_num0)cout0&h2_num0)list_add(h1,h2);prin(h1);continue;/如果都為負數(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);/這種情況得先輸出一個負號cout-;/交換之后加法還是一樣list