Homework answers / question archive / As a recursive thinking/programming exercise, this assignment involves using recursion to solve the problem of determining whether a given singly-linked list (of the type focussed in class) has any of its (data-)values duplicated, as described below: ? Client (driver program) calls directly recursive function listHasDupRecur with prototype bool listHasDupRecur(Node* head); passing to it the list's head pointer, and receives true as return value if the list has any of its (data-)values duplicated and false otherwise

As a recursive thinking/programming exercise, this assignment involves using recursion to solve the problem of determining whether a given singly-linked list (of the type focussed in class) has any of its (data-)values duplicated, as described below: ? Client (driver program) calls directly recursive function listHasDupRecur with prototype bool listHasDupRecur(Node* head); passing to it the list's head pointer, and receives true as return value if the list has any of its (data-)values duplicated and false otherwise

Computer Science

Share With

As a recursive thinking/programming exercise, this assignment involves using recursion to solve the problem of determining whether a given singly-linked list (of the type focussed in class) has any of its (data-)values duplicated, as described below: ? Client (driver program) calls directly recursive function listHasDupRecur with prototype bool listHasDupRecur(Node* head); passing to it the list's head pointer, and receives true as return value if the list has any of its (data-)values duplicated and false otherwise. ? Besides being directly recursive (TIP: it calls listHasDupRecur itself at some point), listHasDupRecur also calls an indirectly recursive function hnValDup with prototype bool hnValDup(Node* head); to help determine if a list (whose head pointer is passed during the call) has its head-node (data-)value duplicated elsewhere on the list (true returned if duplicated and false otherwise). ? Being indirectly recursive, hnValDup doesn't make directly recursive call (of hnValDup itself) but calls an auxiliary function hnValDupAuxRecur (that is directly recursive) with prototype bool hnValDupAuxRecur(Node* head, int givenVal); to help determine if a list has any of its data-value matching a given value (the list's head pointer and the given value are passed during the call, and true is returned if a match is found and false otherwise). Your are to study the supplied (supplemented by above description) and complete (fill in the "holes" tagged "// your code (to be filled in as part of Assignment 6 Part 1)") and test the first 3 functions (hnValDup, hnValDupAuxRecur and listHasDupRecur) appearing in llcpImp.cpp. Other specifications/requirements/notes/. . .: ? Each node of a singly-linked list (of the type focussed in class) has the following structure: struct Node { int data; Node *link; }; ? No looping constructs (for, while, do-while, ...) should be used when completing the body of all the 3 functions. ? No other function calls (besides those mentioned in above description) should be made in the 3 functions. ? No global variables or static local variables should be used. ? No new nodes should be created and no existing nodes should be destroyed. ? A total of 5 lines of code were voided to create the "holes" in the 3 functions. ? Treat this as an in-case-helpful hint/tip, i.e.: ? It doesn't mean you must write a total of no more than 5 lines of code to complete the 3 functions. ? However, something is probably amiss if you find yourself having to write a lot more than 5 lines of code. Examples: (see a6p1test.out of Supplied Files for more) Contents of given list Return value on calling listHasDupRecur with given list (empty) false 6 false 6 6 true 6 9 false 3 11 10 10 true 1 15 10 12 9 13 10 11 true 11 3 6 12 2 4 false 13 6 10 14 3 3 15 true 13 11 12 4 5 9 0 false 4 1 14 2 4 1 1 13 12 true ? Your Tasks ? Read the description thoroughly and carefully to understand exactly what the 3 functions (with "holes") are for and how they make use of recursion (direct and indirect). ? Complete the definitions for the 3 functions. ? Test/debug your code using the supplied tester file (Assign06P1.cpp) and Makefile. ? Do make to compile or re-compile. ? Do make go (after successful compilation or re-compilation) to test with result output to terminal. ? Program will (display some error messages and) abort on the first detection of an incorrect outcome (associated with a certain test case). ? If the program hangs, it typically means your code has led to an infinite loop. Regardless, you should do Ctrl-c to get out of the hanged state. ? If you need to identify which specific test case causes the program to hang or quit abruptly ("bomb out" due to segmentation fault, for instance), uncomment the DebugShowCase line (Line 59 in Assign06P1.cpp as supplied), then re-compile the program and re-run the test. ? If you do enable DebugShowCase (uncomment Line 59 in Assign06P1.cpp) during debugging, be sure to revert it back to disabled when generating the test output (a6p1test.out) for hardcopy submission, otherwise the test output can be humongous. ? Do make gogo (after successful compilation or re-compilation) to test with result (excluding progress-logging messages) output to file (a6p1test.out). ? (The a6p1test.out included in the Supplied Files was generated by compiling and running the program on the CS Linux server. Expect the test cases to be different if another system is used since the algorithm used for the pseudo-random number generator vary from system to system.) ? Deliverables ? llcpImp.cpp source file: ? An as-is "text" version evaluator can use to compile and test. ? A (print-to-)PDF version (be sure it jibes with the as-is "text" version) evaluator can mark on and return. ? Upload it to your TxSt Canvas account by 11:55 pm on the due date. NOTES: ? If you discover anything that appears incorrect, please let me know (through email) as soon as possible. ? Be sure to check the homepage often for any further information related to this assignment.