Part 1- Use pseudo code to describe your add, remove, find, and display options.
Part 2- Answer the following questions
1. What are the inefficiencies associated with using an unordered array if duplicates are not allowed?
2. What are the advantages of using an ordered array?
3. When would using an unordered array be preferred over using an ordered array?
4. Define Big-Oh notation. Explain how z and c in the definition relate to the evaluation of algorithm efficiency.
5. Why does computer science often describe algorithms in terms of lg instead of ln?
6. How do you convert ln(x) to lg(x)?
7. Give an example of algorithm with Big-Oh values of: N2, N lg N, 1, and N.
8. Why is Big-Oh 2N represent an algorithm called intractable?
9. How much slower would a linear search be on 1024 items than 16 items?
10. How much slower would a binary search be on 1024 items than on 16 items?
Part 3- Implement the program.
Instructions
1. For all our labs, use the Eclipse IDE. On your own computer, you will need to install MinGW. You will also need to download and install the C development toolkit (CDT). There are many tutorials on the Web to step you through this process. Eclipse is a popular IDE for C development; it includes a good interactive debugger and project control
2. Write a C program that will maintain a list of employees using either ordered or unordered arrays. Each employee in the list should store an identifier number (integer), a name (String - char array), and a salary (Double). Allow operations to add, remove, display single, display list, reset the list, create a initial list with randomly populated items, help, and exit.
3. You can choose either an unordered list or an ordered list for your implementation. If you choose an unordered list, sort it before display. For an ordered list, use a binary search instead of a linear search.
4. You don't need to implement a GUI for this project. Just create a menu of selections as listed below:
Employee Maintenance
1) Add Employee
2) Remove Employee
3) Display Employee
4) Display Employee List
5) Reset List
6) Create Initial List
7) Sort
8) Help
9) Quit
Please Select:
Note: The sort option is unnecessary if you implement an ordered list.
5. To add an employee, randomly pick an integer employee number that must be unique. The C function rand() can be used. A list of available employee numbers must also be maintained. Initially, this list can be filled with a sequential list of integers. To add a new employee, randomly pick one of these integers and replace its entry in the list with the final entry. Ask the user for an Employee name and salary. Keep track of the number of item numbers that are available using an integer counter.
6. When you remove an employee, the employee number should be returned to the free list.
7. Make sure to validate that the salary is within a reasonable range. You can use the C scanf function. Recall that scanf("%s*") is needed to clear the input buffer after an error. Always output appropriate error messages when the user types in something illegal. Robust programs should never crash.
8. My implementation contained three files; one for the main program (lab1.c), one for the list of employees (EmployeeList.c), and one for maintaining each employee (Employee.c). I also created a header file (empstructs.h), which contained a structure for the employee items and various symbolic constants (see below).
#ifndef EMPSTRUCTS_H_
#define EMPSTRUCTS_H_
#include
#include
#include
#include
#define MAX_EMPLOYEES 100
#define EMP_SIZE 30
#define LINE 80
#define OPTIONS 9
#ifndef NULL
#define NULL ((void *) 0)
#endif
#define FALSE 0;
#define TRUE 1;
typedef struct
{
int id;
char name[EMP_SIZE];
double salary;
} EMPLOYEE;
typedef struct
{
int freeCount;
int employeeIndex;
int numEntries;
int freeList[MAX_EMPLOYEES];
EMPLOYEE *employees[MAX_EMPLOYEES];
} EMPLOYEE_LIST;
/* Declared in Employee.c */
void destroyEmployee(EMPLOYEE**);
EMPLOYEE* createEmployee(char*, double, int);
char* employeeToString(EMPLOYEE*, char*);
/* Declared in EmployeeList.c */
void initializeEmployeeList(EMPLOYEE_LIST*);
EMPLOYEE* insert(EMPLOYEE_LIST*, char*, double);
void sort(EMPLOYEE_LIST*);
int delete(EMPLOYEE_LIST*, int);
void deleteAll(EMPLOYEE_LIST*);
EMPLOYEE* find(EMPLOYEE_LIST*, int);
int traverse(EMPLOYEE_LIST*, void (*)(EMPLOYEE*, char*));
#endif /* EMPSTRUCTS_H_ */
9. When you create a new employee, use the malloc command to allocate the appropriate amount of memory. sizeof(EMPLOYEE), assuming your employee structure is called EMPLOYEE, returns the number of bytes needed for the malloc command. When you remove an employee, or if you are resetting the employee list, make sure to call C's freefunction when getting rid of employees. C does not include garbage collection, so failing to do this leads to memory leaks.
10. The Create option will use a 'for' loop to automatically add items to the employee list. Random non-duplicate item number values are required (as we described above). Use any algorithm that you choose to generate different values for the names and salaries; duplicate field values are ok. A simple way to choose employee names is to declare an array of possible names. The following statement can then be used to randomly choose a description:
name = names[(int)(Math.Rand()%namesSize)];
For the salary field, (int)(Math.Rand()%RANGE) + MINSALARY can be used to guarantee that a valid dollar and cents value is used.
11. The help command redisplays the menu. Otherwise, it should only display once when the program starts.