Basically, the assignment is to create a huge integer class by using a singly linked list, wherein each element of the linked list holds one digit of the number of the huge int. I only have to do addition and multiplication, and addition works. Multiplication *should* work, as far as I'm concerned, but I've spent the last several hours trying to figure out why it isn't working, and I've been unsuccessful. Here's the code...I know it's not as clean (or efficient) as it could be, so I apologize in advance if it's difficult to read.
linkedList.h:
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <iostream>
using namespace std;
struct Digit {
int digit;
Digit * next;
};
class linkedList {
public:
linkedList();
~linkedList();
void add(int datum);
void printList(Digit * d/*, int len*/);
int returnLength();
void setHead(int d);
Digit * getHead();
Digit * getLast();
void deleteItem(); // Deletes first item in list
//int isInList(int num); // If item is not in list, returns 0, else returns number of item
//bool remove(int num);
//void removeHelper(int num);
//double returnItemPrice(int num);
//double returnListPrice();
bool isEmpty();
linkedList & operator=(const linkedList & l);
void reverseList();
//bool operator==(const linkedList & other) const;
//bool operator!=(const linkedList & other) const;
private:
Digit * head;
int length;
};
#endiflinkedList.cpp
#include <iostream>
#include "linkedlist.h"
using namespace std;
linkedList::linkedList() {
head = NULL;
length = 0;
}
linkedList::~linkedList() {
while (head)
deleteItem();
}
void linkedList::add(int datum) {
Digit * p = new Digit;
p->digit = datum;
p->next = head;
head = p;
length++;
}
void linkedList::printList(Digit * d) {
if (d->next) {
printList(d->next);
}
cout << d->digit;
}
int linkedList::returnLength() {
return length;
}
void linkedList::setHead(int d) {
head->digit = d;
}
Digit * linkedList::getHead() {
return head;
}
Digit * linkedList::getLast() {
Digit * p = head;
while (p->next) p = p->next;
return p;
}
bool linkedList::isEmpty() {
return (head == NULL);
}
linkedList & linkedList::operator=(const linkedList & l) {
while (head)
deleteItem();
Digit * current = l.head;
while (current) {
add(current->digit);
current = current->next;
}
return *this;
}
void linkedList::deleteItem() {
Digit * temp = head->next;
delete head;
head = temp;
}
void linkedList::reverseList() {
Digit * first = head, *next = NULL;
while (first->next != NULL) {
next = first->next;
first->next = next->next;
next->next = head;
head = next;
}
}hugeInt.h:
#ifndef HUGEINT_H
#define HUGEINT_H
#include <iostream>
#include "linkedList.h"
using namespace std;
class HUGE_INT {
public:
HUGE_INT();
HUGE_INT(unsigned long int i);
HUGE_INT(const HUGE_INT & h);
~HUGE_INT();
// method to assign an arbitrary unsigned long int to the HUGE_INT (which the constructors may use)
void assign(unsigned long int i);
HUGE_INT add(HUGE_INT h);
HUGE_INT mult(HUGE_INT h);
int getNumDigits();
HUGE_INT & operator=(const HUGE_INT & h);
void printNum();
private:
linkedList * number;
HUGE_INT multHelper(HUGE_INT & thisBetterWork, linkedList * h, Digit * big, Digit * small);
int numDigits;
};
#endifhugeInt.cpp:
#include <iostream>
#include "hugeInt.h"
using namespace std;
HUGE_INT::HUGE_INT() {
//number->setHead(0);
number = new linkedList;
numDigits = 0;
}
HUGE_INT::HUGE_INT(unsigned long int i) {
number = new linkedList;
this->assign(i);
}
HUGE_INT::HUGE_INT(const HUGE_INT & h) {
// call assignment operator
*this = h;
}
HUGE_INT::~HUGE_INT() {
number->~linkedList();
}
HUGE_INT HUGE_INT::add(HUGE_INT h) {
HUGE_INT p;
if (number->isEmpty()) {
cout << "number is empty" << endl;
//number->add(0);
}
int carry = 0, temp = 0;
Digit * a = number->getHead();
Digit * b = h.number->getHead();
while (a && b) {
temp = carry + a->digit + b->digit;
carry = temp / 10;
p.number->add(temp % 10);
a = a->next;
b = b->next;
}
if (a && !b) {
while (a) {
temp = a->digit + carry;
carry = temp / 10;
p.number->add(temp % 10);
a = a->next;
}
}
else if (!a && b) {
while (b) {
temp = b->digit + carry;
carry = temp / 10;
p.number->add(temp % 10);
b = b->next;
}
}
if (carry > 0) {
p.number->add(carry);
}
cout << endl;
p.number->reverseList();
this->number = p.number;
return p;
}
HUGE_INT HUGE_INT::multHelper(HUGE_INT & thisBetterWork, linkedList * h, Digit * big, Digit * small) {
// HUGE_INT total;
HUGE_INT temp;
int carry = 0;
int temp2 = 0;
int multiplier = 1;
int save = multiplier;
while (big) {
carry = 0;
save = multiplier * 10; // save off multiplier
multiplier /= 10;
while (multiplier) { // adjusts for shift in multiplication problems where
temp.number->add(0); // more than one line is needed by adding zeroes
multiplier /= 10; // to the end of the number
}
multiplier = save; // put saved off value back in multiplier
while (small) {
temp2 = (big->digit * small->digit + carry); // temp2 is product of all digits plus carry
carry = temp2 / 10; // carry is digit in ten's place if not zero
temp.number->add(temp2 % 10); // add digit in one's place to temp
small = small->next;
}
if (carry > 0) {
temp.number->add(carry);
}
cout << "Current total is ";
temp.number->reverseList();
temp.printNum();
cout << endl << endl << endl;
HUGE_INT total = thisBetterWork.add(temp); // adds total for current line to total for whole problem
//temp3 = total;
//if (temp3.number->isEmpty()) cout << "temp 3 is empty" << endl;
cout << "Absolute total is ";
thisBetterWork.printNum();
cout << endl << endl << endl;
big = big->next;
small = h->getHead();
temp.~HUGE_INT();
}
thisBetterWork.printNum();
return thisBetterWork;
}
HUGE_INT HUGE_INT::mult(HUGE_INT h) {
HUGE_INT total;
Digit * p = number->getHead();
Digit * q = h.number->getHead();
if (h.getNumDigits() > getNumDigits()) {
return multHelper(total, h.number, p, q);
}
else {
return multHelper(total,number, q, p);
}
return total;
}
int HUGE_INT::getNumDigits() {
return number->returnLength();
}
void HUGE_INT::assign(unsigned long int i) {
unsigned long int temp = i;
while (temp) {
number->add(temp % 10); // adds last digit to list
temp /= 10; // Strips temp of last digit
}
number->reverseList();
}
HUGE_INT & HUGE_INT::operator=(const HUGE_INT & h) {
number = h.number;
return *this;
// should work after = operator is done in linkedList class
}
void HUGE_INT::printNum() {
Digit * d = number->getHead();
number->printList(d);
}main.cpp:
#include <iostream>
#include "hugeInt.h"
using namespace std;
int reverse_num(int sourcenum) {
int temp = sourcenum;
int sum = 0;
while (temp) {
sum *= 10; // sum = sum * 10
sum += temp % 10; // sum = sum + the remainder of temp / 10
temp /= 10; // temp = temp / 10
}
return sum;
}
int main() {
HUGE_INT a(25);
cout << "a is ";
a.printNum();
cout << endl;
HUGE_INT b(301);
cout << "b is ";
b.printNum();
cout << "\n\nTrying to multiply..." << endl;
HUGE_INT c = a.mult(b);
cout << "Succeeded." << endl;
cout << "a * b is ";
c.printNum();
return 0;
}Well, I should say I know what the problem is (I think), I just don't know how to fix it. The problem is in the multHelper() function in hugeInt.cpp. The HUGE_INT that should hold the total product just resets every time, and doesn't even hold a value outside of the while loop. If someone could tell me what I'm doing wrong, I would greatly appreciate it. Thanks
EDIT: I also added a main.cpp in case anyone wants to test it