An array of linked lists to be stored in a hash table and then stored in two more linked lists?

[XboxOne2019]

Our teacher assigned this homework assignment and it is due tuesday. I am not wanting anyone to solve it for me, it is just written so comfusingly and I am not sure exactly what I need to do. Emailing our instructor is not an option as he does not respond and we cannot go to the campus to ask. Here are the instructions:

I have a strange problem that must be solved by you. I have multiple link lists (unsorted) with integers values. I need to generate two list from the input. One list is a list of all values in all list and no duplicates are to be recorded. Two, I need a second list of values where the same values are found in all list (no duplicates).

For example input using 2 link list:

LinkList1: 5 -> 7 -> 3 -> 10 -> 6 -> 2 -> 3

LinkList2: 8 -> 7 -> 5 -> 10 -> 6 -> 3 -> 5

output: combo: 5, 7, 3, 8, 10, 6, 2 all the elements in both list no element is repeated

duplicates: 7, 3, 6, 5 elements in both list again no element repeated.

You will us the Hashing algorithm and enter each value from both list into the hash table. You will count the number of times each value is entered into the has table. The first entry is 1 of course. A second entry and only from a new list will be counted again. Now, to get the combo list, then all entries in the table will be in the combo list. To get the duplicates, that will be all entries with a 2 (or the number of list N for N list) indicating this entry is in all N list. If a second value appears in the same list, it is not to be counted again. You only count values from new list, and not a repeated value in the current/same list.

Your program will also need to handle N list, and output two list, the combo and the duplicate lists. You have the following input files to test your code with.

Files for input: ListOf2 ListOf3, ListOf5 Three different runs???

This program you are writing has to handle Link List. The Link List that your program will be handling comes from another department and the link list are not sorted and there are repeat values in these list, so your list you build are of the same structure and format that it will be handling later in production mode. You are to read in the values form the file and construct a link list for each input list. A simple link list, where each value read in will be the next node in the link list. An unsorted link list is built for each input line. All the data read in are to be placed into the link list, even if the value is a repeated value you will place repeated values in the list. A list is made up of multiple values and for this program, all the values for one link list will be found on one input line. The next line of values represents a new list. There will be at most, in any run, five (5) list to combine/form into two required list. Your program will have to determine the number of list per input file. Each input file I supply has a different number of list to work with. Max Hash Table size is 17. You should have minimal collisions. Keep a count of your collisions and print the number of collision results for each run. You will have to come up with your own Hash Function and a bad Hash Function produces more collisions. If your Hash Function is bad, your grade will suffer. You can pick any one of the three collision algorithms given in the lecture to handle collisions. Your input values are 3-digit integer numbers which is your key you will use to the Hash Table.

Output: Print out your N link list of values across the page, one pre line.

Print out the combo list.

Print out the duplicate list.

Print out the number of collisions encountered.

Hint: Since you will have multiple link list, and you don’t know how many, you will need N head pointers for N link list. A way to handle N head pointers is use an array of ABunchOfHeads where each location of the array is the head pointer for a different link list. Or, you could make a link list of head pointers where each node in the ABunchOfHeads link list is the head pointer to a different link list.

ListOf2.txt

692 694 689 688 689 696 698 695 692 693 694 689 698
686 702 696 688 692 690 689 696 685 700 703 693 686

ListOf5.txt

685 692 692 694 700 689 703 696 686 690 699 689 696 
687 696 702 699 692 690 699 685 699 691 703 699 698 
690 694 695 695 691 691 696 695 689 692 688 699 703 
688 690 685 692 686 697 686 696 687 701 703 699 689 
700 702 697 696 690 701 687 703 693 695 699 692 695

**After doing some stuff I realized that he wants us to make an array of linked lists called ABunchOfHeads. My issue is that after this, I am a little lost. I'm interpreting it as each line of each file is a separate link list so line 1 is ABunchOfHeads[0] and line 2 is [1] for the next one...etc..

After that are we taking the items in all the linked lists and combining them into one hash table, then outputting that hash table into two linked lists called combo and duplicates? I've been trying to figure out how to do this. I have a fully working hash table and a function with only 16 collisions. This was me testing reading all of list 2 file as one. We have to use one of the functions he had in the video. I just don't know how to get the array of linked lists into the hash table and then back out into two more linked lists if that is what he is asking. I'm just needing some clarity. Here is my hash function to show I am working on this and not wanting free code. Just an explanation. Stack overflow downvoted me for lack of clarity. Not sure how much more information to give. Please be patient, I am still very new.

int Hash::getSum(int n) //function to multiply each digit by its position then 
{                       //add them together 
    int i = 1;
    int sum = 0; 
    while (n != 0) 
    { 
     sum = sum + i * (n % 10); 
     n = n/10; 
     i++;
    }  
     return sum; 
 } 

int Hash::createHash(int key)  //creating the indexes for the hash table 
  {
    
    int hash = 0;
    int index;
    
   
    hash = getProduct(key);

   index = hash % tableSize;
    return index;
  }

[TheToaster]

The first question is this. You say you already have a fully working hash table. What does your hash table do when it is given a duplicate value? Does your hash table allow duplicates (like std::unordered_multimap) or disallow them (like std::unordered_map)?

If your hash table disallows duplicates, you need it to convey to the programmer that the element failed to insert was a duplicate. std::unordered_map does this by returning an std::pair in which one of the elements is a bool value that is false if the insert failed.

You can use the same method in your hash table. First, parse the file as you stated and make the ABunchOfHeads array with N elements (linked lists). Then, iterate through each of the N linked lists and add the elements to the hash table. If the insert on the hash table returns true, add the element to the combo linked list, but if the insert on the hash table returns false, add it to the duplicates linked list. Then, after the entire file is parsed, you have two linked lists, one containing the dupes and one containing the non-dupes.

[XboxOne2019]

ok thank you, yes my hash table allows duplicates and prints them out as a separate function. I have a flag that if there is more than one element in there, it will print. I was asking on here to make sure what I was reading is what I need to do. Thank you for clarifying it for me.

[dhayden]

If I'm reading the assignment, it's deceptively complicated because if this:

The first entry [in the hash table] is 1 of course. A second entry and only from a new list will be counted again.

When you go to insert an entry in the hash table and it's already there, how do you know if you should insert the duplicate? How do you know if the entry already there is from the current list or a previous one?

Maybe you need a side hash table of the items in the current list only. Then you store in the main hash table if it isn't in the side hash.

What do you store in the main hash table? I'd store a struct with the number itself, and a count of how many lists it appears in.

To generate the output, you must be able to traverse the hash table. Each item goes in the "all items" list. Items where the count of lists equals the number of input lists also goes into the duplicates list.

Print out your N link list of values across the page, one pre line.

Print this out as you read the input. There's nothing that says you must read all the input before you can generate the output.