Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Need help with logic in my program

linked list

  • Please log in to reply
5 replies to this topic

#1 sensationality

sensationality

    CC Lurker

  • Just Joined
  • Pip
  • 4 posts

Posted 18 March 2011 - 06:30 AM

Hi,

I am making a program which stores a matrix (2D) as a list (linked list) of 1 dimension, where each node in the list stores the value and position of the element in the matrix, as well as the next node. Furthermore, only non-zero elements (value and position) from the matrix must be stored in the list

For example

0 2 1
0 0 2

would be represented as the (value, position): (2,1) --> (1,2) --> (2,5)


My problem is, given only the list without the actual 2D representation of the matrix, I need to find the transpose of the list (matrix). Transpose is found by switching the rows and columns.

The transpose of the above example would be:

0 0
2 0
1 2

and the list now becomes (2,2) --> (1,4) --> (2,5).

I was wondering if someone can guide me on the logic of how to do this. I was thinking I'd have to use recursion somehow, but I am not sure, exactly what I would do.

Thanks in advance
  • 0

#2 gregwarner

gregwarner

    Obi Wan of Programming

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1586 posts
  • Location:Arkansas
  • Programming Language:C, Java, C++, C#, PHP, Transact-SQL

Posted 18 March 2011 - 08:01 AM

You would not need recursion at all.

Knowing the matrix's width, w, and its height, h, the transpose function of a position p would be as follows:

T(p) := h*(p mod w) + floor(p / w)

The floor() function just means to ignore the remainder, i.e., integer division. In C/C++, this is the ordinary behavior of the "/" operator when used on integer operands.

Just write a function to implement the above algorithm, and call it on every item in your list, and your matrix will be transposed.
  • 0

#3 sensationality

sensationality

    CC Lurker

  • Just Joined
  • Pip
  • 4 posts

Posted 18 March 2011 - 08:51 AM

Thanks a lot for your reply. That function indeed works (as I have tested with a few test cases), and I was trying to come up with something similar for quite a while. Thanks for the assistance.

Well, now I can get the new position of the elements in the list. However, the following is my concern now: Once I get the new position, in order to put the value in the new position, I would have to create another pointer and transverse the list accordingly. However, this would lead to O(s^2) run time. The assignment specification says:

"Method transpose must have running time O(s log s), where s is the number of
nonzero elements in the matrix"

Would there be any way to do this in O(s log s) time? This is why I was thinking you would to recursively switch the list.
  • 0

#4 gregwarner

gregwarner

    Obi Wan of Programming

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1586 posts
  • Location:Arkansas
  • Programming Language:C, Java, C++, C#, PHP, Transact-SQL

Posted 18 March 2011 - 11:01 AM

I see what you're saying. You have to rearrange the order of the elements in the list. I was just thinking all you needed to do was set the updated position parameter.

Essentially what you are doing is applying a transformation on the list, and then re-sorting the list using its new position parameter (which has been run through the transformation function) as the value to compare.

Personally, I would use the merge sort algorithm, since it run in O(n log n) time.
  • 0

#5 sensationality

sensationality

    CC Lurker

  • Just Joined
  • Pip
  • 4 posts

Posted 20 March 2011 - 11:53 AM

Thank you so much for your help.

I used merge sort after getting the new location for each element in my list. After sorting it with merge sort I was able to get a transpose.

Thanks again for the help gregwarner!
  • 0

#6 gregwarner

gregwarner

    Obi Wan of Programming

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1586 posts
  • Location:Arkansas
  • Programming Language:C, Java, C++, C#, PHP, Transact-SQL

Posted 20 March 2011 - 12:19 PM

My pleasure. Glad it worked for ya.
  • 0





Also tagged with one or more of these keywords: linked list

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download