Chapter 3 – Control Flow
Exercise 3-1
Our binary search makes two tests inside the loop, when one would suffice (at the price of more tests outside). Write a version with only one test inside the loop and measure the difference in run-time.
#include <stdio.h>
#include <time.h>
#define MAX_ELEMENT 20000
int binsearch(int x, int v[], int n);
int binsearch2(int x, int v[], int n);
int main(void) {
int testdata[MAX_ELEMENT];
int index;
int n = -1;
int i;
clock_t time_taken;
for ( i = 0; i < MAX_ELEMENT; ++i )
testdata[i] = i;
for ( i = 0, time_taken = clock(); i < 100000; ++i ) {
index = binsearch(n, testdata, MAX_ELEMENT);
}
time_taken = clock() - time_taken;
if ( index < 0 )
printf("Element %d not found./n", n);
else
printf("Element %d found at index %d./n", n, index);
printf("binsearch() took %lu clocks (%lu seconds)/n",
(unsigned long) time_taken,
(unsigned long) time_taken / CLOCKS_PER_SEC);
for ( i = 0, time_taken = clock(); i < 100000; ++i ) {
index = binsearch2(n, testdata, MAX_ELEMENT);
}
time_taken = clock() - time_taken;
if ( index < 0 )
printf("Element %d not found./n", n);
else
printf("Element %d found at index %d./n", n, index);
printf("binsearch2() took %lu clocks (%lu seconds)/n",
(unsigned long) time_taken,
(unsigned long) time_taken / CLOCKS_PER_SEC);
return 0;
}
int binsearch(int x, int v[], int n) {
int low, mid, high;
low = 0;
high = n - 1;
while ( low <= high ) {
mid = (low+high) / 2;
if ( x < v[mid] )
high = mid - 1;
else if ( x > v[mid] )
low = mid + 1;
else
return mid;
}
return -1;
}
int binsearch2(int x, int v[], int n) {
int low, high, mid;
low = 0;
high = n - 1;
mid = (low+high) / 2;
while ( low <= high && x != v[mid] ) {
if ( x < v[mid] )
high = mid - 1;
else
low = mid + 1;
mid = (low+high) / 2;
}
if ( x == v[mid] )
return mid;
else
return -1;
}
Exercise 3-2
Write a function escape(s,t) that converts characters like newline and tab into visible escape sequences like /n and /t as it copies the string t to s . Use a switch. Write a function for the other direction as well, converting escape sequences into the real characters.
#include <stdio.h>
#define MAX_LEN 1024
#define SLASH 1
#define TAB 2
#define NEWLINE 3
#define OTHER 4
void escape(char s[], char t[]);
void deescape(char t[], char s[]);
int main() {
char str[] = "This is a test/n. This is another example./n";
char t[MAX_LEN];
char str2[MAX_LEN];
escape(str, t);
printf("%s/n", str);
printf("%s/n", t);
deescape(t, str2);
printf("%s/n", str2);
return 0;
}
void escape(char s[], char t[]) {
int i, j;
for (i = 0, j = 0; s[i] != '/0'; i++) {
if (s[i] == '/t' ) {
t[j++] = '//';
t[j++] = 't';
} else if (s[i] == '/n') {
t[j++] = '//';
t[j++] = 'n';
}
else {
t[j++] = s[i];
}
}
t[j] = '/0';
}
void deescape(char t[], char s[]) {
int state = OTHER, i, j;
for (i = 0, j = 0; t[i] != '/0'; i++) {
switch(state) {
case OTHER:
if (t[i] == '//') {
state = SLASH;
} else {
s[j++] = t[i];
}
break;
case SLASH:
if (t[i] == 't') {
state = TAB;
} else if (t[i] == 'n') {
state = NEWLINE;
} else if(t[i] != '//') {
state = OTHER;
}
break;
case TAB:
s[j++] = '/t';
state = OTHER;
break;
case NEWLINE:
s[j++] = '/n';
state = OTHER;
break;
default: break;
}
}
s[j] = '/0';
}
Exercise 3-3
Write a function expand(s1,s2) that expands shorthand notations like a-z in the string s1 into the equivalent complete list abc...xyz in s2 . Allow for letters of either case and digits, and be prepared to handle cases like a-b-c and a-z0-9 and -a-z . Arrange that a leading or trailing - is taken literally.
#include <stdio.h>
#include <string.h>
void expand(char * s1, char * s2);
int main(void) {
char *s[] = { "a-z-", "z-a-", "-1-6-",
"a-ee-a", "a-R-L", "1-9-1",
"5-5", NULL };
char result[100];
int i = 0;
while ( s[i] ) {
expand(result, s[i]);
printf("Unexpanded: %s/n", s[i]);
printf("Expanded : %s/n", result);
++i;
}
return 0;
}
void expand(char * s1, char * s2) {
static char upper_alph[27] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
static char lower_alph[27] = "abcdefghijklmnopqrstuvwxyz";
static char digits[11] = "0123456789";
char * start, * end, * p;
int i = 0;
int j = 0;
while ( s2[i] ) {
switch( s2[i] ) {
case '-':
if ( i == 0 || s2[i+1] == '/0' ) {
s1[j++] = '-';
++i;
break;
}
else {
if ( (start = strchr(upper_alph, s2[i-1])) &&
(end = strchr(upper_alph, s2[i+1])) )
;
else if ( (start = strchr(lower_alph, s2[i-1])) &&
(end = strchr(lower_alph, s2[i+1])) )
;
else if ( (start = strchr(digits, s2[i-1])) &&
(end = strchr(digits, s2[i+1])) )
;
else {
fprintf(stderr, "EX3_3: Mismatched operands '%c-%c'/n",
s2[i-1], s2[i+1]);
s1[j++] = s2[i-1];
s1[j++] = s2[i++];
break;
}
p = start;
while ( p != end ) {
s1[j++] = *p;
if ( end > start )
++p;
else
--p;
}
s1[j++] = *p;
i += 2;
}
break;
default:
if ( s2[i+1] == '-' && s2[i+2] != '/0' ) {
++i;
}
else {
s1[j++] = s2[i++];
}
break;
}
}
s1[j] = s2[i];
}
Exercise 3-4
In a two's complement number representation, our version of itoa does not handle the largest negative number, that is, the value of n equal to -(2 to the power (wordsize - 1)) . Explain why not. Modify it to print that value correctly regardless of the machine on which it runs.
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>
void itoa2(int n, char s[]);
void reverse(char s[]);
int main(void) {
char buffer[20];
printf("INT_MIN: %d/n", INT_MIN);
itoa2(INT_MIN, buffer);
printf("Buffer : %s/n", buffer);
return 0;
}
void itoa2(int n, char s[]) {
int i, sign;
sign = n;
i = 0;
do {
s[i++] = abs(n % 10) + '0';
} while ( n /= 10 );
if (sign < 0)
s[i++] = '-';
s[i] = '/0';
reverse(s);
}
void reverse(char s[]) {
int c, i, j;
for ( i = 0, j = strlen(s)-1; i < j; i++, j--) {
c = s[i];
s[i] = s[j];
s[j] = c;
}
}
Exercise 3-5
Write the function itob(n,s,b) that converts the integer n into a base b character representation in the string s . In particular, itob(n,s,16) formats n as a hexadecimal integer in s .
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
void itob(int n, char s[], int b);
void reverse(char s[]);
int main(void) {
char buffer[10];
int i;
for ( i = 2; i <= 20; ++i ) {
itob(255, buffer, i);
printf("Decimal 255 in base %-2d : %s/n", i, buffer);
}
return 0;
}
void itob(int n, char s[], int b) {
static char digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int i, sign;
if ( b < 2 || b > 36 ) {
fprintf(stderr, "EX3_5: Cannot support base %d/n", b);
exit(EXIT_FAILURE);
}
if ((sign = n) < 0)
n = -n;
i = 0;
do {
s[i++] = digits[abs(n % b)];
} while ((n /= b));
if (sign < 0)
s[i++] = '-';
s[i] = '/0';
reverse(s);
}
void reverse(char s[]) {
int c, i, j;
for ( i = 0, j = strlen(s)-1; i < j; i++, j--) {
c = s[i];
s[i] = s[j];
s[j] = c;
}
}
Exercise 3-6
Write a version of itoa that accepts three arguments instead of two. The third argument is a minimum field width; the converted number must be padded with blanks on the left if necessary to make it wide enough.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define MAX_LEN 64
void itoa3(int n, char s[], int width);
void reverse(char s[]);
int main(void) {
char buffer[MAX_LEN];
itoa3(INT_MIN, buffer,30);
printf("Buffer:%s/n", buffer);
return 0;
}
void itoa3(int n, char s[], int width) {
int i, sign;
if ((sign = n) < 0)
n = -n;
i = 0;
do {
s[i++] = abs(n % 10) + '0';
} while ((n /= 10));
if (sign < 0)
s[i++] = '-';
while (i < width )
s[i++] = ' ';
s[i] = '/0';
reverse(s);
}
void reverse(char s[]) {
int c, i, j;
for ( i = 0, j = strlen(s)-1; i < j; i++, j--) {
c = s[i];
s[i] = s[j];
s[j] = c;
}
}
![GridView終極用法(一)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)