讲解：CSc 352、c++、linked lists、C++P

CSc 352 (Spring 2019): Assignment 11Due Date: 11:59PM Wed, May 1The purpose of this assignment is to work with linked lists, memory allocation, command linearguments, reading from a file, using free(), representing graphs, and doing more complicatedmanipulation of pointers.General Requirements1. Your C code should adhere to the coding standards for this class as listed in theDocuments section on the Resources tab for Piazza. This includes protecting againstbuffer overflows whenever you read strings.2. Your programs should indicate if they executed without any problems via their exitstatus, i.e., the value returned by the program when it terminates:Execution Exit StatusNormal, no problems 0Error or problem encountered 13. Under bash you can check the exit status of a command or program cmd by typing thecommand echo $? immediately after the execution of cmd. A program can exit withstatus n by executing exit(n) anywhere in the program, or by having main() executethe statement return(n).4. Remember your code will be graded on lectura using a grading script. You should testyour code on lectura using the diff command to compare your output to that of theexample executable.5. Your code must show no errors when run with valgind.6. You must free all your allocated memory before your program exits.TestingExample executables of the programs will be made available. You should copy and run theseprograms on lectura to test your program’s output and to answer questions you might have abouthow the program is supposed to operate. Our class has a home directory on lectura which is:/home/cs352/spring19You all have access to this directory. The example programs will always be in the appropriateassignments/assg#/prob# subdirectory of this directory. They will have the same name as theassigned program with “ex” added to the start and the capitalization changed to maintaincamelback. So, for example, if the assigned program is theBigProgram, then the exampleexecutable will be named exTheBigProgram. You should use the appropriate UNIXcommands to copy these executables to your own directory.Your programs will be graded by a script. This will include a timeout for all test cases. Theremust be a timeout or programs that don’t terminate will cause the grading script to never finish.This time out will never be less than 10 times the time it takes the example executable tocomplete with that test input and will usually be much longer than that. If your program takes anexceedingly long time to complete compared to the example code, you may want to think abouthow to clean up your implementation.MakefilesYou will be required to include a Makefile with each program. Running the command:make progNameshould create the executable file progName, where progName is the program name listed for theproblem. The gcc commands in your Makefile that create the object files must include the -Wallflag. Other than that, the command may have any flags you desire.Submission InstructionsYour solutions are to be turned in on the host lectura.cs.arizona.edu. Since the assignment willbe graded by a script, it is important you have the directory structure and the names of the filesexact. Remember that UNIX is case sensitive, so make sure the capitalization is also correct. Forall our assignments the directory structure should be as follows: The root directory will be namedassg#, where # is the number of the current assignment. Inside that directory should be asubdirectory for each problem. These directories will be named prob# where # is the number ofthe problem within the assignment. Inside these directories should be any files required by theproblem descriptions.To submit your solutions, go to the directory containing your assg11 directory and use thefollowing command:turnin cs352s19-assg11 assg11Problemsprob1: baconWrite a program called bacon which calculates the Bacon score(https://en.wikipedia.org/wiki/Six_Degrees_of_Kevin_Bacon ) of various actors based on theinformation given in an input file. Kevin Bacon is a movie actor and the Bacon score for anymovie actor is the number of movies it takes to connect Kevin Bacon with that actor. Thedefinition is as follows: Kevin Bacon has a Bacon score of 0 Any actor who was in a movie with Kevin Bacon has a Bacon score of 1 For any actor X, if the lowest possible Bacon score of any actor X has been in a moviewith is N, the Xs Bacon score is N + 1It may be hard to follow the outline above, but the concept is not that deep. Read through thewiki page linked to above if you are confused.Basically, this is a graph problem. The actors are the vertices. The edges connecting the actorsare movies. There is an edge between the vertices representing actors A and B if and only if Aand B appeared in a movie together. An actors Bacon score is then the smallest number of edgesconnecting the actor to Kevin Bacon. Invocation: Your program will be invoked with a required argument giving the file nameof a text file containing movie names and cast lists and an optional flag to tell theprogram whether to print out just the Bacon score or to print out the score together withthe path that generated it. The invocation will look like:bacon [-l] inFilewhere inFile is the name of a file which contains the movie list from which you willbuild your graph and –l (thats a lowercase L) is an optional flag. To make our programUNIX like we will allow the arguments to appear in any order and the option flag maybe specified multiple times. Here are some examples of legal invocations:bacon myFile –lbacon –l –l myFilebacon myFileThe following would be illegal invocations:bacon –l //has no file specifiedbacon fileName fileName //too many argumentsbacon –ll myFile //not a legal optionIf the invocation is illegal, you should print an error message to stdCSc 352作业代写、c++实验作业代做、代写linked lists作业、代做C++程序语言作业 代写Python编err indicating how theprogram is used, and exit with a status of 1. If you are confused about what is legal andwhat is not, experiment with the example executable. Movie File: The movie file whose name is given as a command line argument willcontain a list of movies and their cast lists. The format of the file is as follows:Move: Movie: . . .where the actors listed (one per line) after the movie name are the actors in that movie.An example input file is in the subdirectory for this project of the class home directory onlectura. The file may contain blank lines (lines containing only white space) and theseshould be ignored. A single space will follow the keyword Movie:. The name of themovie is considered to be the string starting at the character beyond that space andcontinuing until the end of the line but NOT including the \n. The actors name iseverything on the line except for the possible newline (\n) at the end. To simplify theprogram, do not worry about trimming white space from the ends of the lines (other thanthe \n) or capitalization. In other words the actors John Wayne, John Wayne , johnwayne, and John Wayne can all be considered to be different by your program. Behavior: After reading the file of cast lists and creating your graph, your program willdo the following:1. read in a line from stdin containing an actors name2. compute the Bacon score for that actor (using a breadth first search)3. print the Bacon score (and the connecting actors and movies if –l option invoked)to stdout according to the format specified below.until no further input can be read. ? Assumptions: You can assume the following:o The movie file, if it exists, is in correct format. In other words you may assumethe first nonblank line contains a movie name. You may also assume that if a linestarts with Movie: , then the line continues with some name. Note that sinceblank lines are legal, and empty file is in fact a legal movie file. Output: Output should be printed to stdout. To print out the score, use the formatprintf(Score: %d\n, score)where score is the calculated Bacon score. If there is no path between the actor and KevinBacon, your program should print Score: No Bacon! on a single line.If the actor queried is not in the graph, print a message to stderr and continue readingqueries. As always, whenever you print to stderr, when your program finally exits itshould exit with a status of 1.The –l optionIf the –l option is specified when the program is invoked, your program should print thelist of movies and actors connecting the queried actor to Kevin Bacon. The format for thisoutput should bewas in withwas in with. . .was in withKevin BaconKeeping track of this list is more difficult and only 10% of the test cases will involve thisoption and they will be for extra credit. In other words you can still get 90/90 (100%) onthe assignment even if you fail to implement the –l option (you must still recognize aninvocation with the –l option as legal though), or 100/90 if you correctly implement the –loption. Also note that while the Bacon score is unique, the list printed out may not be.This means that if you are testing this option you may end up with a different output thanthe example executable and still be correct. Dont worry about getting the same list as theexample as long as your list is correct. When I test this part of the program I will use testcases that have only one path to generate the Bacon score. You may want to create suchtest cases yourself. (The example movie file should do.)? Data Structures:Once again you will use linked lists to represent the graph. The vertices of the graph willbe the actors. The edges will be the movies. If you are implementing the –l option theedges will need to contain the movie name.There are certainly variations on this. I used a linked list of actors. Each actor contains alinked list of movies (nodes which point to a movie). Each movie contains a linked list ofactors (nodes pointing to an actor). The Algorithm:A depth first search will not work here. A depth first search finds if there is a pathbetween two vertices. We want to find the shortest path between two vertices. Toaccomplish this, we will use a breadth first search. A depth first search recursivelysearches all the children of each vertex. A breadth first search puts all the children on aqueue. This way all the children are search before the grandchildren, etc. Here is thealgorithm for a breadth first search:BFS(Start, Target)mark Start as queuedset level of Start to 0add Start to the queuewhile queue is not empty do Take A from top of queue For all children C of A do if C == Target return level of A + 1 //found, score A.level + 1 if C not queued mark C as queued set level of C to level of A + 1 add C to queuereturn Target not found //If you get through loop without //finding Target, there is no//path from Start to TargetNote that in C you will have to implement this queue with a linked list. Dont forget tofree it again after youre done using it.Heres a hint for implementing the –l option. It requires you be able to trace the path fromStart to Target. If some actor A is put on the queue when looking at the children of someactor B, the path to A comes from B. If your structure for nodes of the queue contains alink to this parent node, then you can following these links from the queue node for theTarget back to the queue node for the Start. (i.e. It records your path.) Error Conditions:o Fatal errors: Bad invocation of program; input file cannot be opened for reading.o Non-fatal errors: Queried actor is not in the graph. 转自：http://www.7daixie.com/2019042853422448.html