題目：設計一個實現(xiàn)任意長的整數(shù)的加法運算的演示程序
一、需求分析
本演示程序中，利用雙向循環(huán)鏈表來實現(xiàn)長整數(shù)的儲存，每個節(jié)點含一個整型變量。輸入和輸出形式按照中國對于長整數(shù)的表示習慣，每四位一組，組間用逗號隔開；其中輸入的兩個長整數(shù)用 ';' (英語輸入法)結尾，允許逗號位置錯誤，并在輸入非法字符是提示錯誤。
2.測試數(shù)據(jù)
（1）0;0;應輸出“0”。
（2）-2345,6789;-7654,3211;應輸出“-1,0000,0000”
（3）-9999,9999;1,0000,0000,0000;應輸出“9999,0000,0001”
（4）1,0001,0001;-1,0001,0001;應輸出“0”
（5）1,0001,0001;-1,0001,0000;應輸出“1”
（6）-9999,9999,9999;-9999,9999,9999;應輸出“-1,9999,9999,9998”
（7）1,0000,9999,9999;1;應輸出“1,0001,0000,0000”
二、概要設計
1.數(shù)據(jù)結構
為實現(xiàn)上述程序功能，采用雙向循環(huán)鏈表來儲存長整數(shù)。
雙向循環(huán)鏈表的儲存結構:
typedef struct node{
int info;
struct node *prior,*next;
}DLink;
利用頭結點的數(shù)據(jù)域符號來表示長整數(shù)的符號，大小表示長整數(shù)長度。
2.使用函數(shù)
DLink *Dcreat()
操作結果：初始化儲存長整數(shù)的雙向循環(huán)鏈表
DLink *addition(DLink *a, DLink *b)
操作結果：實現(xiàn)同符號長整數(shù)的加法操作
DLink *subtraction(DLink *a, DLink *b)
操作結果：實現(xiàn)異號號長整數(shù)的加法操作
void printDlink(DLink *head)
操作結果：實現(xiàn)長整數(shù)的中國表示方法輸出
void main()
操作結果：主函數(shù)，調(diào)用以上函數(shù)進行加法運算
三、詳細設計
1.讀入數(shù)據(jù)初始化雙向循環(huán)鏈表函數(shù)
采用getchar()從屏幕上讀取字符，定義flag變量表示輸入是否合法，對于不合法的輸入將鏈表頭結點數(shù)據(jù)域(head->info)置為0；對于正規(guī)輸入構成鏈表的頭結點數(shù)據(jù)域為:長整數(shù)長度×符號，長整數(shù)長度（len）在循環(huán)讀入字符時確定，將讀入的','以及'-'外每一位字符轉化為int型，存在鏈表節(jié)點的數(shù)據(jù)域中，實現(xiàn)如下:
DLink *Dcreat()
{
DLink *head,*p,*last;
int flag = 0; //輸入是否合法
char c;
int num;
int len = 0;//長整數(shù)長度
head=(DLink *)malloc(sizeof(DLink));
head->next = NULL;
head->prior = NULL;
head->info = 1;//起始符號位為1
last = head;
while((c=getchar())!=';')
{
if(c=='-')
{
head->info = -1;//符號位
continue;
}
if(c==',')
{
continue;
}
num = c - '0';
if(num > 9 || num <0){
flag = 1; //輸入不合法
break;
}
p = (DLink*)malloc(sizeof(DLink));
p->info = num;
len++;
if(head->next == NULL)
{
head->next = p;
p->prior = head;
last = p;
}
else
{
p->prior = last;
last->next = p;
last = p;
}
}
if(flag == 0)
{
last->next = NULL;
head->prior = last;
head->info = (head->info)*len;
}
else
{
head->info = 0;
}
return head;
}
2. 加法函數(shù)(同號相加)
讀取兩個鏈表頭結點數(shù)據(jù)域的數(shù)值，判斷符號和整數(shù)長度，較長的整數(shù)作為被加數(shù)（upper），從被加數(shù)的尾節(jié)點（個位）開始向前遍歷，兩個鏈表對應節(jié)點的數(shù)據(jù)域數(shù)值相加，有進位(carry=1)情況前一節(jié)點運算時要加上進位值，判斷最高位有進位的時候在頭結點與其之間插入新的節(jié)點，并更新頭結點數(shù)據(jù)域數(shù)值，實現(xiàn)如下:
DLink *addition(DLink *a, DLink *b)
{
int symbol = abs(a->info)/(a->info);
int len_a = abs(a->info);
int len_b = abs(b->info);
DLink *upper,*lower;
if(len_a > len_b)
{
upper = a;
lower = b;
}
else
{
upper = b;
lower = a;
}
int len_up = abs(upper->info);
int len_low = abs(lower->info);
int cnt = 0;
int carry = 0; //進位
while (cnt != len_up)
{
upper = upper->prior; //個位開始
lower = lower->prior;
if (cnt < len_low)
{
upper->info = upper->info + lower->info + carry;
}
else
{
upper->info = upper->info + carry;
}
carry = 0;
if (upper->info >= 10)
{
upper->info -= 10, carry = 1;
}
++cnt;
}
if (carry)
{
DLink *p;
p = (DLink *)malloc(sizeof(DLink));
p->info = carry;
p->prior = upper->prior;
upper->prior->next = p;
p->next = upper;
upper->prior = p;
upper = p;
++len_up;
}
upper = upper->prior;
upper->info = symbol*len_up;
return upper;
}
3. 減法函數(shù)(異號相加)
減法函數(shù)與加法函數(shù)原理基本相同，不同點主要為：需要找到兩個數(shù)中絕對值較大的數(shù)作為被減數(shù)（upper），通過條件語句和對兩鏈表從頭節(jié)點向后遍歷比較各節(jié)點元素來實現(xiàn)，因為是絕對值較大數(shù)減去絕對值較小數(shù)（lower），最高位不會產(chǎn)生借位操作，在向前遍歷進行運算的過程中，節(jié)點有借位情況(carry=1)情況時，前一節(jié)點運算時要減去借位值，實現(xiàn)如下：
DLink *subtraction(DLink *a, DLink *b)
{
int len_a = abs(a->info);
int len_b = abs(b->info);
DLink *upper, *lower;
if(len_a > len_b)
{
upper = a;
lower = b;
}
else if(len_a < len_b)
{
upper = b;
lower = a;
}
else
{
DLink *tmp1 = a, *tmp2 = b;
int cnt = 0;
tmp1 = tmp1->next;
tmp2 = tmp2->next;
while (cnt != len_a)
{
if(tmp1->info > tmp2->info)
{
upper = a;
lower = b;
break;
}
else if(tmp1->info < tmp2->info)
{
upper = b;
lower = a;
break;
}
tmp1 = tmp1->next;
tmp2 = tmp2->next;
++cnt;
}
if(cnt == len_a)
{
upper = a;
lower = b;
}
}
int len_up = abs(upper->info);
int len_low = abs(lower->info);
int symbol = abs(upper->info)/(upper->info);
int cnt = 0;
int carry = 0; // 借位
while (cnt != len_up)
{
upper = upper->prior;
lower = lower->prior;
if (cnt < len_low)
{
upper->info = upper->info - lower->info - carry;
}
else
{
upper->info = upper->info - carry;
}
carry = 0;
if (upper->info < 0)
{
upper->info += 10, carry = 1;
}
++cnt;
}
upper = upper->prior;
upper->info = symbol*len_up;
return upper;
}
4. 輸出
根據(jù)頭結點的符號確定結果是否以’-’開始，由于減法函數(shù)處理后從頭結點到存儲有效數(shù)字的節(jié)點間可能會有0值，需要從頭節(jié)點向后循環(huán)判斷是否為0并輸出（同時考慮結果僅是0的情況），在循環(huán)過程中計算還未輸出的位數(shù)（len），能被4整除時則輸出’,’達到輸出中國表示習慣長整數(shù)的目的，實現(xiàn)如下:
void printDlink(DLink *head)
{
DLink *p;
p = head;
int len = abs(p->info);
int cnt = 1;
if(p->info < 0)
{
printf("-");
}
p = p->next;
while(p->info == 0 && p->next != NULL)
{
p = p->next;
--len;
}
while(len)
{
printf("%d", p->info);
p = p->next;
--len;
if(!(len%4) && len) putchar(',');
}
}
5. 主函數(shù)
提示輸入格式，并通過所構成鏈表頭結點的數(shù)據(jù)判斷輸入是否合法（不合法進行提示），對合法輸入判斷采用函數(shù)種類，計算輸出，實現(xiàn)如下:
void main()
{
printf("請輸入需要計算的兩個長整數(shù)，以分號隔開(如：-9999,9999;1,0000,0000)\n");
DLink *a;
a = Dcreat();
if(a->info == 0)
{
printf("invalid input");
}
else
{
DLink *b;
b = Dcreat();
if(b->info == 0)
{
printf("invalid input");
}
else
{
DLink *c;
if((a->info)*(b->info)<0)
{
c = subtraction(a,b);
}
else
{
c = addition(a,b);
}
printDlink(c);
}
}
}
6. 程序的層次結構
五、用戶手冊
- 本程序的運行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件為：longadd.exe
- 進入程序按提示操作，注意兩數(shù)字間和結束用分號（英文輸入法）隔開
- 輸入后按回車符即顯示結果
六、測試結果
