Thread: Algorithm for multiplying linked lists?

  1. #1
    Registered User
    Join Date
    Apr 2006
    Posts
    5

    Algorithm for multiplying linked lists?

    Hi im trying to create a function to multiply two linked lists filled with integers.

    I have a function that correctly adds two already.
    I have a function that multyplies one list by 10(ie adds a 0 to end)
    I have a function that reverses the list.
    I have a function that multiplies two digits and returns the result along with any carry. (shown later)

    when i first input numbers they go in backwards.

    So inputing the number 43 generates a list of 3->4.
    The add function gives the answer non backwards tho so adding 3->4 and 2->5 gives the list 5->9.

    Now i need to create a multiply function. I just need a basic idea of how to do it.

    Basically im thinking given two lists N1 and N2 to multiply:

    Keep the first digit in N1 and multiply it with every number in N2 to get a list. Then add this list to 10 times the list generated by taking the second digit of N1 and multiplying by all the digits in N2.
    Continue doing this untill all numbers in N1 have been exhausted and continually multiply the adding number by a different power of 10. Basically exactly how one would do it in real life.

    Im having trouble seeing the code for this however.

    So here is my multiply two digits function:

    Code:
    int multiply_two_digits(int d1, int d2, int *carry_in, int *result, int *carry_out){
    	*result = d1*d2+*carry_in;
    	*carry_out=*result/10;
    	if(*result>=10){
    		*result=*result%10;
    	}
    	return 0;
    }
    which returns the result and any carry.

    Any ideas or tips? Everytime i try writing this function it gets way to complicated and i cant figure it out. Thanks for any help.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    Write a function that adds one integer list to another. (looks like that's done)
    Write another function that multiplies an integer list by an integer.
    Then use what is sometimes called "grade school" multiplication, i.e. iterate over one list, and multiply the other list by the current number, and add the resulting list to some total.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Apr 2006
    Posts
    5
    Thx got it to work doing what you said altho you forgot to mention i need to also times it by 10 sometimes.

    For instance
    2222 *111 = 2222*1+2222*1*10+2222*1*10*10. I got it to work putting this into code so thx. The thing that helped me most was the suggestion to make a function that multiplies an entire list by 1 single int. THX .

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  2. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  3. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  4. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM