Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

addition and subtraction ..linked lists

Posted on 1998-04-30
7
Medium Priority
?
285 Views
Last Modified: 2013-12-14
I am looking for algorithms which will add and subtract two dynamically allocated linked lists. These lists may be of different sizes. Do I need to add zeros to the front of the shorter list? If so how do I tell when the shorter list needs to be added to? Do I compare the lists first? Please help. Thanks
0
Comment
Question by:brianhill
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
7 Comments
 
LVL 22

Expert Comment

by:nietod
ID: 1169038
answer coming.
0
 
LVL 2

Expert Comment

by:rayb
ID: 1169039
Can you elaborate on what you mean by adding and subtracting?
i.e.  Is this a list of integers and you need the elements of the lists added together?  Or do you need to add or subtract the nodes of the list, resulting in an expansion or reduction of the list?
Also, are you using STL?

0
 
LVL 22

Expert Comment

by:nietod
ID: 1169040
Hmmmm.  My first answer (now deleted) assumed that when you said "add two linked list" you mean add the items in one list to another list so that the list contained both sets of items.  but now I'm guessing that that is wrong.  what you are asking about is arithmetically adding numbers stored in each element of a linked list?  Is that right?

If so, my first question to you (yes, the expert is asking questions) is how do you plan to store the result.  There are two main strategies.  The first is that one list is altered to contain the results.  That is, each entry will contain the original value plusss the associated value fromt he other list.  The second strategy is to create a third list that contains the results.   This leaves the two input lists unchanged.  Which way are you planning to go?  (This matters for the best answer to your question.)
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 

Author Comment

by:brianhill
ID: 1169041
elaboration: I would have two seperate linked lists of integers and each entire list would represent a single integer. Then I would like for these two seperate representations to be either added or subtracted resulting in a third linked list.For example if I had a linked list with three nodes, 9  7  3 as the values of those respective nodes, then the linked list would represent the integer 973.I hope this clarifies my question. Thanks for the help.  
0
 
LVL 22

Accepted Solution

by:
nietod earned 100 total points
ID: 1169042
answer coming.
0
 
LVL 22

Expert Comment

by:nietod
ID: 1169043
Just as an aside, you would be much better of using dynamically allocated arrays for this.  It would be faster, more memory efficent and easier to program.  I can provide details if you are interested.

Lets say you use the following structure  to store digits.

struct Digit
{
   char Dig;  // should be 0-9 only.  Could use enum.  Should have validity checks.
   Digit *NxtDigit;
}

The "numbers" should be stored with linked lists that start with the lleast significant digit and proceed to the most significant.  Thus 123 would be stored as 3->2->1.

Then you could do.

Digit * Add(Digit *Src1,Digit *Src2)
{
   Digit *Result = NULL;;
   Digit *LastDigit = NULL;
   bool Carry = false;

   while (Src1 || Src2)
   {
      int D1;
      int D2;
      int DR;

      if (Src1)
      {
        D1 = Src1->Dig;
        ++Src1;
      }
      else
         D1 = 0;

      if (Src2)
      {
        D2 = Src2->Dig;
        ++Src2;
      }
      else
         D2 = 0;

      R = D1 + D2;
      if (Carry)
        ++R;
      if (R > 10)
      {
         R -= 10;
        Carry = true;
      }
      else
         Carry = false.
     
     Digit *R = new Digit;
     R->Dig = DR;
     R->NxtDigit = NULL;
     If (LastDigit)
        LastDigit->NxtDigit = R;
     else
        Result = R
     LastDigit = R;  
   }
   return Result;
}


That should be close.  Might not be 100% correct.  Try it and let me know.
0
 
LVL 22

Expert Comment

by:nietod
ID: 1169044
Just checking up.  Is this working for you?
0

Featured Post

Tech or Treat!

Submit an article about your scariest tech experience—and the solution—and you’ll be automatically entered to win one of 4 fantastic tech gadgets.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
How to install Selenium IDE and loops for quick automated testing. Get Selenium IDE from http://seleniumhq.org Go to that link and select download selenium in the right hand column That will then direct you to their download page. From that p…
The viewer will learn how to use NetBeans IDE 8.0 for Windows to connect to a MySQL database. Open Services Panel: Create a new connection using New Connection Wizard: Create a test database called eetutorial: Create a new test tabel called ee…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
Suggested Courses

618 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question