ebook39-6

Size: px

Start display at page:

Download "ebook39-6"

涯武
5 years ago
Views:

1 6 first-in-first-out, FIFO L i n e a r L i s t 3-1 C h a i n F I F O L I F O [ ] q u e n e ( r e a r ) ( f r o n t 6-1a A 6-1b 6-1b D C D 6-1c a) b) c) 6-1 F I F O L I F ADT 6-1

2 190 ADT6-1 Queue { f r o n t r e a r C reate (): IsEmpty (): t r u e f a l s IsFull (): t r u e f a l s First (): Last ( ) : Add (x): x Delete (x): x; location (i ) = i q u e u e [ M a x S i z e ] q u e u e [ 0 ] q u e u e [ 1 ] f r o n t 0 r e a r r e a r + 1 r e a r = a) b) c) r e a r 1 q u e u e [ r e a r ] O ( 1 ) 1 n ( n ) n 6-1 ( 1 ) ( n ) 6-2 ( 1 ) location (i) = location (1) + i location ( 1 ) f r o n t =location ( 1 ) r e a r =location ( )

3 r e a r < f r o n t 6-3b f r o n t r e a r < M a x S i z e - 1 r e a r = M a x S i z e - 1 f r o n t > ( 1 ) 6-2 ( n ) 6-2 a) b) c) a) b) 6-3 ( 1 ) location (i ) = (location (1) + i -1) % M a x S i z e f r o n t r e a r 6-5 a 6-5b 6-5b 6-5c a) b) a) b) c) 6-5 a) b) c)

4 192 front=rear f r o n t = r e a r = 0 6-5b 6-6 f r o n t = r e a r 6-6 M a x S i z e M a x S i z e C + + Q u e u e 5-1 LinearList 3-1 Queue Queue 6-3 L i n e a r L i s t Queue Queue 1 12 Q u e u e < i n t > Q ( 1 2 ) ; T ( 1 ) T O ( M a x S t a c k S i z e ) ( 1 template<class T> class Queue { // FIFO ; p u b l i c : Queue(int MaxQueueSize = 10); ~Queue() {delete [] queue; bool IsEmpty() const {return front == rear; bool IsFull() const {return ( ((rear + 1) % MaxSize == front)? 1 : 0); T First() const; // T Last() const; // Queue<T>& Add(const T& x); Queue<T>& Delete(T& x); p r i v a t e : 6-1 Q u e u e int front; // int rear; // int MaxSize; // T *queue; // template<class T> 6-2 Queue

5 Queue<T>::Queue(int MaxQueueSize) {// M a x Q u e u e S i z e MaxSize = MaxQueueSize + 1; queue = new T[MaxSize]; front = rear = 0; template<class T> T Queue<T>::First() const {// // O u t O f B o u n d s if (IsEmpty()) throw OutOfBounds(); return queue[(front + 1) % MaxSize]; template<class T> T Queue<T>::Last() const {// // O u t O f B o u n d s if (IsEmpty()) throw OutOfBounds(); return queue[rear]; 6-3 Queue template<class T> Queue<T>& Queue<T>::Add(const T& x) {// x // NoMem if (IsFull()) throw NoMem(); rear = (rear + 1) % MaxSize; queue[rear] = x; return *this; template<class T> Queue<T>& Queue<T>::Delete(T& x) {// x // O u t O f B o u n d s if (IsEmpty()) throw OutOfBounds(); front = (front + 1) % MaxSize; x = queue[front]; return *this; 1. A D T 1)

6 194 2) 3) 2. A D T 1) ) C Q u e u e q u e u e L a s t O p A d d D e l e t e f r o n t = r e a r L a s t O p 5. d e q u e 1) C re a t e I s E m p t y I s F u l l L e f t R i g h t A d d L e f t A d d R i g h t D e l e t e L e f t D e l e t e R i g h t 2) 6-3 C + + D e q u e 3) 6.3 f r o n t r e a r f r o n t r e a r 6-7 a r e a r f r o n t 6-7 b f r o n t r e a r f r o n t r e a f r o n t = r e a r = 0 f r o n t = L i n k e d Q u e u e C h a i n L i n k e d Q u e u e L i n k e d Q u e u e N o d e 5-4 a) L i n k e d Q u e u e N o d e L i n k e d Q u e u e b) ( 1 ) 6-7

7 a) b) 6-8 a) 6-7a b) 6-7b a) b) 6-9 a) 6-7a b) 6-7b 6-4 template<class T> class LinkedQueue { // FIFO p u b l i c : LinkedQueue() {front = rear = 0; // ~LinkedQueue(); // bool IsEmpty() const {return ((front)? false : true); bool IsFull() const; T First() const; // T Last() const; // LinkedQueue<T>& Add(const T& x); LinkedQueue<T>& Delete(T& x); p r i v a t e : Node<T> *front; // Node<T> *rear; // ;

8 template<class T> LinkedQueue<T>:: ~ L i n k e d Q u e u e () {// Node<T> *next; while (front) { next = front->link; delete front; front = next; template<class T> bool LinkedQueue<T>::IsFull() const {// Node<T> *p; try {p = new Node<T>; delete p; return false; catch (NoMem) {return true; template<class T> T LinkedQueue<T>::First() const {// // O u t O f B o u n d s if (IsEmpty()) throw OutOfBounds(); return front->data; template<class T> T LinkedQueue<T>::Last() const {// // O u t O f B o u n d s if (IsEmpty()) throw OutOfBounds(); return rear->data; 6-6 template<class T> LinkedQueue<T>& LinkedQueue<T>::Add(const T& x) {// x // n e w NoMem // Node<T> *p = new Node<T>; p->data = x; p->link = 0;

9 // if (front) rear->link = p; // else front = p; // rear = p; return *this; template<class T> LinkedQueue<T>& LinkedQueue<T>::Delete(T& x) {{// x // O u t O f B o u n d s if (IsEmpty()) throw OutOfBounds(); / / x = front->data; // Node<T> *p = front; front = front->link; delete p; return *this; C h a i n A p p e n d C h a i n L i n k e d Q u e u e / F I F O Hk k , 8, 1, 7, 4, 2, 9, 6, 3 k= 3 3

10 H1 6 H H H2 4 H H3 H2 2 H1 3 H H c k O u t p u t H o l d 5-8 R a i l r o a d 1) k 1 2) H LinkedQueue<int> * 3) M i n S M i n Q 4) H o l d ( n ) O ( n k ) AV L 11 O ( n l o g k ) 6-7 void Output(int& minh, int& minq, LinkedQueue<int> H[], int k, int n) {// minh m i n Q. int c; // // minq m i n H H [ m i n Q ]. D e l e t e ( c ) ; cout << "Move car " << minh << " from holding track " << minq << " to output" << endl; // m i n H m i n Q minh = n + 2; for (int i = 1; i <= k; i++) if (!H[i].IsEmpty() && (c = H[i].First()) < minh) { minh = c;

11 minq = i; bool Hold(int c, int& minh, int &minq, LinkedQueue<int> H[], int k) {// c // f a l s e t r u e // c // int BestTrack = 0, // BestLast = 0, // BestTrack x; // // for (int i = 1; i <= k; i++) if (!H[i].IsEmpty()) {// i x = H[i].Last(); if (c > x && x > BestLast) { // i BestLast = x; B e s t Track = i; 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; // m i n H m i n Q if (c < minh) {minh = c; minq = BestTr a c k ; return true; 2. i l a s t [ i ] = 0 l a s t [ i ] i t r a c k [ i ] = 0 t r a c k [ i ] i l a s t [ i ] = 0 1 i k t r a c k [ i ] = 0 1 i n void Output(int NowOut, int Track, int& Last) {// NowOut L a s t

12 200 cout << "Move car " << NowOut << " from holding track " << Track << " to output" << endl; if (NowOut == Last) Last = 0; bool Hold(int c, int last[], int track[], int k) {// c // f a l s e t r u e // c // int BestTrack = 0, // BestLast = 0, // BestTr a c k // for (int i = 1; i <= k; i++) // find best track if (last[i]) {// i if (c > last[i] && last[i] > BestLast) { // i BestLast = last[i]; B e s t Track = i; else // i if (!BestTrack) BestTrack = i; if (!BestTrack) return false; // // c track[c] = BestTr a c k ; l a s t [ B e s t Track] = c; cout << "Move car " << c << " from input " << "to holding track " << BestTrack << endl; return true; bool Railroad(int p[], int n, int k) {// k p [ 1 : n ] // t r u e f a l s e // NoMem // l a s t t r a c k int *last = new int [k + 1]; int *track = new int [n + 1]; for (int i = 1; i <= k; i++) last[i] = 0; // i for (int i = 1; i <= n; i++) track[i] = 0; k--; // k //

13 int NowOut = 1; // for (int i = 1; i <= n; i++) if (p[i] == NowOut) {// cout << "Move car " << p[i] << " from input to output" << endl; N o w O u t + + ; // while (NowOut <= n && track[nowout]) { Output(NowOut, track[nowout], last[nowout]); N o w O u t + + ; else {// p[i] if (!Hold(p[i], last, track, k)) return false; return true; n m 6-11a a b 6-11b a b a) b) 6-11 a) 7 7 b) a b

14 a b a a 1 a a 2 b 6-12a a = ( 3, 2 ) b = ( 4, 6 ) a) b) 6-12 a) b) b b a 6-12a b 9 a b b b a b ( 5, 6 ) 1 a 6-12a ( 5, 6 ) ( 6, 6 ) ( 6, 4 ) ( 5, 4 ) 6-12b C m m 0 1 o ff s e t s bool FindPath(Position start, Position finish, int& PathLen, Position * &path) {// s t a r t f i n i s h // t r u e f a l s e // N o M e m if ((start.row == finish.row) && (start.col == finish.col)) {PathLen = 0; return true; // start = finish //

15 for (int i = 0; i <= m+1; i++) { grid[0][i] = grid[m+1][i] = 1; // grid[i][0] = grid[i][m+1] = 1; // // o ff s e t Position off s e t [ 4 ] ; o ffset[0].row = 0; offset[0].col = 1; // o ffset[1].row = 1; offset[1].col = 0; // o ffset[2].row = 0; offset[2].col = -1; // o ffset[3].row = -1; offset[3].col = 0; // int NumOfNbrs = 4; // Position here, nbr; here.row = start.row; here.col = start.col; grid[start.row][start.col] = 2; // // LinkedQueue<Position> Q; do { // for (int i = 0; i < NumOfNbrs; i++) { n b r.row = here.row + off s e t [ i ]. r o w ; n b r.col = here.col + off s e t [ i ]. c o l ; if (grid[nbr. r o w ][ n b r.col] == 0) { // unlabeled nbr, label it g r i d [ n b r. r o w ][ n b r.col] = grid[here.row][here.col] + 1; if ((nbr.row == finish.row) && (nbr.col == finish.col)) break; // Q.Add(nbr); // if // for // f i n i s h? if ((nbr.row == finish.row) && ( n b r.col == finish.col)) break; // // f i n i s h n b r? if (Q.IsEmpty()) return false; // Q.Delete(here); // while(true); // PathLen = grid[finish.row][finish.col] - 2; path = new Position [PathLen]; // f i n i s h here = finish; for (int j = PathLen-1; j >= 0; j--) { path[j] = here; //

16 204 for (int i = 0; i < NumOfNbrs; i++) { n b r.row = here.row + off s e t [ i ]. r o w ; n b r.col = here.col + off s e t [ i ]. c o l ; if (grid[nbr. r o w ][ n b r.col] == j+2) break; here = nbr; // return true; 6-9 s t a r t f i n i s h 0 o ff s e t a 2 Q s t a r t s t a r 1 s t a r t 2 f i n i s h f i n i s h f i n i s h f i n i s h s t a r t p a t h 1 O (m 2 ) m m P a t h L e n PathLen m m a ( 1, 3 ) ( 2, 3 ) ( 2, 4 2, 3 ( 1, 3 ) ( 2, 3 ) ( 2, 4 ) 6-13a 4 {( 1, 3 ),( 2, 3 ),( 2, 4 ) { ( 3, 5 ),( 4, 4 ),( 4, 5 ),( 5, 5 ) { ( 5, 2 ),( 6, 1 ),( 6, 2 ),( 6, 3 ), ( 7, 1 ),( 7, 2 ),( 7, 3 ) { ( 5, 7 ),( 6, 7 ),( 7, 6 ),( 7, 7 ) 6-13b 0 o ff s e t 2, 3, 1-1 -

17 a) 7 7 b) o ffset for p i x e l [ r ][ c ] = 1 p i x e l [ r ][ c ] 1 i d Label m 2 (m) o ff s e t ( 1 ) p i x e l [ r ][ c ] = = 1 true cnum cnum ( c n u m ) ( ) = ( 1 ) = ( m 2 ) L a b e l ( m 2 ) 6-10 void Label() {// // for (int i = 0; i <= m+1; i++) { pixel[0][i] = pixel[m+1][i] = 0; // pixel[i][0] = pixel[i][m+1] = 0; // // o ff s e t Position off s e t [ 4 ] ; o ffset[0].row = 0; offset[0].col = 1; //

18 206 o ffset[1].row = 1; offset[1].col = 0; // o ffset[2].row = 0; offset[2].col = -1; // o ffset[3].row = -1; offset[3].col = 0; // int NumOfNbrs = 4; // LinkedQueue<Position> Q; int id = 1; // i d Position here, nbr; // for (int r = 1; r <= m; r++) // r for (int c = 1; c <= m; c++) // c if (pixel[r][c] == 1) {// pixel[r][c] = ++id; // i d here.row = r; here.col = c; do {// for (int i = 0; i < NumOfNbrs; i++) { // n b r.row = here.row + off s e t [ i ]. r o w ; n b r.col = here.col + off s e t [ i ]. c o l ; if (pixel[nbr. r o w ][ n b r.col] == 1) { p i x e l [ n b r. r o w ][ n b r.col] = id; Q.Add(nbr); // end of if and for //? if (Q.IsEmpty()) break; Q.Delete(here); while(true); // if f o r m 6-1

19 F I F O F I F O l 0 f f l e v e n t start event 6-2 m=3 n=4 0 M1 M2 M M1 2 M2 M a 1 3 m a c h i n e t i m e 1 M1 2 M2 4 M b M1 M1 2 4 M3 M2 3 I L 0 1 M1 2 M3 M1 3 M3

20 208 a) b) 4 M2 1 M1 2 M3 M2 M M M1 1 1 M2 M M1 2 M1 C 4 4 M1 M3 M1 M M1 M3 2 M1 2 M1 M = = a) b)

21 M3 5 M3 5 M3 M b M1 M C + + N o M e m B a d I n p u t 6-11 c a t c h c a t c h c a t c h void main(void) {// try { InputData(); // StartShop(); // Simulate(); // OutputStats(); // catch (...) { cout << "An exception has occurred" << endl; 3. Ta s k 6-11 m a c h i n e t i m e 6-12 Ta s k 1 m m a c h i n e i n t u n s i g n e d t i m e l o n g Ta s k J o b M o v e To N e x t M a c h i n e J o b Ta s k J o b Ta s k Ta s k m a c h i n e t i m e 4. J o b Ta s k Q J o b L e n g t h 6-12 J o b Ta s k Q

22 210 Ta s k Q A r r i v e Ti m e I D A d d Ta s k p t D e l e t e Ta s k Length 6-12 Ta s k J o b class Task { friend class Job; friend bool MoveTo N e x t M a c h i n e ( J o b *); p r i v a t e : long time; int machine; ; class Job { friend bool MoveTo N e x t M a c h i n e ( J o b *); friend Job* ChangeState(int); friend void Simulate(); friend class Machine; p u b l i c : Job(long id) {ID = id; Length = ArriveTime = 0; void AddTask(int p, long t) { Task x; x.machine = p; x.time = t; Ta s k Q. A d d ( x ); long DeleteTask() { // Task x; Ta s k Q. D e l e t e ( x ); Length += x.time; return x.time; p r i v a t e : L i n k e d Q u e u e < Task> Ta s k Q ; long Length; // long ArriveTime; //

23 ; long ID; // 5. M a c h i n e m*(n-1) m n n n 6-13 Machine J o b Q C h a n g e Ti m e To t a l Wa i t N u m Ta s k s A c t i v e 0 IsEmpty t r u e A d d J o b S e t C h a n g e C h a n g e Ti m e S t a t u s 6-13 M a c h i n e class Machine { friend Job* ChangeState(int); p u b l i c : Machine() {To t a l Wait = NumTasks = 0; Active = 0; bool IsEmpty() {return JobQ.IsEmpty(); void AddJob(Job* x) {JobQ.Add(x); void SetChange(long w) {ChangeTime = w; void Stats(long& tw, long& nt) {tw = To t a l Wa i t ; nt = NumTa s k s ; p r i v a t e : LinkedQueue<Job*> JobQ; // long ChangeTime; // long To t a l Wait; // long NumTasks; // Job *Active; // ;

24 E v e n t L i s t 6-14 E v e n t L i s t F i n i s h Ti m e F i n i s h Ti m e [ p ] p B i g T N u m M a c h i n e s N e x t E v e n t p m ( m ) N e x t E v e n t ( m ) S e t F i n i s h Time ( 1 ) 9 N e x t E v e n t S e t F i n i s h Ti m e O ( l o g m ) T ( T ) NextEvent (T) S e t F i n i s h Ti m e 6-14 N e x t E v e n t S e t F i n i s h Ti m e (T m) O ( T l o g m ) m 6-14 E v e n t L i s t class EventList { p u b l i c : EventList(int m, long BigT); ~EventList(){delete [] FinishTi m e ; void NextEvent(int& p, long& t); long NextEvent(int p) {return FinishTi m e [ p ]; void SetFinishTime(int p, long t) { F i n i s h Time[p] = t; p r i v a t e : long *FinishTime; // int NumMachines; // ; EventList::EventList(int m, long BigT) {// m if (m < 1) throw BadInitializers(); F i n i s h Time = new long [m+1]; NumMachines = m; // for (int i = 1; i <= m; i++) F i n i s h Time[i] = BigT; void EventList::NextEvent(int& p, long& t) {// // p = 1; t = FinishTi m e [ 1 ]; for (int i = 2; i <= NumMachines; i++) if (FinishTime[i] < t) {// i p = i; t = FinishTi m e [ i ];

25 N o w N o L a rg e Ti m e 6-15 // long Now = 0; int m; long n; long LargeTime = 10000; EventList *EL; Machine *M; // // // // // // 8. I n p u t D a t a I n p u t D a t a 6-16 * E L L a rg e Ti m e M (machine, time) p p 6-16 void InputData() {// cout << "Enter number of machines and jobs" << endl; cin >> m >> n; if (m < 1 n < 1) throw BadInput(); // EL = new EventList(m,LargeTi m e ) ; M = new Machine [m+1]; // cout << "Enter change-over times for machines" << endl; for (int j = 1; j <= m; j++) { long ct; // cin >> ct; if (ct < 0) throw BadInput(); M [ j ]. S e t C h a n g e ( c t ) ; // n Job *J; for (int i = 1; i <= n; i++) { cout << "Enter number of tasks for job " << i << endl; int tasks; //

26 214 int first; // cin >> tasks; if (tasks < 1) throw BadInput(); J = new Job(i); cout << "Enter the tasks (machine, time)" << " in process order" << endl; for (int j = 1; j <= tasks; j++) {// int p; // long tt; // cin >> p >> tt; if (p < 1 p > m tt < 1) throw BadInput(); if (j == 1) first = p; // J - > A d d Task(p,tt); // M[first].AddJob(J); // 9. S t a r t S h o p C h a n g e S t a t e C h a n g e S t a t e ( i ) i 6-17 C h a n g e S t a t e 6-17 void StartShop() {// for (int p = 1; p <= m; p++) C h a n g e S t a t e ( p ) ; 6-18 C h a n g e S t a t e p C h a n g e S t a t e 0 ChangeState(p) p p p p M [ p ]. A c t i v e 0 p L a s t J o b 0 L a rg e Ti m e 1 M [ p ]. A c t i v e 0 p L a s t J o b C h a n g e Ti m e 6-18 Job* ChangeState(int p)

27 {// p Job* LastJob; if (!M[p].Active) {// LastJob = 0; // if (M[p].JobQ.IsEmpty()) // E L - > S e t F i n i s h Ti m e ( p, L a r g e Ti m e ) ; else {// Q M [ p ]. J o b Q. D e l e t e ( M [ p ]. A c t i v e ) ; M [ p ]. To t a l Wait += Now - M[p].Active->ArriveTi m e ; M [ p ]. N u m Ta s k s + + ; long t = M[p].Active->DeleteTa s k ( ) ; E L - > S e t F i n i s h Time(p, Now + t); else {// M[p] // LastJob = M[p].Active; M[p].Active = 0; E L - > S e t F i n i s h Time(p, Now + M[p].ChangeTi m e ) ; return LastJob; 10. S i m u l a t e M o v e To N e x t M a c h i n e 6-19 S i m u l a t e n n = 0 w h i l e w h i l e N o w p ( J 0 ) * J M o v e To N e x t M a c h i n e * J M o v e To N e x t M a c h i n e f a l s e n 1 M o v e To N e x t M a c h i n e 6-20 * J f a l s e * J * J p * p p C h a n g e S t a t e 6-19 void Simulate() {// n int p; long t; while (n) {// EL->NextEvent(p,t); // Now = t; // // p Job *J = ChangeState(p);

28 216 // J // J n 1 if (J &&!MoveToNextMachine(J)) n--; 6-20 bool MoveToNextMachine(Job *J) {// J // f a l s e if (J->TaskQ.IsEmpty()) {// cout << "Job " << J->ID << " has completed at " << Now << " Total wait was " << (Now-J->Length) << endl; return false; else {// // int p = J->Ta s k Q. F i r s t ( ). m a c h i n e ; // p M [ p ]. A d d J o b ( J ) ; J - > A r r i v e Time = Now; // p if (EL->NextEvent(p) == LargeTime) { // C h a n g e S t a t e ( p ) ; return true; 11. O u t p u t S t a t s M o v e To N e x t M a c h i n e O u t p u t S t a t s M o v e To N e x t M a c h i n e void OutputStats() {// cout << "Finish time = " << Now << endl; long To t a l Wait, NumTa s k s ; for (int p = 1; p <= m; p++) { M [ p ]. S t a t s ( To t a l Wait, NumTa s k s ); cout << "Machine " << p << " completed " << NumTasks << " tasks" << endl; cout << "The total wait time was " << To t a l Wa i t ; cout << endl << endl;

29 k i s i s i 13. C + + We l c o m e F i n d P a t h C + + We l c o m e L a b e l L a b e l L a b el c a t c h c a t c *20. * N.Sherwani. Algorithms for VLSI Physical Design Automation 2. Kluwer Academic

ebook39-5

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