В атд
 Скачать 46.08 Kb.
|
Оглавление1.1Введение в АТД 1 1.2Описание задания 2 1.3Варианты заданий 5 1.4Примеры определения и реализации АТД 10 1.5Контрольные вопросы 16 Практическая работа 1Тема. Абстрактный тип данных задачи и его реализация на одномерном статическом массивеСтандартные структуры данных языка программирования для представление многоэлементных однородных структур данных задачи в программе. Одномерный статический массив Цель практической работы приобретение умений и навыков определения и реализации абстрактного типа данных задачи в программе; приобретение навыков по реализации алгоритмов операций над массивом через аппарат функций языка С++; приобретение навыков реализации операций модификации (вставка и удаление элементов) одномерного массива и других операций обработки массива как структуры данных. Введение в АТДРазработка программной реализации задачи предусматривает определение абстрактного типа данных (далее АТД) задачи. Абстракция определяет область и структуру данных вместе с набором операций, которые требуются для доступа к данным при решении задачи. АТД – это тип данных, разработанный пользователем. Для каждой задачи разрабатывается свой АТД. АТД является независимым от реализации (языка программирования, структур данных языка программирования) и позволяет программисту сосредоточиться на идеализированных моделях данных и операциях над ними. При программной реализации АТД программист выбирает такую структуру представления данных, чтобы алгоритмы операций были наиболее эффективными. В данной практической работе будет определен АТД задачи, который должен быть реализован на статическом одномерном массиве. В набор операций АТД включаются: операции ввода и вывода массива; операции, определенные в индивидуальном варианте. В следующей работе будут использованы другие структуры реализации этой АТД. Формат АТД АТД Имя_АТД { Данные Описание структуры данных (свойства структуры), типов Операции Операция 1 (указать: действие выполняемое с данными, предусловие, постусловие, заголовок (Имя операции и список входных данных в круглых скобках) Операция 2 …………………….. Операция k } Пример объявления операции в АТД //Операция: удаление из списка значений А заданного значения х //Предусловие: A – входные данные, n>0 //Постусловие: результат при успешном поиске – pos, при безуспешном код завершения -1. searchXinA(Имя_АТД, pos);.- заголовок Описание заданияУсловие задачи для всех вариантов. Дано множество из n целых чисел. Дан набор задач (операций), которые требуется выполнить над исходным множеством. Набор задач определен в варианте задания. Разработать и реализовать АТД задачи, по управлению множеством посредством операций, указанных в варианте задания. В АТД включить операции по заполнению исходного множества и отображения множества. При разработке алгоритмов операций варианта могут быть выявлены дополнительные алгоритмы, например такие: определить является ли число простым, или определить сумму цифр числа, эти алгоритмы надо включить в раздел операций АТД. Требования к выполнению практической работы Разработать абстрактный тип данных задачи: АТД Имя_АТД { Данные (описание свойств структуры данных задачи) n – количество элементов множества А – список значений элементов множества pos – позиция элемента Примечание. Имена данных могут быть другими. Операции (объявления операций) Общие для всех вариантов заполнение структуры данных значениями (с клавиатуры, применение датчика случайных чисел); вывод структуры в консоль; удалить элемент в заданной позиции; вставить элемент в заданную позицию. Дополнительные операции Операции, определенные в варианте и выявленные разработчиком как вспомогательные, для улучшения структуризации кода операции. }; Реализовать список А из АТД можно на трех видах структур данных: статический массив, динамический массив, vector. В задании 1 рассмотрим реализацию на статическом массиве. Реализовать АТД задачи, используя для представления списка А статический массив максимального размера N. Требования к выполнению задания Выполнить реализацию данных на структуре языка С++ struct: включив поля: для А, n и константное поле N (максимальное количество элементов в статическом массиве А). Разработать и записать на псевдокоде алгоритмы операций: удалить элемент в заданной позиции (pos<=n); вставить элемент в заданную позицию (pos<=n); Реализовать все операции, заявленные в АТД, на реализованной структуре представления данных. Каждая операция оформляется отдельной функцией с параметрами. Примечание. Реализацию АТД можно выполнить в отдельном файле заголовка, разрабатываемого проекта. В основной программе его нужно будет подключить. Разработать наборы тестов для тестирования дополнительных операций. Набор тестов для каждой операции оформить отдельной таблицей по формату:
Пример. Оформление теста для операции: удалить элемент в заданной позиции pos. Реализация массива на С++. Алгоритм возвращает код завершения 0 – успешно, 1 не успешно. Таблица 1. Пример оформлления таблицы тестов
Разработать основную программу, демонстрирующую выполнение всех операций над структурой данных на подготовленных тестах. Программа должна управлять всем процессом посредством текстового меню. Выполнить тестирование основной программы на представленных тестах. Оформить отчет Требования по оформлению отчета: Заголовок 1 уровня: шрифт TimesBewRoman, размер 16, выравнивание по центру, нумерация, интервал после абзаца 10. Заголовок 2 уровня: шрифт TimesBewRoman, размер 14, выравнивание по центру, нумерация. Заголовок 3 уровня: шрифт TimesBewRoman, размер 14, выравнивание по левому краю, нумерация. Основной тест: шрифт TimesBewRoman, размер 14, межстрочный интервал Множитель 1,2, отступ первой строки 1 см, выравнивание по ширине. Структура отчета: Титульный лист Оглавление Условие задачи и задание варианта АТД задачи Включить текст АТД. Разработка программы Включить реализацию данных АТД (представить код структуры). Включить алгоритмы операций, указанных в пункте 2 требований к выполнению задания 1 и задачи, отмеченной символом * в варианте. Таблицы тестов тестирования операций варианта. Код проекта, включающий: файл заголовка, в котором представлена реализация АТД и его функций; основная программа. Скрины результатов тестирования. Выводы Указать какие знания умения и навыки вы получили в результате выполнения практической работы. Дайте оценку реализации сложной структуры данных, способами, представленными в примерах 1 и 2. Используемые источники Варианты заданийТаблица 2. Варианты заданий
Примеры определения и реализации АТДПример 1. Реализация АТД с применением типа struct для объединения данных в единую структуру. Условие задачи В заданном множестве из n натуральных чисел найти все числа Армстронга. Число Армстронга — это натуральное число, которое равно сумме цифр числа, возведенных в степень равную количеству цифр в числе. Пример, 153=13+53+33. Постановка задачи. Дано. Множество из n натуральных чисел Результат. Сформировать массив из тех чисел исходного множества, которые являются числами Армстронга (153=13+53+33). АТД задачи АТД setNumbersArmstrong { Данные n – размер входных данных (или размер задачи) Х – множество из n натуральных чисел typeX – тип множества typeitem – тип элемента множества Х Операции Заполнение исходного массива значениями с клавиатуры Предусловие. n – число заполняемых элементов,0 ≤n Постусловие. Заполненный массив X из n элементов. Нет возвращаемого значения. input_X(typeX Х, unsigned int n); Вывод значений массива X Предусловие. n>0, X – выводимый массив Постусловие. Вывод значений массива. Нет возвращаемого значения. output_X(typeX Х, unsigned int n); Функции декомпозиции (подзадачи исходной задачи, которые использует основной алгоритм) //Определение количества цифр в числе Предуслвие. x≥10 – исходное число типа typeitem Постусловие. Результат целое, количество цифр вчисле х count(typeitem); //Возведение целого числа в степень p Предуслвие. а>0 – цифра числа типа typeitem, p>0 – степень Постусловие. Результат целое, возведение а в степень p pow_1(typeitem a, unsigned int p); //Определение числа Армстронга Предуслвие. х>0 входное значение – целое натуральное число Постусловие. Результат true если х число Армстронга, false иначе Armstrong(typeitemx); //Формирование массива чисел Армстронга Предусловие. Х множество значений размера n>0. Y – множество типа typeX, формируемое функцией Постусловие. Результат массив Y из n элементов. Если в массиве А нет чисел Армстронга, то n=0 и массив Y пустое множество. newArrayY(typeX X, typeX Y); } Набор тестов для тестирования программы
Реализация АТД и код программы #include #include"stdlib.h" #include"string.h" using namespace std; typedef unsigned int typeitem; const unsigned int N = 100; //Определение данных АТД задачи struct typeX{ unsigned int n=0; typeitem X[N] = {}; typeX(int n1) { n = n1; } typeX() { n = 0; } }; //Операции АТД – прототипы функций //Вывод множества void output_X(typeX s); //Заполнение множества с клавиатуры void input_X(typeX &s); //Формирование массива Y (множества) из чисел Армстронга исходного множества X void newArrayY(typeX s, typeX &Y); //Определение количества цифр в числе x int count(typeitem x); //Возведение целого числа в степень p>0 typeitem pow_1(typeitem a, unsigned int p); //Является ли число х числом Армстронга bool Armstrong(typeitem x); //Реализация операций АТД //Заполнение множества с клавиатуры //Предусловие. n – число заполняемых элементов, 0 ≤n < N, X – массив с переменной // верхней границей. //Постусловие. Заполненный массив X из n элементов.Нет возвращаемого значения. void input_ar(typeX &s) { cout << "Vvedite "< for (unsigned int i = 0; i < s.n; i++) cin >> s.X[i]; } //Вывод множества //Предусловие.n > 0, X – выводимый массив //Постусловие.Вывод значений массива.Нет возвращаемого значения. void output_ar(typeX s) { cout << "Массив " << endl; for (unsigned int i = 0; i < s.n; i++) cout << "X[" << i << "]=" << s.X[i] << endl; } //Формирование массива (множества) из чисел Армстронга исходного множества //Предусловие. Х множество значений размера n > 0. Y – множество типа typeX, // формируемое функцией //Постусловие. Результат массив Y из n элементов.Если в массиве А нет чисел // Армстронга, то n = 0 и массив Y пустое множество. void newArrayY(typeX s, typeX &Y) { Y.n = 0; for (unsigned int i = 0; i < s.n; i++) { if (Armstrong(s.X[i]) == true) { Y.X[Y.n] = s.X[i]; Y.n++; } } } //Определение количества цифр в числе //Предуслвие. x≥10 – исходное число типа typeitem //Постусловие. Результат целое, количество цифр в числе х int count(typeitem x) { int k = 0; while (x) { k++; x = x / 10; } return k; } //Является ли число х числом Армстронга //Предусловие. х > 0 входное значение – целое натуральное число //Постусловие. Результат true если х число Армстронга, false иначе bool Armstrong(typeitem x) { int p = count(x); //количество цифр в числе и значение степени typeitem sum = 0; typeitem copyx = x; //копия исходного числа while (x) { sum += (unsigned int) pow_1(x % 10, p); x = x / 10; } if (copyx == sum) return true; else return false; } //Возведение целого числа в степень p>0 //Предуслвие.а>0 – цифра числа типа typeitem, p>0 – степень //Постусловие.Результат целое, возведение а в степень p typeitem pow_1(typeitem a, int p) { typeitem R = 1; if (p == 1) return a; while (p) { R *= a; p--; } return R; } //Основная программа, тестирующая операции на подготовленных тестах nt main(int argc, char* argv[]) { int n; cout << "Vvedite razmer mnogestva a"; cin >> n; if (n > 0 && n < N) { typeX a(n), b; input_ar(a); newArrayY(a, b); if (b.n > 0){ cout << "Numbers Armstronga in array a\n"; output_ar(b); } else cout << "Not Numbers Armstronga in array a\n"; } else cout << "n<0 or n>"< return 0; } Пример 2. Реализация АТД без объединения данных в единую структуру #include #include"stdlib.h" #include"string.h" using namespace std; const unsigned int N = 100; //Заполнение множества с клавиатуры //Предусловие.n – число заполняемых элементов, 0 ≤n < N, X – массив с переменной верхней границей. //Постусловие.Заполненный массив X из n элементов.Нет возвращаемого значения. void input_ar(int *s,int n) { cout << "Vvedite " < for (int i = 0; i < n; i++) cin >> s[i]; } //Вывод множества //Предусловие. n > 0, X – выводимый массив //Постусловие. Вывод значений массива.Нет возвращаемого значения. void output_ar(int* s, int n) { cout << "Массив " << endl; for (int i = 0; i < n; i++) cout << "s[" << i << "]=" << s[i] << endl; } //Определение количества цифр в числе //Предуслвие.x≥10 – исходное число типа int //Постусловие. Результат целое, количество цифр в числе х int count(int x) { int k = 0; while (x) { k++; x = x / 10; } return k; } //Возведение целого числа в степень p>0 //Предуслвие. а>0 – цифра числа типа int, p>0 – степень //Постусловие. Результат целое, возведение а в степень p int pow_1(int a, int p) { int R = 1; if (p == 1) return a; while (p) { R *= a; p--; } return R; } //Определение числа Армстронга //Предусловие. х > 0 входное значение – целое натуральное число //Постусловие. Результат true если х число Армстронга, false иначе bool Armstrong (int x) { int p = count(x); //количество цифр в числе и значение степени int sum = 0; int copyx = x; //копия исходного числа while (x) { sum += (int)pow_1(x % 10, p); x = x / 10; } if (copyx == sum) return true; else return false; } //Формирование массива (множества) из чисел Армстронга исходного множества //Предусловие. Х множество значений размера n > 0. Y – множество типа typeX, формируемое функцией //Постусловие. Результат массив Y из n элементов.Если в массиве А нет чисел Армстронга, то n = 0 и массив Y пустое множество. void newArrayY(int* s, int ns, int* Y, int &nY) { nY = 0; for (int i = 0; i < ns; i++) { if (Armstrong(s[i]) == true) { Y[nY] = s[i]; nY++; } } } int main() { unsigned int n = 0; cout << "Vvedite razmer mnogestva a"; cin >> n; if (n > 0 && n < N) { int a[N], b[N]; int nb=0; input_ar(a,n); newArrayY(a,n, b,nb); if (nb > 0) { cout << "Numbers Armstronga in array a\n"; output_ar(b,nb); } else cout << "Not Numbers Armstronga in array a\n"; } else cout << "n<0 or n>" << N << "\n"; return 0; std::cout << "Hello World!\n"; } Контрольные вопросыДайте определение структуре данных. Какие три операции над структурой данных называют базовыми? Что определяет тип данных в языках программирования? Сколько ячеек памяти связано с именем переменной простого типа? Сколько ячеек памяти связано с именем массива размером n? Перечислите свойства, характеризующие структуру данных массив. Какой тип языка программирования С++ пользуется для представления структуры данных, элементы которой различного типа? Могут ли элементом структуры struct быть другие структуры: массив, строка, указатель на другую структуру, другая структура? Определите тип данных для представления в программе точки на плоскости (декартова система координат). Определите структуру для хранения данных по n точкам. Перечислите свойства структуры, организованной на типе struct. Как называется область оперативной памяти, предназначенная для хранения значения простого типа? Что определяет размер ячейки оперативной памяти? Как можно описать организацию оперативной памяти на логическом уровне? Что определяет абсолютный адрес ячейки памяти? Какой способ хранения элементов структуры данных реализует одномерный массив? Какой способ хранения элементов структуры данных реализуется при определении пользовательского типа struct в C++? Что нужно знать (определить), чтобы получить прямой доступ к значению ячейки оперативной памяти? Какой способ хранения структур данных позволяет обеспечит прямой доступ к элементам структуры? Приведите формулу, по которой определяется адрес i - ого элемента массива х. Какой параметр в формуле представляет смещением и почему его так называют? Что представляет собой структура данных, имеющая векторное хранение элементов? Опишите. Приведите характеристики статического массива. Какие переменные называют локальными? Как организована область оперативной памяти для хранения локальных переменных? Что определяет понятие «время жизни переменной»? Если алгоритм функции вычисляет одно значение простого и ссылочного типа, что нужно включить в код функции? (приведите пример) Какую ошибку допустил программист при разработке функции func? #include const int n=10; int *func(){ int a[n]={1,2,3,4,5,6,7,8,9,0}; return a; } int main(){ int *b=func(); for(int i=0;i cout< } Статическому массиву А выделена память под 100 элементов. В него ввели только десять значений (n=10). Алгоритм функции func1 добавил по индексу 11 еще одно значение. Определите ошибку, которую допустил программист при создании функции func1? #include const int m=100; void func1(int *a,int n,int x){ a[n]=x; n++; } int main(){ int n=10; int a[m]={1,2,3,4,5,6,7,8,9,0}; func1(a,n,20); for(int i=0;i cout< } Как объявить типизированный указатель в программе на языке С++? Как объявить указатель без типа в программе на языке С++? Какие арифметические операции допустимы над указателем в С++? Программист написал неверный код копирования массива, который содержал операторы: int x[]={1,2,3,4,5}; int *y=x; Объясните его ошибку. Объясните суть операции «разыменование» для указателя. Приведите модель выполнения операции удаления значения массива из заданной позиции с сохранением порядка следования значений после удаленного значения. Приведите алгоритм удаления значения массива из заданной позиции, не сохраняя порядок следования значений после удаленного значения. Укажите условие, при котором допустима операция вставки нового значения в статический массив. Приведите модель выполнения операции вставки нового значения в заданную позицию массива с сохранением порядка следования значений после вставленного значения. Опишите различие алгоритмов операций вставки и добавления нового значения в массив. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||