class Node{
public:
int data;
Node* next;
};
Node* GetRandomPosition(Node* head)
{
//I know that this doesn't really give a random position
//but I'm not worrying about that right now.
for(Node* node = head; node->next != 0; node = node->next)
{
int random = rand() % 2;
if(random==0)
return node;
}
return node;
}
void MyFunction(Node* head1, Node* head2)
{
Node** ptr_head1 = &GetRandomPosition(head1);
Node** ptr_head2 = &GetRandomPosition(head2);
Node** temp;
*temp = *ptr_head1;
*ptr_head1 = *ptr_head2;
*ptr_head2 = *temp;
}
linked list question
Lets say I have two linked lists, L1 and L2. I want to take some random position in L1 (R1) and a random position in L2 (R2) and then take everything that comes after R1 (including R1) and put it after R2 and everything after R2 (including R2) and put it after R1. For example, let's say that:
L1: 1,2,3,4
L2: 5,6,7,8
R1: a pointer to the number 2
R2: a pointer to the number 7
Then we'd get:
L1: 1,7,8
L2: 5,6,2,3,4
I tried to code it but I ran into trouble. Here's what I tried:
The function I described is "MyFunction". The problem is, VS doesn't let me give the address of a function, so &GetRandomPosition(head1) is undefined. How can I get around this?
Thanks.
Hi,
I think that you don't want to take the address of the function itself (just to clarify).
GetRandomPosition returns the value in a temporary variable and taking its address is impossible (obviously).
The logic behind your "myfunction"-function is ill-conceived. You are trying to do some sort of pointer swapping, which will not accomplish the desired effect.
In order to change your linked list elements, you'll need to change the "Next" pointers. In your case:
L1: 1,2,3,4
L2: 5,6,7,8
R1: a pointer to the number 2
R2: a pointer to the number 7
R1 : Change the next pointer of the previous element (1) to point to R2
R2 : Change the next pointer of the previous element (6) to point to R1
This isn't yet satisfying logic since the first element doesn't have a previous element, but that's something for you to figure out.
Someone who is talented with std::list could explain how to do this kind of operation with the standard library.
Cheers!
[edit] corrected a minor error
[Edited by - kauna on November 8, 2007 8:44:08 AM]
I think that you don't want to take the address of the function itself (just to clarify).
GetRandomPosition returns the value in a temporary variable and taking its address is impossible (obviously).
The logic behind your "myfunction"-function is ill-conceived. You are trying to do some sort of pointer swapping, which will not accomplish the desired effect.
In order to change your linked list elements, you'll need to change the "Next" pointers. In your case:
L1: 1,2,3,4
L2: 5,6,7,8
R1: a pointer to the number 2
R2: a pointer to the number 7
R1 : Change the next pointer of the previous element (1) to point to R2
R2 : Change the next pointer of the previous element (6) to point to R1
This isn't yet satisfying logic since the first element doesn't have a previous element, but that's something for you to figure out.
Someone who is talented with std::list could explain how to do this kind of operation with the standard library.
Cheers!
[edit] corrected a minor error
[Edited by - kauna on November 8, 2007 8:44:08 AM]
This looks like a homework question which reminded me of this blog. It makes a very interesting point and the academic link is interesting as well. To sum it up, if you plot programming ability against a population sample, you will end up with a double-bell curve:
which roughly means that you can divide the population into two groups - those that can program well and those that can't. The linked references above note that very few people managed to move from the non-programmer set to the other.
The point is, linked lists and pointer manipulation are fairly basic and fundamental concepts for a programmer. Maybe you should work out which set you are in and then re-evaluate your future. You don't want to be the guy that ends up with code appearing here.
Skizz
Ability | | *** *** | * * * * | * ** * |** **--------------------- |
which roughly means that you can divide the population into two groups - those that can program well and those that can't. The linked references above note that very few people managed to move from the non-programmer set to the other.
The point is, linked lists and pointer manipulation are fairly basic and fundamental concepts for a programmer. Maybe you should work out which set you are in and then re-evaluate your future. You don't want to be the guy that ends up with code appearing here.
Skizz
Quote:Original post by Skizz
The point is, linked lists and pointer manipulation are fairly basic and fundamental concepts for a programmer. Maybe you should work out which set you are in and then re-evaluate your future. You don't want to be the guy that ends up with code appearing here.
I think that's overly harsh. I'm a grad student in CS and I had a tough time starting out with pointer manipulation too. In fact pretty much every programmer I know did.
Certainly some people have to work harder at this stuff than others, but I don't like the point of view that programming ability makes you a member of some special class of human and nobody else should bother with it. It comes off as being very elitist.
Besides, how do you know what daniel_i_l's goals in the field are? He could be a math student who just needs the basics. Or he could be just learning for fun.
Sorry, I don't have time right now to address the original question, but that point of view annoys me.
The major problem with software is that anyone can do it and produce something that works which leads others less technical to think they are capable. There is no professional status or accredition that is applied to software developers the way it is done in, say, electronics. As an analogy, I toyed around with electronics as a kid and even made some circuits work but I never got the hang of how a transitor really worked and as such would not really have much chance of getting a job designing electronic circuits (even after doing it to degree level - thankfully the software half of the course pulled me through). Software seems to be different in that lots of people think its the job for them but there's no one around to say otherwise. Perhaps if there was a more rigorous professional status to go with the software development job, then we might not have so much buggy software (and no need for stupid EULAs that accept no responsibility for faulty code).
From my own experience, I have worked with very few (i.e. < 10) good developers in my 18 or so years of professional software development (i.e. being paid to do it). Most of the coders I work with, now and in the past, produce poor code and don't spend time refining their skills. Here are two anonymised examples from the project I am currently working on:
This level of coding is the norm! The company I'm currently contracting for has a C test as part of its interview process. The interviewee is given a PC with a default installation of DevStudio - a tool required for the job (would you hire a plumber who didn't know how to use a spanner?) The first coding question involves writing an algorithm to sort an array (bubble sort will do) and the second is to solve the 8 queens on an 8x8 chess board problem. Both problems can be solved in a dozen or so lines of code. Of all the interviews done since they started doing this test, some get the sorting problem but no one has managed the queen problem. One person even sneaked out the building.
The point I'm trying to make, based on personal experience and the comments on several web sites (this being one) is that most potential software development employees really can't do the job and never get any better.
There's nothing wrong with elitism, many professions fall into this - doctors, engineers, etc. and it may make things better if there was more of it in software.
The truth hurts1.
Skizz
1. Maybe not as much as jumping on a bicycle with no saddle.
From my own experience, I have worked with very few (i.e. < 10) good developers in my 18 or so years of professional software development (i.e. being paid to do it). Most of the coders I work with, now and in the past, produce poor code and don't spend time refining their skills. Here are two anonymised examples from the project I am currently working on:
// first example block_of_code while (condition) { block_of_code // identical to code above }// second example - convert drive number to drive letter switch (drive_number) { case 1: drive_name = "A"; break; case 2: drive_name = "B"; break; case 3: drive_name = "C"; break; // repeated in same manner until... case 26: drive_name = "Z"; break; }
This level of coding is the norm! The company I'm currently contracting for has a C test as part of its interview process. The interviewee is given a PC with a default installation of DevStudio - a tool required for the job (would you hire a plumber who didn't know how to use a spanner?) The first coding question involves writing an algorithm to sort an array (bubble sort will do) and the second is to solve the 8 queens on an 8x8 chess board problem. Both problems can be solved in a dozen or so lines of code. Of all the interviews done since they started doing this test, some get the sorting problem but no one has managed the queen problem. One person even sneaked out the building.
The point I'm trying to make, based on personal experience and the comments on several web sites (this being one) is that most potential software development employees really can't do the job and never get any better.
There's nothing wrong with elitism, many professions fall into this - doctors, engineers, etc. and it may make things better if there was more of it in software.
The truth hurts1.
Skizz
1. Maybe not as much as jumping on a bicycle with no saddle.
Quote:Original post by Simian Man
Besides, how do you know what daniel_i_l's goals in the field are? He could be a math student who just needs the basics.
That would be a very badly designed course if the student needed to understand pointer manipulation in a language like C/C++ as a 'basic' requirement. Surely, a maths student would be better off using something like matlab?
This question is computer science style question - abstract and unlikely to be of any use to real world development (hands up, who's needed to do this in a real world application?)
If it's learning for fun then that is to be encouraged - there's nothing like learning new things (I still do). The caveat of course is that finding this difficult could be a sign that programming isn't going to be an enjoyable career.
Skizz
As for the original linked list problem. Whatever you do, don't brute force a solution by trying out every combination of pointer manipulation you can think of. Take a step back and get out a piece of paper and a pencil and draw out the problem using boxes for the nodes and lines for the links and produce a sequence of steps that transform what you have into what you want. This pencil-and-paper technique is very useful, especially in interviews where they sometimes try to confuse you. It has happened to me - an interview question had a linked-list style structure but the implementation obfuscated the algorithm and stored the nodes in reverse order - new nodes added to the front of the list. Only through drawing the lists on paper as the code executed did the subtle trick become apparent.
This will hopefully show you which pointers need changing at each stage.
Skizz
Before: |-------| |-------| |-------| L1 --->| A *---+-->| B *---+-->| C | |-------| |-------| |-------| |-------| |-------| |-------| L2 --->| 1 *---+-->| 2 *---+-->| 3 | |-------| |-------| |-------|Step 1: |-------| |-------|L1 --->| A *---+-->| B | |-------| |-------| |-------| |-------| |-------| L2 --->| 1 *---+-->| 2 *---+-->| 3 | |-------| |-------| |-------| |-------|R1 --->| C | |-------|Step 2: |-------| |-------|L1 --->| A *---+-->| B | |-------| |-------| |-------|L2 --->| 1 | |-------| |-------|R1 --->| C | |-------| |-------| |-------| R2 --->| 2 *---+-->| 3 | |-------| |-------|and so on....After: |-------| |-------| |-------| |-------| L1 --->| A *---+-->| B *---+-->| 2 *---+-->| 3 | |-------| |-------| |-------| |-------| |-------| |-------|L2 --->| 1 *---+-->| C | |-------| |-------|
This will hopefully show you which pointers need changing at each stage.
Skizz
Skizz,
I'm going to take a guess and say that you're not the best programmer in the world.
That means there are people out there who are better than you. Probably more than a few and maybe even some of the people who post regularly on this forum.
To them, maybe YOU'RE not good enough to use a compiler and need to leave the profession you've worked at for 18 years in order to improve the general quality of software.
That's the basic problem with elitism. Nobody ever thinks that THEY are inferior - it's always EVERYONE ELSE.
I've been writing software for 10 years and just yesterday, on this board, I got my relative lack of programming skills bashed. However, even as my ego took a shot, I was never discouraged from programming, nor was I told I didn't have what it took to improve.
The truth, as I see it, is that skill in anything is a combination of how much talent you have and how hard you work and you can make up for a lack of one with an abundance of the other.
For you to discourage someone who came here looking for help just because you think he might not have what it takes is wrong (not to mention rude).
[Edited by - linternet on November 8, 2007 11:31:41 AM]
I'm going to take a guess and say that you're not the best programmer in the world.
That means there are people out there who are better than you. Probably more than a few and maybe even some of the people who post regularly on this forum.
To them, maybe YOU'RE not good enough to use a compiler and need to leave the profession you've worked at for 18 years in order to improve the general quality of software.
That's the basic problem with elitism. Nobody ever thinks that THEY are inferior - it's always EVERYONE ELSE.
I've been writing software for 10 years and just yesterday, on this board, I got my relative lack of programming skills bashed. However, even as my ego took a shot, I was never discouraged from programming, nor was I told I didn't have what it took to improve.
The truth, as I see it, is that skill in anything is a combination of how much talent you have and how hard you work and you can make up for a lack of one with an abundance of the other.
For you to discourage someone who came here looking for help just because you think he might not have what it takes is wrong (not to mention rude).
[Edited by - linternet on November 8, 2007 11:31:41 AM]
Quote:Original post by linternet
I've been writing software for 10 years and just yesterday, on this board, I got my relative lack of programming skills bashed. However, even as my ego, took a shot, I was never discouraged from programming, nor was I told I didn't have what it took to improve.
Yeah, sorry about that [smile]
I tend to disagree with Skizz, though. The fundamental issue is not one of competence (that's just a symptom) but actually one of maturity. Most bad programmers are bad because they consider their code good enough—maybe they never faced a situation where the quality of their code proved to be a problem, or maybe they did and they just accept as an universal truth the fact that writing a 26-case switch statement is a necessary evil when programming. Once a programmer understands that code can be improved, and that such improvement is desirable, there are few people who are too incompetent to do it. Obviously, if programming is done by people who don't suspect that code can be improved (those who learned programming on the fly) or those who don't have the time to improve (those programming as a secondary task in their job), then it will be done badly (for instance, physics research mixes both conditions, and it sucks at coding).
Now, the issue with pointers is that it's a shitty fecal batch of semantics, mixing around reference semantics, iterator semantics, option semantics and reseating semantics. Plus, it's generally explained by jargon lovers who delight in making beginners cringe at terms like "lvalue" and "rvalue", or oversimplifying mother figures who explain them as "house addresses, except that it's for data instead of houses". Strangely enough, the languages who teach their pointer-like semantics the fastest are languages which don't even mention memory. Well, right, it's not strange, it's actually quite normal [smile]
Given that pointers are a lousy mechanism, it's usually easier to revert to simpler semantics to solve the problem, and then translate the algorithm. In this example, a linked list A1...An is defined by saying that Ak is preceded by Ak-1 (except A1) and followed by Ak+1 (except An). By considering two lists An and Bm, you want to splice the end of An (starting at Aa included) at position Bb, and conversely splice the end of Bm at position Aa included. So, in the new situation, everything is as in the initial situation, except that now Aa-1 is followed by Bb and Bb-1 is followed by Aa.
To translate this into pointers:
void Splice(list A, list B){ // Aa list Aa = getRandPos(A); // Aa-1 list Aa_ = Aa -> prev; // Bb list Bb = getRandPos(B); // Bb-1 list Bb_ = Bb -> prev; // Aa-1 is followed by Bb, // unless a = 1 and so Bb follows nothing. Bb -> prev = Aa_; if (Aa_) Aa_ -> next = Bb; // Bb-1 is followed by Aa, // unless b = 1 and so Aa follows nothing. Aa -> prev = Bb_; if (Bb_) Bb_ -> next = Aa;}
It's interesting how saying that programming might not be your best career option leads to such responses. Do other careers have the same issue? If I was tone deaf and training to be a violinist, would advice along the lines of 'this ain't for you kid' lead to similar outcry1? The article I indirectly linked to not only identified the double bell curve indicating that there are people who 'get' programming and those who don't, but also went on to say that even after a few years of tutoring and teaching, very few people moved from one group to the other.
linternet, you are quite right, I am not the best programmer and I know it. I spend a lot of free time learning about programming, trying out new ideas, new languages, going over old code and so on. It would be true to say that there is no such thing as 'the best programmer' - the field is too huge. However, I do believe that there should be a minimum level of competence required before calling oneself a software engineer, more than a degree - other engineering disciplines have them, why not programming?
It's a complex issue, there is definately a lot of code being written that is sub-standard but at the same time there's few ways to identify at interview who's going to produce the goods.
Perhaps we delude ourselves with new and feature rich IDEs into thinking that anyone can program and that it is much easier than it really is. Or maybe it's a management issue not understanding the complexities of what appears to be simple.
Also, linternet, don't feel too bad about being bashed on these boards, it's even happened to me. These days I make sure I double check what I post, even writing test applications to verify code.
Skizz
1. But then we wouldn't have Beethoven
linternet, you are quite right, I am not the best programmer and I know it. I spend a lot of free time learning about programming, trying out new ideas, new languages, going over old code and so on. It would be true to say that there is no such thing as 'the best programmer' - the field is too huge. However, I do believe that there should be a minimum level of competence required before calling oneself a software engineer, more than a degree - other engineering disciplines have them, why not programming?
It's a complex issue, there is definately a lot of code being written that is sub-standard but at the same time there's few ways to identify at interview who's going to produce the goods.
Perhaps we delude ourselves with new and feature rich IDEs into thinking that anyone can program and that it is much easier than it really is. Or maybe it's a management issue not understanding the complexities of what appears to be simple.
Also, linternet, don't feel too bad about being bashed on these boards, it's even happened to me. These days I make sure I double check what I post, even writing test applications to verify code.
Skizz
1. But then we wouldn't have Beethoven
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement