30 / 11 / 5
Регистрация: 01.03.2014
Сообщений: 377
1

Реализовать алгоритм организации и обработки информации с помощью В-деревьев

03.03.2016, 16:55. Показов 361. Ответов 0
Метки нет (Все метки)

Добрый день форумчане.
Появилась необходимость реализовать алгоритм организации и обработки информации с помощью В-деревьев.

Исходные данные: файл с данными, в котором требуется выполнить поиск, вставку и удаление записей на базе В-деревьев (ибо считаю это самым сложным).

Для начала предполагаю, что файл пустой поэтому хочу научиться вставлять в него данные. Изучив соотвествующую литературу получилось что-то такое:
Кликните здесь для просмотра всего текста

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
 
namespace ipr2
{
    
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }
 
        // Структура дерева
        public struct BTree
        {
            public int  t;      // минимальная степень дерева
            public Node root;   // указатель на корень дерева
        }
        
        // Структура узла
        public struct Node
        {
            public bool leaf;  // является ли узел листом
            public int n;      // количество ключей узла
            public int[] key;  // ключи узла
            public Node[] c;   // указатели на детей узла
        }
 
        // Создание пустого дерева
        public void Creat()
        {
            // Создаю узел
            BTree X = new BTree();
            X.root.leaf = true;
            X.root.n = 0;
            // Делаю узел корнем
            BTree T = new BTree();
            T.t = 2;
            T.root = X.root;
        }
 
        /* Метод Split получает в качестве входного параметра незаполненный внутренний узел X  
        * и  ин*декс i, такой, что узел X.Ci является заполненным дочерним узлом X.
        * Метод разбивает дочерний узел на два и со*ответствующим образом обновляет поля X, внося в него  
        * информацию о новом дочернем узле. Для разбиения заполненного корневого узла сначала делаем 
        * корень дочерним узлом нового пустого корневого узла, после чего можем исполь*зовать вызов Split.
        * При этом высота дерева увеличивается на 1.*/
        public void Split(BTree X, int i)
        {
            Node Z = new Node();
            Node Y = new Node();
            Y = X.root.c[i];
            Z.leaf = Y.leaf;
            Z.n = X.t-1;
            for (int j = 1; j < (X.t - 1); j++)
            {
                Z.key[j] = Y.key[j + X.t];
            }
            if (Y.leaf == false)
            {
                for (int j = 1; j < X.t; j++)
                {
                    Z.c[j] = Y.c[j + X.t];
                }
                Y.n = X.t - 1;
            }
            for (int j = X.root.n; j < i + 1; j--)
            {
                X.root.c[j + 1] = X.root.c[j];
            }
            X.root.c[i + 1] = Z;
            for (int j=X.root.n; j<i; j--)
            {
                X.root.key[j + 1] = X.root.key[j];
            }
            X.root.key[i] = Y.key[X.t];
            X.root.n = X.root.n + 1;
        }
 
        /* Вставка ключа k в дерево Т. Метод Insert использу*ет метод SPLIT для гарантии того, что
         * рекурсия никогда не столкнется с заполненным узлом.*/
        public void Insert(BTree T, int k)
        {
            BTree R = new BTree();
            R.root = T.root;
            if (R.root.n==(2*T.t-1))
            {
                BTree S = new BTree();
                T.root = S.root;
                S.root.leaf = false;
                S.root.n = 0;
                S.root.c[1] = R.root;
                Split(S, 1);
                InsertN(S, k);
                InsertN(R, k);
            }
        }
 
        /* Вспомогательный рекурсивный метод InsertN  вставля*ет  ключ  k в  узел  X, 
         * который при вызове метода должен быть незаполнен*ным.  
         * Операции Insert и InsertN гарантируют, что это условие незаполненности будет выполнено.*/
        public void InsertN(BTree X, int k)
        {
            int i = X.root.n;
            if (X.root.leaf == true)
            {
                while ((i >= 1) & (k < X.root.key[i]))
                {
                    X.root.key[i + 1] = X.root.key[i];
                    i--;
                }
                X.root.key[i + 1] = k;
                X.root.n++;
 
            }
            else
            {
                while ((i >= 1) & (k < X.root.key[i]))
                {
                    i--;
                }
                i++;
                if (X.root.c[j].n == 2 * X.t - 1)
                {
                    Split(X, i);
                    if (k > X.root.key[i])
                    {
                        i++;
                    }
                    InsertN(X, k); //!!!
                }
            }
        }
 
 
    }
}

Буду рад любой помощи.

Добавлено через 17 часов 40 минут
Всё ещё мучаюсь со своей проблемой.
Такая ситуация:
C#
1
2
3
// Корень B-дерева
   BTree root = new BTree();
   root = CreatRoot(records[0].Key);
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
        // Структура узла
        public struct Node
        {
            public bool leaf;  // является ли узел листом
            public int n;      // количество ключей узла
            public int [] key   // ключи узла
            {
                get 
                {
                    return new int[3]{-1,-1,-1};
                }
            }
            public Node[] c   // указатели на детей узла
            {
                get 
                {
                    return new Node[4];
                }
            }
        }
C#
1
2
3
4
5
6
7
8
9
10
        // Создание корня дерева
        public BTree CreatRoot(int key)
        {
            BTree X = new BTree();
            X.root.leaf = true;
            X.root.n = 1;
            X.root.key[0] = key;
            X.t = 2;
            return X;
        }
records это объект типа List <Record> содержит пару Key,Value.
records[0].Key принимает значение типа int
далее выполняется метод CreatRoot(int key)
Но в строке
C#
1
            X.root.key[0] = key;
X.root.key[0] не присваивается никакое значение. При отладке по этой строке прохожу, но ничего не происходит.

В чем может быть проблема?
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.03.2016, 16:55
Ответы с готовыми решениями:

почему именно сортировка очень важна при организации обработки информации
почему именно сортировка очень важна при организации обработки информации?

Разработка системы сбора, хранения и обработки необходимой информации с функцией рекламы деятельности организации
Всем привет! Перейду сразу к делу, есть Тех.задание, которое я приведу ниже: НАЗНАЧЕНИЕ...

Реализовать передачу - прием информации. С одного ПК на другой, реализовать нужна с помощью (winapi с++). Нужна информация или книги
Необходимо реализовать передачу - прием информации. С одного ПК на другой, реализовать нужна с...

Реализовать нейросетевой алгоритм обработки сигналов
подскажите как

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.03.2016, 16:55
Помогаю со студенческими работами здесь

Реализовать алгоритм обработки текстового файла
Привет уважаемому сообществу! Нужно обработать 12 ГБ логов, задача одноразовая, хочу сделать это...

Придумать и реализовать алгоритм шифрования текста (использовать функции обработки символов и строк)
5)Придумать и реализовать алгоритм шифрования текста (использовать функции обработки символов и...

деревья. программы обработки деревьев
Моя тема &quot;деревья. программы обработки деревьев&quot;. Вопрос такой: какие программы вы бы...

Как реализовать алгоритм для вычисления корней уравнения (tg) с помощью метода простой итерации?
Необходимо найти корень уравнения tg(1,5773х) – 2,3041х = 0 с заданной точностью с помощью метода...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru