使用链表进行堆排序时出现错误

Question

我正在用C#为链表编写堆排序算法，遇到了一个似乎无法解决的错误。基本上，它不是对列表进行正确排序，而是复制一些元素并删除其他元素。结果是一个与原始长度相同的列表，但缺少和重复的元素，并且没有正确排序。我已经尝试修复这个错误很长一段时间了，但还没有成功。有人能帮我找出问题吗？

提前感谢！

这是相关代码：

MyFileList类：

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);
}
}

程序.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

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

节点似乎存储在以下格式的二进制文件中：偏移到head节点、节点值(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？

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