ebook39-5

5 3 last-in-first-out, LIFO 3-1 L i n e a r L i s t 3-8 C h a i n 3 3. 8. 3 C + + 5.1 [ ] s t a c k t o p b o t t o m 5-1a 5-1a E D 5-1b 5-1b E E 5-1a 5-1b 5-1c E t o p D t o p D C C B B B t o p A b o t t o m A b o t t o m A b o t t o m a ) b ) c ) 5-1

162 A D T ADT 5-1 ADT5-1 S t a c k{ C re a t e( ) I s E m p t y( ) t r u e f a l s e I s F u l l( ) t r u e f a l s e To p( ) A d d(x) x D e l e t e(x) x 5.2 C + + B A B A B A B A B A B A class B: public A B A C A C class B: public A, private C A A B B A A B A B B A A X B F B A X. F X F A B X F F B X.. F () A B

5 1 6 3 v i r t u a l 12 5.3 3. 3 e l e m e n t [ l e n g t h - 1 ] e l e m e n t [ 0 5-1 S t a c k 3-1 L i n e a r L i s t L i n e a r L i s t S t a c k L i n e a r L i s t S t a c k 5-1 template<class T> class Stack :: private LinearList <T>{ // LIFO ; p u b l i c : Stack(int MaxStackSize = 10) L i n e a r L i s t < T > ( M a x S t a c k S i z e ) { bool IsEmpty() const {return LinearList<T>::IsEmpty(); bool IsFull() const {return (Length() == GetMaxSize()); T Top() const {if (IsEmpty()) throw OutOfBounds(); T x; Find(Length(), x); return x; Stack<T>& Add(const T& x) {Insert(Length(), x); return *this; Stack<T>& Delete(T& x) { L i n e a r L i s t < T > : : D e l e t e (Length(), x); return *this; S t a c k M a x S t a c k S i z e S t a c k S t a c k L i n e a r L i s t I s E m p t y () :: I s F u l l S t a c k L i n e a r L i s t L i n e a r L i s t < T > :: M a x S i z e M a x S i z L i n e a r L i s t L i n e a r L i s M a x S i z e S t a c k L i n e a r L i s t G e t M a x S i z e () p r o t e c t e d : int GetMaxSize() const {return MaxSize; S t a c k L i n e a r L i s t G e t M a x S i z e L i n e a r L i s t I s F u l l 5-1 S t a c k < T > :: I s F u l l L i n e a r L i s t < T > :: L e n g t h () S t a c k

164 L e n g t h () To p O u t O f B o u n d s F i n d A d d x x D e l e t e x A d d D e l e t e A d d D e l e t e I n s e r t L i n e a r L i s t : : D e l e t e X S t a c k F S t a c k X X. F L i n e a r L i s t L e n g t h X. F L i n e a r L i s t S t a c k 5.3.1 Stack T ( 1 ) O ( M a x S t a c k S i z e ) ( 1 ) L i n e a r L i s t S t a c k L i n e a r L i s t l e n g t h () I n s e r t () I n s e r t f o r 0 S t a c k S t a c k L i n e a r L i s t T < < = = < < L i n e a r L i s t : : S e a r c h 5.3.2 S t a c k 5-2 S t a c k s t a c k t o p M a x To p + 1 5-2 S t a c k template<class T> class Stack{ // LIFO p u b l i c : Stack(int MaxStackSize = 10); ~Stack () {delete [] stack; bool IsEmpty() const {return top == -1; bool IsFull() const {return top == MaxTo p ; T Top() const; Stack<T>& Add(const T& x); Stack<T>& Delete(T& x); p r i v a t e : int top; // int MaxTop; //

5 1 6 5 ; T *stack; template<class T> // Stack<T>::Stack(int MaxStackSize) {// Stack M a x Top = MaxStackSize - 1; stack = new T[MaxStackSize]; top = -1; template<class T> T Stack<T>::Top() const {// if (IsEmpty()) throw OutOfBounds(); else return stack[top]; template<class T> Stack<T>& Stack<T>::Add(const T& x) {// x if (IsFull()) throw NoMem(); stack[++top] = x; return *this; template<class T> Stack<T>& Stack<T>::Delete(T& x) {// x if (IsEmpty()) throw OutOfBounds(); x = stack[top--]; return *this; f o r 100 000 5-1 5-2 50 % 1. A D T 1) 2) 3) 2. A D T 1) 2) 3. M a x S t a c k S i z e

166 M a x To p = 0 A d d M a x To p 2 * M a x To p + 1 M a x To p + 1 / 4 1) S t a c k M a x To p = 0 1 t o p 2) n f (n) cf c 5.4 3. 3. 4 M a x S i z e - 1 5-2 A d d ( 1 ) O ( A r r a y S i z e ) D e l e t e ( 1 ) 1 2 5-2 ( 1 ) I n s e r t ( n, x ) D e l e t e ( n, x ) n ( n ) I n s e r t ( 0, x ) D e l e t e ( 1, x ) ( 1 ) 5-3 C h a i n 5-3 C h a i n template<class T> class LinkedStack : private Chain<T> { p u b l i c :

5 1 6 7 ; bool IsEmpty() const {return Chain<T>::IsEmpty(); bool IsFull() const; T Top() const {if (IsEmpty()) throw OutOfBounds(); T x; Find(1, x); return x; LinkedStack<T>& Add(const T& x) {Insert(0, x); return *this; LinkedStack<T>& Delete(T& x) {Chain<T>::Delete(1, x); return *this; template<class T> bool LinkedStack<T>::IsFu11() const {//? try {ChainNode<T> *p = new ChainNode<T>; delete p; return false; catch (NoMem) {return true; I s F u l l N o d e 5-1 5-4 10 000 f o r 5-3 5-4 2 5 % 5-4 template <class T> class Node{ friend LinkedStack<T>; p r i v a t e : T data; Node<T> *link; ; template<class T> class LinkedStack { p u b l i c : LinkedStack () {top = 0; ~ L i n k e d S t a c k (); bool IsEmpty() const {return top==0; bool IsFull() const; T Top() const; LinkedStack<T>& Add(const T& x); LinkedStack<T>& Delete(T& x); p r i v a t e : Node<T> *top; // : template<class T> L i n k e d S t a c k < T > :: ~ L i n k e d S t a c k ()

168 {// Node<T> *next; while (top) { next = top->link; delete top; top = next; template<class T> bool LinkedStack<T>::IsFu11() const {//? try {Node<T> *p = new Node<T>; delete p; return false; catch (NoMem) {return true; template<class T> T LinkedStack<T>::Top() const {// if (IsEmpty()) throw OutOfBounds(); return top->data; template<class T> LinkedStack<T>& LinkedStack<T>::Add(const T& x) {// x Node<T> *p = new Node<T>; p->data = x; p->link = top; top = p; return *this; template<class T> LinkedStack<T>& LinkedStack<T>::Delete(T& x) {// x if (IsEmpty()) throw OutOfBounds(); x = top->data; Node<T> *p = top; top = top->link; delete p; return *this; 4. 1) 100 000 5-1 5-2 5-3 5-4 3 2) 3 100 000 5. L i n k e d S t a c k

5 1 6 9 1) 2) 3) 6. L i n k e d S t a c k 1) 2) 5.5 5.5.1 ( a *( b + c ) + d ) 1 4 8 11 1 11 4 8 ( a + b ))( 6 7 C + + C + + { 5-5 C + + 5-3 / 5-5 (n) n 5-5 #include <iostream.h> #include <string.h> #include <stdio.h> #include "stack.h" const int MaxLength = 100; // void PrintMatchedPairs(char *expr) {// Stack<int> s(maxle n g t h ) ; int j, length = strlen(expr); // expr ( ) for (int i = 1; I<=length; i++) { if (expr[i - 1] ==' ( ' ) s.add(i); else if (expr[i - 1] ==' ) ' ) t r y { s. D e l e t e ( j ) ; cout << j <<' ' << i << endl; catch (OutOfBounds) { cout << "No match for right parenthesis" << " at " << i << endl; // ( while(!s.isempty()) {

170 s. D e l e t e ( j ); cout << "No match for left parenthesis at " <<j< endl; void main(void) { char expr[maxlength]; cout << "Type an expression of length at most " << MaxLength << endl; c i n. g e t l i n e ( e x p r, MaxLength); cout <<"The pairs of matching parentheses in" << endl; puts (expr); cout <<"are" << endl; P r i n t M a t c n e d P a i r s ( e x p r ); Type an expression of length at most 100 ( d + ( a + b )* c *( d + e )- f ))(() The pairs of matching parentheses in the expression ( d + ( a + b )* c *( d + e )- f ))(() a r e 4 8 12 16 1 19 No match for right parenthesis at 20 22 23 No match for left parenthesis at 21 5-3 5.5.2 Towers of Hanoi 1 64 5-2 3 1 2 3 n 3 1 2 n= 2, 3 4 2 n- 1 3 2 n- 1 2 2 1 2 3 5-6 C + + To w e r s O f H a n o i ( n, 1, 2, 3 ) 5-6

5 1 7 1 1 2 3 5-4 5-6 void TowersOfHanoi(int n, int x, int y, int z) {// n x y z if (n > 0) { TowersOfHanoi(n-1, x,z,y); cout << "Move top disk from tower " << x <<" to top of tower " << y << endl; TowersOfHanoi(n-l, z, y, x); 5-6 5-6 moves (n) 2 2-20 m o v es (n) = 2 n - 1 2 n - 1 n= 64 To w e r s O f H a n o i ( 2 n ) 5-6 1 2 L I F O n n 1 2 n 3 n- 1 3n- 1 n n n 3 0 n

172 5-7 To w e r s O f H a n o i ( n ) H a n o i :: To w e r s O f H a n o i 5-6 S [ 1 : 3 ] 3 1 n i n t N o M e m H a n o i :: To w e r s O f H a n o i H a n o i :: To w e r s O f H a n o i S h o w S t a t e 5-7 class Hanoi{ ; friend void To w e r s O f H a n o i ( i n t ) ; p u b l i c : void TowersOfHanoi(int n, int x, int y, int z); p r i v a t e : Stack<int> *S[4]; void Hanoi::TowersOfHanoi(int n, int x, int y, int z) {// n x y z int d; // if (n > 0) { TowersOfHanoi(n-l, x, z, y); S[x]->Delete(d); // x S[y]->Add(d); // y S h o w S t a t e ( ) ; TowersOfHanoi(n-l, z, y, x); void TowersOfHanoi(int n) {// Hanoi::towersOfHanoi Hanoi X X.S[1] = new Stack<int> (n); X.S[2] = new Stack<int> (n); X.S[3] = new Stack<int> (n); for (int d = n; d > 0; d--) // X.S[1]->Add(d); // d 1 // 1 n 3 2 X. TowersOfHanoi(n, 1, 2, 3); 5.5.3 n 1 ~n 1 1 n

5 1 7 3 k 5-5a k= 3 H1 H2 H3 n 1 n 5-5a n= 9 5 8 1 7 4 2 9 6 3 5-5b a) b) 5-5 a) b) L I F O 5-5 a 3 1 2 3 3 H1 6 6 H1 3 6 3 6 H2 9 H3 H1 H2 5-6a a) b) 5-6 2 2 H1 H3 7 8 2 H2 4 H3 5 7 8 u

174 v v > u v assignment rule 4 2 6 9 4 H2 7 H3 5-6b 1 H1 2 H1 3 H2 4 8 H1 5 H2 6 H3 7 H1 8 H3 9 5-5a 1, n, n-1,..., 2 n- 1 k k n - 1 R a i l r o a d 5-8 n k p [ 1 : n ] R a i l r o a d f a l s e t r u e N o M e m R a i l r o a d H H [ i ] i 1 i k N o w O u t m i n H m i n S m i n f o r i p [ i ] p [ i ] = N o w O u t N o w O u t 1 w h i l e p [ i ] p [ i ] 5-8 bool Railroad(int p[], int n, int k) {// k p [ 1 : n ] // t r u e false // NoMem / / LinkedStack<int> *H; H = new LinkedStack<int> [k + 1]; int NowOut = 1; // int minh = n+l; // int mins; //minh / / for (int i = 1; i <= n; i++) if (p[i] == NowOut) {// t cout << "Move car " << p[i] << " from input to output" << endl; N o w O u t + + ; / / while (minh == NowOut) { Output(minH, mins, H, k, n);

5 1 7 5 N o w O u t + + ; else {// p[i] if (!Hold(p[i], minh, mins, H, k, n)) return false; return true; 5-9 5-10 R a i l r o a d O u t p u t H o l d O u t p u t m i n S m i n H H o l d c m i n S m i n H 5-9 5-8 Output void Output(int& minh, int& mins, LinkedStack<int> H[ ], int k, int n) {// m i n S m i n H int c; // // m i n S minh H [ m i n S ]. D e l e t e ( c ) ; cout << "Move car " << minh << " from holding track " << mins << " to output" << endl; // m i n H m i n S minh = n + 2; for (int i = 1; i <= k; i++) if (!H[i].IsEmpty() && (c = H[i].Top()) < minh) { minh = c; mins = i; 5-10 5-8 H o l d bool Hold(int c, int& minh, int &mins, LinkedStack<int> H[], int k, int n) (// c // false // N o M e m // true // c // int BestTrack = 0, // B e s t Top = n + 1, // x;// / / for (int i = 1; i <= k; i++) if (!H[i].IsEmpty()) {// i x = H[i].To p ( ) ; if (c < x && x < BestTop) { // i B e s t Top = x; B e s t Track = i;

176 else // i if (!BestTrack) BestTrack = i; if (!BestTrack) return false; // // c H [ B e s t Tr a c k ]. A d d ( c ) ; cout << "Move car " << c << " from input " "to holding track " << BestTrack << endl; // minh mins if (c < minh) {minh = c; mins = BestTr a c k ; return true; 5-8 O u t p u t H o l d ( k ) R a i l r o a d w h i l e n - 1 e l s e n - 1 O u t p u t H o l d O ( k n ) R a i l r o a d f o r ( n ) 5-8 O ( k n ) AV L 11 O ( n l o g k ) O u t p u t H o l d O ( l o g k ) k 5.5.4 5-7a ( 1, 4,) ( 2, 3 ) ( 5, 6 ) ( 7, 8 ) 5-7b (1,4) (2,3) 5-7c routable switch box a) b) c) 5-7 5-7b 5-7c x y x y

5 1 7 7 ( 1, 4 ) 2 3 5 ~ 8 1 5-7a 1, 2,..., 8 1 4 1 4 4 1 4 2 3 2 3 2 2 4 1 1 5-7a ( 1, 5 ) ( 2, 3 ) ( 4, 7 ) ( 6, 8 ) 1 2 3 2 4 4 5 1 5 4 5-11 C + + 5-7c n et= [ 1, 2, 2, 1, 3, 3, 4, 4 ] 5-11 ( n ) n 5-11 bool CheckBox(int net[ ], int n) {// Stack<int> *s = new Stack<int> (n); / / for (int i = 0; i < n; i++) { // n e t [ i ] if (!s->isempty() ) { if (net[i] == net[s->top()] ) { // net[i] int x; s->delete(x);) else s->add(i); else s->add(i); //? if (s->isempty()) {

178 delete s; cout << "Switch box is routable" << endl; return true; delete s; cout << "Switch box is not routable" << endl; return false; 5.5.5 3. 8. 3 n r r n 5-12 C + + 5-12a n, r r i c h a i n [ i ] j (i, j) (j, i) 5-12b o u t i o u t [ i ] = t r u e s t a c k o u t m c h a i n [ m ] m ( m, p ) p p c h a i n [ m ] m p d o ( 1 ) 5-12a ( n + r ) 5-12 b ( n ) ( 1 ) 5-12a n 2 r 5-12b 2 r ( r ) 5-12 ( n + r ) 5-12a ( ) void main(void) {// int n, r; // n r cout << "Enter number of elements" << endl; cin >> n; if (n < 2) {cerr << "Too few elements" << endl; exit(l); cout << "Enter number of relations" << endl; cin >> r; if (r < 1) {cerr << "Too few relations" << endl; exit(l); // n

5 1 7 9 Chain<int> *chain; try {chain = new Chain<int> [n+1]; catch (NoMem) {cerr << "Out of memory" << endl; exit(1); // r for (int i = 1; i <= r; i++) { cout << "Enter next relation/pair" << endl; int a, b; cin >> a >> b; c h a i n [ a ]. I n s e r t ( 0, b ) ; c h a i n [ b ]. I n s e r t ( 0, a ) ; 5-12b ( ) / / LinkedStack<int> stack; bool *out; try {out = new bool [n+1]; catch (NoMem) {cerr << "Out of memory" << endl; exit(l); for (int i = 1; i <= n; i++) out[i] = false; / / for (int i = 1; i <= n; i++) if (!out[i]) {// cout << "Next class is: " << i << ' ' ; out[i] = true; s t a c k. A d d ( i ) ; / / while (!stack.isempty()) { int *q, j; s t a c k. D e l e t e ( j ) ; // c h a i n [ j ] c ChainIterator<int> c; q = c.initialize(chain[j1); while (q){ if (!out[*q]) { cout << "q << ' '; out[*q] = true; s t a c k. A d d ( * q ) ; q = c.next(); cout << endl; cout << endl << "End of class list" << endl; 5-12 c h a i n o u t 5-12

180 5.5.6 1. m a z e 5-8 5-8 n m ( 1, 1 ) (n,m) n m (i,j) 1 0 5-9 5-8 rat in a maze 5-10 5-9 5-8 5-10 4

5 1 8 1 2. 0 1 5-11 5-11 Please Enter Row 1 Press <Enter> when done

182 3. 5-12 m a i n 5-13 5-12 // // We l c o m e // I n p u t M a z e // F i n d P a t h // O u t p u t P a t h void main(void) { We l c o m e ( ) ; I n p u t M a z e ( ) ; if (FindPath()) OutputPath; else cout << "No path" << endl; 4. 5-13 16 5-14 C + + C + + 5-14

5 1 8 3 bool FindPath() { ; if ( ) return true; else return false; 5-14 FindPath 5-8 ( 1, 1 ) ( 1, 1 ) ( 2, 1 ) ( 2, 1 ( 1, 1 ) ( 2, 1 ) ( 3, 1 ) ( 2, 2 ) ( 3, 1 ) ( 2, 1 ) ( 3, 1 ( 4, 1 ) ( 3, 2 ) ( 4, 1 ( 3, 1 ) ( 4, 1 ) (5,1) (6,1) ( 7, 1 ) ( 8, 1 ) ( 8, 1 ) ( 1, 1 ) ( 8, 1 ) ( 8, 1 ( 7, 1 ) ( 7, 1 ) ( 7, 1 ( 6, 1 ) ( 3, 1 ) 3, 2 5-14 0 1 i n t m a z e 0 1 16 i n t 16 i, j m a z e [i, j] 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 1 1 0 1 0 1 0 1 0 1 1 0 1 m n 1 0 1 0 1 0 1 0 1 0 0 1 m a z e 0 m + 1 0 1 0 1 1 1 0 1 0 1 0 1 1 m + 1 5-15 1 0 1 0 0 0 1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 m a z e 5-15 5-8

184 bool FindPath() {// ( 1, 1 ) ( m, m ) ; P o s i t i o n r o w c o l // P o s i t i o n Position here; here.row = 1; here.col = 1; Stack<Position> path(maxpathlength); M a x P a t h L e n g t h // while ( ) do { ; if ( ) { m m m 2 here p a t h ; 5-16 a // here = neighbor; MaxPathLength= m 2-1maze[here.row] [here.col] = 1; else { 2 m // if ( p a t h ) return false; a) b) 5-14 5-16 a) b) 5-17 C + + return true; h e r e maze [1] [1] = 1; // p a t h here; 5-17 5-14

5 1 8 5 5-18 0 1 2 3 5-18 o ff s e t [ i ]. r o w o ff s e t [ i ]. c o l i r o w c o l ( 3, 4 ) 3 + o ff s e t [ 0 ]. r o w = 3 4 + o ff s e t [ 0 ]. c o l = 5 5-17 5-13 C + + 5-13 m a z e m ( ) p a t h int **maze, m; Stack<Position> *path; F i n d P a t h P o s i t i o n m a z e m I n p u t M a z e o ff s e t [ m o v e ]. r o w o ff s e t [ m o v ]. c o l 0 0 1 1 1 0 2 0-1 3-1 0 5-18 5-13 bool FindPath {// ( 1, 1 ) ( m, m ) // true f a l s e // N o M e m path = new Stack<Position>(m * m - 1); / / Position off s e t [ 4 ] ; o ffset[0].row = 0; offset[0].col = 1; // o ffset[l].row = 1; offset[l].col = 0; // o ffset[2].row = 0; offset[2].col = -1; // o ffset[3].row = -1; offset[3].col = 0; // / / for (int i = 0; i <= m+l; i++) { maze [0] [i] = maze[m+l] [i] = 1; // maze [i] [0] = maze[i] [m+l] = 1; // Position here; here.row = 1; here.col = 1; maze [i] [i] = 1; // int option = 0; int LastOption = 3; / / while (here.row!= m here.col!= m) {// / /

186 int r, c; while (option <= LastOption) { r = here.row + off s e t [ o p t i o n ]. r o w ; c = here.col + off s e t [ o p t i o n ]. c o l ; if (maze[r][c] == 0) break; option++; // //? if (option <= LastOption) {// maze[r] [c] p a t h - > A d d ( h e r e ) ; here.row = r; here.col = c; / / maze [r] [c] = 1; option = 0; else {// if (path->isempty()) return false; Position next; p a t h - > D e l e t e ( n e x t ) ; if (next.row == here,row) option = 2 + next.col - here.col; else option = 3 + next.row - here.row; here = next; return true;// F i n d P a t h * p a t h w h i l e h e r e p a t h ( n e x t ) n e x t h e r e h e r e n e x t if ( next.row == here.row) Option= 2 + next.col - here.col; else option = 3 + next.row - here.row; ( 1 ) O (u n b l o c k e d) u n b l o c k e d O ( u n b l o c k e d ) =O ( m 2 ) 7. 5-6

5 1 8 7 8. 1 ~n 1 5-6 cout 9. 5-7 ShowState 10. 11. k k *12. 1) k 5-8 2) n+ ( ) 5-8 k 5-8 13. i s i 1 i k 14. C + + C h e c k B o x C h e c k B o x (n) n 15. C h a i n L i n k e d S t a c k C h a i n :: D e l e t e L i n k e d S t a c k :: A d d c h a i n [ j ] d a t a x o u t [ x ] = 0 o u t n e w d e l e t e 1) C h a i n L i n k e d S t a c k d e l e t e o u t n e w 2) 5-12 16. C + + 1) We l c o m e 2) I n p u t M a z e m a z 3) O u t p u t P a t h 17. 5-8 F i n d P a t h 1

188 18. F i n d P a t h 19. p a t h m 2-1 20. p a t h 1 5-13 21. 5-13 p a t h 22. 5-13 S t a c k S t a c k 5-13 t o p p a t h 1 t o p 23. F i n d P a t h 5-13 5.6 1) C.Hsu. General River Routing Algorithm. ACM/IEEE Design Automation Confere n c e, 578~583, 1983 2) R.Pinter. River-routing:Methodology and Analysis. T h i rd Caltech Conference on VLSI, 1 9 8 3. 3