Лекция 4 2017 Строки, массивы, структуры (Лекции (2017)), страница 2

НГУ, ФФ, 2017???Лысаков К.Ф.Структурное программированиеВ 1968 году Эдсгер Вибе Дейкстраопубликовал свое знаменитое письмо«Оператор GoTo считается вредным»методология разработки программного обеспечения,в основе которой лежит представление программыв виде иерархической структуры блоков.Предложена в 1970-х годах Э. Дейкстрой и др.• Любая программа строится без использования оператора goto• Три базовых управляющих структуры: последовательность, ветвление, цикл• Использование подпрограмм (функций)• Разработка программы ведётся пошагово, методом «сверху вниз»Курс «Основы программирования».

НГУ, ФФ, 2017Лысаков К.Ф.Метод «сверху вниз»1. Сначала пишется текст основной программы, в котором, вместо каждого связногологического фрагмента текста, вставляется вызов подпрограммы.2. Вместо настоящих, работающих подпрограмм, в программу вставляются фиктивныечасти — заглушки.• заглушка удовлетворяет требованиям интерфейса заменяемого фрагмента(модуля), но не выполняет его функций или выполняет их частично.3. После того, как программист убедится, что подпрограммы вызываются вправильной последовательности (то есть общая структура программы верна),подпрограммы-заглушки последовательно заменяются на реально работающие.• разработка каждой подпрограммы ведётся тем же методом, что и основнойпрограммы.Такая последовательность гарантирует, что на каждом этапе разработки программистодновременно имеет дело с обозримым и понятным ему множеством фрагментов.При сопровождении и внесении изменений в программу выясняется, в какие именнопроцедуры нужно внести изменения.

Они вносятся, не затрагивая части программы,непосредственно не связанные с ними. Это гарантирует, что при внесении изменений иисправлении ошибок не выйдет из строя часть программы, находящаяся в данныймомент вне зоны внимания.Курс «Основы программирования». НГУ, ФФ, 2017Лысаков К.Ф.Постановка задачи0! Выяснить особенности поставленной задачи – сформулировать ТЗЗадача:Отсортировать введенной пользователеммассив и распечатать на экранУточнения:1. Какие данные, диапазон2.

Размер массива – кто задает3. Способ сортировки• Трудоемкость• Где хранить данные• Предварительные знания••••••••••••Целочисленные данныеДиапазон от -1000 до 5000Размер задает пользовательСкорость сортировки не важнаРезультат сортировки вотдельном массивеТип данных intХранение в виде динамического массиваРазмер задается с консолиДанные вводятся с консоли, необходим контроль диапазонаСоздание второго массива с результатамиСортировка пузырькомВывод массива на консольКурс «Основы программирования». НГУ, ФФ, 2017Лысаков К.Ф.1. Текст основной программы, в котором, вместо каждого связногологического фрагмента текста, вставляется вызов подпрограммы.void main(){int *pMas, *pResMas;int size, order;printf("Input size: ");scanf("%d", &size);pMas = AllocateMemory(size);•••••••Тип данных intХранение в виде динамического массиваРазмер задается с консолиДанные вводятся с консоли, контроль диапазонаСоздание второго массива с результатамиСортировка пузырькомВывод массива на консольInitAndCheckMassive(pMas, size, -1000, 5000);pResMas = AllocateMemory(size);printf("0 to ascending order, else 1");scanf("%d", &order);BubbleSort(pMas, pResMas, size, order);PrintMas(pResMas, size);free(pMas);free(pResMas);••••Имена переменныхИмена функцийЧитаемость кодаПонятность действий• Параметры ивозвращаемые значения• Контроль памяти}Курс «Основы программирования».

НГУ, ФФ, 2017Лысаков К.Ф.2. Добавление «заглушек» функцийint* AllocateMemory(size){int* p = NULL;заглушка удовлетворяетreturn p;требованиям интерфейса}заменяемого фрагмента (модуля),void InitAndCheckMassive(int* pMas, int size, int Min, int Max) но не выполняет его функций иливыполняет их частично{}void BubbleSort(int* pSrcMas, int* pResMas, int size, int order){}void PrintMas(int* pMas, int size){}Цель:void main()1. Компиляция{…….2. Сборка (линковка)pMas = AllocateMemory(size);3. Запуск программыInitAndCheckMassive(pMas, size, -1000, 5000);4.

Исполнение программы……pResMas = AllocateMemory(size);BubbleSort(pMas, pResMas, size, order);• Корректное завершение……PrintMas(pResMas, size);…….}Курс «Основы программирования». НГУ, ФФ, 2017Лысаков К.Ф.3. Заглушки дополняются необходимой функциональностьюint* AllocateMemory(int size){int* p = NULL;p = malloc(size * sizeof(int));return p;}void InitAndCheckMassive(int* pMas, int size, int Min, int Max){int i, flag;•for(i = 0; i < size; i++)•{•do{•printf("mas[%d] = ", i);scanf("%d", (pMas+i));if(*(pMas+i) >= Min && *(pMas+i) <= Max)•flag = 1;elseflag = 0;} while(!flag);}}Курс «Основы программирования».

НГУ, ФФ, 2017Имена переменныхИмена функцийЧитаемость кодаПонятность действийОбъем кода для однойфункции не долженпревышать видимойобластиЛысаков К.Ф.3. Заглушки дополняются необходимой функциональностьюvoid CopyData(int* pSrcMas, int* pDstMas, int size){разработка каждой}int Compare(int* pMas, int i, int j)// 1 [i] > [j]подпрограммы ведётся{// -1 [i] < [j]тем же методом, чтоint res = 0;// 0 [i] = [j]и основной программыreturn res;}void Replace(int* pMas, int i, int j){}void BubbleSort(int* pSrcMas, int* pResMas, int size, int order){int res, n, i;CopyData(pSrcMas, pResMas, size);for(n = 0; n < size-1; n++)for(i = 0; i < size-2; i++){res = Compare(pResMas, i, i+1);if(res == order)Replace(pResMas, i, i+1);}}комментарии=документацияКурс «Основы программирования».

НГУ, ФФ, 2017Лысаков К.Ф.При сопровождении и внесении изменений в программувыясняется, в какие именно процедуры нужно внестиизменения. Они вносятся, не затрагивая части программы,непосредственно не связанные с ними.void BubbleSort(int* pSrcMas, int* pResMas, int size, int order){int res, n, i;CopyData(pSrcMas, pResMas, size);for(n = 0; n < size-1; n++)for(i = 0; i < size-2; i++){res = Compare(pResMas, i, i+1);if(res == order)Replace(pResMas, i, i+1);}}Изменения в алгоритме сортировки(оптимизации)затрагивают только одну функциюКурс «Основы программирования». НГУ, ФФ, 2017Лысаков К.Ф.Никлаус Вирт (Niklaus Wirth, род.

15 февраля 1934 года)• швейцарский учёный, специалист в области информатики• один из известнейших теоретиков в области разработки языковпрограммирования• создатель и ведущий проектировщик языков программированияПаскаль, Модула-2, Оберон...«Инструмент долженсоответствовать задаче.Если инструмент несоответствует задаче, нужнопридумать новый, который бы ейсоответствовал, а не пытатьсяприспособить уже имеющийся»технология структурного программированияразработана, обоснована и внедрена в жизньВиртом, Дейкстрой и Хоаром.Курс «Основы программирования». НГУ, ФФ, 2017Лысаков К.Ф.ЛитератураНиклаус Вирт.Алгоритмы иструктуры данных.•••фундаментальные принципыпостроения эффективных инадежных программНа примерах прорабатываютсятрадиционные темыалгоритмики: сортировка ипоиск, рекурсия, динамическиеструктуры данныхпрограммы на языке Модула-2Брайан У.

Керниган,Деннис М. Ритчи.Язык программирования C.Дональд Эрвин Кнут.Искусство программирования.••••••фундаментальная монографияв 1999 году признана одной издвенадцати лучших физикоматематических монографийстолетиятом 1. Основные алгоритмы.том 2. Получисленные алгоритмы.том 3. Сортировка и поиск.том 4, A. Комбинаторныеалгоритмы…..Курс «Основы программирования». НГУ, ФФ, 2017•••Классическая книга по языку С,написанная самимиразработчиками этого языкаявляется как практическиисчерпывающим справочником,так и учебным пособиемКнига не рекомендуется длячтения новичкам (требует знанияоснов программирования ивычислительной техники)Лысаков К.Ф..