Реализация последовательных списков с использованием массивов

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

Эта задача может быть реализована на языке Си++ с помощью следующего программного кода:

#include< iostream>

usingnamespace std;

intmain()

{

const int n=20; // количество элементов массива

int b[n]; // описание массива

int i;

for(i=0; i< n; i++) cin > > b[i]; // вводмассива

for(i=0; i< n-1; i++) // n-1 раз поиск наименьшего элемента

{

// принимаем за наименьший первый из рассматриваемых элементов

int imin=i;

// поиск номера первого элемента из неупорядоченных

for(int j=i+1; j< n; j++)

// если нашли меньший элемент, запоминаем его номер

if(b[j]< b[imin]) imin=j;

int a=b[i]; // обмен элементов

b[i]=b[imin]; // с номерами

b[imin]=a; // i и imin

}

// вывод упорядоченного массива

for(i=0; i< n; i++)cout < < b[i] < < ' ';

return 0;

}

В данной программе выполняется ввод с клавиатуры списка из 20 целых чисел, которые формируют одномерный массив. Далее элементы массива сортируются по возрастанию и выводятся на экран монитора.

Алгоритм сортировки целочисленного массива состоит в том, что выбирается наименьший элемент массива и меняется местами с первым элементом. Далее, рассматриваются элементы, начиная со второго, и наименьший из них меняется местами со вторым элементом, так далее n-1 раз. При последнем проходе цикла при необходимости меняются местами предпоследний и последний элементы массива.

Процесс обмена элементов массива с номерами i и imin через буферную переменную a на i-м проходе показан на рис.2. Цифры около стрелок обозначают порядок действий.

Индексы

i

imin

Массив:

а

Рисунок 2- Обмен значений двух переменных

 

Ввод и вывод целых чисел (элементов одномерного массива) осуществляется с использованием стандартных потоков (cin и cout) и операций (> > и < <) ввода-вывода языка программирования Си⁺⁺.

Более сложный пример хранения данных в памяти компьютера представляет собой хранение списка из десяти имен, каждое из которых не длиннее восьми символов. В таком случае программист может создать непрерывный список в виде двумерного массива символов, состоящего из десяти строк и восьми столбцов, размещение которого в непрерывном блоке оперативной памяти показано на рис. 3 (предполагается, что массив хранится построчно). Такая организация данных также называется последовательным (непрерывным) списком. Из рисунка видно, что большой блок ячеек памяти разделен на подблоки, содержащие по восемь ячеек. В каждом подблоке хранится имя, записанное в кодах ASCII, и для хранения каждой буквы используется одна ячейка. Если длины имени не хватает для заполнения всех ячеек в выделенном для него подблоке, оставшиеся ячейки можно заполнить кодом ASCII для пробела. Этот подход требует 80 последовательных ячеек памяти для хранения списка из 10 имен.

Непрерывный блок ячеек памяти

Первое имя хранится здесь

Второе имя хранится здесь

Десятое имя хранится здесь

Рисунок 3 – Имена, хранящиеся в памяти в виде непрерывного списка

 

Эта задача реализуется на языке Си⁺⁺ с помощью следующего программного кода:

#include< iostream>

usingnamespace std;

int main()

{

constint n=10, m=8; //

char Name[n][m]; //

int i, j;

 

// Вводзаписейсписка

cout < < " Vvedite spisok\n\n";

for(i=0; i< n; i++) //

for(j=0; j< m; j++) cin > > Name[i][j];

cout < < " \n";

 

// Выводсписка

for(i=0; i< n; i++)

{

for(j=0; j< m; j++) cout < < Name[i][j];

cout < < " \n";

}

return 0;

}

В данной программе вводится с клавиатуры список из десяти фамилий, а затем осуществляется его вывод на экран монитора. Элементы массива имеют символьный тип данных char. Тип элементов массива вместе с его размерностью определяет объем памяти, необходимый для размещения массива, которое определяется на этапе компиляции программы. Поэтому выбор типа данных для хранения списка программист должен осуществлять продуманно. Например, если список представляет собой последовательность только цифр, то в этом случае целесообразно использовать для элементов массива int, float или double в зависимости от величины элементов списка. При этом, если хотя бы один элемент будет иметь тип который требует для своего хранения большее количество байт, чем остальные элементы списка, то тип именно этого элемента и будет определять тип данных массива. Например, один элемент списка (3.14) имеет тип float, а все остальные элементы списка (1 2 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20) имеют тип int. Следовательно, в качестве типа данных для массива следует выбрать тип float. После ввода каждого элемента строки следует нажимать клавишу пробела, а после ввода последнего элемента клавишу ввода. При таком способе ввода расположение элементов массива на экране монитора будет аналогично концептуальному представлению списка.

В случае, если в списке имеется хотя бы один символ, не являющийся цифрой (какая либо буква, символы @, # и т.п.), то для элементов массива следует использовать символьный тип char или расширенный символьный тип wchar_t (в случае если для кодировки недостаточно одного байта). При этом следует помнить, что в этом случае каждому элементу массива будет соответствовать только один введенный символ. Любая последовательность символов введенных подряд (без пробелов), например 1A#B, будет восприниматься компилятором как инициализация четырех элементов массива. Символы, превышающие количество элементов массива игнорируются.

Реализация последовательных списков с использованием структур

Очень часто в повседневной жизни приходится иметь дело со списками, представляющие собой объединение данных различного типа. Например, совокупность сведений об успеваемости студента может состоять из элемента символьного типа для указания фамилии и нескольких элементов целочисленного типа, указывающих оценки студента по учебным дисциплинам. Данный вид списка наиболее удобно реализовать в языке программирования Си⁺⁺ с помощью структуры. Структура, в отличие от массива, может содержать данные различных типов. Элементы структуры, представляющие из себя совокупность данных, называются полями. Поскольку вся эта информация относится к одному объекту (студенту), логично дать ему имя. Чтобы впоследствии к нему можно было обращаться. Для этого описывается новый тип данных, после описания которого ставится точка с запятой.

Описание нового типа данных - структуры (неоднородного массива) на языке Си⁺⁺ может выглядеть так:

StructStudent // Описание структуры с именем «Студент»

{

Описание полей (элементов) структуры

charName [20], Faculty [30], Speciality [50];

int Course, Mathematics, Physics, Computer science;

};

Имя нового типа данных – Student. Можно описать переменные этого типа точно так же, как и переменные встроенных типов, например:

Studentst1, st2[10].

В данной строке описываются:

· структура st1, представляющая организационное объединение семи полей различного типа. Структура, также как и массив, храниться в памяти в виде непрерывного блока ячеек памяти, при этом поля структуры располагаются в блоке последовательно, друг за другом:

Непрерывный блок ячеек памяти

Первое поле хранится здесь

Второе поле хранится здесь

Седьмоеполе хранится здесь

Структура st1

Рисунок 4 - Структура, хранящаяся в памяти в виде непрерывного блока

· массив структур st2[10], то есть массив, элементами которого являются десять структур, каждая из которых в свою очередь состоит из семи полей различного типа.

Непрерывный блок ячеек памяти

Структура st2[0] хранится здесь

Структура st2[1] хранится здесь

Структура st2[9] хранится здесь

Массив структурst2[10]

Поля структур

Рисунок 5 – Массив структур, хранящийся в памяти в виде непрерывного блока