CS计算机代考程序代写 Hive using System;

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

// Based on http://igoro.com/archive/skip-lists-are-fascinating/

namespace SkipLists
{
// Interface for SkipList

interface ISkipList where T : IComparable
{
void Insert(T item); // Inserts item into the skip list (duplicates are permitted)
bool Contains(T item); // Returns true if item is found; false otherwise
void Remove(T item); // Removes one occurrence of item (if possible) from the skip list
}

// Class SkipList

class SkipList : ISkipList where T : IComparable
{
private Node head; // Header node of height 32
private int maxHeight; // Maximum height among non-header nodes
private Random rand; // For generating random heights

// Class Node (used by SkipList)

private class Node
{
public T Item { get; set; }
public int Height { get; set; }
public Node[] Next { get; set; }

// Constructor
public Node(T item, int height)
{
Item = item;
Height = height;
Next = new Node[Height];
}
}

// Constructor
// Creates an empty skip list with a header node of height 32
// Time complexity: O(1)

public SkipList()
{
head = new Node(default(T), 32); // Set to NIL by default
maxHeight = 0; // Current maximum height of the skip list
rand = new Random();
}

// Insert
// Inserts the given item into the skip list
// Duplicate items are permitted
// Expected time complexity: O(log n)

public void Insert(T item)
{
// Randomly determine height of a node

int height = 0;
int R = rand.Next(); // R is a random 32-bit positive integer
while ((height < maxHeight) && ((R & 1) == 1)) { height++; // Equal to the number consecutive lower order 1-bits R >>= 1; // Right shift one bit
}
if (height == maxHeight) maxHeight++;

// Create and insert node

Node newNode = new Node(item, height + 1);
Node cur = head;
for (int i = maxHeight – 1; i >= 0; i–) // for each level
{
while (cur.Next[i] != null && cur.Next[i].Item.CompareTo(item) < 0) cur = cur.Next[i]; // Adjust references at level i once the height is within range if (i < newNode.Height) { newNode.Next[i] = cur.Next[i]; cur.Next[i] = newNode; } } } // Contains // Returns true if the given item is found in the skip list; false otherwise // Expected time complexity: O(log n) public bool Contains(T item) { Node cur = head; for (int i = maxHeight - 1; i >= 0; i–) // for each level
{
while (cur.Next[i] != null && cur.Next[i].Item.CompareTo(item) < 0) cur = cur.Next[i]; if (cur.Next[i] != null && cur.Next[i].Item.CompareTo(item) == 0) return true; } return false; } // Remove // Removes one occurrence (if possible) of the given item from the skip list // Expected time complexity: O(log n) public void Remove(T item) { Node cur = head; for (int i = maxHeight - 1; i >= 0; i–) // for each level
{
while (cur.Next[i] != null && cur.Next[i].Item.CompareTo(item) < 0) cur = cur.Next[i]; if (cur.Next[i] != null && cur.Next[i].Item.CompareTo(item) == 0) { cur.Next[i].Height--; // Decrease height by 1 when a level is removed cur.Next[i] = cur.Next[i].Next[i]; // Remove reference at level i } // Decrease maximum height by 1 when the number of nodes at height i is 0 if (head.Next[i] == null) maxHeight--; } } // Print // Outputs the item in sorted order // Time complexity: O(n) public void Print() { Node cur = head.Next[0]; while (cur != null) { Console.Write(cur.Item + " "); cur = cur.Next[0]; } Console.WriteLine(); } // Profile // Prints out a "skyline" of the skip list // Time complexity: O(n) public void Profile() { Node cur = head; while (cur != null) { Console.WriteLine(new string('*', cur.Height)); // Outputs a string of *s cur = cur.Next[0]; } } } class Program { static void Main(string[] args) { SkipList S = new SkipList();

int i;

for (i = 1; i <= 6; i++) { S.Insert(i); S.Insert(7 - i); } S.Print(); S.Profile(); for (i = 1; i <= 2; i++) { S.Remove(6); S.Remove(3); } for (i = 1; i <= 6; i++) Console.WriteLine(S.Contains(i)); S.Print(); S.Profile(); Console.ReadKey(); } } }