如何使用 link list 寫 大數運算 < c >

Question

有哪位大大可以教小弟一下
我只想到方法
但是程式碼寫失敗
只須寫加法跟減法就行了 <今天考試的題目>
下面是我初次寫的
失敗的..
#include
int k,f;
typedef struct z *p;
typedef struct z{
int data;
p link1;
p link2;
}z;
p a,b,c;
p d,t,s;
p u,v;
int main()
{
while(1)
{
a=(p)malloc(sizeof(struct z));
a->link2=NULL;
t=a;
printf("\n\n輸入數字A 完畢請按 -100 \n\n");
scanf("%d",&a->data);
while(1)
{
s=(p)malloc(sizeof(struct z));
scanf("%d",&s->data);
if(s->data==-100)
break;
s->link1=NULL;
t->link1=s;
s->link2=t;
t=s;
}
b=(p)malloc(sizeof(struct z));
b->link2=NULL;
v=b;
printf("\n\n輸入數字B 完畢請按-100\n\n");
scanf("%d",&b->data);
while(1)
{
u=(p)malloc(sizeof(struct z));
scanf("%d",&u->data);
if(u->data==-100)
break;
u->link1=NULL;
v->link1=u;
u->link2=v;
v=u;
}
printf("\n");
for(;t;t=t->link2)
{
if(v!=NULL)
{
k=v->data;
f=t->data;
printf("%d",k+f);
v=v->link2;
}
}
}
}

題目是不管任何多大的數字都能夠進行運算，但是必須得用 link list，想法是把數字拆解掉，存入每個z中，連結起來，再重後面，往前做運算，所以我有使用ｄｏｕｂｌｅ　ｌｉｎｋ　ｌｉｓｔ　，上面的程式，沒做進位，因為我直接加都失敗，所以還在修正程式碼。

一開始，我是用ｃｈａｒ，但是我做，１＋１印出來的是圖案，所以我才改成ｉｎｔ。

龍 抱歉唷 目前還沒學過c++的語法
所以我看不大懂...

g=0;
for(;t;t=t->link2)
{
if(v!=NULL)
{
k=v->data;
f=t->data;
i=(k+f+g)%10;
printf("%d",i);
g=(k+f+g)/10;
v=v->link2;
}
我把後面修改之後，可以算，但是，是到過來印，而且必須是相同位數，才能做運算。

我上面的做法是先建立往前的 link同一時間也建立向後的link，後面的計算是因為，我每個struct只存一個數字，所以我用迴圈，一個一個做並且印出來。因此必須必須一個一個輸入才能跑！

Answer 1

你的程式有兩個小錯誤.

1.第一個小錯誤可能不是錯誤. 可能是你們老師制定一定要這樣. 小錯誤就是你是把一個大數分成好幾個小數來讀. 例40000002000001變成4000000和2000001兩個數. 但如果使用者打入4和0000002000001的話40000002000001就會變成42000001. 還有就是如果使用者打進4000000200000和1也不行. 因4000000200000超過int的上限. 但這可能是你們老師制定一定要這樣. 所以可能沒關係
2.就是你在加的時候沒有考慮到進位的問題. 如果A是499和99, B是1. 那你加出來的數為499100. 所以在你的z裡你還要有一個int叫len表示data是幾位數. 如果兩個z的data加出來的結果的位數超出兩個z的len. 那表示有進位. 假如99和1相加等於100. 100是三位數3大於2. 所以要進一位. 還有你最好一從link list的尾往頭加. 這樣在加進位時比較簡單.
3. 就是如果A是499和11, B是1. 那你只顯示12. 499不見了. 你的for迴圈要運行到v和t的link2都是NULL才行

P.S. 如果用你現在的做法來做減法很困難. 最好是先用字串(string或char *)讀進大數. 再從字串分解到小數. 分的時後每個z都有同等的位數(這樣就不用len啦). 這樣自己分的話在做加和減時比較簡單. 尤其是做減法時簡單多了.

比如說用char *讀進大數12345678901234567890之後, 把字串分割為9位數. 因int的最大數是2147483648. 不能用10位數, 因int不能代表4000000000. 所以12345678901234分割後會變成有3個z的link list. 第一個z的data是12. 第二個z的data是345678901. 第三個z的data是234567890.

所以如果兩個z相加成10位數的話就會有進位. 如果z的data少於9位數且不是在link link裡的第一個z. 那我們知道當顯示data時要在前面補0. 直到補滿9位數為止.

照我的建議試試看可不可以

懂不懂? 不懂請再問
------------------------------------------------------------------------------------
你要把1加上'0'才是'1'.
到這看看. 這個解答雖然是用string.但是用link list也是同樣的道理
http://tw.knowledge.yahoo.com/question/?qid=1005032603732

====================================================

你可以把以上的程式從string改成link list. 每一個z裡的data裝一個個位數
-----------------------------------------------------------------------------------
#include
#include
#include

struct unit
{
int data;
struct unit *next;
struct unit *prev;
};

struct unit *str2unit(char *);
void print(struct unit *);
void free_unit(struct unit *);

int
main()
{
char n[81];
struct unit *num1, *num2;

//向使用者要第一個大數
printf("Please type in the first number : ");
scanf("%80s", n);
//把字串轉換成unit的link list
num1 = str2unit(n);
//向使用者要第二個大數
printf("Please type in the second number : ");
scanf("%80s", n);
//把字串轉換成unit的link list
num2 = str2unit(n);

//顯示大數字
printf("number 1 : ");
print(num1);
//顯示大數字
printf("number 2 : ");
print(num2);
return(0);
}
/*
* 把字串轉換成unit的link list
*/
struct unit *
str2unit(char *n)
{
struct unit *tmp, *head;
int len;

len = strlen(n);
head = NULL;
//每九個數字合成一個unit
while (len > 9)
{
tmp = (struct unit *) malloc(sizeof(struct unit));
//如果malloc失敗就表示沒有記憶體了. 要退出
if (tmp == NULL)
goto no_mem;
//把新的unit插入link list的前頭.
tmp->prev = NULL;
if (head == NULL) {
head = tmp;
tmp->next = NULL;
} else {
tmp->next = head;
head->prev = tmp;
head = tmp;
}
//把字串轉換成數字
len -= 9;
tmp->data = atoi(&n[len]);
n[len] = '\0';
}
//把最後一組數字組成一個unit
tmp = (struct unit *) malloc(sizeof(struct unit));
//如果malloc失敗就表示沒有記憶體了. 要退出
if (tmp == NULL)
goto no_mem;
//把新的unit插入link list的前頭.
tmp->prev = NULL;
if (head == NULL) {
head = tmp;
tmp->next = NULL;
} else {
tmp->next = head;
head->prev = tmp;
head = tmp;
}
//把字串轉換成數字
tmp->data = atoi(n);
return(head);
no_mem:
//要退出之前要還回所有的記憶體
free_unit(head);
return(head);
}

//顯示大數字
void
print(struct unit *list)
{
while (list)
{
printf("%d", list->data);
list = list->next;
}
printf("\n");
}

//free大數字
void
free_unit(struct unit *list)
{
struct unit *tmp;

while (list)
{
tmp = list->next;
free(list);
list = tmp;
}
}

這程式先用字串讀進大數, 然後再轉換成unit的link list.
比如:
大數1234123456789123456789會被轉換成
1234<->123456789<->123456789的link list

加減法自己試試吧. 跟你寫的差不多. 只不過要考慮進位的問題. 你改的有一點不正確. 如果每一個unit是9個數字. 為何只%10和/10?應該是10000000000才對
有問題請再問
------------------------------------------------------------------------------
但你是用scanf("%d", &&u->data);所以使用者可以打進2314, 而不是2.那怎麼辦?
在你的for迴圈之前用另一個迴圈把t移到link list的尾端之後在你的for迴圈裡用link1就好了

Answer 2

到下面的網址看看吧

▶▶http://*****