Как сделать список с простым перебором? - 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();
    }
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

14   голосов , оценка 4.357 из 5
Похожие ответы