Reputation: 49
I'm doing some graph exercises in C and was confused by the sample solutions. I've attached my code below with additions from the sample solutions I don't understand yet.
My question is why in the sp_algo
function multiple declaration and initialization of struct queueNode adjCell;
and struct Point new_point;
works? On the other hand, if I, for example, declare and initalize struct Point end = {2, 6};
in the main function twice, it returns an error:
previous definition of 'end' was here & redefinition of 'end'.
The code is not so important but I'll explain it briefly. The task was to get the shortest path from a starting point to a end point in a maze given by array A. For that I implemented a BFS. There's also an implementation of a Queue which I need in the sp_algo
in order to implement the BFS.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define GRIDSIZE 7
#define MAXQSIZE 49
struct Point{
int x;
int y;
};
struct queueNode
{
struct Point pt; // The cordinates of a cell
int dist; // cell's distance of from the source
};
bool isValid(int row, int col)
{
// return true if row number and column number
// is in range
return (row >= 0) && (row < GRIDSIZE) &&
(col >= 0) && (col < GRIDSIZE);
}
struct queueNode queue[MAXQSIZE]; //initialize QUEUE
int front = -1;
int rear = -1;
int size = -1;
bool q_isempty()
{
return size < 0;
}
void q_enqueue(struct queueNode value)
{
if(size<MAXQSIZE)
{
if(size<0)
{
queue[0] = value;
front = rear = 0;
size = 1;
}
else if(rear == MAXQSIZE-1)
{
queue[0] = value;
rear = 0;
size++;
}
else
{
queue[rear+1] = value;
rear++;
size++;
}
}
else
{
printf("Queue is full\n");
}
}
int q_dequeue()
{
if(size<0)
{
printf("Queue is empty\n");
}
else
{
size--;
front++;
}
}
struct queueNode q_front()
{
return queue[front];
}
////FUNCTION WE NEED TO IMPLEMENT...
int sp_algo(int A[GRIDSIZE][GRIDSIZE], struct Point start, struct Point end){
int visited[GRIDSIZE][GRIDSIZE];
for (int i=0; i<GRIDSIZE; ++i){
for(int j=0; j<GRIDSIZE; ++j){
visited[i][j] = -1;
}
}
//all 4 directions we can go to (up,down,left,right)
int row_num[] = {-1, 0, 0, 1};
int col_num[] = {0, -1, 1, 0};
struct queueNode n1;
struct queueNode tmp;
n1.dist = 0;
n1.pt = start;
q_enqueue(n1);
while(q_isempty() == false){
tmp = q_front();
q_dequeue();
if(tmp.pt.x == end.x && tmp.pt.y == end.y){ //we found it!!!
return tmp.dist;
}
///else, search the neighbors!
for(int i=0; i<4; ++i){
int new_row = tmp.pt.x + row_num[i];
int new_col = tmp.pt.y + col_num[i];
if (isValid(new_row, new_col) == true && visited[new_row][new_col] == -1 && A[new_row][new_col] == '.'){
struct queueNode adjCell;
struct Point new_point;
new_point.x = new_row;
new_point.y = new_col;
adjCell.dist = tmp.dist+1;
adjCell.pt = new_point;
visited[new_row][new_col] = 1;
q_enqueue(adjCell);
}
}
}
}
int main() {
int A[7][7] =
{
{ '.', '.', '#', '.', '.', '#', '#'},
{ '.', '.', '#', '.', '.', '.', '.'},
{ '.', '.', '#', '.', '#', '.', '.'},
{ '.', '.', '#', '.', '#', '.', '#'},
{ '#', '.', '#', '.', '#', '.', '.'},
{ '.', '.', '#', '.', '.', '#', '.'},
{ '#', '.', '.', '.', '.', '.', '.'},
};
struct Point start = {0, 0};
struct Point end = {2, 6};
int spDist = sp_algo(A, start, end);
printf("It takes a total of %d steps to reach the destination!\n", spDist);
}
Upvotes: 0
Views: 58
Reputation: 853
struct queueNode adjCell
and struct Point new_point
are being initialized twice, but not in the same scope.
Eg.
{
int a = 5;
printf("%d\n", a); //The scope of a is limited to the {} braces,
} //meaning after the closing brace, a no longer exists
//a doesn't exist here
int a = 2 //This can even be a different data type
printf("%d\n", a);
And it prefers local variables(ones whose scope is limited to the current piece of code) over global ones. Eg.
int a = 5;
{
int a = 3;
printf("%d\n", a); //This prints 3
}
Same with the if loops, it behaves the same like:
{
struct Point new_point;
//Whatever code
}
{
struct Point new_point;
//Whatever code
}
{
struct Point new_point;
//Whatever code
}
//On and on for how many loops
NOTE: I'm not saying this is how loops work, I am saying it behaves like this
...Continues however many times the loop continues. Basically, after one iteration of a loop, it enters a new scope where the previous variables don't exist.
This is what allows you to declare variables inside loops.
for (int i = 0; i < 5; i++) {
int a; //Even though this code executed 5 times, this doesn't cause problems.
}
Most of my explanation is in the comments, so please read those.
Upvotes: 1