链表堆排序中的错误

Question

我正在用 C# 为链表编写堆排序算法，遇到了一个我似乎无法解决的错误。基本上发生的事情不是正确排序列表，而是复制一些元素并删除其他元素。结果是一个与原始长度相同但缺少和重复元素且排序不正确的列表。我已经尝试修复该错误已有一段时间了，但尚未成功。谁能帮我发现问题？

提前致谢！

相关代码如下：

我的文件列表class:

using System;
using System.Collections.Generic;
using System.Text;
using System.IO;

namespace Lab1
{
    class MyFileList : DataList
    {
        int prevNode;
        int currentNode;
        int nextNode;

        public MyFileList(string filename, int n)
        {
            length = n;
            Random rand = new Random();

            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++)
                    {
                        char c = (char)rand.Next('a', 'z');
                        int ri = (int)rand.Next();
                        Element e = new Element(c, ri);
                        writer.Write(e.partOne);
                        writer.Write(e.partTwo);
                        writer.Write((j + 1) * 9 + 4); 
                    }
                }
            }
            catch (IOException ex)
            {
                Console.WriteLine(ex.ToString());
            }
        }
        public FileStream fs { get; set; }
        public override Element Head()
        {
            BinaryReader br = new BinaryReader(fs);
            prevNode = -1;
            br.BaseStream.Seek(0, SeekOrigin.Begin); 
            currentNode = br.ReadInt32();
            br.BaseStream.Seek(currentNode, SeekOrigin.Begin);
            char c = (char)br.ReadChar();
            int i = br.ReadInt32();


            Element result = new Element(c, i);
            nextNode = br.ReadInt32();
            return result;
        }
        public override Element Next()
        {
            prevNode = currentNode;
            currentNode = nextNode;
            BinaryReader br = new BinaryReader(fs);
            char c = (char)br.ReadChar(); 
            int i = br.ReadInt32(); 
            Element result = new Element(c, i);
            nextNode = br.ReadInt32(); 
            return result;

        }

        public override Element returnAtIndex(int index)
        {
            //int tempcurrent = currentNode; int tempprev = prevNode; int tempnext = nextNode;

            Element result = Head();
            for (int i = 0; i < index; i++)
            {
                result = Next();
            }

            //Console.WriteLine(prevNode);

            //currentNode = tempcurrent; prevNode = tempprev; nextNode = tempnext;

            return result;
        }

        public override void Swap(int index1, int index2)
        {
            Byte[] data1 = new Byte[6];
            Byte[] data2 = new Byte[6];
            Element e = null;
            BinaryReader br = new BinaryReader(fs);
            BinaryWriter bw = new BinaryWriter(fs);

            Head();
            for (int i = 0; i < index1; i++)
                Next();
            br.BaseStream.Seek(currentNode, SeekOrigin.Begin);
            br.BaseStream.Read(data1, 0, 6);

            Head();
            for (int i = 0; i < index2; i++)
                Next();
            br.BaseStream.Seek(currentNode, SeekOrigin.Begin);
            br.BaseStream.Read(data2, 0, 6);

            Console.WriteLine();


            Head();
            for (int i = 0; i < index1; i++)
                Next();
            bw.BaseStream.Seek(currentNode, SeekOrigin.Begin);
            bw.Write(data2, 0, 6);

            Head();
            for (int i = 0; i < index2; i++)
                Next();
            bw.BaseStream.Seek(currentNode, SeekOrigin.Begin);
            bw.Write(data1, 0, 6);
        }

        public int findNodeofElement(Element e)
        {
            Element elem = Head();
            for (int i = 0; i < length; i++)
            {
                elem = Next();
                if (elem.partOne == e.partOne && elem.partTwo == e.partTwo) break;

            }
            return currentNode;
        }

        public override void setValues(Element e)
        {
            BinaryWriter bw = new BinaryWriter(fs);
            bw.BaseStream.Seek(currentNode, SeekOrigin.Begin);
            bw.Write(e.partOne);
            bw.Write(e.partTwo);
        }

    }

Program.cs:

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

namespace Lab1
{
    class Program
    {
        static void Main(string[] args)
        {
            int seed = (int)DateTime.Now.Ticks & 0x0000FFFF;


            rikiavimas(10);

        }


        public static void rikiavimas(int n)
        {
            string filename = @"test1.txt";
            MyFileList myfilelist = new MyFileList(filename, n);
            using (myfilelist.fs = new FileStream(filename, FileMode.Open, FileAccess.ReadWrite))
            {
                Console.WriteLine("\n *****FILE LIST***** \n");
                myfilelist.Print(n);
                PerformHeapSort(myfilelist); 
                Console.WriteLine("\n *****SORTED FILE LIST***** \n");
                myfilelist.Print(n); 
            }
        }

        public static void PerformHeapSort(MyFileList arr)
        {
            int heapSize = arr.Length - 1;
            BuildHeap(arr);
            for (int i = arr.Length - 1; i >= 0; i--) 
            {
               Console.WriteLine("********* " + i);
                if (i!= 0) arr.Swap(0, i);
                heapSize--;
                Heapify(arr, 0);
            } 
        }

        private static void BuildHeap(MyFileList arr)
        {
            int heapSize = arr.Length - 1;
            for (int i = heapSize / 2; i >= 0; i--) 
            {
                Heapify(arr, i);
            }
        }
        private static void Heapify(MyFileList arr, int index)
        {
            int heapSize = arr.Length - 1;
            int left = 2 * index;
            int right = 2 * index + 1;
            int largest = index;

            Element elmLeft = null; Element elmRight = null;
            if (left <= heapSize) elmLeft = arr.returnAtIndex(left);
            if (right <= heapSize) elmRight = arr.returnAtIndex(right);
            Element elmLargest = arr.returnAtIndex(largest);

            if (left <= heapSize && elmLeft > elmLargest) //index
            {
                largest = left;
            }

            if (right <= heapSize && elmRight > elmLargest)
            {
                largest = right;
            }

            if (largest != index)
            {
               if (index != largest) arr.Swap(index, largest);
                Console.WriteLine("*******index is " + index + " largest is " + largest);
                Heapify(arr, largest);
            }
        }



    }

    abstract class DataList
    {
        protected int length;
        public int Length { get { return length; } }
        public abstract Element Head();
        public abstract Element Next();
        //public abstract Element Previous();
        public abstract Element returnAtIndex(int index);
        //public abstract Element returnAtIndex(int index);
        public abstract void Swap(Element a, Element b);
        public abstract void Swap(int index1, int index2);
        public abstract void setValues(Element e);
        //public abstract void Append ()
        //public abstract void PerformHeapSort(DataList list);
        public void Print(int n)
        {

            Element head = Head();
            Console.Write(head.partOne);
            Console.WriteLine(head.partTwo);
            for (int i = 1; i < n; i++)
            {
                Element elem = Next();
                Console.Write(elem.partOne);
                Console.WriteLine(elem.partTwo);
            }
            Console.WriteLine();

        }

    } 

    class Element
    {
        public char partOne;
        public int partTwo;

        public Element (char c, int i)
        {
            partOne = c;
            partTwo = i;
        }

        public void PrintInt()
        {
            Console.WriteLine(partTwo);
        }

        public void PrintChar()
        {
            Console.WriteLine(partOne);
        }

        public static bool operator < (Element e1, Element e2)
        {
            if (e1.partOne < e2.partOne) return true;
            else if (e1.partOne == e2.partOne && (e1.partTwo < e2.partTwo)) return true;
            else return false;
        }

        public static bool operator > (Element e1, Element e2)
        {
            if (e1.partOne > e2.partOne) return true;
            else if (e1.partOne == e2.partOne && (e1.partTwo > e2.partTwo)) return true;
            else return false;
        }
    }
}

这是我在运行此代码时得到的输出示例：

 *****FILE LIST*****

j849146725
q569436044
r1645801130
p1861344598
k886292186
a852479939
v1166576825
j1180639416
v1227743602
y739268292

 *****SORTED FILE LIST*****

v1227743602
v1227743602
j1180639416
p1861344598
r1645801130
a852479939
y739268292
r1645801130
q569436044
j849146725

Answer 1

我认为可能存在多个错误，但我发现了一个问题，我认为这是导致重复值的原因，发生在您进行交换时。

节点似乎以以下格式存储在二进制文件中：到头节点的偏移量、节点值（一个 char 和一个 int）和到下一个节点的偏移量所以像这样：

04 00 00 00 67 D0 DB 2C 0E 0D 00 00 00

0x00000004 is the offset to the head node
0x67D0DB2C0E is the head node value (0x67 is the char 'g' and 0x0E2CDBD0 is the int)
0x0000000D is the offset to the next node

我看到了两种使用链表的方法：1) 从不更改链表偏移量而只是交换值或 2) 将值保留在原处并更新链表偏移量以交换值。看起来您正在尝试在 Print 和 Next 函数中使用第一种方法。例如，在您的 Next 函数中，它只是从文件中读取下一个节点，基本上忽略了链表偏移量。然后问题出现在您的 Swap 函数中。它有点混合使用方法 1 和方法 2。它使用文件中的偏移量，但它也在交换它们。 Swap 函数从文件中读取和写入 6 个字节（5 个值字节和到下一个节点的偏移量的第一个字节）。所以它正在改变偏移量和值。如果您将其更改为仅读取 5 个字节，那么它只会更改值。

您需要确保所有代码在使用链表的方式上保持一致。它会使用链表偏移量还是假设头节点始终位于偏移量 4，下一个节点位于偏移量 13？

正如我在一开始提到的，可能还有其他问题，但我相信这是导致重复值的原因。

链表堆排序中的错误

Bug in Heap Sort with Linked List

c#

linked-list

heapsort