computer sciences - C language

CptS 122 – Data Structures

Programming Assignment 3: Video Playlist Manager &

Doubly Linked Lists

– Part II

Assigned: Monday February 10, 2020 Due: Friday, February 21, 2020

I. Learner Objectives: At the conclusion of this programming assignment, participants should be able to:

• Design and implement a dynamic doubly linked list

• Allocate and de-allocate memory at runtime

• Manipulate links in a dynamic linked list

• Insert items into a dynamic linked list

• Delete items from a dynamic linked list

• Edit items in a dynamic linked list

• Traverse a dynamic linked list

• Design and implement basic test cases

II. Prerequisites:

Before starting this programming assignment, participants should be able to:

• Analyze a basic set of requirements for a problem

• Compose C language programs

• Create basic test cases for a program

• Apply arrays, strings, and pointers

• Summarize differences between array notation and pointer notation

• Apply pointer arithmetic

• Apply basic string handling library functions

• Apply pointer arithmetic

• Apply basic string handling library functions

• Summarize the operations of a linked list

III. Overview & Requirements:

• In this assignment you will complete the Video Playlist Manager that you started in PA 2. You must implement the following features:

o (4) insert o (5) delete o (7) sort (extra credit)

o (10) shuffle You will also be required to write 3 test functions.

a. What must “insert” do?

The “insert” command must prompt the user for the details of a new movie record. The prompt must request the movie title, director, description, genre, running time, year, number of times played, and rating. The new record must be inserted at the front of the list.

b. What must “delete” do?

The “delete” command must prompt the user for a movie title and remove the matching record from the list. If the movie title does not exist, then the list remains unchanged.

c. What must “shuffle” do? The “shuffle” command must provide a random order in which the movies are played. This command must not modify the links in the list. It must just specify the order in which movies are played, based on the position of the movie in the list. For example, let’s say we have a list with 5 movies at positions 1 – 5 in the list, shuffle must generate an order 1 – 5 in which the movies are played. An order 2, 5, 3, 1, 4 would require that the second movie in the list is played first, the fifth movie in the list is played second, the third movie in the list is played third, the first movie in the list is played fourth, and the fourth movie in the list is played fifth. The movies are accessed by traversing the list both forwards and backwards to satisfy the order. Hence, the need for a doubly linked list!

d. What must “sort” do? (EXTRA CREDIT)

The “sort” command must prompt the user for 4 different methods to sort the records in the list. These include:

1. Sort based on director (A-Z) 2. Sort based on file name(A-Z) 3. Sort based on rating (1-5) 4. Sort based on times played (largest-smallest)

Once a sort method is selected by the user, the sort must be performed on the records in the list. Consider using bubble sort, insertion sort, or selection sort.

• What “test” functions are required?

You must design and implement 3 test functions. These test functions must not accept any arguments or return any values. They should be self-sufficient. You should provide function declarations for them that are in a separate header file than your utility/application function declarations. You must implement one test function for insert, delete, and shuffle features for a total of 3 functions.

o For the insert test function you must provide a test case with the following

test point: movie title = “Bohemian Rhapsody”, director = “Bryan Singer”, description= “Freddie Mercury the lead singer of Queen defies stereotypes and convention to become one of history's most beloved entertainers.”, genre = “Drama”, running time = “2:13”, year = 2018, times played = -1, rating = 6. You must think about what is your expected result? Should you able to insert a movie with -1 times played? Should you able to add a movie with rating 6? Is the head pointer of the list updated?

o For the delete test function you must provide a test case with the

following test point: movie title = “Bohemian Rhapsody”, director = “Bryan Singer”, description= “Freddie Mercury the lead singer of Queen defies stereotypes and convention to become one of history's most beloved entertainers.”, genre = “Drama”, running time = “2:13”, year = 2018, times played = -1, rating = 6. You must think about what is your expected result? Has the head pointer been updated? Is it NULL? Did the memory get released?

o For the shuffle test function you must provide a test case with the

following test point: list the play order that was randomly generated and list the movies. Example: play order = 3, 1, 2. List state = you provide 3 movies. Does the shuffle play in the correct order?

IV. Logical Block Diagram The logical block diagram for your doubly linked list should look like the following:

Record 1: Film Title Director

Description Genre

Running Time Year

Director Times Played

Rating

…

Record 1: Film Title Director

Description Genre

Running Time Year

Director Times Played

Rating

Record 1: Film Title Director

Description Genre

Running Time Year

Director Times Played

Rating

Record 1: Film Title Director

Description Genre

Running Time Year

Director Times Played

Rating

NULL

NULL

As you can see from the illustration a doubly linked list has a pointer to the next node and the previous node in the list. The first node’s previous node pointer is always NULL and the last node’s next pointer is always NULL. When you insert and delete nodes from a doubly linked list, you must always carefully link the previous and next pointers.

V. Submitting Assignments:

1. Must submit your assignment in a zip file through blackboard.

2. Your project must contain at least one header file (a .h file), two C source files

(which must be .c files), and a local copy of the .csv file.

3. Your project must build properly. The most points an assignment can receive if it

does not build properly is 65 out of 100. VI. Grading Guidelines: This assignment is worth 70 points. Your assignment will be evaluated based on a successful compilation and adherence to the program requirements. We will grade according to the following criteria:

• 5 pts – Appropriate top-down design, style, and commenting according to class standards

• 17 pts – Correct “insert” command implementation o (7 pts - 1pt/attribute) For prompting and getting the details of

a new record from the user o (10 pts) For correctly inserting the record at the front of the list

• 23 pts – For correct “delete” command implementation o (3 pts) For prompting and getting the movie title from the user o (5 pts) For searching for specific record matching the movie title o (15 pts) For removing the matching record from the list, and

reconnecting the list correctly

• 15 pts – Correct “shuffle” command implementation o (5 pts) For generating the random order based on the number of movies

in the list o (10 pts) For moving through the list (forwards and backwards) and

playing the movies in the order generated

• 10 pts – Robust test functions – 3 required o (4 pts) For a test function that challenges the bounds of r insert feature. o (3 pts) For a test function that challenges the bounds of

r delete feature. o (3 pts) For a test function that challenges the bounds of

your shuffle feature.

• Extra Credit: 30 pts – Correct “sort” command implementation o (3 pts) For prompting and getting the sort method from the user

o (7 pts) For sorting based on movie title (A-Z) o (7 pts) For sorting based on director (A-Z) o (6 pts) For sorting based on rating (1-5) o (6 pts) For sorting based on times played (largest-smallest)