BigInt Linked List Long Division
This is what I have to do by Sunday:
http://www.cs.ucf.edu/courses/cop350...ssignment4.doc
Basically, the assignment is to read in two large numbers into linked lists of digits, and then divide the two to get a remainder and quotient.
Currently I have code that reads the numbers from the file and into two linked lists of digits. Other than that my mind is just.. blank. I know I have to long divide, but I cannot seem to figure out how to do that in code.
I've spent the last 3 days hacking away at this with no avail. I've sifted through every known code database trying to find an example, with again, no avail. I realize what needs to be done is subtraction from the front of the bigger number, however, coding this seems quite the challenge.
If anyone would be willing to explain this to me in pseudo code, or really in any way at all, I would be very grateful.
Here is my current file IO code with a function to print the lists:
Code:
#include <stdio.h>
typedef struct node
{
int digit;
struct node *next;
} listnode;
//function prototypes
void printlist(listnode* list);
int main(){
char loc[64];
int listAcnt = 0;
int listBcnt = 0;
char c;
listnode* listA = NULL;
listnode* listB = NULL;
listnode* result = NULL;
listnode* pCur = NULL;
listnode* newnode = NULL;
FILE *Fp;
printf("Enter the name of the file containing the numbers\n");
scanf("%s", loc);
Fp = fopen(loc, "r"); // Open the file
if(Fp==NULL) { //check if not valid filename
printf("Error: can't open file.\n");
return -1; //error so quit
}
else {
c = fgetc(Fp); //read first char of listA
while(c != '\n' && c != EOF) { // Read until new line or EOF
newnode = (listnode*)(malloc(sizeof(listnode))); // Make space for new digit
newnode->digit = c - '0'; // Convert char to int, ascii conversion, and store
newnode->next = NULL; //Set next pointer to null to terminate list for now
if(listA == NULL) { //
listA = newnode;
pCur = listA;
}
else { // Otherwise, simply add it.
pCur->next = newnode;
pCur = pCur->next;
}
listAcnt++; // iterate digit counter
c = fgetc(Fp); // read in new char
}//end a while
c = fgetc(Fp); //read first char of listB
while(c != '\n' && c != EOF) { // While we're not at a new line or the end of the file.
newnode = (listnode*)(malloc(sizeof(listnode))); // Create new node
newnode->digit = c - '0'; // Add data, adjusting the ascii value to make it a real int
newnode->next = NULL;
if(listB == NULL) { // if null add first node
listB = newnode;
pCur = listB;
}
else { // add digit to list
pCur->next = newnode;
pCur = pCur->next;
}
listBcnt++; //iterate digit counter
c = fgetc(Fp); // read in new char
}//end b while
}//end file read in code
printf("Closing file...");
fclose(Fp);
//TEST
printlist(listA);
printlist(listB);
while(1);
return 0;
}
//This function prints any linked list of digits
void printlist(listnode* list){
listnode* pTrav = list;
while(pTrav!=NULL){
printf("%d", pTrav->digit);
pTrav=pTrav->next;
}
printf("\n");
return;
}
