Arndt - Algorithms for Programmers (523138), страница 37
Текст из файла (страница 37)
That is, a call totemplate <typename Type>void heap_sort(Type *x, ulong n){build_heap(x, n);heap_sort_ascending(x, n);}will sort the array x[] into ascending order. Note that sorting into descending order is not any harder:template <typename Type>void heap_sort_decending(Type *x, ulong n)// sort an array that has the heap-property into descending order.// On return x[] is _not_ a heap anymore.{Type *p = x - 1;for (ulong k=n; k>1; --k){++p; --n;// remaining array is one element lessheapify1(p, n, 1); // restore heap-property}}[FXT: file sort/heapsort.h]Find a demo in [FXT: file demo/heapsort-demo.cc], its output in [FXT: file demo/heapsort-out.txt].Chapter 10Data structures10.1Stack (LIFO)A stack (or LIFO for last-in, first-out) is a data structure that supports the operations: push to saves anentry and pop to retrieve and remove the entry that was entered last.
The occasionally useful operationpeek retrieves the same element as pop but does not remove it. Similarly, poke modifies the last entry.An implementation with the option to let the stack grow when necessary can be found in [FXT: fileds/stack.h]template <typename Type>class stack{public:Type *x_; // dataulong s_; // sizeulong p_; // stack pointer (position of next write), top entry @ p-1ulong gq_; // grow gq elements if necessary, 0 for "don’t grow"public:stack(ulong n, ulong growq=0){s_ = n;x_ = new Type[s_];p_ = 0; // stack is emptygq_ = growq;}~stack() { delete [] x_; }private:stack & operator = (const stack &); // forbiddenpublic:ulong n() const// return number of entries{return p_;}ulong push(Type z)// return size of stack, zero on stack overflow// if gq_ is non-zero the stack grows{if ( p_ >= s_ ){if ( 0==gq_ ) return 0; // overflowulong ns = s_ + gq_; // new sizeType *nx = new Type[ns];copy(x_, nx, s_);delete [] x_; x_ = nx;s_ = ns;}211CHAPTER 10.
DATA STRUCTURES212x_[p_] = z;++p_;return s_;};}ulong pop(Type &z)// read top entry and remove it// return number of entries at function start// if empty return zero is returned and z is undefined{ulong ret = p_;if ( 0!=p_ ) { --p_; z = x_[p_]; }return ret;}ulong poke(Type z)// modify top entry// return number of entries// if empty return zero is returned and nothing done{if ( 0!=p_ ) x_[p_-1] = z;return p_;}ulong peek(Type &z)// read top entry (without removing it)// return number of entries// if empty zero is returned z is undefined{if ( 0!=p_ ) z = x_[p_-1];return p_;}Its working is demonstrated in [FXT: file demo/stack-demo.cc].
An example output where the initialsize is 4 and the growths-feature enabled (in steps of 4 elements) looks like:push( 1)push( 2)push( 3)push( 4)push( 5)push( 6)push( 7)pop== 7pop== 6push( 8)pop== 8pop== 5push( 9)pop== 9pop== 4push(10)pop==10pop== 3push(11)pop==11pop== 2push(12)pop==12pop== 1push(13)pop==13pop== 0(stackpush(14)pop==14pop== 0(stackpush(15)1 - - 1 2 - 1 2 3 1 2 3 41 2 3 41 2 3 41 2 3 41 2 3 41 2 3 41 2 3 41 2 3 41 2 3 41 2 3 41 2 3 41 2 3 1 2 3 101 2 3 1 2 - 1 2 11 1 2 - 1 - - 1 12 - 1 - - - - - 13 - - - - - - - - was empty)14 - - - - - - - - was empty)15 - - -#=1#=2#=3#=45 5 65 65 65 5 85 - 9 - - - - - - - - - - - - - - -7--#=5#=6#=7#=6#=5#=6#=5#=4#=5#=4#=3#=4#=3#=2#=3#=2#=1#=2#=1#=0#=1#=0#=0----#=1#=0#=0----#=1CHAPTER 10.
DATA STRUCTURES10.2213Ring bufferA ring buffer is a array plus read- and write operations that wrap around. That is, if the last position ofthe array is reached writing continues at the begin of the array, thereby erasing the oldest entries. Theread operation should start at the oldest entry in the array.The ringbuffer utility class in [FXT: class ringbuffer in ds/ringbuffer.h] is as simple as:template <typename Type>class ringbuffer{public:Type *x_;// data (ring buffer)ulong s_;// allocated size (# of elements)ulong n_;// current number of entries in bufferulong wpos_; // next position to write in bufferulong fpos_; // first position to read in bufferpublic:explicit ringbuffer(ulong n){s_ = n;x_ = new Type[s_];n_ = 0;wpos_ = 0;fpos_ = 0;}~ringbuffer() { delete [] x_; }ulong n() const { return n_; }void insert(const Type &z){x_[wpos_] = z;if ( ++wpos_>=s_ ) wpos_ = 0;if ( n_ < s_ ) ++n_;else fpos_ = wpos_;}ulong read(ulong n, Type &z) const// read entry n (that is, [(fpos_ + n)%s_])// return 0 if entry #n is last in buffer// else return n+1{if ( n>=n_ ) return 0;ulong j = fpos_ + n;if ( j>=s_ ) j -= s_;z = x_[j];return n + 1;}};Reading from the ring buffer goes like:ulong k = 0;Type z; // type of entrywhile ( (k = f.read(k, z)) ){// do something with z}A demo is in [FXT: file demo/ringbuffer-demo.cc], its output isinsert(insert(insert(insert(insert(insert(insert(insert(insert(1)2)3)4)5)6)7)8)9)11112345622234567#=13345678r=1w=0r=2w=0#=3r=3w=04#=4r=0w=05#=4r=1w=16#=4r=2w=27#=4r=3w=38#=4r=0w=09#=4r=1w=1#=2CHAPTER 10.
DATA STRUCTURES214Ring buffers can be useful for storing a constant amount of history-data such as for logging purposes. Forthat one would enhance the ringbuffer class so that it uses an additional array of (fixed width) strings.The message to log would be copied into the array and the pointer set accordingly. Read should thenjust return the pointer to the string.10.3Queue (FIFO)A queue (or LIFO for first-in, first-out) is a data structure that supports two operations: push saves anentry and pop retrieves (and removes) the entry that was entered the longest time ago. The occasionallyuseful operation peek retrieves the same element as pop but does not remove it.A utility class with the optional feature of growing if necessary is [FXT: class queue in ds/queue.h]:template <typename Type>class queue{public:Type *x_;// data (ring buffer)ulong s_;// allocated size (# of elements)ulong n_;// current number of entries in bufferulong wpos_; // next position to write in bufferulong rpos_; // next position to read in bufferulong gq_; // grow gq elements if necessary, 0 for "don’t grow"public:explicit queue(ulong n, ulong growq=0){s_ = n;x_ = new Type[s_];n_ = 0;wpos_ = 0;rpos_ = 0;gq_ = growq;}~queue() { delete [] x_; }ulong n() const { return n_; }ulong push(const Type &z)// returns number of entries// zero is returned on failure//(i.e.
space exhausted and 0==gq_){if ( n_ >= s_ ){if ( 0==gq_ ) return 0; // growing disabledulong ns = s_ + gq_; // new sizeType *nx = new Type[ns];// move read-position to zero:rotate_left(x_, s_, rpos_);wpos_ = s_;rpos_ = 0;copy(x_, nx, s_);delete [] x_; x_ = nx;s_ = ns;}x_[wpos_] = z;++wpos_;if ( wpos_>=s_ ) wpos_ = 0;++n_;return n_;}ulong peek(Type &z)// returns number of entries// if zero is returned the value of z is undefined{z = x_[rpos_];return n_;CHAPTER 10.
DATA STRUCTURES};215}ulong pop(Type &z)// returns number of entries before pop// i.e. zero is returned if queue was empty// if zero is returned the value of z is undefined{ulong ret = n_;if ( 0!=n_ ){z = x_[rpos_];++rpos_;if ( rpos_ >= s_ ) rpos_ = 0;--n_;}return ret;}Its working is demonstrated in [FXT: file demo/queue-demo.cc]. An example output where the initialsize is 4 and the growths-feature enabled (in steps of 4 elements) looks like:push( 1) 1 - - #=1r=0push( 2) 1 2 - #=2r=0push( 3) 1 2 3 #=3r=0push( 4) 1 2 3 4#=4r=0push( 5) 1 2 3 4 5 - - push( 6) 1 2 3 4 5 6 - push( 7) 1 2 3 4 5 6 7 pop== 1- 2 3 4 5 6 7 pop== 2- - 3 4 5 6 7 push( 8) - - 3 4 5 6 7 8pop== 3- - - 4 5 6 7 8pop== 4- - - - 5 6 7 8push( 9) 9 - - - 5 6 7 8pop== 59 - - - - 6 7 8pop== 69 - - - - - 7 8push(10) 9 10 - - - - 7 8pop== 79 10 - - - - - 8pop== 89 10 - - - - - push(11) 9 10 11 - - - - pop== 9- 10 11 - - - - pop==10- - 11 - - - - push(12) - - 11 12 - - - pop==11- - - 12 - - - pop==12- - - - - - - push(13) - - - - 13 - - pop==13- - - - - - - pop== 0- - - - - - - (queue was empty)push(14) - - - - - 14 - pop==14- - - - - - - pop== 0- - - - - - - (queue was empty)push(15) - - - - - - 15 -w=1w=2w=3w=0#=5#=6#=7#=6#=5#=6#=5#=4#=5#=4#=3#=4#=3#=2#=3#=2#=1#=2#=1#=0#=1#=0#=0r=0r=0r=0r=1r=2r=2r=3r=4r=4r=5r=6r=6r=7r=0r=0r=1r=2r=2r=3r=4r=4r=5r=5w=5w=6w=7w=7w=7w=0w=0w=0w=1w=1w=1w=2w=2w=2w=3w=3w=3w=4w=4w=4w=5w=5w=5#=1#=0#=0r=5r=6r=6w=6w=6w=6#=1r=6w=7This is [FXT: file demo/queue-out.txt].
You might want to compare this to the stack-demo at page 212.10.4Deque (double-ended queue)A deque (for double-ended queue) combines the data structures stack and queue: insertion and deletionis possible both at the first- and the last postion, all in time-O(1). An implementation with the optionto let the stack grow when necessary can be found in [FXT: file ds/deque.h]template <typename Type>class deque{public:CHAPTER 10.
DATA STRUCTURESType *x_;// data (ring buffer)ulong s_;// allocated size (# of elements)ulong n_;// current number of entries in bufferulong fpos_; // position of first element in buffer// insert_first() will write to (fpos-1)%nulong lpos_; // position of last element in buffer plus one// insert_last() will write to lpos, n==(lpos-fpos) (mod s)// entries are at [fpos, ... , lpos-1] (range may be empty)ulong gq_; // grow gq elements if necessary, 0 for "don’t grow"public:explicit deque(ulong n, ulong growq=0){s_ = n;x_ = new Type[s_];n_ = 0;fpos_ = 0;lpos_ = 0;gq_ = growq;}~deque() { delete [] x_; }ulong n() const { return n_; }ulong insert_first(const Type &z)// returns number of entries after insertion// zero is returned on failure//(i.e.
space exhausted and 0==gq_){if ( n_ >= s_ ){if ( 0==gq_ ) return 0; // growing disabledgrow();}--fpos_;if ( fpos_ == -1UL ) fpos_ = s_ - 1;x_[fpos_] = z;++n_;return n_;}ulong insert_last(const Type &z)// returns number of entries after insertion// zero is returned on failure//(i.e. space exhausted and 0==gq_){if ( n_ >= s_ ){if ( 0==gq_ ) return 0; // growing disabledgrow();}x_[lpos_] = z;++lpos_;if ( lpos_>=s_ ) lpos_ = 0;++n_;return n_;}ulong extract_first(Type & z)// return number of elements before extract// return 0 if extract on empty deque was attempted{if ( 0==n_ ) return 0;z = x_[fpos_];++fpos_;if ( fpos_ >= s_ ) fpos_ = 0;--n_;return n_ + 1;}ulong extract_last(Type & z)// return number of elements before extract// return 0 if extract on empty deque was attempted{216CHAPTER 10.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
