This assignment needs a working jsfiddle The first step of this assignment will

Question

This assignment needs a working jsfiddle

The first step of this assignment will be to create a List. You may use any List that you have already created. For the purposes of this assignment it does not matter if your list is a doubly linked list of a singly linked list. I recommend that if you created a good useful list in the previous lists assignment use this list.

Your list will be a little different in that it will have 2 content properties. I recommend calling them contentA and contentB.

The next step will be to fill the contentA and contentB list with actual content. ContentA will be filled with a random string or number. You may select a string of any length. ContentB will be filled with a Hash of ContentA. You may choose any simple hash function and apply it.

I would recommend a function that is 8 bits or more to avoid collisions. An incredibly good description of some hash function

You must document the name and source of your hash function in the comments of your code. This should be relatively easy once you implement your hash function. (Hint: Google simple Hash functions, you will find plenty)

ContentB = HashFunction(ContentA);   (note that some Hash function accept additional "seed" parameters)

Your List should contain 10 nodes. Use a loop to create it.

Once you have filled in all the ContentA and ContentB values you will create an object (similar to a Node) that contains (1) ContentB - the hashed value and (2) A pointer to the node it came from for each of the 10 nodes in the list. These objects will be placed into an array. This is your index. You will sort the array on these values (you may use the built-in array functions).

Here is the sample input and output.

The output of Create List would look something like this (horizontal or vertical)

The output of the Adler 32 bit hash for the input values would be as shown

Each value of the Hash function maintains a pointer to the value that created it. You do this by simply having a specific pointer in your construction of the List when you created it (you could call the pointer source). The results of sorting the Hash list and then the output could look something like this

Explanation / Answer

Created Below JS code:

String.prototype.hashCode = function() {
var hash = 0, i, chr;
if (this.length === 0) return hash;
for (i = 0; i < this.length; i++) {
chr = this.charCodeAt(i);
hash = ((hash << 5) - hash) + chr;
hash |= 0; // Convert to 32bit integer
}
return hash;
};

function Node (ContentA, next) {
this.ContentA = ContentA;
this.ContentB = ContentA.toString().hashCode();
this.next = next;
}

Node.prototype = {toString: function() {return this.ContentA;}}

function LinkedList (){
this.current = null;
this.count = 0;
this.first = null;
}

LinkedList.prototype = {
last: function (node) {
if (!node) node = this.current;
return node.next? this.last(node.next) : node;
},
insert: function (node) {
if (!this.current) this.current = this.first = node;
else this.last().next = node;
this.count++;
},
move: function (num) {
if (!num) return this.current;
this.current = this.current.next;
return this.move(num -1);
},
getList: function () {
var list = [(this.current = this.first)];
for (var i=1; i< this.count; i++, this.move(1))
list.push(this.current.next);
return list;
}
};

var list = new LinkedList();
for(var i=0; i<10; i++) {
   list.insert(new Node(parseInt(Math.random()*10000)));
}

nodes = list.getList();
for(var i=0; i<nodes.length; i++) {
   console.log(nodes[i].ContentA + " -> " + nodes[i].ContentB);
}

console.log(' after sorting');
nodes.sort(function(a, b) {
   return a.ContentB - b.ContentB;
});

for(var i=0; i<nodes.length; i++) {
   console.log(nodes[i].ContentA + " -> " + nodes[i].ContentB);
}

Sample Output on console:

676 -> 53653
6882 -> 1664316
7425 -> 1690080
727 -> 54460
9872 -> 1753658
9627 -> 1751586
9834 -> 1753536
8704 -> 1722691
8767 -> 1722880
9924 -> 1754466

after sorting
676 -> 53653
727 -> 54460
6882 -> 1664316
7425 -> 1690080
8704 -> 1722691
8767 -> 1722880
9627 -> 1751586
9834 -> 1753536
9872 -> 1753658
9924 -> 1754466

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.