+- Southperry.net (https://www.southperry.net)
+-- Forum: Social (https://www.southperry.net/forumdisplay.php?fid=14)
+--- Forum: Rubik's Cube (https://www.southperry.net/forumdisplay.php?fid=58)
+--- Thread: Linked Lists in C (/showthread.php?tid=30421)
Linked Lists in C - Sivrat - 2010-09-14
Ok, i have a programming assignment due tomorrow, and I can not really grasp Linked lists very well. Well, i mean i understand what they are and know some of the syntax, but ive been staring at my computer for the last few hours dumbfounded as to how to add or subtract 2 seperate linked lists. Thats my assignment, i have to read 2 numbers from a file into seperate linked lists (in reverse order), read whether they should be added or subtracted, do the function and save new sum/difference in a new linked list and print it out. Apparently this is in case of large integers that can't be stored as just int. There was a example posted that added 2 linked lists of the same size, but it doesnt work on different sizes and doesnt work for subtraction.
I feel dumb when programming classes make me unsure how to do basic math with a computer.
Linked Lists in C - Fiel - 2010-09-14
Post word for word what the assignment says.
Linked Lists in C - Sivrat - 2010-09-14
The Problem
The unsigned int type in C requires 4 bytes of memory storage. With 4 bytes we can store integers as large as 2^32-1; but what if we need bigger integers, for example ones having hundreds of digits? If we want to do arithmetic with such very large numbers we cannot simply use the unsigned data type, because there is not enough space, in an int, to store that large of a value. So what is a workaround? One way of dealing with this is to use a different storage structure for integers, such as linked lists. If we represent an integer as a linked list, we can represent very large integers, where each digit is a node in the list. Since the integers are allowed to be as large as we like, linked lists will prevent the possibility of overflows in representation. However we need new functions to add, subtract, read and write these very large integers.
Write a program that will manipulate such arbitrarily large integers. Each integer should be represented as a linked list of digits. Your program will be required to read in big integers from a file, print big integers, and do addition or subtraction as required.
Your program should store each decimal digit (0-9) in a separate node of the linked list. In order to perform addition and subtraction more easily, it is better to store the digits in the list in the reverse order. For instance, the value 1234567890 might be stored as:
0->9->8->7->6->5->4->3->2->1
Note: Although this seems counter-intuitive, it makes the code slightly easier, because in all standard mathematical operations, we start with the least significant digits. When you add 123 and 415 to get 538, you start adding with the least significant digit; meaning, you start by adding the 3 and the 5 to get the 8 in the final answer. Now, with linked lists, if there is some operation that you want to perform over the entire length of the list, do you want to start performing this operation at the beginning of the list or at the end of the list? Of course, it is easier to start performing any indicated operations at the front of the list, and then you simply traverse the list (in the normal way shown in class) and you perform the operations as you walk down the list. As a result, since you want to start working on list from the front of the list AND since you start adding/subtracting numbers from the LEAST significant digit, it makes the most sense that the number is stored in REVERSE order (as depicted above), with the least significant digit being stored in the first node of the linked list.
Your program should include the following functions:
• a function that will read the digits of the large integer character by character, convert them into integers and place them in nodes of a linked list. The pointer to the head of the list is returned. The input to this function is simply the character array of numbers that was read in from the file.
• a function that will print an integer that is stored as a linked list.
• a function that will add two integers represented as linked lists and returns a pointer to the resulting list.
• a function that compares two integers and returns -1 if the first is less than the second, 0 if they are equal, and 1 if the first is greater than the second.
• a function that will subtract one integer from the other and return a pointer to the resulting list. Since you’ll be dealing with positive integers only, the result should be a positive number. To ensure that the result is integer you should subtract the smaller number from the larger one (or equal). For this purpose you’re given a function that compares two large integers and returns –1, 0 or 1, depending on whether the first number is less than, equal to or greater than the second number.
Input/Output Specification
Your program should allow the user to do two things:
1) Add two big integers
2) Subtract to big integers
Instead of getting input from the user, you read in input from a file, "bigint.txt". The name MUST BE “bigint.txt”. Have this AUTOMATED. Do not ask the user to enter “bigint.txt”. You should read in this automatically. (This will expedite the grading process.)
The input file format is as follows:
The first line will contain a single positive integer, n, representing the number of operations to carry out. The next n lines will contain one problem each. Each line will have three integers separated by white space. The first integer on each of these lines is guaranteed to either be 1 or 2, indicating addition and subtraction, respectively. The next two integers on the line will be the two operands for the problem. You may assume that these two integers are non-negative, are written with no leading zeros (unless the number itself is 0) and that the number of digits in either of the numbers will never exceed 200.
***NOTE***: You should generate your output to a FILE that you will call “out.txt”. In particular, you should generate one line of output per each input case. Your output should fit one of the two following formats:
X + Y = Z
X – Y = Z
corresponding to which option was chosen. For the first option, always print the first operand first. For the second option, always print the larger of the two operands first. If the two operands are equal, the same number is printed both times.
***WARNING***
Your program MUST adhere to this EXACT format (spacing capitalization, use of dollar signs, periods, punctuation, etc). The graders will use very large input files, resulting in very large output files. As such, the graders will use text comparison programs to compare your output to the correct output. If, for example, you have two spaces between in the output when there should be only one space, this will show up as an error even through you may have the program correct. You WILL get points off if this is the case, which is why this is being explained in detail. Minimum deduction will be 10% of the grade, as the graders will be forced to go to text editing of your program in order to give you an accurate grade. So as an example, here is the first format shown above (if the instruction was an addition):
X + Y = Z
First we have one of the “integers”. Then we have ONE space. Then we have a plus sign. Then we have ONE space. Then we have the second “integer”. Then we have ONE space. Then we have the equals sign. Then we have ONE space. Finally, we have the answer with NO spaces afterwards.
Again, your output MUST ADHERE EXACTLY to the line shown above.
Implementation Restrictions
You must use the following struct:
struct integer{
int digit;
struct integer *next;
}
Whenever you store or return a big integer, always make sure not to return it with any leading zeros. Namely, make sure that the last node in the linked list returned does NOT store 0, unless the number stored is 0, in that case a single node should have 0 in it.
The prototypes for the functions you will write are below. You may include other functions, but it is required for these functions to be included.
//Preconditions: the first parameter is string that stores
// only contains digits, doesn't start with
// 0, and is 200 or fewer characters long.
//Postconditions: The function will read the digits of the
// large integer character by character,
// convert them into integers and place them in
// nodes of a linked list. The pointer to the // head of the list is returned.
struct integer* read_integer(char* stringInt);
//Preconditions: p is a pointer to a big integer, stored in
// reverse order, least to most significant
// digit, with no leading zeros.
//Postconditions: The big integer pointed to by p is
// printed out.
void print(struct integer *p);
//Preconditions: p and q are pointers to big integers,
// stored in reverse order, least to most
// significant digit, with no leading zeros.
//Postconditions: A new big integer is created that stores
// the sum of the integers pointed to by p
// and q and a pointer to it is returned.
struct integer* add(struct integer *p, struct integer *q);
//Preconditions: p and q are pointers to big integers,
// stored in reverse order, least to most
// significant digit, with no leading zeros.
//Postconditions: A new big integer is created that stores
// the absolute value of the difference
// between the two and a pointer to this is
// returned.
struct integer* subtract(struct integer *p, struct integer *q);
//Preconditions: Both parameters of the function are
// pointers to struct integer.
//Postconditions: The function compares the digits of two
// numbers recursively and returns:
// -1 if the first number is smaller than the second,
// 0 if the first number is equal to the second number,
// 1 if the first number is greater than the second.
int compare(struct integer *p, struct integer *q);
Sample Input File
3
1 8888888888 2222222222
2 9999999999 10000000000
2 10000000000 9999999999
Corresponding Output (saved to file called “out.txt”
8888888888 + 2222222222 = 11111111110
10000000000 – 9999999999 = 1
10000000000 – 9999999999 = 1
Deliverables
Turn in a single file, bigintll.c, over Webcourses that solves the specified problem. If you decide to make any enhancements to this program, clearly specify them in your header comment so the grader can test your program accordingly.
Linked Lists in C - Fiel - 2010-09-14
The assignment goes into great detail about how to do this and gives you a lot of freedom about how to go about doing this so long as you get the correct answer.
Sounds like you'll need to manually implement carry and reduction operations on big integers. This seems like so much fun. I wish I had the time to do it. I could use a brush up on my linked lists.
Each linked list is stored in an array filled with linked lists. Read in the data, parse the data, then clear the buffers you created. Read one line at a time. Do one thing at a time.
Linked Lists in C - Stereo - 2010-09-14
Fiel Wrote:Read one line at a time. Do one thing at a time.
Recurse everything! No limits!
Also, implement subtraction as A + -B (instead of plus(a,b), it'll be add(a,b,negative)). It'll be awesome.
1234
- 207
4 + -7 = 7 (carry -1)
-1 + 3 + -0 = 2 (carry 0)
2 + -2 = 0 (carry 0)
1 + -0 = 1
1027!
I wish they'd taught subtraction this way in school.
1000
- 1
0 + -1 = 9 (carry -1)
-1 + 0 = 9 (carry -1)
-1 + 0 = 9 (carry -1)
-1 + 1 = 0
999!
Linked Lists in C - Sivrat - 2010-09-15
ok, ive tried and tried and still cant figure out how to do this with linked lists. I guess i just dont understand linked lists. Anyone want to do it for me for 10k nx? or maybe some in game stuff in khaini.
Linked Lists in C - Stereo - 2010-09-15
I won't get into the C part of it, but in terms of a linked list,
for example, the first input
1 8888888888 2222222222
To take input, start reading the line
1: adding
[space]: begin new bigInteger
8: create a LL element, with the value 8, pointing to null. Keep the pointer to this element
8: create a LL element, with the value 8, pointing to the previous element
[...]
8: ditto. Keep a pointer to this element.
[space]: end bigInteger, return the pointer to the previous element as the bigInteger. Begin another bigInteger
2: do the same as before, with returning a pointer to the final element when you hit the end of the line.
With them stored in backwards order like this, adding and subtracting are simple iterations over the linked lists - the output bigInteger's first element is the sum of the 2 first elements, next is the sum of next two, etc., with carries included to complicate things slightly.
Personally I would only use their given headers for the first elements of the bigIntegers, and have the next ones go
Code:
struct integer* combine(integer* a, integer* b, integer carry, integer sign)
// In this case, you'd have
{
integer temp <- a.digit + sign*b.digit + carry
this.digit <- temp%10
this.next <- addsub(a.next, b.next, temp/10, sign)
}Code:
sign*abs(temp/10)In fact I would probably have
Code:
struct integer* add(struct integer *p, struct integer *q)
return combine(p,q,0,1);
struct integer* subtract(struct integer*p, struct integer*q)
return combine(p,q,0,-1);The rest of the functions look a lot like this aside from printing. Print would have to go something like (using pseudocode again here)
Code:
print (integer* a)
{
if (a.next == null ptr)
print a.digit
else
print(a.next);
print a.digit
}Linked Lists in C - Sivrat - 2010-09-15
ok, ive got most of it working. Only 2 things i have wrong atm, I cant get the compare function to really work at all, and I'm not sure how to get it to stop printing 0's if they are unnecessary, so 1000-999 shows up as 0001.
i have this for the compare so far:
Code:
int compare(struct integer *p, struct integer *q)
{
int j;
while (p != NULL){
if(q==NULL){
return 1;}
else if (q!=NULL){
if (p>q){
j=1;}
else if (p<q){
j= -1;}
else if (p==q){
j= 0;}
}
p= p->next;
q= q->next;
}
return (j);
}it works if the one number is more digits then the other, but if they are the same number of digits it acts up. Dont know how im going to get it to work with 1000 and like 1001.
Linked Lists in C - Stereo - 2010-09-15
Digitwise comparison is pretty simple but I'm too lazy to read your code.
Initialize to "equal"
Current digit the same -> keep any previous results
Current digit higher in one number -> that number has 'advantage' (ex. 19 vs. 20 - 2 > 1 so the second is larger, lower digits don't matter)
One has nonzero digits, other doesn't -> return, that number is bigger
Both have zero digits -> return advantage or equal
Killing trailing zeros is pretty easy with a higher level keeping track of pointers
a -> last non-zero LL item
b -> current LL item
Iterate b through the linked list, updating a when you find non-zeros. Then when you reach the end, set the current 'a' to have a null pointer.
As for why your code acts up when they're equal length - P is null, so it breaks from the loop without checking if Q is also null. while(p != null && q != null) would fix this, though you'd have to add a line checking if p == NULL inside the loop.
Alternative approach, because recursion is sexier than while loops:
Code:
compare (*p, *q) {
if (p == null) return -1;
if (q == null) return 1;
// or vice versa
if (p->next != null && q -> next != null) {
c = compare(p->next, q->next)
if (c == 0) {
if (p > q) return 1;
if (q > p) return -1;
else return 0;
}
else return c;
}
else return 0;
}Linked Lists in C - Sivrat - 2010-09-15
yeah i tried using that code and it acted up wierd. i put in
5555 4000
4000 5555
10000 9999
9999 10000
1000 1000
and got
4000 - 5555 = -18445
5555 - 4000 = 1555
9999 - 10000 = 9999
10000 - 9999 = 00001
1000 - 1000 = 0000
im not terribly worried about the 0's. I need to get this part working and then focus on lesser problems
also, should note, the last one isnt returning 0. Dont know whether its returning 1 or -1, but its not 0.
mine was getting the two 10000 and 9999's right, but everything else returned the same.
yeah, its just returning -1 for everything. huh
Linked Lists in C - Stereo - 2010-09-15
Okay, took the time to look at the spec for how that should behave so I can get the signs right >_>
p < q: -1
p = q: 0
p > q: 1
Code:
compare (*p, *q) {
if (p == null) return -1;
if (q == null) return 1;
// or vice versa
if (p->next != null && q -> next != null) {
c = compare(p->next, q->next)
if (c == 0) {
if (p > q) return 1;
if (q > p) return -1;
else return 0;
}
else return c;
}
else return 0;
}p = null & q = null -> return 0
p = 4, q = 5, c = 0 -> return -1
p = 0, q = 5, c = -1 -> return c = -1 (repeat x3)
return -1
Since 4000 < 5555 this seems to be returning the correct value of -1.
Whereas your code,
Code:
int compare(struct integer *p, struct integer *q)
{
int j;
while (p != NULL){
if(q==NULL){
return 1;}
else if (q!=NULL){
if (p>q){
j=1;}
else if (p<q){
j= -1;}
else if (p==q){
j= 0;}
}
p= p->next;
q= q->next;
}
return (j);
}p=0, q=5 -> j = -1 (repeat x3)
p=4, q=5 -> j = -1
now p == null so it should break out of the while loop and return j=-1.
I'm not sure what you have differently but this seems like it would work correctly?
Linked Lists in C - Sivrat - 2010-09-15
Code:
int compare(struct integer *p, struct integer *q)
{
int j;
while (p != NULL){
if(q==NULL){
return 1;}
else if (q!=NULL){
if (p>q){
j=1;}
else if (p<q){
j= -1;}
else if (p==q){
j= 0;}
}
p= p->next;
q= q->next;
}
return (j);
}Code:
int compare(struct integer *p, struct integer *q)
{
int c;
if (p == NULL) return -1;
if (q == NULL) return 1;
// or vice versa
if (p->next != NULL && q -> next != NULL) {
c = compare(p->next, q->next);
if (c == 0) {
if (p > q) return 1;
if (q > p) return -1;
else return 0;
}
else return c;
}
else return 0;
}returns all -1s, which is wrong for the first, third, and last ones. The only thing i changed in your code was i added a semicolon after c = compare(p->next, q->next) since it wouldnt let me compile, and capitalized the null to NULL. And I declared c, since it was undeclared.
Linked Lists in C - Stereo - 2010-09-15
Yeah, my code's kinda messed up cause I had one of the if statements backwards.
Code:
compare (*p, *q) {
if (p == NULL) return -1;
if (q == NULL) return 1;
// or vice versa
if (p->next == NULL && q -> next == NULL)
c = 0;
else
c = compare(p->next, q->next);
if (c == 0) {
if (p > q) return 1;
if (q > p) return -1;
else return 0;
}
else return c;
}I should probably also note that although I have used "<-" in pseudocode, I mean it as being equivalent to the assignment operator (=), not some pointer thing.
There's also the version for people who like playing fast and dangerous with concepts like true and false... this may not actually return +1 and -1 but some other positive/negative number...
Code:
compare (*p, *q) {
if (p == NULL) return -1;
if (q == NULL) return 1;
// or vice versa
if (p->next == NULL && q -> next == NULL)
return (p>q)-(q>p);
else
c = compare(p->next, q->next);
if (c==0) return (p>q)-(q>p);
}
else return c;
}Linked Lists in C - Sivrat - 2010-09-15
still getting a return of -1 for all but the 3rd one.
Linked Lists in C - Stereo - 2010-09-15
I edited my post a bunch of times, the early versions wouldn't work right.
Linked Lists in C - Sivrat - 2010-09-15
ok, I see that. and it looks like it should work to me, but its still returning -1 all but the 3rd case. I did some fiddling and when i changed the
if (q > p) return -1;
to
if (q > p) return 0;
it returns 0, 0, 1, -1, 0.
for some reason, with both our codes it always returns -1 if the numbers are the same number of digits.
Linked Lists in C - Sivrat - 2010-09-15
turned in. never did get the compare function working. oh well, lets see how much i get off for it.