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

@VASYA_A · Регистрация: 11.09.2013

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

Здравствуйте ! Нужно разобраться с таблицами прямого доступа . После прочтения теории я понял немногое:
например , вот мы создаём массив и 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 · 12.10.2013, 11:03

Сообщение от VASYA_A

а как создать для него таблицу прямого доступа ?

Находите в массиве максимальное число, создаёте динамический массив, размером на единицу больше этого числа.

@VASYA_A · 12.10.2013, 11:20 **[ТС]**

Сообщение от alsav22

Находите в массиве максимальное число, создаёте динамический массив, размером на единицу больше этого числа.

Вот , создал:

C++

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++

T[3]=3;
T[5]=5;
T[9]=9;
T[28]=28;
T[724]=724

Правильно ли это?
Может я что-то не так понимаю..просто очень мало информации есть про ТПД.

alsav22 · 12.10.2013, 11:22

Сообщение от VASYA_A

Нужно вручную записывать на каждый индекс значения из нашего массива?

Можно не вручную:

C++

#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 · 12.10.2013, 11:30 **[ТС]**

Сообщение от alsav22

Можно не вручную:

C++

#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 · 12.10.2013, 11:44

Сообщение от VASYA_A

можете вот эти строчки объяснить ,

C++

1 2	for (int i = 0; i < 5; ++i) arr[A[i]] = A[i];

В массив arr, по индексу, равному значению элемента в массиве A, записывается значение этого элемента

@VASYA_A · 12.10.2013, 12:00 **[ТС]**

Сообщение от alsav22

C++

1 2	for (int i = 0; i < 5; ++i) arr[A[i]] = A[i];

В массив arr, по индексу, равному значению элемента в массиве A, записывается значение этого элемента

Спасибо большое. С массивом разобрался.
А вот если работать , например , с массивом структур ? Как для него создать таблицу прямого доступа?
В структуре Data есть 3 поля , поиск осуществляется по полю а.

C++

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 · 12.10.2013, 12:07

Сообщение от VASYA_A

Как создать ТПД для поля а?

Находите самое большое значение поля а и т.д.:

Сообщение от alsav22

создаёте динамический массив, размером на единицу больше этого числа.

и т.д.

@VASYA_A · 12.10.2013, 12:22 **[ТС]**

Сообщение от alsav22

Находите самое большое значение поля а и т.д.:

и т.д.

то есть, нужно так:

C++

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++

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 · 12.10.2013, 13:19

Не по теме:

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

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

Добавлено через 1 минуту
Что вы собираетесь хранить в таблице? Какое-то поле структуры? Сами структуры?

@VASYA_A · 12.10.2013, 13:34 **[ТС]**

Сообщение от alsav22

Не по теме:

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

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

Есть массив структур . Нужно для него создать ТПД и выполнить поиск по одному полю.
Вот пробую сделать так, но когда нахожу максимальный элемент , то программа прерывается на этом моменте.

C++

#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 · 12.10.2013, 13:38

Для начала max инициализируйте.

@VASYA_A · 12.10.2013, 13:42 **[ТС]**

Сообщение от alsav22

Для начала max инициализируйте.

то есть , присвоить ему 0?

C++

int max=0

или нужно этот max как-то связать с искомым полем kod?

alsav22 · 12.10.2013, 13:52

У вас там напутано с поиском max.

C++

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 · 12.10.2013, 13:59 **[ТС]**

Сообщение от alsav22

У вас там напутано с поиском max.

C++

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 · 12.10.2013, 14:23

Сообщение от VASYA_A

Вот такая вот задача.

Задача туманна.

Сообщение от VASYA_A

организовать поиск по ключу

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

Добавлено через 1 минуту
Если искать в таблице структруру по kod:

C++

//#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 · 12.10.2013, 14:29 **[ТС]**

Сообщение от alsav22

Задача туманна.

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

Добавлено через 1 минуту
Если искать в таблице структруру по kod:

C++

//#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 ? и зачем нужен амперсанд?

alsav22 · 12.10.2013, 14:35

C++

//#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 ? и зачем нужен амперсанд?

Это я не то написал. Там цикл не нужен.

alsav22 5498 / 4893 / 831 Регистрация: 04.06.2011 Сообщений: 13,587
	12.10.2013, 11:03	2
	Сообщение от VASYA_A а как создать для него таблицу прямого доступа ? Находите в массиве максимальное число, создаёте динамический массив, размером на единицу больше этого числа. 0

alsav22 5498 / 4893 / 831 Регистрация: 04.06.2011 Сообщений: 13,587
	12.10.2013, 12:07	8
	Сообщение от VASYA_A Как создать ТПД для поля а? Находите самое большое значение поля а и т.д.: Сообщение от alsav22 создаёте динамический массив, размером на единицу больше этого числа. и т.д. 1

alsav22 5498 / 4893 / 831 Регистрация: 04.06.2011 Сообщений: 13,587
	12.10.2013, 13:19	10
	Не по теме: Л/с получили? Добавлено через 21 минуту У вас несколько задача расплылась. По структурам задачу нужно по-новой сформулировать. То, что приводилось, как пример, в первом посте, здесь уже, как я понимаю, не подходит. Добавлено через 1 минуту Что вы собираетесь хранить в таблице? Какое-то поле структуры? Сами структуры? 0

alsav22 5498 / 4893 / 831 Регистрация: 04.06.2011 Сообщений: 13,587
	12.10.2013, 13:38	12
	Для начала max инициализируйте. 0