"Stack" is a basic data structure, its principle is: advanced afterwards. This procedure is written when the second grade of our university. At that time, the operation of the data structure was required, but this is indeed a classic program. Since there is no learning-oriented technology at the time, Struct is implemented. The program is in TC2,0 (need to remove // annotation) and VC 6.0 below
#include
#include
#define sis 100
#define n 10
Struct Sit
{
Int seatx;
INT seaty;
}; // Currently accessible coordinates
Struct Finds
{
Int Ord;
Struct Sit * Seat;
Int Di;
}; // Di is the direction of the next looking
Struct stack
{
Struct Finds * Base;
Struct Finds * TOP;
Int size;
}
Void InitStack (Struct Stack * S)
{
Struct Finds * link, * end;
S-> Base = S-> TOP = link = (struct finds *) Malloc (SIS * SIZEOF (Struct Finds));
END = LINK SIS-1;
For (; link <= end; link )
Link-> seat = (struct Sit *) Malloc (Struct Sit);
S-> SIZE = SIS;
} // Stack initialization
Void Push (Struct Stack * S, Struct Finds * Find)
{
Struct Finds * link, * end;
IF (S-> TOP-S-> Base> = S-> size)
{
S-> Base = (Struct Finds *) Realloc (S-> Base, (S-> Size SIS) * SizeOf (Struct Finds));
LINK = S-> Base S-> size;
S-> TOP = S-> Size S-> Base;
S-> Size = SIS;
End = S-> Base S-> size;
For (; link <= end; link )
Link-> seat = (struct Sit *) Malloc (Struct Sit);
}
S-> TOP-> ORD = FIND-> ORD;
S-> TOP-> seat-> seatx = find-> seat-> seatx;
S-> TOP-> seat-> seaty = find-> seat-> seaty;
S-> TOP-> DI = FIND-> DI;
S-> TOP ;
}
Void Pop (Struct Stack * S, Struct Finds * Find)
{
S-> TOP -;
Find-> ORD = S-> TOP-> ORD;
Find-> seat-> seatx = S-> TOP-> seat-> seatx;
Find-> seat-> seaty = S-> TOP-> seat-> seaty;
Find-> di = S-> TOP-> DI;
}
Void Footprint (int A [n] [n], struct SIT * SEAT)
{
INT I, J;
I = seat-> seatx;
J = seat-> seaty;
a [i] [j] = - 1;
}
Void nextpos (Struct Sit * Find, Struct Sit * SEAT, INT DI)
{
INT I, J;
Switch (di)
{casse 1: i = seat-> seatx; j = seat-> seaty 1; break;
Case 2: i = seat-> seatx 1; j = seat-> seaty;
Case 3: i = seat-> seatx; j = seat-> seaty-1; break;
Case 4: i = seat-> seatx-1; j = seat-> seaty; break;
}
Find-> seatx = i;
Find-> seaty = j;
}
INT Pass (Struct Sit * Curpos, Int A [N] [N])
{
INT I, J;
i = curpos-> seatx;
J = Curpos-> seaty;
IF (a [i] [j] == 0) Return 1;
Else Return 0;
}
Print (Struct Stack * s) {DO {Printf ("(% D,% d)", S-> Base-> seat-> seatx, s-> base-> seat-> seaty); S-> Base ; } while (S-> Top! = S-> Base);} void main () {struct stack * s; struct finds * find, * e; struct sit * start, * end, * curpos; int curstep = 1, A [N], I, J, N, M, Pa; CHAR C [N] [N]; S = (Struct Stack *) Malloc (Struct Stack); Find = (Struct Finds *) Malloc (Struct Finds)); E = (Struct Finds *) Malloc (Struct Finds)); START = (Struct Sit *) Malloc (Struct Sit); End = (Struct Sit *) Malloc SIZEOF (STRUCT SIT); curpos = (Struct Sit *) Malloc (Struct Sit); INITSTACK (S); PUTS ("Please read the instructions carefully before use); while (1) {printf (" Please enter the length and width (n, m) "of the labyrinth); PA = Scanf ("% D,% D ", & n, & m); if (pa! = 2 || N> 81 || m> 81 || N <= 0 || m <= 0) PUTS ("Enter data error, re-enter"); else break;
Printf ("Please enter your maze (0 representative path, continuous input) / N"); for (i = 0; i
Scanf ("% s", c [i]);
For (i = 0; i
For (j = 0; J
A [i] [j] = c [i] [j] -48;
While (1)
{
Printf ("Enter the location of the maze (n, m)");
Scanf ("% D,% D", & curpos-> seatx, & curpos-> seaty); if (curpos-> seatx> 81 || Curpos-> seaty> 81 || Curpos-> seatx <= 0 || Curpos > seaty <= 0 || Curpos-> seatx> = N || Curpos-> seatx> = m || Curpos-> seaty> = m || curpos-> seaty> = n) PUTS ("Enter data error, please re-enter");
Else Break;
WHILE (1) {printf ("Going out of the labyrinth position (n, m)"); scanf ("% d,% d", & end-> seatx, & end-> seaty); if (end-> seatx> 81 || end-> seaty> 81 || End-> seatx <= 0 || end-> seaty <= 0 || end-> seatx> = n || End-> seatx> = m || End-> seaty > = N || End-> seaty> = m) PUTS ("Enter data error, re-enter"); else break;
Do {IF (Pass (Curpos, A)) {FootPrint (a, curpos); E-> ORD = Curstep; E-> seat = curpos; E-> Di = 1; Push (S, E); IF (Curpos -> seatx == end-> seatx && curpos-> seaty == end-> seaty) Break; NextPos (CURPOS, E-> SEAT, 1); Curstep ;} else {IF (e-> di <4) {POP ( S, E); E-> DI , Push (S, E); NextPOS (CURPOS, E-> SEAT, ELSE IF (E-> Di == 4) {POP (S, E ); POP (s, e); push (s, e); E-> Di ; if (e-> di> 4) POP (s, e); Nextpos (CURPOS, E-> SEAT, E-> Di );}}} While (1); PUTS ("output path is"); Print (s); PUTS ("/ n");}
