Массивы
Работа из раздела: «
Цифровые устройства»
B.I.Березін,С.Б.Березін(С.83) МАСИВИ І ПОКАЖЧИКИ
Раніше ми ввели типи даних в мові С, які називаються іноді базовими або
вбудованими. На основі цих типів даних мова С дозволяє будувати інші типи
даних і структури даних. Масив - один з найбільш простих і відомих структур
даних. Під масивом в мові С розуміють набір даних одного і того ж типу,
зібраних під одним ім'ям. Кожний елемент масиву визначається ім'ям масиву і
порядковим номером елемента, який називається індексом. Індекс в мові С
завжди ціле число.
ОГОЛОШЕННЯ МАСИВУ В ПРОГРАМІ
Основна форма оголошення масиву розмірності N така:
тип <ім'я масиву>[размер1][размер2]...[размерН]
Частіше за все використовуються одновимірні масиви:
тип <ім'я масиву> [розмір] ;
тип - базовий тип елементів масиву, розмір - кількість елементів
одновимірного масиву.
При описі двовимірного масиву оголошення має наступний вигляд:
тип <ім'я масиву> [размері][размер2];
У цьому описі можна трактувати оголошення двовимірного масиву як
оголошення масиву масивів, т. е. масив розміру [размер2], елементами якого
є одновимірні масиви <ім'я масиву>[размер1].
Розмір масиву в мові С може задаватися константою або константним
виразом. Не можна задати масив змінного розміру. Для цього існує окремий
механізм, званий динамічним виділенням пам'яті.
ОДНОВИМІРНІ МАСИВИ
У мові С індекс завжди починається з нуля. Коли ми говоримо про перший
елемент масиву, то маємо на увазі елемент з індексом 0. Еслі ми оголосили
масив
int a[100] ;
це означає, що масив містить 100 елементів від а[0] до а[99]. Для
одновимірного масиву легко підрахувати, скільки байт в пам'яті буде займати
цей масив:
кільк.байтів=<розмір базового типу>*<кільк.елементів>.
У мові С під масив завжди виділяється безперервне місце в оперативній
пам'яті.
У мові С не перевіряється вихід індексу за межі масиву. Якщо масив
а[100] описаний як цілочисельний масив, що має 100 елементів, а ви в
програмі вкажете а[200], то повідомлення про помилку не буде видане, а як
значення елемента а[200] буде видано деяке число, що займає відповідні 2
байти. Можна визначити масив будь-якого визначеного раніше типу, наприклад
unsigned arr[40], long double al[1000], char ch[80].
|/*поміняти місцями max з min*/ |// Сортування і програвання масиву |
|#include main() |#include #include |
|{ int i,j,a[10], max. nmax, min, |#'\ nclude void main() { int |
|nmin, temp; clrscr(); for (i=0; i<10;|temp, і, j, a[ 1 0]; clrscr(); for |
|i++) сіп » a[i]; max=min=a[0]; |(i=0;i<10;i++) сіп » a [ і ]; for |
|nmax=nmin=0; for (i=0; i<10; i++) |(i=0;i<9;i++) for (j=i+1 ;j<10;j++) if |
|if(a[i]>max) { max=a[i]; nmax=i;} |(a[i]>a[j]) { temp=a[i]; a[i]=a[j]; |
|else if(a[i] void main () { char s1[80], |#i nclude void |
|s2[80]; scanf( %s, 's1); І' можна об'єднати 2 scanf |main () { char s1[80], |
|в один s c a n f ( % s % s , ' s 1 , s 2); * / |s2[80]; gets(s1); gets(s2) |
|scanf('%S', s2); printf('%s
', s1); printf('%s', |puts(s1); puts(s2); |
|s2); } ввели: Hello! Good I uck! Резул ьтат: Hello! |} ввели: Hello! Good luck! |
|Good |Результат: Hello! Good luck!|
Виведення виробляється функціями printf() або puts(). Обидві функції
виводять вміст масиву до першого нульового байта. Функція puts() додає в
кінці рядка, що виводиться символ нового рядка. У функції printf()
перехід на новий рядок треба передбачати в рядку формату самим.
ФУНКЦІЇ ДЛЯ РОБОТИ З РЯДКАМИ
Для роботи з рядками існує спеціальна бібліотека, опис якої
знаходиться в файлі string.h. Найчастіше використовуються функції
strcpyO, strcat(), strlenQ, strcmpO.
Виклик функції strcpy() має вигляд
strcpy(si, s2) ;
Функція strcpy() використовується для копіювання вмісту рядка s2 в
рядок s1. Масив s1 повинен бути досить великим, щоб в нього вмістився
рядок s2. Якщо місця мало, компілятор не видає вказівки на помилку або
попередження; це не перерве виконання програми, але може привести до
псування інших даних або самої програми і неправильній роботі програми
надалі. Виклик функції strcat() має вигляд
strcat(sl, s2) ;
Функція strcat() приєднує рядок s2 до рядка s1 і вміщує його в масив, де
знаходився рядок s1, при цьому рядок s2 не змінюється. Нульовий байт,
який завершував рядок s1, буде замінений першим символом рядка s2. їв
функції strcpyO, і в функції strcat() рядок, що виходить, автоматично
завершується нульовим байтом.
Розглянемо простий приклад використання цих функцій.
Резул ьтат:
Hello, World!
Hello, World! World!
#include
#і ncl ude
main () {
char s1[20], s2[20];
strcpy(s1 , 'Hello, ');
strcpy(s2, 'World!');
puts(s1);
puts(s2);
strcat(s1, s2);
puts(s1);
puts(s2);
}
Виклик функції strcmpO має вигляд
strcmp(sl, s2);
Функція strcmpO порівнює рядки si і s2 і повертає значення О, якщо рядки
однакові, тобто містять одне і те ж число однакових символів. Під
порівнянням рядків ми розуміємо порівняння в лексикографічному значенні,
так як це відбувається, наприклад, в словнику. Звичайно, в функції
відбувається посимвольне порівняння кодів символів. Код першого символа
одного рядка порівнюється з кодом символа другого рядка. Якщо вони
однакові, розглядаються другі символи тощо. Якщо зі лексикографічно (в
значенні словника) більше s2, то функція strcmpO повертає додатне значення,
якщо менше -від'ємне значення.
Виклик функції strlen() має вигляд
strlen(s) ;
Функція strlen() повертає довжину рядка з, при цьому завершальний
нульовий байт не враховується. Виклик length('Hello') поверне
значення 5.
Розглянемо застосування цієї функції для обчислення довжини рядка, що
вводиться з клавіатури.
#include
#incl ude m а і n () { char s(80], printf( 'Введіть
рядок:');
gets(s);
printf( 'Рядок\п%з\п має довжину %d символів
', s, strlen(s)); }
ДВОВИМІРНІ МАСИВИ
Як ми вже зазначали, мова С допускає багатовимірні масиви, найпростішою
формою яких е двовимірний масив (two-dimentional array). Можна сказати, що
двовимірний масив - це масив одновимірних масивів .
Двовимірний масив int a[3][4] можна подати у вигляді таблички:
Другий індекс
Перший індекс
|а[0] [0] |а[0][1] |а[0][2] |а[0] [3] |
|а[1] [0] |а[1][1] |а[1][2] |а[1][3] |
|а[2][0] |а[2] [1] |а[2][2] |а[2] [3] |
Перший індекс - номер рядка, другий індекс - номер стовпця. Кількість байт
пам'яті, яке необхідне для зберігання масиву, обчислюється по формулі
Кільк.байтів = <розмір типу даних>*<кільк.рядків>*<кільк.ствпців>.
У пам'яті комп'ютера масив розташовується безперервно по рядках, тобто
а[0][0], а[0][1], а[0][2], а[0][3], а[1][0], а[1][1], а[1] [2], а[2] [1],.
... а[2] [3] .
Потрібно пам'ятати, що пам'ять для всіх масивів, які визначені як
глобальні, відводиться в процесі компіляції і зберігається весь час, поки
працює програма.
Часто двовимірні масиви використовуються для роботи з таблицями, що містять
текстову інформацію. Також дуже часто використовуються масиви рядків.
ІНІЦІАЛІЗАЦІЯ МАСИВІВ
Дуже важливо уміти ініціалізувати масиви, тобто привласнювати елементам
масиву деякі початкові значення. У мові С для цього є спеціальні
можливості. Самий простий спосіб ініціалізації наступний: в процесі
оголошення масиву можна указати в фігурних дужках список ініціалізаторів:
float а[6]={1.1, 2.2, 3.3, 4.0, 5, 6};
В іншому випадку така форма запису еквівалентна набору операторів:
а[0]=1.1; а[1]=2.2; ... а [5] =6.
Багатовимірні масиви, в тому числі і двовимірні масиви, можна
ініціалізувати, розглядаючи іх як масив масивів.
Ініціалізації int а[3][5]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
і int а[3][5]={{1,2,3,4,5}, {6,7,8,9,10}, {11,12,13,14,15}};
еквівалентні.
Кількість ініціалізаторів не зобов'язана співпадати з кількістю
елементів масиву. Якщо ініціалізаторів менше, то значення решти
елементів масиву не визначені.
У той же час ініціалізації
int а[3][5]={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11);
і
int а[3][5]={{1, 2, 3}, {4, 5, 6, 7, 8}, {9, 10, 11}};
різні.
//change strings: 1-6, 2-5, 3-4
#i nclude
void mai n()
{ int temp, i, j, a[6][4]={1,2,3,4,
5,6,7,8,
9,10,11,12,
1 3,14,1 5,16,
17,18,19,20,
21 ,22,23,24};
for (i=0;i<3;i++) for (j=0;j<4;j++)
{ temp=a[i][j]; a[i][j]=a[5-i][j]; a[5-i][j]=temp; } for (i=0; i<6; i++)
{
for (j=0;j<4;j++)
printf ('%4d', a[i][j]);
printf('
');
}}
Символьні масиви можуть ініціалізувати як звичайний масив:
char str[15]={'В', ' о ' , ' г ' , ' 1 ' , ' а ' , ' n ' , ' d' , ' ','
С',^',^'};
а можуть - як рядок символів:
'char str[15]= Borland C++';
Відмінність цих двох способів полягає в тому, що у другому випадку буде
доданий ще і нульовий байт. До того ж другий спосіб коротше. Допускається
також оголошення і ініціалізація масиву без явної вказівки розміру масиву.
Наприклад, для виділення місця під символьний масив звичайним способом
char str[80]= 'Це оголошення і ініціалізація масиву символів';
ми повинні вважати кількість символів в рядку або указати явно більший
розмір масиву.
При ініціалізації масиву без вказівки його розміру
char str[ ]= 'Це оголошення і ініціалізація масиву символів';
компілятор сам визначить необхідну кількість елементів масиву, включаючи
нульовий байт. Можна оголошувати таким же способом масиви будь-якого типу:
int mass []={!, 2, 3, 1, 2, 3, 4};
Від LG: При ініціалізації можна не вказувати розмірність масиву, вона
обчислюється автоматично (проте для двовимірних масивів кількість
стовпців треба указати), а при оголошенні - обов'язково. При
оголошенні масивів з невідомою кількістю елементів можна не вказувати
розмір тільки в самих лівих квадратних дужках.
ПОКАЖЧИКИ І АДРЕСИ (Керніган, Рітчі і Б.І.Березін,С.)(Б.Березін)
Пам'ять машини являє собою масив послідовно розташованих і
пронумерованих комірок, з якими можна працювати окремо і зв'язаними
ділянками. Покажчик - це група комірок в пам'яті комп'ютера, в яких може
зберігатися адреса.
[pic]
Унарний оператор & видає адресу об'єкта, так що інструкція
р=&а;
привласнює адресу комірки а змінній р (тепер р вказує на а або посилається)
.
Оператор & застосовується тільки до об'єктів, розташованих в пам'яті:
до змінних і елементам масивів. Його операндом не може бути ні вираз, ні
константа, ні регістрова змінна.
Унарний оператор * є оператор розкриття посилання. Застосований до
покажчика, він видає об'єкт, на який даний покажчик посилається.
ОГОЛОШЕННЯ ПОКАЖЧИКІВ
Якщо змінна буде покажчиком, то вона повинна бути оголошена таким
чином:
тип *<ім'я змінної>;
У цьому оголошенні тип - деякий тип мови С, визначальний тип об'єкта,
на який вказує покажчик (адреса якого містить); * - означає, що наступна за
нею змінна є покажчиком.
ОПЕРАЦІЇ НАД ПОКАЖЧИКАМИ
З покажчиками пов'язані дві спеціальні операції.: & і *. Обидві ці
операції є унарними, т. е. мають один операнд, перед якими вони ставляться.
Операція & відповідає операції 'взяти адресу'. Операція * відповідає
словам 'значення, розташоване за вказаною адресою' .
Особливість мови С полягає в тому, що знак * відповідає двом операціям,
що не мають один до одного ніякого відношення: арифметичній операції
множення і операції взяти значення. У той же час сплутати їх в контексті
програми не можливо, оскільки одна з операцій унарна (містить один
операнд), інша - множення - бінарна (містить два операнди). Унарні
операції & і * мають найвищий пріоритет нарівні з унарним мінусом.
В оголошенні змінної, що є покажчиком, дуже важливий базовий тип. Якщо
покажчик має базовий тип int, то змінна займає 2 байти, char - 1 байт тощо.
Приклад.
int а=3, Ь=5;
int *р;
р = &а; /* тепер р вказує на а*/ Ь = *р; /* b тепер
дорівнює З*/ *р= 0; /*а тепер дорівнює О*/
&*а => а - розадресація.
Унарні оператори * і & мають більш високий пріоритет, ніж арифметичні
оператори:
b = *р + 1 (взяти те, на що вказує р, додати до нього 1, а результат
привласнити змінній b.
До покажчиків можна застосувати операцію привласнення. Покажчики одного і
того ж типу можуть використовуватися в операції привласнення, як і будь-які
інші змінні. Розглянемо приклад. #include void mai n() { int x=
1 0;
int *p, *g;
p=&x;
g=p;
printf('%p', р); /* друк вмісту р */
printf('%p',g); /* друк вмісту g */
р г і n t f (' % d % d ', x, * g); / * друк величини хі величини за
адресою g*/
} Результат: FFF4 FFF4 10 10
У цьому прикладі приведена ще одна специфікація формату функції
printf() - %р. Цей формат використовується для друку адреси пам'яті в
шістнадцятковій формі.
Не можна створити змінну типу void, але можна створити покажчик на тип
void. Покажчику на void можна привласнити покажчик будь-якого іншого типу.
Однак при зворотному привласненні необхідно використати явне перетворення
покажчика на void/void *pv;
float f, *pf;
pf=&f;
pv=pf;
pp=(fioat*) pv;
У мові С допустимо привласнити покажчику будь-яку адресу пам'яті.
Однак, якщо оголошений покажчик на ціле
int *р;
а за адресою, яка привласнена даному покажчику, знаходиться змінна х типу
float, то при компіляції програми буде видане повідомлення про помилку в
рядку
р=&х;
Цю помилку можна виправити, перетворювавши покажчик на int до типу
покажчика на float явним перетворенням типу:
p=(int*)&x;
Але при цьому втрачається інформація про те, на який тип вказував
початковий покажчик.
Як і над іншими типами змінних, над покажчиками можна виробляти
арифметичні операції: складання і віднімання (операції ++ і є окремими
випадками операцій складання і віднімання). Арифметичні
дії над покажчиками мають свої особливості. Виконаємо найпростішу
програму
#include void main() { і n t x= 1 0;
int *p, *g;
p=&x;
g=p;
printf('%p', p); /* друк вмісту p */ printf('%p', p++); /* друк вмісту g
*/ } Результат: FFF4 FFF6
Після виконання цієї програми ми побачимо, що при операції ++1
значення покажчика р збільшилося не на 1, а на 2. І це правильне, оскільки
нове значення покажчика повинно вказувати не на наступну адресу пам'яті, а
на адресу наступного цілого. А ціле, як ми пам'ятаємо, займає 2 байти. Якби
базовий тип покажчика був не int, a double, то були б надруковані адреси,
відмінні на 8 (Результат:
FFEE FFF6), саме стільки байт пам'яті займає змінна типу double, тобто при
кожній операції ++р значення покажчика буде збільшуватися на кількість
байт, що займаються змінної базового типу покажчика .
Операції над покажчиками не обмежуються тільки операціями ++ і
--. До покажчиків можна додавати деяке ціле або відняти ціле. int *p=2000;
float *p=2000;
Р=Р+3; р=р+10;
Результат: р=2006 Результат: р=2040
Загальна формула для обчислення значення покажчика після виконання
операції р=р+п; буде мати вигляд
<р>=<р>+п*<кільк.байтів пам'яті базового типу покажчика>
Можна також відняти один покажчик з іншого. Так, якщо р і pi
-покажчики на елементи одного і того ж масиву, то операція р-рі дає такий
же результат, як і віднімання індексів відповідних елементів масиву.
Інші арифметичні операції над покажчиками заборонені, наприклад не
можна скласти два покажчики, помножити покажчик на число і т.д.
|#include void rnai n() {|#incl ude void main() { |
|int *p, *g, x; p=&x; |int *p, *g, x; p=&x; |
|g=p; |g=p; |
|printf('
p=%p', p); P= P + 8; |p r і n t f (' \ n \ n \ n p = % p ', |
|printf(' p+5=%p', p); printf(' g=%p',|p); P= P + 8; printf(' p+5=%p', p); |
|g); printf(' p-g=%p', p-g); |printf(' g=%p', g); printf(' p+g=%p', |
|} Результат: p=07DO p+5=07EO g=07DO |p+g); } Результат: Error UKAZAT2.CPP |
|p-g=0008 |14: Invalid pointer addition |
Покажчики можна порівнювати. Застосовні всі 6 операцій:
<, >, <=, >=, =, == і !=.
Порівняння р < g означає, що адреса, що знаходиться в р, менше адреси,
що знаходиться в g.
Якщо рід вказують на елементи одного масиву, то індекс елемента, на
який вказує р, менше індексу масиву, на який вказує g.
ЗВ'ЯЗОК ПОКАЖЧИКІВ І МАСИВІВ
Будь-який доступ до елемента масиву за допомогою операції
індексування може бути виконаний за допомогою покажчика (що в загальному
випадку працює швидше).
Декларація
int a[10]
визначає масив а розміру 10:
[pic]
Запис а[і] посилає нас до і-му елемента масиву. int *р;
р=&а[0]; /* р вказує на нульовий елемент а або містить адресу елемента а[0]
*/
[pic]
х = *р; => х = а[0], У= *(Р+1); => У = а[1];
Значення змінної типу масив (ім'я масиву) є адреса
нульового елемента масиву.
р = &а[0]; => р = а;
*(а+і) ^ а[і] &а[і] => а+і
Результат буде один і той же. Перевага використання другого варіанту
полягає в тому, що арифметичні операції над покажчиками виконуються швидше,
якщо ми працюємо з підряд йдучими елементами масиву. Якщо ж вибір елементів
масиву випадковий, то швидше і більш наочна робота з індексами.
Між ім'ям масиву і покажчиком,-виступаючим в ролі імені масиву, існує
одна відмінність. Покажчик змінна, тому можна написати р = а або р++. Але
ім'я масиву не є змінною, і записи типу а = р або а++ не допускаються.
Дуже часто доводиться працювати над обробкою текстів, т. е. з масивами
рядків. Як ми пам'ятаємо, в мові С рядок - це масив символів, що
закінчується нульовим байтом. Розглянемо дві програми, що реалізовують
практично, одні і ті ж дії.
#incl ude
#include
void main()
{ char *p, str[]='String From Letters in Different Registers';
/* Рядок, що Складається з Букв в Різних Регістрах; */ int і=0; printf(
'Рядок Буде Надрукований Заголовними Буквами');
while (str[i]) printf('%c', toupper(str[i++]));
p=str; printf(' Рядок Буде Надрукований Малими Буквами');
while (*p) printf('%c', tolower(*p++)); }
Якщо в цих прикладах замінити рядок на англійській мові на рядок,
набраний російськими буквами, то ніякого перетворення букв в рядкові або,
навпаки, в прописні не станеться. Це пов'язано з тим, що стандартні функції
toupper() і tolower () аналізують значення
1
0 аргументу і повертають те ж саме значення, якщо він не є відповідно малою
або великою буквою латинського алфавіту. Якщо ж аргумент є малою буквою
латинського алфавіту, то значенням функції toupper() буде відповідна
велика буква (точніше, код цієї букви). Функція tolower () змінює код лише
великих букв латинського алфавіту. Прототипи цих функцій знаходяться в
заголовному файлі ctype.h.
МАСИВИ ПОКАЖЧИКІВ
Покажчики, як і змінні будь-якого іншого типу, можуть об'єднуватися в
масиви. Оголошення масиву покажчиків на 10 цілих чисел має вигляд int
*x[10] ;
Кожному з елементів масиву можна привласнити адресу; наприклад, третьому
елементу привласнимо адресу цілої змінної у:
х[2]=&у;
щоб знайти значення змінною у, можна написати *х(2].
Наведемо приклад використання масиву покажчиків. Частіше за все це
буває зручно при обробці масиву рядків.
/* you must run. exe-file to watch the rezult of this program. Перегляд
файлів в поточному каталозі з одним з шести розширень */
#include
#include ^include
#include
main()
{char ch, s[80], *ext[]={'exe', 'corn', 'cpp', 'c', 'pas', '*'};
clrscr();
for(;;) {do { printf( 'Файли з розширенням:^');
printf('1. exe
'); 'printf( 2. com
'); 'printf( 3. cpp
'); 'pnntf( 4.
з \ n ');
printf('5. pas
'); printf('6. *
'); //any extension printf('7.
quit
');
printf('BauJ вибір(1-7):)(
');
ch=getche();
printf('
');
} while (ch<'1' ;! ch>'7');
if (ch=='7') break;
strcpy(s, 'dir *.'); strcat(s, ext[ch-'0'-1 ]); strcat(s, '/p');
system(s);} }
Тут функція system() - бібліотечна функція, яка примушує операційну
систему DOS виконати команду, що є аргументом цієї функції.
Взагалі рядкова константа в мові С асоціюється з адресою початку рядка в
пам'яті, тип рядка виходить char* (покажчик на тип char). Тому можливо і
активно використовується наступне привласнення:
char *pc;
'рс = Hello, World!';
У мові С можлива також ситуація, коли покажчик вказує на покажчик. У
цьому випадку опис буде мати наступний вигляд:
int -*'*point;
[pic]
point має тип покажчик на покажчик на int. Відповідно, щоб набути
цілочисельного значення змінною, на яку указьіваеі point, треба у
вираженні використати **point.;
Приклад використання:
11
^include
void m а і n()
{ int i, pi, ppi;
і =7; pi=&i;
p p i = & p i;
printf( 'i = %d pi = %p ppi = %p
', i, pi, ppi);
*pi++;
printf( 'i = %d pi = %p ppi = %p
', i, pi, ppi);
**ppi = 12;
printf( 'i = %d pi = %p ppi = %p
', i, pi, ppi);
}
ІНІЦІАЛІЗАЦІЯ ПОКАЖЧИКІВ
Після того як покажчик був оголошений, але до того, як йому було
привласнене якесь значення, покажчик містить невідоме значення. Спроба
використати покажчик до привласнення йому якогось значення є неприємною
помилкою, оскільки вона може порушити роботу не
тільки вашої програми, але і операційної системи. Навіть якщо цього не
сталося, результат роботи програми буде неправильним і знайти цю помилку
буде досить складно.
Вважають, що покажчик, який вказує в 'нікуди', повинен мати значення
null, однак і це не робить його 'безпечним'. Після того, як він попаде в
праву або ліву частину оператора привласнення, він знову може стати
'небезпечним'.
З іншого боку нульовий покажчик можна використати, наприклад, для
позначення кінця масиву покажчиків.
Якщо була спроба привласнити яке-небудь значення тому, на що вказує
покажчик з нульовим значенням, система видає попередження, що з'являється
під час роботи програми (або після закінчення роботи програми) 'Null
pointer assignment'. Поява цього повідомлення є мотивом для пошуку
використання неініціалізувати покажчика в програмі.
