Лекция основы си++ 7
|
Скачать 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 #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 void print_backwards(); 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 ); } |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Похожие:
 |
Лекция основы Си++ 9 Б73 Основы программирования на языке Си++: Для студентов физико-математических факультетов педагогических институтов. – Коломна:... |
|
Лекция I и проблема языка и сознания лекция II 31 слово и его семантическое... Монография представляет собой изложение курса лекций, про* читанных автором на факультете психологии Московского государственного... |
|
Лекция психосексуальное развитие. Возрастная динамика взаимоотношения полов 15 Основы семейной психопедагогики (курс лекций) / В. И. Короткий. — Архангельск: М'арт, 2003. — 178 с |
|
Лекция Архитектура 32-разрядных ос windows 7 Б73 Основы программирования на языке Си++: Для студентов физико-математических факультетов педагогических институтов. – Коломна:... |
|
Лекция Основные понятия ооп 7 Б73 Основы программирования на языке Си++: Для студентов физико-математических факультетов педагогических институтов. – Коломна:... |
|
Лекция №1. Введение. Элементы дифференциальной геометрии. 2 Лекция №5. Множества Жюлиа, множество Мандельброта и их компьютерное представление. 18 |
|
Лекция на тему: «Современные подходы к содержанию дополнительного образования детей» ... |
|
Лекция в Дорнахе 22 мая 1920 года Канта и протестантизма. Эта лекция вызвала негодование среди членов Лиги, культивировавших и признававших под названием монизма вообще... |
|
Курс лекций Лекция Введение в философскую суицидологию. Лекция Общая... Открыть, в чём состоит суть суицида, наука не в состоянии (по собственной ограниченной природе) и потому должна обращаться за объяснениями... |
|
Лекция для слушателей курса «Основы религий» Я не могу всего этого понять, потому что некоторые пытливые учителя, помню, меня просто одолевали вопросами, где найти, например,... |