Я пишу алгоритм сортировки кучи для связанного списка в 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