0

我不知道从哪里开始,但这很混乱。基本上我需要为单链表编写一个插入排序方法——这会导致足够的问题,因为通常对于插入排序——你应该向后遍历数组/列表元素——实现单链表似乎毫无意义,因为重点-您只能在列表中前进,除此之外->我需要在外部执行“交换”操作,我不完全了解如何在使用列表结构时执行该操作。

这是我使用的 ArrayClass 和 Swap 方法:

class MyFileArray : DataArray
{
    public MyFileArray(string filename, int n, int seed)
    {
        double[] data = new double[n];
        length = n;
        Random rand = new Random(seed);
        for (int i = 0; i < length; i++)
        {
            data[i] = rand.NextDouble();
        }
        if (File.Exists(filename)) File.Delete(filename);
        try
        {
            using (BinaryWriter writer = new BinaryWriter(File.Open(filename,
           FileMode.Create)))
            {
                for (int j = 0; j < length; j++)
                    writer.Write(data[j]);
            }
        }
        catch (IOException ex)
        {
            Console.WriteLine(ex.ToString());
        }
    }
    public FileStream fs { get; set; }
    public override double this[int index]
    {
        get
        {
            Byte[] data = new Byte[8];
            fs.Seek(8 * index, SeekOrigin.Begin);
            fs.Read(data, 0, 8);
            double result = BitConverter.ToDouble(data, 0);
            return result;
        }
    }
    public override void Swap(int j, double a)
    {
        Byte[] data = new Byte[16];
        BitConverter.GetBytes(a).CopyTo(data, 0);
        fs.Seek(8 * (j + 1), SeekOrigin.Begin);
        fs.Write(data, 0, 8);
    }
}

这是我的数组插入排序:

public static void InsertionSort(DataArray items)
    {
        double key;
        int j;
        for (int i = 1; i < items.Length; i++)
        {
            key = items[i];
            j = i - 1;
            while (j >= 0 && items[j] > key)
            {
                items.Swap(j, items[j]);
                j = j - 1;
            }
            items.Swap(j, key);

        }
    }

现在我必须以某种方式做同样的事情 - 但是使用单链表,我可以使用这种类(允许进行更改):

class MyFileList : DataList
{
    int prevNode;
    int currentNode;
    int nextNode;
    public MyFileList(string filename, int n, int seed)
    {
        length = n;
        Random rand = new Random(seed);
        if (File.Exists(filename)) File.Delete(filename);
        try
        {
            using (BinaryWriter writer = new BinaryWriter(File.Open(filename,
           FileMode.Create)))
            {
                writer.Write(4);
                for (int j = 0; j < length; j++)
                {
                    writer.Write(rand.NextDouble());
                    writer.Write((j + 1) * 12 + 4);
                }
            }
        }
        catch (IOException ex)
        {
            Console.WriteLine(ex.ToString());
        }
    }
    public FileStream fs { get; set; }
    public override double Head()
    {
        Byte[] data = new Byte[12];
        fs.Seek(0, SeekOrigin.Begin);
        fs.Read(data, 0, 4);
        currentNode = BitConverter.ToInt32(data, 0);
        prevNode = -1;
        fs.Seek(currentNode, SeekOrigin.Begin);
        fs.Read(data, 0, 12);
        double result = BitConverter.ToDouble(data, 0);
        nextNode = BitConverter.ToInt32(data, 8);
        return result;
    }
    public override double Next()
    {

        Byte[] data = new Byte[12];
        fs.Seek(nextNode, SeekOrigin.Begin);
        fs.Read(data, 0, 12);
        prevNode = currentNode;
        currentNode = nextNode;
        double result = BitConverter.ToDouble(data, 0);
        nextNode = BitConverter.ToInt32(data, 8);
        return result;
    }

老实说-我不确定我应该如何实现插入排序,也不确定如何将其转换为外部排序。我以前使用此代码不进行外部排序:

       public override void InsertionSort()
    {
        sorted = null;
        MyLinkedListNode current = headNode;
        while (current != null)
        {
            MyLinkedListNode next = current.nextNode;
            sortedInsert(current);
            current = next;
        }
        headNode = sorted;
    }

    void sortedInsert(MyLinkedListNode newnode)
    {
        if (sorted == null || sorted.data >= newnode.data)
        {
            newnode.nextNode = sorted;
            sorted = newnode;
        }
        else
        {
            MyLinkedListNode current = sorted;
            while (current.nextNode != null && current.nextNode.data < newnode.data)
            {
                current = current.nextNode;
            }
            newnode.nextNode = current.nextNode;
            current.nextNode = newnode;
        }
    }

因此,如果有人可以提供某种提示/解释 - 或者如果你曾经尝试过这个 - 如何解决此类问题的代码示例,将不胜感激!

4

1 回答 1

1

实际上,我最近已经解决了这个问题。

这是您可以使用的代码示例,它应该可以开箱即用。

public class SortLinkedList {

 public static class LinkListNode {
    private Integer value;
    LinkListNode nextNode;

    public LinkListNode(Integer value, LinkListNode nextNode) {
        this.value = value;
        this.nextNode = nextNode;
    }

    public Integer getValue() {
        return value;
    }

    public void setValue(Integer value) {
        this.value = value;
    }

    public LinkListNode getNextNode() {
        return nextNode;
    }

    public void setNextNode(LinkListNode nextNode) {
        this.nextNode = nextNode;
    }

    @Override
    public String toString() {
        return this.value.toString();
    }
}

public static void main(String...args) {
    LinkListNode f = new LinkListNode(12, null);
    LinkListNode e = new LinkListNode(11, f);
    LinkListNode c = new LinkListNode(13, e);
    LinkListNode b = new LinkListNode(1, c);
    LinkListNode a = new LinkListNode(5, b);
    print(sort(a));
}


public static void print(LinkListNode aList) {
    LinkListNode iterator = aList;
    while (iterator != null) {
        System.out.println(iterator.getValue());
        iterator = iterator.getNextNode();
    }
}

public static LinkListNode sort(LinkListNode aList){
    LinkListNode head = new LinkListNode(null, aList);
    LinkListNode fringePtr = aList.getNextNode();
    LinkListNode ptrBeforeFringe = aList;
    LinkListNode findPtr;
    LinkListNode prev;
    while(fringePtr != null) {
        Integer valueToInsert = fringePtr.getValue();
        findPtr = head.getNextNode();
        prev = head;
        while(findPtr != fringePtr) {
            System.out.println("fringe=" + fringePtr);
            System.out.println(findPtr);
            if (valueToInsert <= findPtr.getValue()) {
                LinkListNode tmpNode = fringePtr.getNextNode();
                fringePtr.setNextNode(findPtr);
                prev.setNextNode(fringePtr);
                ptrBeforeFringe.setNextNode(tmpNode);
                fringePtr = ptrBeforeFringe;
                break;
            }
            findPtr = findPtr.getNextNode();
            prev = prev.getNextNode();
        }
        fringePtr = fringePtr.getNextNode();
        if (ptrBeforeFringe.getNextNode() != fringePtr) {
            ptrBeforeFringe = ptrBeforeFringe.getNextNode();
        }
    }
    return head.getNextNode();
 }
}

从高层次来看,您正在做的是跟踪边缘 ptr,并且您正在插入一个节点 st,它位于相应子列表中的正确位置。

例如,假设我有这个 LL。

3->2->5->4

第一次迭代,我在 2 处有 fringePtr,并且我想在子列表中边缘 ptr 之前的某个位置插入 2,所以我基本上从 head 开始遍历到边缘 ptr,直到该值小于当前值。我还有一个对前一个 ptr 的先前跟踪(为了说明 null,我在遍历开始时有一个哨兵节点,所以我可以将它插入到头部)。

然后,当我看到它小于当前时,我知道我需要将它插入到上一个旁边,所以我必须:

  1. 使用临时 ptr 来跟踪我以前的当前下一个。
  2. 将 previuos 绑定到我的 toInsert 节点旁边。
  3. 将我的 toInsert 节点绑定到我的临时节点旁边。

然后,要继续,你只需推进你的边缘 ptr 并重试,基本上建立一个子列表,当你移动时排序,直到边缘到达末尾。

即迭代看起来像

1. 3->2->5->4
      ^
2. 2->3->5->4
         ^
3. 2->3->5->4
            ^
4. 2->3->4->5 FIN.
于 2018-02-08T03:27:21.443 回答