Сравнение работы двух таблиц идентификаторов

@ashsvis · Регистрация: 08.10.2018

Студворк — интернет-сервис помощи студентам

Нужно организовать две таблицы идентификаторов, одну - методом цепочек, другую - методом бинарного дерева,
загрузить в каждую таблицу до 200 идентификаторов с длиной каждого не более 32 символов и
сделать подсчет среднего числа выполненных операций сравнения:
- при размещении нового идентификатора,
- при поиске заданного пользователем идентификатора.

Идеи будут?

@ashsvis · 20.03.2019, 08:53 **[ТС]**

Так как у нас две таблицы, то нужно два класса.
Начнем с "бинарного дерева":

Кликните здесь для просмотра всего текста

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
using System;
 
namespace CompIdentModel
{
    /// <summary>
    /// Таблица идентификаторов типа "Бинарное дерево"   
    /// </summary>
    public class BinaryTreeTable
    {
        public int AddCount { get; private set; } = 0;
        public int AddCompareCount { get; private set; } = 0;
        public int SeekCount { get; private set; } = 0;
        public int SeekCompareCount { get; private set; } = 0;
 
        public BinaryNode HeadNode { get; set; }    // головной узел
        public BinaryNode CurrentNode { get; set; } // текущий узел
 
        /// <summary>
        /// Добавление нового идентификатора
        /// </summary>
        /// <param name="name">Новый идентификатор</param>
        /// <param name="content">Связанные с идентификатором данные (общий вид)</param>
        public void AddNode(string name, object content)
        {
            AddCount++;
            // шаг 1. Первый идентификатор помещается в вершину дерева
            if (HeadNode == null) { HeadNode = new BinaryNode { Name = name, Content = content }; return; }
            // шаг 2. Сделать текущим узлом дерева корневую вершину
            CurrentNode = HeadNode;
            while (true)
            {
                BinaryNode item;
                // шаг 3. Сравнить очередной идентификатор с идентификатором, содержащимся в текущем узле дерева
                AddCompareCount++;
                switch (string.Compare(name, CurrentNode.Name))
                {
                    case 0:  // если очередной идентификатор равен текущему
                        throw new Exception("Двух одинаковых идентификаторов быть не должно!");
                    case -1: // шаг 4. Если очередной идентификатор меньше                        
                        if (CurrentNode.LeftNode != null) // шаг 5. Если у текущего узла существует левая вершина
                        {
                            CurrentNode = CurrentNode.LeftNode; // то сделать ее текущим узлом
                            continue; // и вернуться к шагу 3
                        }
                        // шаг 6. Создать новую вершину, поместить в нее очередной идентификатор, 
                        item = new BinaryNode { Name = name, Content = content };
                        // сделать эту новую вершину левой вершиной текущего узла
                        CurrentNode.LeftNode = item;
                        // и вернуться
                        return;
                    case 1: // шаг 7. Если очередной идентификатор больше
                        if (CurrentNode.RightNode != null) // если у текущего узла существует правая вершина
                        {
                            CurrentNode = CurrentNode.RightNode; // то сделать ее текущим узлом
                            continue; // и вернуться к шагу 3
                        }
                        // шаг 8. Создать новую вершину, поместить в нее очередной идентификатор, 
                        item = new BinaryNode { Name = name, Content = content };
                        // сделать эту новую вершину правой вершиной текущего узла
                        CurrentNode.RightNode = item;
                        // и вернуться
                        return;
                }
            }
        }
 
        /// <summary>
        /// Поиск нужного элемента по идентификатору в дереве
        /// </summary>
        /// <param name="name">Идентификатор для поиска</param>
        /// <returns>Найденный узел</returns>
        public BinaryNode SeekNode(string name)
        {
            SeekCount++;
            // шаг 1. Сделать текущим узлом дерева корневую вершину
            CurrentNode = HeadNode;
            while (true)
            {
                // шаг 2. Сравнить очередной идентификатор с идентификатором, содержащимся в текущем узле дерева
                SeekCompareCount++;
                switch (string.Compare(name, CurrentNode.Name))
                {
                    case 0:  // шаг 3. Если идентификаторы совпадают, то искомый идентификатор найден
                        return CurrentNode;
                    case -1: // шаг 4. Если очередной идентификатор меньше                        
                        if (CurrentNode.LeftNode != null) // шаг 5. Если у текущего узла существует левая вершина
                        {
                            CurrentNode = CurrentNode.LeftNode; // то сделать ее текущим узлом
                            continue; // и вернуться к шагу 2
                        }
                        return null;
                    case 1: // шаг 6. Если очередной идентификатор больше
                        if (CurrentNode.RightNode != null) // если у текущего узла существует правая вершина
                        {
                            CurrentNode = CurrentNode.RightNode; // то сделать ее текущим узлом
                            continue; // и вернуться к шагу 2
                        }
                        return null;
                }
            }
 
        }
    }
 
    public class BinaryNode
    {
        public string Name { get; set; }
        public BinaryNode LeftNode { get; set; }
        public BinaryNode RightNode { get; set; }
        public object Content { get; set; }
    }
}

@ashsvis · 20.03.2019, 17:57 **[ТС]**

Продолжим с "методом цепочек"

Кликните здесь для просмотра всего текста

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
using System;
using System.Linq;
 
namespace CompIdentModel
{
    /// <summary>
    /// Таблица идентификаторов типа "Метод цепочек" 
    /// </summary>
    public class HashLinkTable
    {
        private LinkItem[] hashtable = new LinkItem[256];
        public int AddCount { get; private set; } = 0;
        public int AddCompareCount { get; private set; } = 0;
        public int SeekCount { get; private set; } = 0;
        public int SeekCompareCount { get; private set; } = 0;
 
        public LinkItem[] GetItems()
        {
            return hashtable.ToArray();
        }
 
        /// <summary>
        /// Добавление нового идентификатора
        /// </summary>
        /// <param name="name">Новый идентификатор</param>
        /// <param name="content">Связанные с идентификатором данные (общий вид)</param>
        public void AddItem(string name, object content)
        {
            AddCount++;
            // шаг 1. Получаем хеш идентификатора
            var key = GetHash(name);
            // шаг 2. Если место в хеш-таблице свободно
            AddCompareCount++;
            if (hashtable[key] == null)
            {
                // шаг 3. Добавляем идентификатор и данные в таблицу
                hashtable[key] = new LinkItem { Name = name, Content = content };
                return; // выходим
            }
            else
            {
                // шаг 4. Получаем ссылку на уже записанный в таблицу идентификатор
                var item = hashtable[key];
                if (item.Name == name) // если очередной идентификатор равен текущему
                    throw new Exception("Двух одинаковых идентификаторов быть не должно!");
                // шаг 5. Ищем в цепочке последний элемент (с пустой ссылкой на следующий элемент)
                while (item.LinkToItem != null)
                {
                    AddCompareCount++;
                    item = item.LinkToItem;
                }
                // шаг 6. Создаем и добавляем в цепочку новый идентификатор
                item.LinkToItem = new LinkItem { Name = name, Content = content };
            }
        }
 
        /// <summary>
        /// Поиск нужного элемента по идентификатору в таблице
        /// </summary>
        /// <param name="name">Идентификатор для поиска</param>
        /// <returns>Найденный элемент</returns>
        public LinkItem SeekItem(string name)
        {
            SeekCount++;
            // шаг 1. Получаем хеш идентификатора
            var key = GetHash(name);
            // шаг 2. Если место в хеш-таблице свободно
            SeekCompareCount++;
            if (hashtable[key] == null)
            {
                // шаг 3. Идентификатор в таблице не найден
                return null; // выходим
            }
            else
            {
                // шаг 4. Получаем ссылку на уже записанный в таблицу идентификатор
                var item = hashtable[key];
                if (item.Name == name) // если очередной идентификатор равен текущему
                    return item; // идентификатор в таблице найден, выходим
                // шаг 5. Ищем в цепочке последний элемент (с пустой ссылкой на следующий элемент)
                while (item.LinkToItem != null)
                {
                    SeekCompareCount++;
                    item = item.LinkToItem;
                    if (item.Name == name) // если идентификатор в цепочке равен искомому
                        return item; // идентификатор в таблице найден, выходим
                }
                // шаг 6. Создаем и добавляем в цепочку новый идентификатор
                return item; // идентификатор в таблице найден, выходим
            }
        }
 
        /// <summary>
        /// Эта функция будет вычислять нам хеш идентификатора
        /// </summary>
        /// <param name="name"></param>
        /// <returns></returns>
        private byte GetHash(string name)
        {
            var r = (byte)0xff;
            for (var i = 0; i < name.Length; i++)
            {
                var dat = (byte)name[i];
                for (var j = 0; j < 8; j++)
                {
                    var aux = (dat ^ r) & 0x01;
                    if (aux == 1) r = (byte)(r ^ 0x18);
                    r = (byte)(r >> 1);
                    r = (byte)(r | (aux << 7));
                    dat = (byte)(dat >> 1);
                }
            }
            return r;
        }
    }
 
    public class LinkItem
    {
        public string Name { get; set; }
        public object Content { get; set; }
        public LinkItem LinkToItem { get; set; }
        public override string ToString()
        {
            return Name;
        }
    }
}

Для алгоритма расчёта хеш-функции взял расчёт контрольной суммы для контроллера "Метакон"

Результат работы программы:

Сравнение работы двух таблиц идентификаторов

Ну, и сама программа, для тех, кому это необходимо: CompIdentTables.zip

@ashsvis · 23.03.2019, 09:10 **[ТС]**

Добавим для сравнения третью таблицу - "простой односвязный список"

Кликните здесь для просмотра всего текста

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
using System;
 
namespace CompIdentModel
{
    /// <summary>
    /// Таблица идентификаторов типа "Простой список" 
    /// </summary>
    public class SimpleLinkTable
    {
        public int AddCount { get; private set; } = 0;
        public int AddCompareCount { get; private set; } = 0;
        public int SeekCount { get; private set; } = 0;
        public int SeekCompareCount { get; private set; } = 0;
 
        public LinkItem HeadItem { get; set; }    // головной элемент
        public LinkItem CurrentItem { get; set; } // текущий элемент
 
        /// <summary>
        /// Добавление нового идентификатора в простой список
        /// </summary>
        /// <param name="name">Новый идентификатор</param>
        /// <param name="content">Связанные с идентификатором данные (общий вид)</param>
        public void AddItem(string name, object content)
        {
            AddCount++;
            // шаг 1. Первый идентификатор помещается в вершину списка
            if (HeadItem == null) { HeadItem = new LinkItem { Name = name, Content = content }; return; }
            // шаг 2. Сделать текущим элементом списка вершину списка
            CurrentItem = HeadItem;
            AddCompareCount++;
            if (CurrentItem.Name == name) // если очередной идентификатор равен текущему
                throw new Exception("Двух одинаковых идентификаторов быть не должно!");
            // шаг 3. Ищем в цепочке последний элемент (с пустой ссылкой на следующий элемент)
            while (CurrentItem.LinkToItem != null)
            {
                CurrentItem = CurrentItem.LinkToItem;
                AddCompareCount++;
                if (CurrentItem.Name == name) // если очередной идентификатор равен текущему
                    throw new Exception("Двух одинаковых идентификаторов быть не должно!");
            }
            // шаг 4. Создаем и добавляем в цепочку новый идентификатор
            CurrentItem.LinkToItem = new LinkItem { Name = name, Content = content };
        }
 
        /// <summary>
        /// Поиск нужного элемента по идентификатору в простом списке
        /// </summary>
        /// <param name="name">Идентификатор для поиска</param>
        /// <returns>Найденный элемент</returns>
        public LinkItem SeekItem(string name)
        {
            SeekCount++;
            // шаг 1. Первый идентификатор помещается в вершину списка
            if (HeadItem == null) return null;  // идентификатор в списке не найден
            // шаг 2. Сделать текущим элементом списка вершину списка
            CurrentItem = HeadItem;
            AddCompareCount++;
            if (CurrentItem.Name == name) // если очередной идентификатор равен текущему
                return CurrentItem; // идентификатор в списке найден, выходим
            // шаг 3. Ищем в цепочке последний элемент (с пустой ссылкой на следующий элемент)
            while (CurrentItem.LinkToItem != null)
            {
                CurrentItem = CurrentItem.LinkToItem;
                SeekCompareCount++;
                if (CurrentItem.Name == name) // если идентификатор в списке равен искомому
                    return CurrentItem; // выходим
            }
            return null; // шаг 4. Идентификатор в списке не найден, выходим
        }
    }
}

где элемент списка LinkItem будет таким же, как в "методе цепочек".
Результат работы программы:

Модифицированная программа, для тех, кому это необходимо: CompIdent3Tables.zip

@ashsvis · 23.03.2019, 13:05 **[ТС]**

Для удобства сравнения отставим в приложении два метода - "Бинарное дерево" и "Простой список"
Форма теперь выглядит так:

И содержимое проекта для этого случая: CompIdent2Tables.zip

Новые блоги и статьи Все статьи Все блоги /
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	Влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .

@ashsvis 923 / 503 / 202 Регистрация: 08.10.2018 Сообщений: 1,553 Записей в блоге: 11

	Сравнение работы двух таблиц идентификаторов 19.03.2019, 19:14. Показов 1127. Ответов 4 Метки бинарное дерево, идентификаторы, метод цепочек (Все метки) Нужно организовать две таблицы идентификаторов, одну - методом цепочек, другую - методом бинарного дерева, загрузить в каждую таблицу до 200 идентификаторов с длиной каждого не более 32 символов и сделать подсчет среднего числа выполненных операций сравнения: - при размещении нового идентификатора, - при поиске заданного пользователем идентификатора. Идеи будут? 0

@ashsvis 923 / 503 / 202 Регистрация: 08.10.2018 Сообщений: 1,553 Записей в блоге: 11
	23.03.2019, 13:05 [ТС]
	Для удобства сравнения отставим в приложении два метода - "Бинарное дерево" и "Простой список" Форма теперь выглядит так: И содержимое проекта для этого случая: CompIdent2Tables.zip 1