Форум программистов, компьютерный форум CyberForum.ru

Таблицы прямого доступа в С++ - C++

Восстановить пароль Регистрация
 
VASYA_A
2 / 2 / 0
Регистрация: 11.09.2013
Сообщений: 129
12.10.2013, 10:53     Таблицы прямого доступа в С++ #1
Здравствуйте ! Нужно разобраться с таблицами прямого доступа . После прочтения теории я понял немногое:
например , вот мы создаём массив и 5-ти значений
C++
1
int A[5]={5,12,3,724,9}
дальше нужно создать таблицу прямого доступа в которой будет 725 элементов(от 0 индекса до 724, определяется по наибольшей цифре)
C++
1
int Tabl[725]={  , , ,3, ,5, , , , 9, , ,12......,724
получается , что на месте 3-го индекса должна стоять 3-ка , на месте 5-то стоит 5-ка и т.д. , а на пустых значениях стоит, например , -1 .
затем вводим ключ и ищем этот ключ в таблице .
если ключ в таблице не равен -1 , то выводим этот ключ.

Это я так понял ..но мне не понятно с реализацией : вот создали массив , а как создать для него таблицу прямого доступа ? как заполнить её значениями ???
Помогите , пожалуйста , разобраться ! Буду очень благодарен Вашей помощи !!!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
12.10.2013, 11:03     Таблицы прямого доступа в С++ #2
Цитата Сообщение от VASYA_A Посмотреть сообщение
а как создать для него таблицу прямого доступа ?
Находите в массиве максимальное число, создаёте динамический массив, размером на единицу больше этого числа.
VASYA_A
2 / 2 / 0
Регистрация: 11.09.2013
Сообщений: 129
12.10.2013, 11:20  [ТС]     Таблицы прямого доступа в С++ #3
Цитата Сообщение от alsav22 Посмотреть сообщение
Находите в массиве максимальное число, создаёте динамический массив, размером на единицу больше этого числа.
Вот , создал:
C++
1
2
3
4
5
6
7
8
9
int mas[5]={5,28,3,724,9};
  int max=0;
  for(int i=0;i<5;i++)
  {if(mas[i]>max)
   max=mas[i];
  }
  int *T=new int[max+1];
  for(int i=0;i<max+1;i++)
  {*(T+i)=-1;}
Я заполнил пока все значения таблицы значениями -1.
А как дальше работать с этой таблицей? Нужно вручную записывать на каждый индекс значения из нашего массива?
C++
1
2
3
4
5
T[3]=3;
T[5]=5;
T[9]=9;
T[28]=28;
T[724]=724
Правильно ли это?
Может я что-то не так понимаю..просто очень мало информации есть про ТПД.
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
12.10.2013, 11:22     Таблицы прямого доступа в С++ #4
Цитата Сообщение от VASYA_A Посмотреть сообщение
Нужно вручную записывать на каждый индекс значения из нашего массива?
Можно не вручную:
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
#include <iostream>
#include <cstdlib>
using namespace std;
 
int max(int *A, int n)
{
    int max = A[0];
    for (int i = 1; i < n; ++i)
    {
        if (max < A[i]) max = A[i];
    }
 
    return max;
}
 
int main()
{
    int A[5] = {5, 12, 3, 724, 9};
    
    int size = max(A, 5);
    ++size;
    int *arr = new int[size];
 
    for (int i = 0; i < size; ++i)
        arr[i] = -1;
 
    for (int i = 0; i < 5; ++i)
        arr[A[i]] = A[i];
 
    system("pause");
    return 0;
}
VASYA_A
2 / 2 / 0
Регистрация: 11.09.2013
Сообщений: 129
12.10.2013, 11:30  [ТС]     Таблицы прямого доступа в С++ #5
Цитата Сообщение от alsav22 Посмотреть сообщение
Можно не вручную:
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
#include <iostream>
#include <cstdlib>
using namespace std;
 
int max(int *A, int n)
{
    int max = A[0];
    for (int i = 1; i < n; ++i)
    {
        if (max < A[i]) max = A[i];
    }
 
    return max;
}
 
int main()
{
    int A[5] = {5, 12, 3, 724, 9};
    
    int size = max(A, 5);
    ++size;
    int *arr = new int[size];
 
    for (int i = 0; i < size; ++i)
        arr[i] = -1;
 
    for (int i = 0; i < 5; ++i)
        arr[A[i]] = A[i];
 
    system("pause");
    return 0;
}
можете вот эти строчки объяснить , пожалуйста ?
C++
1
2
for (int i = 0; i < 5; ++i)
        arr[A[i]] = A[i];
я так понимаю , это замена моему ручному присваиванию элемента индексу в таблице?
но немного не понимаю алгоритм написаного
почему i<5 ?
таблица же у нас до 724 индекса?
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
12.10.2013, 11:44     Таблицы прямого доступа в С++ #6
Цитата Сообщение от VASYA_A Посмотреть сообщение
можете вот эти строчки объяснить ,
C++
1
2
for (int i = 0; i < 5; ++i)
        arr[A[i]] = A[i];
В массив arr, по индексу, равному значению элемента в массиве A, записывается значение этого элемента
VASYA_A
2 / 2 / 0
Регистрация: 11.09.2013
Сообщений: 129
12.10.2013, 12:00  [ТС]     Таблицы прямого доступа в С++ #7
Цитата Сообщение от alsav22 Посмотреть сообщение
C++
1
2
for (int i = 0; i < 5; ++i)
        arr[A[i]] = A[i];
В массив arr, по индексу, равному значению элемента в массиве A, записывается значение этого элемента
Спасибо большое. С массивом разобрался.
А вот если работать , например , с массивом структур ? Как для него создать таблицу прямого доступа?
В структуре Data есть 3 поля , поиск осуществляется по полю а.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct A{
int a;
int b;
int c;
}
Set(ob1,N)               //заполнение структуры
{for(int i=0;i<N;i++)
 {ob1[i].a=i;
   ob1[i].b=i+1;
   ob1[i].c=i+2;
}
}
 
int main()
{ int N=3;
 Data *ob1=new Data[N];
  Set(ob1,N);
getch();
return 0;}
Я вот не могу понять , как работать с массивом структур..Как создать ТПД для поля а?
Можете объяснить , пожалуйста?
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
12.10.2013, 12:07     Таблицы прямого доступа в С++ #8
Цитата Сообщение от VASYA_A Посмотреть сообщение
Как создать ТПД для поля а?
Находите самое большое значение поля а и т.д.:
Цитата Сообщение от alsav22 Посмотреть сообщение
создаёте динамический массив, размером на единицу больше этого числа.
и т.д.
VASYA_A
2 / 2 / 0
Регистрация: 11.09.2013
Сообщений: 129
12.10.2013, 12:22  [ТС]     Таблицы прямого доступа в С++ #9
Цитата Сообщение от alsav22 Посмотреть сообщение
Находите самое большое значение поля а и т.д.:

и т.д.
то есть, нужно так:
C++
1
2
3
4
5
6
7
8
int max=0;   //макс.значения поля а
for(int i;i<N;i++)
{if(max>ob1[i].a)
max=ob1[i].a;
}
 
++max;
int *Table=new int [max];    //cоздание ТПД
Добавлено через 11 минут
Цитата Сообщение от VASYA_A Посмотреть сообщение
то есть, нужно так:
C++
1
2
3
4
5
6
7
8
int max=0;   //макс.значения поля а
for(int i;i<N;i++)
{if(max>ob1[i].a)
max=ob1[i].a;
}
 
++max;
int *Table=new int [max];    //cоздание ТПД
я потом заполняю этот массив -1.
C++
1
2
3
int *T=new int[max];
for(int i=0;i<max;i++)
{*(T+1)=-1;}
А как записать элементы структуры по индексу в этот массив? ( так , как это делалось в массиве) ?
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
12.10.2013, 13:19     Таблицы прямого доступа в С++ #10

Не по теме:

Л/с получили?



Добавлено через 21 минуту
У вас несколько задача расплылась. По структурам задачу нужно по-новой сформулировать. То, что приводилось, как пример, в первом посте, здесь уже, как я понимаю, не подходит.

Добавлено через 1 минуту
Что вы собираетесь хранить в таблице? Какое-то поле структуры? Сами структуры?
VASYA_A
2 / 2 / 0
Регистрация: 11.09.2013
Сообщений: 129
12.10.2013, 13:34  [ТС]     Таблицы прямого доступа в С++ #11
Цитата Сообщение от alsav22 Посмотреть сообщение

Не по теме:

Л/с получили?



Добавлено через 21 минуту
У вас несколько задача расплылась. По структурам задачу нужно по-новой сформулировать. То, что приводилось, как пример, в первом посте, здесь уже, как я понимаю, не подходит.
Есть массив структур . Нужно для него создать ТПД и выполнить поиск по одному полю.
Вот пробую сделать так, но когда нахожу максимальный элемент , то программа прерывается на этом моменте.
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
#include "stdafx.h"
#include <iostream>
#include <conio.h>
using namespace std;
struct Data
{int kod;
 int type;
 int kol;
 int p;
};
 
void Set(Data *ob1,int N)              //функция автоматического заполнения массива структур
{   for(int i=0;i<N;i++)
{   ob1[i].kod=i+1;
    ob1[i].type=i+2;
    ob1[i].kol=i+3;
    ob1[i].p=i+4;
}
}
void Show(Data *ob1,int N)           //функция вывода на экран массива структур
{for(int i=0;i<N;i++)
{cout<<"\n ";
cout<<ob1[i].kod<<" ";
cout<<ob1[i].type<<" ";
cout<<ob1[i].kol<<" ";
cout<<ob1[i].p<<" ";
cout<<"\n  ";
}
}
int _tmain(int argc, _TCHAR* argv[])
{ int N;
 cout<<"\n Enter N:";
 cin>>N;
 Data *ob1=new Data[N];
 Set(ob1,N);  //заполнение массива структур
 Show(ob1,N);  //вывод  массива структур
 int max;   //максимальное значение поля kod
 for(int i=0;i<N;i++)
 {  if(max>ob1[i].kod)
    max=ob1[i].kod;
 }
 
max=max+1;
int *T=new int[max];
for(int i=0;i<max;i++)
{*(T+1)=-1;}
 
for(int i=0;i<N;i++)
{T[ob1[i].kod]=ob1[i].kod;
}
getch();
return 0;
}
Что я делаю не так? Помогите , пожалуйста , понять .

Добавлено через 13 минут
Цитата Сообщение от alsav22 Посмотреть сообщение

Не по теме:

Л/с получили?



Добавлено через 21 минуту
У вас несколько задача расплылась. По структурам задачу нужно по-новой сформулировать. То, что приводилось, как пример, в первом посте, здесь уже, как я понимаю, не подходит.

Добавлено через 1 минуту
Что вы собираетесь хранить в таблице? Какое-то поле структуры? Сами структуры?
Как я понимаю , то нужно хранить в таблице искомое поле структуры, а размер уже задавать исходя из максимального значения этого поля( как и при работе с массивом )
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
12.10.2013, 13:38     Таблицы прямого доступа в С++ #12
Для начала max инициализируйте.
VASYA_A
2 / 2 / 0
Регистрация: 11.09.2013
Сообщений: 129
12.10.2013, 13:42  [ТС]     Таблицы прямого доступа в С++ #13
Цитата Сообщение от alsav22 Посмотреть сообщение
Для начала max инициализируйте.
то есть , присвоить ему 0?
C++
1
int max=0
или нужно этот max как-то связать с искомым полем kod?
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
12.10.2013, 13:52     Таблицы прямого доступа в С++ #14
У вас там напутано с поиском max.
C++
1
2
3
4
5
6
int max = ob1[0].kod;   //максимальное значение поля kod
for(int i = 1; i < N; i++)
{  
    if(max < ob1[i].kod)
    max = ob1[i].kod;
}
Добавлено через 5 минут
Цитата Сообщение от VASYA_A Посмотреть сообщение
Как я понимаю , то нужно хранить в таблице искомое поле структуры, а размер уже задавать исходя из максимального значения этого поля( как и при работе с массивом )
Задача какая? Найти структуру, в которой есть искомое поле? Или?
VASYA_A
2 / 2 / 0
Регистрация: 11.09.2013
Сообщений: 129
12.10.2013, 13:59  [ТС]     Таблицы прямого доступа в С++ #15
Цитата Сообщение от alsav22 Посмотреть сообщение
У вас там напутано с поиском max.
C++
1
2
3
4
5
6
int max = ob1[0].kod;   //максимальное значение поля kod
for(int i = 1; i < N; i++)
{  
    if(max < ob1[i].kod)
    max = ob1[i].kod;
}
Добавлено через 5 минут

Задача какая? Найти структуру, в которой есть искомое поле? Или?
У меня есть входные данные:kod,type,kol,p
ключ-это kod
организовать поиск по ключу , используя таблицу прямого доступа
Вот такая вот задача.
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
12.10.2013, 14:23     Таблицы прямого доступа в С++ #16
Цитата Сообщение от VASYA_A Посмотреть сообщение
Вот такая вот задача.
Задача туманна.
Цитата Сообщение от VASYA_A Посмотреть сообщение
организовать поиск по ключу
Поиск чего? Стркутуры с таким полем? Если поиск по kod, то зачем, во входных данных, ещё type, kol, p?

Добавлено через 1 минуту
Если искать в таблице структруру по kod:
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
//#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <iomanip>
using namespace std;
 
struct Data
{
    int kod;
    int type;
    int kol;
    int p;
};
 
void Set(Data *ob1, int N)              //функция автоматического заполнения массива структур
{   
    for(int i = 0; i < N; i++)
    {   
        ob1[i].kod  = i + 1;
        ob1[i].type = i + 2;
        ob1[i].kol  = i + 3;
        ob1[i].p    = i + 4;
    }
}
void Show(Data *ob1, int N)           //функция вывода на экран массива структур
{
    for(int i = 0; i < N; i++)
    {
        cout << "\n";
        cout << setw(3) << ob1[i].kod;
        cout << setw(3) << ob1[i].type;
        cout << setw(3) << ob1[i].kol;
        cout << setw(3) << ob1[i].p;
        cout << "\n";
    }
}
 
int main()
{ 
    int N;
    cout << "\n Enter N:";
    cin >> N;
    Data *ob1 = new Data[N];
    Set(ob1, N);  //заполнение массива структур
    Show(ob1, N);  //вывод  массива структур
    int max = ob1[0].kod;   //максимальное значение поля kod
    for(int i = 1; i < N; i++)
    {  
        if(max < ob1[i].kod)
        max = ob1[i].kod;
    }
 
    max = max + 1;
    Data *T = new Data[max];
    for(int i = 0; i < max; i++)
    {
        T[i].kod  = -1;
        T[i].type = -1;
        T[i].kol  = -1;
        T[i].p    = -1;
    }
 
    for(int i = 0; i < N; i++)
    {
        T[ob1[i].kod] = ob1[i];
    }
    
    cout << endl;
    for (int i = 0; i < max; ++i)
        Show(&T[i], 1);
 
    getch();
    return 0;
}
VASYA_A
2 / 2 / 0
Регистрация: 11.09.2013
Сообщений: 129
12.10.2013, 14:29  [ТС]     Таблицы прямого доступа в С++ #17
Цитата Сообщение от alsav22 Посмотреть сообщение
Задача туманна.

Поиск чего? Стркутуры с таким полем? Если поиск по kod, то зачем, во входных данных, ещё type, kol, p?

Добавлено через 1 минуту
Если искать в таблице структруру по kod:
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
//#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <iomanip>
using namespace std;
 
struct Data
{
    int kod;
    int type;
    int kol;
    int p;
};
 
void Set(Data *ob1, int N)              //функция автоматического заполнения массива структур
{   
    for(int i = 0; i < N; i++)
    {   
        ob1[i].kod  = i + 1;
        ob1[i].type = i + 2;
        ob1[i].kol  = i + 3;
        ob1[i].p    = i + 4;
    }
}
void Show(Data *ob1, int N)           //функция вывода на экран массива структур
{
    for(int i = 0; i < N; i++)
    {
        cout << "\n";
        cout << setw(3) << ob1[i].kod;
        cout << setw(3) << ob1[i].type;
        cout << setw(3) << ob1[i].kol;
        cout << setw(3) << ob1[i].p;
        cout << "\n";
    }
}
 
int main()
{ 
    int N;
    cout << "\n Enter N:";
    cin >> N;
    Data *ob1 = new Data[N];
    Set(ob1, N);  //заполнение массива структур
    Show(ob1, N);  //вывод  массива структур
    int max = ob1[0].kod;   //максимальное значение поля kod
    for(int i = 1; i < N; i++)
    {  
        if(max < ob1[i].kod)
        max = ob1[i].kod;
    }
 
    max = max + 1;
    Data *T = new Data[max];
    for(int i = 0; i < max; i++)
    {
        T[i].kod  = -1;
        T[i].type = -1;
        T[i].kol  = -1;
        T[i].p    = -1;
    }
 
    for(int i = 0; i < N; i++)
    {
        T[ob1[i].kod] = ob1[i];
    }
    
    cout << endl;
    for (int i = 0; i < max; ++i)
        Show(&T[i], 1);
 
    getch();
    return 0;
}
спасибо , я примерно так и делал .
но что это означает ?
C++
1
 Show(&T[i], 1);
что за 1 ? и зачем нужен амперсанд?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.10.2013, 14:35     Таблицы прямого доступа в С++
Еще ссылки по теме:

C++ Нечетные элементы массива отсортировать методом пузырька, а четные методом прямого доступа
Сортировка методом прямого включения C++

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

Или воспользуйтесь поиском по форуму:
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
12.10.2013, 14:35     Таблицы прямого доступа в С++ #18
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
//#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <iomanip>
using namespace std;
 
struct Data
{
    int kod;
    int type;
    int kol;
    int p;
};
 
void Set(Data *ob1, int N)              //функция автоматического заполнения массива структур
{   
    for(int i = 0; i < N; i++)
    {   
        ob1[i].kod  = i + 1;
        ob1[i].type = i + 2;
        ob1[i].kol  = i + 3;
        ob1[i].p    = i + 4;
    }
}
void Show(Data *ob1, int N)           //функция вывода на экран массива структур
{
    for(int i = 0; i < N; i++)
    {
        cout << "\n";
        cout << setw(3) << ob1[i].kod;
        cout << setw(3) << ob1[i].type;
        cout << setw(3) << ob1[i].kol;
        cout << setw(3) << ob1[i].p;
        cout << "\n";
    }
}
 
int main()
{ 
    int N;
    cout << "\n Enter N:";
    cin >> N;
    Data *ob1 = new Data[N];
    Set(ob1, N);  //заполнение массива структур
    Show(ob1, N);  //вывод  массива структур
    int max = ob1[0].kod;   //максимальное значение поля kod
    for(int i = 1; i < N; i++)
    {  
        if(max < ob1[i].kod)
        max = ob1[i].kod;
    }
 
    max = max + 1;
    Data *T = new Data[max];
    for(int i = 0; i < max; i++)
    {
        T[i].kod  = -1;
        T[i].type = -1;
        T[i].kol  = -1;
        T[i].p    = -1;
    }
 
    for(int i = 0; i < N; i++)
    {
        T[ob1[i].kod] = ob1[i];
    }
    
    cout << endl;
    
    Show(T, max);
 
    cout << "\nEnter code: ";
    int kod;
    cin >> kod;
    if (kod > 0 && kod < max)
    {
        if (T[kod].kod != -1)
            Show(&T[kod], 1);
        else cout << "No!" << endl;
    }
    else cout << "No!!" << endl;
 
    getch();
    return 0;
}
Добавлено через 3 минуты
Цитата Сообщение от VASYA_A Посмотреть сообщение
что за 1 ? и зачем нужен амперсанд?
Это я не то написал. Там цикл не нужен.
Yandex
Объявления
12.10.2013, 14:35     Таблицы прямого доступа в С++
Ответ Создать тему
Опции темы

Текущее время: 18:09. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru