Compare function in recursive mode
Posted on 2012-08-30
I have wrote complete program. But, stuck in compare function in recursive mode.
Not getting how to maintain flags and return.
Problem statement is as :
Write a program that finds the kth smallest Number from a list of any base-n numbers (for
any n up to a fixed maximum value, maxN). The definition of the ADT called Number is
the same as that defined in Lab-1. For ease of implementation, assume that each digit is
represented by a character. A separate lookup table needs to be created for storing the
symbols (character) corresponding to the various digit values.
The program must take two command-line parameters:
the first parameter is the name of a file containing the sequence of characters to
be used for the digit values from 0 to maxN-1, and
the second parameter is the name of a file containing N Numbers.
The sequence of characters corresponding to digit values 0 to maxN-1 is given in the first
line of the first input file, separated by spaces. Note that maxN to be used in the particular
instance of execution is calculated by the number of entries in the first line. Only
alphanumeric characters can be used for representing digits in the number system. (Note
that the total number of alphanumeric characters is limited to 62.)
Consider this sample file:
b i g s o u n d
By reading this you should infer that maxN is 8 and the value of symbol o is 4 and that of
symbol n is 6 and so on.
The second input file contains a list of N Numbers, with one Number in each line.
Consider the following sample (second) file: containing the numbers 59 in base-6, 36 in
base-8, 10 in base-2, 7 in base-3, 576 in base-4, 9 in base-2. Representation of the first
number in File2 is shown below.
The definition for lookup table named Base, containing a list of symbols indexed by
digit values. Note that since the base is immutable (i.e. won’t change), the list can
be allocated at time of definition.
The type definition for a Number, containing the fields: the base of the number, a
linked list of digits each of which is a character, and other field that may be useful.
The type definition for an enumerated type called Order, that can have either
GREATER, LESSER or EQUAL.
Design of Base ADT with the following operations
(a) int initializeBase(FILE *basefile) : reads the file containing the
characters corresponding to each digit, populates the lookup table and returns the
maximum base supported in the current execution. Note that to use the number
system; this function has to be called first, before any other function.
(b) int lookup(char c) : looks-up the character in the Base lookup table and
returns the value associated with the character.
Design of Number ADT with the following operations:
(a) Number createNumber(char *number_format): takes the number
format as a string containing the base of the number, followed by a space, followed
by the number using the custom characters(Most Significant Digit first). This
function then creates a Number using the values corresponding to the digits and
(b) void printNumber(Number n): prints the Number in the base stored in
(c) Number convert(Number n, int to_base): converts the number n to a
number of base to_base, and returns it.
(d) Order compare(Number n1, Number n2): This function is used to
compare two Numbers of any valid base. This function returns GREATER if n1 >
n2; LESSER if n1 < n2; or EQUAL if n1 = n2. This function must be written using
(e) int partition(Number list, int start, int end): This
function partitions the list[start...end] into 2 sublists, such that all
Numbers in left sublist is less than a chosen pivot and all the Numbers in the right
sublist are greater than the chosen pivot. Here, the pivot element is chosen as
median of the five elements list[start], list[(start+end)/4],
list[(start+end)/4*3], list[(start+end)/2], and list[end].
This function uses compare described above for comparison.
(f) Number quickSelect(Number list, int size, int k): This
functions returns the kth smallest Number in the list, using an iterative version of
quickselect. This function uses partition described above for partitioning about
a pivot element,