| Author |
Message |
Guest
|
 Posted:
Thu Mar 03, 2005 7:57 am Post subject:
collating (mixing) two linked lists using C |
|
|
Dear all,
1)In one of our implementation for an application we are supposed to
collate two linked lists.The actual problem is like this:
There are two singularly linked lists, the final output will be a
"perfectly shuffle" of the lists together into a single list. The new
list should consist of consecutively alternating nodes from both
lists.Note that both these linked lists have same kind of data
structure in their nodes.
solution:
The logic which I thought for implementing this is to create temporary
node which resembles the nodes in the input linked lists and then copy
second node into it,swap the pointers to insert the second lists first
node into the first lists second node and proceed so on recursively by
inserting the second lists node in between the first lists node.
Is my thinking correct?I believe this is not that efficient way of
doing it.Can some one let me know how effectively should we implement
this collation between two linked lists?
2)I came across the following code snippet regarding linked lists:
struct _tagElement
{
int m_cRef;
unsigned char m_bData[20];
struct _tagElement * m_next;
} NODE, * PNODE;
PNODE DoesWhat (PNODE pn1, PNODE pn2)
{
PNODE * ppnV = &pn1;
PNODE * ppn1 = &pn1;
PNODE * ppn2 = &pn2;
for ( ; *ppn1 || *ppn2; ppn1 =
&((*ppn1)->m_next))
{
if (!(*ppn1) || (0 <
memcmp((*ppn1)->m_bData, (*ppn2)->m_bData,
sizeof((*ppn2)->m_bData))))
{
PNODE pn = *ppn1;
*ppn1 = *ppn2;
pn2 = (*ppn2)->m_next;
(*ppn1)->m_next = pn;
}
}
return *ppnV;
}
I inferred from this code,that the actual functionality of the function
"DoesWhat" is to collate two linked list as stated in query (1)
referred in this post.But my friend disagrees.I said that the function
doeswhat takes first node of two linked lists(pn1 is first node of
linkedlist1,pn2 is first node of linkedlist2-This is my assumption(need
not be correct!)),and the code inside inserts nodes of list2 into nodes
of list1,also the list will be sorted in increasing order of number of
characters present in the array m_bData.
Is my understanding and assumption regarding the input params for
function "doeswhat" correct?Note that I dont have full code with me,so
this code puzzled me,so I have to make it out myself!.
Sorry if it looks too immature to ask,but I thought better learn now
then never.I wish I am able to prove to my friend that I am
correct,though I am ready to accept my fault incase I am disproved with
proper proof.
I appologise incase this is OT for this group.Kindly refer me to proper
group in that case.
Looking farward to all your replys and advanced thanks for the same,
Regards,
s.subbarayan |
|
| Back to top |
|
 |
Terje Mathisen
Guest
|
| Posted:
Thu Mar 03, 2005 7:57 am Post subject:
Re: collating (mixing) two linked lists using C |
|
|
s_subbarayan@rediffmail.com wrote:
| Quote: | Dear all,
1)In one of our implementation for an application we are supposed to
collate two linked lists.The actual problem is like this:
There are two singularly linked lists, the final output will be a
"perfectly shuffle" of the lists together into a single list. The new
list should consist of consecutively alternating nodes from both
lists.Note that both these linked lists have same kind of data
structure in their nodes.
[snip]
Sorry if it looks too immature to ask,but I thought better learn now
then never.I wish I am able to prove to my friend that I am
correct,though I am ready to accept my fault incase I am disproved with
proper proof.
I appologise incase this is OT for this group.Kindly refer me to proper
group in that case.
|
This is the perfect group to frequent if you want to learn something
about computer architecture, but for askin questions like yours, your
results might be more mixed.
However, I have an idea for you:
Concatenate the two list into a single array, while marking each item as
coming from either the first or the second half, then do a random
permute of the array before checking that the order is the one you want.
If it isn't, try again from the top.
For a more optimized version, you should note that the quite expensive
initial step, consisting of the array allocation and copying of both
lists can be skipped, so that only the permute and check stages remain!
| Quote: | Looking farward to all your replys and advanced thanks for the same,
|
You're welcome!
Terje
--
- <Terje.Mathisen@hda.hydro.com>
"almost all programming can be viewed as an exercise in caching" |
|
| Back to top |
|
|
Grumble
Guest
|
| Posted:
Thu Mar 03, 2005 2:04 pm Post subject:
Re: collating (mixing) two linked lists using C |
|
|
s_subbarayan@rediffmail.com wrote:
| Quote: | In one of our implementation for an application we are supposed to
collate two linked lists.
|
=> comp.programming |
|
| Back to top |
|
|
Hank Oredson
Guest
|
| Posted:
Thu Mar 03, 2005 11:18 pm Post subject:
Re: collating (mixing) two linked lists using C |
|
|
"Terje Mathisen" <terje.mathisen@hda.hydro.com> wrote in message
news:d06dtb$8tk$1@osl016lin.hda.hydro.com...
| Quote: | s_subbarayan@rediffmail.com wrote:
Dear all,
1)In one of our implementation for an application we are supposed to
collate two linked lists.The actual problem is like this:
There are two singularly linked lists, the final output will be a
"perfectly shuffle" of the lists together into a single list. The new
list should consist of consecutively alternating nodes from both
lists.Note that both these linked lists have same kind of data
structure in their nodes.
[snip]
Sorry if it looks too immature to ask,but I thought better learn now
then never.I wish I am able to prove to my friend that I am
correct,though I am ready to accept my fault incase I am disproved with
proper proof.
I appologise incase this is OT for this group.Kindly refer me to proper
group in that case.
This is the perfect group to frequent if you want to learn something about
computer architecture, but for askin questions like yours, your results
might be more mixed.
However, I have an idea for you:
Concatenate the two list into a single array, while marking each item as
coming from either the first or the second half, then do a random permute
of the array before checking that the order is the one you want.
If it isn't, try again from the top.
|
There might be better results using a polynomial mixing
of the two lists, perhaps using the standard CRC polynomial.
Then much of the work could be accompished with simple
shift and add instructions, and this could be coded in assembler.
| Quote: | For a more optimized version, you should note that the quite expensive
initial step, consisting of the array allocation and copying of both lists
can be skipped, so that only the permute and check stages remain!
|
Yes, you could make a linked list of pointers to the two linked
lists, and traverse that for each step in the polynomail mixing.
| Quote: | Looking farward to all your replys and advanced thanks for the same,
You're welcome!
|
Hope I was able to help!
--
... Hank
http://home.earthlink.net/~horedson
http://home.earthlink.net/~w0rli |
|
| Back to top |
|
|
John R. Levine
Guest
|
| Posted:
Thu Mar 03, 2005 11:46 pm Post subject:
Re: collating (mixing) two linked lists using C |
|
|
| Quote: | s_subbarayan@rediffmail.com wrote:
In one of our implementation for an application we are supposed to
collate two linked lists.
=> comp.programming
|
Perhaps it's time for comp.homework. |
|
| Back to top |
|
|
Hank Oredson
Guest
|
| Posted:
Fri Mar 04, 2005 7:56 am Post subject:
Re: collating (mixing) two linked lists using C |
|
|
<s_subbarayan@rediffmail.com> wrote in message
news:1109911805.974778.157630@l41g2000cwc.googlegroups.com...
| Quote: |
Hank Oredson wrote:
"Terje Mathisen" <terje.mathisen@hda.hydro.com> wrote in message
news:d06dtb$8tk$1@osl016lin.hda.hydro.com...
s_subbarayan@rediffmail.com wrote:
Dear all,
1)In one of our implementation for an application we are
supposed to
collate two linked lists.The actual problem is like this:
There are two singularly linked lists, the final output will be a
"perfectly shuffle" of the lists together into a single list. The
new
list should consist of consecutively alternating nodes from both
lists.Note that both these linked lists have same kind of data
structure in their nodes.
[snip]
Sorry if it looks too immature to ask,but I thought better learn
now
then never.I wish I am able to prove to my friend that I am
correct,though I am ready to accept my fault incase I am disproved
with
proper proof.
I appologise incase this is OT for this group.Kindly refer me to
proper
group in that case.
This is the perfect group to frequent if you want to learn
something about
computer architecture, but for askin questions like yours, your
results
might be more mixed.
However, I have an idea for you:
Concatenate the two list into a single array, while marking each
item as
coming from either the first or the second half, then do a random
permute
of the array before checking that the order is the one you want.
If it isn't, try again from the top.
There might be better results using a polynomial mixing
of the two lists, perhaps using the standard CRC polynomial.
Then much of the work could be accompished with simple
shift and add instructions, and this could be coded in assembler.
For a more optimized version, you should note that the quite
expensive
initial step, consisting of the array allocation and copying of
both lists
can be skipped, so that only the permute and check stages remain!
Yes, you could make a linked list of pointers to the two linked
lists, and traverse that for each step in the polynomail mixing.
Looking farward to all your replys and advanced thanks for the
same,
You're welcome!
Hope I was able to help!
--
... Hank
Hank,
Thanks for your reply and terjeMathisens input.But can you please
explain or point me to some links where I can learn about "polynomial
mixing of the two lists, perhaps using the standard CRC polynomial"
said in your post as I have not come across it till now.
|
Google.
--
... Hank
http://home.earthlink.net/~horedson
http://home.earthlink.net/~w0rli |
|
| Back to top |
|
|
Guest
|
| Posted:
Fri Mar 04, 2005 7:56 am Post subject:
Re: collating (mixing) two linked lists using C |
|
|
Hank Oredson wrote:
| Quote: | "Terje Mathisen" <terje.mathisen@hda.hydro.com> wrote in message
news:d06dtb$8tk$1@osl016lin.hda.hydro.com...
s_subbarayan@rediffmail.com wrote:
Dear all,
1)In one of our implementation for an application we are
supposed to
collate two linked lists.The actual problem is like this:
There are two singularly linked lists, the final output will be a
"perfectly shuffle" of the lists together into a single list. The
new
list should consist of consecutively alternating nodes from both
lists.Note that both these linked lists have same kind of data
structure in their nodes.
[snip]
Sorry if it looks too immature to ask,but I thought better learn
now
then never.I wish I am able to prove to my friend that I am
correct,though I am ready to accept my fault incase I am disproved
with
proper proof.
I appologise incase this is OT for this group.Kindly refer me to
proper
group in that case.
This is the perfect group to frequent if you want to learn
something about
computer architecture, but for askin questions like yours, your
results
might be more mixed.
However, I have an idea for you:
Concatenate the two list into a single array, while marking each
item as
coming from either the first or the second half, then do a random
permute
of the array before checking that the order is the one you want.
If it isn't, try again from the top.
There might be better results using a polynomial mixing
of the two lists, perhaps using the standard CRC polynomial.
Then much of the work could be accompished with simple
shift and add instructions, and this could be coded in assembler.
For a more optimized version, you should note that the quite
expensive
initial step, consisting of the array allocation and copying of
both lists
can be skipped, so that only the permute and check stages remain!
Yes, you could make a linked list of pointers to the two linked
lists, and traverse that for each step in the polynomail mixing.
Looking farward to all your replys and advanced thanks for the
same,
You're welcome!
Hope I was able to help!
--
... Hank
Hank, |
Thanks for your reply and terjeMathisens input.But can you please
explain or point me to some links where I can learn about "polynomial
mixing of the two lists, perhaps using the standard CRC polynomial"
said in your post as I have not come across it till now.
Regards,
s.subbarayan |
|
| Back to top |
|
|
Guest
|
| Posted:
Fri Mar 04, 2005 7:56 am Post subject:
Re: collating (mixing) two linked lists using C |
|
|
Hi,
If you are not able to give me proper reply,please dont pass circaustic
comments,because any one can do that,I believe professional like you
would behave like a professional !
Regards,
s.subbarayan |
|
| Back to top |
|
|
Bill Todd
Guest
|
| Posted:
Fri Mar 04, 2005 5:21 pm Post subject:
Re: collating (mixing) two linked lists using C |
|
|
s_subbarayan@rediffmail.com wrote:
| Quote: | Hi,
If you are not able to give me proper reply,please dont pass circaustic
comments,because any one can do that,I believe professional like you
would behave like a professional !
|
He is.
You're not.
- bill |
|
| Back to top |
|
|
s.subbarayan
Guest
|
| Posted:
Sat Mar 05, 2005 4:10 pm Post subject:
Re: collating (mixing) two linked lists using C |
|
|
Bill Todd <billtodd@metrocast.net> wrote in message news:<p9KdnYVAY_9Az7XfRVn-gQ@metrocastcablevision.com>...
| Quote: | s_subbarayan@rediffmail.com wrote:
Hi,
If you are not able to give me proper reply,please dont pass circaustic
comments,because any one can do that,I believe professional like you
would behave like a professional !
He is.
You're not.
- bill
|
Neither u! |
|
| Back to top |
|
|
Hank Oredson
Guest
|
| Posted:
Sat Mar 05, 2005 8:42 pm Post subject:
Re: collating (mixing) two linked lists using C |
|
|
"s.subbarayan" <s_subbarayan@rediffmail.com> wrote in message
news:c396173e.0503050310.267e2857@posting.google.com...
| Quote: | Bill Todd <billtodd@metrocast.net> wrote in message
news:<p9KdnYVAY_9Az7XfRVn-gQ@metrocastcablevision.com>...
s_subbarayan@rediffmail.com wrote:
Hi,
If you are not able to give me proper reply,please dont pass circaustic
comments,because any one can do that,I believe professional like you
would behave like a professional !
He is.
You're not.
- bill
Neither u!
|
Someone notify this entities mommy that she left her compter logged in.
--
... Hank
http://home.earthlink.net/~horedson
http://home.earthlink.net/~w0rli |
|
| Back to top |
|
|
s.subbarayan
Guest
|
| Posted:
Tue Mar 08, 2005 7:57 am Post subject:
Re: collating (mixing) two linked lists using C |
|
|
"Hank Oredson" <horedson@earthlink.net> wrote in message news:<orkWd.1929$cN6.1050@newsread1.news.pas.earthlink.net>...
| Quote: | "s.subbarayan" <s_subbarayan@rediffmail.com> wrote in message
news:c396173e.0503050310.267e2857@posting.google.com...
Bill Todd <billtodd@metrocast.net> wrote in message
news:<p9KdnYVAY_9Az7XfRVn-gQ@metrocastcablevision.com>...
s_subbarayan@rediffmail.com wrote:
Hi,
If you are not able to give me proper reply,please dont pass circaustic
comments,because any one can do that,I believe professional like you
would behave like a professional !
He is.
You're not.
- bill
Neither u!
Someone notify this entities mommy that she left her compter logged in.
|
I feel you are best fit to do that! |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in