#include <stdio.h> // for printf(), scanf()
#define SIZE 100 // array size
int strLen(char []); // strlen() is declared in string.h, included by stdio.h
// sort v[0] ... v[n-1] into increasing order
void shellsort(char v[], int n);
int main()
{
char array[SIZE];
printf("Type a word: ");
scanf("%s", array);
shellsort(array, strLen(array));
printf("Sorted: %s\n", array);
return 0;
}
int strLen(char s[])
{
int i = 0;
while (s[i] != '\0')
{i++;}
return i;
}
// sort v[0] ... v[n-1] into increasing order
void shellsort(char v[], int n)
{
int gap, i, j, temp;
for (gap = n/2; gap > 0; gap /= 2)
{
for (i = gap; i < n; i++)
{
for (j = i-gap; j >= 0 && v[j] > v[j+gap]; j -= gap)
{ // interchange v[j], v[j+gap] using a temporary variable
temp = v[j];
v[j] = v[j+gap];
v[j+gap] = temp;
}
}
}
}
/*
gcc shellc.c -o shellc
./shellc
Type a word: abracadabra
Sorted: aaaaabbcdrr
./shellc
Type a word: hocus-pocus
Sorted: -cchoopssuu
*/
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
#include <stdio.h> // for printf()
#define SIZE 100 // array size
#define SEED 24 // seed for rand()
unsigned long int next = 1; // global var used by rand()
int rand(void); // pseudo-random number generator
void srand(unsigned int seed); // set seed for rand()
// sort v[0] ... v[n-1] into increasing order
void shellsort(int v[], int n);
void printArray(int arr[], int n);
int main()
{
int array[SIZE];
int i;
srand(SEED);
for (i = 0; i < SIZE; i++)
{array[i] = rand();}
printf("Unsorted:\n");
printArray(array, SIZE);
shellsort(array, SIZE);
printf("\nSorted:\n");
printArray(array, SIZE);
return 0;
}
// return pseudo-random integer on 0..32767
int rand(void)
{
next = next * 1103515245 + 12345;
return (unsigned int)(next / 65536) % 32768;
}
void srand(unsigned int seed)
{
next = seed; // set seed for rand()
}
// sort v[0] ... v[n-1] into increasing order
void shellsort(int v[], int n)
{
int gap, i, j, temp;
for (gap = n/2; gap > 0; gap /= 2)
{
for (i = gap; i < n; i++)
{
for (j = i-gap; j >= 0 && v[j] > v[j+gap]; j -= gap)
{ // interchange v[j], v[j+gap] using a temporary variable
temp = v[j];
v[j] = v[j+gap];
v[j+gap] = temp;
}
}
}
}
void printArray(int arr[], int n)
{
int i;
for (i = 0; i < n; i++)
{
printf("%d%c", arr[i], ((i % 10) == 9) || (i == n-1) ? '\n' : ' ');
}
}
/*
gcc shelli.c -o shelli
./shelli
Unsorted:
10903 4890 13005 9985 9417 7879 19373 18922 11980 2947
13349 11897 22310 32244 26256 22527 21518 3349 24032 10771
11943 29378 26935 2553 26106 14595 7494 10959 17846 28696
32614 28797 27815 14664 18040 5466 16118 12906 19837 32415
16422 3632 5108 27532 4298 25911 26615 27484 3078 3023
5652 17897 16589 30858 15084 17183 17108 1926 4750 32034
3928 9850 24977 10559 405 13699 21491 916 4865 10412
28085 18814 25421 13887 26930 28357 17433 7630 8003 31113
17529 21504 21780 12524 30764 7965 3013 2685 30358 28759
11712 615 19843 1502 13789 19038 25498 8610 11319 31557
Sorted:
405 615 916 1502 1926 2553 2685 2947 3013 3023
3078 3349 3632 3928 4298 4750 4865 4890 5108 5466
5652 7494 7630 7879 7965 8003 8610 9417 9850 9985
10412 10559 10771 10903 10959 11319 11712 11897 11943 11980
12524 12906 13005 13349 13699 13789 13887 14595 14664 15084
16118 16422 16589 17108 17183 17433 17529 17846 17897 18040
18814 18922 19038 19373 19837 19843 21491 21504 21518 21780
22310 22527 24032 24977 25421 25498 25911 26106 26256 26615
26930 26935 27484 27532 27815 28085 28357 28696 28759 28797
29378 30358 30764 30858 31113 31557 32034 32244 32415 32614
*/
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
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 ho handle cases like a-b-c, a-z0-9, and -a-z. Arrange that a leading or trailing - is taken literally.
#include <stdio.h> // for printf(), scanf()
#define SIZE 100 // array size
void expand(char [], char []); // expand a-z A-Z 0-9
int main()
{
char s1[SIZE], s2[SIZE*10];
printf("Type a word with unexpanded sequences like a-z A-Z 0-9:\n");
scanf("%s", s1);
expand(s1, s2);
printf("%s\n", s2);
return 0;
}
void expand(char s[], char t[]) // expand a-z A-Z 0-9
{
int i, j = 0, k;
for (i = 0; s[i] != '\0'; i++)
{
if (s[i] == '-')
{
if (i > 0 && s[i-1] >= '0' && s[i-1] <= '9' && s[i+1] > s[i-1] && s[i+1] <= '9')
{
for (k = s[i-1]+1; k <= s[i+1]; k++)
{t[j++] = k;}
i++;
}
else if (i > 0 && s[i-1] >= 'a' && s[i-1] <= 'z' && s[i+1] > s[i-1] && s[i+1] <= 'z')
{
for (k = s[i-1]+1; k <= s[i+1]; k++)
{t[j++] = k;}
i++;
}
else if (i > 0 && s[i-1] >= 'A' && s[i-1] <= 'Z' && s[i+1] > s[i-1] && s[i+1] <= 'Z')
{
for (k = s[i-1]+1; k <= s[i+1]; k++)
{t[j++] = k;}
i++;
}
else {t[j++] = s[i];}
}
else {t[j++] = s[i];}
}
t[j] = '\0';
}
/*
gcc expand.c -o expand
./expand
-a-t+A-f+a-G+A-B-A-C+Z-T+1-8-
-abcdefghijklmnopqrst+A-f+a-G+AB-ABC+Z-T+12345678-
*/
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
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 INT_MIN, -2^(wordsize-1). Explain why not. Modify it to print that value correctly, regardless of the machine on which it runs.
#include <stdio.h> // for printf(), scanf()
#define SIZE 100 // array size (max no of digits)
// reverse s[], knowing its length:
void reverse(char s[], int len);
int itoa (int , char []); // int to string of chars
int main()
{
char digits[SIZE];
int n;
printf ("Give an integer: ");
scanf ("%d", &n);
itoa(n, digits);
printf ("%s\n", digits); // with an eventual sign
return 0;
}
// reverse s[], knowing its length:
void reverse(char s[], int len)
{
int i = 0, j = len-1;
char temp;
while (i < j)
{
temp = s[i];
s[i] = s[j];
s[j] = temp;
i++;
j--;
}
}
// get the digits of n into s[] (convert n to a string of characters),
// return the length of s[] (no of digits, plus an eventual sign):
int itoa (int n, char s[])
{
int i = 0, sign = 1;
if (n < 0)
{
sign = -1;
}
do
{ // get the digits in reverse order:
s[i++] = (n % 10)*sign + '0'; // get next (last read) digit
// if n < 0, (n /= 10) <= 0, (n % 10) < 0
} while (n /= 10); // while ((n /= 10) != 0); // delete last digit
if (sign < 0) {s[i++] = '-';} // first char after reverse
s[i] = '\0'; // end the string
reverse(s, i);
return i;
}
/*
gcc itoa.c -o itoa
./itoa
Give an integer: 0
0
./itoa
Give an integer: -1
-1
./itoa
Give an integer: 123
123
./itoa
Give an integer: -125
-125
./itoa
Give an integer: -2147483647 // INT_MIN+1
-2147483647
./itoa
Give an integer: -2147483648 // INT_MIN
-2147483648
./itoa
Give an integer: -2147483649 // INT_MIN-1
2147483647 // INT_MAX (underflow)
./itoa
Give an integer: -2147483650 // INT_MIN-2
2147483646 // INT_MAX-1 (modulo 2 arithmetic)
./itoa
Give an integer: 2147483647 // INT_MAX
2147483647
./itoa
Give an integer: 2147483648 // INT_MAX+1
-2147483648 // INT_MIN (overflow)
./itoa
Give an integer: 2147483649 // INT_MAX+2
-2147483647 // INT_MIN+1
*/
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
#include <stdio.h> // for printf(), scanf()
#define SIZE 100 // array size (max no of digits)
// reverse s, knowing its length:
void reverse(char s[], int len);
int utoa (unsigned , char []); // unsigned to string of chars
int main()
{
char digits[SIZE];
unsigned n;
printf ("Give an unsigned integer: ");
scanf ("%u", &n);
utoa(n, digits);
printf ("utoa(%u) = %s\n", n, digits);
return 0;
}
// reverse s, knowing its length:
void reverse(char s[], int len)
{
char temp;
int start = 0, end = len-1; // last position before '\0'
while (start < end)
{
temp = s[start];
s[start] = s[end];
s[end] = temp;
start++;
end--;
}
}
// get the digits of n into s[] (convert n to a string of characters),
// return the length of s[] (no of digits):
int utoa (unsigned n, char s[])
{
int len = 0; // length of s[]
do
{ // get the digits in reverse order:
s[len++] = (n % 10) + '0'; // get next (last read) digit
} while (n /= 10); // while ((n /= 10) > 0); // delete last digit
s[len] = '\0'; // end the string
reverse(s, len);
return len;
}
/*
gcc utoa.c -o utoa
./utoa
Give an unsigned integer: 0
utoa(0) = 0
./utoa
Give an unsigned integer: -0
utoa(0) = 0
./utoa
Give an unsigned integer: +0
utoa(0) = 0
./utoa
Give an unsigned integer: 1
utoa(1) = 1
./utoa
Give an unsigned integer: +123
utoa(123) = 123
./utoa
Give an unsigned integer: -1 (underflow - scanf() makes the conversion)
utoa(4294967295) = 4294967295 // UINT_MAX (limits.h)
./utoa
Give an unsigned integer: -2
utoa(4294967294) = 4294967294 // UINT_MAX-1 (modulo 2 arithmetic)
./utoa
Give an unsigned integer: 4294967295 // UINT_MAX
utoa(4294967295) = 4294967295
./utoa
Give an unsigned integer: 4294967296 // UINT_MAX + 1 (overflow)
utoa(0) = 0 // (modulo 2 arithmetic - scanf() makes the conversion)
./utoa
Give an unsigned integer: 4294967297 // UINT_MAX + 2
utoa(1) = 1 // (modulo 2 arithmetic)
*/
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
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 the string s.
#include <stdio.h> // for printf(), scanf()
#define SIZE 100 // array size (max no of digits)
// reverse s[], knowing its length:
void reverse(char s[], int len);
int itob (int n, char s[], int b); // int n to string of chars, base b
int main()
{
char digits[SIZE];
int n, base;
printf ("Give an integer: ");
scanf ("%d", &n);
printf ("Convert to base (2 <= base <= 36): ");
scanf ("%d", &base); // 0..9a..z = 36 chars
if (base < 2 || base > 36)
{
printf ("2 <= base <= 36\n");
printf ("Your input: %d\n", base);
return 1; // end program with an error message
}
itob(n, digits, base);
printf ("In base %d: %s\n", base, digits); // with an eventual sign
return 0;
}
// reverse s[], knowing its length:
void reverse(char s[], int len)
{
int i = 0, j = len-1;
char temp;
while (i < j)
{
temp = s[i];
s[i] = s[j];
s[j] = temp;
i++;
j--;
}
}
// get the digits of n into s[] (convert n to a string of characters), base b,
// return the length of s[] (no of digits, eventual sign):
int itob (int n, char s[], int b)
{ // both base b and remainder must be int, not unsigned, to prevent
// automatic conversion from int to unsigned in case n < 0
int i = 0, sign = 1;
int remainder;
if (n < 0)
{
sign = -1;
}
do
{ // get the digits in reverse order:
remainder = (n % b) * sign; // if n < 0, (n % b) < 0
// if remainder or b unsigned, n < 0 converted to large positive number
if (remainder < 10)
{s[i++] = remainder + '0';} // 0..9
else
{s[i++] = remainder - 10 + 'a';} // a..z
// if n < 0, (n /= b) <= 0
} while (n /= b); // while ((n /= b) != 0); // delete last digit
// if b unsigned, n < 0 converted to large positive (unsigned) number
if (sign < 0) {s[i++] = '-';} // first char after reverse
s[i] = '\0'; // end the string
reverse(s, i);
return i;
}
/*
gcc itob.c -o itob
./itob
Give an integer: 0
Convert to base (2 <= base <= 36): 1
2 <= base <= 36
Your input: 1
./itob
Give an integer: 1
Convert to base (2 <= base <= 36): 37
2 <= base <= 36
Your input: 37
./itob
Give an integer: 123456
Convert to base (2 <= base <= 36): 36
In base 36: 2n9c
./itob
Give an integer: -123456
Convert to base (2 <= base <= 36): 36
In base 36: -2n9c
./itob
Give an integer: 123456
Convert to base (2 <= base <= 36): 2
In base 2: 11110001001000000
./itob
Give an integer: -123456
Convert to base (2 <= base <= 36): 2
In base 2: -11110001001000000
./itob
Give an integer: 32767
Convert to base (2 <= base <= 36): 16
In base 16: 7fff
./itob
Give an integer: 32767
Convert to base (2 <= base <= 36): 8
In base 8: 77777
./itob
Give an integer: 32767
Convert to base (2 <= base <= 36): 2
In base 2: 111111111111111
*/
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
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> // for printf(), scanf()
#define SIZE 100 // array size (max no of digits)
#define WIDTH 8 // could also be 16, 32, or 64
// reverse s[], knowing its length:
void reverse(char s[], int len);
// int to string of chars, minimum field width:
int itoap (int n, char s[], unsigned width);
int main()
{
char digits[SIZE];
int n;
printf ("Give an integer: ");
scanf ("%d", &n);
itoap(n, digits, WIDTH);
printf ("%s\n", digits); // with an eventual sign
return 0;
}
// reverse s[], knowing its length:
void reverse(char s[], int len)
{
int i = 0, j = len-1;
char temp;
while (i < j)
{
temp = s[i];
s[i] = s[j];
s[j] = temp;
i++;
j--;
}
}
// get the digits of n into s[] (convert n to a string of characters),
// with a minimum field width (padded to the left if necessary),
// return length of s[] (digits, eventual sign):
int itoap (int n, char s[], unsigned width)
{
int i = 0, sign = 1, diff;
if (n < 0)
{
sign = -1;
}
do
{ // get the digits in reverse order:
s[i++] = (n % 10)*sign + '0'; // get next (last read) digit
// if n < 0, (n /= 10) <= 0, (n % 10) < 0
} while (n /= 10); // while ((n /= 10) != 0); // delete last digit
if (sign < 0) {s[i++] = '-';} // first char after reverse
diff = width-i;
while (diff > 0) // while (diff)
{
s[i++] = ' ';
diff--;
}
s[i] = '\0'; // end the string
reverse(s, i);
return i;
}
/*
gcc itoap.c -o itoap
./itoap
Give an integer: 0
0
./itoap
Give an integer: -1
-1
./itoap
Give an integer: 123
123
./itoap
Give an integer: -125
-125
./itoap
Give an integer: 1234567
1234567
./itoap
Give an integer: 12345678
12345678
./itoap
Give an integer: 123456789
123456789
./itoap
Give an integer: -123456
-123456
./itoap
Give an integer: -1234567
-1234567
./itoap
Give an integer: -12345678
-12345678
*/
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
#include <stdio.h> // for printf()
#include <string.h> // for strlen()
#define SIZE 100 // array size
void escape(char s[], char t[]); // copy t[] to s[] making escapes visible
int trim(char s[], int len); // remove beginning and trailing whitespace
int main()
{
char empty[] = " \t\r\n \t\v\f\n";
int len = strlen(empty);
char array[SIZE*2];
escape(array, empty); // empty does not change
printf("trim(\"%s\"[%d]): ", array, len);
len = trim(empty, len); // empty is trimmed
printf("\"%s\"[%d]\n", empty, len);
char nonempty[] = "\t \f \v\r\nHello \n\v\r\f \t";
len = strlen(nonempty);
escape(array, nonempty); // nonempty does not change
printf("trim(\"%s\"[%d]): ", array, len);
len = trim(nonempty, len); // nonempty is trimmed
printf("\"%s\"[%d]\n", nonempty, len);
char nowhite[] = "Hello";
len = strlen(nowhite);
escape(array, nowhite); // nowhite does not change
printf("trim(\"%s\"[%d]): ", array, len);
len = trim(nowhite, len); // nowhite is trimmed
printf("\"%s\"[%d]\n", nowhite, len);
return 0;
}
void escape(char s[], char t[]) // copy t[] to s[] making escapes visible
{
int i, j = 0;
for (i = 0; t[i] != '\0'; i++)
{
switch(t[i])
{
case '\'' :
s[j++] = '\\'; s[j++] = '\'';
break;
case '\"' :
s[j++] = '\\'; s[j++] = '\"';
break;
case '\t' :
s[j++] = '\\'; s[j++] = 't';
break;
case '\n' :
s[j++] = '\\'; s[j++] = 'n';
break;
case '\r' :
s[j++] = '\\'; s[j++] = 'r';
break;
case '\f' :
s[j++] = '\\'; s[j++] = 'f';
break;
case '\v' :
s[j++] = '\\'; s[j++] = 'v';
break;
case '\a' :
s[j++] = '\\'; s[j++] = 'a';
break;
case '\b' :
s[j++] = '\\'; s[j++] = 'b';
break;
case '\\' :
s[j++] = '\\'; s[j++] = '\\';
break;
default:
s[j++] = t[i]; // copy non-escapes
break;
}
}
s[j] = '\0'; // properly end string
}
// remove beginning and trailing whitespace
int trim(char s[], int len)
{
int n; // new length
for (n = len-1; n >= 0; n--)
{
if (s[n] != ' ' && s[n] != '\t' && s[n] != '\n' &&
s[n] != '\f' && s[n] != '\v' && s[n] != '\r')
{break;} // out of for()
// else {continue;}
}
n++; // new length after trimming trailing whitespace
s[n] = '\0';
if (n == 0) {return 0;} // return n; // empty string
int i; // here s[n-1] is not whitespace, but s[] may have beginning whitespace
for (i = 0; i < n; i++)
{
if (s[i] == ' ' || s[i] == '\t' || s[i] == '\n' ||
s[i] == '\f' || s[i] == '\v' || s[i] == '\r')
{continue;}
else {break;} // out of for()
} // i counts no of beginning whitespaces
n -= i; // n = n-i; // final length
if (i == 0) {return n;} // no beginning whitespace
int j; // here i > 0
for (j = 0; j < n; j++)
{ // shift string to the beginning, thus removing
s[j] = s[j+i]; // the beginning whitespace
}
s[j] = '\0'; // s[n] = '\0';
return n; // return j;
}
/*
gcc trim.c -o trim
./trim
trim(" \t\r\n \t\v\f\n"[10]): ""[0]
trim("\t \f \v\r\nHello \n\v\r\f \t"[19]): "Hello"[5]
trim("Hello"[5]): "Hello"[5]
*/
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
*****************************************************************************************
#include <stdio.h> // for printf()
#include <string.h> // for strlen()
#define SIZE 100 // array size
void escape(char s[], char t[]); // copy t[] to s[] making escapes visible
int trim(char s[], int len); // remove beginning and trailing whitespace
int main()
{
char empty[] = " \t\r\n \t\v\f\n";
int len = strlen(empty);
char array[SIZE*2];
escape(array, empty); // empty does not change
printf("trim(\"%s\"[%d]): ", array, len);
len = trim(empty, len); // empty is trimmed
printf("\"%s\"[%d]\n", empty, len);
char nonempty[] = "\t \f \v\r\nHello \n\v\r\f \t";
len = strlen(nonempty);
escape(array, nonempty); // nonempty does not change
printf("trim(\"%s\"[%d]): ", array, len);
len = trim(nonempty, len); // nonempty is trimmed
printf("\"%s\"[%d]\n", nonempty, len);
char nowhite[] = "Hello";
len = strlen(nowhite);
escape(array, nowhite); // nowhite does not change
printf("trim(\"%s\"[%d]): ", array, len);
len = trim(nowhite, len); // nowhite is trimmed
printf("\"%s\"[%d]\n", nowhite, len);
return 0;
}
void escape(char s[], char t[]) // copy t[] to s[] making escapes visible
{
int i, j = 0;
for (i = 0; t[i] != '\0'; i++)
{
switch(t[i])
{
case '\'' :
s[j++] = '\\'; s[j++] = '\'';
break;
case '\"' :
s[j++] = '\\'; s[j++] = '\"';
break;
case '\t' :
s[j++] = '\\'; s[j++] = 't';
break;
case '\n' :
s[j++] = '\\'; s[j++] = 'n';
break;
case '\r' :
s[j++] = '\\'; s[j++] = 'r';
break;
case '\f' :
s[j++] = '\\'; s[j++] = 'f';
break;
case '\v' :
s[j++] = '\\'; s[j++] = 'v';
break;
case '\a' :
s[j++] = '\\'; s[j++] = 'a';
break;
case '\b' :
s[j++] = '\\'; s[j++] = 'b';
break;
case '\\' :
s[j++] = '\\'; s[j++] = '\\';
break;
default:
s[j++] = t[i]; // copy non-escapes
break;
}
}
s[j] = '\0'; // properly end string
}
// remove beginning and trailing whitespace
int trim(char s[], int len)
{
int n; // new length
for (n = len-1; n >= 0; n--)
{
switch (s[n])
{
case ' ' : case '\t' : case '\n' :
case '\f' : case '\v' : case '\r' :
break; // continue; // go to next for() iteration
default:
goto out1; // break would just exit switch() and continue
} // with the next for() iteration
}
out1: // first label for goto
n++; // new length after trimming trailing whitespace
s[n] = '\0';
if (n == 0) {return 0;} // return n; // empty string
int i; // here s[n-1] is not whitespace, but s[] may have beginning whitespace
for (i = 0; i < n; i++)
{
switch (s[i])
{
case ' ' : case '\t' : case '\n' :
case '\f' : case '\v' : case '\r' :
break; // continue; // go to next for() iteration
default:
goto out2; // break would just exit switch() and continue
} // with the next for() iteration
}
out2: // second label for goto
// i counts no of beginning whitespaces
n -= i; // n = n-i; // final length
if (i == 0) {return n;} // no beginning whitespace
int j; // here i > 0
for (j = 0; j < n; j++)
{ // shift string to the beginning, thus removing
s[j] = s[j+i]; // the beginning whitespace
}
s[j] = '\0'; // s[n] = '\0';
return n; // return j;
}
/*
gcc trimg.c -o trimg
./trimg
trim(" \t\r\n \t\v\f\n"[10]): ""[0]
trim("\t \f \v\r\nHello \n\v\r\f \t"[19]): "Hello"[5]
trim("Hello"[5]): "Hello"[5]
*/