Ad:

C++ Discussion Thread
Marked Solved
Views: 1089

Oct 28th, 2008

Pointer / Linked list question

Expand Post »

Okay, I'm making a program that will let you traverse a maze where the beginning is the top right corner (coming from the right) and it ends in the bottom left corner (going to the right). We have a 2D array for the board and are using a stack to keep the values entered so that if they hit a dead end, they can back track to where they messed up and try another path.

Now, I'm obsessive of making my program look good, so I decided to make it so that it looks at the previous input and the recent output, and then uses that to to tell what symbol should be inputted (like if you came from the left to right, it prints out a straight line, if from up to right, it does a sort of corner that shows how it goes down then turns right).

Would it be better to have two pointers (one pointing to top and the other to the previous response) or would it be better to handle this some other way?

Second, the first value, no matter what it is, the previous value should be 'R' cause it starts from the right. How would I initiate it so that R is the previous value even though it shouldn't be within the stack?

If anything isn't clear, tell me and I'll try to figure out another way to phrase it. I'm just a little sleepy at the moment to really put it into major details.

Similar Threads

Double linked list - possible memory error in C
Minimal element in a linked list? in Computer Science
linked list question in C
linked list..quick question in Java
Seg Fault ~ Linked List Delete in C

DemonGal711

Reputation Points: 18

Solved Threads: 10

Junior Poster

Offline

190 posts
since Apr 2008

Permalink

Oct 28th, 2008

Re: Pointer / Linked list question

I thought I had the specs right until you said down-right instead of up-right in your 2nd paragraph.

Maybe a picture will be helpful?

Also, what are you using to graphically display your program? Is it a Console program or are you using some kind of GUI API? This question is merely out of curiosity.

Alex Edwards

Reputation Points: 392

Solved Threads: 108

Posting Shark

Offline

971 posts
since Jun 2008

Permalink

Oct 28th, 2008

Re: Pointer / Linked list question

Well, I can see why, I totally murdered describing it. Obviously I shouldn't try to explain things on no sleep.

Basically, say this is my maze. I want it to fill in so that it looks like this. The actual maze is basically a 2D array surrounded by a border.

If you look at those two pictures, you can see that to make the line that runs through the maze, you need to know where it is coming from and which direction it is going to. I figured to handle most of that, I could just use two pointers, one that points to the top of the stack, and the one that points to the one item below the top.

That should work in most cases except the beginning. At the beginning, it needs to interpret the previous item in the stack as an 'R'. Of course, the problem is that the stack should be empty. I'm not sure how to handle that.

I thought about initializing my stack with an 'R' in it, but I didn't think that would be good cause if it was told to pop that value out, it would mess up the program. So, any clue how to handle this? Can I make it so that it won't pop that value out? Any help?

And, your last question Edwards, just the standard output stream. Nothing fancy cause we haven't learned any of that yet.

Last edited by DemonGal711; Oct 28th, 2008 at 6:15 pm.

DemonGal711

Reputation Points: 18

Solved Threads: 10

Junior Poster

Offline

190 posts
since Apr 2008

Permalink

Oct 28th, 2008

Re: Pointer / Linked list question

ehh, now i'm confused... it would be helpful to see some code you've done already, but this is my suggestion: don't use a stack. it's a maze... a pretty straightforward graph. if you know where you should start, and where you should finish, you bfs through the graph, keeping track of node parents in another array. (you should set the first slot to null or something). after your bfs has traversed the graph, you have the list of parent nodes which you then follow from the last to the root, marking the steps as you go, which gives you the path.
this seems like the easiest way to do it, only problem would be if you were assigned that problem to solve using some other way..

gregorynoob

Reputation Points: 12

Solved Threads: 5

Junior Poster in Training

Offline

86 posts
since Jun 2008

Permalink

Oct 28th, 2008

Re: Pointer / Linked list question

At the moment, the only coding I have is taking in the code and outputting what the maze looks like. I can give you that, but it isn't gonna help with what I'm asking. Right now I'm just planning how to tackle the stack and getting the answers to the parts I can't solve by myself.

And, I have to use a stack, it's part of the program guidelines. We're suppose to let the user input which direction to go. If they hit a dead end, we send them back and let them make a different choice.

DemonGal711

Reputation Points: 18

Solved Threads: 10

Junior Poster

Offline

190 posts
since Apr 2008

Permalink

Oct 29th, 2008

Re: Pointer / Linked list question

Okay, looking at it again, I'm only need one pointer, but that still doesn't solve my issue.

Could I just do something that my stack takes in a value (say L cause the person wants to move left). So, my stack would be comprised of an L and the NULL. Could I just say something like:

if (tPtr->next == NULL)
{ prev = 'R'; }
else prev = tPtr->next;

cause basically I need it to assume the previous value is 'R' at the beginning, but other then that, it needs to take the previous input and use it. Think that would work?

DemonGal711

Reputation Points: 18

Solved Threads: 10

Junior Poster

Offline

190 posts
since Apr 2008

Permalink

Oct 29th, 2008

Re: Pointer / Linked list question

I don't think just L and R will cut it.

Lets say your maze is a rectangle that has n number of points, and there are walls inside it that construct a number of paths. Now the user needs to take the path that will take him/her to the finish.

You'll probably have an initial state for your maze where you have the points and the paths which are open from that point. From each point you could ideally move in 4 directions, Left(L), Right(R), Top(T) and Down (D) to the next point.

If your start point is X, push X onto your stack. Then based on the state for X, you could give the user a set of valid moves, say R, D. The user chooses R, so you move to the point at location R, push that onto the stack and give the user the next set of valid moves. If at any time you reach a point which has no valid moves, then you pop it off the stack, and ask the user to choose a different option.

Something like this might work ..

stilllearning

Reputation Points: 161

Solved Threads: 43

Posting Whiz

Offline

309 posts
since Oct 2007

Permalink

Oct 29th, 2008

Re: Pointer / Linked list question

Actually, I think I figured it out. But just in case, this is what I'm worried about.

In general there are 6 different symbols I could put in each cell of that 2D array:
Symbol 1
Symbol 2
Symbol 3
Symbol 4
Symbol 5
Symbol 6

Now, since the maze starts from the opening to the right, the only three values that the program should focus on are the first three cause they touch the left side of the space which would create a line like I want.

The problem is that, I ask the user to choose a direction. That direction is stored in my stack. Then my program looks at that direction and the previous one. That will work for all cases except the first one.

For the very first input, whatever it is, if I tell the program to look at the previous output, it will point at NULL instead of a directional input.

What I'm trying to figure out is if there is a way I can make it that so that the program will know that the previous value for the first input is 'R'.

Right now I'm gonna try something like this:

C++ Syntax (Toggle Plain Text)
if (tPtr->next == NULL)
{ prev = 'R'; }
else prev = tPtr->next;
if (tPtr->next == NULL)
{ prev = 'R'; }
else prev = tPtr->next;

and see if it works. If not though, any other suggestions?

DemonGal711

Reputation Points: 18

Solved Threads: 10

Junior Poster

Offline

190 posts
since Apr 2008

Permalink

Oct 30th, 2008

Re: Pointer / Linked list question

You could just have a pointer called "start" and when "current == start" you can set the input as you need.

stilllearning

Reputation Points: 161

Solved Threads: 43

Posting Whiz

Offline

309 posts
since Oct 2007

This thread is solved

Either the thread starter or a moderator has marked this thread as solved. You can most likely trust the responses and answers given. There is most likely no reason for any further responses to be posted here. If you have a related question, please start a new thread in this forum instead.

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: 2d arrays

Next Thread in C++ Forum Timeline: Best book to buy to learn C++ then to be able to code GUI?

DaniWeb Message

Cancel Changes

User Name
Password