Розовая методичка. Огнева М. В., Кудрина Е. В. Структуры данных и алгоритмы программирование на языке c
 Скачать 1.93 Mb.
|
|
Огнева М.В., Кудрина Е.В. СТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ: ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ C++ ЧАСТЬ 1 ООО Издательский Центр «Наука» 2013 УДК 681.3 026(076.1) ББК 32.973-01*73 O38 Огнева М.В., Кудрина Е.В. O38 Структуры данных и алгоритмы: программирование на языке C++: Учеб, пособие в 2 ч. Часть 1. - Саратов: ООО Издательский Центр «Наука», 2013. - 88 с. ISBN 978-5-9999-1539-9 Отсканировано, распознано и отредактировано Котом. Каждый читатель обязуется использовать этот файл только в образовательных целях и как дополнение к честно купленному печатному изданию. Эта методичка была отсканирована и распознана специальным ПО. Ни одна программа не сможет идеально распознать текст. И если в художественных текстах это не так страшно, то здесь из-за одного неверно распознанного символа в тексте исходного кода программа не скомпилируется или будет работать с ошибками. Именно поэтому я рекомендую не копировать коды необходимых классов (стек, очередь, списки) отсюда, а скачать их по этой ссылке: https://github.com/leoon51/Ogneva-classes (Кнопка Download ZIP справа внизу) Я взял на себя смелость немного изменить реализацию некоторых элементов, упростить некоторые функции, добавить новые фичи и перегрузить операторы. Очень надеюсь, что меня не отчислят, не выпишут штраф и не посадят за такое. Авторские права – серьезная штука. Но я делаю это не для выгоды, а что бы я и мои знакомые могли читать методичку не только в печатном виде, но и на своем телефоне/ноутбуке. Так ведь удобнее: меньше таскать с собой, можно быстро найти нужную информацию, да и не нужен особый уход за бумагой (моя методичка вот уже вся скукожилась и испачкалась). Желаю всем хорошей учёбы! — Кот Данное пособие предназначено для тех читателей, которые уже знают основы программирования на языке C++. Оно поможет познакомится с объектно- ориентированной реализацией таких базовых структур данных, как списки, деревья и графы, а также с подходами и приемами использования данных структур при решении практических задач. Пособие состоит из двух частей. Первая часть включает в себя 6 разделов. В первом разделе рассматриваются основные понятия и принципы объектно- ориентированного программирования. Во втором разделе рассматриваются основные приемы правильного оформления программ, которыми пользуются разработчики современного программного обеспечения. Третий и четвертый разделы пособия посвящены описанию объектно- ориентированных возможностей языка C++, позволяющих эффективно создавать программы большого объема. Пятый раздел посвящен реализации абстрактного типа данных "список" с помощью классов языка C++. Рассмотрены частные случаи списка (стек и очередь) и их односвязная реализация, а также список общего вида в односвязной и двусвязной реализации. В шестом разделе рассматривается реализация списков с помощью классов- контейнеров стандартной библиотеки шаблонов STL. Все разделы данного пособия, кроме первого и второго, имеют следующую структуру: теоретическая часть, примеры программ с подробными пояснениями, набор упражнений. Некоторые разделы завершаются заданиями повышенной сложности (они отмечены звездочками), для решения которых от читателей потребуется самостоятельное изучение дополнительной литературы, список которой приведен в конце пособия. Авторы выражают искреннюю благодарность декану факультета компьютерных наук и информационных технологий Саратовского государственного университета имени Н.Г. Чернышевского (СГУ) Федоровой Антонине Гавриловне. Ваша поддержка, помощь и критические замечания играют большую роль не только в работе над данным пособием, но и в нашем профессиональном развитии. Авторы благодарят технического директора компании ЕРАМ Systems Агурова Павла Владимировича, внесшего существенный вклад в раскрытие идей объектно- ориентированного программирования в данном пособии, а также ведущего специалиста учебного центра компании ЕРАМ Systems Кузнецова Александра Владимировича за материалы, которые составили основу второго раздела «Стиль программирования». Авторы выражают свою признательность всем сотрудникам кафедры информатики и программирования СГУ, принимавшим участие в апробации пособия во время проведения лекционных и практических занятий со студентами факультета компьютерных наук и информационных технологий и механико-математического факультета СГУ. 3 1. ВВЕДЕНИЕ В ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ Технология объектно-ориентированного программирования (ООП) использует идею объединения данных и методов для их обработки в специальные конструкции, получившие название объектов. Программные объекты отражают строение объектов реального мира, поэтому в их качестве могут выступать люди (сотрудники, студенты, читатели библиотеки, вкладчики банков), хранилища данных (словари, списки товаров, каталоги книг), типы данных (комплексные числа, точки на плоскости, время), структуры данных (массивы, списки, деревья, графы) и многое другое. Программа, разработанная на основе технологии ООП, представляет собой совокупность объектов, которые взаимодействуют между собой посредством вызова методов друг друга. Технология ООП позволяет упростить процесс написания программ за счет использования таких важных принципов как инкапсуляция, наследование и полиморфизм. ООП основывается на введении понятия «класс». С точки зрения компилятора класс является типом данных, определяемым пользователем. Содержательно класс объединяет в себе данные и методы для их обработки, позволяя скрывать ту часть информации, которую не нужно видеть пользователю. В этом случае говорят, что данные и методы инкапсулированы. Инкапсуляция повышает степень абстракции программы — для использования в программе какого-то класса не требуется знаний о его реализации, достаточно знать только его интерфейс (описание). Это позволяет изменить реализацию класса, не затрагивая саму программу, при условии, что интерфейс класса останется прежним. Конкретные величины типа данных «класс» называются экземплярами класса или объектами. Класс содержит члены-данные (поля) и члены-функции (функции класса). Например, мы можем определить класс «сотрудник», в котором описать такие поля как фамилия, имя, отчество, дата рождения, оклад, стаж и многое другое, а также такие функции как «показать данные о сотруднике», «рассчитать зарплату», «рассчитать отпускные», «начислить премию» и т.д. Объекты класса «сотрудник» — это реальные люди, например, Иванов Иван Иванович, Алексеева Татьяна Сергеевна, Данилов Павел Александрович. У всех объектов значения полей данных будут различные, а вот функции по их обработке будут одинаковые, и это естественно, так как существует единое правило (алгоритм) расчета зарплаты, отпускных и премиальных. Если изменится, например, правило расчета зарплаты, то достаточно будет изменить соответствующую функцию в классе «сотрудник», и это изменение отразится на всех объектах. В повседневной жизни мы часто сталкиваемся с разбиением классов на подклассы. Например, класс «наземный транспорт» содержит такие подклассы как «легковые автомобили», «грузовые автомобили» и т.д. Каждый подкласс обладает свойствами того класса, из которого он выделен. Кроме этого, каждый подкласс обладает и собственными свойствами. Так, например, и легковые, и 4 грузовые автомобили обладают колесами и мотором и способны передвигаться по земле. Это - свойства, присущие классу «наземный транспорт». В то же время подкласс «легковые автомобили» содержит небольшое количество посадочных мест для перевозки пассажиров, а подкласс «грузовые автомобили» — кузов для перевозки грузов. Деление классов на подклассы ложится в основу принципа наследования. Наследование в ООП - это возможность создания иерархии классов, когда потомки (производные классы) наследуют все свойства своих предков (базовых классов), могут их изменять и добавлять новые. При этом свойства повторно не описываются, что сокращает объем программы. Иерархия классов представляется в виде древовидной структуры, в которой более общие классы располагаются ближе к корню, а более специализированные - ближе к листьям. Еще один важный принцип, заложенный в основу ООП, - это полиморфизм. Полиморфизм - это возможность использовать в рамках одного класса или различных классов одно имя для обозначения сходных по смыслу действий и гибко выбирать требуемое действие во время выполнения программы. Частным случаем полиморфизма является перегрузка функций. К основным преимуществам ООП относятся: 1. Логичность. Человек мыслит не терминами команд, переменных и операций, а терминами объектов, их характеристик и возможностей. С этой точки зрения, ООП идеально соответствует образу человеческого мышления. 2. Повторное использование кода. Программный код, написанный в концепциях ООП, достаточно хорошо подходит для повторного использования (как непосредственного, так и с некоторыми переработками). 3. Высокая скорость разработки. Данный показатель обуславливается как упрощением процесса написания кода, так и возможностью повторного использования ранее написанного кода. В идеале, при наличии соответствующих библиотек, приложение не пишется, а собирается из готовых кусков с написанием незначительных по объему «связок». Вместе с тем у ООП есть и недостатки: 1. Большие, по сравнению с остальными технологиями программирования, временные затраты на проектирование. Это тормозит начальную фазу разработки, но окупается на последующих этапах разработки программного обеспечения. 2. Снижение скорости работы приложения. Поддержка технологии ООП требует от среды исполнения некоторых затрат как по времени работы, так и по объему занимаемой оперативной памяти. Для небольших задач, например, уровня простейшего калькулятора вполне применимо написание кода программы с использованием технологии структурного программирования. Причина проста: все недостатки этой технологии перекроются отсутствием затрат на проектирование и написание оболочек подпрограмм и классов. Для решения более сложных задач, например, разработки калькулятора с синтаксическим анализом текста или простой тестовой системы может 5 потребоваться разбиение кода программы на несколько подпрограмм и их объединение в логически завершенные модули, т.е. использование технологии модульного программирования. При этом снизится объем программы и улучшится читаемость кода. Большинство современных задач требуют использования технологии ООП, так как при очень большом объеме программного кода удержать в голове (тем более в головах нескольких разработчиков) все особенности проектирования и реализации невозможно. Разбиение программы на изолированные кирпичики (классы) позволяет решить эту проблему, так как каждый может решать только свою задачу, не беспокоясь о нюансах написания чужих программных фрагментов. В результате упрощается процесс написания, отладки и последующей модификации программного кода. Замечание Более подробно познакомиться с ООП можно изучив дополнительную литературу [6-8, 10, 11]. 2. СТИЛЬ ПРОГРАММИРОВАНИЯ Нам предстоит разрабатывать относительно большие программы, в которых мы будем создавать собственные классы и даже целую иерархию классов. В этих условиях проблема создания читабельного кода весьма актуальна. Поэтому в данном разделе мы рассмотрим основные приемы правильного оформления программ, взяв за основу неофициальный стандарт, предложенный Майком Крюгером, и получивший довольно широкое распространение среди разработчиков программного обеспечения. 2.1. Правила объявления идентификаторов При задании имен идентификаторов необходимо придерживаться следующих правил именования: Осмысленность имен Имена идентификаторов должны быть осмысленными и отражать их содержание. Например, для обозначения суммы чисел может использоваться переменная с именем sum, но не s, х, или var. Оптимальным является название, состоящее из полных английских слов. Если вы не уверены в своем английском — не используйте сокращения. Ваши сокращения могут оказаться не вполне очевидными для других людей, более того, они могут оказаться самостоятельными словами, возможно, не вполне приличного смысла. Например, при использовании переменной, объявленной как: int sesID; возможно, как минимум, три варианта толкования сокращения ses: 1. Satellite Earth Station - земная станция спутниковой связи; 2. Surface-Effect Ship - судно на воздушной подушке; 3. SESion - сессия. Какой именно из этих вариантов толкования имеется в виду? 6 Также недопустимым считается использование транслита. Далеко не каждый англоговорящий программист в состоянии понять, что MailFolder и PochtovayaPapka - это одно и то же. Одна строка — одна переменная На одной строке лучше объявлять только одну переменную. Это необходимо для того, чтобы можно было прокомментировать каждую из них. Например, вместо объявления вида: int х, у; Лучше написать: int х; int у; Форматы именований Существует несколько видов нотаций - соглашений о правилах создания имен. В нотации Pascal каждое слово, входящее в идентификатор, начинается с заглавной буквы. Например: Age, LastName, TimeOfDeath. В нотации Camel с заглавной буквы начинается каждое слово идентификатора, кроме первого. Например: age, lastName, timeOfDeath. Венгерская нотация отличается от предыдущих наличием префикса, соответствующего типу величины. Например: fAge или FAge, sName или SName. Нотация Upper case допускает в названии программных объектов использовать только заглавные буквы. Например, Е, PI, SUM. Рассмотрим на примерах, для каких идентификаторов какую нотацию рекомендуется использовать. Для именования локальных переменных принято использовать нотацию Camel. В данном случае корректными будут считаться следующие имена переменных: localVariable, sum, temporaryArray. Для счетчиков циклов допустимо использовать однобуквенные имена, например, i, j, k. В циклах более чем тройной степени вложенности дополнительно могут использоваться имена l, m, n. Соответственно, использовать имена i, j, k для других целей, а также имена l, m, n - не рекомендуется. При задании имен классов и структур используются следующие правила: 1. Название должно представлять собой существительное в единственном или множественном числе; 2. Имя записывается в соответствии с нотацией Pascal; 3. Какие-либо префиксы в имени отсутствуют. Примерами корректных имен классов и структур могут быть: Circle, Filelnfo и Graphics. Названия членов-функций классов рекомендуется записывать в соответствии со следующими правилами: 1. Имена функций должны образовываться глагольными формами единственного и множественного числа; 7 2. Имена функций должны писаться в соответствии с нотацией Pascal. Например, функция, которая вычисляет и возвращает площадь фигуры, может называться GetArea, функцию вставки имеет смысл называть Insert, а функцию удаления Delete. При задании имен параметров членов-функций и членов-данных классов рекомендуется придерживаться нотации Camel. Например, корректными будут названия полей: length, arrayLength, area. А при задании имен констант рекомендуется использовать нотацию Pascal. Для случая коротких названий допустимо использование нотации Upper case. 2.2. Форматирование текста При форматировании текста также следует придерживаться простых правил: Длина строк Длина каждой строки программного кода не должна превышать 80 символов (примерно столько символов умещается на экране без горизонтальной прокрутки). В случае необходимости следует осуществлять перенос кода на следующую строку. Правила переноса Перенос можно осуществлять после запятой, точки с запятой или после оператора или операции. При этом переносимая часть строки должна быть сдвинута вправо как минимум на один стандартный символ табуляции. Пример, правильного переноса: cout << "Значение выражения равно:" << (b + sqrt(b * b - 4 * а)) / (2 * а) – pow(a, 3) + pow(b, -2); Пример, неправильных переносов: //выравнивание происходит без сдвига cout << "Значение выражения равно:" « (b + sqrt(b * b - 4 * а)) / (2 * а) – pow(a, 3) + pow(b, -2); //перенос произошел до операции cout << "Значение выражения равно:" « (b + sqrt(b * b - 4* а)) / (2 * а) - pow(a, 3) + pow(b, -2); Пустые строки Рекомендуется использовать пустые строки, не содержащие в себе кода, для отделения друг от друга отдельных функций, а также логических блоков внутри функции для повышения читабельности кода. 2.3. Правило записи операторов Продемонстрируем правило записи операторов на примере оператора if. Если в if предполагается использовать только один оператор действия, то можно записать его без использования блока {} , например, так : if (х < 0) у = 0; else у = 1; 8 Однако предпочтительнее и в этом случае использовать блок {}, начиная его с новой строки. Это улучшает читабельность программы и значительно сокращает вероятность ошибки при внесении последующих изменений. В нашем случае оператор if следует записать так: if (х < 0) { y = 0; } else { y = 1; } Далее будем придерживаться данного правила не только для оператора if, но и для других операторов. 2.4. Комментарии Еще одной очень важной составляющей оформления программного кода является его грамотное документирование. Принято считать, что программа продокументирована на приемлемом уровне, если объем комментариев в ней составляет не менее 30% от общего объема исходного кода программы. Причем речь идет об осмысленных комментариях, поясняющих логику работы программы, а не о формальных действиях: int radius; //объявляем переменную radius целого типа Данный комментарий не имеет смысла. Правильнее было бы прокомментировать предназначение переменной, например, следующим образом: int radius; //радиус окружности |