Простейшие типы данных

1.3 Вектор

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

Такая структура хранения наиболее близко соответствует реальной организации памяти большинства ЭВМ. Все элементы структуры данных имеют одинаковую длину. Доступ к отдельному элементу осуществляется с использованием базового адреса (адреса начала) вектора и номера этого элемента. Обычно в векторной памяти размещаются массивы (одномерные и многомерные), строки, стеки, очереди, таблицы и т.п.

Для манипулирования со структурой данных, хранимой в векторе, требуется управляющая информация, определяющая адрес начала вектора, тип элементов структуры данных и их количество в векторе и т.п. Для хранения управляющей информации создается дескриптор (описатель) вектора, или информационный вектор.

Таким образом, структура вектора состоит из двух частей: дескриптора и непосредственно вектора, в котором последовательно размещаются элементы структуры данных.

дескриптор вектора

Адрес начала вектора

Длина элемента

Индекс начального эл-та

Индекс конечного эл-та

Дескриптор содержит: адрес начала вектора, тип элементов структуры данных или их длину, число элементов или их начальный и конечный индексы. Адрес элемента с индексом i определяется выражением А_i= A_m+(i - m) *L,

В большинстве случаев отображение структур данных в структуры хранения в виде вектора можно выполнить, используя такой тип данных, как «массив». При этом транслятор создает как дескриптор вектора, так и сам вектор, а обращение к элементам вектора сводится к обращению к элементам массива. Однако трансля-тор создает статический массив с фиксированными размерами, что может явиться ограничивающим фактором его применения. В прикладной программе можно организовать хранение данных в динамическом векторе. Для этого нужно выполнить ряд операций: определить структуру дескриптора, получить динамическую память под дескриптор и заполнить дескриптор управляющей информацией. Используя данные из дескриптора, определить размер памяти для вектора и получить динамическую память. При необходимости инициализировать лементы структуры данных в векторе. Адреса элементов для доступа к ним вычисляются с использованием управляющей информации из дескриптора. В программе доступ к структуре данных, хранимой в виде вектора, осуществляется посредством указателя на дескриптор.

Указатель на дескриптор —» Дескриптор —>Вектор

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

Приведем пример программы организации хранения структуры данных в векторной памяти и обработки ее элементов.

Элементами структуры данных являются вещественные числа, обработка элемента сводится сначала к занесению в элемент некоторого значения, а затем к выводу его значения на печать. Доступ к элементам структуры данных осуществляется по их индексам, значения которых меняются от m до п.

Пример 1.1.BR
/*Использование векторной памяти. */
#include <stdio.h>
#include <alloc.h>
#include <string.h>
#define DESC struct D_s       /* Дескриптор вектора */
DESC
{float *ptr_v;        /* Указатель начала вектора*/
int len;         /* Длина элемента структуры */
int m;          /* индекс начального элемента */
int n;         /* Индекс конечного элемента */
}
int main()
{DESC *d1;         /*Указатель на дескриптор */
float ptr_i;        /* Указатель на элемент*/
float a;         /* для выборки эл-та */
int i;
/* Получение памяти под дескриптор */
d1 = (DESC*) calloc(1,sizeof(DESC));
if (d1==NULL)       /*память под дескриптор не выделена */
return -1;      /* неудачное завершение программы */
/* Занесение в дескриптор управляющей информации */
d1->len = sizeof(float);     /* Длина элемента */
d1-> m= -3;       /• Индекс начального элемента */
d1->n = 5;        /* Индекс конечного элемента 7
/* Получение памяти под вектор размером (n-m+1)*len */
d1->ptr_v = malloc((d1->n — d1->m +1)*d1->len);
if (d1->ptr_v == NULL)         /* память под вектор не выделена */
{free (d1);          /* освобождение памяти из-под дескриптора */
return -1;            /* неудачное завершение программы */
}
/* Инициализация элементов структуры */
for (i=d1->m; i≤d1->n; i++)
{ /* Адрес i-го элемента структуры */
ptr_i = d1->ptr_v + i - d1->m;
/* Занесем в i-й элемент число */
*ptr_i = 12.34/(i+1);
}
/* Выборка и обработка элементов структуры */
for (i = d1->m; i ≤ d1->n; i++)
{ ptr_i = d1->ptr_v + i -d1->m;      /* адрес элемента */
a = *ptr_i;           /* Выборка элемента */
printf(«\n %d -й элемент = %f»,i,a); /* Печать */
}
getchar();          /* Ждем нажатия ввода */
}