임의의 긴 정수 덧셈 연산

8639 단어 데이터 구조

[문제 설명]
      임의의 긴 정수 로 덧셈 연산 을 하 는 시범 프로그램 을 설계 하 다.
[기본 요구]
시스템 은 메뉴 알림 방식 으로 작 동 합 니 다.
기본 기능 은 큰 정수 입력, 덧셈 연산, 큰 정수 출력 을 포함한다.
양 방향 순환 링크 를 이용 하여 긴 정수 의 저장 을 실현 하고 모든 노드 는 하나의 정형 변 수 를 포함한다.모든 정형 변수의 범 위 는 - (215 - 1) ~ (215 - 1) 이다.
입 출력 형식: 중국 이 긴 정수 에 대한 표현 습관 에 따라 네 명 씩 한 그룹 씩 그룹 간 에 쉼표 로 분리 합 니 다.예 를 들 어: 1, 0000, 0000, 0000 [테스트 데이터] 0;0;"0" 을 입력 해 야 합 니 다.
-2345,6789;-7654,3211;"- 1, 0000, 0000" 을 출력 해 야 합 니 다.
-9999,9999;1,0000,0000,0000;"9999, 0000, 0001" 을 출력 해 야 합 니 다.
1,0001,0001;-1,0001,0001;"0" 을 출력 해 야 합 니 다.
1,0001,0001;-1,0001,0000;"1" 을 출력 해 야 합 니 다.
-9999,9999,9999;-9999,9999,9999;"- 1, 9999, 9999, 9998" 을 출력 해 야 합 니 다.
1,0000,9999,9999;1;"1, 0001, 0000, 0000" 을 출력 해 야 합 니 다.
//                          
#include "stdafx.h"
#include 
#include 
#include 
#include 
#include 
using namespace std;
//           
struct Cltype
{
	int num;
	Cltype *nextNode;
	Cltype *preNode;
};
//       
struct Answer
{
	int num = 0;
	int caorbo = 0;
	Answer *nextNode;
	Answer *preNode;
};
Cltype*FindEnd(Cltype*head)  //      
{
	Cltype*htemp;
	htemp = head;
	while (htemp->nextNode != NULL)
	{
		htemp = htemp->nextNode;
	}
	return htemp;
}
Answer*FindEnd(Answer*head)  //           
{
	Answer*htemp;
	htemp = head;
	while (htemp->nextNode != NULL)
	{
		htemp = htemp->nextNode;
	}
	return htemp;
}
Cltype*AddnodeNum(int num, Cltype*head)  //    (  )
{
	Cltype *htemp, *node;
	if (!(node = new Cltype))
	{
		cout << "      ";
		return NULL;
	}
	else
	{
		node->num = num;
		node->nextNode = NULL;
		if (head == NULL)
		{
			head = node;
			return head;
		}
		htemp = head;
		while (htemp->nextNode != NULL)
		{
			htemp = htemp->nextNode;
		}
		htemp->nextNode = node;
		node->preNode = htemp;
		return head;
	}
}
Answer*AddnodeAns(int num, Answer*head)  //            
{
	Answer *htemp, *node;
	if (!(node = new Answer))
	{
		cout << "      ";
		return NULL;
	}
	else
	{
		node->num = num;
		node->nextNode = NULL;
		if (head == NULL)
		{
			head = node;
			return head;
		}
		htemp = head;
		while (htemp->nextNode != NULL)
		{
			htemp = htemp->nextNode;
		}
		htemp->nextNode = node;
		node->preNode = htemp;
		return head;
	}
}
Answer*add(Cltype*head1, Cltype*head2, Answer*head3)  //                        
{                                                      //    
	Cltype*end1 = FindEnd(head1);
	Cltype*end2 = FindEnd(head2);
	Answer*End = FindEnd(head3);
	while (end2 != head2)
	{
		End->num = end1->num + end2->num + End->caorbo;
		if (End->num > 9)
		{
			End->num = End->num % 10;
			End->preNode->caorbo = 1;
		}
		end1 = end1->preNode;
		end2 = end2->preNode;
		End = End->preNode;
	}
	End->num = head2->num + end1->num + End->caorbo;  //head2    end2,       
	if (End->num > 9)            //               10  ,   
	{
		End->num = End->num % 10;
		End->preNode->caorbo = 1;
	}
	while (end1 != head1)
	{
		end1 = end1->preNode;
		End = End->preNode;
		End->num = end1->num + End->caorbo;
		if (End->num > 9)            //               10  ,   
		{
			End->num = End->num % 10;
			End->preNode->caorbo = 1;
		}
	}
	End = End->preNode;
	End->num = End->caorbo;
	return head3;
}
//******************************************
//        head1          head2         
//******************************************
Answer*subs(Cltype*head1, Cltype*head2, Answer*head3)
{
	Cltype*end1 = FindEnd(head1);
	Cltype*end2 = FindEnd(head2);
	Answer*End = FindEnd(head3);
	while (end2 != head2)
	{
		End->num = end1->num - end2->num + End->caorbo;
		if (End->num < 0)
		{
			End->num += 10;
			End->preNode->caorbo -= 1;
		}
		end1 = end1->preNode;
		end2 = end2->preNode;
		End = End->preNode;
	}
	End->num = end1->num - head2->num + End->caorbo;
	if (End->num < 0)          //          0,          ,     -1
	{
		End->num += 10;
		End->preNode->caorbo -= 1;
	}
	while (end1 != head1)
	{
		end1 = end1->preNode;
		End = End->preNode;
		End->num = end1->num + End->caorbo;
		if (End->num < 0)          //          0,          ,     -1
		{
			End->num += 10;
			End->preNode->caorbo -= 1;
		}
	}
	return head3;
}
void AllNode(Answer*head)   //    
{
	int a[100];
	memset(a, 0, 100);
	int i = 0;
	Answer*temp, *thend;
	thend = FindEnd(head);
	temp = head;
	while (temp)
	{
		if (temp->num == -1 || temp->num == 0)   //         0        0
		{
			if (temp == thend)
				cout << "0";
		}
		if (temp->num != -1 && temp->num != 0)
			break;
		temp = temp->nextNode;
	}
	Answer*htemp;
	int flag = 0;
	htemp = head;
	while (htemp)
	{
		if (htemp->num != -1 && htemp->num != 0 || flag == 1)
		{
			a[i++] = htemp->num;
			flag = 1;
		}
		htemp = htemp->nextNode;
	}
	if (i > 4)
	{
		int k, w = i % 4;
		for (k = 0; k < w; k++)
			cout << a[k];
		if (w != 0)        //                       
			cout << ",";
		for (; k < i; k++)
		{
			for (int d = 0; d < 4; d++)    //       
			{
				cout << a[k];
				k++;
			}
			k--;
			if (k != i - 1)    //        ,                 
				cout << ",";
		}
	}
	else
	{
		for (int g = 0; g < i; g++)
			cout << a[g];
	}
}
int count(string s)
{
	int cnt = 0;
	for (auto c : s)
	if (isdigit(c))
		++cnt;
	return cnt;
}
//****************************************
//            ,         0   
//****************************************
void send(string org, char*&num, int n)
{
	int k = 1;
	if (isdigit(org[0]))
		num[0] = '1';    //1    
	else num[0] = '0';   //0    
	for (int i = 0; k < n, i < org.length(); i++)
	{
		if (isdigit(org[i]))
		{
			num[k] = org[i];
			k++;
		}
	}
}
//******************************************
//return 1  num1      num2
//******************************************
int compare(string s1, string s2)
{
	int a = count(s1) + 1;   //           +1     
	int b = count(s2) + 1;
	if (a > b) return 1;
	if (a < b) return 0;
	char*num1 = new char[a];
	char*num2 = new char[b];
	memset(num1, 0, a);        //                 
	memset(num2, 0, b);
	send(s1, num1, a);         //                    num1 num2 
	send(s2, num2, b);
	for (int i = 1; i < a; i++)
	{
		if (num1[i]>num2[i])
			return 1;
		if (num1[i] < num2[i])
			return 0;
	}
	return 1;
}
Cltype*ass(Cltype*head, char*num, int n)
{
	for (int i = 1; i <= n - 1; i++)
	{
		int su = num[i] - '0';
		head = AddnodeNum(su, head);
	}
	return head;
}
int _tmain(int argc, _TCHAR* argv[])
{
	Cltype*head1 = NULL, *head2 = NULL;/***************    Num1   */
	Answer*head3 = NULL;
	//	int length1, length2;
	string s1, s2;
	cin >> s1 >> s2;
	int a = count(s1) + 1;   //           +1     
	int b = count(s2) + 1;
	char*num1 = new char[a];
	char*num2 = new char[b];
	memset(num1, 0, a);        //                 
	memset(num2, 0, b);
	send(s1, num1, a);         //              
	send(s2, num2, b);
	head1 = ass(head1, num1, a);  //    
	head2 = ass(head2, num2, b);
	int q = a > b ? a + 1 : b + 1;
	for (int j = 1; j < q; j++)
		head3 = AddnodeAns(-1, head3);
	if (compare(s1, s2))
	{
		if (num1[0] == '0' && num2[0] == '0')
		{
			add(head1, head2, head3);
			cout << "-";
			AllNode(head3);
		}
		if (num1[0] == '1' && num2[0] == '0')
		{
			subs(head1, head2, head3);
			AllNode(head3);
		}
		if (num1[0] == '0'&& num2[0] == '1')
		{
			subs(head1, head2, head3);
			cout << "-";
			AllNode(head3);
		}
		if (num1[0] == '1' && num2[0] == '1')
		{
			add(head1, head2, head3);
			AllNode(head3);
		}
	}
	else
	{
		if (num1[0] == '0' && num2[0] == '0')
		{
			add(head2, head1, head3);
			cout << "-";
			AllNode(head3);
		}
		if (num1[0] == '1' && num2[0] == '0')
		{
			subs(head2, head1, head3);
			cout << "-";
			AllNode(head3);
		}
		if (num1[0] == '0' && num2[0] == '1')
		{
			subs(head2, head1, head3);
			AllNode(head3);
		}
		if (num1[0] == '1' && num2[0] == '1')
		{
			add(head2, head1, head3);
			AllNode(head3);
		}
	}
	return 0;
}

좋은 웹페이지 즐겨찾기