list_str_mul.c

2个1000位大整数相乘

//把1000位大整数分段成为数组，然后分段相乘，存在链表当中。最后累加合并。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BATCH 8

char *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;
}