New version page

# Princeton COS 217 - Modulo Arithmetic and Character

Pages: 13
Documents in this Course

4 pages

14 pages

27 pages

27 pages

21 pages

6 pages

6 pages

29 pages

7 pages

16 pages

13 pages

34 pages

12 pages

20 pages

32 pages

17 pages

5 pages

36 pages

26 pages

2 pages

3 pages

38 pages

9 pages

13 pages

4 pages

52 pages

57 pages

22 pages

4 pages

33 pages

12 pages

8 pages

14 pages

4 pages

13 pages

18 pages

43 pages

12 pages

17 pages

46 pages

14 pages

7 pages

34 pages

24 pages

4 pages

8 pages

16 pages

20 pages

51 pages

15 pages

8 pages

39 pages

51 pages

15 pages

35 pages

102 pages

22 pages

7 pages

36 pages

13 pages

13 pages

16 pages

4 pages

31 pages

40 pages

38 pages

12 pages

20 pages

8 pages

31 pages

26 pages

23 pages

32 pages

18 pages

21 pages

2 pages

16 pages

20 pages

39 pages

7 pages

48 pages

38 pages

27 pages

10 pages

32 pages

22 pages

33 pages

44 pages

26 pages

41 pages

35 pages

19 pages

6 pages

10 pages

33 pages

19 pages

6 pages

26 pages

36 pages

5 pages

5 pages

67 pages

31 pages

35 pages

7 pages

15 pages

4 pages

10 pages

42 pages

2 pages

9 pages

11 pages

17 pages

103 pages

4 pages

7 pages

29 pages

27 pages

48 pages

48 pages

12 pages

16 pages

80 pages

22 pages

34 pages

34 pages

19 pages

7 pages

5 pages

24 pages

20 pages

6 pages

18 pages

Load more

## This preview shows page 1-2-3-4 out of 13 pages.

View Full Document

End of preview. Want to read all 13 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document
Unformatted text preview:

1 1 Midterm Review!(overview of fall 2005 midterm)"COS 217!2 1. Modulo Arithmetic and Character I/O"void f(unsigned int n) { do { putchar(‘0’ + (n % 10)); } while (n /= 10); putchar(‘\n’); } • What does f(837) produce? • What does this function do?2 3 1. Modulo Arithmetic and Character I/O"void f(unsigned int n){ for ( ; n; n /= 10) putchar(‘0’ + (n % 10)); putchar(‘\n’); } • When is the answer different? 4 2. Pointers and Strings"void 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 \03 5 3. 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? !Text Data BSS Stack Heap 6 4. 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 number4 7 4. Deterministic Finite Automata"• Optional “+” or “-”!• Zero or more digits!+ - # # # 8 4. Deterministic Finite Automata"• Optional “+” or “-”!• Zero or more digits!• Optional decimal point! Followed by zero or more digits!. + - # # # # # . .5 9 4. Deterministic Finite Automata"• Optional “+” or “-”!• Zero or more digits!• Optional decimal point! Followed by zero or more digits!. # # # # # . • Optional exponent “E” or “e”! Followed by optional “+” or “-”! Followed by one or more digits!. E E e e # + - + - # # 10 5: 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); #endif !6 11 5: Abstract Data Types"• Data structures for a Queue!struct list { void* item; struct list *next; }; struct Queue_t { struct list *head; struct list *tail; }; Why void*? 12 5: Abstract Data Types"• An implementation for a Queue_new!Queue_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.7 13 5: Abstract Data Types"• An implementation for a Queue_empty int Queue_empty(Queue_T queue) { assert(queue != NULL); return queue->head == NULL; } 14 5: Abstract Data Types"• An implementation for a Queue_add 3 2 1 head tail 0 newnode 3 2 1 head tail 08 15 5: Abstract Data Types"• An implementation for a Queue_add head tail 0 newnode 0 head tail NULL 16 Queue_add() Implementation"void 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; !} !9 17 5. ADT Common Mistakes"• Adding to the queue! Implementing a stack rather than a queue!– Adding element to the head, rather than the tail! Not handling the case where the queue is empty! Missing assert() after call to malloc() for new entry!• Removing from the queue! Missing assert() when removing an element from an empty queue! Not handling removing the last item from the queue! Not doing a free() to return space used by the head element!18 Midterm Review!(overview of spring 2008 midterm)"10 19 Bit-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. !20 What 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; !} !11 21 Good 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 space Temporary memory 22 Fixing the Bug: Rewrite"char *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++; !12 23 Fixing 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; !} !Common Errors for this Problem"• Mishandle case where n is 0, which requires 1 character • Assume n is unsigned, and not allocate space for the minus sign • Omit the “assert(retbuf)” after the call to malloc • Use “sizeof(n)” to compute the length: gives bytes in int type • Extract each of the digits of n, using code similar to question 1b (but base 10). Perfectly valid, though using “sprintf” is simpler. • An interesting, and clever, answer was to create a large array of characters as a local variable, use sprintf to place the string representation of n in the array, use strlen() to compute the length of the string, use malloc() to allocate the appropriate amount of space to retbuff, and then copy the string from the local variable to retbuf. 2413 25 Preparing for the Exam"• Studying for the exam! Read through lecture and precept nodes! Study past midterm exams!

View Full Document
Unlocking...
Sign Up

Join to view Modulo Arithmetic and Character and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?