1

I have this code for a skip list I modified from a source online, the add(x) method somewhat works. 

add(5);
add(4);
add(7);

it works when you add a number like 5, then any number smaller than the last number, like 4 but once it get to 7 or any number larger than the previous it gets stuck in a loop, and I cannot see why.

package assignment1;

public class Node {
    public static int item;
    public static Node[] next;
    public static int MAX_LEVEL = 6;
    public static int level;
    public static int n;
    public static Node head = new Node(MAX_LEVEL, 0);


    public Node(int level, int value){
        next = new Node[level + 1];
        this.item = value;
    }
    public static int randomLevel() {
        int lvl = (int)(Math.log(1. * -Math.random()) / Math.log(1. * -0.5));
        return Math.min(lvl, MAX_LEVEL);
    } 

    public static void add(int value){
        Node current = head;    
        Node[] update = new Node[MAX_LEVEL + 1];

        for (int i = level; i >= 0; i--) {
        while (current.next[i] != null && current.next[i].item - value < 0) {
            current = current.next[i];
        }
        update[i] = current; 
    }
    current = current.next[0];

        if (current == null || current.item != value) {        
        int lvl = randomLevel();

            if (lvl > level) {
                for (int i = level + 1; i <= lvl; i++) {
                update[i] = head;
        }
                level = lvl;
        }
            current = new Node(lvl, value);
        for (int i = 0; i <= lvl; i++) {
            current.next[i] = update[i].next[i];
            update[i].next[i] = current;
        }
            n++;
        }
    }

    public static void remove(int value){
        Node current = head;    
        Node[] update = new Node[MAX_LEVEL + 1];

        for (int i = level; i >= 0; i--) {
        while (current.next[i] != null && current.next[i].item - value < 0) {
            current = current.next[i];
            }
        update[i] = current; 
    }
    current = current.next[0];

        if (current.item == value) {
            for (int i = 0; i <= level; i++) {
            if (update[i].next[i] != current){
                break;
            }
            update[i].next[i] = current.next[i];
        }
            while (level > 0 && head.next[level] == null) {
            level--;
        }
            n--;
        }
    }

    public static void list(){
        Node current = head;
        System.out.print("[");
        for (int i = 0; i < n; i++){
            System.out.print(current.item + ",");
            current = current.next[0];
        }
        System.out.print("]");
    }


    public static void main(String[] args){
        add(10);
        add(9);
        add(8);
        add(7);
        add(6);
        add(5);
        add(4);
        add(3);
        add(2);
        add(1);
        list();
    }
}

EDIT: I uploaded the entire code I developed, the code is from a Textbook of mine that is in Pseudocode, it needed to be adapted into Java format. I cannot see why its failing.

4

1 回答 1

0

我无法弄清楚您的实现出了什么问题，所以这是一个可行的，您可以学习并且应该让您走上正确的道路：

import java.util.Random;
import java.util.Arrays;

public class SkipList
{
private class Node
{
    private int item;
    private Node[] next;

    public Node(int value, int level)
    {
        this.item = value;
        next = new SkipList.Node[level+1];
    }

    public int level()
    {
        return next.length-1;
    }
}

private  Node head;
private int size;

/**
 * Constructs a new, empty instance of SkipList.
 */
public SkipList()
{
    head = new Node(0, 0);
    size = 0;
}

private int randomLevel()
{
    int level;

    Random rand = new Random();

    for (level = 0; rand.nextInt() % 2 == 0; level++)
        ;

    return level;
}


public void add(int item)
{
    int maxLevel = head.level();

    Node current = head;

    Node[] nodePath = new SkipList.Node[maxLevel + 1];

    for (int level = maxLevel; level >= 0; level--)
    {
        while (current.next[level] != null && item > current.next[level].item)
        {
            current = current.next[level];
        }

        nodePath[level] = current;
    }

    current = current.next[0];

    if (current != null && item==(current.item))
    {
        return;
    } 
    else
    {
        int nodeLevel = randomLevel();

        if (nodeLevel > maxLevel)
        {
            head.next = Arrays.copyOf(head.next, nodeLevel + 1);

            nodePath = Arrays.copyOf(nodePath, nodeLevel + 1);

            for (int level = maxLevel + 1; level <= nodeLevel; level++)
            {
                nodePath[level] = head;
            }

            maxLevel = nodeLevel;
        }

        current = new Node(item, nodeLevel);

        for (int level = 0; level <= nodeLevel; level++) {
            current.next[level] = nodePath[level].next[level];

            nodePath[level].next[level] = current;
        }

        size++;
    }
}



public void list()
{
    Node current = head.next[0];
    System.out.print("[");
    while(current != null)
    {
        System.out.print(current.item + ",");
        current = current.next[0];
    }
    System.out.println("\b]");
}


public static void main(String[] args)
{
    SkipList theList= new SkipList();

    theList.add(10);
    theList.add(9);
    theList.add(8);
    theList.add(11);
    theList.add(6);
    theList.add(5);
    theList.add(7);
    theList.add(3);
    theList.add(4);
    theList.add(1);
    theList.add(2);
    theList.list();
}
}

输出：

[1,2,3,4,5,6,7,8,9,10,11]
于 2015-03-18T23:51:04.510 回答