Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
0 / 0 / 0
Регистрация: 01.05.2019
Сообщений: 2
1

Программа вылетает с ошибкой нарушения прав доступа при чтении при заполнении дерева более чем 50 элементами

02.05.2019, 10:49. Просмотров 685. Ответов 3
Метки нет (Все метки)

Приветствую всех.
Задание: Для древовидных структур данных предусмотреть вывод характеристик сбалансированности дерева (средняя длина ветви) и процедуру выравнивания (балансировки).
{Двоичное дерево в динамическом массиве с вычисляемыми индексами потомков (2n и 2n+1). Для хранении текста (слов) используется динамический массив указателей char**.}
Проблема заключается в том,что при вводе более 50 элементов вылетает ошибка доступа при чтении (Вызвано исключение по адресу 0x0FABEA12 (ucrtbased.dll) в KypcoBa9_6_3.exe: 0xC0000005: нарушение прав доступа при чтении по адресу 0xDDDDDDDD.) на строке 56
C++
1
if (strcmp(ss, p[n]) < 0)
А мне необходимо чтобы программа могла принимать более 10 000 элементов для измерения времени работы. Буду признателен, если подскажите в чём проблема.
Полный код программы:
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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
//#define _CRT_SECURE_NO_WARNINGS
 
#include "pch.h"
#include <iostream>
#include <string>
#include <locale> 
#include <Windows.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h> 
#pragma warning(disable : 4996)
using namespace std;
 
 
 
// Двоичное дерево в массиве (массив указателей на строки)
 
struct btree {
    char **p; // дерево в массиве указателей на строки
    int sz; // текущая размерность массива
 
    void init() {
        sz = 10;
        p = new char*[sz]; // NULL-указатель для свободной вершины
        for (int i = 0; i < sz; i++) p[i] = NULL;
    }
 
    //-- Число вершин в поддереве
 
    int size(int n) {
        if (n >= sz || p[n] == NULL) return 0;
        return 1 + size(2 * n) + size(2 * n + 1);
    }
 
    //-- Поиск вершины по логическому номеру
 
    char *get_n(int m, int n) {
        if (m >= sz || m >= size(n)) return NULL;
        int ll = size(2 * n); // число вершин в левом поддереве
        if (m < ll) return get_n(m, 2 * n); // ЛН в левом поддереве
        m -= ll; // отбросить вершины левого поддерева
        if (m-- == 0) return p[n]; // ЛН – номер текущей вершины
        return get_n(m, 2 * n + 1); // в правое поддерево с остатком ЛН
    }
 
    // Включение с сохранением порядка
 
    void insert(int n, char *ss) {
        if (n >= sz) { // увеличение размерности при выходе
            sz *= 2; // за пределы массива
            p = (char**)realloc(p, sz * sizeof(char*));
            for (int i = sz / 2; i < sz; i++) p[i] = NULL; // с обнулением новой части
        }
        if (p[n] == NULL) { p[n] = ss; return; } // свободная вершина - включение
        if (strcmp(ss, p[n]) < 0)
            insert(2 * n, ss); // выбор левого или правого поддерева
        else // в зависимости от результата сравнения
            insert(2 * n + 1, ss);
    }
 
    // вывод дерева
    void print() {
        for (int i = 0; i < sz; i++) {
            if (p[i] != NULL)
                cout << p[i] << endl;
            else
                cout << "NULL" << endl;
        }
    }
 
    // балансировка дерева
 
    void balance() {
        for (int i = 0; i < sz; i++) {
            if (p[i] == NULL) {
                for (int j = i + 1; j < sz; j++) {
                    if (p[j] != NULL) {
                        p[i] = p[j];
                        p[j] = new char[100];
                        p[j] = NULL;
                        break;
                    }
                }
            }
        }
    }
 
    // глубина дерева
 
    int LvL() {
        int Level = 1;
        int k = 0;
        int conttLeft = 0, countRight = 0;
        double n = 1;
        while (n < 10) {
            k++;
            int num = pow(2.0, k) - 1;
            int kk = pow(2.0, k) / 2;
            for (int i = num; i < num + kk; i++) {
                if (i >= sz)
                    break;
                if (p[i] != NULL || p[i] == "0xfdfdfdfd") {
                    conttLeft++;
 
                }
 
            }
            for (int i = num + kk; i < num + kk * 2; i++) {
                if (i >= sz)
                    break;
                if (p[i] != NULL || p[i] == "0xfdfdfdfd") {
                    countRight++;
 
                }
 
            }
            n = num + kk * 2 + 1;
 
        }
                    
        return abs(countRight - conttLeft);
    }
 
};
 
 
 
 
int main()
{
    //unsigned int start_time = clock();
    setlocale(LC_ALL, "Rus");
    btree El;
    El.init();
    int k;
    /*do {
        int index;
        cout << "Введите индекс" << endl;
        cin >> index;
        char *name2 = new char[50];
 
        cout << "Введите строку" << endl;
        cin >> name2;
 
        cout << endl;
        El.insert(index, name2);
        cout << "Ввести значение? 1 - да; 2 - нет" << endl;
        cin >> k;
 
 
    } while (k == 1);*/
    srand(time(0));
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        int k = rand() % N ;
        char name2[] =  "stroka";
        El.insert(k, name2);
    }
 
 
    int f = El.LvL();
    cout << "до" << f << endl;
 
    El.print();
    cout << endl << endl;
    unsigned int start_time = clock();
    El.balance();
    unsigned int end_time = clock();
    f = El.LvL();
    cout << "после" << f << endl;
    El.print();
    //unsigned int end_time = clock();
    cout << "Время выполнения: "<< end_time - start_time << "мс" << endl;
    system("pause");
 
    return 0;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.05.2019, 10:49
Ответы с готовыми решениями:

Нарушения прав доступа при чтении
Добрый день. Возникла проблема: Во время отладки программы возникает ошибка:...

Нарушения прав доступа при чтении
Всем доброй ночи! Пишу курсовую и появилась проблема: нарушения прав доступа при чтении. Проверил...

Ошибка нарушения прав доступа при чтении по адресу, возникающая при инициализации трехмерного массива
Очень нужна ваша помощь! Я уже не знаю что тут можно сделать. Код части программы, где вылазит...

При заполнении двумерного динамического массива выдает ошибку "нарушения прав доступа"
#include&lt;iostream&gt; using namespace std; int main() { int sizeC, sizeS; cout &lt;&lt;...

3
3505 / 1965 / 824
Регистрация: 07.02.2019
Сообщений: 5,273
02.05.2019, 10:55 2
kiri0n, а разве можно реаллочить то, что выделено с помощью new?
0
716 / 654 / 123
Регистрация: 10.08.2015
Сообщений: 2,847
02.05.2019, 11:52 3
Тебя обманули - это не дерево. дерево это как минимум:
C++
1
2
3
4
5
6
7
8
9
10
11
12
class BinTree {
public:
    BinTree(){/*конструктор*/};
    ~BinTree(){/* деструктор */};
    int Add(int num){/*добавить*/};
private:
    struct Node {
        int value;
        Node* left ;
        Node* right;
    }* root;
};
0
0 / 0 / 0
Регистрация: 01.05.2019
Сообщений: 2
02.05.2019, 11:56  [ТС] 4
vlisp ,Честно говоря я практически сам это чудо написал. И был очень рад,что оно хоть как то да работает. Но вот вылезла такая проблема и не знаю как её решить. Я так понимаю проще переписать полностью чем пытаться исправлять?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.05.2019, 11:56

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Программа тасовки колоды карт: Нарушение прав доступа при чтении по адресу
Всем доброго времени суток. Помогите найти ошибку. Ни на что не ругается, просто выдает ошибку. ...

Не работает чтение из файла, не могу понять в чём ошибка (нарушение прав доступа при чтении по адресу 0xCDCDCDD5)
#include &quot;pch.h&quot; #include &lt;iostream&gt; #include &lt;string&gt; #include &lt;fstream&gt; #include...

Нарушения прав доступа при записи. Исключение
Здравствуйте! Выскочило исключение - с таким исключением впервые стыкаюсь. Что это и почему оно...

Нарушения прав доступа при записи(не в файл).
Вот такая проблемка есть: char* ret=&quot;&quot;; __asm { lea esi,ret; mov eax,0x34; inc...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.