CSCE 2014 - Laboratory Assignment 4

    The purpose of this lab is to gain more experience with the linked list data structure and to learn how to do program timing experiments. You will be using the StudentNode class from last lab, and a new StudentList class that implements the linked list abstract data type.

  1. Creating a StudentList
  2. Create a new NetBeans project, and copy the files student_node.h, student_node.cpp, student_list.h, student_list.cpp and student_test.cpp into the project. When you look at this code, you will see that the student_node.h file has the declaration and student_node.cpp has the implementation of the StudentNode class that you saw in the previous lab. Similarly student_list.h has the declaration and student_list.cpp has the implementation of the StudentList class, with operations to insert and print StudentNodes. The main program in student_test.cpp is currently empty, so when you compile and run the program it will not do anything.

    Edit the main program in student_test.cpp to declare a StudentList object and insert five student records into the StudentList using the methods provided by the class. You can make up any student names, addresses, and gpas that you want. After the insertions, print the contents of the list. Once you have your program compiling and running, cut and paste the main program below.

  3. Comparing insertHead to insertTail
  4. If you look at the implementation of "insertHead" you will see that it adds a new StudentNode at the beginning of the linked list using code like we discussed in class. If you look at "insertTail" you will see that this code "walks the list" to get the the end of the list and inserts the new node there.

    Edit your program above to use "insertHead" to add your five student records. Now compile and run your program and cut and paste your program output below.

    Now change your program to use "insertTail" instead. Compile and run your program again and cut and paste your program output below. Hopefully you will see a big change from above.

  5. Calculating Excution Times
  6. As you can guess "insertTail" has to do more work than "insertHead" when adding StudentNodes to the linked list. A natural question is: How much time does this take? To find out, we must run some experiments.

    Most programming languages have commands that will let you get the current time inside the program. If we do this before and after running a chunk of code, we can calculate the elapsed time for the computation. In C++ we do this with the following code.

       // Get start time
       clock_t time1=clock();
    
       // Some chunk of code
    
       // Get end time
       clock_t time2=clock();
       double run_time = (time2-time1)/(double)CLOCKS_PER_SEC;
       cout << "Run time: " << run_time << " seconds\n";
    

    Modify your program to put the timing code around your code to insert data into a linked list. You will also need to add a "#include < time.h >" statement at the top of the program. When you run your program, you will probably find out that it runs so quickly, that it finishes in 0 seconds.

    Now modify your program to add a for loop around your insertTail code, so it executes 100 times. If you used cout/cin for interactive user input for the insertion in the previous steps, do NOT do so here. Instead, you can hard code a set of name, address, and gpa into your insert function inside the loop.

    Compile and run your program. It should take longer to insert 500 nodes, but it may still register as 0 seconds. Modify your program again to try 1000 loops and see what happens. Continue changing the number of loops until your program takes more than 1 second to execute. If your program runs for more than 10 seconds, then kill it to save the CPU.

    Try the experiment again with insertHead and record the execution times in the table below. Hopefully, you will see that one method is far faster than the other. You should also see that the rate of increase is very different for these two insertion methods.

  7. Searching the StudentList
  8. So far, we have added a lot of data to the StudentList object, but we have not done anything with this data. Your final task is to implement methods to search the linked list for specific student records.

    Add methods called "searchName" and "searchGPA" to the StudentList class and create empty implementations of these methods. These methods should take in either a string or a floating point value as input parameters, and they should return a pointer to a StudentNode object.

    To implement the "searchName" method you will need to write code to "walk the list" and stop when you find a node with a Name that is equal to the parameter value. You should use "str1.compare(str2)" to compare strings (and not str1 == str2). If you do not find a matching student node, your method should return a NULL pointer.

    To implement the "searchGPA" method you will need to write code to "walk the list" and stop when you find a node with a GPA that is greater than or equal to the parameter value. There may be several students that match your query, just return the first one that you find. Again, if you do not find a matching student node, your method should return a NULL pointer.

    Remove your loop code from your main program, and test your search function on a linked list of five students. If you find a matching record, print the student information using "ptr->print()". If you do not find a matching record, print "student not found". Cut and paste your entire StudentList program and your program output below.

  9. Submit Work
  10. This lab assignment will be submitted electronically to the TAs once you fill in the fields below and click on the "submit" button. You do NOT need to print a copy of this document to hand in.

    Your UAID number:
    Your website PASSWORD: