Курсова робота на тему: «АЛГОРИТМИ ОБРОБКИ РЯДКІВ»

Зміст

ВСТУП    3

1.    ОСНОВНІ ВИЗНАЧЕННЯ І ПОНЯТТЯ    4

2.    ФОРМАЛЬНІ СИСТЕМИ ОБРОБКИ РЯДКІВ    7

2.1.    Алгоритми Маркова    8

2.2.    Алгоритм Markov    11

3.    ПРИМІТИВНІ ФУНКЦІЇ ДЛЯ МАНІПУЛЮВАННЯ РЯДКАМИ    18

4.    ПОШУК ПІДРЯДКІВ    23

5.    МАНІПУЛЯЦІЇ НАД РЯДКАМИ В МОВІ С    25

5.1.    Функції обробки символів та рядків    26

5.2.    Функції, що стосуються рядків, які розглядаються як послідовність байт        27

5.3.    Функції, що реалізують обробку рядків    28

ВИСНОВКИ    30

ЛІТЕРАТУРА    31

ДОДАТКИ    32

ВСТУП

Темою даної роботи є: «Алгоритми обробки рядків». На сьогоднішній день вона є досить актуальна, адже рядки є важливим елементом будь – якої мови програмування. Їх опрацювання вимагає ґрунтовного знання про рядки та маніпуляцій над ними. У цій роботі необхідно дати основні визначення та поняття символьних рядків, та операцій над ними. В ній будуть описані системи для представлення та маніпулювання символьними рядками. При цьому будуть поставлені дві мети: підкріплення понять, введених раніше, і, що більш важливо, подання розуміння примітивних операцій, які можуть виконуватись над рядками.

В роботі описується система, або модель, яка називається алгоритмами Маркова, що заснована на операції типу підстановки, яка може бути застосована до будь-якого вхідного рядку з даного алфавіту. Типи маніпуляцій над рядками в рамках цієї моделі фактично необмежені. Тим не менше Марківська система непрактична з точки зору програмування та обробки даних. У слідуючому пункті пропонується набір примітивів і сукупність базисних функцій обробки рядків. В завершення роботи, будуть приведені основні функції обробки рядків на мові С.

 

  1. ОСНОВНІ ВИЗНАЧЕННЯ І ПОНЯТТЯ

    У цій частині розглядаються операції (або маніпуляції), які можна проводити над рядками. Як і в арифметичних операцій над натуральними числами, в операцій над рядками існує багато цікавих властивостей. Звернемось, наприклад, до операції додавання натуральних чисел. Її можна представити у вигляді функції двох змінних:

        (1.1)

    де х і у – натуральні числа. Ця функція володіє деякими цікавими властивостями. По-перше, сума будь-яких двох натуральних чисел є натуральним числом. Ця властивість називається замиканням. Замикання – необхідний атрибут системи (тобто сукупності деякої множини і операції над цією множиною), що називається алгеброю, або алгебраїчною системою. По-друге (х + у) + z = х + (у + z) = х + у + z, коли х, у та z є натуральними числами. Відповідно до цього операція додавання є асоціативною. По-третє, існує число i, таке, що для будь-якого натурального числа х справедливо х + i = х. Це число х є нулем і називається нейтральним елементом адитивної системи. Є багато інших важливих властивостей, зокрема дистрибутивність і комутативність, які притаманні арифметичним операціям (таким як додавання та множення) над множиною натуральних чисел.

    Обговорення рядків почнемо з формального визначення рядка.З цією метою введемо поняття алфавіту і операцію конкатенації. Взагалі кажучи, алфавітом V називають кінцеву не порожню множину символів. Відомим прикладом алфавіту є множина V={а, b, c, …, z,} а {α, β, γ, ε} – чотирьох-символьний алфавіт, який являє собою під-алфавіт грецького алфавіту.

    Кажуть, що конкатенація двох символів алфавіту, наприклад, символів ‘а’ і ‘b’, утворює послідовність символів, а саме ‘ab’.(Зазначимо, що в подальшому при посиланні на символ з алфавіту або на послідовність таких символів, вони будуть вноситись в апострофи). Операція конкатенації може бути застосована також і до послідовностей символів. Наприклад, у результаті конкатенації ‘ab’і ‘ab’ вийде ‘abab’ оператор конкатенації будемо позначати спеціальним знаком ©. Це дасть можливість записувати вирази, такі як ‘ab’ © ‘а’, що еквівалентно послідовності ‘aba’.

    Рядок з алфавіту V є 1) символ з алфавіту V або 2) послідовність символів, отримана в результаті конкатенації символів з алфавіту V. Прикладами рядків над алфавітом V={1,2,3} є ‘1’, ’31 ‘, ‘3332’ і ‘222 ‘.

    Нехай V © V = V2 означає множину всіх рядків довжини 2 над V, V © V © V = V2 © V = V3 – множина рядків довжини 3 над V, і взагалі V © V © …© V=Vn – множина рядків довжини n над V. Тоді транзитивне замикання алфавіту V, що позначається через V+ визначиться як

        (1.2)

    Додамо до цієї множини для повноти спеціальний рядок , так званим порожнім(або нульовим) рядком, і отримаємо рефлексивне замикання V* алфавіту V, тобто

        (1.3)

    Рядок має властивість одиниці (тобто х © = © х = х для будь-якого рядка х, що входить до множини V*) і називається одиничним елементом в алгебрі, утвореної множиною V* і операцією конкатенації. Іншою властивістю цієї алгебри є асоціативність [тобто(х ©y)©z — х ©{у © z) =x©y©z для х, у, z б V*].(х © y) © z = х © (у © z) = x © y © z для х, у, zϵV *].

    В якості прикладу розглянемо множину рядків V*, які можуть бути породжені з алфавіту V = {a,b}. Деякі підмножини множини V* такі:

        (1.4)

        (1.5)

        (1.6)

    Далі ми будемо неодноразово посилатися на замикання V* того чи іншого алфавіту.

    ЗАВАНТАЖИТИ

    Для скачування файлів необхідно або Зареєструватись

    Alg Obrob Rjadkiv (213.4 KiB, Завантажень: 2)

    ЗАВАНТАЖИТИ

    Для скачування файлів необхідно або Зареєструватись

    Alg Obrob Rjadkiv (706.1 KiB, Завантажень: 1)

Сторінка: 1 2 3 4 5 6 7 8 9
завантаження...
WordPress: 23.38MB | MySQL:26 | 0,454sec