Programming Problems Using Structure 285
// bits . c1
# inc lude < stdio .h >2
# inc lude < stdlib .h >3
# inc lude < string .h >4
int main ( i nt argc , char * * argv )5
{6
unsigned char a = 129; // decimal 129 , he xadecima l 0 X817
unsigned char b = 0 XF0 ; // decimal 2408
unsigned char c = a & b ; // h exadecim a l 0 X80 , decimal 1289
printf (" %d , %X n" , c , c ); // 128 , 8010
unsigned char d = a | b ; // h exadecim a l 0 XF1 , decimal 24111
printf (" %d , %X n" , d , d ); // 241 , F112
unsigned char e = d << 3; // he xadecima l 0 X88 , decimal 13613
printf (" %d , %X n" , e , e ); // 136 , 8814
unsigned char f = d >> 2; // he xadecima l 0 X3C , decimal 6015
printf (" %d , %X n" , f , f ); // 60, 3C16
return EXIT _SUCCES S ;17
}18
The output of this program is:
128, 80
241, F1
136, 88
60, 3C
The final bit-wise operation that we will consider is the exclusive or operation, often
abbreviated as XOR. With XOR, the resulting bit is 1 if and only if the two input bits are
different from each other. Here is an illustrative example:
0 1 1 0 1 0 0 1
∧ 1 1 0 1 0 0 0 0
1 0 1 1 1 0 0 1
Please note that ∧ means exclusive or (XOR) in C programs. In some other languages, ∧
means exponential. C uses exp for exponential.
17.2.4 Inserting and Retrieving Decimal Digits
In DecPack, a decimal digital (0 to 9) requires only 4 bits. Thus, to put this digital into
the upper 4 bits, it needs to be shifted left by 4; 4 zeros will be added to the right 4 bits.
To retrieve one decimal digit from the upper 4 bits, the byte is shifted right by 4 bits; 4
zeros will be added to the left 4 bits. To put one decimal digital into the lower 4 bits, it can
be added to the byte. To retrieve one decimal digital from the lower 4 bits, a mask 0x0F is
used to block the upper 4 bits.
The indexes need to be carefully managed. The value of used means the number of
digits that have been already inserted. If used is an even number (for example, 8), then the
next inserted digit should be the 9
th
digit. In C programs, array indexes start from 0. The
9
th
digit uses the 5
th
byte and the index should be 4. The index is 8 / 2 (integer division).
Thus, used / 2 is the correct index. If used is an odd number (for example, 11), then the
next inserted digit is the 12
th
digit. It should be the 6
th
byte and the index is 5; used / 2
is also the correct index. Thus, used / 2 is the correct index for insertion; used should be
incremented after insertion.
286 Intermediate C Programming
When deleting a digit, used should decrement before the retrieval. Aside from being
symmetric to insertion, this can be understood by working through some examples. Suppose
used is an even number, say 12, then six bytes are used. The last digit is at the 6
th
byte
and the index is 5. If used decrements first, it becomes 11 and used / 2 is 5. If used is an
odd number, say 9, then we are using five bytes. The last digit is at the 5
th
byte and the
index is 4. If used decrements first, it becomes 8 and used / 2 is 4. In both cases, used
should decrement before deletion.
17.2.5 DecPack Program
The header file decpack.h is listed below:
// decpack .h1
#i f n d e f DECPACK_H2
#d ef in e DECPACK_ H3
typedef s t ru ct4
{5
int size ; // how many digits can be stored6
int used ; // how many digits are actua l l y stored7
unsigned char * data ; // store the digits8
// size should be 2 * the a c tually al l ocated memory becau s e9
// each byte can store two digits10
} DecPack ;11
// create a DecPack object with the given size12
DecPack * DecPa ck_cre ate ( in t sz );13
// Insert a decimal value into the DecPack object . The new14
// value is at the end of the array15
void DecPa ck_ins ert ( DecPack * dp , i n t val ) ;16
// delete and return the last value in the D e c P a c k object17
// do not shrink the data array even if nothing is stored18
// The return e d value should be b e t w e e n 0 and 919
// return -1 if no digit can be deleted20
int DecPa ck_del ete ( DecPack * dp ) ;21
// print the values stored in the object , the first inserted22
// value should be printed first23
// the printed values are between ’0 ’ and ’9’24
void DecPa ck_prin t ( DecPack * dp );25
// destroy the whole DecPack object , release all memory26
void DecP a ck_de stroy ( DecPack * dp ) ;27
#e ndif28
Here are sample implementations of the functions in decpack.c:
// decpack .c1
# inc lude < stdio .h >2
# inc lude < stdlib .h >3
# inc lude < string .h >4
# inc lude " decpack .h "5
DecPack * DecPa ck_cre ate ( in t sz )6
{7
// allocat e memory for DecPack8
DecPack * dp = malloc ( s i z e o f ( D e c P a c k ) ) ;9
Programming Problems Using Structure 287
// check whether allocation fails10
i f ( dp == NULL )11
{12
return NULL ;13
}14
// ini tialize size to sz and used to 015
dp -> size = sz ;16
dp -> used = 0;17
// allocat e memory for data , should be only sz /2 because18
// each byte can store two digits19
20
// if sz is odd , increm ent sz by one21
i f (( sz % 2) == 1) { sz ++; }22
dp -> data = malloc ( s i z e o f ( unsigned char ) * ( sz / 2) );23
// check whether allocation fails24
i f ( dp -> data == NULL )25
{26
free ( dp ) ;27
return NULL ;28
}29
// return the a l l ocate memory30
return dp;31
}32
void DecPa ck_ins ert ( DecPack * dp , i n t val )33
{34
// if the object is empty , do nothing35
i f ( dp == NULL ) { return ; }36
37
// if val < 0 or val > 9, ignore and do nothing38
i f (( val < 0) || ( val > 9) ) { return ; }39
40
// If the allocated memory is full , double the size ,41
// allocat e memory for the new size , copy the data ,42
// and insert the new value43
int used = dp -> used ;44
i f ( used == dp -> size )45
{46
unsigned char * newdata =47
malloc ( s i z e o f ( unsigned char ) * ( dp -> size )) ;48
int iter ;49
for ( iter = 0; iter < used ; iter ++)50
{51
newdata [ iter / 2] = dp -> data [ iter / 2];52
}53
( dp -> size ) *= 2;54
free ( dp -> data );55
dp -> data = newdata ;56
}57
// If used is an even number , the inserted value should58
// use the upper ( left ) 4 bits .59
// If used is an odd number , the inserted value should60
288 Intermediate C Programming
// use the lower ( right ) 4 bits .61
//62
// careful : do not lose the data already stored in DecPack63
i f (( used % 2) == 0)64
{65
// shiftin g left adds zeros for the lower bits66
dp -> data [ used / 2] = ( val << 4);67
}68
e l s e69
{70
// reset the lower four bits , may be left from delete71
unsigned char upper = dp -> data [ used / 2] & 0 XF0 ;72
dp -> data [ used / 2] = upper + val ;73
}74
( dp -> used ) ++;75
}76
int DecPa ck_del ete ( DecPack * dp )77
{78
// if the object is empty , do nothing79
i f ( dp == NULL ) { return -1; }80
// return -1 if the DecPack object stores no data81
i f (( dp -> used ) == 0) { return -1; }82
// If used is even , the returned value is the upper83
// ( left ) 4 bits . Make sure the r eturned value is between84
// 0 and 9. If used is odd , the returned value is the85
// lower ( right ) 4 bits . Make sure the returned value86
// is between 0 and 9.87
int val ;88
// decr e ment the used attribut e in the DecPack object89
( dp -> used ) - -;90
int used = dp -> used ;91
i f (( used % 2) == 0)92
{93
val = dp -> data [ used / 2] >> 4;94
}95
e l s e96
{97
val = ( dp -> data [ used / 2]) & 0 X0F ;98
}99
// return the value100
return val ;101
}102
void DecPa ck_prin t ( DecPack * dp )103
{104
// if the object is empty , do nothing105
i f ( dp == NULL ) { return ; }106
int iter ;107
int used = dp -> used ;108
109
// go through every value stored in the data attrib u te110
for ( iter = 0; iter < used ; iter ++)111
Programming Problems Using Structure 289
{112
i f (( iter % 2) == 0)113
{114
printf (" %d" , ( dp - > data [ iter / 2] >> 4) ) ;115
}116
e l s e117
{118
printf (" %d" , ( dp - > data [ iter / 2] & 0 X0F ) );119
}120
}121
printf (" n" );122
}123
void DecP a ck_de stroy ( DecPack * dp )124
{125
// if the object is empty , do nothing126
i f ( dp == NULL ) { return ; }127
// release the memory for the data128
free ( dp -> data );129
// release the memory for the object130
free ( dp ) ;131
}132
This is the main function:
// main . c1
#in clude < stdio .h >2
#in clude < stdlib .h >3
#in clude " decpack . h"4
int main ( i nt argc , char * * argv )5
{6
DecPack * dp = DecP ack_cr eate (5) ;7
int iter ;8
for ( iter = 0; iter < 21 ; iter ++)9
{10
DecP a ck_ins ert ( dp , iter % 10) ;11
}12
DecPa ck_pri n t ( dp ) ;13
for ( iter = 0; iter < 7 ; iter ++)14
{15
printf (" delete % dn " , D ecPack _delet e ( dp )) ;16
}17
DecPa ck_pri n t ( dp ) ;18
for ( iter = 0; iter < 6 ; iter ++)19
{20
DecP a ck_ins ert ( dp , iter % 10) ;21
}22
DecPa ck_pri n t ( dp ) ;23
for ( iter = 0; iter < 6 ; iter ++)24
{25
printf (" delete % dn " , D ecPack _delet e ( dp )) ;26
}27
DecPa ck_pri n t ( dp ) ;28
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.