PRACTICUM 21

Oefening met stack [zie HC22.08ff]

de elementen op de stack zijn karakters
de stack bestaat uit een array van karakters en een veld waarvan de waarde
gelijk is aan de index van de eerste vrije positie in het array
De declaratie van stack: 
 
	#define STACK_CAPACITY (24)
	typedef char stackElt;
	typedef struct stack {
		stackElt* elts;
		int  size;
	} stack;

de capaciteit van de stack wordt gegeven door een constante
de prototypes van de stack functies zijn voorgeschreven en
het testprogramma is ook al voor je klaar gemaakt stack PR21
reproduceer de uitvoer vermeld aan het eind van dit programma

=> HC22.08


Oefening met queue [zie HC22.13ff]

de elementen in de queue zijn karakters
de queue bestaat uit twee stacks met de namen in en out
stack in wordt exclusief gebruikt voor de insert operatie
stack out wordt exclusief gebruikt voor de serve operatie
op het moment dat de serve operatie wordt aangeroepen hevel je
de elementen van in over naar out en voert dan de operatie uit!
Ja! daar moet je even over nadenken!!

De declaratie van queue: 
 
	typedef stackElt queueElt;
	typedef struct queue {
		stack  in, // stack to enqueue 
	              out; // stack to dequeue
	} queue;
enkele vragen waarop je zelf een antwoord moet bedenken:
- hoe karakteriseer je een lege queue?
- hoe karakteriseer je een volle queue?
- hoe schrijf je de elementen van de queue naar het scherm?
- wat zou de betekenis zijn van de notatie [[..][..]] die in de
- uitvoer door mij wordt gebruikt?
de prototypes van de queue functies zijn voorgeschreven en
het testprogramma is ook al voor je klaar gemaakt queue PR21
reproduceer de uitvoer vermeld aan het eind van dit programma

=> HC22.13 


UNDERSTANDING STACKS AND QUEUES: PAINTING A POLYGON

	polygon poly = initPolygon();   // define a polygon
	setRedRim(poly);                // paint the rim in red
	stack s = createStack();        // a stack of pixels p
	pixel p = getRandom(poly);      // get p random from interior
	s = push(p, s);                 // add p to stack s
	while (!isEmptyStack(s)) {
		setRedPixel(p = top(s));    // paint p on top of s 
		s = pop(s);                 // remove this p from s
		for all neigbours n of p    // north east, south and west
			if (isWhite(n))         // white neighbours 
				s = push(n, s);     // are pushed onto s
	}

										
	Consider a square (very simple polygon).

	1 Let the random pixel be the center of the square.
	Describe the order in which the interior pixels are painted.

	2 Let the random pixel be the most top-right interior pixel
	Describe the order in which the interior pixels are painted.
 
	
	polygon poly = initPolygon();   // define a polygon
	setRedRim(poly);                // paint the rim in red
	queue q = createQueue();        // a queue of pixel locations
	pixel p = getRandom(poly);      // get p random from interior
	q = add(p, q);                  // add p to queue q
	while (!isEmptyQueue(q)) {
		setRed(p = front(q));       // paint p on front of q
		q = serve(q);               // remove this p from q
		for all neigbours n of p    // north east, south and west
			if isWhite(n)           // white neighbours 
				q = add(n, q);      // are added to q
	}

										
	Consider a square (very simple polygon).

	1 Let the random pixel be the center of the square.
	Describe the order in which the interior pixels are painted.

	3 Let the random pixel be the most bottom-left interior pixel
	describe the order in which the interior pixels are painted.

HOORCOLLEGES

PRACTICA

WWW

HC• PR• WWW
home