//把1000位大整數分段成為數組，然后分段相乘，存在鏈表當中。最后累加合并。#include <stdio.h>#include <stdlib.h>#include <string.h>#define BATCH 8char *str_a = "111111111111111111";char *str_b = "11111111111111111111";struct __node_t{	int value;	int exp;	struct __node_t *next;};typedef struct __node_t node_t;//顯示節點值int show_node (node_t *ptail){	if (ptail == NULL)	{		printf ("%s.%d\n", __FILE__, __LINE__);		return -1;	}	printf ("(v: %d, e: %d)", ptail->value, ptail->exp);	return 0;}//顯示鏈表內容int show_list (node_t *ptail){	if (ptail == NULL)	{		printf ("%s.%d\n", __FILE__, __LINE__);		return -1;	}	printf ("-----\n");	node_t *p = ptail;	while (p)	{		show_node (p);		printf (" -> ");		p = p->next;	}	printf ("NULL\n");	return 0;}//合并鏈表int combine_list (node_t *tail){	//get len	if (tail == NULL)	{		printf ("%s.%d\n", __FILE__, __LINE__);	}	int len;	node_t *p = tail;	while (p->next != NULL)		p = p->next;	len = 2 * (p->exp);	char *pres = (char *)malloc (sizeof (len + 1));	memset (pres, '0', len);	pres[len] = '\0';		p = tail;	while (p)	{		plus_res(&pres, len, p);		p = p->next;	}		printf ("result= %s\n", pres);		return 0;}//鏈表中的結果相加int plus_res (char **ppres, int len, node_t *p){	int acc = 0;	int i;	int index = len - p->exp - 1; 	int value = p->value;	int tmp;	for (i = 0; i < 4; i++)	{		tmp = *(*ppres + index - i) - '0' + value % 10 + acc;		*(*ppres + index - i) = tmp % 10 + '0';		acc = tmp / 10;		value = value / 10;	}	while (acc)	{		tmp = *(*ppres + index - i) - '0' + acc;		*(*ppres + index - i) += tmp % 10 + '0';		acc = tmp / 10;		i++;	}		return 0;}//鏈表增加節點int add_value (node_t **pptail, int value, int exp){	if (*pptail == NULL)	{			if (value < 10000)		{			*pptail = (node_t *)malloc (sizeof (node_t));			(*pptail)->value = value;			(*pptail)->exp = exp;			(*pptail)->next = 0;			return 0;		}		if (value >= 10000)		{			*pptail = (node_t *)malloc (sizeof (node_t));			(*pptail)->value = value % 10000;			(*pptail)->exp = exp;			(*pptail)->next = (node_t *)malloc (sizeof (node_t));			(*pptail)->next->value = value / 10000;			(*pptail)->next->exp = exp + 4;			(*pptail)->next->next = 0;			return 0;		}	}	node_t *p = *pptail;	while (1)	{		if (p->exp == exp)		{			while (p->next != NULL)			{				if (p->next->exp != exp)					break;				p = p->next;			}			p->value += value;			if (p->value > 9999)			{				int tmp = p->value / 10000;				p->value = p->value % 10000;				node_t *new_node = (node_t *)malloc (sizeof (node_t));				if (new_node == NULL)				{					printf ("%s.%d\n", __FILE__, __LINE__);					return -1;				}				new_node->value = tmp;				new_node->exp = p->exp + 4;				new_node->next = p->next;				p->next = new_node;			}			return 0;		}		if (p->exp < exp)		{			if (p->next == NULL)			{				node_t *tmp = (node_t *)malloc (sizeof (node_t));				tmp->value = value;				tmp->exp = exp;				tmp->next = 0;				p->next = tmp;				return 0;			}			if (p->next->exp > exp)			{				node_t *tmp = (node_t *)malloc (sizeof (node_t));				tmp->value = value;				tmp->exp = exp;				tmp->next = p->next;				p->next = tmp;				return 0;			}		}		p = p->next;	}	return 0;}//1000位大整數變成鏈表int tran_list (char *src, node_t **pptail){	int len = strlen (src);	int i;	int value;	int exp;	for (i = len - 4; i >= 0; i -= 4)	{		value = (src[i] - '0') * 1000   + (src[i + 1] - '0') * 100;		value = (src[i + 2] - '0') * 10 + (src[i + 3] - '0') + value;		add_value (pptail, value, len - i - 4);		//show_list (*pptail);	}	if (i < 0)	{		int pad = len % 4;		if (pad != 0)		{			exp = (len / 4) * 4;			if (pad == 1)				value = src[0] - '0';			if (pad == 2)				value = (src[0] - '0') * 10 + (src[1] - '0');			if (pad == 3)				value = (src[0] - '0') * 100 + (src[1] - '0') * 10 + (src[2] - '0');			add_value (pptail, value, exp);			//show_list (*pptail);		}		}	return 0;}//大整數和單個數字相乘int single_mul (char *src, char ch){	int len = strlen (src);	int row = len / BATCH + 1;	int res_len = row * BATCH;	int pad_len = res_len - len;	char (*res)[BATCH + 1];	res = (char (*)[BATCH + 1])malloc (row * (BATCH + 1));	memset (res, 0, res_len);	int i;	for (i = 0; i< pad_len; i++)		res[0][i] = '0';	//memcpy ((char *)res + pad_len , src, len);	int j;	for (i = pad_len, j = 0; j < len; i++, j++)	{		if (i % (BATCH + 1) == BATCH)			i++;		*(*res + i) = *(src + j);	}	for (i = 0; i < row; i++)		printf ("cp res= %s\n", res[i]);	printf ("\n");	int acc = 0;	int value;	for (i = row - 1; i >= 0; i--)	{		value = atoi (res[i]);		value = value * (int)(ch - '0') + acc;		acc = value / 100000000;		value = value % 100000000;		int j;		for (j = BATCH - 1; j >= 0; j--)		{			res[i][j] = value % 10 + '0';			value = value / 10;		}	}	for (i = 0; i < row; i++)		printf ("mul res= %s\n", res[i]);	printf ("\n");	return 0;}//2個大整數變成2個鏈表后相乘（存在小問題^_^）int list_mul (node_t *dst, node_t *src, node_t **res){	if ((dst == NULL) || (src == NULL))	{		printf ("%s.%d\n", __FILE__, __LINE__);		exit (1);	}	node_t *dp;	node_t *sp = src;	printf ("src: ");	//show_list (src);	int value;	while (sp)	{		dp = dst;		while (dp)		{			value = (dp->value) * (sp->value);			add_value (res, value, dp->exp + sp->exp);			//show_list (*res);			dp = dp->next;		}		sp = sp->next;				//show_list(*res);	}	return 0;}//2個字符串數組相加int add (char *dst, char *src, char *res){	int dlen = strlen (dst);	int slen = strlen (src);		int alen;	int blen;	char *a;	char *b;	if (dlen > slen)	{		alen = dlen;		blen = slen;		a = dst;		b = src;	}	else	{		alen = slen;		blen = dlen;		a = src;		b = dst;	}	res = (char *)malloc (sizeof (alen + 2));	memset (res, 0, alen + 2);	int i;	int temp;	int acc = 0;	for (i = blen - 1; i >= 0; i--)	{		temp = a[i + alen - blen] + b[i] - '0' - '0' + acc; 		res [i + alen - blen + 1] = temp % 10 + '0';		acc = temp / 10;	}	for (i = alen - blen - 1; i >= 0; i--)	{		temp = a[i] + acc;		res[i + 1] = temp % 10 + '0';		acc = temp /10;	}	res[0] = acc + '0';	printf ("a= %s, b= %s\n", a, b);	printf ("res= %s\n", res);	return 0;}int main (void){	//char *res;	//add (str_a, str_b, res);	//char ch = '2';	//single_mul (str_a, ch);	node_t *dst = NULL;	node_t *src = NULL;	tran_list (str_a, &dst);	tran_list (str_b, &src);	show_list (dst);	show_list (src);	node_t *res= NULL;	list_mul (dst, src, &res);	printf ("-----\n");	show_list (res);	combine_list (res);	printf ("a: %s\n", str_a);	printf ("b: %s\n", str_b);	return 0;}