Лекция основы си++ 7




НазваниеЛекция основы си++ 7
страница14/18
Дата публикации08.06.2014
Размер1.94 Mb.
ТипЛекция
literature-edu.ru > Курсовая работа > Лекция
1   ...   10   11   12   13   14   15   16   17   18

Рис. 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).

Пример экранного ввода/вывода текстовой программы в типичном сеансе работы:

Введите первое слово (или '.' для завершения списка): это

Введите следующее слово (или '.' для завершения списка): тестовое

Введите следующее слово (или '.' для завершения списка): сообщение

Введите следующее слово (или '.' для завершения списка): из

Введите следующее слово (или '.' для завершения списка): нескольких

Введите следующее слово (или '.' для завершения списка): слов

Введите следующее слово (или '.' для завершения списка): на

Введите следующее слово (или '.' для завершения списка): русском

Введите следующее слово (или '.' для завершения списка): языке

Введите следующее слово (или '.' для завершения списка):

ТЕКУЩЕЕ СОДЕРЖИМОЕ СПИСКА:

это тестовое сообщение из нескольких слов на русском языке

ПОСЛЕ КАКОГО СЛОВА ВЫ ХОТИТЕ ВСТАВИТЬ НОВОЕ СЛОВО? это КАКОЕ СЛОВО ВЫ ХОТИТЕ ВСТАВИТЬ? небольшое

ТЕКУЩЕЕ СОДЕРЖИМОЕ СПИСКА:

это небольшое тестовое сообщение из нескольких слов на русском языке

КАКОЕ СЛОВО ВЫ ХОТИТЕ УДАЛИТЬ? тестовое

ТЕКУЩЕЕ СОДЕРЖИМОЕ СПИСКА:

это небольшое сообщение из нескольких слов на русском языке

СОДЕРЖИМОЕ СПИСКА ПОСЛЕ СОРТИРОВКИ:

из на небольшое нескольких русском слов сообщение это языке

Подсказки. Основные черты алгоритма добавления нового узла заключаются в сле­дующем:

  1. Для поиска и запоминания узла, после которого надо вставить новый
    узел, применяется дополнительный указатель.


  2. Для создания нового узла применяется еще один дополнительный указа­
    тель.


  3. После выполнения действий 1) и 2) следует модифицировать соответ­
    ствующие указатели.


Возможный алгоритм удаления узла:

  1. Заведите дополнительный указатель на узел перед удаляемым узлом и указатель
    на удаляемый узел.


  2. Измените указатель внутри узла, расположенном до удаляемого узла, так, чтобы
    он указывал на узел, расположенный после удаляемого.


  3. Удалите лишний узел.

Для сортировки связного списка несложно адаптировать алгоритм сортиров­ки массива из 6-й лекции.

ЛЕКЦИЯ 8. Рекурсия

1. Понятие рекурсии

В хорошо спроектированной программе на Си++ в определениях функций час­то встречаются вызовы других функций этой же программы или библиотеки Си++. Например, в предыдущей (7-й) лекции, в определении функции "assign_list (...)" есть вызов "assign_new_node (...)". Если в определении функции содержится вызов ее самой, то такая функция называется рекурсивной.

Понятие рекурсии хорошо известно в математике и логике. Например, можно привести следующее рекурсивное определение натуральных чисел:

  • 1 является натуральным числом

  • целое число, следующее за натуральным, есть натуральное число.

В данном контексте понятие рекурсии тесно связано с понятием математиче­ской индукции. Обратите внимание, что в приведенном определении натуральных чи­сел есть нерекурсивная часть (базовое утверждение о том, что 1 является натураль­ным числом).

Еще одним известным примером рекурсивного определения является опреде­ление функции факториала "!" для неотрицательных целых чисел:

  • 0! = 1

  • если n>0, тоn! = n*(n-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

Введите символ: Н 2-й ВПЗОВ print backwards




Введите символ: i 3-й ВЫЗОВ print backwards










Введите символ:.










ЗАВЕРШЕНИЕ 3-го ВЫЗОВА













Рис. 3. Возврат из 3-го экземпляра функции "print_backwards () " во второй.

НАЧАЛО ГЛАВНОЙ ФУНКЦИИ 1-й B5I3OB print backwards

Введите символ: Н 2-й ВЫЗОВ print backwards




Введите символ: i 3-й ВЫЗОВ print backwards










Введите символ: .










ЗАВЕРШЕНИЕ 3-го BS30BA ПЕЧАТЬ! i1




ЗАВЕРШЕНИЕ 2-го ВЫЗОВА ПЕЧАТЬ! Н1

ЗАВЕРШЕНИЕ 1-го ВВЗОВА ПЕЧАТЬ НОВОЙ СТРОКИ ЗАВЕРШЕНИЕ ГЛАВНОЙ ФУНКЦИИ

Рис. 4.. Завершение выполнения программы.

Второй экземпляр "print_backwards ()" завершается, но перед завершением вы­водит на экран символ "i". В свою очередь, первый экземпляр функции перед завер­шением работы напечатает на экране символ "H" (рис. 4).

Для организации вызовов функций и создания автоматических переменных в программах на Си++ отводится специальная область памяти - стек. Память, необхо­димая для очередного вызова функции, выделяется в верхней части стека (в старших адресах). При завершении функции размер стека уменьшается на соответствующую величину. Изменение состояния программного стека для рассмотренного выше при­мера показано на рис. 5.




стек)

бывоб

1-Й БЫЗОБ

2-й вызр


(пустой стек)


1-И БЫЗОБ
1

.-й вызов




Z-и вызов






















Рис. 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   ...   10   11   12   13   14   15   16   17   18

Похожие:

Лекция основы си++ 7 iconЛекция основы Си++ 9
Б73 Основы программирования на языке Си++: Для студентов физико-математических факультетов педагогических институтов. – Коломна:...

Лекция основы си++ 7 iconЛекция I и проблема языка и сознания лекция II 31 слово и его семантическое...
Монография представляет собой изложение курса лекций, про* читанных автором на факультете психологии Московского государственного...

Лекция основы си++ 7 iconЛекция психосексуальное развитие. Возрастная динамика взаимоотношения полов 15
Основы семейной психопедагогики (курс лекций) / В. И. Короткий. — Архангельск: М'арт, 2003. — 178 с

Лекция основы си++ 7 iconЛекция Архитектура 32-разрядных ос windows 7
Б73 Основы программирования на языке Си++: Для студентов физико-математических факультетов педагогических институтов. – Коломна:...

Лекция основы си++ 7 iconЛекция Основные понятия ооп 7
Б73 Основы программирования на языке Си++: Для студентов физико-математических факультетов педагогических институтов. – Коломна:...

Лекция основы си++ 7 iconЛекция №1. Введение. Элементы дифференциальной геометрии. 2
Лекция №5. Множества Жюлиа, множество Мандельброта и их компьютерное представление. 18

Лекция основы си++ 7 iconЛекция на тему: «Современные подходы к содержанию дополнительного образования детей»
...

Лекция основы си++ 7 iconЛекция в Дорнахе 22 мая 1920 года
Канта и протестантизма. Эта лекция вызвала негодование среди членов Лиги, культивировавших и признававших под названием монизма вообще...

Лекция основы си++ 7 iconКурс лекций Лекция Введение в философскую суицидологию. Лекция Общая...
Открыть, в чём состоит суть суицида, наука не в состоянии (по собственной ограниченной природе) и потому должна обращаться за объяснениями...

Лекция основы си++ 7 iconЛекция для слушателей курса «Основы религий»
Я не могу всего этого понять, потому что некоторые пытливые учителя, помню, меня просто одолевали вопросами, где найти, например,...

Литература


При копировании материала укажите ссылку © 2015
контакты
literature-edu.ru
Поиск на сайте

Главная страница  Литература  Доклады  Рефераты  Курсовая работа  Лекции