Chapter 9
Programming Problems Using Heap
Memory
9.1 Sorting an Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
9.1.1 Generating Test Input and Expected Output . . . . . . . . . . . . . . . . . . . . . . . . . 125
9.1.2 Redirecting Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
9.1.3 Sorting Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
9.1.4 Using valgrind to Detect Memory Leaks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
9.2 Sort Using qsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
9.2.1 qsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
9.2.2 The Comparison Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
9.2.3 Execution Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
9.2.4 Sorting Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
9.1 Sorting an Array
This problem asks you to write a program that reads integers from a file, sorts the
numbers, and writes the sorted numbers out to another file.
9.1.1 Generating Test Input and Expected Output
The previous chapter explained why testing does not guarantee that a program is correct:
There are too many possible cases. Nevertheless, testing still plays a central role in software
development, because testing helps detect problems. Before writing a program, or even a
single function, software developers should always think about how to test it. Often this
involves creating test inputs by hand, based on an understanding of where the weakness in
the function or program may be. This can be a lot of work, however, and it is often useful
to write small programs to generate test case input.
To test sorting, first write a program that generates random integers. To make this
program more flexible, it has one command-line argument: argv[1] tells the program how
many numbers should be generated. The program uses a random number generator. In C,
the function rand returns a number between 0 and the largest integer. These numbers are
“random” because it is difficult to predict which number will appear next. If we call rand
multiple times, it will return an unpredictable sequence of numbers. You can increase the
“randomness” by giving a seed. The seed is used to initialize the random number generator.
If we give the same seed in two different runs of the program, then the program generates
the same sequence of numbers. This can be useful for testing and debugging. If the seed
changes, the sequence also changes. The function srand sets the seed. Linux has a function
time. This function returns the number of seconds since 00:00:00 January 1st 1970. If srand
is called with time as an argument, then the seed changes every second. This is good enough
for many applications that require sequences of random numbers. This is not, however, truly
125
126 Intermediate C Programming
random since the seed is predictable. Generating truly random numbers is beyond the scope
of this book. This is the program for generating test inputs:
// testgen .c1
#in clude < stdio .h >2
#in clude < stdlib .h >3
#in clude < time .h >4
#in clude < string .h >5
#d ef in e RANGE 100006
int main ( i n t argc , char * * argv )7
{8
i f ( argc < 2)9
{10
printf (" need a positive integer n ") ;11
return EXIT _FAILUR E ;12
}13
int num = strtol ( argv [1] , NULL , 10) ;14
i f ( num <= 0)15
{16
printf (" need a positive integer n ") ;17
return EXIT _FAILUR E ;18
}19
srand ( time ( NULL )) ; // set the seed20
int count ;21
for ( count = 0; count < num ; count ++)22
{23
printf (" %d n" , rand () % RANGE );24
}25
return EXIT _SUCCES S ;26
}27
This problem requires the output to be sorted. If the generator produces a sequence of
random numbers, how can we get the correctly sorted result without first knowing that the
final program is correct? This is a circular problem: We do not have the program correctly
written yet so we do not have the sorted numbers. Without sorted numbers, we cannot check
whether the program is correct. Fortunately, we can use the sort program in Linux. The
sort program treats the values as strings; “9” is greater than “10” because the character
’9’ is greater than the character ’1’. Adding -n after sort treats the values as numbers, and
9 is smaller than 10. Below is the Makefile—it calls the sort program in Linux.
GCC = gcc1
CFLAGS = -g - Wall - Wshadow2
3
testgen : t e st gen . c4
$( GCC ) testgen . c -o testgen5
6
inputgen : testgen7
./ testgen 6 > input68
./ testgen 20 > input209
./ testgen 50 > input5010
./ testgen 100 > input10011
sort -n input6 > expecte d 612
sort -n input20 > e xpected2013
Programming Problems Using Heap Memory 127
sort -n input50 > e xpected5014
sort -n input100 > ex p ected10015
16
clean :17
/ bin / rm testgen input * expected *18
Now if we type:
$ make inputgen
eight files will be generated: Four are called input and the other four are called expected.
The input files have numbers in some random order. The numbers in the expected files are
sorted.
9.1.2 Redirecting Input
Section 1.2 describes how to use redirection for program outputs. This program uses
redirection for inputs. When a program calls scanf, the program waits for the user to
enter data from the keyboard. If we execute the program by adding < and a file name, the
program reads data from the file instead of from the keyboard. Below is the main function
for reading the input file. The purpose is to test whether the function can read from a file.
/*1
* main . c2
*/3
#in clude < stdio .h >4
#in clude < stdlib .h >5
#in clude < string .h >6
#in clude " mysort .h "7
int main ( i n t argc , char * * argv )8
{9
i f ( argc != 2)10
{11
return EXIT _FAILUR E ;12
}13
int number = strtol ( argv [1] , NULL , 10) ;14
int ind ;15
for ( ind = 0; ind < number ; ind ++)16
{17
int val ;18
scanf (" %d" , & val ) ;19
printf (" %d n" , val ) ;20
}21
return EXIT _SUCCES S ;22
}23
Below is the Makefile. Please pay special attention to the part for testinput.
GCC = gcc1
CFLAGS = -g - Wall - Wshadow2
OBJS = mysort .o main .o3
HDRS = mysort .h4
5
128 Intermediate C Programming
mysort : $( OBJS ) $ ( HDRS )6
$( GCC ) $ ( CFLAGS ) $( OBJS ) -o $@7
8
.c .o:9
$( GCC ) $ ( CFLAGS ) -c $ *. c10
11
testinput : mysort12
./ mysort 6 < input6 > temp613
diff temp6 input614
./ mysort 20 < input20 > temp2015
diff temp20 input2016
./ mysort 50 < input50 > temp5017
diff temp50 input5018
./ mysort 100 < input100 > temp10019
diff t e m p1 0 0 input10020
21
testgen : t e st gen . c22
$( GCC ) testgen . c -o testgen23
24
inputgen : testgen25
./ testgen 6 > input626
./ testgen 20 > input2027
./ testgen 50 > input5028
./ testgen 100 > input10029
sort -n input6 > expecte d 630
sort -n input20 > e xpected2031
sort -n input50 > e xpected5032
sort -n input100 > ex p ected10033
34
clean :35
/ bin / rm testgen input * expected * temp *36
If we type:
$ make testinput
it ensures that “mysort” has been compiled, and then runs the program in such a way that
the program reads input from an input file, instead of from the keyboard.
$ ./mysort 6 < input6 > temp6
The argument argv[1] is the number of integers. The actual values are stored in the
input file. In a later chapter we will explain how to get the number of integers from the file
itself without using argv[1]. With < input6, the input comes from the file called input6,
and not from the keyboard. With > temp6, the output is stored in the file called temp6,
and not printed to the computer screen. Using files like this helps us repeat the same tests
easily. The next line,
$ diff temp6 input6
checks whether the program reads the input values correctly. If the program is incorrect,
the values in temp6 and input6 are different. It is important to ensure the input values are
correct before sorting the values. If the program cannot read the input values correctly, the
program should be corrected before attempting to sort the values.
Programming Problems Using Heap Memory 129
9.1.3 Sorting Integers
The header file declares the sort function:
// mysort1
#i f n d e f MYSORT_H2
#d ef in e MYSORT_H3
void mysort ( in t * arr , int len );4
#e ndif5
Many sorting algorithms have been developed. In this example, we use selection sort. It
selects the smallest value among the array elements and then puts it at the beginning of the
array. Then, it selects the second smallest value and puts it as the second element of the
array. This process continues until reaching the end of the array. Here is an implementation
of the selection sort algorithm:
/*1
* mysort . c2
*/3
#in clude < stdio .h >4
s t a t i c void swap ( i n t * a , i nt * b)5
{6
int t = * a;7
* a = * b ;8
* b = t ;9
}10
11
void mysort ( in t * arr , int len )12
{13
/* in each iteration , find the smallest value and14
put it at the beginning of the array */15
int ind1 ;16
int ind2 ;17
for ( ind1 = 0; ind1 < len ; ind1 ++)18
{19
int minind = ind1 ;20
for ( ind2 = ind1 + 1; ind2 < len ; ind2 ++)21
{22
i f ( arr [ minind ] > arr [ ind2 ])23
{24
minind = ind2 ; // index of the smallest value25
}26
}27
i f ( minind != ind1 )28
{29
// move the smallest value to the correct loca t i on30
swap (& arr [ ind1 ] , & arr [ minind ]) ;31
}32
}33
}34
In mysort, ind1 is the counter for each iteration. When ind1 is zero, the smallest element
is moved to the beginning of the array. When ind1 is one, the second smallest element is
moved to the second element of the array. The value ind1 separates the array into two
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.