Скачать 1.94 Mb.
|
Рис. 13. Последний узел списка заполнен данными и в предыдущий узел помещен соответствующий указатель. После выполнения первой строки во второй итерации цикла "while" состояние программы см. рис. 14. word ptr_to _next node ptr_to _next node last node current _node Рис. 14.. В хвост списка был добавлен новый узел. Допустим, в ответ на следующий запрос пользователь напечатает ".". Тогда после завершения цикла "while" программа будет в состоянии, как на рис. 15. 85 current las!; _node -node word "ной' -I 4 a_list ptr_to ptr_to Г _next _next / node node / current _node Рис. 15.. Был удален последний узел списка. Символ "." сигнализирует о том, что пользователь захотел прекратить ввод данных для списка. Поэтому функция "assign_list (...)" завершается и при выходе из нее автоматически уничтожаются локальные переменные-указатели "current_node" и "last_node" (которые были объявлены в теле функции). После возврата из функции состояние программы будет таким, как на рис. 16. a_list ptr_to ptr_to _ _next node node Рис. 16.. Состояние программы 5.1 после выхода из функции ввода списка с клавиатуры. 5.3 Печать связного списка Напечатать содержимое связного списка на экране несложно. Ниже приведена функция для печати строк, хранящихся в узлах списка: void print_list( node_ptr a_list ) { while ( a_list != NULL ) { cout « a_list->word « " "; a_list = a_list->ptr_to_next_node; } } Фрагмент программы 5.1. 6. Сводка результатов В лекции описаны способы динамического распределения оперативной памяти и работа с динамическими переменными с помощью указателей. В Си++ имена массивов можно рассматривать как указатели. Поэтому массивы можно создавать и уничтожать динамически. В выражениях с указателями можно применять арифметические операции сложения и вычитания. В конце лекции кратко рассмотрены основные свойства связного списка и приведен пример реализации этого абстрактного типа данных с помощью указателей. 86 7. Упражнения Упражнение 1 Не запуская приведенную далее программу, определите, какие сообщения она выводит на экран. Для проверки своего ответа запустите программу. #include typedef int* IntPtrType; int main() { IntPtrType ptr_a, ptr_b, *ptr_c; ptr_a = new int; *ptr_a = 3; ptr_b = ptr_a; cout « *ptr_a « " " « *ptr_b « "\n"; ptr_b = new int; *ptr_b = 9; cout « *ptr_a « " " « *ptr_b « "\n"; *ptr_b = *ptr_a; cout « *ptr_a « " " « *ptr_b « "\n"; delete ptr_a; ptr_a = ptr_b; cout « *ptr_a « " " « *&*&*&*&*ptr_b « "\n"; ptr_c = &ptr_a; cout « *ptr_c « " " « **ptr_c « "\n"; delete ptr_a; ptr_a = NULL; return 0; Упражнение 2 Напишите логическую функцию с двумя параметрами-строками. Функция должна возвращать "true", если ее первый параметр-строка по алфавиту расположена раньше, чем вторая строка. В противном случае функция должна возвращать "false". Можете считать, что обе строки содержат только строчные буквы, и в них нет ни пробелов, ни служебных символов. Проверьте работу функции с помощью тестовой программы. После отладки функции напишите ее вариант с применением арифметических выражений с указателями. Убедитесь, что функция работает так же, как и первый вариант. Упражнение 3 В программу 5.1 добавьте 3 новых функции и измените программу так, чтобы проверить их действие. • Функция void add_after(node_ptr& list, char a_word[], char word_after[]) Вставляет в связный список "list" после первого встретившегося узла со СЛОВОМ "a_word" новый узел со словом "word_af ter". Если в списке "list" 87 нет узла со словом "a_word", то функция не должна модифицировать список. • Функция void delete_node(node_ptr& a_list, char a_word[]) Удаляет в связном списке "a_list" первый встретившийся узел СО словом "a_word". • Функция void list_selection_sort(node_ptr& a_list) Выполняет сортировку узлов списка в алфавитном порядке (см. Упражнение 2). Пример экранного ввода/вывода текстовой программы в типичном сеансе работы: Введите первое слово (или '.' для завершения списка): это Введите следующее слово (или '.' для завершения списка): тестовое Введите следующее слово (или '.' для завершения списка): сообщение Введите следующее слово (или '.' для завершения списка): из Введите следующее слово (или '.' для завершения списка): нескольких Введите следующее слово (или '.' для завершения списка): слов Введите следующее слово (или '.' для завершения списка): на Введите следующее слово (или '.' для завершения списка): русском Введите следующее слово (или '.' для завершения списка): языке Введите следующее слово (или '.' для завершения списка): ТЕКУЩЕЕ СОДЕРЖИМОЕ СПИСКА: это тестовое сообщение из нескольких слов на русском языке ПОСЛЕ КАКОГО СЛОВА ВЫ ХОТИТЕ ВСТАВИТЬ НОВОЕ СЛОВО? это КАКОЕ СЛОВО ВЫ ХОТИТЕ ВСТАВИТЬ? небольшое ТЕКУЩЕЕ СОДЕРЖИМОЕ СПИСКА: это небольшое тестовое сообщение из нескольких слов на русском языке КАКОЕ СЛОВО ВЫ ХОТИТЕ УДАЛИТЬ? тестовое ТЕКУЩЕЕ СОДЕРЖИМОЕ СПИСКА: это небольшое сообщение из нескольких слов на русском языке СОДЕРЖИМОЕ СПИСКА ПОСЛЕ СОРТИРОВКИ: из на небольшое нескольких русском слов сообщение это языке Подсказки. Основные черты алгоритма добавления нового узла заключаются в следующем:
Возможный алгоритм удаления узла:
Для сортировки связного списка несложно адаптировать алгоритм сортировки массива из 6-й лекции. ЛЕКЦИЯ 8. Рекурсия 1. Понятие рекурсии В хорошо спроектированной программе на Си++ в определениях функций часто встречаются вызовы других функций этой же программы или библиотеки Си++. Например, в предыдущей (7-й) лекции, в определении функции "assign_list (...)" есть вызов "assign_new_node (...)". Если в определении функции содержится вызов ее самой, то такая функция называется рекурсивной. Понятие рекурсии хорошо известно в математике и логике. Например, можно привести следующее рекурсивное определение натуральных чисел:
В данном контексте понятие рекурсии тесно связано с понятием математической индукции. Обратите внимание, что в приведенном определении натуральных чисел есть нерекурсивная часть (базовое утверждение о том, что 1 является натуральным числом). Еще одним известным примером рекурсивного определения является определение функции факториала "!" для неотрицательных целых чисел:
В этом определении факториала "!" есть базовое утверждение (определение 0!) и рекурсивная часть. Согласно определению, факториал 6 вычисляется следующим образом: 6! = 6*5! = 6*5*4! = 6*5*4*3! = 6*5*4*3*2! = 6*5*4*3*2*1! = 6*5*4*3*2*1*1 = 720 2. Простой пример рекурсии Рассмотрим рекурсивную функцию "print_backwards о " из программы 2.1. Эта функция предназначена для ввода с клавиатуры последовательности символов. Для прекращения ввода пользователь должен напечатать специальный символ (точку). После этого функция печатает введенные символы в обратном порядке. #include int main () { print_backwards(); cout « "\n"; return 0; } void print_backwards() { char character; cout « "Введите символ (или '.' для завершения ввода): "; cin » character; if ( character != '.' ) 89 print_backwards(); cout « character; Программа 2.1. Программа 2.1 печатает на экране подобные сообщения: Введите символ (или '.' для завершения ввода): H Введите символ (или '.' для завершения ввода): i Введите символ (или '.' для завершения ввода): . iH Порядок выполнения функции "print_backwards ()" подробно описан в следующем параграфе. Пока обратите внимание на то, что вызов "print_backwards ()" (в ее собственном определении) находится внутри оператора "if". В определениях рекурсивных функций обычно есть некоторый оператор ветвления, у которого, как минимум, одна нерекурсивная ветвь, реализующая "базовое утверждение" определения функции. Если такой ветви нет, то функция будет вызывать себя бесконечно (в действительности, до тех пор, пока не будет занята вся память). В программе 2.1 базовое утверждение реализовано неявно - это возврат из функции, если был введен символ "." (точка). 3. Как выполняется рекурсивный вызов Порядок выполнения программы 2.1 легко понять с помощью нескольких схем. Главная функция начинается с вызова "print_backwards ()". Для выполнения вызова функции в памяти компьютера выделяется некоторое количество памяти (необходимое для запоминания адреса возврата, для создания копий параметров по значению и для передачи параметров-указателей). Свободная область памяти в момент первого вызова "print_backwards ()" на рис. 1 изображена в виде пустого прямоугольника. Внутри прямоугольника показано содержимое экрана в соответствующие моменты времени (на схемах считается, что направление "сверху-вниз" соответствует увеличению времени, прошедшему с момента запуска программы). НАЧАЛО ГЛАВНОЙ ФУНКПЩ 1-Й ВШОВ prizt_backiea?ds НАЧАЛО ГЛАВНОЙ ФУНШЩ 1-Й ВЯЗОВ print backwards Введите символ: Н 2-Й BS30B print_baclo?ar Рис. 1.. Свободная область памяти перед первым вызовом "print_backwards () Рис. 2. Свободная область памяти перед вторым вызовом "print_backwards () Выполнение функции "print_backwards ()" начинается со ввода символа, а затем происходит второй вызов "print_backwards ()" (в этот момент программа еще не 90 начинала обратную печать символов). Для второго вызова также выделяется некоторое количество памяти, поэтому объем свободной памяти уменьшается (рис. 2). Далее процесс повторяется, но, допустим, при третьем вызове "print_backwards ()" пользователь ввел завершающий символ (точку). Поэтому после третьего вызова происходит возврат в вызывающую функцию (т.е. во второй экземпляр "print_backwards () "), см. рис. 3. начало главной" функции 1-й ВЯЗОВ print_backwards
Рис. 3. Возврат из 3-го экземпляра функции "print_backwards () " во второй. НАЧАЛО ГЛАВНОЙ ФУНКЦИИ 1-й B5I3OB print backwards
ЗАВЕРШЕНИЕ 1-го ВВЗОВА ПЕЧАТЬ НОВОЙ СТРОКИ ЗАВЕРШЕНИЕ ГЛАВНОЙ ФУНКЦИИ Рис. 4.. Завершение выполнения программы. Второй экземпляр "print_backwards ()" завершается, но перед завершением выводит на экран символ "i". В свою очередь, первый экземпляр функции перед завершением работы напечатает на экране символ "H" (рис. 4). Для организации вызовов функций и создания автоматических переменных в программах на Си++ отводится специальная область памяти - стек. Память, необходимая для очередного вызова функции, выделяется в верхней части стека (в старших адресах). При завершении функции размер стека уменьшается на соответствующую величину. Изменение состояния программного стека для рассмотренного выше примера показано на рис. 5. стек) -и бывоб 1-Й БЫЗОБ 2-й вызр (пустой стек)
Рис. 5.. Последовательность состояний стека программы 2.1 применительно к тестовому примеру. Стек в программах на Си++ используется при вызове всех функций, а не только рекурсивных. Стек, как и связный список, является одной из разновидностей абстрактных типов данных. Характерная особенность стека - соответствие принципу "последним прибыл - первым обслужен" (в отличие от стека, очередь является примером абстрактного типа данных, действующего по принципу "последним прибыл - последним обслужен"). 91 4. Еще три примера рекурсии В этом параграфе приводятся три примера рекурсивных функций. В 3-й лекции рассматривалась функция для вычисления факториала целого положительного числа (лекция 3, программа 3.1). Ниже приведен рекурсивный аналог этой функции: int factorial( int number ) { if ( number < 0 ) { cout << "\nОшибка - отрицательный аргумент факториала\n"; exit(1); } else if ( number == 0 ) return 1; return number*factorial( number - 1 ); } |
И. П. Гиривенко к т. н., доцент, зав кафедрой информатики и вычислительной... Цели: 1 продолжить знакомство с героями поэмы «Полтава»; познакомиться с изображением Полтавской битвы в поэме | И. П. Гиривенко к т. н., доцент, зав кафедрой информатики и вычислительной... ... | ||
Методические рекомендации по подготовке, оформлению, предзащите и... В. А. Усков, заместитель декана естественно-географического факультета по развитию, доцент кафедры физической географии и методики... | Проблемы коммуникации М. Е. Евсевьева (зав кафедрой, доцент А. А. Ветошкин); С. А. Борисова, директор Института международных отношений Ульяновского государственного... | ||
Программа по формированию навыков безопасного поведения на дорогах... Елена Святославовна Симакова, кандидат педагогических наук, доцент кафедры гуманитарных и естественнонаучных дисциплин Рязанского... | Программа курса по выбору «Орнитология» предназначена для студентов... Автор программы: к б н., доцент, зав кафедрой биологии и химии Марина Николаевна Харламова | ||
Российской Федерации Федеральное государственное образовательное... Петренко И. М., зав кафедрой экономической теории, д-р экон наук профессор Дулин М. П., зав кафедрой педагогики и психологии, д-р... | Рахманкулова Людмила Кузьминична, кандидат филологических наук, доцент... Автор программы: С. А. Виноградова, кандидат филологических наук, доцент, зав кафедрой английского языка и английской филологии | ||
Протокол №5 От 12 января 2012 г Заседания кафедры электроники и вычислительной... Зав кафедрой Хакимова Г. Г. сообщила, что кафедра проводит 2-й Чемпионат по цифровой схемотехнике | Лингвистические проблемы Московского государственного педагогического института иностранных языков им. М. Тореза (зав кафедрой доцент Ю. А. Денисенко); д-р... | ||
Мгпу учебно-методический комплекс дисциплины А. В. Прялухина, кандидат психологических наук, доцент, зав кафедрой психологии Российского государственного социального университета... | Рабочая программа по дисциплине «теория экономического анализа» Рецензент: к с н., доцент, зав кафедрой «Экономики и управления на предприятии и маркетинга» Пятигорского государственного гуманитарно-технологического... | ||
Рабочая программа по дисциплине «международный менеджмент» Рецензент: к с н., доцент, зав кафедрой «Экономики и управления на предприятии и маркетинга» Пятигорского государственного гуманитарно-технологического... | Методические рекомендации по написанию курсовых работ дисциплине Рецензент: к с н., доцент, зав кафедрой «Экономики и управления на предприятии и маркетинга» Пятигорского государственного гуманитарно-технологического... | ||
Учебное пособие Краснодар 2008 В. А. Оробец); кафедра паразитологии и ветсанэкспертизы Донского государственного аграрного университета (зав кафедрой, проф., к... | Рабочая программа по дисциплине «Экономика организаций (предприятий)... Рецензент: к с н., доцент, зав кафедрой «Экономики и управления на предприятии и маркетинга» Пятигорского государственного гуманитарно-технологического... |