Програмування С, С++теорія та практика (частина 1)
1.19.1 Лінійні списки
Лінійний список - це скінченна послідовність однотипних елементів (вузлів). Кількість елементів у цій послідовності називається довжиною списку. Наприклад :
Р=(1,2,3,4,5,6) - лінійний список, його довжина 6.
При роботі зі списками дуже часто доводиться виконувати такі операції :
• додавання елемента в початок списку;
• вилучення елемента з початку списку;
• додавання елемента в будь-яке місце списку;
• вилучення елемента з будь-якого місця списку;
• перевірку, чи порожній список;
• очистку списку;
• друк списку.
Основні методи зберігання лінійних списків поділяються на методи послідовного та зв ’язаного зберігання.
Послідовне зберігання списків. Метод послідовного зберігання списків ґрунтується на використанні масиву елементів деякого типу та змінної, в якій зберігається поточна кількість елементів списку.
#йе£іпе МАХ 100 /* максимально можлива довжина
списку */
£урегіе£ з'Ьгис'Ь {
іп£ х; /* тут потрібно описати структуру елементів списку*/
} е1етеп'Ь'Ьуре ;
£урегіе£ з'Ьгис'Ь {
е1етеп'Ь'Ьуре е1етеп'Ьз [МАХ] ; іп£ соип'Ь ;
} 1із^^уре;
У вищенаведеному фрагменті програми описуються типи даних еіетепііуре (визначає структуру елемента списку) та Іііііуре (містить масив для зберігання елементів та змінну для зберігання поточного розміру списку).
Наводимо приклади реалізації функцій для виконання основних операцій над списками.
1. Ініціалізація списку (робить список порожнім).
VОІЙ. 1із'Ь_гезе'Ь(1із'Ь'Ьуре *1із£)
{
1із^->соип^=0;
};
2. Додавання нового елементу у кінець списку.
VОій. 1із'Ь_агігі(1із'Ь'Ьуре *1із'Ь,е1етеп'Ь'Ьуре е1етеп'Ь)
{
і£ (1із'Ь->соип'Ь==МАХ) ге'Ьигп;
1із'Ь->е1етеп'Ьз [1із'Ь->соип'Ь++ ] =е1етеп'Ь;
};
3. Додавання нового елементу в позицію роз.
|
10 11 12 13 14
|
Рис. 1.24. Додавання нового елемента в задану позицію
Vоій. 1І5'Ь_іп5ег'Ь(1І8'Ь'Ьуре *1із'Ь,іп'Ь роз,е1етеп'Ь'Ьуре еІетеп'Ь)
{
іп£ і ;
і£ (роз<0| |роз>1із'Ь->соип'Ь| |роз>=МЛХ) ге'Ьигп;
£ог (і=1із^->соип^;і>роз;і--)
{
1із'Ь->е1етеп'Ьз[і ]=1із'Ь->е1етеп'Ьз[]-1];
} ;
1із'Ь->е1етеп'Ьз[]]=е1етеп^;
1із£->соип'Ь++;
};
|
4. Вилучення елемента з номером роз.
|
Рис.1.25. Схема вилучення елемента зі списку
VОІЙ. 1І5'Ь_гіе1Є'Ье(1І5'Ь'ЬурЄ *1І5'Ь,ІП'Ь роз)
{
іпї і ;
і£ (роз<0||роз>1із'Ь->соип'Ь) ге'Ьигп;
£ог (і=роз+1;і<1із^->соип^;і++)
{
1із'Ь->е1етеп'Ьз[]-1]=1із^->е1етепїз[]];
} ;
1із^->соип^--;
};
5. Отримання елемента з номером рох.
іп£ 1із'Ь_де'Ь(1із'Ь'Ьуре *1із'Ь,іп'Ь роз,е1етеп'Ь'Ьуре *е1етеп'Ь)
{
і£ (роз<0||роз>1із'Ь->соип'Ь)
{
ге'Ьигп 0 ;
 |
|||||||
 |
|||||||
 |
 |
||||||
|
|
|
в) |
|
Рис. 1.26. Схематична структура односпрямованого (а), двоспрямованого (б), та кільцевого списків (в) |
При послідовному зберіганні списків за допомогою масивів елементи списку зберігаються в масиві. Така організація дозволяє легко переглядати вміст списку та додавати нові елементи в його кінець. Але такі операції, як вставка нового елемента в середину списку чи вилучення елементу з середини списку потребують зсуву всіх наступних елементів. При збільшенні елементів масиву кількість операцій, потрібна для впорядкування списку, стрімко зростає.
Зв’язане зберігання лінійних списків. Найпростіший спосіб зв’язати множину елементів - зробити так, щоб кожний елемент
містив посилання на наступний. Такий список називається односпрямованим (однозв ’язаним). Якщо додати в такий список ще й посилання на попередній елемент, то отримаємо двозв’язаний список. А список, перший та останній елементи якого зв’язані, називається кільцевим.
Структуру даних для зберігання односпрямованого лінійного списку можна описати таким чином :
£урегіе£ 1опд е1епЛуре;
£урегіе£ з'Ьгис'Ь погіе {
е1ет^уре Vа1; з'Ьгис'Ь погіе *пех£;
} 1із^;
В даному фрагменті програми описуються декілька типів даних : еїетіуре - визначає тип даних лінійного списку. Можна використовувати будь-який стандартний тип даних, включаючи структури.
їізі - визначає структуру елемента лінійного списку (уаї - значення, яке зберігається у вузлі, пехґ - покажчик на наступний вузол).
Схематично лінійний односпрямований список виглядає так :
|
|
уаї |
пехт |
|
уаї |
пехт |
|
|
|
|
|
т |
|
|
02 |
|
|
|
|
|
|
|
|
|
|
(II: |
Рис. 1.27. Схематичне зображення односпрямованого лінійного списку
Реалізація основних операцій :
1. Включення елемента в початок списку.
|
Рис. 1.28. Схема дії операції включення елемента в початок списку |
Ііз'Ь *агігіЬед(1із'Ь *£ігз^, е1епЛуре х) { Ііз'Ь *^зр;
Vзр = (1із£ *) та11ос(зігео£(1із'Ь)) Vзр->Vа1=x;
Vзр->пеx^=£і^з^;
£і^з■Ь=Vзр; ге'Ьигп £ігз^;
}
|
2. Видалення елемента з початку списку.
Рис. 1.29. Схема дії операції видалення елемента |
1із£ *гіе1Ьед(1із'Ь *£ігз£) { 1із£ *^зр;
Vзр=£і^з^->пеx^; £гее(£ігз£); ге'Ьигп Vзр;
}
3. Включення нового елемента у список.
Рис. 1.30. Схема включення нового елемента у список
1із£ *агігі(1із'Ь *ргей, е1епЛуре х)
{ 1із£ *^зр;
Vзр = (1із£ *) та11ос(зігео£(1із'Ь)); Vзр->Vа1=x;
Vзр->пеx^=р^ей.- >пеx^ ; р^егі.->пеx■Ь=Vзр ; ге'Ьигп Vзр;
4. Видалення елемента зі списку.
уаі пехт уаі пехт уаі пехт
... ~Н І рИЧ І "-ЬН І
ртесі І________________________ *
Рис. 1.31. Схема вилучення елемента зі списку
е1епЛуре йе1(1із£ *ргей)
{ е1ет£уре х ;
1із£ *^зр;
Vзр=р^ей.- >пех£ ; ргегі->пех'Ь=ргегі.->пех'Ь->пех'Ь ; x=Vзр->Vа1;
£гее(Vзр); ге'Ьигп х;
}
5. Друк значень списку.
VОІЙ. ргіп^(1ізї *£ігзї)
{ 1із£ *^зр;
Vзр=£і^з■Ь; мЬі1е (Vзр)
{
ргіп££("%і\п",Vзр->Vа1);
Vзр=Vзр->пеxї;
}
}
6. Перевірка, чи порожній список іп£ риз^(1ізї *£ігзї)
{
ге'Ьигп !£ігзї;
}
7. Знищення списку 1ізї *кі11(1із-Ь *£ігзї)
{
мЬі1е (•риз'Ь (£ігз£)) £ігз'Ь=гіе1Ьед(£ігз'Ь); ге'Ьигп £ігзї;
12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99