Computer programming - Lab 13

Abstract datatypes

1. Complex numbers Implement an abstract data type (including .h and .c file) for a complex number. Use a 64-bit value that encodes both real and imaginary part as 32-bit floats. Implement functions that construct a complex number given real and imaginary parts; extract real/imaginary part; multiply two complex numbers; print a complex number.
Note: In C, the header complex.h defines support for complex numbers. It defines the types float complex, double complex and long double complex and the macro I for the imaginary unit.
Optionally, figure out how a value of type float complex is represented in memory.

2. Rationals Implement a datatype for rational numbers, using a 64-bit value. Use 4 bits to represent the number of bits on which the positive denominator is stored (a value from 2 to 17). Use the remaining bits to represent the deumerator. Implement addition and multiplication. Choose a value to represent overflow.

3. Bitsets
a) Implement and test a library for sets of bounded unsigned integers, using one bit per element. The maximum value for a set element is given at set creation time.
b) Implement an abstract datatype for a set of alphanumeric characters, using a 64-bit value. In addition to the usual set functions, also write a function that takes a string and produces the set of alphanumeric characters contained in the string.

4. Date Implement an abstract data type (including .h and .c file) for a calendar date (including fields from year to second). Use a 32-bit integer, with separate bit fields for each component, having the year 1970 as starting point. Implement functions that construct a date from 6 parameters, check if an integer represents a valid date, compute the difference (in seconds) between two dates, and extract day and month from a date.
For one of the latter two functions use bitwise operators and for the other cast the pointer to the date value to a pointer to a structure with bitfields, and use those bitfields.
Note: the UNIX time representation simply counts seconds from a starting date (Jan. 1, 1970) and does not use separate bitfields. The MS-DOS time format used a similar bitfield representation, but in multiples of two seconds (4 bits for the second field), and with 1980 as starting year (7 bits for the year).


5. Delete duplicates Implement a function that takes a list of integers and removes any consecutive duplicates (leaving only one value from any sequence of equal values). Modify the list in place and free the memory for the deleted values.

6. List of text lines. Write a program that reads text lines until end of input and stores them in a list. Then rotate the list so that it starts with the line that is alphabetically first, then the lines following it in the original text, then the lines preceding it. Minimize the changes needed.

7. Lists of lists Implement a datastructure for lists of integer lists. Use it to store integers read until end of input (separated by whitespace), each input line resulting in a list. Use the address of the (link) pointer to append each new integer to the end of the list for a line.

8. Conditions on lists Use the integer list ADT defined in class to implement the following functions, each taking as parameter a list and a pointer to function that takes an integer and returns a boolean (0 or 1):

9. Lists and trees A binary tree with integer nodes is either the empty tree, or a node (root) with a left and a right subtree.
A binary tree with different values in each node may be uniquely reconstructed if the lists of its nodes in both preorder and inorder traversals are given.
Preorder traversal means visiting the root followed by the left and right subtree. Inorder traversal means visiting the left subtree, the root and then the right subtree. In both cases, subtrees are traversed in the same order as specified.
For example, given the lists:
preorder: [2; 7; 1; 6; 5; 11; 8; 9; 4]
inorder: [1; 7; 5; 6; 11; 2; 8; 4; 9]
the first element in the preorder list is the root. Searching for it in the inorder list splits the list into [1; 7; 5; 6; 11] for the left subtree and [8; 4; 9] for the right subtree (both inorder). Splitting the tail of the preorder list in pieces of the corresponding lengths produces the (preorder) lists [7; 1; 6; 5; 11] and [8; 9; 4]. Thus the problem is reduced to solving it recursively for the two subtrees.
Implement a function that takes two lists and returns the tree reconstructed from these lists. Do not destroy the original lists, but free any intermediate memory allocated. Report inconsistent input.
Simpler version: Solve the problem for arrays instead of lists. Avoid any copying in this case.

Marius Minea
Last modified: Tue Dec 19 20:30:00 EET 2017