#c# #arrays #recursion #stack-overflow #binary-search
Вопрос:
Я пытаюсь выполнить поиск по нескольким индексам строк, используя рекурсивный двоичный поиск из массива строк. Однако мое приложение попало в stackoverflowexception и достигло точки останова. Что я делаю неправильно; Я воспроизвел поток рекурсивности в своем уме, казалось, все было в порядке, но я понятия не имею, почему это не работает. Было ли слишком много кода? Любая альтернатива / решение / помощь будут оценены.
код:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.Security.Cryptography;
using System.Text.RegularExpressions;
namespace ProjectNumeroUno
{
internal class Program
{
public static int BinSearch(int[] array, int first, int last, int item)
{
if (first <= last)
{
int middle = (int)Math.Ceiling((decimal)((first last) / 2));
if (array[middle] == item)
return middle;
if (array[middle] > item)
{
first = middle - 1;
return BinSearch(array, first, last, item);
}
if (array[middle] < item)
{
last = middle 1;
return BinSearch(array, first, last, item);
}
}
return -1;
}
static void Main(string[] args)
{
string path = @"D:ytraddijyhcnuap.txt";
string[] vs = { }, site = { }, usrnme = { }, pass = { };
int[] num = { }, m = { };
List<int> mList = new List<int>();
List<int> numhList= new List<int>();
List<string> list = new List<string>(vs.ToList());
Console.Write("Welcome to your personal password database.nData will be protected, and cannot be accessed directly.nVery personalized and secure!nn1. New Data entryn2. Display (latest → oldest) and searchn3. Clear password listn4. ExitnEnter your option: ");
string option = Console.ReadLine();
while (option != "4")
{
if (option == "1")
{
Console.Write("Enter website: ");
string url = Console.ReadLine();
Console.Write("Enter username: ");
string usr = Console.ReadLine();
Console.Write("Enter password: ");
string pwd = Console.ReadLine();
string mmm = url "Ψ" usr "Ψ" pwd;
using (Aes Entry = Aes.Create())
{
Entry.Key = Encoding.Default.GetBytes(new string('j', 16));
Entry.IV = Encoding.Default.GetBytes(new string('j', 16));
byte[] encrypted = EncryptionOfContent(mmm, Entry.Key, Entry.IV);
using (StreamWriter sw = File.AppendText(path))
{
sw.WriteLine(Convert.ToBase64String(encrypted));
}
}
}
else if (option == "2")
{
vs = new string[0];
Console.Write("n");
try
{
var lineData = File.ReadAllLines(path);
foreach (var data in lineData)
{
using (Aes entry = Aes.Create())
{
entry.Key = Encoding.Default.GetBytes(new string('j', 16));
entry.IV = Encoding.Default.GetBytes(new string('j', 16));
string decrypted = DecryptionOfContent(Convert.FromBase64String(data), entry.Key, entry.IV);
list.Add(decrypted);
}
}
vs = list.ToArray();
}
catch (IOException e)
{
Console.WriteLine("The file could not be read due to:");
Console.WriteLine(e.Message);
}
num = new int[vs.Length];
site = new string[vs.Length];
usrnme = new string[vs.Length];
pass = new string[vs.Length];
m = new int[] { };
for (int i = 0; i < vs.Length; i )
{
vs[i] = ((i 1) "Ψ" vs[i]);
}
for (int i = 0;i < vs.Length; i )
{
string[] split = vs[i].Split('Ψ');
num[i] = int.Parse(split[0]);
}
for (int i = 0; i < num.Length - 1; i )
{
int max = i;
for (int j = i 1; j < num.Length; j )
{
if (num[j] > num[max])
{
max = j;
}
}
if (max != i)
{
int tempi = num[i];
var tempv = vs[i];
num[i] = num[max];
vs[i] = vs[max];
num[max] = tempi;
vs[max] = tempv;
}
}
for (int i = 0; i < vs.Length; i )
{
string[] split = vs[i].Split('Ψ');
site[i] = split[1];
usrnme[i] = split[2];
pass[i] = split[3];
}
string A = "No.";
string B = "Site";
string C = "Username";
string D = "Password";
Console.WriteLine("{0,-10} {1,-20} {2,-20} {3,-0}", A, B, C, D);
for (int i = 0;i < vs.Length; i )
{
Console.WriteLine("{0,-10} {1,-20} {2,-20} {3,-0}", num[i], site[i], usrnme[i], pass[i]);
}
Console.Write("n");
Console.Write("Enter the website that you want to search: ");
string site2search = Console.ReadLine();
foreach (string s in site)
{
if (s == site2search)
{
mList.Add(Array.IndexOf(site, s));
}
}
m = mList.ToArray();
foreach (int s in m)
{
numhList.Add(BinSearch(num, 0, num.Length - 1, s 1));
}
int[] numh = numhList.ToArray();
Console.WriteLine("{0,-10} {1,-20} {2,-20} {3,-0}", A, B, C, D);
for (int i = 0; i < numh.Length; i )
{
Console.WriteLine("{0,-10} {1,-20} {2,-20} {3,-0}", num[i], site[i], usrnme[i], pass[i]);
}
Console.Write("n");
}
Console.Write("n1. New Data entryn2. Display (latest → oldest) and searchn3. Clear password listn4. ExitnEnter your option: ");
option = Console.ReadLine();
}
}
static byte[] EncryptionOfContent(string plainText, byte[] Key, byte[] IV)
{
// Check arguments.
if (plainText == null || plainText.Length <= 0)
throw new ArgumentNullException("plainText");
if (Key == null || Key.Length <= 0)
throw new ArgumentNullException("Key");
if (IV == null || IV.Length <= 0)
throw new ArgumentNullException("IV");
byte[] encrypted;
// Create an Aes object
// with the specified key and IV.
using (Aes aesAlg = Aes.Create())
{
aesAlg.Key = Key;
aesAlg.IV = IV;
// Create an encryptor to perform the stream transform.
ICryptoTransform encryptor = aesAlg.CreateEncryptor(aesAlg.Key, aesAlg.IV);
// Create the streams used for encryption.
using (MemoryStream msEncrypt = new MemoryStream())
{
using (CryptoStream csEncrypt = new CryptoStream(msEncrypt, encryptor, CryptoStreamMode.Write))
{
using (StreamWriter swEncrypt = new StreamWriter(csEncrypt))
{
//Write all data to the stream.
swEncrypt.Write(plainText);
}
encrypted = msEncrypt.ToArray();
}
}
}
// Return the encrypted bytes from the memory stream.
return encrypted;
}
static string DecryptionOfContent(byte[] cipherText, byte[] Key, byte[] IV)
{
// Check arguments.
if (cipherText == null || cipherText.Length <= 0)
throw new ArgumentNullException("cipherText");
if (Key == null || Key.Length <= 0)
throw new ArgumentNullException("Key");
if (IV == null || IV.Length <= 0)
throw new ArgumentNullException("IV");
// Declare the string used to hold
// the decrypted text.
string plaintext = null;
// Create an Aes object
// with the specified key and IV.
using (Aes aesAlg = Aes.Create())
{
aesAlg.Key = Key;
aesAlg.IV = IV;
// Create a decryptor to perform the stream transform.
ICryptoTransform decryptor = aesAlg.CreateDecryptor(aesAlg.Key, aesAlg.IV);
// Create the streams used for decryption.
using (MemoryStream msDecrypt = new MemoryStream(cipherText))
{
using (CryptoStream csDecrypt = new CryptoStream(msDecrypt, decryptor, CryptoStreamMode.Read))
{
using (StreamReader srDecrypt = new StreamReader(csDecrypt))
{
// Read the decrypted bytes from the decrypting stream
// and place them in a string.
plaintext = srDecrypt.ReadToEnd();
}
}
}
}
return plaintext;
}
}
}
ввод:
first set → google, 1, 1
second set → google 2, 2
third set → stackoverflow 3, 3
fourth set → stackoverflow 4, 4
fifth set → NoN-Existent, 69, 69
Ожидаемый ввод-вывод: если бы я искал «stackoverflow», я должен был бы получить оба входных сигнала ‘stackoverflow 3, 3’ и ‘stackoverflow 4, 4’, и наоборот, но, как уже было сказано, он попал в переполнение smh.
Ответ №1:
Рассмотрим случай, когда first = 0 и last = 1 . (first last) / 2) становится 1 / 2 , и поскольку это целочисленное деление, результатом будет 0 , если вы не хотите целочисленное деление, 2.0 вместо этого разделите на. Потолок нуля равен нулю, и предполагается array[0] < item , что мы снова вызываем метод с last = middle 1 помощью , т.е. 1 . Таким образом, метод будет выполняться снова с идентичными параметрами, что в конечном итоге приведет к переполнению стека.
Я не уверен, что это именно та проблема, с которой вы столкнулись, вполне возможно, что есть другие проблемы с кодом. Это была самая очевидная проблема, которую я заметил.
Простым решением было бы использовать Array .Вместо этого выполняется двоичный поиск, но я бы предположил, что это какое-то назначение. Если это так, я бы посоветовал научиться использовать отладчик, см. раздел Как отлаживать небольшие программы. Это должно позволить вам пошагово выполнить программу для ввода некоторого примера и проверить, что каждый шаг дает ожидаемый результат. Это бесценный навык для начинающих программистов.