我正在用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);
}
}
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
我认为可能有多个错误，但是我发现了一个问题，并且我认为这会导致重复的值，发生在您进行交换时。
似乎节点以以下格式存储在二进制文件中：偏移到头节点，节点值（一个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函数中，它仅从文件中读取下一个节点，而基本上忽略了链表偏移。然后问题出在交换功能中。它有点混合使用方法1和方法2。它使用文件中的偏移量，但也交换它们。交换功能从文件读取和写入6个字节（5个值字节和到下一个节点的偏移量的第一个字节）。因此，它正在更改偏移量和值。如果将其更改为仅读取5个字节，则它将仅更改值。
您需要确保所有代码在使用链表时都保持一致。是要使用链表偏移量，还是要假设头节点始终位于偏移量4，下一个节点始终位于偏移量13？
正如我在开始时提到的，可能还有其他问题，但是我相信这是导致重复值的问题。