linked list reversal

adding to very large numbers from file

Page 1 of 1

2 Replies - 2428 Views - Last Post: 14 April 2010 - 08:23 AM Rate Topic: -----

#1 jessicalegner  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 1
  • View blog
  • Posts: 66
  • Joined: 05-June 09

linked list reversal

Posted 13 April 2010 - 12:51 PM

Hello DIC world.
I have the following coded so far. My problem is that after reading the specs a second time to be sure that I did everything right, I didn't. The two numbers that come in from file need to be printed as they are in file, not in reverse order as they are in the linked list.
I have thought about putting the two linked lists into a stack, but it seems to me that wouldn't help.
What I have so far prints the resulting number in correct sequence. I am stuck on how to print ONLY the two from file in right order.
My professor gave us this driver and we cannot change IT in ANY way (understandably so).
DRIVER
#include<fstream>
using namespace std;

#include"VeryLongInt.h"

int main()
{
	VeryLongInt A("prgm8num1.txt");
	VeryLongInt B("prgm8num2.txt");
	VeryLongInt C;

	A.write();
	B.write();

	C = A + B;
	C.write();
	system("pause");
	return 0;
}

VERYLONGINT CLASS
/*
Created by: Jessica Legner
On: 		04/12/2010
*/
// This file implements the VeryLongInt class
// the int 'carryOver' is used if the two numbers being added
// together are greater than ten.  In addition, the number to carry will
// never be greater than 1.  if the sum of the two number is less than 10,
// the value carried over is 0.
#include<string>
#include<fstream>
#include<iostream>
#include<cmath>
using namespace std;

#include "VeryLongInt.h"
#include "LinkedList.h"

// Default Constructor
VeryLongInt::VeryLongInt()
{
	aNumber;
}
// Constructor
VeryLongInt::VeryLongInt(string fileName)
{
	// Open the file
	ifstream theFile(fileName.data());

	// Get characters and insert into linked list
	char incomingChar = '\n';						// holds char from file
	theFile.get(incomingChar);						// priming read - get first char
	while(incomingChar != '\n')						// until end of the string
	{
		int num = atoi(&incomingChar);				// convert char to int
		aNumber.insertNode(num);					// put int into linked list
		theFile.get(incomingChar);					// get next char
	}
}

// add numbers
VeryLongInt VeryLongInt::operator+(VeryLongInt OBP)
{
	VeryLongInt result;								// Linked list to hold the result
	int num1, 										// holds number from listB
		num2, 										// holds number from listA
		sum, 										// holds sum of num1 + num2
		carryOver = 0, 								// holds the value carried over
													// ones place of sum
		digit;										// holds the value to be inserted
													// tens place of sum (1 or 0)
	int i = 0;										// pointer to traverse through both lists

	OBP.aNumber.resetList();						// reset the lists to look at list head
	aNumber.resetList();
	int listBLen = OBP.aNumber.getLength();			// get list lengths
	int listALen = aNumber.getLength();
	
	while(i != listBLen && i != listALen)			// while there are values in BOTH lists
	{
			num1 = OBP.aNumber.getNextItem();		// get next item in lists
			num2 = aNumber.getNextItem();
			sum = num1 + num2 + carryOver;			// add the numbers together
			digit = sum % 10;						// get digit to insert
			carryOver = sum / 10;					// get carryOver value if any
			result.aNumber.insertNode(digit);		// insert the digit into the list
			i++;									// advance "pointer" 
	}
	// If the lists are not equal to each other, there are going to be remainding numbers
	// to be inserted to the list.  These two if statements will take care of the remainding
	// numbers to be printed. 'i' from previous while loop will be used to pick up where left off

	if(listBLen > listALen)							// if list B is larger than list A			 	
	{
		while(i != listBLen)						// while not end of list
		{
			int nextItem = OBP.aNumber.getNextItem(); // get next item from list
			sum = nextItem + carryOver;				// add the next item and carry over	
			digit = sum % 10;						// get digit to insert
			carryOver = 0;							// there are no numbers to add therefore,
													// there is no more carry over value
			result.aNumber.insertNode(digit);		// insert digit
			i++;									// advance pointer
		}
	}
	if(listBLen < listALen)							// if list A is larger than list B
	{
		while(i != listALen)						// while not end of list
		{
			int nextItem = aNumber.getNextItem();	// get next item from list
			sum = nextItem + carryOver;				// add the next item and carry over	
			digit = sum % 10;						// get digit to insert
			carryOver = 0;							// there are no numbers to add therefore,
													// there is no more carry over value
			result.aNumber.insertNode(digit);		// insert digit
			i++;									// advance pointer
		}
	}
	return result;
}

// method to display the number
void VeryLongInt::write()
{
	aNumber.displayList();
}


Is This A Good Question/Topic? 0
  • +

Replies To: linked list reversal

#2 callahan09  Icon User is offline

  • D.I.C Head

Reputation: 20
  • View blog
  • Posts: 61
  • Joined: 13-April 10

Re: linked list reversal

Posted 13 April 2010 - 01:53 PM

It's going to depend on how the LinkedList class is programmed. A basic LinkedList is likely only going to have a pointer to the most recently added item and it will traverse the list in the reverse order of how the data was added to the list.

It works like this:

First item is added to the list:
Memory Address = 1200
Head Pointer = 1200
Data = 1
Link = NULL

Second item added:
Memory Address = 1400
Head Pointer = 1400
Data = 2
Link = 1200

Third item added:
Memory Address = 2000
Head Pointer = 2000
Data = 3
Link = 1400

So as each new data item is added to the LinkedList, you could look at it like the data is being added to the front of the list. The first data item's link will always be pointing to null (signifying that it's the end of the list) and the "first" data item on the list (where the head pointer points) is always changed to the newly added item, so it's always pointing to the most recently added item on the list.

So when you go to print it, the only "link" that the list can reference is the head pointer, which it prints first, then it prints the item linked to by that item, and traverses the list as such, like so:

2000 -> 1400 -> 1200 -> NULL
3 2 1

If you want to be able to print the data in the order it was added to the list, then you need to modify how the LinkedList class works. You want to make the LinkedList keep pointers to the first node and the last node (set both to the same address when the list has its first item added), and when a new node is created, change last's link to the new node's address, make sure the new node has a NULL link, then change last to the new node (the order of these 3 operations is important!). And then when the print function starts from the first node, it traverses the list in the same order as the items were added.

This post has been edited by callahan09: 13 April 2010 - 01:57 PM

Was This Post Helpful? 0
  • +
  • -

#3 jessicalegner  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 1
  • View blog
  • Posts: 66
  • Joined: 05-June 09

Re: linked list reversal

Posted 14 April 2010 - 08:23 AM

well, to make this answer short, I do have an .append() which would add to the end instead of the front as .insert() did. That did the trick. :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1