6.087-07 Pointers , string arrays, Stacks and Queues

6.087 Lecture 7 – January 20, 2010Review More about Pointers Pointers to Pointers Pointer Arrays Multidimensional Arrays Data Structures Stacks Queues Application: Calculator 1 Review: Compound data types• struct -structure containing one or multiple fields, each with its own type (or compound type) • size is combined size of all the fields, padded for byte alignment • anonymous or named • union -structure containing one of several fields, each with its own type (or compound type) • size is size of largest field • anonymous or namedBit fields -structure fields with width in bits• • aligned and ordered in architecture-dependent manner can result in inefficient code • 1 Review: Compound data types• Consider this compound data structure: struct foo { short s; union { int i; char c;} u;unsigned int flag _s : 1;unsigned int flag_u : 2;unsigned int bar ;}; • Assuming a 32-bit x86 processor, evaluate sizeof(struct foo) 2 Review: Compound data types• Consider this compound data structure: struct foo { short s; ← 2 bytes union { ← 4 bytes, int i; 4 byte-aligned char c; } u; unsigned int flag _s : 1; bit fields unsigned int flag_u : 2; ← unsigned int bar ; 4 bytes,←}; 4 byte-aligned • Assuming a 32-bit x86 processor, evaluate sizeof(struct foo) 2 Review: Compound data types• How can we rearrange the fields to minimize the size of struct foo? 3 Review: Compound data types• How can we rearrange the fields to minimize the size of struct foo? • Answer: order from largest to smallest: struct foo { union {int i;char c;} u;unsigned i n t bar ;short s;unsigned i n t flag _s : 1;unsigned i n t flag _u : 2;}; sizeof(struct foo) = 12 3 Review: Linked lists and trees• Linked list and tree dynamically grow as data is added/removed • Node in list or tree usually implemented as a struct • Use malloc(), free(), etc. to allocate/free memory dynamically • Unlike arrays, do not provide fast random access by index (need to iterate) 4 6.087 Lecture 7 – January 20, 2010Review More about Pointers Pointers to Pointers Pointer Arrays Multidimensional Arrays Data Structures Stacks Queues Application: Calculator 5 Pointer review• Pointer represents address to variable in memory • Examples: int ∗pn; – pointer to int struct div_t ∗ pdiv; – pointer to structure div_t • Addressing and indirection: double pi = 3.14159;double ∗ ppi = πprintf ( "pi = %g\n" , ∗ ppi );• Today: pointers to pointers, arrays of pointers, multidimensional arrays 5 Pointers to pointers• Address stored by pointer also data in memory • Can address location of address in memory – pointer to that pointer int n= 3;int ∗pn =&n; /∗ pointer to n ∗ /int ∗∗ppn =&pn; /∗ pointer to address of n ∗ /• Many uses in C: pointer arrays, string arrays 6 Pointer pointers exampleWhat does this function do? • void swap( int ∗∗a, int ∗∗b) { int ∗temp = ∗a; ∗a= ∗b; ∗b = temp ; } 7 Pointer pointers exampleWhat does this function do? • void swap( int ∗∗a, int ∗∗b) {int ∗temp = ∗a;∗a= ∗b;∗b = temp ;} • How does it compare to the familiar version of swap? void swap( int ∗a, int ∗b) {int temp = ∗a;∗a= ∗b;∗b = temp ;} 7 Pointer arrays• Pointer array – array of pointers int ∗arr [20]; – an array of pointers to int’s char ∗arr[10]; – an array of pointers to char’s • Pointers in array can point to arrays themselves char ∗strs [10]; – an array of char arrays (or strings) 8 Pointer array example• Have an array int arr [100]; that contains some numbers • Want to have a sorted version of the array, but not modify arr • Can declare a pointer array int ∗ sorted_array[100]; containing pointers to elements of arr and sort the pointers instead of the numbers themselves • Good approach for sorting arrays whose elements are very large (like strings) 9 Pointer array exampleInsertion sort: /∗ move previous elements down until insertion point reached ∗ /void shift _element ( unsigned int i) { int ∗ pvalue ; /∗ guard against going outside array ∗ /for ( pvalue = sorted_array [ i ] ; i && ∗ sorted_array [ i −1] > ∗ pvalue ; i −−){ /∗ move pointer down ∗ /sorted_array [ i ] = sorted_array [ i −1]; } sorted_array [ i ] = pvalue ; /∗ insert pointer ∗ /} 10 Pointer array exampleInsertion sort (continued): /∗ iterate until out−of−order element found ; shift the element , and continue iterating ∗ /void insertion _sort ( void ){ unsigned i n t i, len = array_length(arr); for (i =1; i initialized for empty stack ∗/16 Stack as array• Add element using void push(int); void push ( int elem) {stack _buffer[itop++] = elem;}• Remove element using int pop(void); int pop ( void ){if ( itop > 0)return stack _buffer[−− itop ];elsereturn 0; /∗ or other special value ∗ /}• Some implementations provide int top(void); to read last (top) element without removing it 17 Stack as linked list• Store as linked list (dynamic allocation): struct s_listnode {int element ;struct s_listnode pnext;∗ }; struct s_listnode ∗ stack_buffer = NULL; – start empty • “Top” is now at front of linked list (no need to track) 18 Stack as linked list• Add element using void push(int); void push ( int elem) { struct s_listnode ∗new_node = /∗ allocate new node ∗ /( struct s_listnode ∗ ) malloc ( sizeof ( struct s_listnode )) new_node−>pnext = stack _buffer ; new_node−>element = elem ; stack _buffer = new_node; } • Adding an element pushes back the rest of the stack 19 Stack as linked list• Remove element using int pop(void); int pop ( void ){ if (stack _buffer) { struct s_listnode ∗pelem = stack _buffer ; int elem = stack_buffer −>element ; stack _buffer = pelem−>pnext ; free(pelem); /∗ remove node from memory ∗ /return elem ; } elsereturn 0; /∗ or other special value ∗ /}• Some implementations provide int top(void); to read last (top) element without removing it 20 The queue• Opposite of stack -first in (enqueue), first out (dequeue) • Read and write from opposite ends of list • Important for UIs (event/message queues), networking (Tx, Rx packet queues) • Imposes an ordering on elements 21 Queue as array• Again, store as array buffer (static or dynamic allocation); float queue_buffer[100]; • Elements added to end (rear), removed from beginning (front) • Need to keep track of front and rear: int ifront = 0, irear = 0; • Alternatively, we can track the front and number of elements: int ifront = 0, icount = 0; • We’ll use the second way (reason apparent later) 22 Queue as array• Add element using void enqueue(float); void enqueue ( float elem) { if ( icount < 100) { queue_buffer[ifront+icount] = elem; icount ++; }}• Remove element using float dequeue(void); float dequeue ( void ){ if ( icount > 0) {icount −−;return queue_buffer[ ifront++];} else return 0.; /∗ or other special value ∗ /} 23 � � � � Queue as arrayThis would make for a very poor queue! Observe a queue • of capacity 4: a cb front rear Enqueue ’d’ to the rear of the queue: • a cb d front rearThe queue is now full.24 � � Queue as arrayDequeue ’a’:• cb d front rear Enqueue ’e’ to the rear: where should it go? • Solution: use a circular (or “ring”) buffer • ’e’ would go in the beginning of the array • 25 Queue as array• Need to modify void enqueue(float); and float dequeue(void); • New void enqueue(float);: void enqueue ( float elem) { if ( icount < 100) { queue_buffer[(ifront+icount) % 100] = elem; icount ++; }}26 Queue as array• New float dequeue(void);: float dequeue ( void ){ if ( icount > 0) { float elem = queue_buffer[ ifront ]; icount −−; ifront ++; if ( ifront == 100) ifront = 0; return elem ; } else return 0.; /∗ or other special value ∗ /} • Why would using “front” and “rear” counters instead make this harder? 27 Queue as linked list• Store as linked list (dynamic allocation): struct s_listnode {float element ;struct s_listnode pnext;∗ }; struct s_listnode ∗queue_buffer = NULL; – start empty • Let front be at beginning – no need to track front Rear is at end – we should track it: • struct s_listnode ∗prear = NULL; 28 Queue as linked list• Add element using void enqueue(float); void enqueue ( float elem) { struct s_listnode ∗new_node = /∗ allocate new node ∗ /( struct s_listnode ∗ ) malloc ( sizeof ( struct s_listnode )) new_node−>element = elem ; new_node−>pnext = NULL; /∗ at rear ∗ /if ( prear ) prear −>pnext = new_node; else /∗ empty ∗ /queue_buffer = new_node;prear = new_node;}• Adding an element doesn’t affect the front if the queue is not empty 29 Queue as linked list• Remove element using float dequeue(void); float dequeue ( void ){ if ( queue_buffer ) { struct s_listnode ∗pelem = queue_buffer ; float elem = queue_buffer −>element ; queue_buffer = pelem−>pnext ; if (pelem == prear ) /∗ at end ∗ /prear = NULL; free(pelem); /∗ remove node from memory ∗ /return elem ; } elsereturn 0.; /∗ or other special value ∗ /}• Removing element doesn’t affect rear unless resulting queue is empty 30 A simple calculator• Stacks and queues allow us to design a simple expression evaluator • Prefix, infix, postfix notation: operator before, between, and after operands, respectivelyInfixA+BA*B-C( A + B ) * ( C -D)Prefix+AB -*ABC *+AB-CD PostfixAB+AB*CAABCD-*• Infix more natural to write, postfix easier to evaluate 31 Infix to postfix• "Shunting yard algorithm" -Dijkstra (1961): input and output in queues, separate stack for holding operators • Simplest version (operands and binary operators only): 1. dequeue token from input 2. if operand (number), add to output queue 3. if operator, then pop operators off stack and add to output queue as long as • top operator on stack has higher precedence, or • top operator on stack has same precedence and is left-associativeand push new operator onto stack4. return to step 1 as long as tokens remain in input 5. pop remaining operators from stack and add to output queue 32 Infix to postfix example• Infix expression: A + B * C -D TokenA + B * C -D (end) Output queueA A AB AB ABC ABC*+ ABC*+D ABC*+D-Operator stack+ + +* +* --• Postfix expression: A B C * + D ₭ What if expression includes parentheses? 33 Example with parentheses• Infix expression: ( A + B ) * ( C -D ) Token( A + B ) * ( C -D ) (end) Output queueA A AB AB+ AB+ AB+ AB+C AB+C AB+CD AB+CDAABCD-* Operator stack( ( (+ (+ * *( *( *(**­ • Postfix expression: A B + C D -* 34 Evaluating postfix• Postfix evaluation very easy with a stack: 1. dequeue a token from the postfix queue 2. if token is an operand, push onto stack 3. if token is an operator, pop operands off stack (2 for binary operator); push result onto stack 4. repeat until queue is empty 5. item remaining in stack is final result 35 Postfix evaluation example• Postfix expression: 3 4 + 5 1 -* Token33 434 +7 575 1751 -*28 (end)answer = 28 Stack74 • Extends to expressions with functions, unary operators • Performs evaluation in one pass, unlike with prefix notation 36 SummaryTopics covered: • Pointers to pointers • pointer and string arrays • multidimensional arraysData structures• • stack and queue • implemented as arrays and linked lists • writing a calculator 37 MIT OpenCourseWarehttp://ocw.mit.edu 6.087 Practical Programming in CJanuary (IAP) 2010For information about citing these materials or our Terms of Use,visit: http://ocw.mit.edu/terms.