data structures - c language
CIS2520 Data Structures II Assignment 2 Dr. Charlie Obimbo Due time: 11:59 pm, Oct 15, 2022. Name: 1 Stacks 1. (60%) Write a program in which linked lists are used to maintain the data structure for a car rental company. The program allows several types of transactions to be applied to the data structure in order to keep the lists up-to-date. In the program three linked lists are maintained for cars: • available for rent, • rented, • in repair. The cars on the available list are ordered by mileage, with the car having the least miles at the front of the list. The cars on the rented list are ordered by the expected return dates, with the first car on this list having the earliest expected return date. The program prompts the user for a transaction code (integer) as follows: (a) add a new car to the available-for-rent list, (b) add a returned car to the available-for-rent list, (c) add a returned car to the repair list, (d) transfer a car from the repair list to the available-for-rent list, (e) rent the first available car, (f) print all the lists, (g) quit. For the new car addition and the return transactions (codes 1 - 3), the program should then prompt for a plate number (character string) and a mileage (integer). For the transfer trans- action (code 4), the program should then prompt for a plate number (character string). For the rent transaction (code 5), the program should then prompt for an expected return date (integer: yymmdd). For the print transaction (code 6), the program should not prompt any additional information. The program should quit when the user selects 7 in the prompter. When a transaction is processed, a message should be printed indicating what action is taken, for example which car is transferred from which list to which list. For each return transaction, a charge is computed and printed as follows: 1 • a flat rate of $80.00 for up to 200 km, • 15 cents per km for the additional (i.e. beyond 200) kilometres. When a quit transaction is completed, the program prints the total income from all the rented cars. Also when a quit transaction is completed, the program should store the data into a disk file, and when the program restarts, the program should read the data from the file and restore the lists. Please create an initial disk file so that when the program starts for the first time, there are data on the lists. The file should contain at least 5 cars for each list. Your program should be able to reasonably detect error conditions (such as invalid transac- tion code, and an attempt to return a non-existent car) and print an appropriate error message. 2 Reverse Polish notation (RPN): Łukasiewicz notation 2. (40%) An expression is in postfix form (Reverse Polish Notation) if the operators appear after their operands, for example, “1 2+” means “1 + 2”, and “1 2 + 5 3 − ∗” means “(1 + 2) ∗ (5− 3)”. Write a program that evaluates postfix expressions composed of single digits and binary operators of +, −, ∗, and /, for addition, subtraction, multiplication, and devision respectively. The program takes an expression as a command-line argument, with no space in it, for ex- ample q2 12+53-*, where q2 is the name of the executable. The program prints a result that has two digits after the decimal point. 3 Assignment 2 Guideline For question 1, you should create three ordered lists and functions for the required operations in- cluding insertion, deletion, transfer, etc. For question 2, you could create a stack to store operands, intermediate results, and final results, when the input is scanned from left to right. Create two C files for the two questions respectively, for example, q1.c and q2.c. Create a makefile for compiling the programs. The makefile should be able to generate two executable files, for example, q1 and q2. Please note that for this and future assignments, it is required that all students compile with “gcc -Wall -std=c99 -pedantic”. Your submission may include something like readme.txt, q1.c, q2.c, makefile, and for question 1 the data file for initializing and/or restoring the lists. Any compilation error or warning will result in a mark deduction appropriate to the severity of the error. There will be some marks allocated for style and documentation, but the majority will be for the execution of the programs. Each file should have a comment at the beginning containing your name, id, the date, and the assignment name. 2 For the readme file, it should contain the following: • name, id and assignment number. • a brief description of how to run each program, e.g. any command line arguments needed. • sample output demonstrating the proper functioning of the program. For each of the C files, any function should have a brief comment describing its purpose. Also, any section of code where it is not easily apparent what the code does should have a short comment. Don’t forget indentation. 3