? 我們都知道加法，1+1=2.c語言實(shí)現(xiàn)一個(gè)加法也是初學(xué)者的必修課。但是你有沒有想過如果兩個(gè)超過long long 類型的數(shù)據(jù)在c語言中要怎么實(shí)現(xiàn)加減乘除？比如一個(gè)一百位的數(shù)加上另一個(gè)一百位的數(shù)。好接下來先介紹高精度算法的處理方式。大家如果有發(fā)現(xiàn)什么BUG請(qǐng)私信告訴我謝謝。（我現(xiàn)在也不能保證我的屎山代碼是正確的hh）
警告：使用鏈表處理需要保持?jǐn)?shù)據(jù)結(jié)構(gòu)的高度一致?。?！（不然就會(huì)像我一樣一大堆的段錯(cuò)誤）
? 既然不能直接用整形進(jìn)行處理，那么我們就用長度不限的數(shù)組來進(jìn)行處理，但是這個(gè)數(shù)組比較特別，它的元素代表它在一個(gè)數(shù)的各位。比如：
? 大數(shù)：123456789101112131415161718
? 數(shù)組：{1,2,3,4,5,6,7,8,9,1,0,1,1,1,2,1,3,1,4,1,5,1,6,1,7,1,8}
接下來的高精度操作都是這樣處理的。（我的鏈表里存的都不是ASCII都是整形數(shù)字，所以輸出也用的%d）
? 對(duì)鏈表的此鏈表的規(guī)定? 因?yàn)槲蚁胗脝捂湵砑訂谓Y(jié)構(gòu)體解決掉高精度計(jì)算，所以在如何儲(chǔ)存大數(shù)的長度的時(shí)候犯了難。但是看到頭節(jié)點(diǎn)還沒有好好利用起來時(shí)，我把大數(shù)的位數(shù)存進(jìn)了頭節(jié)點(diǎn)的數(shù)據(jù)域，在后面講減法的時(shí)候會(huì)用到這個(gè)，快速比較兩個(gè)數(shù)的大小關(guān)系。這里先放一個(gè)結(jié)構(gòu)體的定義。因?yàn)樵诟呔瘸朔ɡ镉幸粋€(gè)權(quán)值的思想，所以我規(guī)定結(jié)構(gòu)體里的 id 代表各位數(shù)的權(quán)值，后面會(huì)講到 id 有什么用。
? 讓我們想想自己是怎么計(jì)算兩個(gè)數(shù)的和的，比如9876987+999999。我們先會(huì)把他們對(duì)齊對(duì)吧？按地位對(duì)齊。
然后再各位先加，逢10進(jìn)1，在計(jì)算機(jī)里我們仿照人對(duì)加法的操作。首先解決第一個(gè)問題--->按低位對(duì)齊。然后是第二個(gè)問題，逢十進(jìn)一。
按低位對(duì)齊? 我們這里用鏈表實(shí)現(xiàn)，所以之后的所有語言都是基于鏈表的。如果鏈表不熟悉的小伙伴可以先看看鏈表專題。（傳送門）
初學(xué)者的鏈表總結(jié)_zhywyt的博客-博客鏈表c語言實(shí)現(xiàn)
這樣我們就能得到一個(gè)倒序輸入的大數(shù)了。也就是說我們已經(jīng)達(dá)到了按低位對(duì)齊的目的了。
逢十進(jìn)一? 在我們把兩個(gè)數(shù)的個(gè)位加起來之后，需要對(duì)各位的數(shù)字進(jìn)行處理，從低位開始，逢十進(jìn)一。這個(gè)操作也很簡單，只需要用一個(gè)變量temp來保存進(jìn)位就行。初始化temp位0表示沒有進(jìn)位。
圖中的 at , bt 表示本次循環(huán)中 a 的數(shù)字大小，bt 同理。因?yàn)閮蓚€(gè)數(shù)的長度很可能不一樣，也就是說在短的數(shù)遍歷完之后，長的數(shù)還有元素需要加到結(jié)果里，這時(shí)候需要設(shè)置短的那個(gè)大數(shù)的本次循環(huán)數(shù)字大小為零。
兩個(gè)數(shù)相加，得到的結(jié)果長度大是max(lena,lenb)+1，最小是max(lena,lenb)所以我們只需要先循環(huán)max(lena,lenb)次，為結(jié)果插入元素，然后在循環(huán)外面判斷是否有進(jìn)位，進(jìn)位的數(shù)由整型data保存，于是有：
? 我們從逆序輸入加數(shù)，然后逆序插入到結(jié)果中，那么結(jié)果其實(shí)已經(jīng)是正序了，設(shè)想一下，如果我們要連加的話，那么輸入的格式和輸出的格式一定不能是相反的，所以我們最后把得到的鏈表reverse一下，得到逆序的鏈表然后返回。還有就是對(duì)數(shù)據(jù)的處理方面，輸入的大數(shù)需要去除前導(dǎo)零。注意！去除前導(dǎo)零的函數(shù)要記得讓頭節(jié)點(diǎn)的 data 減小相應(yīng)的大小。
代碼展示
重慶分公司
重慶分公司
node* add(node* a, node* b){
node* ans = NewNode();
ans->next = NULL;
ans->id = 1;
a = inzero(a), b = inzero(b);//inzero()是一個(gè)去除前導(dǎo)零的函數(shù)，在輸入的時(shí)候，如果輸入001+002，沒有這個(gè)操作是很危險(xiǎn)的。
int lena = a->data,lenb=b->data;
int at, bt, lenans = max(lena, lenb);
int data = 0;
for (int i = 0; i< lenans; i++){
if (a->next != NULL){
at = a->next->data;
a = a->next;
}
else at = 0;
if (b->next != NULL){
bt = b->next->data;
b = b->next;
}
else bt = 0;
int temp = at + bt + data;
data = temp % 10;
temp /= 10;
insert(ans, data);
data = temp;
}
if (data)insert(ans, data);
reverse(ans);
return ans;
}? 和加法不同，如果說加法是在進(jìn)位的話，減法就是在退位了。我們這里只想處理a>b的情況。所以在減之前，先判斷 a 和 b 的大小關(guān)系，如果 b 大于 a 那么就交換 a 和 b 并且給ans添上負(fù)的記號(hào)。也就是ans的頭節(jié)點(diǎn)里的 id 了。id 為-1表示這個(gè)數(shù)是負(fù)數(shù)，我們?cè)谳敵龅臅r(shí)候判斷頭節(jié)點(diǎn)里的記號(hào)是否是-1，如果是的話先輸出一個(gè)負(fù)號(hào)。減法和加法在操作上是差不多的，只不過減法是判斷得到的數(shù)是不是負(fù)數(shù)，如果是負(fù)數(shù)的話就借十。從高位借十。這就是高位借十的操作。
寫一個(gè)比較函數(shù)，來判斷 a 和 b 誰大。首先比較 a 和 b 的長度關(guān)系，這里就用到之前存在頭節(jié)點(diǎn)里的data了。當(dāng)長度不一樣的時(shí)候，可以直接判斷出大小關(guān)系。當(dāng)長度一樣的時(shí)候，從高位開始比較，直到出現(xiàn)不一樣的或者到達(dá)最后。這里要注意，因?yàn)閭鬟M(jìn)來的鏈表是逆序的，所以在逐位比較的時(shí)候需要先reverse。
int compare(node* a, node* b){
int lena = a->data,lenb=b->data;
if (lena != lenb)return lena - lenb;
else {
reverse(a), reverse(b);
node* q = a, * p = b;
while (a->next && b->next && a->next->data == b->next->data)a = a->next, b = b->next;
if (a->next && b->next){
int at = a->next->data;
int bt = b->next->data;
reverse(q), reverse(p);
return (at - bt);
}
else{
reverse(q), reverse(p);
return 0;
}
}
}? 減法得到的結(jié)果是有可能出現(xiàn)前導(dǎo)零的，所以在返回答案之前需要去除前導(dǎo)零。
代碼展示node* mins(node* a, node* b){
//考慮b大于a
node* ans = NewNode();
ans->next = NULL;
ans->id = 1;
ans->data = 0;
int lena = a->data, lenb = b->data;
int flag=compare(a,b);
if (flag< 0){
swap(&a, &b);
int temp = lena;
lena = lenb;
lenb = temp;
ans->id = -1;
}
else if (flag == 0){
insert(ans, 0);
ans->data = 1;
return ans;
}
int at, bt,lenans = max(lena, lenb);
int data = 0;
for (int i = 0; i< lenans; i++){
if (a->next != NULL){
at = a->next->data;
a = a->next;
}
else at = 0;
if (b->next != NULL){
bt = b->next->data;
b = b->next;
}
else bt = 0;
int temp = at - bt + data;
data = temp;
if (temp< 0){
data += 10;
temp = -1;
}
else temp = 0;
insert(ans, data);
data = temp;
}
reverse(ans);
ans=inzero(ans);
return ans;
}? 乘法也是遵循我們對(duì)兩個(gè)數(shù)豎式相乘的步驟， a , b 兩個(gè)數(shù)比如12345 和 6789看其中一個(gè)數(shù)，12345中第一位1它的權(quán)值是4?也就是看成1*10e4, 第二位數(shù)2 看成2*10e3，后面的同理。再看6789=6*10e3+7*10e2+8*10e1+9*10e0。先給數(shù)加上權(quán)值，然后再進(jìn)行乘法操作。對(duì) a 中的每一位數(shù)都需要和 b 中的每一位數(shù)進(jìn)行乘法操作。得到的數(shù)放在 ans 的 a->id+b->id中。我們需要一個(gè)find函數(shù)，來找到ans 中對(duì)應(yīng)權(quán)值的所在位置。為了減少find 函數(shù)的使用，我們借助循環(huán)的線性性質(zhì)，對(duì)于 a 中的每一位數(shù)，我們遍歷 b 這個(gè)過程對(duì)應(yīng) ans 中的權(quán)值就是連續(xù)的，對(duì)于 a 中的各位數(shù)我們只需要調(diào)用一次find函數(shù)。find函數(shù)是很簡單的。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
node* multiplication(node* a, node* b){
node* ans = NewNode();
ans->next = NULL;
ans->id = 1;
a = inzero(a), b = inzero(b);
int lena = a->data, lenb = b->data;
int lenans = (lena + lenb-1);//最小是這個(gè)長度，大是它加一
node* am = a->next, * bm = b->next;
int i = 0;
//添加權(quán)值
while (am){
am->id = i++;
am = am->next;
}
i = 0;
while (bm){
bm->id = i++;
bm = bm->next;
}
for (int i = 0; i< lenans; i++)insert(ans, 0);//先插入空節(jié)點(diǎn)
a = a->next, b = b->next;
for(node*i=a;i;i=i->next){
node* p;
p = find(ans, (i->id));//只需要找一次
for(node*j=b;j;j=j->next){
p->data += (i->data) * (j->data);
p = p->next;
}
}
int data = 0;
node* p=ans;
ans = ans->next;
while (ans){
int temp = ans->data+data;
ans->data = temp % 10;
temp /= 10;
data = temp;
ans = ans->next;
}
ans = p;
reverse(ans);
if (data)insert(ans, data),ans->data++;
//去前導(dǎo)零套裝
reverse(ans);
ans=inzero(ans);
return ans;
}? 想象一下豎式計(jì)算，比如 16 /?2 我們的做法是，先從較大的那個(gè)數(shù)的高位取一位數(shù)，這里是? 1 ，然后比較 1 和 2 的大小，發(fā)現(xiàn) 1 小了，那么給答案鏈表加一個(gè) 0，再在16 里取下一位，得到 16和 2 比較，發(fā)現(xiàn)比 2 大，就用 16減去 2，得到 14 存下來，答案鏈表中的該位加一，重復(fù)這個(gè)操作，直到 16 變成小于 2.最后再去除答案鏈表中的前導(dǎo)零，就結(jié)束操作了。
注：這些圖片來組b站up主SherlockGn，她對(duì)高精度的講解非常到位，大家也可以去看他的視頻。高精度計(jì)算除法，計(jì)算大數(shù)相除、求余再也不用求人了！_嗶哩嗶哩_bilibili
一個(gè)視頻帶你了解高精度計(jì)算！再也不用擔(dān)心數(shù)據(jù)溢出了！_嗶哩嗶哩_bilibili
細(xì)節(jié)處理? 前面講高精度減法的時(shí)候有提到compare函數(shù)，使用compare函數(shù)就需要嚴(yán)格的遵守長度設(shè)置規(guī)則，不能出現(xiàn)有一個(gè)數(shù)的長度未初始化，不然會(huì)出現(xiàn)奇怪的事情。（我甚至有一次把電腦跑黑屏了，任務(wù)管理器直接罷工）那么去除前導(dǎo)零就極為重要。寫除法的時(shí)候，我兩次推翻了前面構(gòu)建好的加減乘體系，全部重寫了兩次，才把這幾個(gè)東西統(tǒng)一起來。各位寫的時(shí)候一定要小心，多留一個(gè)心眼。
node* devide(node* a, node* b){
node* ans = NewNode(), * leave = NewNode();
ans->next = NULL,leave->next=NULL;
ans->data = 0, leave->data = 0;
ans->id = 1,leave->id=1;//先做最簡單的十進(jìn)制算法
int flag = compare(a, b);
if (flag< 0){
printf("0 ****** ");
RPrint(a);
printf("\n");
insert(ans, 0);
return ans;
}
else if (flag == 0){
insert(ans, 1);
printf("1 ****** 0");
return ans;
}//a要用到正序所以轉(zhuǎn)回來
reverse(a);
node * q = leave;
a = a->next;
while (a){
insert(leave, a->data);
insert(ans, 0);
inzero(leave);//如果leave是0 的話，再插入一個(gè)零就需要去除前導(dǎo)零了，所以這部不能刪
int flag;
while ((flag=compare(leave, b)) >= 0){
if (flag >0) {
leave = mins(leave, b);
destroy(q);
q = leave;
ans->next->data++;
}
else if (flag == 0){
leave = NewNode();
leave->data = 0,leave->id=1,leave->next=NULL;
insert(leave, 0);
free(q);
q = leave;
ans->next->data++;
}
}
a = a->next;
}
inzero(ans);
RPrint(ans);
printf(" ****** ");
RPrint(q);
printf("\n");
printf("The ans has %d digit.\n", ans->data);
return ans;
}最后是我的屎山代碼。（建議在VS2022下運(yùn)行）
#include#include#include#ifndef max(a,b) ((a)>(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#endif
//頭節(jié)點(diǎn)里的data是數(shù)字位數(shù) id 是數(shù)字正負(fù) 1為非負(fù) -1為負(fù)
struct node {
int data;
int id;
node* next;
};
typedef struct node node;
node* NewNode();
//在頭節(jié)點(diǎn)之后倒序插入數(shù)據(jù)
void SetColor(unsigned short ForeColor, unsigned short BackGroundColor)
{
HANDLE hCon = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTextAttribute(hCon, (ForeColor % 16) | (BackGroundColor % 16 * 16));
}
void insert(node* la, int data);
//倒序打印鏈表
void RPrint(node* la);
//逆序輸入，返回逆序
node* add(node* a, node* b);
//逆序輸入，返回逆序
node* mins(node* a, node* b);
//逆序輸入，返回逆序
node* multiplication(node* a, node* b);
//逆序輸入，返回逆序
node* devide(node* a, node* b);
void destroy(node* la);
//帶頭節(jié)點(diǎn)
void reverse(node* la);
void swap(node* a, node* b);
//比較逆序的兩個(gè)數(shù)
int compare(node* a, node* b);
//去除后導(dǎo)零
node* inzero(node* la);
node* find(node* la, int a);
int main(){
while (1){
system("cls"),printf("######## Author is zhywyt. ########\n");
printf("Please input a line of claculation.\nLike a+b or a-b or a*b or a/b without space!\n");
SetColor(4, 0),printf("Please not input space between data!\n"), SetColor(15, 0);
node* a = NewNode(), * b = NewNode(), * ans=NewNode();
char c;
a->next = NULL, b->next = NULL,a->data=0,b->data=0,ans->data=0,ans->next=NULL;
while ((c = getchar()) >= '0' && c<= '9')insert(a, c - '0');
char m;
m = c;
if (c!='+'&&c!='-'&&c!='*'&&c!='/'){
SetColor(4, 0), system("cls"), printf("Format Error !\a\a\a\n");
SetColor(15, 0), printf("Plaese input true format!!\n\n"), printf("Enter to continue.\n");
getchar();
continue;
}
while ((c = getchar()) >= '0' && c<= '9')insert(b, c - '0');
while (!a->data){
printf("Please input a!\a\na = ");
while ((c = getchar()) >= '0' && c<= '9')insert(a, c - '0');
}
while (!b->data){
printf("Please input b!\a\nb = ");
while ((c = getchar()) >= '0' && c<= '9')insert(b, c - '0');
}
a = inzero(a), b = inzero(b);
switch (m){
case('+'): {
RPrint(a), printf(" + "), RPrint(b), printf(" = ");
ans=add(a, b), RPrint(ans);
printf("\nThe answer have %d digits.\n",ans->data);
break;
}
case('-'): {
RPrint(a), printf(" - "), RPrint(b), printf(" = ");
ans=mins(a, b), RPrint(ans);
printf("\nThe answer have %d digits.\n", ans->data);
break;
}
case('*'): {
RPrint(a), printf(" * "), RPrint(b), printf(" = ");
ans=multiplication(a, b), RPrint(ans);
printf("\nThe answer have %d digits.\n", ans->data);
break;
}
case('/'): {
if (b->data == 1 && b->next->data == 0) {
printf("0 is not to be the fenmu!\a\a\a\n");
insert(ans, 0);
break;
}
RPrint(a), printf(" / "), RPrint(b), printf(" = ");
ans=devide(a, b);
break;
}
}
destroy(ans);
destroy(a);
destroy(b);
printf("\nPlease input a 'enter' to continue or '0' to exit.\n");
char n;
scanf("%c", &n);
if (n == '\n')continue;
getchar();
if (n == '0')break;
}
return 0;
}
node* NewNode(){
node* la = (node*)malloc(sizeof(node));
if (la == NULL){
printf("memory error!\a");
exit(-1);
}
return la;
}
void insert(node* la, int data){
la->data++;
node* p = NewNode();
p->next = la->next;
la->next = p;
p->data = data;
}
void destroy(node* la){
node* p;
while (la){
p = la->next;
free(la);
la = p;
}
}
void RPrint(node*la){
node* p = la;
reverse(la);
if (la->id == -1)printf("-");
la = la->next;
while (la){
printf("%d", la->data);
la = la->next;
}
reverse(p);
}
void reverse(node* la){
node* p = la->next;
la->next = NULL;
while (p){
node* q = p;
p = p->next;
q->next = la->next;
la->next = q;
}
}
void swap(node** a, node** b){
node* temp =* a;
*a = *b;
*b = temp;
}
node* inzero(node* la){
node* p = (node*)malloc(sizeof(node));
if (!p){
printf("Eroor!\a");
exit(-1);
}
p=la;
reverse(la);
la = la->next;
while (la && !la->data && la->next){
node* q = la;
la = la->next;
free(q);
(p->data)--;
}
p->next = la;
reverse(p);
return p;
}
node* find(node* la, int a){
for (int i = 0; i<=a; i++)la = la->next;
return la;
}
int compare(node* a, node* b){
int lena = a->data,lenb=b->data;
if (lena != lenb)return lena - lenb;
else {
reverse(a), reverse(b);
node* q = a, * p = b;
while (a->next && b->next && a->next->data == b->next->data)a = a->next, b = b->next;
if (a->next && b->next){
int at = a->next->data;
int bt = b->next->data;
reverse(q), reverse(p);
return (at - bt);
}
else{
reverse(q), reverse(p);
return 0;
}
}
}
node* devide(node* a, node* b){
node* ans = NewNode(), * leave = NewNode();
ans->next = NULL,leave->next=NULL;
ans->data = 0, leave->data = 0;
ans->id = 1,leave->id=1;//先做最簡單的十進(jìn)制算法
int flag = compare(a, b);
if (flag< 0){
printf("0 ****** ");//6個(gè)
RPrint(a);
printf("\n");
insert(ans, 0);
return ans;
}
else if (flag == 0){
insert(ans, 1);
printf("1 ****** 0");
return ans;
}//a要用到正序所以轉(zhuǎn)回來
reverse(a);
node * q = leave;
a = a->next;
while (a){
insert(leave, a->data);
insert(ans, 0);
inzero(leave);//
int flag;
while ((flag=compare(leave, b)) >= 0){
if (flag >0) {
leave = mins(leave, b);
destroy(q);
q = leave;
ans->next->data++;
}
else if (flag == 0){
leave = NewNode();
leave->data = 0,leave->id=1,leave->next=NULL;
insert(leave, 0);
free(q);
q = leave;
ans->next->data++;
}
}
a = a->next;
}
inzero(ans);
RPrint(ans);
printf(" ****** ");
RPrint(q);
printf("\n");
printf("The ans has %d digit.\n", ans->data);
return ans;
}
node* add(node* a, node* b){
node* ans = NewNode();
ans->next = NULL;
ans->id = 1;
a = inzero(a), b = inzero(b);//inzero()是一個(gè)去除前導(dǎo)零的函數(shù)，在輸入的時(shí)候，如果輸入001+002，沒有這個(gè)操作是很危險(xiǎn)的。
int lena = a->data,lenb=b->data;
int at, bt, lenans = max(lena, lenb);
int data = 0;
for (int i = 0; i< lenans; i++){
if (a->next != NULL){
at = a->next->data;
a = a->next;
}
else at = 0;
if (b->next != NULL){
bt = b->next->data;
b = b->next;
}
else bt = 0;
int temp = at + bt + data;
data = temp % 10;
temp /= 10;
insert(ans, data);
data = temp;
}
if (data)insert(ans, data);
reverse(ans);
return ans;
}
node* mins(node* a, node* b){
//考慮b大于a
node* ans = NewNode();
ans->next = NULL;
ans->id = 1;
ans->data = 0;
int lena = a->data, lenb = b->data;
int flag=compare(a,b);
if (flag< 0){
swap(&a, &b);
int temp = lena;
lena = lenb;
lenb = temp;
ans->id = -1;
}
else if (flag == 0){
insert(ans, 0);
ans->data = 1;
return ans;
}
int at, bt,lenans = max(lena, lenb);
int data = 0;
for (int i = 0; i< lenans; i++){
if (a->next != NULL){
at = a->next->data;
a = a->next;
}
else at = 0;
if (b->next != NULL){
bt = b->next->data;
b = b->next;
}
else bt = 0;
int temp = at - bt + data;
data = temp;
if (temp< 0){
data += 10;
temp = -1;
}
else temp = 0;
insert(ans, data);
data = temp;
}
reverse(ans);
ans=inzero(ans);
return ans;
}
node* multiplication(node* a, node* b){
node* ans = NewNode();
ans->next = NULL;
ans->id = 1;
a = inzero(a), b = inzero(b);
int lena = a->data, lenb = b->data;
int lenans = (lena + lenb-1);
node* am = a->next, * bm = b->next;
int i = 0;
//添加權(quán)值
while (am){
am->id = i++;
am = am->next;
}
i = 0;
while (bm){
bm->id = i++;
bm = bm->next;
}
for (int i = 0; i< lenans; i++)insert(ans, 0);
a = a->next, b = b->next;
for(node*i=a;i;i=i->next){
node* p;
p = find(ans, (i->id));
for(node*j=b;j;j=j->next){
p->data += (i->data) * (j->data);
p = p->next;
}
}
int data = 0;
node* p=ans;
ans = ans->next;
while (ans){
int temp = ans->data+data;
ans->data = temp % 10;
temp /= 10;
data = temp;
ans = ans->next;
}
ans = p;
reverse(ans);
if (data)insert(ans, data),ans->data++;
//去前導(dǎo)零套裝
reverse(ans);
ans=inzero(ans);
return ans;
} 你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
