Как сделать список с простым перебором? - C#
Формулировка задачи:
требуется написать программу, которая получает на входе набор идентификаторов, организует таблицу по заданному методу и позволяет осуществить поиск идентификатора в этой таблице. Список идентификаторов считать заданным в виде текстового файла. Длину идентификаторов можно считать ограниченной 32 символами.
Для организации таблицы используется простейшая хэш-функция, указанная в варианте задания, а при возникновении коллизий используется дополнительный метод размещения идентификаторов в памяти. Если в качестве этого метода используется дерево или список, то они должны быть связаны с элементом главной хэш-таблицы.
В каждом варианте требуется, чтобы программа сообщала среднее число коллизий и среднее количество сравнений, выполненных для поиска идентификатора.
тип хеш-функции - Сумма кодов первой и средней букв.
способ разрешения коллизий - список с простым перебором.
Вот мой код, как сделать список с простым перебором и вместо последней буквы, суммировать среднюю?
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using System.IO; namespace ConsoleApplication11 { class Program { public struct city { public string name; public int hash; public city(string name1, int hash1) { name = name1; hash = hash1; } } static void Main(string[] args) { StreamReader readfile = File.OpenText("spisok.txt"); string input = null; List<city> CityList = new List<city>(); while ((input = readfile.ReadLine()) !=null) { city CITY = new city(input, (int)input[0] + (int)input.Last()); CityList.Add(CITY); } Console.WriteLine("==========="); Console.WriteLine("чтение завершено"); Console.WriteLine(); Console.WriteLine("в итоге {0} городов", CityList.Count); Console.WriteLine("==========="); Console.ReadLine(); for (int i = 0; i < CityList.Count; i++) { Console.WriteLine("{0}) Город: {1} |Хеш:{2}", i + 1, CityList[i].name, CityList[i].hash); } Console.ReadLine(); } } }
Решение задачи: «Как сделать список с простым перебором?»
textual
Листинг программы
using System; using System.Collections.Generic; struct City { public readonly string Name; public City(string Name = "") { this.Name = Name; } public override int GetHashCode() { return string.IsNullOrEmpty(Name) ? 0 : Name[0] + Name[Name.Length / 2]; } public override string ToString() { return Name; } public static City Empty { get { return new City(); }} } struct StorageFinder { public City City; public int Index; public int Hash; public List<City> List; public int NewCollisions; public StorageFinder(Storage Storage, string Key) { NewCollisions = 0; City = new City(Key); Hash = City.GetHashCode(); List = Storage.Table[Hash] ?? (Storage.Table[Hash] = new List<City>()); for (Index = 0; Index < List.Count; Index++) if (List[Index].Equals(City)) break; if (Index == List.Count) { List.Add(City); if (List.Count == 2) NewCollisions = 2; if (List.Count > 2) NewCollisions = 1; } } } class Storage { // хэш таблица public readonly List<City>[] Table = new List<City>[255 * 2]; // Число коллизий public int Collisions = 0; // Число сравнений public int Сomparison = 0; public int ComparisonCount = 0; void Log(StorageFinder Finder) { Collisions += Finder.NewCollisions; Сomparison += Finder.Index + 1; ComparisonCount++; } public City this[string Key] { get { var finder = new StorageFinder(this, Key); Log(finder); return finder.List[finder.Index]; } set { var finder = new StorageFinder(this, Key); Log(finder); finder.List[finder.Index] = value; } } public void Load(string data) { foreach(string key in data.Split()) this[key] = new City(key); } } class Program { static void Main(string[] args) { Storage storage = new Storage(); storage.Load("aab aac aad abc"); // тестовый поиск: Console.WriteLine(storage["aad"]); Console.WriteLine("Коллизии: {0}", storage.Collisions); Console.WriteLine("Среднее число сравнений: {0,2}", (float)storage.Сomparison / storage.ComparisonCount); Console.ReadKey(); } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д