Midterm Review (overview of fall 2005 midterm)1. Modulo Arithmetic and Character I/OSlide 32. Pointers and Strings3. Short Answer4. Deterministic Finite AutomataSlide 7Slide 8Slide 95: Abstract Data TypesSlide 11Slide 12Slide 13Slide 14Slide 15Queue_add() Implementation5. ADT Common MistakesMidterm Review (overview of spring 2008 midterm)Bit-Wise ManipulationsWhat Does This Function Do?Good Bug HuntingFixing the Bug: RewriteSlide 23Preparing for the Exam1Midterm Review(overview of fall 2005 midterm)Professor Jennifer RexfordCOS 21721. Modulo Arithmetic and Character I/Ovoid f(unsigned int n) { do { putchar(‘0’ + (n % 10)); } while (n /= 10); putchar(‘\n’); } • What does f(837) produce?• What does this function do?31. Modulo Arithmetic and Character I/Ovoid f(unsigned int n){ for ( ; n; n /= 10) putchar(‘0’ + (n % 10)); putchar(‘\n’);} •When is the answer different?42. Pointers and Stringsvoid f(char *s) { char *p = s; while (*s) s++; for (s--; s>p; s--,p++) { char c = *s; *s = *p; *p = c; } } •What does this function do?b a r \053. Short Answer•In the memory layout for a UNIX process:Why does the heap grow from the top down and the stack from the bottom up, instead of both growing from the top down or both growing from the bottom up? TextDataBSSStackHeap64. Deterministic Finite Automata•Valid numbers“-34”“78.1”“+298.3”“-34.7e-1”“34.7E-1”“7.”“.7”“999.99e99” •Invalid numbers“abc”“-e9”“1e”“+”“17.9A”“0.38+”“.”“38.38f9” Identify whether or not a string is a floating-point number74. Deterministic Finite Automata•Optional “+” or “-”•Zero or more digits+-###84. Deterministic Finite Automata•Optional “+” or “-”•Zero or more digits•Optional decimal pointFollowed by zero or more digits.+-#####..94. Deterministic Finite Automata•Optional “+” or “-”•Zero or more digits•Optional decimal pointFollowed by zero or more digits.#####.•Optional exponent “E” or “e”Followed by optional “+” or “-”Followed by one or more digits.EEee#+-+-##105: Abstract Data Types•Interface for a Queue (a first-in-first-out data structure)#ifndef QUEUE_INCLUDED #define QUEUE_INCLUDED typedef struct Queue_t *Queue_T; Queue_T Queue_new(void); int Queue_empty(Queue_T queue); void Queue_add(Queue_T queue, void* item); void* Queue_remove(Queue_T queue); #endif115: Abstract Data Types•An implementation for a Queue (in queue.c)#include <stdlib.h> #include <assert.h> #include "queue.h" struct list { void* item; struct list *next; }; struct Queue_t { struct list *head; struct list *tail; }; Why void*?Why declared here and not in queue.h?125: Abstract Data Types•An implementation for a Queue_newQueue_T Queue_new(void) { Queue_T queue = malloc(sizeof *queue); assert(queue != NULL); queue->head = NULL; queue->tail = NULL; return queue; } Implement a check for whether the queue is empty.135: Abstract Data Types•An implementation for a Queue_emptyint Queue_empty(Queue_T queue) { assert(queue != NULL); return queue->head == NULL; }145: Abstract Data Types•An implementation for a Queue_add3 2 1headtail0newnode3 2 1headtail0155: Abstract Data Types•An implementation for a Queue_addheadtail0newnode0headtailNULL16Queue_add() Implementationvoid Queue_add(Queue_T queue, void *item) { struct list *newnode; assert(queue != NULL); newnode = (struct list*)malloc(sizeof(*newnode)); assert(newnode != NULL); newnode->item = item; newnode->next = NULL; if (queue->tail == NULL) queue->head = newnode; else queue->tail->next = newnode; queue->tail = newnode; }175. ADT Common Mistakes•Adding to the queueImplementing a stack rather than a queue–Adding element to the head, rather than the tailNot handling the case where the queue is emptyMissing assert() after call to malloc() for new entry•Removing from the queueMissing assert() when removing an element from an empty queueNot handling removing the last item from the queueNot doing a free() to return space used by the head element18Midterm Review(overview of spring 2008 midterm)19Bit-Wise Manipulations•Consider the following code, where k is an unsigned int: printf(“%u\n”, k – ((k >> 2) << 2)); •What does the code do? Rewrite the line of code in a more efficient way. •Replaces last two bits with 0Same as doing: k & 320What Does This Function Do?char* f(unsigned int n) { int i, numbits = sizeof(unsigned int) * 8; char* ret = (char *) malloc(numbits + 1); for (i=numbits-1; i>=0; i--, n>>=1) ret[i] = ‘0’ + (n & 1); ret[numbits] = ‘\0’; return ret; } n = 19 0001001121Good Bug Hunting•Consider this function that converts an integer to a string•Where the sprintf() function “prints” to a formatted string, e.g., sprintf(retbuf, “%d”, 72) places the string “72” starting at the location in memory indicated by the address retbuf: char *itoa(int n) { char retbuf[5]; sprintf(retbuf, “%d”, n); return retbuf; } Not enough spaceTemporary memory22Fixing the Bug: Rewritechar *itoa(int n) { int size = 0; int temp = n; /* Count number of decimal digits in n */ while (temp /= 10) size++; size++; /* If n is negative, add room for the "-" sign */ if (n < 0) size++;23Fixing the Bug: Rewrite /* Allocate space for the string */ char* retbuf = (char *) malloc(size + 1); assert(retbuf != NULL); /* Convert the number to a string of digits */ sprintf(retbuf, "%d", n); return retbuf; }24Preparing for the Exam•Studying for the examRead through lecture and precept nodesStudy past midterm examsRead through exercises in the book•Taking the examRead briefly through all questionsStrategize where you spend your time•Exam logisticsWednesday 10-10:50am in COS 104Open book, open notes, open mind… just no computerNo questions on UNIX tools (e.g., emacs, gcc, gdb, …)•No Wednesday/Thursday precept this weekHave a great spring
View Full Document
Unlocking...