Practice Exercise
List is K-Periodic
Your task is to write a function, listIsKPeriodic
, that takes two arguments: a linked list and a value k
, and determines if the list is k-periodic. A list is k-periodic if it repeats itself every k
values. If the list has k
or fewer elements, then it is k-periodic by default.
Assumptions and Constraints
k
is positive.- You must not use arrays.
- You must not use any variant of
malloc
, either directly or indirectly. - You must not modify the given list.
Download
While in your practice exercises directory, run the following command:
unzip /web/cs2521/practice-exercises/lists/listIsKPeriodic/downloads/listIsKPeriodic.zip
If you're working at home, download listIsKPeriodic.zip
by clicking on the above link and then unzip the downloaded file.
Files
list.c | Contains the implementation of basic list functions |
list.h | Contains the definition of the list data structure and function prototypes |
testListIsKPeriodic.c | Contains the main function, which reads in a list and a position from standard input, calls listIsKPeriodic , and prints out the result. |
listIsKPeriodic.c | Contains listIsKPeriodic , the function you must implement |
Makefile | A makefile to compile your code |
tests/ | A directory containing the inputs and expected outputs for some basic tests |
autotest | A script that uses the tests in the tests directory to autotest your solution. You should only run this after you have tested your solution manually. |
Examples
./testListIsKPeriodic Enter list: 2 2 2 2 2 2 2 Enter k: 1 List: [2] -> [2] -> [2] -> [2] -> [2] -> [2] -> [2] -> X listIsKPeriodic returned TRUE
./testListIsKPeriodic Enter list: 2 2 2 2 2 2 3 Enter k: 1 List: [2] -> [2] -> [2] -> [2] -> [2] -> [2] -> [3] -> X listIsKPeriodic returned FALSE
./testListIsKPeriodic Enter list: 2 3 4 2 3 4 2 Enter k: 2 List: [2] -> [3] -> [4] -> [2] -> [3] -> [4] -> [2] -> X listIsKPeriodic returned FALSE
./testListIsKPeriodic Enter list: 2 3 4 2 3 4 2 Enter k: 3 List: [2] -> [3] -> [4] -> [2] -> [3] -> [4] -> [2] -> X listIsKPeriodic returned TRUE
Testing
You can compile and test your function using the following commands:
make # compiles the program ./testListIsKPeriodic # tests with manual input, outputs to terminal ./testListIsKPeriodic < input-file # tests with input from a file, outputs to terminal ./testListIsKPeriodic < tests/01.in # for example, tests with input from tests/01.in # (then manually compare with tests/01.exp)
After you have manually tested your solution, you can autotest it by running ./autotest
. This will run some basic tests on your program, as well as check for memory leaks/errors.
It is possible to devise your own tests by creating your own input files. See the existing input files for examples. Note that you will need to check the output yourself.