acbadbabbad. Наступні схеми ілюструють всі етапи виконання алгоритму:
Таблиця зміщень для зразка" abbad .
Початок пошуку. Останній символ зразка не збігається з накладеним символом рядка. Зрушуємо зразок вправо на 5 позицій:
Три символи зразка співпали, а четвертий - ні. Зрушуємо зразок вправо на одну позицію:
Останній символ знову не збігається з символом рядка. Відповідно до таблиці зміщень зрушуємо зразок на 2 позиції:
Ще раз зрушуємо зразок на 2 позиції:
Тепер, відповідно до таблиці, зрушуємо зразок на одну позицію, і отримуємо шукане входження зразка:
1.6 Лінійний односпрямований список
У одинзв'язного списку кожен елемент інформації містить посилання на наступний елемент списку. Кожен елемент даних зазвичай являє собою структуру, яка складається з інформаційних полів і покажчика зв'язку. Концептуально однозв'язний список виглядає так, як показано на рис.2.
Існує два основних способи побудови одинзв'язного списку. Перший спосіб - поміщати нові елементи в кінець списку. Другий - вставляти елементи в певні позиції списку, наприклад, в порядку зростання. Від способу побудови списку залежить алгоритм функції додавання елемента. Давайте почнемо з простішого способу створення списку шляхом приміщення елементів в кінець.
Як правило, елементи пов'язаного списку є структурами, оскільки, крім даних, вони містять посилання на наступний елемент. Тому необхідно визначити структуру, яка буде використовуватися в подальших прикладах. Оскільки списки розсилки зазвичай зберігаються в пов'язаних списках, хорошим вибором буде структура, що описує поштову адресу. Її опис показано нижче:
struct address {name [40]; street [40]; city [20]; state [3]; zip [11];
struct address * next;/* Посилання на наступну адресу */
} info;
Наведена нижче функція slstore () створює однозв'язний список шляхом поміщення кожного чергового елемента в кінець списку. Як параметри їй передаються покажчик на структуру типу address, що містить новий запис, і покажчик на останній елемент списку. Якщо список порожній, покажчик на останній елемент повинен бути рівний нулю.
void slstore (struct address * i, address ** last)
{(! * last) * last=i;/* Перший елемент у списку */(* last) - gt; next=i; gt; next=NULL;
* last=i;
}
Незважаючи на те, що створений за допомогою функції slstore () список можна відсортувати окремою операцією вже після його створення, легше відразу створювати впорядкований список, вставляючи кожен новий елемент у потрібне місце в послідовності. Крім того, якщо список вже відсортований, має сенс підтримувати його впорядкованість, вставляючи нові елементи у відповідні позиції. Для вставки елем?? нта таким способом потрібно послідовно переглядати список до тих пір, поки не буде знайдено місце нового елемента, потім вставити в знайдену позицію новий запис і перевстановити посилання.
При вставці елементу в однозв'язний список може виникнути одна з трьох ситуацій: елемент стає першим, елемент вставляється між двома іншими, елемент стає останнім. На рис.3 показана схема зміни посилань в кожному випадку.
Слід пам'ятати, що при вставці елемента в початок (першу позицію) списку необхідно також змінити адресу входу в список десь в іншому місці програми. Щоб уникнути цих складнощів, можна в якості першого елементу списку зберігати службовий сторожовий елемент. У разі впорядкованого списку необхідно вибрати деяке спеціальне значення, яке завжди буде першим у списку, щоб початковий елемент залишався незмінним. Недоліком даного методу є досить велика витрата пам'яті на зберігання сторожового елемента, але зазвичай це не настільки важливо.
Наступна функція, sls_store (), вставляє структури типу address в список розсилки, впорядковуючи його по зростанню значень у полі name. Функція приймає покажчики на покажчики на перший і останній елементи списку, а також покажчик на вставляється елемент. Оскільки перший або останній елементи списку можуть змінитися, функція sls_store () при необхідності автоматично оновлює покажчики на початок і кінець списку. При першому виклику даної функції покажчики first і last повинні бути рівні нулю.
/* Вставка в упорядкований однозв'язний список. */sls_store (struct address * i,/* новий елемент */address ** start,/* початок списку */address ** last)/* кінець спис...
