Практическо ръководство по програмиране на С++
СЪДЪРЖАНИЕ
СПИСЪК НА СЪКРАЩЕНИЯТА ...................................................................................................... 2
ПРЕДГОВОР ........................................................................................................................................ 3
1. СКАЛАРНИ ТИПОВЕ ДАННИ В C++. СЪВМЕСТИМОСТ ...................................................... 7
1.1 ОСНОВНИ ЕЛЕМЕНТИ НА ЕЗИКА. ......................................................................................... 7
1.1.1 Основни знакове ..................................................................................................................... 7
1.1.2 Идентификатори (имена) ...................................................................................................... 7
1.1.3 Ключови думи ............................................................................................................................ 7
1.1.4 Величини .................................................................................................................................... 8
1.1.5 Обща структура на програмата ............................................................................................ 9
1.1.6 Изрази ......................................................................................................................................... 9
1.2 СКАЛАРНИ ТИПОВЕ ДАННИ..................................................................................................... 9
1.2.1 Стандартни скаларни типове данни ................................................................................ 11
1.2.2 Целочислени типове ............................................................................................................. 11
1.2.3 Приближени (реални) типове ............................................................................................ 14
1.2.4 Логически (булев) тип ........................................................................................................... 16
1.2.5 Знаков тип ................................................................................................................................ 17
1.2.6 Изброим тип ............................................................................................................................ 18
1.3 СЪВМЕСТИМОСТ ...................................................................................................................... 18
1.3.1 Неявно преобразуване на типове ..................................................................................... 18
1.3.2 Явно преобразуване на типове........................................................................................... 19
1.4 ПРОГРАМИ ЗА ИЗЧИСЛЯВАНЕ НА ИЗРАЗИ ....................................................................... 19
1.4.1 Приоритет на операциите и асоциативност ................................................................... 19
1.4.2 Въвеждане и извеждане на данни .................................................................................... 20
1.5 ЗАДАЧИ И УПРАЖНЕНИЯ ........................................................................................................ 22
2. ОПЕРАТОРИ.................................................................................................................................... 24
2.1 ПРОСТИ ОПЕРАТОРИ ............................................................................................................... 24
2.2 СТРУКТУРИРАНИ ОПЕРАТОРИ ............................................................................................. 27
3. ЛИНЕЙНИ АЛГОРИТМИ .............................................................................................................. 29
4. РАЗКЛОНЕНИ АЛГОРИТМИ ....................................................................................................... 34
4.1 ЛОГИЧЕСКИ ИЗРАЗИ. ............................................................................................................... 34
4.2 ОПЕРАТОР IF ............................................................................................................................... 38
4.3 ОПЕРАТОР ЗА ИЗБОР НА ВАРИАНТИ SWITCH................................................................... 44
5. ОПЕРАТОР ЗА ЦИКЪЛ FOR......................................................................................................... 48
5.1 ЦИКЛИ FOR СЪС СТЪПКА РАЗЛИЧНА ОТ 1 ....................................................................... 50
5.2 ПОВЕЧЕ УПРАВЛЯВАЩИ ПРОМЕНЛИВИ ............................................................................ 51
5.3 ВЛОЖЕНИ ЦИКЛИ ...................................................................................................................... 54
6. ЦИКЛИ С УСЛОВИЯ. ИТЕРАЦИОННИ АЛГОРИТМИ ........................................................... 58
6.1 ЦИКЛИ С УСЛОВИЯ. .................................................................................................................. 58
6.1.1 Цикъл while ... ........................................................................................................................... 58
6.1.2 Цикъл do…while........................................................................................................................ 60
6.2 ОПЕРАТОРИ BREAK И CONTINUE ......................................................................................... 63
6.3 ИНТЕРПОЛАЦИЯ. РЕКУРЕНТНИ РЕДИЦИ ......................................................................... 64
6.4 БЕЗКРАЙНИ СУМИ ..................................................................................................................... 66
6.5 ЗАДАЧИ ЗА САМОСТОЯТЕЛНО РЕШАВАНЕ ........................................................................ 68
7. ЯВНО ИЗБРОИМ ТИП ДАННИ ................................................................................................... 70
7.1 ОПЕРАЦИИ НА ЯИТ.................................................................................................................... 71
7.2 СТАНДАРТНИ ФУНКЦИИ. ......................................................................................................... 71
7.3 ЗАДАЧИ И УПРАЖНЕНИЯ ........................................................................................................ 72
8. ПОДПРОГРАМИ ............................................................................................................................. 74
8.1 ФУНКЦИИ ...................................................................................................................................... 74
8.2 ФОРМАЛНИ И ФАКТИЧЕСКИ ПАРАМЕТРИ .......................................................................... 78
8.3 ОБЛАСТ И ПЕРИОД НА ДЕЙСТВИЕ НА ПРОМЕНЛИВИТЕ. КЛАСОВЕ ПАМЕТ. ......... 81
8.4 ПОДПРОГРАМИТЕ КАТО ПАРАМЕТРИ .................................................................................. 85
8.5 СТРАНИЧНИ ЕФЕКТИ НА ФУНКЦИИТЕ ............................................................................... 86
9. РЕКУРСИЯ. РЕКУРСИЯ И ИТЕРАЦИЯ ................................................................................... 98
9.1 РЕКУРСИВНИ ПОДПРОГРАМИ............................................................................................... 98
9.2 ВЗАИМНО–РЕКУРСИВНИ ПОДПРОГРАМИ. ПРЕДВАРИТЕЛНО ДЕКЛАРИРАНЕ НА ПОДПРОГРАМИ100
9.3 МЕХАНИЗЪМ НА ДЕЙСТВИЕ НА РЕКУРСИЯТА ............................................................... 100
9.4 ПРИМЕРНИ ЗАДАЧИ, КОИТО СЕ РЕШАВАТ С РЕКУРСИЯ............................................ 101
9.5 ВРЪЗКА МЕЖДУ РЕКУРСИЯ И ИТЕРАЦИЯ ...................................................................... 107
10. ОБЩИ ЗАДАЧИ И ТЕСТОВЕ .................................................................................................. 111
10.1 ЗАДАЧИ ..................................................................................................................................... 111
10.2 ТЕСТОВЕ.................................................................................................................................. 119
11. МАСИВИ ..................................................................................................................................... 122
11.1 ДЕФИНИРАНЕ НА МАСИВ ................................................................................................... 122
11.2 ИНИЦИАЛИЗАЦИЯ НА МАСИВИ ........................................................................................ 124
11.3 ЗАДАЧИ С ЕДНОМЕРНИ МАСИВИ (ВЕКТОРИ)............................................................... 124
11.4 ЗАДАЧИ С ДВУМЕРНИ МАСИВИ (МАТРИЦИ) ................................................................. 139
11.5 ОБЩИ ЗАДАЧИ ........................................................................................................................ 152
12. СОРТИРОВКА И ТЪРСЕНЕ. КОМБИНАТОРИКА .............................................................. 157
12.1 СОРТИРОВКА ......................................................................................................................... 157
12.1.1 Метод на простото вмъкване .......................................................................................... 158
12.1.2 Метод на мехурчето ........................................................................................................... 160
12.1.3 Сортировка чрез клатене (щейкър сортировка) ........................................................ 161
12.1.4 Метод на пряк избор (пряка селекция)......................................................................... 162
12.1.5 Сортировка на Шел............................................................................................................. 163
12.1.6 Бърза сортировка ............................................................................................................... 164
12.1.7 Метод на пирамидата ......................................................................................................... 166
12.2 ДВОИЧНО ТЪРСЕНЕ В ПОДРЕДЕН МАСИВ ................................................................... 168
12.3 КОМБИНАТОРИКА ................................................................................................................... 171
12.3.1 Пермутации ........................................................................................................................... 171
12.3.1.1 Алгоритъм за лексикографско пораждане ............................................................... 171
12.3.1.2 Алгоритъм с най-малък брой трансформации ........................................................ 173
12.3.2 Пораждане на всички подмножества. ........................................................................... 175
12.3.3 Комбинации без повторения. .......................................................................................... 176
13. ЗНАКОВ НИЗ ............................................................................................................................... 182
13.1 ДЕФИНИРАНЕ НА ЗНАКОВ НИЗ (ТЕКСТОВ ТИП) ........................................................... 182
13.2 ОПЕРАЦИИ С НИЗОВЕ .......................................................................................................... 183
13.2.1 Присвояване на стойност на текстова променлива.................................................... 183
13.2.2 Въвеждане и извеждане на данни от текстов тип ...................................................... 183
13.2.3 Достъп до отделни компоненти (знакове) на низ. ...................................................... 184
13.3 СТАНДАРТНИ ФУНКЦИИ ЗА РАБОТА С НИЗОВЕ ............................................................ 184
13.3.1 Копиране. ................................................................................................................................ 184
13.3.2 Копиране на n знака. ........................................................................................................... 185
13.3.3 Сравнение. ............................................................................................................................. 185
13.3.4 Сравнение на n знака. ........................................................................................................ 186
13.3.5 Конкатенация ......................................................................................................................... 186
13.3.6 Конкатенация на n знака .................................................................................................... 186
13.3.7 Дължина (брой знакове) ..................................................................................................... 186
13.3.8 Търсене на подниз ............................................................................................................... 186
13.3.9 Търсене на знак .................................................................................................................... 186
13.3.10 Преобразуване на цяло число в низ (библиотека stdlib *) ...................................... 187
13.3.11 Преобразуване на реално число в низ (библиотека stdlib *) .................................. 187
13.3.12 Преобразуване на низ в число (библиотека stdlib) ................................................... 188
13.3.13 Преобразуване (конвертиране) на знакове (библиотека ctype) ............................ 188
13.3.14 Преобразуване (конвертиране) на низове (библиотека string *) .......................... 188
13.4 ТЕСТОВЕ И ЗАДАЧИ ................................................................................................................. 189
14. МОДЕЛИРАНЕ НА МНОЖЕСТВА. ТЕКСТООБРАБОТКА ..................................................... 202
14.1 ФУНКЦИИ ИЗПОЛЗВАЩИ МНОЖЕСТВА ОТ ЗНАКОВЕ ................................................... 202
14.1.1 Намиране на първия знак принадлежащ на дадено множество............................. 202
14.1.2 Намиране на дължината на най-дългия водещ подниз
от знакове принадлежащи на дадено множество ................................................................... 202
14.1.3 Намиране на първия знак принадлежащ на дадено множество.............................203
14.1.4 Сегментиране (разбор) на низ, чрез задаване на множеството
от разделители .................................................................................................................................. 203
14.2 УСТАНОВЯВАНЕ НА ПРИНАДЛЕЖНОСТ .......................................................................... 204
14.3 ЗАДАЧИ И ТЕСТОВЕ ................................................................................................................ 204
15. СТРУКТУРИ И ОБЕДИНЕНИЯ ................................................................................................ 214
15.1 ДЕФИНИРАНЕ НА СТРУКТУРА ............................................................................................. 214
15.2 ОПЕРАЦИИ СЪС СТРУКТУРИ .............................................................................................. 215
15.2.1 Достъп до поле на структура............................................................................................... 215
15.2.2 Присвояване на стойност на поле от структура ............................................................ 215
15.2.3 Въвеждане и извеждане на стойности ............................................................................ 215
15.2.4 Участие на полетата в изрази ............................................................................................ 216
15.3 ВЛОЖЕНИ СТРУКТУРИ............................................................................................................ 216
15.4 СТРУКТУРИ И ФУНКЦИИ ЗА КАЛЕНДАРНО ВРЕМЕ ........................................................ 216
15.4.1 Извличане на текущо календарно време – time.......................................................... . 217
15.4.2 Преобразуване на календарно време от тип time_t в tm структура. ....................... 217
15.4.3 Преобразуване на календарно време от tm структура в тип time_t. ........................218
15.4.4 Изчисляване разлика на 2 календарни времена. ........................................................218
15.4.5 Преобразуване на календарно време в знаков низ ....................................................219
15.5 ОБЕДИНЕНИЯ ........................................................................................................................... 220
15.6 ЗАДАЧИ И ТЕСТОВЕ ..................................................................................................................220
16. МАСИВИ С ЕЛЕМЕНТИ ОТ ТИП СТРУКТУРА. ХЕШ-ТАБЛИЦИ ....................................... 225
16.1 МАСИВИ С ЕЛЕМЕНТИ ОТ ТИП СТРУКТУРА..................................................................... 225
16.2 ХЕШ-ТАБЛИЦИ С ВЪЗМОЖНОСТ ЗА КОЛИЗИИ ............................................................... 239
17. ОБЩИ ЗАДАЧИ ............................................................................................................................ . 258
17.1 ЗАДАЧИ ОТ СЕМЕСТРИАЛНИ ИЗПИТИ ............................................................................... 258
17.2 ЗАДАЧИ ЗА ПОДГОТОВКА ЗА ИЗПИТИ
В ПЛОВДИВСКИ УНИВЕРСИТЕТ „ПАИСИЙ ХИЛЕНДАРСКИ” ................................................. 265
17.3 ЗАДАЧИ ОТ ДЪРЖАВНИ ИЗПИТИ ВЪВ ФМИ НА ПУ .......................................................... 273
17.4 ЗАДАЧИ ОТ КАНДИДАТСТУДЕНТСКИ ИЗПИТИ В ПУ „ПАИСИЙ ХИЛЕНДАРСКИ” .... 278
17.5 ТЕСТОВЕ ОТ КАНДИДАТСТУДЕНТСКИ ИЗПИТИ .............................................................. 307
17.6 ОТГОВОРИ И ОБЯСНЕНИЯ НА ТЕСТОВЕТЕ ..................................................................... 337
ПРИЛОЖЕНИЯ ..................................................................................................................................... 340