Студопедия — Реализация последовательных списков с использованием массивов
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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






Примитивы для конструирования и манипуляции массивами, предлагаемые в большинстве языков программирования высокого уровня, являются удобными инструментами для создания и работы с последовательными (непрерывными) списками. Если все элементы списка принадлежат одному примитивному типу данных (например, 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 – Массив структур, хранящийся в памяти в виде непрерывного блока

 







Дата добавления: 2014-11-10; просмотров: 577. Нарушение авторских прав; Мы поможем в написании вашей работы!



Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

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

Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...

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

ФАКТОРЫ, ВЛИЯЮЩИЕ НА ИЗНОС ДЕТАЛЕЙ, И МЕТОДЫ СНИЖЕНИИ СКОРОСТИ ИЗНАШИВАНИЯ Кроме названных причин разрушений и износов, знание которых можно использовать в системе технического обслуживания и ремонта машин для повышения их долговечности, немаловажное значение имеют знания о причинах разрушения деталей в результате старения...

Различие эмпиризма и рационализма Родоначальником эмпиризма стал английский философ Ф. Бэкон. Основной тезис эмпиризма гласит: в разуме нет ничего такого...

Индекс гингивита (PMA) (Schour, Massler, 1948) Для оценки тяжести гингивита (а в последующем и ре­гистрации динамики процесса) используют папиллярно-маргинально-альвеолярный индекс (РМА)...

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

Тема 5. Анализ количественного и качественного состава персонала Персонал является одним из важнейших факторов в организации. Его состояние и эффективное использование прямо влияет на конечные результаты хозяйственной деятельности организации.

Билет №7 (1 вопрос) Язык как средство общения и форма существования национальной культуры. Русский литературный язык как нормированная и обработанная форма общенародного языка Важнейшая функция языка - коммуникативная функция, т.е. функция общения Язык представлен в двух своих разновидностях...

Studopedia.info - Студопедия - 2014-2024 год . (0.009 сек.) русская версия | украинская версия