МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Тульського державного педагогічного університету
ІМ. Л.М. ТОЛСТОГО
Кафедра іноземних мов
РЕФЕРАТ
на право отримання допуску до складання кандидатського іспиту
з іноземної мови
Тема: "Алгоритми та структури даних. Програмування у Cі "
Гордєєв В'ячеслав Валерійович, аспірант
кафедри інформатики та обчислювальної техніки
ТГПУ ім. Л.М. Толстого
Матеріали реферату: Grundlagen Computernetze, Prof. Jьrgen Plate, FH Mьnchen, FB 04, http://www.netzmafia.de/skripten/ad/index.html. р. 232.
Дата здачі: квітень 2004 р .
Сі - це структурний мова програмування високого рівня, створений в 1972 році Керніганом та Рітчі. Він створювався як мова для розробки операційної системи UNIX. Cи дозволяє працювати з даними практично так само ефективно, як на асемблері (машинному мовою), надаючи при цьому структуровані керуючі конструкції та абстракції високого рівня (структури і масиви). Саме з цим пов'язана його величезна популярність і понині. При цьому компілятор C дуже слабо контролює типи, тому дуже легко написати зовні зовсім правильну, але логічно помилкову програму.
У вступі Юрген Платі коротко розповідає про структуру книги. Вона складається з двох основних частин - основних понять алгоритмізації та основ програмування. Обидві частини є досить тісно взаємопов'язані, тому що при вивченні основних понять доводиться вдаватися до прикладів рішення задач на конкретних мовах програмування, а при вивченні програмування необхідно постійно пам'ятати основи алгоритмізації.
Автора спонукало написати цю книгу ситуація, яка склалася у світі створення програмного забезпечення. Незважаючи на те, що в останні роки в методиці створення програмного забезпечення зроблено великий прогрес - з'явилася дисципліна програмна інженерія (техніка програмного забезпечення), багато розробників недостатньо кваліфіковані в цій області. Тому необхідно краще навчати мистецтву програмування. І ця книга в зручній формі викладає основні прийоми програмування, що супроводжується великою кількістю прикладів на мові програмування С.
Кожен програміст повинен виконувати ряд правил при написанні програм:
§ Грунтовно подумати перед тим, як натискати на клавіші.
§ Мати власний стиль програмування.
§ Навчитися звертатися з підводними каменями і з недбалістю мов програмування.
§ Виконувати безліч вправ для досягнення результату.
§ Що таке "інформація"?
§ Що є "сполученням"?
§ Як інформація передається?
§ Як інформація є?
Поряд з енергією і матерією, інформація - це базове поняття універсального значення. В інформатиці поняття інформації дещо відрізняється від повсякденного. Інформація - це знання про що-небудь. Повідомлення служать для відображення інформації.
Обсяг інформаційного повідомлення фіксуються, визначається кількістю рішень в повідомленні і вимірюється в бітах.
Після абстрактної інформації автор переходить до конкретного відображення інформації, повідомлень. Для цього він наводить кілька визначень:
§ Повідомлення - набір символів для інформаційної передачі.
§ Символ - елемент символьного запасу, встановленої кінцевої маси різних символів.
§ Алфавіт - впорядкований набір символів.
§ Слово - послідовність символів, які розглядаються в певному зв'язку в якості єдиної величини.
Фізично повідомлення можуть представлятися через сигнали. При цьому розрізняються аналогові і цифрові сигнали. При аналогових або безперервних сигналах йде безперервний розподіл фізичної величини до обсягу інформації повідомлення, а при цифрових (дискретних) сигналах є тільки кінцеве число можливих станів фізичної величини. Цифрова техніка працює зазвичай з двома значеннями сигналу - 0 і 1.
Програма - це опис шляху, виходячи з певних вхідних даних, до певного результату або метод одержання рішення.
Звідси виділяють наступні властивості алгоритмів:
1. Повнота опису. Повинна бути показана повна послідовність дій. Посилання на невідому інформацію повинні бути відсутніми.
2. Повторюваність алгоритму. Алгоритм можна повторювати скільки завгодно часто і кожне повторення повинне приносити при рівних вхідних даних рівний результат.
3. Коректність алгоритму. На практиці коректність потрібно підтверджувати. Тому використовуються тести, при яких вже відомий для заявлених вхідних даних результат, і порівнюються потім дані з результатами.
4. Ефективність опису та виконання алгоритму.
Після опису властивостей необхідно дати досить коротке визначення поняття алгоритм:
Оброблюваний припис називається алгоритмом, якщо воно має такі властивості:
1. Припис описується кінцевими засобами.
2. Воно однозначно встановленим способом для введених даних видає точний результат.
Далі Юрген Платі говорить про те, що програма складається з кінцевого числа кроків і наводить конкретні приклади, наочно це обгрунтовуючи. Для написання програм необхідно використовувати особливі мови. Мови програмування - це нормовані мови, які служать для опису інструкцій обробки, структур даних, а також введення і виведення даних.
Необхідно перетворювати алгоритм завжди таким чином, щоб виділяти в ньому "подалгорітми". Теорія розробки програмного забезпечення грунтується на цій ідеї. Складні і комплексні структури та види діяльності реалізуються відомими структурами і простішими подалгорітмамі. Розробка та складання алгоритмів перетвориться в конструювання з готових алгоритмів.
Найпростіший мову програмування складається з системи команд. Це - вбудовані команди, вони порівнянні з командами мікрокалькулятора, які ви викликаєте, натискаючи клавіші. Цими командами можна виконувати арифметичні операції і зберігати результати дій.
Якщо будь-яким чином нумерують команди, то отримують машинну мову. Це найпростіший програмістський код. У цьому коді номер команди може використовуватися як її ім'я. Програма на машинному мовою є нічим іншим як довгою послідовністю таких слів коду.
Програмувати на мові машин досить важко. Тому стали переводити коди комп'ютерів в скорочення незашифрованого тексту. Відповідні перекладацькі програми, які називають асемблера, були розроблені для всіх комп'ютерів.
Програма на мові асемблера - це послідовність команд, які складаються з 2-4 букв і до яких додаються адреси елементів пам'яті. Наприклад, команда ADD R2, R6 складає вмісту комірки пам'яті R2 і вмісту R6 і зберігає суму в R6.
Проте з часом недоліки програмування на асемблері ставали все більш очевидними: залежність від моделі комп'ютера, винахід різних «трюків» у зв'язку з обмеженими можливостями мови, труднощі виправлення помилок, незручна форма роботи для людини. Це вело, в тому числі, до розвитку так званих "більш високих мов програмування", які більш зручні для людини.
У наступному параграфі автор розповідає про програми перекладу з машинної мови в більш зручну для людини форму - інтерпретатора і компіляторах. Ці програми переводили різні послідовності букв у форму, яку може розуміти комп'ютер. Разом з тим програми могли писатися мовою, який складається зі слів розмовної мови. Крім того, значно спрощується пошук помилок при програмуванні.
· Як можна нормувати мову?
· Що потрібно для опису алгоритмів?
У результаті нормування природної мови від багатьох варіацій поєднання залишається тільки єдина версія і скорочення з перестановками більше не допустимі.
Однак, алгоритмічна мова не обходиться одними символами, також необхідно давати імена показниками і відбувається дій.
"Більш високі" мови програмування як, наприклад, BASIC, FORTRAN, Pascal чи C розроблялися, щоб полегшити вирішення різних завдань. Автор описує розробників і призначення даних мов і особливо зупиняється на мовах Pascal та C.
Перш ніж писати програму, необхідно мати алгоритм для вирішення завдання. Алгоритм резюмує всі кроки, які потрібно пройти на шляху до вирішення. Він представлений таким чином, що може утворювати основу для програми, але ще не формулює її мовою програмування. Хороший програміст може перенести алгоритм без праці з розмовної мови в будь-яку мову програмування. Для початківця "нечіткість" розмовної мови являє навпаки велику проблему.
· Перший крок - це запис вимог клієнтів. Розробник намагається вловити необхідні для створення програмного забезпечення зв'язку і відкинути несуттєве.
· На наступному кроці розробник постає у ролі дизайнера. Подібно архітектору він створює структуру програмного забезпечення.
· На 3 етапі він грає роль програміста.
· На 4 етапі клієнт відчуває програмне забезпечення і розраховується.
Найважливіша фаза при складанні алгоритму - це аналіз постановки проблеми та міркування про рішення. Ця частина потребує більше часу, ніж власне робота з яким-небудь мовою програмування.
У програмуванні необхідно замінювати вербально представлений алгоритм командами мови. При цьому проходять такі етапи, як кодування, введення даних, переклад і тестування. Компілятор допомагає нам знаходити синтаксичні помилки, однак логічні помилки в програмі можна дізнаватися лише з допомогою роздумів і письмових тестів.
Послідовність - це набір команд, які запускаються у черговості їх запису. Тому говорять також про лінійної послідовності і повторюваної послідовності.
Вибір позначається нелінійної послідовністю з розгалуженням. Вибір шляху вирішення залежить від умови.
Структура повторення виходить, якщо послідовність команд повинна повторюватися неодноразово для вирішення завдання. Мінімум одна команда повинна піклуватися про те, щоб після кінцевого числа проходжень не було більше виконано умова повторення.
При написанні програми бажано розбиття її на модулі. У всіх вищих мовами програмування ця можливість реалізована у формі підпрограм. За застосування підпрограм свідчать такі причини: наочність, економічність, можливість швидкого внесення змін.
Потім автором розглядаються основні способи подання алгоритмів: вербальне опис, графічні способи представлення (логічна схема програми і структограмми).
Основною причиною появи нової дисципліни є неможливість повністю усунути помилки програмування. У рамках дисципліни «Розробка програмного забезпечення» розробляються моделі і методи, за допомогою яких навіть найбільші програмні системи можуть працювати безпомилково.
Найважливішими критеріями тут є: надійність і коректність, зручність і гнучкість (можливість швидких змін у програмі) роботи, легкість для читання програмного коду, ефективність створення та застосування.
У цьому параграфі досить докладно розглядаються теоретичні основи розробки ПЗ і особлива увага приділяється підготовці, аналізу проблеми і постановці завдань програмування.
Величезне значення тут мають типи даних, а також їх значення і властивості. Тип змінних величин характеризується діапазоном прийнятих значень. У кожній програмі домовляються про імені і тип змінних.
Крім змінних автор згадує і про константи, значення яких можуть безпосередньо вноситися до структури програми.
Кожна змінна характеризується своїм ім'ям і значенням. Особливу увагу Платі звертає на відмінність між розподілом значень і рівнянням в математичному сенсі. Таким чином, математичне рівняння X = X + 1 не має рішення, а в мові програмування цей запис означає, що "додають 1 до значення X і зберігають результат знову в X" або коротше "Підвищують X на 1".
Автор пояснює також, з чого складаються вираження в мовах програмування. Це формули, які завжди дають якийсь результат і складаються з операндів (константа, змінні величини і функції), операторів (однозначних і двозначних).
Далі автор детально зупиняється на стандартних типах даних, які використовуються в усіх мовах програмування:
· Boolean - логічний тип (приймає значення True або False).
· Integer - тип цілих чисел. Тульського державного педагогічного університету
ІМ. Л.М. ТОЛСТОГО
Кафедра іноземних мов
РЕФЕРАТ
на право отримання допуску до складання кандидатського іспиту
з іноземної мови
Тема: "Алгоритми та структури даних. Програмування у Cі "
Гордєєв В'ячеслав Валерійович, аспірант
кафедри інформатики та обчислювальної техніки
ТГПУ ім. Л.М. Толстого
Матеріали реферату: Grundlagen Computernetze, Prof. Jьrgen Plate, FH Mьnchen, FB 04, http://www.netzmafia.de/skripten/ad/index.html. р. 232.
Дата здачі: квітень
Тула - 2004
Введення
Дана книга написана професором Мюнхенського університету Юргеном Платі. Вона входить в серію книг, присвячених інформаційним технологіям, які виходять в рамках проекту «Netzmafia». Книга присвячена одному з головних розділів інформатичних освіти - алгоритмізації та програмування і адресована тим, хто бажає познайомитися і зануритися у світ алгоритмів і розробки програм. Вона складається з двох досить докладних лекцій з тем «Алгоритми та структури даних» та «Програмування». У книзі вводиться поняття алгоритму і розглядаються всі необхідні поняття, пов'язані з алгоритмами. Потім обговорюються принципи написання алгоритмів і складання програм мовою програмування Сі.Сі - це структурний мова програмування високого рівня, створений в 1972 році Керніганом та Рітчі. Він створювався як мова для розробки операційної системи UNIX. Cи дозволяє працювати з даними практично так само ефективно, як на асемблері (машинному мовою), надаючи при цьому структуровані керуючі конструкції та абстракції високого рівня (структури і масиви). Саме з цим пов'язана його величезна популярність і понині. При цьому компілятор C дуже слабо контролює типи, тому дуже легко написати зовні зовсім правильну, але логічно помилкову програму.
У вступі Юрген Платі коротко розповідає про структуру книги. Вона складається з двох основних частин - основних понять алгоритмізації та основ програмування. Обидві частини є досить тісно взаємопов'язані, тому що при вивченні основних понять доводиться вдаватися до прикладів рішення задач на конкретних мовах програмування, а при вивченні програмування необхідно постійно пам'ятати основи алгоритмізації.
Автора спонукало написати цю книгу ситуація, яка склалася у світі створення програмного забезпечення. Незважаючи на те, що в останні роки в методиці створення програмного забезпечення зроблено великий прогрес - з'явилася дисципліна програмна інженерія (техніка програмного забезпечення), багато розробників недостатньо кваліфіковані в цій області. Тому необхідно краще навчати мистецтву програмування. І ця книга в зручній формі викладає основні прийоми програмування, що супроводжується великою кількістю прикладів на мові програмування С.
Кожен програміст повинен виконувати ряд правил при написанні програм:
§ Грунтовно подумати перед тим, як натискати на клавіші.
§ Мати власний стиль програмування.
§ Навчитися звертатися з підводними каменями і з недбалістю мов програмування.
§ Виконувати безліч вправ для досягнення результату.
1. Дані та алгоритми
У цій главі автор зібрав основний теоретичний матеріал з алгоритмізації. Тут представлений загальний огляд як програмного, так і апаратного забезпечення. Але основний наголос природно робиться на поняття алгоритму, способи запису алгоритмів, методи та етапи складання програм.1.1 Основні поняття: повідомлення та інформація
У цьому параграфі професором розглядаються наступні питання:§ Що таке "інформація"?
§ Що є "сполученням"?
§ Як інформація передається?
§ Як інформація є?
Поряд з енергією і матерією, інформація - це базове поняття універсального значення. В інформатиці поняття інформації дещо відрізняється від повсякденного. Інформація - це знання про що-небудь. Повідомлення служать для відображення інформації.
Обсяг інформаційного повідомлення фіксуються, визначається кількістю рішень в повідомленні і вимірюється в бітах.
Після абстрактної інформації автор переходить до конкретного відображення інформації, повідомлень. Для цього він наводить кілька визначень:
§ Повідомлення - набір символів для інформаційної передачі.
§ Символ - елемент символьного запасу, встановленої кінцевої маси різних символів.
§ Алфавіт - впорядкований набір символів.
§ Слово - послідовність символів, які розглядаються в певному зв'язку в якості єдиної величини.
Фізично повідомлення можуть представлятися через сигнали. При цьому розрізняються аналогові і цифрові сигнали. При аналогових або безперервних сигналах йде безперервний розподіл фізичної величини до обсягу інформації повідомлення, а при цифрових (дискретних) сигналах є тільки кінцеве число можливих станів фізичної величини. Цифрова техніка працює зазвичай з двома значеннями сигналу - 0 і 1.
1.2 Створення програмного забезпечення (програмування)
Цей параграф Платі починає з пояснення поняття алгоритм. Автор говорить про те, що алгоритми повинні розроблятися не для спеціальних цілей, а містити кроки, які потрібно застосовувати при вирішенні певного класу проблем, а не для окремого прикладу.Програма - це опис шляху, виходячи з певних вхідних даних, до певного результату або метод одержання рішення.
Звідси виділяють наступні властивості алгоритмів:
1. Повнота опису. Повинна бути показана повна послідовність дій. Посилання на невідому інформацію повинні бути відсутніми.
2. Повторюваність алгоритму. Алгоритм можна повторювати скільки завгодно часто і кожне повторення повинне приносити при рівних вхідних даних рівний результат.
3. Коректність алгоритму. На практиці коректність потрібно підтверджувати. Тому використовуються тести, при яких вже відомий для заявлених вхідних даних результат, і порівнюються потім дані з результатами.
4. Ефективність опису та виконання алгоритму.
Після опису властивостей необхідно дати досить коротке визначення поняття алгоритм:
Оброблюваний припис називається алгоритмом, якщо воно має такі властивості:
1. Припис описується кінцевими засобами.
2. Воно однозначно встановленим способом для введених даних видає точний результат.
Далі Юрген Платі говорить про те, що програма складається з кінцевого числа кроків і наводить конкретні приклади, наочно це обгрунтовуючи. Для написання програм необхідно використовувати особливі мови. Мови програмування - це нормовані мови, які служать для опису інструкцій обробки, структур даних, а також введення і виведення даних.
Необхідно перетворювати алгоритм завжди таким чином, щоб виділяти в ньому "подалгорітми". Теорія розробки програмного забезпечення грунтується на цій ідеї. Складні і комплексні структури та види діяльності реалізуються відомими структурами і простішими подалгорітмамі. Розробка та складання алгоритмів перетвориться в конструювання з готових алгоритмів.
Найпростіший мову програмування складається з системи команд. Це - вбудовані команди, вони порівнянні з командами мікрокалькулятора, які ви викликаєте, натискаючи клавіші. Цими командами можна виконувати арифметичні операції і зберігати результати дій.
Якщо будь-яким чином нумерують команди, то отримують машинну мову. Це найпростіший програмістський код. У цьому коді номер команди може використовуватися як її ім'я. Програма на машинному мовою є нічим іншим як довгою послідовністю таких слів коду.
Програмувати на мові машин досить важко. Тому стали переводити коди комп'ютерів в скорочення незашифрованого тексту. Відповідні перекладацькі програми, які називають асемблера, були розроблені для всіх комп'ютерів.
Програма на мові асемблера - це послідовність команд, які складаються з 2-4 букв і до яких додаються адреси елементів пам'яті. Наприклад, команда ADD R2, R6 складає вмісту комірки пам'яті R2 і вмісту R6 і зберігає суму в R6.
Проте з часом недоліки програмування на асемблері ставали все більш очевидними: залежність від моделі комп'ютера, винахід різних «трюків» у зв'язку з обмеженими можливостями мови, труднощі виправлення помилок, незручна форма роботи для людини. Це вело, в тому числі, до розвитку так званих "більш високих мов програмування", які більш зручні для людини.
У наступному параграфі автор розповідає про програми перекладу з машинної мови в більш зручну для людини форму - інтерпретатора і компіляторах. Ці програми переводили різні послідовності букв у форму, яку може розуміти комп'ютер. Разом з тим програми могли писатися мовою, який складається зі слів розмовної мови. Крім того, значно спрощується пошук помилок при програмуванні.
1.3 Алгоритмічні мови
У цьому розділі автор досліджує, які властивості повинні мати мови, які використовуються для опису алгоритмів (алгоритмічні мови). Мова йде про нормованих мовах, які служать опису алгоритмів. Тут Юрген Платі відповідає на 2 основних питання:· Як можна нормувати мову?
· Що потрібно для опису алгоритмів?
У результаті нормування природної мови від багатьох варіацій поєднання залишається тільки єдина версія і скорочення з перестановками більше не допустимі.
Однак, алгоритмічна мова не обходиться одними символами, також необхідно давати імена показниками і відбувається дій.
"Більш високі" мови програмування як, наприклад, BASIC, FORTRAN, Pascal чи C розроблялися, щоб полегшити вирішення різних завдань. Автор описує розробників і призначення даних мов і особливо зупиняється на мовах Pascal та C.
Перш ніж писати програму, необхідно мати алгоритм для вирішення завдання. Алгоритм резюмує всі кроки, які потрібно пройти на шляху до вирішення. Він представлений таким чином, що може утворювати основу для програми, але ще не формулює її мовою програмування. Хороший програміст може перенести алгоритм без праці з розмовної мови в будь-яку мову програмування. Для початківця "нечіткість" розмовної мови являє навпаки велику проблему.
1.4 Від проблеми до рішення
У цьому параграфі автор розповідає про найважливіше етапі створення програм - цілях програмування: навіщо і чому програмне забезпечення повинно створюватися і що має вміти робити. Є мінімум 2 учасники процесу створення ПЗ: клієнт і розробник.· Перший крок - це запис вимог клієнтів. Розробник намагається вловити необхідні для створення програмного забезпечення зв'язку і відкинути несуттєве.
· На наступному кроці розробник постає у ролі дизайнера. Подібно архітектору він створює структуру програмного забезпечення.
· На 3 етапі він грає роль програміста.
· На 4 етапі клієнт відчуває програмне забезпечення і розраховується.
Найважливіша фаза при складанні алгоритму - це аналіз постановки проблеми та міркування про рішення. Ця частина потребує більше часу, ніж власне робота з яким-небудь мовою програмування.
У програмуванні необхідно замінювати вербально представлений алгоритм командами мови. При цьому проходять такі етапи, як кодування, введення даних, переклад і тестування. Компілятор допомагає нам знаходити синтаксичні помилки, однак логічні помилки в програмі можна дізнаватися лише з допомогою роздумів і письмових тестів.
1.5 Розвиток і зображення алгоритму
У цьому параграфі Юрген Платі звертає увагу, що команди програми складаються з чотирьох основних структур: послідовностей, вибору, повторення і підпрограм.Послідовність - це набір команд, які запускаються у черговості їх запису. Тому говорять також про лінійної послідовності і повторюваної послідовності.
Вибір позначається нелінійної послідовністю з розгалуженням. Вибір шляху вирішення залежить від умови.
Структура повторення виходить, якщо послідовність команд повинна повторюватися неодноразово для вирішення завдання. Мінімум одна команда повинна піклуватися про те, щоб після кінцевого числа проходжень не було більше виконано умова повторення.
При написанні програми бажано розбиття її на модулі. У всіх вищих мовами програмування ця можливість реалізована у формі підпрограм. За застосування підпрограм свідчать такі причини: наочність, економічність, можливість швидкого внесення змін.
Потім автором розглядаються основні способи подання алгоритмів: вербальне опис, графічні способи представлення (логічна схема програми і структограмми).
1.6 Розвиток програмного забезпечення
У цьому параграфі професор розповідає про причини появи нової дисципліни в межах інформатики, а також намагається визначити область її застосування.Основною причиною появи нової дисципліни є неможливість повністю усунути помилки програмування. У рамках дисципліни «Розробка програмного забезпечення» розробляються моделі і методи, за допомогою яких навіть найбільші програмні системи можуть працювати безпомилково.
Найважливішими критеріями тут є: надійність і коректність, зручність і гнучкість (можливість швидких змін у програмі) роботи, легкість для читання програмного коду, ефективність створення та застосування.
У цьому параграфі досить докладно розглядаються теоретичні основи розробки ПЗ і особлива увага приділяється підготовці, аналізу проблеми і постановці завдань програмування.
1.7 Введення в структури даних
У цьому розділі автор розповідає про те, що дисципліна розробки програм сформувалася поряд з проблемно-орієнтованим програмуванням. При цьому спочатку визначається структура даних для кожного оброблюваного обсягу даних. Потім встановлюють, які види зв'язків між ним існують.Величезне значення тут мають типи даних, а також їх значення і властивості. Тип змінних величин характеризується діапазоном прийнятих значень. У кожній програмі домовляються про імені і тип змінних.
Крім змінних автор згадує і про константи, значення яких можуть безпосередньо вноситися до структури програми.
Кожна змінна характеризується своїм ім'ям і значенням. Особливу увагу Платі звертає на відмінність між розподілом значень і рівнянням в математичному сенсі. Таким чином, математичне рівняння X = X + 1 не має рішення, а в мові програмування цей запис означає, що "додають 1 до значення X і зберігають результат знову в X" або коротше "Підвищують X на 1".
Автор пояснює також, з чого складаються вираження в мовах програмування. Це формули, які завжди дають якийсь результат і складаються з операндів (константа, змінні величини і функції), операторів (однозначних і двозначних).
Далі автор детально зупиняється на стандартних типах даних, які використовуються в усіх мовах програмування:
· Boolean - логічний тип (приймає значення True або False).
· Character - символьний тип.
· Real - тип дійсних чисел.
Також він розглядає структурні типи даних:
· Feld (Array) - Поле (масив). Змінні величини цього типу містять безліч елементів однакового стандартного типу.
· Record (Structure) - Записи (зв'язку). Містять елементи різного типу і мають кожен своє ім'я.
У висновку огляду розглядається загальний тип даних - файли. Вони складаються з великої кількості даних різних типів. Разом з даним типом визначається кілька стандартних операцій: відкриття та закриття доступу до файлу, читання з файлу і запис даних у файл.
1.9 Забезпечення високої якості розробки програм
Професор визначає дане в заголовку поняття так:Якість програмного забезпечення - це сукупність ознак і значень програмного продукту, які необхідні для нормального функціонування програми та задоволення потреб користувачів.
Платі виділяє наступні ознаки ПЗ, які визначають його якість:
1. Функціональність
2. Надійність
3. Придатність до вживання
4. Ефективність
5. Мінливість
6. Переносимість
Для того, щоб створити якісний програмний продукт автор говорить про необхідність виконання ряду дій:1. Тестування ПЗ
Тест «письмового столу» - відповідно з поставленим завданням необхідно вибрати вхідні дані і раціональний хід рішення.
Тест «чорного ящика» - функціональний тест, який розглядає алгоритм у якості чорного ящика, в який не можна заглянути (проводить зазвичай покупець).
Тест «білого ящика» - він передбачає, щоб вхідні дані були підібрані так, щоб алгоритм виконався хоча б один раз.
2. Перевірка справжності ПЗ - це комплекс заходів, спрямованих на бездоганне функціонування програми при будь-яких вхідних даних, що показується за допомогою математичного апарату.
3. Тестове планування і тестова документація. Так як досить часто тестування проходить непродумано і позапланово, то необхідно складати план тестів і протоколювати хід тестування, щоб виключити появу інших помилок в програмі.
Таким чином, розробка ПЗ включає в себе наступні етапи:
1. Інтуїтивна розробка алгоритмів.
2. Формалізація алгоритму, математичний опис.
3. Зображення алгоритмів структограммой. Поділ на модулі та підпрограми.
4. Розробляють алгоритмів за допомогою мови програмування високого рівня.
5. Кодування.
2. Структура програми
Перш ніж приступати до програмування, автор обгрунтовує вибір як мови, що вивчається програмування - мови С.
Мова C був спочатку розроблений як розширення для операційної системи UNIX, але згодом перетворився на стандартний ЯП для різних платформ. Цьому сприяло:
§ багатство операторів,
§ відносна машинна незалежність,
§ можлива висока мобільність,
§ невеликий мовної обсяг (лише 32 ключових слова),
§ багато синтаксичних можливостей у комбінації зі спрощеними стилями.
2.1 Основні елементи програми на C
У цій главі автор знайомить нас з основними синтаксичними одиницями мови С:n Набір символів С-програми - це літери, цифри, знаки, а також деякі специфічні елементи (пробіл, попередження, повернення, табуляція)
n Роздільники - прогалини, табулятори, кінець рядка, переклад сторінки, коментарі служать для розділення основних елементів мови
n Директива компілятора # include - підключає до компілятора файли.
n Функції - з них складається вся програма. Для кожної програми головною є функція Main, яка починається з "{" і закінчується "}".
n Стандартні бібліотеки - стандартні функції надаються стандартними бібліотеками.
n Ключові слова мають визначене значення, яке не може змінюватися.
n Ідентифікатор и і імена - усі об'єкти C мають ідентифікатори, які складаються з послідовності букв, цифр або підкреслення.
n Escape-послідовності - за допомогою них записуються недруковані символи через "\".
2.2 Умовні оператори
Автор знайомить нас з першої нелінійної структурою. Структура If ... Else означає розгалуження з переходом вперед. Тут можливі два різних шляхи вирішення в залежності від умови. Існує два види цієї структури:§ односторонній вибір - виконує дію тільки на одному з шляхів розгалуження і з'єднує обидва шляху в один, тобто if (Умовний вираз) Інструкція;
§ двосторонній вибір - виконує дії на кожній колії розгалуження і також з'єднує обидва шляхи, тобто if (Умовний вираз) Інструкція1; else Інструкція2;
Далі автор розглядає ще один вид умовного оператора, що виражається знаком питання. Він має наступний вигляд:
Умовний вираз? Вираз1: Вираженіє2
Вираз з умовою не може стояти на самоті, як у попередньому розгалуження, а стоїть всередині вираження.
Третя умовна структура - багаторазовий вибір switch .. case. Автор показує, що в цій структурі є більше ніж 2 шляхи вибору, які також з'єднуються. Для кожної умови обов'язково існує своя інструкція. Для всіх решти випадків виконується якась дія. Структура switch .. case має такий вигляд:
switch (Вираз)
{
case W1: Посібник 1;
...;
case Wn: Посібник n;
default: Посібник (за умовчанням);
}
2.3 Циклічні оператори
У цьому параграфі професор пояснює, що структури повторення використовуються, якщо послідовність команд повинна повторюватися неодноразово для вирішення задачі. Програмування структури повторення веде до так званого "програмному циклу".У випадку зі структурою while умова стоїть на початку програмного циклу, тому цикл може не виконатися жодного разу. Загальний вигляд команди такий:
while (Умовні вирази) Інструкції;
Наступна циклічна структура - повторення for представляє найбільшу універсальну форму повторення. Команда має наступний вигляд:
for (Вираз 1; Вираз 2; Вираз 3) Команда;
де Вираз 1 - початкове значення виразу, Вираження 2 - умовний вираз, яке повинно виконатися для виконання команд, Вираження 3 - змінює лічильну величину для продовження повторення.
Потім автор розглядає структуру, зворотний структурі while. Послідовність команд запускається в будь-якому випадку, по меншій мірі, одного разу. Тому цю структуру називають також невідворотних повторенням.
Do
Інструкція;
while (Умовний вираз);
Таким чином, в цьому розділі автором були розібрані різні типи трьох структурних одиниць будь-якої мови програмування - лінійної, розгалужується і циклічно.
3. Функції
У цій главі автор розповідає про один з головних структурних елементів програми - функціях. У всіх високорівневих мовах програмування відбувається поділ програм на частини за допомогою підпрограм-функцій.
3.1 Поняття
Функції реалізують ідеологію структурного програмування і виконують всі необхідні завдання для вирішення загального завдання. Для самих важливих і часто використовуваних завдань є стандартні функції, занесені до програмні бібліотеки C. Для вирішення інших завдань необхідно написати власні функції. Всі C-програми складаються з набору невеликих функцій. Для визначення функції в мові C необхідно вказати тип та ім'я, а також список параметрів у круглих дужках.У мові C будь-яка функція визначається глобально, тобто не залежить від інших функцій. У загальному вигляді цю структуру можна представити так:
Тип ім'я функції (список параметрів)
{
Угоди
Інструкції
return (значення функції)
}
Для кожного з параметрів функції пропонується його тип. Ці формальні параметри мають власне ім'я, яке використовується в межах роботи функції і власний тип. Наприклад, функція:
int quad (int x)
{
return (x * x);
}
містить параметр з ім'ям x типу Integer (цілий).
При виконанні функції формальні параметри замінюються актуальними параметрами, у якості яких можуть виступати певні значення, константи або змінні величини. Наприклад: y = quad (25); При цьому тип актуального параметра повинен обов'язково відповідати типу формального параметра.
3.2 Готовність і термін служби імен
Особливо автор звертає увагу на імена змінних, констант, функцій в програмі. У програмі існують дві позиції на значення імен:1. Готовність (Доступність). Цим властивістю визначаються місця програми, у яких можна отримати доступ до тих чи інших об'єктів (змінним величинами чи функцій). Тут існує 4 основних програмних області - програма, модуль, функція, блок. Об'єкти, які визначаються в самій програмі або модулі є глобальними об'єктами, а якщо визначаються в межах блоку або функції, то є локальними об'єктами.
2. Термін служби (Життєвий цикл). Тут йдеться про тривалість упорядкування елементів пам'яті. Розрізняють повний час поширення (статична тривалість) та час виконання блоку, в якому визначався об'єкт.
Ці правила дають ряд переваг при написанні програм:
· Змінна отримує певне значення в межах функції.
· Локальні змінні не застосовуються для всієї програми, тому можна використовувати однакові імена змінних в різних функціях.
· Глобальні змінні визначаються один раз і використовуються всіма функціями програми.
· Якщо імена глобальних і локальних змінних співпадають, то в даній функції використовуються значення локальних змінних. Таким чином, необхідно уникати написання однакових імен змінних.
3.3 Рекурсія і ітерація
У цьому параграфі автор розповідає про дуже важливому методі вирішення завдань - рекурсивних алгоритмах. Алгоритм називається рекурсивним, якщо виклик функції відбувається в межах самої функції, тобто функція посилається сама на себе. При цьому основна думка полягає в тому, щоб зменшувати рекурсивним чином дану проблему до тих пір, поки не буде отриманий простий випадок. При цьому значно зменшується алгоритм вирішення задачі.Щоб досягти рекурсивно, локальні змінні величини і параметри повинні зберігатися не в статичній пам'яті, а в так званої динамічної пам'яті, яка реалізується програмно.
Також з великої кількості кроків складається ітераційний алгоритм. Він містить проміжні кроки, які утворюють основу для проміжних результатів наступного повторенні (ітерації). Ітерації використовуються в основному при обробці великих масивів даних. Розрізняють 2 основних види ітерацій:
§ Алгоритми з заздалегідь відомим кількістю кроків повторення.
§ Алгоритми з заздалегідь невідомою кількістю кроків повторення.
Програміст повинен завжди піклуватися про те, щоб всі процеси, які протікають в певній програмі, після кінцевого числа кроків завершувалися. На жаль, часто цього не відбувається і програма "зациклюється".
Тому, якщо написана якась умовна або циклічна структура, необхідно стежити, щоб після кінцевого числа проходжень умова не була більше виконано. Кінцівка повторення можна підсумувати наступним чином: число кроків залежить від змінних величин програми і воно більше 0, якщо умова виконується хоча б один раз, а значення лічильника визначається в залежності від дій.
3.4 Функції введення-виведення
У цьому параграфі автор розповідає про найбільш важливих стандартних функціях, які дозволяють вводити інформацію з клавіатури і виводити її на екран.Введення і виведення даних в C відбувається через файловий інтерфейс. При цьому з пристроями, як, наприклад, принтер або консоль звертаються як з файлами. У стандартній C-бібліотеці для декількох пристроїв існують стандартні файли:
· Stdin (стандартне введення даних, клавіатура)
· Stdout (стандартний висновок, монітор)
· Stderr (помилки виведення, монітор)
З функціями введення-виведення пов'язаний файл заголовка stdio.h стандартної бібліотеки заголовків. У ньому визначені для застосування функцій необхідні функціональні прототипи, такі як типи і константи (дії), які стоять у зв'язку з реалізацією та програмою функцій. Крім усього іншого визначається константа EOF, яка служить для внутрішньої ідентифікації кінця файлів.
Також існує спеціальна функція виведення інформації - printf, яка має вигляд:
int printf (контрольна рядок, аргумент1, аргумент2, ...). Функція printf копіює символи з формату стандартного висновку або до кінця рядка, або до символу%. Щоб визначити тип формату виводу, функція шукає наступні за% символи. Найбільш часто використовуваним є формат% d, який виводить цілі числа в десятковій системі числення.
Стандартної функцією введення даних в C є функція scanf, яка має наступний вигляд: scanf (контрольна рядок, аргумент1, аргумент2 ,...). Вона переводить відповідно до управляючої рядок "контрольний рядок" такого типу і формату. Вона задає формат і призначає конвертовані значення через певну адресу відповідним змінним величинам arg1, arg2 ....
4. Типи даних в C
4.1 Числа і числові системи
У цій частині автор розповідає про основи представлення чисел в комп'ютері.Значення числа Z = a n a n-1 ... a 0 a -1 ... a-m в позиційній системі числення за основою B має вигляд:
де 0 <= a <B.
Наприклад, у десятковій системі числення число 1972 виглядає так:
1972 = 1 * 103 + 9 * 102 + 7 * 101 + 2 * 100
Формою представлення чисел в комп'ютері є двійкова. Недоліком цієї системи є заплутана, монотонна послідовність цифр при зображенні довгих двійкових чисел. Тому в інформатиці також використовують часто вісімкову і шістнадцяткову системи числення. Саме про них розповідає автор у цій главі.
Досить часто виникає необхідність перетворення чисел з однієї системи в іншу, зокрема, в найбільш зрозумілу людині десяткову систему числення. Правило перетворення з будь-якої системи числення в десяткову виглядає так:
При перекладі числа з будь-якої системи в десяткову треба це число представити у вигляді суми ступенів підстави його системи числення.
Дробові числа можливо зображати в інформатиці двома способами:
§ Зображення з фіксованою крапкою (наприклад, 1.25). При цьому крапка завжди стоїть на своєму місці в потрібному розряді.
§ Зображення з плаваючою крапкою. При цьому зображенні число записується таким чином, що точка ковзає завжди до першої відмінною від нуля цифрі. Такий запис виглядає наступним чином:
Z = М * B E, де M = 0.xxxxxxx ...., 1 / B <= М <1
Так як основа нам відома, то число може представлятися мантиссой М і експонентою E (нормалізоване зображення). Наприклад:
Z = 42.5456 -> 0.425456 * 10 2 -> M = 425456, E = 2
4.2 Основні типи даних
У цьому розділі професор перераховує відповідні категорії мови C.До елементарним типам даних, що використовуються в C відносяться: char (символьний), int (цілий), float (речовий тип з одинарною точністю), double (речовий тип з подвійною точністю), void (порожній, використовується для функцій і покажчиків).
Автор виділяє наступні види констант, що використовуються в мові Сі:
· Цілочисельні константи, які мають тип signed int.
· Константи з плаваючою крапкою. Вони видаються в десятковому або експоненційному вигляді і мають тип double.
· Символьні константи вказуються в лапках''.
· Літерні константи мають тип String і розташовані в лапках "".
Потім Платі розглядає основні арифметичні оператори («-», «+», «*», «/», «%»), використовувані в мові C. Тут, на відміну від інших мов програмування, присвоювання значень записується прямо в операторах, тому арифметичні операції застосовуються у всіх структурах, де є оператори. У C також використовується також два спеціальних оператора:
o Інкремент (приріст на 1) - «+ +»
o декремент (негативне приріст на 1) - «-»
Вони можуть стояти перед або після операнда, що задає порядок виконання операцій.
Крім цього в C використовуються логічні оператори:
·! - Логічне заперечення
· & & - Логічне «і»
· | | - Логічне «або»
Професор окремо виділяє оператори порівняння, використовувані в мові:
· <- Менше
· <= - Менше одно
·> - Більше
·> = - Більше одно
· == - Одно (тотожно)
·! = - Не дорівнює
Спеціального логічного типу даних Boolean в C не існує, а вважається, що
Ø Неравное 0 - правда (значення 1)
Ø Так само 0 - брехня (значення 0)
Складові оператори використовуються для більш компактній запису виразів у С. Автор показує, що тут можливі такі записи:
Вираз1 op = Вираженіє2, яка еквівалентна запису -
Вираз1 = (Вираз1) op (Вираженіє2), де op - будь-який оператор.
Потім професор виділяє два основних види масивів:
§ Одномірні поля. Визначимо поле з 5 елементами - int n [5]; Тоді ці 5 змінних величин розташовуються в пам'яті послідовно:
| n [0] | n [1] | n [2] | n [3] | n [4] |
При цьому не відбувається перевірка на допустиму область пам'яті компілятором.
§ Багатовимірні поля. Для багатовимірних масивів змінні величини задаються дещо іншими типами індексів. Приклад визначення двовимірного масиву: float x [8] [30]; Тут перший елемент - x [0] [0], і відповідно останній x [7] [29].
Юрген Платі підходить до пояснення роботи з символами та рядками як з одновимірними полями, які мають кілька особливостей. Рядки можуть инициализироваться також у класі пам'яті auto і повинні бути замкнуті '\ 0'. Наприклад: char s [] = {'s', 't', 'r', 'i', 'n', 'g', '\ 0'};Масиви char можуть инициализироваться також константами String -
char s [] = "string";
У C не є ніяких спеціальних елементів мови для маніпуляції рядками символів. Ряд функцій існують в C-стандартній бібліотеці (копіювання, порівняння, довжина рядків).
На відміну від масивів, які працюють з об'єктами одного типу, записи задають структуру для опису різних типів під спільним ім'ям. Переваги цих структур полягає в об'єднанні комплексних даних. Наприклад, це персональні дані (П.І.Б., адреса, соціальний статус і т.д.) або студентські дані (П.І.Б., адреса, дисципліна, відмітка і т.д.).
Записи в мові C описуються за допомогою ключового слова struct:
struct ім'я структури {компонент (n)} мінлива структури (n);
Для доступу до елементу записи використовуються 2 власних оператора.
При цьому для прямого доступу необхідна точка як роздільник змінної структури та імені компонента, тобто мінлива структури. компонент
Структури можуть мати також елементи, які є signed (зі знаком) або unsigned (без знака) int, а деякі мають бітову довжину. Тому позначають ці елементи як поля біта. При визначенні структури число бітів таких змінних величин вказується визначено, згідно синтаксису:
typedef struct
{Unsigned b1: 1;
unsigned b2: 1;
int: 6;
int farbe: 4;
} Bitpack;
Таким чином, у цій главі автором розглянуті практично всі типи даних, використовуваних в С і мають широкі можливості застосування.
5. Файли
Наступною структурі, яка є основним носієм інформації в комп'ютері, автор присвятив окрему главу.Файли - це основна структура для постійного зберігання і введення-виведення даних. Файли складаються з різних компонентів певного типу даних. У кінець файлу можуть додаватися різні дані.
Разом з типом файлу визначаються і кілька стандартних операцій з файлами (Open - відкриття файлу, Close - закриття файлу, Read - читання з файлу даних, Write - запис даних у файл).
5.1 Типи доступу
У наступних параграфах автор визначає 2 основних типи доступу для файлів у Cі:
1) Послідовні файли використовувалися на зорі розвитку комп'ютерної техніки, оскільки запис на перфострічку або магнітну стрічку могла вестися тільки послідовно.
2) Файли з довільним доступом. З появою жорстких дисків, які дозволяють звертатися до будь-яких ділянок пам'яті в будь-який час, з'явилися файли з довільним доступом.
У послідовних файлах позиціонування компонентів здійснюється неявно і не підпорядковується впливу програми. У файлах з довільним доступом операції зчитування і запису доповнюються зазначенням індексу компонентів. При цьому індекс компонентів відлічується, як правило, від 1. Разом з тим файл з довільним доступом володіє схожістю з типом даних "масив". Доступ до різних периферійних пристроїв в C здійснюється за допомогою покажчиків. При цьому файл повинен відкриватися до початку доступу і закриватися після. Для виконання цих функцій використовується стандартний файл C-бібліотеки <stdio.h>.
Що стосується самого поширеного типу файлів - текстових, то в C вони являють собою файли, компоненти яких літери, тобто символи типу char. Всі тексти ми поділяємо на рядки, і тут постає проблема: як визначити кінець рядка, коли реалізація текстових файлів у всіх програмах різна?
У Сі використовується, так званий, буферний висновок. Це означає, що виводиться тільки тоді, якщо кінець рядка надсилається пристрою виводу, або виводиться зовсім, якщо програма завершує свої дії.
Тут використовують такі функції мови C:
· Int putc (int c, FILE * f) - записує символи в текстові файли.
· Int getc (FILE * f) - читає символи з файлу.
· Int puts (const char * s) - записує послідовність символів у файл.
· Char * gets (char * s) - читання послідовності з файлу.
При бінарному введення і виведення дані представлені в допустимій формі, а внутрішнє зображення з пам'яті перенесе (побайтово) дані у файл. Наприклад, для бінарної запису змінних величин long потрібно 4 байт пам'яті. Необхідна кількість пам'яті залежить від величини числа і відповідно від його формату.
Функція fwrite записує вказану кількість елементів даних рівної величини у файл. Тут повинні передаватися:
· Адреса першого елемента даних.
· Величина окремого елемента даних.
· Кількість записуваних елементів даних
· Вихідний файл
Потім автор розповідає, як отримати доступ до окремих наборів даних файлу з довільним доступом. Для цього в C використовуються наступні команди: int fseek (FILE * f, long offset, int origin)
Ця функція ставить покажчик на певну позицію в межах файлу. Функція позиціонує зміщення (offset), яке вважається в байтах. Значення origin встановлюється відповідно зі зміщенням (SEEK_SET oder 0 - зміщення з початку файлу, SEEK_END oder 1 - зміщення з поточної позиції, SEEK_CUR oder 2 - зміщення з кінця файлу)
Функція long ftell (FILE * f) вказує поточну позицію у файлі, на якій знаходиться покажчик файлу. У випадку помилки ftell приймає значення -1.
Функція void rewind (FILE * f) переміщає покажчик на початок файлу і видаляє значення помилки.
Таким чином, Юрген Платі на відміну від інших авторів книг з програмування досить докладно описує процес роботи з файлами, постачаючи кожну операцію докладними коментарями та прикладами на мові С.
6. Покажчик
У цій главі автор розповідає про один з найважливіших понять програмування в C - покажчиках.
6.1 Основи покажчика
Покажчики - це такі ж змінні величини, які потребують в елементах пам'яті. Покажчик - це змінна величина, яка містить адресу іншого об'єкта. Потім можна отримати доступ до цього об'єкта побічно за допомогою покажчика. У цих адресах пам'яті міститься або адреси інших змінних величин, або адреси функцій.Дороговкази в мові C необхідно застосовувати в наступних випадках:
· При передачі параметра
· При обробці масивів
· Для обробки тексту
· Для доступу до спеціальних осередків пам'яті
Позначаються покажчики наступним чином: int * pc;, тобто мінлива pc є покажчиком тип int.
При цьому використовують переважно два типи покажчиків:
1. Оператор адреси &, який застосовується до об'єкта, який доставляє адресу цього об'єкта. Наприклад, pc = & c.
2. Змістовний оператор *, який застосовує покажчик до об'єкту, що знаходиться в цьому осередку. Наприклад, c =* pc; * pc = 5;
Особливо важливим є те, що * і & мають більш високий пріоритет, ніж арифметичні оператори. При цьому якщо використовуються кілька операторів покажчика послідовно, то вираз обробляється справа наліво.
Аргументи покажчика володіють можливістю звертатися до об'єктів функції з іншої функції і змінювати їх.
Автор також показує, що з покажчиками можна проводити певні арифметичні операції і операції порівняння. Дозволені, звичайно, тільки такі операції, які ведуть до осмислених результатів. До вказівниками можуть цілочисельні значення додаватися й відніматися з них. До вказівниками можуть також застосовувати декремент.
Можна покажчики допомогою операторів>,> =, <, <=,! = І == порівнювати один з одним. Всілякі арифметичні і логічні операції, не описані вище, не дозволені з покажчиками.
6.2 Покажчик та масив
Як зазначає автор у наступних параграфах, між покажчиками і полями існує яскраво виражена зв'язок. Кожна операція, яка може застосовуватися до елементів масиву, може виражатися також і покажчиками. Програма, що містить покажчики виконується набагато швидше. Проте зрозуміти сенс використання покажчиків набагато важче.Присвоєння pa = * a [0] показує, що pa вказує на 0-ой елемент масиву a, тобто pa містить адресу a [0]. Замість цього можна записати наступне: pa = a;
До окремих елементів масиву можна звертатися 3 різними способами:
· A [i] - i-ий елемент масиву
· * (Pa + i) - покажчик pa + i * (довжина елементів масиву a)
· * (A + i) початок масиву + i * (довжина елементів a)
Таким чином, кожне значення індексу масиву може визначатися також як значення зсуву покажчика і навпаки. Вираз pa + i не означає, що до pa значення i додається, а i встановлює зсув об'єкту від pa.
Багатовимірні масиви можна задавати через покажчики наступним чином:
Matrix [1] [2] =* (Matrix [1] +2)
Matrix [1] [2 ]=*(*( Matrix +1) +2)
Matrix [1] [2 ]=*(* Matrix +1 * M +2)
Так звані структурні покажчики мають дещо інше позначення:
Покажчик на структурну змінну -> назва елемента
Наприклад, punkt.px відповідає (* punkt) -> px
Так як структура покажчиків і масивів дуже схожа, то далі автор пояснює як скласти масив покажчиків.
Масив покажчиків - це масив, що складається з елементів-покажчиків. Вектор покажчиків визначається наступним чином:
Тип вихідних даних * Ім'я вектора []
Цей запис необхідно відрізняти від покажчика на вектор:
(* Ім'я вектора) []
Компоненти вектора можуть бути також адресами масивів. При цьому такий масив покажчиків схожий на багатовимірний масив.
Наприклад, char * Z [3], де відбувається визначення масиву з 3 елементами, які є відповідно покажчиками типу char. При цьому Z є покажчиком на масив з 3 покажчиками char.
6.3 Покажчик на функцію
Крім покажчиків на типи даних в C можна визначати покажчики і на функцію, які можна використовувати потім як змінні величини. Це може стати в нагоді для передачі значення функції в іншу функцію. Покажчик на функцію в C записується таким чином:
Тип повернення (* Ім'я функції) (Аргументи функції)
Тут необхідно звернути особливу увагу на те, що ім'я функції коштує в дужках. Якщо ми запишемо без дужок * Ім'я функції (), то функція буде повертати значення покажчика.
Функціональні покажчики можна використовувати в наступних випадках:
· Як змінну-вказівник, яка на функцію вказує.
· Розподіляти значення функціональних покажчиків.
· Визначати масиви функціональних покажчиків.
· Передавати покажчик на функцію як параметр.
· Отримувати покажчик на функцію як повернене значення.
Таким чином, професор звертає також особливу увагу на широке використання покажчиків при програмуванні в С. Це, загалом-то, виправдано досить високим швидкодією програм з покажчиками, але може призвести до додаткових помилок програмування через труднощі сприйняття покажчиків.
7. Динамічні структури даних
Працювати з ними не завжди зручно, тому що в процесі виконання програми виникає необхідність збільшити розміри пам'яті, виділеної для цієї структури. Для боротьби з цим необхідно визначати такі об'єкти з максимальною величиною.
Найбільш прийнятним рішенням тут буде застосування динамічно розподіляє пам'яті, тобто визначати об'єкти під час дії, тобто динамічно. Це рішення дозволяє оперативно звільняти велику кількість пам'яті і уникати її переповнення або марного витрачання при статичному розподілі.
Динамічні об'єкти визначаються дещо по-іншому. До них звертаються не по імені, а тільки на їх адресу. Ця адресація виникає при розподілі пам'яті і призначається зазвичай за допомогою змінних-вказівників. Динамічний розподіл пам'яті відбувається за допомогою стандартних функцій мови програмування С:
· Void * malloc (size_t size) - займає певну зв'язну область пам'яті і поставляє з неї початковий адресу.
· Void * calloc (size_t nobj, size_t size) - повертає початковий адресу великій області; зміст цієї області ініціалізується значенням 0.
· Void * realloc (void * ptr, size_t size) - зміна величини розміщення блоку пам'яті.
· Void free (void *) - використовується для звільнення області пам'яті, яка більше не використовується.
· Size_t sizeof (something) - визначає довжину аргументу.
При використанні покажчиків, які служать в якості значень, що повертаються функцією, потрібно стежити, щоб вони не вказували на локальні об'єкти, які зникають після роботи функції.
Відношення окремих вузлів шикуються наступним чином: покажчик одного вузла вказує на місце пам'яті «сусіда». Найважливішими з цих структур даних є:
· Лінійні списки - прості ланцюгові списки, подвійні ланцюгові списки, спеціальні форми, буфер (FIFO), стек (LIFO).
· Дерева - Бінарні дерева - 2 сусіда, многодорожние дерева - більше ніж 2 сусіда.
· Загальні графи
Лінійні списки використовують елементи, в яких вказані пов'язані відомості у формі рядки символів. Елементи списків можна уявити наочно наступним чином:
При побудові ланцюжка списку окремі елементи списку шикуються в певному порядку один за одним:
де символ електричної маси наприкінці списку вказує на NULL-покажчик, який показує кінець списку, а root - покажчик, який показує походження списку (як правило, глобальна змінна)
Ще одна важлива динамічна структура, про яку розповідає автор у цій главі - деревоподібна. Деревоподібні структури відіграють дуже важливу роль в організації даних. Їх використовують в наступних випадках:
Таким чином, динамічні структури даних, як показує автор, є найбільш ефективним способом розподілу оперативної пам'яті і відповідно необхідно їх використовувати в програмі, застосовуючи покажчики.
8. Вибрані алгоритми
У цій главі Юрген Платі розглядає найбільш поширені і типові види алгоритмів, реалізовані на Сі.
Поряд з простими операторами є ряд комплексних команд для строкових символів. Прототипи знаходяться в стандартній бібліотеці <STRING.H>.
· Strcat (char * a, char * b) - Послідовність символів b додається до a.
· Strncat (char * a, char * b, int n) - додаються до а n символів b.
· Strcpy (char * a, char * b) - рядок b копіюється після a
· Strncpy (char * a, char * b, int n) - n символів рядка b копіюється після a
· Int n = strlen (char * a) - повертає довжину рядка
В першу чергу автор розповідає про юліанському датоісчісленіі. При цьому не було б ніякої проблеми 2000 року. Замість цього дата зберігалася в комп'ютерах як рядок символів (TTMMJJ) і це призвело до того, щоб після 99 йшов рік 00. Причина такого датоісчісленія була пов'язана з необхідністю економії пам'яті.
Алгоритм розрахунку дати за Юліанським стилем можна представити наступним чином:
Y = рік, М = місяць, D = день
Якщо M> 2, то Y і М залишаються незмінними. Якщо М = 1 або М = 2, то
Y = Y - 1
М = М + 13
Для знаходження поточної дати маємо:
JD = INT (365 .25 * (Y + 4 716)) + INT (3 0.6001 * (М + 1)) + D + B - 1524.5
Досить часто в алгоритмах необхідно визначити чи є число простим. Щоб це устанавіть, потрібно ділити число X на числами, які більше 2 і менше X. Якщо число ні на яке з них не ділиться, воно повинно бути простим.
Потім автор розповідає про знаходження нулів функцій. Для цього застосовують методи апроксимації. Якщо заданий інтервал (a; b), на якому визначена функція, то необхідно кожного разу ділити інтервал навпіл і перевіряти де знаходиться нуль. Повторюється дію до тих пір, поки інтервал не стане досить малий.
Ще один типовий приклад розглянуто в цьому параграфі автором - рішення систем лінійних рівнянь методом Гауса.
Нехай задана система рівнянь виду Ax = b. Вважається, що якщо k-е рівняння буде вирішено, то:
При вирішенні методом Гаусса вихідні рівняння перетворять таким чином, що матриця коефіцієнтів містить нулі нижче головних діагоналей. Для цього використовуються операції додавання і віднімання рівнянь, а також множення їх на число. При цьому система приймає вигляд:
Методом математичної статистики аналізують масові явища. При цьому виявляються певні закономірності, які не можна формулювати для одиничних явищ. Кращим поданням статистичних даних є графічне зображення. В якості прикладу зображено розподіл частоти гаусового нормального розподілу.
Поряд з функцією частоти основну сукупність даних можна охарактеризувати за допомогою середнього значення і дисперсії. Арифметичне середнє значення визначається так:
а дисперсія наступним чином:
При роботі з вимірювальними величинами часто необхідно встановити зв'язок між окремими точками. Тут допомагають такі операції як інтерполяція і регресія.
При лінійної інтерполяції виконують апроксимацію функціональних значень f (x) на проміжку (x 1, x 2) з відомих значень f (x 1) і f (x 2).
Пошук і сортування
У цьому параграфі автор розповідає про найбільш поширені в програмуванні операцій з даними - пошуку і сортування.
Сортування значно полегшує роботи з даними в програмуванні. Наслідком таких операцій є більш ефективний пошук в програмі.
Розрізняють декілька основних методів пошуку, що залежать від типу даних:
1. Табличний пошук здійснюється за індексом даних в таблиці.
2. Лінійний пошук припускає перегляд всіх елементів по порядку до знаходження потрібного.
3. Бінарний пошук здійснюється після проведення сортування, суть якого полягає у перевірці середнього елемента послідовності та визначення за ключем у який бік рухатися для знаходження потрібного елемента.
Сортування є однією з найважливіших операцій з даними. Професор наводить таке визначення сортування:
Сортування - процес упорядкування заданої множини об'єктів у певному порядку. Виділяють такі види алгоритмів сортування:
§ Бульбашкова сортування. У першому проході масив обробляється з кінця до початку і порівнюється з кожним кроком поточний компонент з наступним. Якщо нижній компонент менше ніж верхній, то вони міняються місцями. Це відбувається до тих пір, поки послідовність не буде зростаючою або спадання.
§ Сортування вибором. У цьому випадку беруть перший елемент послідовності і шукають найменший елемент, з яким його і міняють місцями. Потім починають з другого і його міняють на найменший у залишилася послідовності і т.д.
§ Сортування вставкою. При цьому передбачається, що частина послідовності вже відсортована. Елементи не сортованого частини по порядку переміщують у сортований до тих пір поки елемент не стане більше або рівним попереду йде елемента.
§ Сортування методом Шелла. Спочатку масив поділяється на кілька груп, між членами яких є рівну відстань. Нехай, наприклад, використовується відстань 3, тоді компоненти 1, 4, 7 належать одній групі, так само як і 2, 5, 8 ..., 3, 6, 9 ... і т.д. ці групи упорядковуються окремо, потім відстань зменшується і дії повторюється до відстані 1.
§ Швидке сортування. Вибирають будь-який компонент масиву - наприклад, середній - і масив ділиться на 2 групи: одна з компонентами, які більше ніж обраний, а інша з меншими. Ці обидві групи діляться знов по заданому алгоритму. Таким чином, виходить рекурсивна функція, яка досить швидко сортує дані.
Однак безлічі можливо уявити за допомогою бітових масивів. Елементи масиву нумеруються, і кожен елемент множини являє собою 1 біт. Якщо відповідний біт встановлено (1), то елемент міститься в множині, якщо біт дорівнює 0, відповідний елемент не міститься в множині. Перетин і об'єднання можна використовувати за допомогою логічних операторів UND і ODER. Так як змінні величини типу int або char тільки відносно маленькі безлічі можуть представляти, то отримати до них доступ можна за допомогою покажчика на бітовий масив.
8.2 Екскурс: процеси та сигнали
У цьому параграфі професор дещо йде від програмування і намагається пояснити, як виконуються програми в операційній системі на прикладі ОС Linux.
Linux - це багатозадачна операційна система, яка може виконувати кілька завдань одночасно. При цьому кожна з цих програм веде себе таким чином, як якщо б вона була єдиною, яка завантажується в даний момент на комп'ютері.
Якщо під Linux запускається програма, вона отримує однозначний ідентифікаційний номер ID, який лежить в діапазоні між 1 і 32 767. За допомогою цього номера ОС може ідентифікувати знаходяться в пам'яті програми та отримати доступ до них. Для роботи з ID використовуються дві функції, які визначені у файлі заголовка unistd.h:
У таблиці автор наводить список найчастіше подаються Unix сигналів.
§ Використовуйте * define для символьних констант.
§ Використовуйте виключно прописні букви для констант і змішану форму запису або символ підкреслення для змінних та імен функцій.
§ Використовуйте функції, щоб Ваші програми були короткими, ясними і дотримувався принцип модульності. Кожен крок необхідно коментувати.
§ Мова C передбачає тільки мінімальну перевірку помилок в програмі. Це значно прискорює роботу програми і допускає деякі вільності в програмуванні. Але, тим не менш, програмісту необхідно перевіряти деякі значення в програмі за допомогою різних структур.
§ При написанні виразів, особливо умов, використовуйте дужки, щоб вказати послідовність і пріоритет оцінки.
§ Вирівнюйте команди таким чином, що легко визначалася структура програми, що складається з окремих блоків.
§ Використовуйте масиви з покажчиками з рядків символів замість двовимірних масивів, якщо рядки символів мають різну довжину.
§ По можливості використовуйте динамічні структури даних
9.2 Пастки в C
У висновку професор застерігає нас від найбільш часто зустрічаються помилок програмування в C:
Мова C теж був вибраний автором не випадково. Платі поставив метою цієї книги навчити мистецтву програмування і вказати на помилки у складанні програм. Мова C як не можна краще підходить для цих цілей, так як його використовують професійні програмісти всього світу і він досить демократичний в плані написання різних структур. Правда, у зв'язку з цим постійно виникають деякі труднощі в написанні коду, які необхідно вчасно усунути. Автор допомагає в цьому досить докладно розібратися.
Першу главу автор починає з поняття інформації як основної структури науки інформатика, без якої неможливо складання алгоритмів. Також розглядаються загальні питання пристрої комп'ютера, основних механізмів його функціонування для розуміння сутності яка протікає програмних процесів на машинному рівні. Далі професор досить докладно і зрозуміло вводить поняття алгоритму: розповідає, як і де використовуються алгоритми, дає визначення, докладно описує властивості.
На наступному етапі автор підходить до поняття мови та системи програмування, дається досить докладний огляд мов програмування і види систем програмування.
У другій частині цієї глави основну увагу приділив Платі формами представлення алгоритмів і запису основних алгоритмічних структур в них. Коротко розбираються графічні форми подання алгоритмів - блок-схеми і структограмми. Далі відразу автор намагається використовувати структури мови C, що досить складно для початківців і незрозуміло до пояснень синтаксису мови. Тому, в першу чергу, необхідно використовувати проміжні мови (наприклад, алгоритмічна мова).
У другій частині роботи розглядається процес програмування на мові програмування С. Для цього спочатку вводиться синтаксис основних команд С. Потім пояснюється їх призначення та особливості роботи. Завершується цей процес досить численними і різноманітними прикладами програм.
Варто звернути увагу на те, що автор періодично відволікається від процесу програмування і розглядає загальні інформатичні питання якимось чином пов'язані з темою (системи числення, процеси в операційній системі). Це дає можливість стверджувати, що дана праця є не тільки навчальним посібником з програмування, але і з інформатики в цілому.
Безсумнівно, ця книга становить великий інтерес як для початківців, так і для досвідчених програмістів, а також для людей займаються інформатичних проблемами. Багато поради та рекомендації щодо організації процесу створення ПЗ, дані автором, я буду використовувати в своєму дисертаційному дослідженні.
Тип повернення (* Ім'я функції) (Аргументи функції)
Тут необхідно звернути особливу увагу на те, що ім'я функції коштує в дужках. Якщо ми запишемо без дужок * Ім'я функції (), то функція буде повертати значення покажчика.
Функціональні покажчики можна використовувати в наступних випадках:
· Як змінну-вказівник, яка на функцію вказує.
· Розподіляти значення функціональних покажчиків.
· Визначати масиви функціональних покажчиків.
· Передавати покажчик на функцію як параметр.
· Отримувати покажчик на функцію як повернене значення.
Таким чином, професор звертає також особливу увагу на широке використання покажчиків при програмуванні в С. Це, загалом-то, виправдано досить високим швидкодією програм з покажчиками, але може призвести до додаткових помилок програмування через труднощі сприйняття покажчиків.
7. Динамічні структури даних
У цій главі автор розглядає зовсім інший спосіб зберігання даних у пам'яті.
7.1 Динамічне управління пам'яттю
До цих пір мова йшла тільки про об'єкти даних, для яких компілятор C надає пам'ять і її кількість і величина повинні бути визначені до початку перекладу програми в машинні коди. Такі об'єкти називають статичними.Працювати з ними не завжди зручно, тому що в процесі виконання програми виникає необхідність збільшити розміри пам'яті, виділеної для цієї структури. Для боротьби з цим необхідно визначати такі об'єкти з максимальною величиною.
Найбільш прийнятним рішенням тут буде застосування динамічно розподіляє пам'яті, тобто визначати об'єкти під час дії, тобто динамічно. Це рішення дозволяє оперативно звільняти велику кількість пам'яті і уникати її переповнення або марного витрачання при статичному розподілі.
Динамічні об'єкти визначаються дещо по-іншому. До них звертаються не по імені, а тільки на їх адресу. Ця адресація виникає при розподілі пам'яті і призначається зазвичай за допомогою змінних-вказівників. Динамічний розподіл пам'яті відбувається за допомогою стандартних функцій мови програмування С:
· Void * malloc (size_t size) - займає певну зв'язну область пам'яті і поставляє з неї початковий адресу.
· Void * calloc (size_t nobj, size_t size) - повертає початковий адресу великій області; зміст цієї області ініціалізується значенням 0.
· Void * realloc (void * ptr, size_t size) - зміна величини розміщення блоку пам'яті.
· Void free (void *) - використовується для звільнення області пам'яті, яка більше не використовується.
· Size_t sizeof (something) - визначає довжину аргументу.
При використанні покажчиків, які служать в якості значень, що повертаються функцією, потрібно стежити, щоб вони не вказували на локальні об'єкти, які зникають після роботи функції.
7.2 Динамічні структури даних
Динамічні структури даних, як пояснює Юрген Платі в наступних параграфах, змінюють свою структуру і зайняте ними простір пам'яті під час виконання програми. Вони формуються з окремих елементів, так званих 'вузлів', між якими існують певні взаємозв'язки. Мова в основному при цьому йде про структури, які позначаються як 'списки' або 'дерева'.Відношення окремих вузлів шикуються наступним чином: покажчик одного вузла вказує на місце пам'яті «сусіда». Найважливішими з цих структур даних є:
· Лінійні списки - прості ланцюгові списки, подвійні ланцюгові списки, спеціальні форми, буфер (FIFO), стек (LIFO).
· Дерева - Бінарні дерева - 2 сусіда, многодорожние дерева - більше ніж 2 сусіда.
· Загальні графи
Лінійні списки використовують елементи, в яких вказані пов'язані відомості у формі рядки символів. Елементи списків можна уявити наочно наступним чином:
| Інформація елементів списку (рядки символів, наприклад, ім'я) | Покажчик на наступний елемент |
де символ електричної маси наприкінці списку вказує на NULL-покажчик, який показує кінець списку, а root - покажчик, який показує походження списку (як правило, глобальна змінна)
Ще одна важлива динамічна структура, про яку розповідає автор у цій главі - деревоподібна. Деревоподібні структури відіграють дуже важливу роль в організації даних. Їх використовують в наступних випадках:
· При побудові родовідного дерева;
· При розподілі тексту по главам, розділам, абзаців і т.д.
Дерево визначається наступним чином: · Деревоподібні структури мають розгалуження, які можуть виходити з початкового елемента структури і з самих розгалужень до тих пір, поки кінцевих точок не досягнутий.
· Елементи дерева називають вузлами, причому початковий елемент називається кореневим вузлом, а кінцеві точки - листами.
· Лінії з'єднання двох вузлів називається ребрами. Послідовність ребер від кореня до будь-якого вузла називається шляхом.
· Вузли, які однаково віддалені від кореня утворюють рівень дерева. Загальне число рівнів вказує глибину дерева.
· Максимальна кількість спадкоємців, які має вузол, визначають ступінь дерева. Дерево ступеня 2 - це бінарне дерево, найбільш важливий випадок.
Деревоподібна структура має рекурсивну природу, оскільки спадкоємці вузла відповідно можуть розумітися як коріння дерев. Бінарне дерево можна зобразити наступним чином: Таким чином, динамічні структури даних, як показує автор, є найбільш ефективним способом розподілу оперативної пам'яті і відповідно необхідно їх використовувати в програмі, застосовуючи покажчики.
8. Вибрані алгоритми
У цій главі Юрген Платі розглядає найбільш поширені і типові види алгоритмів, реалізовані на Сі.
· Обробка рядків символів (Strings)
До простих операторам рядків, які задаються за допомогою <ctype.h>, автор відносить наступні оператори:| islower (c) | Мала літера |
| isupper (c) | Прописна буква |
| isalpha (c) | Рядкова або велика літера |
| isdigit (c) | Десяткове число |
| isalnum (c) | Рядкова або прописна буква або десяткове число |
· Strcat (char * a, char * b) - Послідовність символів b додається до a.
· Strncat (char * a, char * b, int n) - додаються до а n символів b.
· Strcpy (char * a, char * b) - рядок b копіюється після a
· Strncpy (char * a, char * b, int n) - n символів рядка b копіюється після a
· Int n = strlen (char * a) - повертає довжину рядка
· Арифметика дат
У цьому параграфі автором зібрані досить прості алгоритми, пов'язані з використанням дати і часу.В першу чергу автор розповідає про юліанському датоісчісленіі. При цьому не було б ніякої проблеми 2000 року. Замість цього дата зберігалася в комп'ютерах як рядок символів (TTMMJJ) і це призвело до того, щоб після 99 йшов рік 00. Причина такого датоісчісленія була пов'язана з необхідністю економії пам'яті.
Алгоритм розрахунку дати за Юліанським стилем можна представити наступним чином:
Y = рік, М = місяць, D = день
Якщо M> 2, то Y і М залишаються незмінними. Якщо М = 1 або М = 2, то
Y = Y - 1
М = М + 13
Для знаходження поточної дати маємо:
JD = INT (365 .25 * (Y + 4 716)) + INT (3 0.6001 * (М + 1)) + D + B - 1524.5
· Числовий тип
Тут професор наводить деякі алгоритми, які працюють з числовими даними.Досить часто в алгоритмах необхідно визначити чи є число простим. Щоб це устанавіть, потрібно ділити число X на числами, які більше 2 і менше X. Якщо число ні на яке з них не ділиться, воно повинно бути простим.
Потім автор розповідає про знаходження нулів функцій. Для цього застосовують методи апроксимації. Якщо заданий інтервал (a; b), на якому визначена функція, то необхідно кожного разу ділити інтервал навпіл і перевіряти де знаходиться нуль. Повторюється дію до тих пір, поки інтервал не стане досить малий.
Ще один типовий приклад розглянуто в цьому параграфі автором - рішення систем лінійних рівнянь методом Гауса.
Нехай задана система рівнянь виду Ax = b. Вважається, що якщо k-е рівняння буде вирішено, то:
При вирішенні методом Гаусса вихідні рівняння перетворять таким чином, що матриця коефіцієнтів містить нулі нижче головних діагоналей. Для цього використовуються операції додавання і віднімання рівнянь, а також множення їх на число. При цьому система приймає вигляд:
· Статистична міра
У цьому параграфі автор зачіпає статистичний метод обробки інформації та побудова програм на основі цього методу. Статистика обробляє емпіричні числа і на підставі цієї обробки робляться прогнози і приймаються рішення.Методом математичної статистики аналізують масові явища. При цьому виявляються певні закономірності, які не можна формулювати для одиничних явищ. Кращим поданням статистичних даних є графічне зображення. В якості прикладу зображено розподіл частоти гаусового нормального розподілу.
Поряд з функцією частоти основну сукупність даних можна охарактеризувати за допомогою середнього значення і дисперсії. Арифметичне середнє значення визначається так:
а дисперсія наступним чином:
При роботі з вимірювальними величинами часто необхідно встановити зв'язок між окремими точками. Тут допомагають такі операції як інтерполяція і регресія.
При лінійної інтерполяції виконують апроксимацію функціональних значень f (x) на проміжку (x 1, x 2) з відомих значень f (x 1) і f (x 2).
Пошук і сортування
У цьому параграфі автор розповідає про найбільш поширені в програмуванні операцій з даними - пошуку і сортування.
Сортування значно полегшує роботи з даними в програмуванні. Наслідком таких операцій є більш ефективний пошук в програмі.
Розрізняють декілька основних методів пошуку, що залежать від типу даних:
1. Табличний пошук здійснюється за індексом даних в таблиці.
2. Лінійний пошук припускає перегляд всіх елементів по порядку до знаходження потрібного.
3. Бінарний пошук здійснюється після проведення сортування, суть якого полягає у перевірці середнього елемента послідовності та визначення за ключем у який бік рухатися для знаходження потрібного елемента.
Сортування є однією з найважливіших операцій з даними. Професор наводить таке визначення сортування:
Сортування - процес упорядкування заданої множини об'єктів у певному порядку. Виділяють такі види алгоритмів сортування:
§ Бульбашкова сортування. У першому проході масив обробляється з кінця до початку і порівнюється з кожним кроком поточний компонент з наступним. Якщо нижній компонент менше ніж верхній, то вони міняються місцями. Це відбувається до тих пір, поки послідовність не буде зростаючою або спадання.
§ Сортування вибором. У цьому випадку беруть перший елемент послідовності і шукають найменший елемент, з яким його і міняють місцями. Потім починають з другого і його міняють на найменший у залишилася послідовності і т.д.
§ Сортування вставкою. При цьому передбачається, що частина послідовності вже відсортована. Елементи не сортованого частини по порядку переміщують у сортований до тих пір поки елемент не стане більше або рівним попереду йде елемента.
§ Сортування методом Шелла. Спочатку масив поділяється на кілька груп, між членами яких є рівну відстань. Нехай, наприклад, використовується відстань 3, тоді компоненти 1, 4, 7 належать одній групі, так само як і 2, 5, 8 ..., 3, 6, 9 ... і т.д. ці групи упорядковуються окремо, потім відстань зменшується і дії повторюється до відстані 1.
§ Швидке сортування. Вибирають будь-який компонент масиву - наприклад, середній - і масив ділиться на 2 групи: одна з компонентами, які більше ніж обраний, а інша з меншими. Ці обидві групи діляться знов по заданому алгоритму. Таким чином, виходить рекурсивна функція, яка досить швидко сортує дані.
· Реалізація множин
Автор у цій главі згадує про множини - досить важливій структурі програмування. Інші мови програмування (наприклад, Паскаль) мають тип даних множини. У мові C такого немає.Однак безлічі можливо уявити за допомогою бітових масивів. Елементи масиву нумеруються, і кожен елемент множини являє собою 1 біт. Якщо відповідний біт встановлено (1), то елемент міститься в множині, якщо біт дорівнює 0, відповідний елемент не міститься в множині. Перетин і об'єднання можна використовувати за допомогою логічних операторів UND і ODER. Так як змінні величини типу int або char тільки відносно маленькі безлічі можуть представляти, то отримати до них доступ можна за допомогою покажчика на бітовий масив.
8.2 Екскурс: процеси та сигнали
У цьому параграфі професор дещо йде від програмування і намагається пояснити, як виконуються програми в операційній системі на прикладі ОС Linux.
Linux - це багатозадачна операційна система, яка може виконувати кілька завдань одночасно. При цьому кожна з цих програм веде себе таким чином, як якщо б вона була єдиною, яка завантажується в даний момент на комп'ютері.
Якщо під Linux запускається програма, вона отримує однозначний ідентифікаційний номер ID, який лежить в діапазоні між 1 і 32 767. За допомогою цього номера ОС може ідентифікувати знаходяться в пам'яті програми та отримати доступ до них. Для роботи з ID використовуються дві функції, які визначені у файлі заголовка unistd.h:
1. pid_t getpid (void) - повертає PID
2. pid_t getppid (void) - повертає батьків PID-процесу.
Наступний важливий елемент для операційних систем - сигнали, які надають можливість запускати нові процеси або замінювати процес іншим процесом. Сигнали - це повідомлення, які надсилаються операційною системою в поточну програму для будь-яких дій. Деякі сигнали викликаються в результаті помилки в програмі, інші викликаються на вимогу користувача. У таблиці автор наводить список найчастіше подаються Unix сигналів.
| Ім'я | Значення | Функція |
| SIGHUP | 1 | Вихід із системи |
| SIGINT | 2 | Переривання користувача (клавіші Ctrl + C) |
| SIGQUIT | 3 | Запит користувача на закінчення (клавіша CTRL + \) |
| SIGFPE | 8 | Помилка з плаваючою комою |
| SIGKILL | 9 | Примусове завершення процесу |
9. Стиль програмування. Пастки
9.1 Стиль програмування в C
Існує таке поняття в програмуванні як стиль програмування. Для різних мов програмування він різний. Автор намагається дати рекомендації для програмування в C. З численних рад автора можна виділити наступні, найзагальніші:§ Використовуйте * define для символьних констант.
§ Використовуйте виключно прописні букви для констант і змішану форму запису або символ підкреслення для змінних та імен функцій.
§ Використовуйте функції, щоб Ваші програми були короткими, ясними і дотримувався принцип модульності. Кожен крок необхідно коментувати.
§ Мова C передбачає тільки мінімальну перевірку помилок в програмі. Це значно прискорює роботу програми і допускає деякі вільності в програмуванні. Але, тим не менш, програмісту необхідно перевіряти деякі значення в програмі за допомогою різних структур.
§ При написанні виразів, особливо умов, використовуйте дужки, щоб вказати послідовність і пріоритет оцінки.
§ Вирівнюйте команди таким чином, що легко визначалася структура програми, що складається з окремих блоків.
§ Використовуйте масиви з покажчиками з рядків символів замість двовимірних масивів, якщо рядки символів мають різну довжину.
§ По можливості використовуйте динамічні структури даних
9.2 Пастки в C
У висновку професор застерігає нас від найбільш часто зустрічаються помилок програмування в C:
§ Щоб уникнути помилок memory fault (нестача пам'яті) необхідно в програмі перевіряти кордону одержуваних строкових величин.
§ Одна з частих помилок - постановка точки з комою в кінці команди. Компілятор C помічає це тільки в наступному рядку і вказує потім на цю помилку.
§ При написанні умовної структури часто не ясно, до якого IF належить ELSE. Наприклад,
if (i> j)
if (k <100)
tuwas ();
else
tuwasanderes ();
При цьому виходить, що ELSE належить першому IF. Насправді вона належить завжди найближчого IF.
§ Якщо оголошується змінна double d = 3 / 4, то в результаті виходить 0, тому що 3 і 4 - цілі числа. Для того, щоб отримати результат необхідно записати 3.0 та 4.0
§ NULL визначається лише # define NULL. Покажчики не можуть бути ніякими цілими значеннями. Покажчик повинен бути инициализирован допустимим адресою пам'яті.
Висновок
Тема, висвітлена автором в цій книзі, є однією з найактуальніших тем курсу інформатики. Алгоритмізація, розглянута в першому розділі книги, є основою побудови науки «інформатика», а програмування, викладене в наступних розділах, є основним способом реалізації алгоритмічних структур за допомогою машинних кодів.Мова C теж був вибраний автором не випадково. Платі поставив метою цієї книги навчити мистецтву програмування і вказати на помилки у складанні програм. Мова C як не можна краще підходить для цих цілей, так як його використовують професійні програмісти всього світу і він досить демократичний в плані написання різних структур. Правда, у зв'язку з цим постійно виникають деякі труднощі в написанні коду, які необхідно вчасно усунути. Автор допомагає в цьому досить докладно розібратися.
Першу главу автор починає з поняття інформації як основної структури науки інформатика, без якої неможливо складання алгоритмів. Також розглядаються загальні питання пристрої комп'ютера, основних механізмів його функціонування для розуміння сутності яка протікає програмних процесів на машинному рівні. Далі професор досить докладно і зрозуміло вводить поняття алгоритму: розповідає, як і де використовуються алгоритми, дає визначення, докладно описує властивості.
На наступному етапі автор підходить до поняття мови та системи програмування, дається досить докладний огляд мов програмування і види систем програмування.
У другій частині цієї глави основну увагу приділив Платі формами представлення алгоритмів і запису основних алгоритмічних структур в них. Коротко розбираються графічні форми подання алгоритмів - блок-схеми і структограмми. Далі відразу автор намагається використовувати структури мови C, що досить складно для початківців і незрозуміло до пояснень синтаксису мови. Тому, в першу чергу, необхідно використовувати проміжні мови (наприклад, алгоритмічна мова).
У другій частині роботи розглядається процес програмування на мові програмування С. Для цього спочатку вводиться синтаксис основних команд С. Потім пояснюється їх призначення та особливості роботи. Завершується цей процес досить численними і різноманітними прикладами програм.
Варто звернути увагу на те, що автор періодично відволікається від процесу програмування і розглядає загальні інформатичні питання якимось чином пов'язані з темою (системи числення, процеси в операційній системі). Це дає можливість стверджувати, що дана праця є не тільки навчальним посібником з програмування, але і з інформатики в цілому.
Безсумнівно, ця книга становить великий інтерес як для початківців, так і для досвідчених програмістів, а також для людей займаються інформатичних проблемами. Багато поради та рекомендації щодо організації процесу створення ПЗ, дані автором, я буду використовувати в своєму дисертаційному дослідженні.