Робота з динамічними структурами даних. Списки
Практикум
із курсу «Системне програмування»
Вступ
В наш час персональні комп'ютери знайшли широке застосування в різних галузях народного господарства. Комп'ютери даного класу працюють під управлінням операційної системи (ОС) MS Windows. Дана система надає користувачу можливості по управлінню файловою системою, організації введення-виведення, управлінню пам’яттю, запуску файлів на виконання [1].
Користувач може скористатися можливостями операційної системи за допомогою системних викликів з програм на мові високого рівня. Об'єктні коди процедур, що підтримують роботу з операційною системою, зібрані в бібліотеки. Такі бібліотеки є у складі багатьох систем програмування: Borland C++, Visual C++ та ін.
В даному посібнику описана техніка системного програмування в MS Windows при роботі в середовищі Visual C++ 6.0 (консольний режим) В якості тем для вивчення вибрані наступні типові задачі системного програмування, що виникають не лише при роботі в Windows, а також при використанні інших операційних систем, наприклад, UNIX:
- програмування динамічних структур даних;
- запуск файлів, що виконуються, з програми;
- організація прямого доступу в потоках, зв'язаних з файлами на диску;
- перевизначення дескрипторів файлів і вказівників на потоки;
- проектування файлів з прямим доступом;
- розробка програм-обробників сигналів.
Наведені тексти лабораторних робіт містять повний опис функцій, що використовуються, з системних бібліотек. Наводяться приклади.
Методика викладання иатеріалу базується на трьох основних підходах:
· розбір теоретичних основ з описом деяких найбільш уживаних функцій;
· освоєння нового матеріалу з розбором конкретних кодів;
· виконання завдань до лабораторних робіт, що передбачають розробку, відладку та тестування програм.
Така методика дозволяє краще засвоїти техніку програмування на мові Сі.
Лабораторна робота №1.
Запуск файлів, що виконуються, з програми.
Мета роботи. Вивчити можливості використання функцій spawnl - spawnvpe мови Сі для запуску файлів, що виконуються, з програми.
Теоретична частина.
Термін "процес" визначається як програма, яка виконується під управлінням операційної системи. Процес складається з кодів програми і даних плюс інформація, що належить статусу процесу, така як число відкритих файлів. Якщо Ви починаєте виконання програми в середовищі операційної системи, то тим самим Ви запускаєте обчислювальний процес. В різних ОС присутні директиви, що дозволяють з програми користувача виконувати команди по породженню, завершенню, припиненню, відновленню і синхронізації процесів.
В системі програмування Visual C++ є набір функцій, виклики яких приводять до звертання програми, що виконується, до директив ОС по управлінню процесами. Всі ці функції (виключаючи signal()) оголошені в заголовочному файлі process.h і дозволяють виконати із викликаючої програми наступні дії:
1. Ідентифікувати процес унікальним числом (getpid).
2. Завершити процес (abort,exit,_exit).
3. Управляти сигналами (signal).
4. Почати новий процес (різновиди exec- і spawn-функцій, system-функція).
В даній роботі вивчаються наступні функції по управлінню процесами:
spawnl - виконати породжуваний процес із списком аргументів.
spawnle - виконати породжуваний процес із списком аргументів і заданим оточенням.
spawnlp - виконати породжуваний процес, використовуючи змінну оточення PATH і список аргументів
spawnlpe - виконати породжуваний процес, використовуючи змінну оточення PATH, задане оточення і список аргументів.
spawnv - виконати породжуваний процес з масивом аргументів
spawnve - виконати породжуваний процес з масивом аргументів і заданим оточенням.
spawnvp - виконати породжуваний процес, використовуючи змінну PATH і масив аргументів.
spawnvpe - виконати породжуваний процес, використовуючи PATH змінну, задане оточення і масив аргументів.
Перш ніж почати опис spawn-функцій, нагадаємо про аргументи функції main( ) і концепції оточення.
Прототип функції main має вигляд:
main(int argc, char *argv[],char *envp[]).
Параметр argc визначає загальне число аргументів,що передаються функції main() через командний рядок. Параметр argv оголошується як масив покажчиків на передані функції main аргументи. Параметр envp оголошується як масиввказівників на рядки, що визначають операційне середовище (оточення), в якому виконується програма.
Аргумент argv[0] завжди містить повне ім'я файлу, що виконується, тому значення argc на одиницю перевищує кількість аргументів, що передаються. Аргументи командного рядка можуть задавати, наприклад, режими роботи, імена файлів та інші дані для програми і відділяються один від одного пробільними символами. Якщо пробільний символ повинен бути представлений в аргументі, аргумент має бути поміщений у лапки. Якщо, наприклад, командний рядок виклику Сі-програми має вигляд:
А:\>cprog Working З program
і виконуваний файл cprog знаходиться в кореневому каталозі диска А, то аргументи argc і argv мають вигляд:
argс=4
argv[0]="a:\cprog.exe"
argv[1]="Working"
argv[2]="C"
argv[3]="program"
argv[4]=""=NULL='\0'.
Операційне середовище програми (оточення) складається з масиву рядків, що називають змінними оточення. Рядки звичайно мають форму:
" NAME = value "
де NAME - ім'я змінної оточення, а value є текстове значенням цієї змінної. Зауважемо, що value не береться в подвійні лапки. Останнім елементом в оточенні повинен бути NULL. Найбільш часто використовуються такі змінні оточення:
PROMPT - вид запрошення ОС
PATH - список каталогів, в яких OС шукає файли, що виконуються
COMSPEC - повне ім'я командного процесора, що використовується.
Приклад найпростішого оточення:
envp[0]="PROMPT=$g$s"
envp[1]="path=a:\;c:\"
envp[2]="comspec=c:\command.com"
envp[3]=""=NULL'\0'.
Spawn-функції завантажують виконуваний файл і починають новий процес, що назвають породжуваним процесом. Директиви типу spawn здатні (на відміну від exec-функцій) повертати управління з породжуваного процесу до його «батька». При spawn-виклику і «батько», і породжуваний процес можуть одночасно розміщатися в пам'яті, отже, повинно бути достатньо пам'яті для завантаження і виконання породжених процесів. Наведемо опис spawn-функцій.
#include <stdio.h>
int spawnl(modeflag,pathname,arg0,arg1...,argn,NULL);
int spawnle(modeflag,pathname,arg0,arg1...,argn, NULL,envp);
int spawnlp(modeflag,pathname,arg0,arg1...,argn,NULL);
int spawnlpe(modeflag,pathname,arg0,arg1...,argn, NULL,envp);
int spawnv(modeflag,pathname,argv);
int spawnve(modeflag,pathname,argv,envp);
int spawnvp(modeflag,pathname,argv);
int spawnvpe(modeflag,pathname,argv,envp);
int modeflag;
char *pathname;
char *arg0,*arg1...,*argn;
char *argv[];
char *envp[];
Аргумент modeflag визначає режим взаємодії породжуючого і породженого процесів. У файлі process.h для modeflagбули визначені такі значення:
P_WAIT - призупинити породжуючий процес, доки виконання процесу, що породжується. не завершиться;
P_OVERLAY - вилучити з пам'яті процес, що породжує.
Аргумент pathname визначає файл, який буде виконуватись як процес, шо породжується. Pathnameможе визначити повний шлях (з кореня), частковий шлях (з поточного каталога) або просто ім'я файлу. Якщо pathname не має розширення і не закінчується крапкою, то функція додає розширення "COM" і шукає файл. Якщо пошук пройшов безуспішно, то додається розширення "EXE" і робиться нова спроба. Якщо pathnameмістить розширення, то використовується тільки це розширення. Якщо pathname закінчується крапкою, то пошук ведеться для pathname без розширення. Spawnlp, spawnlpe, spawnvp і spawnvpe команди ведуть пошук для імені файлу в каталогах, що визначені у змінній оточення PATH, що встановлена для породжуючого процесу.
Процесу, що породжується, аргументи передаються у вигляді одного або більше рядків (покажчиків на char). Сумарна довжина рядків, що формують набір аргументів, не повинна перевищувати 128 байт. Нульовий символ ('\\0') для кожного рядка не враховується але символи пропусків, що розділяють аргументи, приймаються до уваги.
Для функцій spawnl, spawnle, spawnlp, spawnlpe рядки можуть бути передані як окремі аргументи arg0, arg1... argn, тобто списком, а для функцій spawnv, spawnve, spawnvp spawnvpe як масив покажчиків argv.
Мінімум один аргумент, arg0або argv[0], повинен бути переданий процесу, що породжується. За угодою, цей аргумент є копією імені файлу pathname.
Виклик spawnl, spawnle, spawnlp, spawnlpe звичайно використовується, коли число аргументів відоме наперед. Наступним за аргументом argn повинен бути покажчик NULL, що означає кінець списку аргументів.
Виклик spawnv, spawnvp, spawnve, spawnvpe звичайно використовується, коли число аргументів змінне. Покажчики на аргументи передаються як масив argv. Аргумент argv[0] звичайно є ім'ям файлу pathname, а аргументи від argv[1] до argv[n] – це покажчики на рядки, що формують новий список аргументів. Аргумент argv[n+1] повинен бути NULL тобто, покажчик, що означає кінець списку аргументів.
При виклику spawnl, spawnlp, spawnv, spawnvp породжуваний процес успадковуватиме і оточення «батька». Виклик spawnle spawnlpe, spawnve або spawnvpe дозволяє користувачу змінити операційне середовище для породжуваного процесу, передавши йому через аргумент envp нові значення для змінних оточення. Аргумент envp є масивом покажчиків на символ, кожний елемент якого є рядком, що визначає змінну оточення. Останнім елементом в envp повинен бути покажчик NULL. Коли envp містить тільки NULL, породжуваний процес успадковуватиме оточення від «батька».
В таблиці 1.1 наведені способи формування набору фактичних параметрів для різних spawn-функцій. Ім'я функції задається в першій колонці. Друге поле визначає: чи використовується змінна оточення операційної системи PATH для пошуку виконуваного файлу, який визначає породжуваний процес. Третє поле описує метод передачі аргументів породжуваному процесу. Останнє поле визначає: чи успадковуватиме оточення породжуваний процес від батька або воно буде змінено.
Таблиця 1.1
| Функція | Використання змінної PATH | Спосіб передачі аргументів | Оточення |
| spawnl | Не використовує PATH | Список аргументів | Наслідує від батька |
| spawnle | Не використовує PATH | Список аргументів | Масив оточення |
| spawnlp | Використовує PATH | Список аргументів | Наслідує від батька |
| spawnlpe | Використовує PATH | Список аргументів | Масив оточення |
| spawnv | Не використовує PATH | Масив аргументів | Наслідує від батька |
| spawnve | Не використовує PATH | Масив аргументів | Масив оточення |
| spawnvp | Використовує PATH | Масив аргументів | Наслідує від батька |
| spawnvpe | Використовує PATH | Масив аргументів | Масив оточення |
Spawn-функції повертають статус завершення породжуваного процесу. Статус завершення рівний 0, якщо процес завершиться нормально. Породжуваний процес може спеціально встановити свій статус завершення шляхом виклику функції exit з бажаним аргументом. У протилежному випадку позитивний статус завершення процесу відображає про його ненормальне завершення. Якщо при виклику spawn-функцій вони повертають -1, то це сповіщає про помилку запуску породжуваного процесу і глобальна змінна errno встановлюється в одне з наступних значень:
E2BIG - список аргументів або область оточення перевищує допустимий розмір;
EINVAL - недійсний аргумент modeflag;
ENOENT - файл або ім'я шляху не знайдений;
ENOEXEC - спроба запустити на виконання файл;
ENOMEM - для виконання породжуваного процесу недостатньо пам'яті.
Відзначимо, що файли, які були відкриті коли викликалася spawn-функція, залишаються відкритими і в породжуючому процесі, проте в загальному випадку не зберігають свої атрибути. Тому в породженому процесі, для правильної установки атрибутів, рекомендується використовувати функцію setmode().Слід також пам'ятати, що сигнал, виданий в процесі-батькові, не сприймається в породженому процесі.
Практична частина
1. Вивчити теоретичну частину. Вміти відповідати на контрольні запитання.
2. Скласти програму prog для друку командного рядка і значень змінних оточення. Командний рядок передається програмі в пункті Settings меню Project, вкладка Debug, поле Program Arguments. Отримати виконуваний файл prog.exe.
3. Скласти програму, яка повинна, використовуючи всі можливі варіанти функції spawn (8 варіантів), запускати на виконання файл prog.exe (8 разів). Для породжуваного процесу в програмі необхідно визначити аргументи, що передаються, і, якщо можливо, то нові значення змінних оточення. Рекомендується для операційного середовища встановити лише нове значення параметра PATH. Кожному варіанту функцій spawnl-spawnvpe можна присвоїти порядковий номер від 1 до 8 та, набираючи на клавіатурі відповідну цифру, передавати управління потрібній функції spawn. Програма повинна видавати на дисплей ім'я викликаної spawn-функції і повідомлення про її нормальне завершення.
Контрольні питання
1. Що таке обчислювальний процес?
2. Які операції можна проводити над процесами в системі програмування Visual C++?
3. Які формальні параметри має функція main?
4. Як в програмі отримати доступ до командного рядка?
5. Що таке оточення програми та які Ви знаєте змінні оточення?
6. Які spawn-функції використовують змінну оточення PATH для пошуку файлів, що виконуються?
7. Як після завершення породженого процесу забезпечити повернення в породжуючий?
8. Яка інформація повинна бути повторена двічі при spawn-виклику?
9. Чим завершується список або масив аргументів і масив оточення?
10. При яких spawn-викликах породжуваний процес успадковує оточення батька?
Лабораторна робота №2.
Робота з динамічними структурами даних. Списки.
Мета роботи. Вивчити принципи програмування динамічних структур даних.
Теоретична частина.
При створенні системного програмного забезпечення широко застосовуються різноманітні структури даних. Важливе місце серед них займають списки. Список - це неіндексована послідовність однотипних елементів інформації. На відміну від множин для списків важливий порядок елементів. Номери елементів великого значення не мають. Як приклад можна навести списки цілих чисел, дійсних чисел, рядків, даних про працівників установи. В системному програмуванні використовують списки вільних областей оперативної пам'яті, списки активних процесів, списки заблокованих процесів, списки запитів на введення-виведення, списки незайнятих областей диска, списки фізичних блоків, що входять у файл, списки процесів, що очікують закінчення введення-виведення або іншого обслуговуваня тощо. Списки застосовуються для зберігання масивів змінної довжини.
Розглянемо основні поняття, що використовуються при програмуванні списків. Як приклад візьмемо списки цілих чисел.
Хай дан список < 0 1 2 0 3 1 2 > . Його перший елемент називається головою списку, а список з елементів, що залишилися, - це хвіст списку. В нашому випадку голова - це число 0, а список < 1 2 0 3 1 2 > є хвостом.
Список допускає ряд операцій над своїм вмістом.
1. Створити список з одного елемента. Так для числа 6 маємо список < 6 >.
2. Перевірка входження заданого елемента в список Наприклад, число 2 не входить в список < 6 7 3 7 1 >.
3. Визначення голови списку. В нашому випадку це число 6.
4. Додавання елемента в голову списка. Наприклад, після додавання числа 2 в голову списка, маємо новий список < 2 6 7 3 7 1 >.
5. Додавання елемента в хвіст списка. Наприклад, після додавання числа 2 в хвіст списку, маємо < 2 6 7 3 7 1 2 >.
6. Вилучення елемента з голови списка. Наприклад, після вилучення наш список буде мати вигляд < 6 7 3 7 1 2 > .
7. Вилучення елемента з хвоста списка. Після цієї операції для нашого списку маємо < 6 7 3 7 1 >.
8. Вилучення першого елемента списку, що має задане значення. Якщо провести цю дію для числа 7, то отримаємо < 6 3 7 1>.
9. Виведення (друк) елементів списку.
10. Злиття двох списків в один, наприклад, для списків < 1 2 3 4 > і < 9 8 7 5 >
маємо список < 1 2 3 4 9 8 7 5 >.
11. Створення копії списку.
Якщо список допускає операції 4 і 6, або 5 і 7, то він називається стеком. Черга - це список з операціями 5 і 6. Структура, що підтримує операції 4, 5, 6 і 7, називається деком.
Кожний елемент списку повинен містити змістовну частину і інформацію про його розташування щодо інших елементів. Елементи прийнято представляти у вигляді структур з використанням вказівників. Так, якщо є список прізвищ робітників установи з вказівкою їх віку, то структура для зберігання його елементів має вигляд:
struct list {struct name_age data;
struct list *next;};
де data - змістовна частина, що зберігається як структура
struct name_age {char *name; /* Прізвище*/
int age;}; /*Вік*/
а next - вказівник на наступний елемент списку.
Список повністю ідентифікується вказівником на свою голову. В нашому випадку список - це дане типу вказівника на структуру struct list*;
Ознакою кінця списку є нульовий покажчик в полі елемента, що відповідає за зв'язок з іншими елементами списку. Для конкретного прикладу ознакою кінця списку є нульове значення поля next.
Для списку цілих чисел конструкція спрощується і прийме вид структури
struct list{int val; /* Значення елемента списка*/
struct list *next;};.
Для зручності програмування визначимо новий тип даних
typedef struct list{int val;
struct list *next;} LIST;
Тоді елементи списку цілих чисел є даними типу LIST, а сам список має тип LIST*. Визначимо ознаку кінця списку як
#define END (LIST*)0.
Для роботи з цілочисельним списком запропонуємо наступний програмний інтерфейс, що реалізовує операції 1-11.
LIST* crtlst(int); /*Створити*/
int exist(LIST* h,int i); /*Входження i в h*/
int head(LIST* h); /*Значення голови h*/
void uptoh(LIST** ph, int i);/*Додати i в голову (*ph)*/
void uptot(LIST* h,int i); /* Додати i в хвіст h*/
int delfromh(LIST** ph); /*Вилучити з голови (*ph)*/
int delfromt(LIST** ph); /*Вилучити з хвоста (*ph)*/
int del(LIST** ph, int i); /*Вилучити i з (*ph)*/
void print(LIST* h); /*Надрукувати h*/
LIST* concat(LIST* f,LIST* s);/*Об’єднати списки f і s в один*/
LIST *dbl(LIST* s); /*Дублювати список*/
Зверніть увагу на подвійний покажчик LIST**. Він присутній в прототипах тих функцій, які змінюють значення покажчика на список, тобто на його голову.
Реалізація функції head тривіальна і не відображає техніки програмування із списками і динамічними структурами
int head(LIST* h);
{return h->val;}
Списки дають найбільший ефект, якщо вони були запрограмовані з використанням динамічного виділення і звільнення пам’яті. Пам'ять під елемент виділяється при його приєднанні до списку і звільняється при видаленні. Стандартна бібліотека Сі для динамічного розподілу даних надає функції malloc і free.
Функція
void* malloc(unsigned size)
повертає покажчик на ділянку пам'яті завдовжки в size байт. При неможливості виділити ділянку пам'яті заданої довжини функція повертає нульовий покажчик NULL. Для звільнення пам'яті, що була виділена за допомогою malloc, використовується функція
void free(void *p)
де р - адреса початку ділянки пам'яті, що звільняється.
Наприклад, для виділення пам'яті під елемент цілочисельного списку слід написати
LIST *j;
j=(LIST*)malloc(sizeof(LIST));
Звільнити її можна командою free(j).
Для освоєння техніки програмування списків наведемо реалізації деяких функцій програмного інтерфейсу.
LIST* crtlst(int l) /*Створити*/
{LIST* h=(LIST*)malloc(sizeof(LIST));
h->val=l; h->next=END;
return h;}
Функція створює одноелементний список і ініціалізує вміст елемента цілим числом l. Ознакою кінця списку є нульове (END) значення поля next.
#define END (LIST*)0
void uptoh(LIST** h, int v) /*Додати v в голову (*h)*/
{LIST *oldh=*h;
*h=(LIST*)malloc(sizeof(LIST));
(*h)->val=v;
(*h)->next=oldh; }
Зверніть увагу, що після додавання елемента змінюється покажчик на початок списку (*h).
int delfromt(LIST** h) /*Вилучити з хвоста (*h)*/
{ LIST *i,*j;
int v;
if((*h)->next==END)
{v=(*h)->val; free(*h); (*h)=END;return v;}
for(j=(*h),i=j->next;i->next;j=i,i=j->next);
v= i->val;free(i);
j->next=END;
return v;}
Якщо список складається з одного елемента, то він знищується. Перегляд списку проводиться по парах для того, щоб правильно встановити кінець списку після вилучення останнього елемента.
void print(LIST* h) /*Надрукувати*/
{LIST *i;
printf("\n Список ");
if(h==END) printf(" порожній");
for(i=h;i;i=i->next)
printf(" %d ",i->val); }
Функція виводить в стандартний вихідний потік значення елементів списку. Зверніть увагу на цикл, що організує перебір всіх елементів списку.
LIST*concat(LIST* f, LIST* s) /*Об’єднати списки f і s в один*/
{LIST* i;
for(i=f;i->next;i=i->next);
i->next=s; return f;}
Функція додає список s в кінець списку f. Результуючий список займає місце в пам'яті, де раніше розташовувалися списки f і s. Функція повертає покажчик на новий список.
LIST *dbl(LIST* s) /*Дублювати список*/
{LIST *p,*t,*i;
t=(LIST*)malloc(sizeof(LIST));
for(p=s,i=t;p->next;p=p->next)
{i->val=p->val;
i=i->next=(LIST*)malloc(sizeof(LIST));
}
i->next=END;
i->val=p->val;
return t;}
Функція здійснює поелементне копіювання списку s в список t. Пам'ять для чергового елемента копії виділяється за допомогою функції malloc. Новий список завершується нульовим вказівником END.
Практична частина.
1. Вивчити теоретичну частину. Уміти відповідати на контрольні запитання.
2. Введіть в комп’ютер наведені вище функції для роботи зі списками crtlst, delfromt, uptoh і print.
3. Запрограмуйте функції програмного інтерфейсу, що реалізовують операції з цілочисельними списками і не розглянуті вище в теоретичній частині:
а) Функція перевірки входження елемента в список
int exist(LIST* h, int i); /*Входження i в h*/ .
Організувати цикл для перебору елементів, як це зроблено при реалізації функції print. Функція повертає 1 при успішному завершенні і 0 за відсутності в списку елемента із заданим значенням.
б) Функція додавання цілого числа i в хвіст списку
void uptot(LIST* h,int i); /*Додати i в хвіст h*/
Для реалізації цієї функції необхідно досягти останнього елемента списку, зарезервувати пам'ять для нового елементу, помістити в нього ціле число і, перевизначивши поля next включити новий елемент в кінець списку. Пам'ятайте, що останній елемент списку повинен мати в полі next значення 0 (END).
г) Функція для вилучення елемента з голови списку.
int delfromh(LIST** ph); /*Видалити з голови (*ph)*/ .
На відміну від попередніх функцій тут не потрібно циклічних конструкцій. Треба просто переустановити покажчик на початок списку (*h) на наступний елемент і звільнити пам'ять з-під попереднього елемента.
д) Функція для видалення із списку першого елемента зі значенням i
int del(LIST** ph, int i); /*Удалить i з (*ph)*/
Якщо перший елемент має потрібне значення, то застосуйте функцію delfromh, у протилежному випадку проглядайте список по парах, як це зроблено у функції delfromt. Знайшовши потрібний елемент, видаляйте його, переустановивши відповідним чином поля next. Не забувайте звільняти пам'ять. Функція повертає 1 при успішному завершенні і -1 за відсутності даного числа i.
3. Головна програма для тестування розроблених функцій має вигляд:
#include <stdio.h>
typedef struct list{int val;
struct list *next;} LIST;
#define END (LIST*)0
LIST* crtlst(int);
int delfromh(LIST**);
void uptot(LIST*,int);
void uptoh(LIST**,int);
int delfromt(LIST**);
int del(LIST**,int);
int exist(LIST*,int);
void print(LIST*);
main( )
{int i; LIST* h;
printf(" \nЗначення першого цілого для списку? ");
scanf("%d",&i));
h=crtlst(i);
print(h);
while(1)
{printf(" \nЦіле число? ");
scanf("%d",&i)) ;
if(h==(LIST*)0){printf("\n Список порожній\n");exit(1);}
print(h);
if (exist(h,i ))
{printf(" \nЧисло %d існує в списку \n",i);
printf(" \nВилучити перше входження %d зі списку(у/n)?",i);
if(getche()=='y')
{del(&h,i);
if(h==END){printf("\n Список порожній\n");exit(1);}
print(h); }
}
printf(" \nДодати %d в хвіст списка (у/n)? ",i);
if(getche()=='y') {uptot(h,i);print(h);}
printf(" \nДодати %d в голову списка (у/n)h? ",i);
if(getche()=='y') {uptoh(&h,i); print(h);}
printf(" \nВидалити елемент з голови списка (у/n)?");
if(getche()=='y')
if(h==END){printf("\n Список порожній\n");exit(1);}
else
{printf(" \n З голови списку вилучено %d\n"
delfromh(&h));
print(h); }
printf(" \nВилучити елемент з хвоста списка (у/n)?");
if(getche()=='y')
if(h==END) {printf("\n Список порожній\n");exit(1);}
else
{printf(" \n З хвоста списку вилучено %d\n"
delfromt(&h));
print(h);
}}}
Контрольні питання
1. Що таке список та чим він відрізняється від масиву? Наведіть приклади.
2. Яку роль грають списки в системному програмуванні?
3. Перерахуйте 11 операцій над списками. Відповіді проілюструйте прикладами з цілочисельними списками.
4. З яких частин складається елемент списку? Як в елементі списку можна зберігати інформацію про його зв'язки з наступним елементом?
5. Чому тип деяких аргументів у функціях роботи зі списками мають тип подвійного покажчика LIST**?
6. Як організувати перебір елементів списку? Наведіть приклад.
7. За допомогою яких функцій здійснюється динамічне виділення і звільнення пам'яті при додаванні і вилученні елементів списку? Наведіть приклади.
8. Що є ознакою кінця списку при його програмуванні на Сі?
9. Чому у функції delfromt здійснюється перебір елементів списку по парах?
Лабораторна робота №3.
Прямий доступ в потоках.
Мета роботи. Вивчення організації прямого доступу в потоках, пов'язаних з файлами на диску.
Програми введення і виведення в стандартній бібліотеці мови Сі дозволяють обмінюватися інформацією з файлами та пристроями. Можливі наступні 3 типи функцій введення-виведення:
- введення-виведення потоком;
- введення-виведення на нижньому рівні;
- введення-виведення з консоллю та портом.
В операційній системі файли розглядаються як неіндексовані масиви символів (байт). Для роботи з файлами використовують функції введення-виведення нижнього (базового) рівня, трансльовані системою в команди до контроллерів зовнішніх пристроїв.
Функції по забезпеченню обміну інформації з потоками є надбудовою над базовою системою введення-виведення. Подібно базовому рівню функції введення-виведення потоком розглядають дані файлу як неіндексований масив, проте обмін інформацією відбувається не безпосередньо із зовнішнім пристроєм,а через буфер, що виділяється системою в адресному просторі процесу користувача.
При послідовному записі, вміст вихідного буфера записується на зовнішній носій тільки тоді, коли буфер заповнений, потік був закритий або програма нормально завершилася. При послідовному зчитуванні блок даних із зовнішнього пристрою переписується у вхідний буфер і дані читаються з буфера. Наступний блок даних передається в буфер лише тоді, коли вхідний буфер вичерпаний.
Операційна система надає велике число функцій для роботи з потоками. Ці функції оголошені у файлі stdio.h. Тут також визначені константи EOF ( кінець файлу) і NULL (вказівник на нуль ), а також шаблон структури FILE, що містить поля для занесення інформації про потік. Знайдіть і прогляньте цей файл.
До виконання операції введення і виведення з потоком, він повинен бути відкритий. При відкритті файл зв'язується із структурою типу FILE, в яку заноситься інформація про файл і відповідний поток. Відкриття потоку можна здійснити функцією fopen. Вона повертає покажчик на структуру FILE, який використовується для подальшого звернення до потоку. Функція має формат:
FILE *fopen(char *pathname,char *type) ,
де pathname - ім'я файлу, що відкривається, type - рядок символів, який визначає тип доступу до файлу:
"r" - відкрити для читання (файл повинен існувати);
"w" - відкрити порожній файл для запису, якщо файл існує, той його вміст втрачається;
"a" - відкрити для запису в кінець файлу (додавання); файл створюється, якщо він не існує;
"r+" - відкрити для читання і запису (файл повинен існувати);
"w+" - відкрити порожній файл для читання і запису, якщо файл існує його зміст втрачається;
"a+" - відкрити для читання і додавання; файл створюється, якщо він не існує.
Будьте обережні при використанні режимів "w" і "w+", бо вони можуть зіпсувати існуючі файли.
Тип доступу повинен бути сумісний з атрибутами файлу (наприклад, існують файли, що допускають тільки читання). Існує два модифікатори для визначення типу доступу до файлу:
"t" - відкрити в текстовому режимі ( при введенні послідовність символів повернення_каретки і нового_рядка (CRLF) переводиться в символ нового рядка (LF), а при виведенні символ LF переводиться у послідовність CR-LF; символ Ctrl-Z сприймається як кінець файлу);
"b" - відкрити в двійковому режимі ( визначені вище переведення ігноруються і Ctrl-Z не визначає кінець файлу).
Наприклад, послідовність "rb" відповідає відкриттю файлу для читання в двійковому режимі. За умовчанням використовується модифікатор "t".
При помилці функція fopen повертає константу NULL.
Існує ряд стандартних потоків, що відкриваються автоматично при початку роботи Сі програми. Це такі потоки як:
stdin - стандартне введення (як правило, клавіатура);
stdout – стандартне виведення(як правило, екран);
stderr - стандартний потік помилок (як правило, екран);
stdprn - стандартний друк (як правило, принтер).
Приклад відкриття файлу з іменем "abc.def" для читання:
#include <stdio.h>
main()
{
FILE *stream;
if ((stream = fopen("abc.def","r")) == NULL) {
printf (" неможливо відкрити файл abc.def\n" );
exit(1); /* Завершення програми з кодом 1*/}
}
Коли програма завершується, потоки автоматично закриваються. Проте, по завершенню операцій з потоком його рекомендуєтся закривати, оскільки число потоків, які можуть бути відкриті одночасно, обмежено. Для закриття потоків використовується функція
int fclose(FILE *stream) ,
де stream - потік, що закривається.
Функція повертає 0 при успішному закритті потоку та EOF – в разі помилки.
При закритті потоку вміст системного буфера, пов'язаного з потоком, виводиться у файл, а структура FILE звільняється.
Приклад
#include <stdio.h>
main()
{ FILE *stream;
stream = fopen("abc.def","r");
if(EOF==fclose(stream))
printf("Не можу закрити файл abc.def.\n");
}
Операції читання і запису в потоках починаються з поточної позиції в потоці, званої вказівником запису-читання потоку або просто вказівником. Вказівник змінюється після виконання кожної операції читання або запису. Наприклад, якщо ви читаєте один символ з потоку, вказівник збільшується на 1 байт, так що наступна операція почнеться з наступного символу. Якщо потік був відкритий для додавання, то перед кожною операцією запису вказівник автоматично позиціонується в кінець файлу. У всіх інших випадках після відкриття файлу вказівник встановлюється в нульову позицію. Потік, пов'язаний з пристроєм (таким як консоль або принтер), не має вказівника файлу.
Базовим засобом для обміну інформації з потоком є функції fgetс і fputс.
Функція int fgetc(FILE *stream) читає один символ з поточної позиції вхідного потоку stream, переміщує вказівник на наступний символ і повертає символ, що був введений. Якщо був знайдений кінець файлу або відбулася помилка читання, функція повертає EOF. Щоб розрізнити причини ненормального завершення функції слід використовувати функції feof або ferror.
Приклад
# include <stdio.h>
main()
{FILE *stream;
char buffer[81];
int i, ch;
/* Введення рядка з потоку stream */
for (i = 0; i < 80 && ( (ch = fgetc(stream)!= EOF) && (ch != '\n'); i++)
buffer[i]= ch;
buffer[i]= '\0'; }
Функція int fputc(int с, FILE *stream) записує символ з молодшого байта цілого с в поточну позицію вихідного потоку stream. Функція повертає записаний символ або EOF, якщо був знайдений кінець файлу або помилка запису. Причини ненормального завершення можна розрізнити, використовуючи функції feof або ferror.
Приклад.
#include <stdio.h>
main( )
{ FILE *stream;
char buffer[81];
int i, ch;
/* Наступні оператори виводять вміст масиву buffer в потік stream*/
for (i = 0; i < 81 && ((ch = fputc(buffer[i], stream))! = EOF); i++);
}
Використовуючи функцію fseek, програміст має можливість змінювати положення вказівника запису-читання потоку. Функція має наступний формат
int fseek (FILE *stream, long offset, int origin).
Функція переміщує вказівник файлу, пов'язаного з потоком stream, в нову позицію, рівну зсуву на offset байтів від точки відліку, що визначається аргументом origin. Параметр origin повинен бути однією з наступних констант, визначених в stdio.h:
SEEK_SET - початок файлу;
SEEK_CUR - поточна позиція вказівника файлу;
SEEK_END - кінець файлу.
Наступна операція з потоком виконується з нового місця розташування вказівника.
В потоці, відкритому для оновлення (режими a+, r+ і w+) наступною операцією може бути як читання, так і запис. Коли файл був відкритий з "a" або "a+" типом, дані записуються в кінець файлу. Хоча вказівник файлу може бути переміщений, використовуючи fseek або rewind функції, проте він завжди переміщатиметься назад на кінець файлу при записі даних. Таким чином, існуючі дані не можуть бути затерті.
Функція може бути використана, щоб перемістити вказівник в будь-яке місце файлу. Вказівник може бути переміщений за кінець файлу. Проте розмір файлу зміниться лише після запису. Спроба перемістити вказівник до початку файлу приведе до помилки. При успішному завершенні функція повертає значення 0.
Приклад.
#include <stdio.h>
main()
{FILE *stream; int result;
stream = fopen("data","r");
. . .
/* Наступне твердження повертає вказівник на початок файлу */
result = fseek(stream,0L,SEEK_SET);
}
Для визначення поточної позиції вказівника запису-читання потоку stream, використовується функція
long ftell(FILE *stream),
яка повертає позицію вказівника відносно початку файлу або -1L при помилці.
Приклад.
#include <stdio.h>
main()
{ FILE *stream;
long роsition;
stream = fopen("data","rb");
. . .
роsition = ftell(stream); }
Сі програма, як правило, продовжує виконуватися навіть за наявності помилок виконання бібліотечних функцій. При виклику кожної функції програміст повинен протестувати її код повернення і в разі ненормального завершення провести діагностику помилок. Істотну допомогу при цьому може надати функція
void реrror (char string),
яка виводить повідомлення про помилку в стандартний потік stderr.Спочатку видається аргумент string, за яким слідує двокрапка, системне помилкове повідомлення для останнього виклику бібліотеки, який дав помилку і символ нового рядка. Код помилки поміщається в системну змінну errno, яка повинна бути описана на зовнішньому рівні. Системні помилкові повідомлення розташовані в системному масиві рядків sys_errlist, впорядкованому по відповідних кодах помилок. функція рerror друкує відповідне помилкове повідомлення, використовуючи значення errno, як індекс для sys-errlist. Для правильної роботи реrror повинна бути викликана зразу ж після завершення роботи бібліотечної функції, яка повернула код помилки. В іншому випадку значення errno може бути затерте при подальших викликах.
Приклад.
, , ,
{ FILE *p;
if(NULL==(p=fopen("file.dat","r")))
реrror("Помилка відкриття файлу FILE.DAT"); }
Якщо файлу FILE.DAT не існує, то на екран буде видане повідомлення:
«Помилка відкриття файлу FILE.DAT: No such file or directory».
Якщо відбувається помилка в операції з потоком або був виявлений кінець файлу, асоційованого з даним потоком, то у відповідних полях структури FILE встановлюються ознаки помилки і кінця файлу. Для встановлення цих фактів використовуються макроси ferror і feof. Слід користуватись функцію void clearerr (FILE *stream), яка скидає ознаки помилки і кінця файлу для вказаного потоку stream.
Макрос ferror має формат
int ferror(FILE *stream)
і повертає ненульове значення, якщо при при обміні інформацією з потоком stream відбулася помилка.
Приклад.
#include <stdio.h>
main()
{int i;
i=fputc ('*', stdin);
if (ferror(stdin)) {
реrror("Помилка запису");
clearerr();}
}
Оскільки стандартний потік stdin був відкритий тільки для читання, то буде видано повідомлення: «Помилка запису: Error 0».
Для визначення чи був досягнутий кінець файлу, пов'язаного з потоком stream, слід використовувати макрос int feof(stream). При досягненні кінця файлу макрос повертає нуль. Індикатор кінця файлу залишається встановленим до тих пір, поки потік не буде закритий або не буде викликана функція clearerr. Функція fseek не може скинути індикатор.
Приклад.
#include <stdio.h>
main()
{char st[100];
FILE *stream;
/* Наступні інструкції здійснюють читання і обробку
вхідних рядків, доки не наступить кінець файлу */
while (! feof (stream))
{
(fscanf(stream,"%s",st))
/* О б р о б к а*/}
Макроси ferror і feof слід використовувати спільно з функцією clearerr.
Приклад.
#include <stdio.h>
#include <stdlib.h>
main( )
{FILE *stream;
int c;
/* Наступні інструкції виводять дані в потік і потім виконують перевірку: чи була помилка. Потік повинен бути заздалегідь відкритий для запису*/
if ((c=getc(stream)) == EOF) {
if (ferror(stream){
реrror("помилка запису\n");
clearerr(stream);}
}
Крім вищеозначених функцій в роботі слідує також використовувати функцію
int асcess(char *pathname, int mode),
яка встановлює: чи існує вказаний файл pathname і чи є до нього доступ в даному режимі mode. Можливі значення параметра mode і його суть наступні:
06 - перевірити на можливість читання і запису;
04 - перевірити на можливість читання;
02 перевірити на можливість запису;
00 - перевірити на існування файлу.
Функція повертає 0, якщо є доступ до файлу у вказаному режимі і -1, якщо немає доступу у вказаному режимі або файлу не існує. В іншому випадку номер помилки errno встановлюється в одне з наступних значень:
EACCES - немає доступу вказаним способом доступу;
ENOENT - файл або шлях до нього не знайдений..
Приклад.
#include<io.h>
main( )
{ FILE *fn;
/* перевірка на можливість запису */
if ((асcess("data",2))== -1) {
реrror("немає доступу для запису у файл");
exit(1); }
else
fn = fopen("data", "a");}
Практична частина.
1. Вивчити основні принципи і функції для роботи з потоками.
2. Напишіть функцію
FILE *rndfopen(char* path),
що відкриває файл path як потік для запису і читання в двійковому режимі. Введення і виведення може здійснюватися в будь-яку позицію потоку. Якщо файл існував, то його колишній вміст зберігається за винятком тих байт, в які був проведений запис (включаючи ті байти, які знаходяться за межами початкового файлу). Функція повинна також забезпечити створення нового файлу, який відкривається для запису і читання записаного. Функція повертає покажчик на структуру FILE, що описує відкритий потік, і NULL при помилці. Для написання функції слід використовувати функції fopen і асcess.
3. В цілях перевірки правильності роботи складеної функції rndfopen, завершіть складання тестової програми, начерк якої наведений нижче. Для цього вбудовані речення на українській мові замінить на потрібні оператори мови Сі.
Виклик кожної бібліотечної функції повинен супроводжуватись тестуванням на помилку. Наприклад, фразу "Перемістити покажчик в позицію l" замінюємо на оператори:
if(fseek(p,l, SEEK_SET))
реrror("\n Hе можу перемістити покажчик!");
/* Начерк тестової программы*/
#include <stdio.h>
FILE *rndfopen(char*); /* Прототип */
char s[10], n[15];
main()
{long l, ll; int с,ii;
FILE *p;
printf("\nІм’я файлу?");
gets(n); /* Введення з консолі імені файла*/
if(NULL==(p=rndfopen(n))) /* Виклик Вашої функції з тестом на помилку*/
{реrror("\n Помилка відкриття.");
exit(1);} /* Завершення програми з кодом повернення 1 */
while(1)
{ printf("\nПозиція ?");
gets(s); /* Введення з терміналу рядка - номера позиції */
l=atol(s); для введення-виведення і перетворення її
в довге ціле l*/
<Перемістити вказівник в позицію l.>
<Читання позиції вказівникф в змінну ll.>
<Читання символу з поточної позиції в змінну ii.>
printf("\n В позиції %ld записано %c (%d).",ll,ii,ii);
printf("\nЗаписуватимете (у/n) ?");
if(getche()=='y')
{printf("\n Символ?");
c=getche(); /* Читання символу з клавіатури. */
< Перемістити вказівник в позицію l. >
<Записати символ c в потік,>
printf("\nЩе (у/n) ?");
if(getche()=='n')break;
}
<Закрити потік.>
}
FILE *rndfopen(char *n)
{ <Тіло Вашої функції.> }
4. Після налагодження Ваша програма повинна підтримувати наступний приклад діалогу:
а) файл ra.dat не існує.
Ім'я файлу? ra.dat
Позиція ? 0
У позиції 0 записано (-1)
Записуватимете (у/n) ? n
Ще (у/n) ? у
Позиція ? 3
У позиції 3 записано (-1)
Записуватимете (у/n) ? у
Символ? 4
Ще (у/n) у
Позиція ? 3
У позиції 3 записано 4 (52)
Записуватимете (у/n) ? n
Ще (у/n) у
Позиція ? 0
У позиції 0 записаний ДОВІЛЬНИЙ_СИМВОЛ_0
Записуватимете (у/n) ? у
Символ? 1
Ще (у/n) у
Позиція ? 0
У позиції 0 записано 1 (49)
Записуватимете (у/n) ? n
Ще (у/n) n
Файл ra.dat складається з 4-х байт і має вигляд:
'1' ДОВІЛЬНИЙ_СИМВОЛ_1 ДОВІЛЬНИЙ_СИМВОЛ_2 '4'
б) Знову запустимо програму. Файл ra.dat. існує.
Ім'я файлу? ra.dat
Позиція ? 0
У позиції 0 записано 1 (49)
Записуватимете (у/n) ? n
Ще (у/n) ? у
Позиція ? 3
У позиції 3 записано 4 (52)
Записуватимете (у/n) ? у
Символ? 0
Ще (у/n) у
Позиція ? 5
У позиції 5 записано (-1)
Записуватимете (у/n) ? у
Символ? 6
Ще (у/n) у
Позиція ? 4
У позиції 4 записаний ДОВІЛЬНИЙ_СИМВОЛ_4
Записуватимете (у/n) ? n
Ще (у/n) у
Позиція ? 1
У позиції 1 записаний ДОВІЛЬНИЙ_СИМВОЛ_1
Записуватимете (у/n) ? у
Символ? 2
Ще (у/n) n
Тепер файл ram.dat складається з 6-ти байт і має вигляд:
'1' '2' ДОВІЛЬНИЙ_СИМВОЛ_2 '0' ДОВІЛЬНИЙ_СИМВОЛ_4 '6'.
Контрольні питання
1. Чим відрізняється обмін інформації з потоками від базової системи введення-виведення? Коли змінюється вміст буфера?
2. При яких режимах відкриття файлу його вміст зберігається?
5. Чи можна змінити старий вміст файлу, якщо він відкритий для додавання?
6. Чому при читанні текстового файлу передаються не всі його байти?
7. Що повертає функція fopen?
8. Навіщо закривати файли?
9. В які позиції встановлюється вказівник запису/читання при відкритті потоку в різних режимах?
10. Чи можливий запис інформації за межі файлу?
11. Чи можливе читання інформації за межами файлу?
12. Чому функції запису і читання символів fgetc і fputc повертають ціле?
13. Коли зміниться розмір файлу при переміщенні вказівника за його кінець?
15. Як поводиться Сі-програма за наявності помилок виклику функцій?
17. Якими засобами можна визначити ненормальне хід виконань операцій з потоками?
18. Які можливості надає функція асcess?
19. Поясніть чому у файлі ra.dat з'явилися довільні символи?
Лабораторна робота №4.