280 Intermediate C Programming
i f ( argc < 4)11
{12
return EXIT _FAILUR E ;13
}14
Pers o nDatab ase * perdb = Perso n_read ( argv [1]) ;15
i f ( perdb == NULL )16
{17
return EXIT _FAILUR E ;18
}19
// Pe rson_pr i nt ( perdb );20
Pers on_so rtByN ame ( perdb );21
// Pe rson_pr i nt ( perdb );22
i f ( Pe rson_wr ite ( argv [2] , perdb ) == 0)23
{24
Pers on_des truct ( perdb ) ;25
return EXIT _FAILUR E ;26
}27
Pers on_so r tByAg e ( perdb ) ;28
// Pe rson_pr i nt ( perdb );29
i f ( Pe rson_wr ite ( argv [3] , perdb ) == 0)30
{31
Pers on_des truct ( perdb ) ;32
return EXIT _FAILUR E ;33
}34
Pers on_des truct ( perdb ) ;35
return EXIT _SUCCES S ;36
}37
The example introduces a new way to debug a program. The intended output should
be a file on a disk. The sorted Person database can be printed to the computer screen
by using a pre-defined FILE pointer called stdout. It means “standard output”. You do
not (and cannot) fopen this pre-defined pointer. It already exists whenever any program
runs. Writing to stdout is precisely what printf does. So you have already been using
stdout since your first C program. The functions Person
print and Person write both
call Person writeHelp, which writes the database to a file. Passing stdout means that the
database is written to the terminal.
This is an example of the DRY (Don’t Repeat Yourself) principle. Here we reuse the
same code for saving the data to a file and for printing the same data to the computer screen.
If something is wrong with Person writeHelp or the format of the data needs changes, then
you only need to make changes in one place. This saves a lot of time and reduces the chance
of mistakes. The DRY principle is a characteristic of well written code.
The program calls qsort, passing the array of Person * pointers—each element of the
array is a pointer to a Person object. Therefore, each item’s size is sizeof(Person *). The
two comparison functions, comparebyName and comparebyAge, need some careful thought.
Each argument is the address of an array element. Each element, in turn, is a pointer to a
Person object, i.e., Person *. Thus, the arguments to the comparison functions are pointers
to Person *, i.e., Person * *. A pointer stores a memory address. One of those * simply
means it is a pointer. The rest, Person *, is what is being pointed to. The two arguments
pp1 and pp2 in the comparison functions are Person * *. Inside each function pv1 and
pv2 are the pointers to Person objects, i.e., Person *. Please notice that * has different
meanings in the following statement:
Programming Problems Using Structure 281
const Person const * pv1 = * pp1 ;1
Table 4.1 summarizes the different ways of using *. In this statement, the first * means that
pv1 is a pointer. The second * means dereferencing pp1. Dereferencing a pointer means
going to the address stored in pp1, and retrieving the value stored at that address. Since
pp1 is the address of another pointer (pp1 is the address of an address), pp1’s value is also
an address; * pp1 is a pointer and this address is assigned to pv1. For pv1, the names
and ages are obtained by using pv1 -> name and pv1 -> age. Please read this program
carefully and fully understand the reasons and the purposes for each *.
17.2 Packing Decimal Digits
17.2.1 Number Systems
The minimum unit of information in a computer is called a bit. One bit can have two
possible values: 0 or 1. A sequence of bits can be used to represent a binary number, a
number in base 2. This is a binary system. We usually think of numbers in base ten, a
decimal system. In base ten we form numbers with ten different values: 0, 1, 2, 3, 4, 5, 6,
7, 8, 9. What does 2783 mean in the decimal system? Two thousands + seven hundreds +
eight tens + three:
2 × 10
3
+ 7 × 10
2
+ 8 × 10 + 3 × 10
0
(17.1)
How does this relate to the binary systems? The number binary 10110 means:
1 × 2
4
+ 1 × 2
2
+ 1 × 2
1
+ 0 × 2
0
(17.2)
Another commonly used number system is the hexadecimal system. Hexadecimal num-
bers are in base sixteen, and thus require sixteen symbols: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B,
C, D, E, F. What does EA29 mean in the hexadecimal system? It means
E × 16
3
+ A × 16
2
+ 2 × 16
1
+ 9 × 16
0
(17.3)
In C programs, hexadecimal numbers start with 0x (or 0X), for example, 0xAC, 0x9B, and
0x15. Sixteen is the fourth power of two and one hexadecimal digit can express a binary
number that is four bits long. A decimal number requires four bits. Table 17.1 shows the
relationships between the three different number systems.
In general, if a number system is base n, n symbols are allowed: zero, one, two, ..., n −1.
A number a
m
a
m−1
a
m−2
...a
1
a
0
means
a
m
× n
m
+ a
m−1
× n
m−1
+ a
m−2
× n
m−2
+ ... + a
1
× n
1
+ a
0
× n
0
(17.4)
How to convert between number systems? If a decimal number is 273, what is the binary
representation? 273 = 256 + 16 + 1 = 2
8
+ 2
4
+ 1. Therefore, 273
d
= 100010001
b
. Here,
the subscripts
d
and
b
indicate the numbers are decimal and binary respectively.
In C programs, the minimum size of a variable is one byte (8 bits) and its type is
unsigned char. The valid decimal values for unsigned char are 0 through 255, inclusively.
It is not possible to have a one-bit variable in C programs. Also, C does not allow for the
expression of binary numbers. For example, 10100110
b
is expressed as 0xA6 and 11001011
b
is expressed as 0xCB. Binary numbers may be used with gcc by prefixing 0b. For example,
282 Intermediate C Programming
Decimal Binary Hexadecimal
0 0 0
1 1 1
2 10 2
3 11 3
4 100 4
5 101 5
6 110 6
7 111 7
8 1000 8
9 1001 9
10 1010 A
11 1011 B
12 1100 C
13 1101 D
14 1110 E
15 1111 F
16 10000 10
17 10001 11
18 10010 12
19 10011 13
TABLE 17.1: Different number systems.
0b1010 is the number 10. This is an extension to normal C, and may not work in other
compilers. Instead, binary numbers should be expressed as hexadecimal numbers.
17.2.2 Packing Two Decimal Digits into One Byte
ASCII uses 8 bits (i.e., one byte) to store characters. This is inefficient if only decimal
digits (0, 1, 2, ..., 9) are needed. Only 4 bits are necessary for storing a single decimal digit.
This problem asks you to implement a structure called DecPack, which packs two decimal
digits into one single byte (unsigned char). Each DecPack object has three attributes:
• size: the maximum number of decimal digits that can be stored in a DecPack object.
• used: the actual number of decimal digits that are stored in a DecPack object.
• data: an array of unsigned char. Each element stores two decimal digits. The upper
(i.e., left) 4 bits stores one decimal digit and the lower (i.e., right) 4 bits stores another
decimal digit. If the attribute size is an even number, the size of the array should
be size / 2. If the attribute size is an odd number, the size of the array should
be (size + 1) / 2.
The following diagram shows a graphical view of a byte in the DecPack data structure.
Each byte contains two decimal digits:
upper (left) 4 bits lower (right) 4 bits
When inserting a decimal digit using DecPack insert, the function checks whether data
is full. If it is full, then the size of the data array doubles. The old array is copied to the
new array and the memory for the old array is released. If a byte has not been used, then
the decimal digit uses the upper 4 bits. If the upper 4 bits of a byte are already used, the
decimal digit uses the lower 4 bits. When deleting a decimal digit using DecPack delete,
the function modifies used and returns the most recently inserted decimal digit. The digit’s
Programming Problems Using Structure 283
value must be between 0 and 9 (not ’0’ to ’9’). DecPack delete does not shrink the data
array even if used is zero. The DecPack print function prints the decimal digits stored in
the object. The printed decimal digits should be between ’0’ and ’9’—if the decimal digit
is 0, then ’0’ is printed, if the decimal digit is 1, then ’1’ is printed, and so on. Finally,
DecPack destroy releases the memory.
17.2.3 Bit Operations
C provides a variety of ways to directly manipulate the bits in a byte, including:
operation operator
bit-wise AND &
bit-wise OR |
shift left <<
shift right >>
exclusive or (XOR) ∧
The bit-wise AND operation is used between two numbers. If the bits from both numbers
are 1, the resultant bit is 1. If one or both bits are zero, then the resultant bit is zero. The
following shows some examples (in binary representation).
0 1 1 0 1 0 0 1
& 1 1 0 1 0 0 1 1
0 1 0 0 0 0 0 1
Sometimes, a program wants to keep some bits while discarding the other bits. For
example, if the program wants to keep only the lower (right) four bits of a byte, then the
program uses bit-wise AND with 0x0F, 0000 1111 in binary.
- - - - a b c d
& 0 0 0 0 1 1 1 1
0 0 0 0 a b c d
It does not matter whether - is 0 or 1, the first (higher, left) four bits of the result will
always be 0. The other four bits: a, b, c, d are either 0 or 1 depending on the values of
a, b, c, and d. This is also called a mask. A mask blocks some bits and allows the other
bits to pass through. If a program wants to check if the leftmost bit is 1 or 0, then it can
use a mask whose binary representation is 1000 0000
b
(0x80 in hexadecimal). The following
example checks whether the variable a’s leftmost bit is 1 or 0:
unsigned char a = 161;1
unsigned char mask = 0 x80 ;2
i f (( a & mask ) == mask )3
{4
// a ’s leftmost bit is 15
}6
e l s e7
{8
// a ’s leftmost bit is 09
}10
In this example, a & mask equals mask because 161 is greater than 127 and the leftmost
bit must be set to 1. Please note that the following if condition is wrong. It is a common
mistake.
284 Intermediate C Programming
unsigned char a = 161;1
unsigned char mask = 0 x80 ;2
i f (( a & mask ) == 1)3
{4
// a ’s leftmost bit is 15
}6
e l s e7
{8
// a ’s leftmost bit is 09
}10
Why is this wrong? If a’s leftmost bit is 1, a & mask equals 128, not 1.
The bit-wise AND operator & is useful for masking numbers—setting some bits to zero,
while leaving others unaffected. The bit-wise OR operation is also used between two num-
bers. If the bit from either number is 1, the resultant bit is 1. If both are zero, then the
resultant bit is zero. Here is an example:
0 1 1 0 1 0 0 1
| 1 1 0 1 0 0 0 0
1 1 1 1 1 0 0 1
The bit-wise shift left operation moves bits to the left and adds zeros to the right. The
following example shows left-shifting by two. The leftmost two bits are discarded (marked
as -) and two zeros are added to the right:
0 1 1 0 1 0 0 1 << 2
- - 1 0 1 0 0 1 0 0
The next example shows shifting left by four. The leftmost four bits are discarded
(marked as -) and four zeros are added to the right:
1 1 0 1 1 1 1 0 << 4
- - - - 1 1 1 0 0 0 0 0
Shifting left by one is equivalent to multiplying by two. If the result is greater than 255,
then the leftmost bit is discarded.
The bit-wise shift left operation has a complementary bit-wise shift right operation,
moving bits to the right and adding zeros to the left. The following shows an example of
shifting right by two. The rightmost two bits are discarded (marked as -) and two zeros are
added to the left.
0 1 1 0 1 0 0 1 >> 2
0 0 0 1 1 0 1 0 - -
The next example shows shifting right by four. The rightmost four bits are discarded
(marked as -) and four zeros are added to the right.
1 1 0 1 1 1 1 0 >> 4
0 0 0 0 1 1 0 1 - - - -
Shifting right by one is equivalent to division by two.
The following program shows how to use bit-wise operations:
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.