SHARE
SPREAD
HELP

The Tradition of Sharing

Help your friends and juniors by posting answers to the questions that you know. Also post questions that are not available.


To start with, Sr2Jr’s first step is to reduce the expenses related to education. To achieve this goal Sr2Jr organized the textbook’s question and answers. Sr2Jr is community based and need your support to fill the question and answers. The question and answers posted will be available free of cost to all.

 

#
Authors:
Walter Savitch ,kenrick Mock
Chapter:
Linked Data Structures
Exercise:
Programming Projects
Question:3 | ISBN:9780132830317 | Edition: 5

Question

Add a copy constructor to the HugeNumber class described in the previous problem that makes a deep copy of the input HugeNumber . Also create an add method that adds an input HugeNumber to the instance’s HugeNumber value and returns a new HugeNumber that is set to the sum of the two values. Write code to test the additions to your class.


TextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbookTextbook

Answer

Program:

// HugeNumber.java
public class HugeNumber
{
	private class DoublyNode
	{
		private int digit;
		private DoublyNode previous;
		private DoublyNode next;

		public DoublyNode()
		{
			digit = 0;
			previous = null;
			next = null;
		}

		public DoublyNode(int newDigit, DoublyNode newPrevious,
				                                 DoublyNode newNext)
		{
			digit = newDigit;
			previous = newPrevious;
			next = newNext;
		}
	}

	private DoublyNode head;

	public HugeNumber()
	{
		head = null;
	}

	public HugeNumber(HugeNumber other)
	{
		HugeNumber copy = new HugeNumber();

		if(other.head == null)
		{
			this.head = null;
		}
		else
		{
			copy.head = new DoublyNode(other.head.digit, null, other.head.next);
			DoublyNode currNode = copy.head.next;
			DoublyNode prevNode = copy.head;

			while(currNode != null)
			{
				DoublyNode newNode = 
                        new DoublyNode(currNode.digit, prevNode, currNode.next);
				prevNode.next = newNode;
				prevNode = newNode;
				currNode = currNode.next;
			}

			this.head = copy.head;
		}
	}

	public void addMostSignificantDigit(int newDigit)
	{
		DoublyNode newNode = new DoublyNode(newDigit, null, head);

		if(head != null)
		{
			head.previous = newNode;
		}

		head = newNode;
	}
	
	public HugeNumber addNumber(HugeNumber other)
	{
		if(head == null)
			return other;
		
		if(other.head == null)
			return this;
		
		HugeNumber tempNum = new HugeNumber();
		
		DoublyNode curr1 = head;
		DoublyNode curr2 = other.head;
				
		int carry = 0;
		int sum = 0;
		while(curr1 != null && curr2 != null)
		{
			sum = curr1.digit + curr2.digit + carry;
			
			if(sum < 10)
				carry = 0;
			else
			{
				sum = sum % 10;
				carry = 1;
			}
			
			tempNum.addMostSignificantDigit(sum);
			
			curr1 = curr1.next;
			curr2 = curr2.next;
		}
		
		while(curr1 != null)
		{
			sum = curr1.digit + carry;
			
			if(sum < 10)
				carry = 0;
			else
			{
				sum = sum % 10;
				carry = 1;
			}
			
			tempNum.addMostSignificantDigit(sum);
			
			curr1 = curr1.next;
		}
		
		while(curr2 != null)
		{
			sum = curr2.digit + carry;
			
			if(sum < 10)
				carry = 0;
			else
			{
				sum = sum % 10;
				carry = 1;
			}
			
			tempNum.addMostSignificantDigit(sum);
			
			curr2 = curr2.next;
		}
		
		if(carry > 0)
		{
			tempNum.addMostSignificantDigit(carry);
		}
		
		HugeNumber hugeSum = new HugeNumber();
		DoublyNode current = tempNum.head;
		
		while(current != null)
		{
			hugeSum.addMostSignificantDigit(current.digit);
			current = current.next;
		}		
		
		return hugeSum;
	}

	public void reset()
	{
		head = null;
	}

	public String getNumber()
	{
		return this.toString();
	}

	public int size()
	{
		int count = 0;
		DoublyNode current = head;

		while(current != null)
		{
			count++;
			current = current.next;
		}

		return count;
	}

	public String toString()
	{
		String result = "";

		DoublyNode current = head;

		while(current != null)
		{
			result = current.digit + result;
			current = current.next;
		}

		return result;
	}
}
// HugeNumberDemo.java
public class HugeNumberDemo
{
	public static void main(String[] args)
	{
		HugeNumber number1 = new HugeNumber();
		
		number1.addMostSignificantDigit(9);
		number1.addMostSignificantDigit(8);
		number1.addMostSignificantDigit(7);
		number1.addMostSignificantDigit(6);
		number1.addMostSignificantDigit(5);
		number1.addMostSignificantDigit(4);
		number1.addMostSignificantDigit(3);
		number1.addMostSignificantDigit(2);
		number1.addMostSignificantDigit(1);
		number1.addMostSignificantDigit(0);
		number1.addMostSignificantDigit(9);
		number1.addMostSignificantDigit(8);
		
		System.out.println("Number1: " + number1.getNumber());
		
		HugeNumber number2 = new HugeNumber(number1);
		System.out.println("Number2: " + number2.getNumber());
				
		HugeNumber number3 = number1.addNumber(number2);
		System.out.println("\n" + number1 + " + " + number2 + " = " + number3);
	}
}

Output:

Number1: 987654321098
Number2: 987654321098

987654321098 + 987654321098 = 1975308642196

 

0 0

Discussions

Post the discussion to improve the above solution.