Основи програмування на С ++ для початківців

Пошук підрядка в інсультом

Зараз ми розберемо на прикладах, як може виглядати алгоритм пошуку підрядка в рядку. Приклади будуть грунтуватися на функціях стандартних бібліотек, адже саме в таких функціях і проявляються всі зручності написання програм. А ось класичний розбір алгоритму, заснований на циклах і порівняннях, також досить примітний. Тому ми його розглянемо в цьому ж уроці.

Сам алгоритм в принципі дуже простий. Є два рядки. Наприклад "Привіт Світ"  і "це"

Працювати будемо в два цикли:

  1. Перший буде виконувати прохід по всій рядку, і шукати місце розташування першої літери шуканої рядка ( "це" ).
  2. другий, починаючи з знайденої позиції першої літери – звіряти, які букви стоять після неї і скільки з них підряд збігаються.

Проілюструємо пошук підрядка в рядку:

алгоритми пошуку з ++, подстрока пошуку інсульту, C ++, як знайти підрядок в рядку, програмування на с ++ для початківців, доповідь, курсова робота

На перших двох ітераціях циклу порівнювані літери не будуть збігатися (виділено червоним). На третій ітерації шукана буква (перший символ шуканого слова) збіглася з символом у рядку, де відбувається пошук. При такому збігу в роботу включається другий цикл.

Він покликаний відраховувати кількість символів після першого в шуканої рядку, які будуть співпадати з символами в рядку вихідної. Якщо один з наступних символів не збігається – цикл завершує свою роботу. Немає сенсу ганяти цикл даремно, після першого розбіжності, так як вже зрозуміло, що шуканого тут немає.

На третій ітерації збігся тільки перший символ шуканої рядка, а ось другий вже не збігається. Доведеться першого циклу продовжити роботу. Четверта ітерація дає необхідні результати – збігаються всі символи шуканої рядка з частиною вихідної рядки. А раз все символи збіглися – подстрока знайдена. Роботу алгоритму можна закінчити.

Посмотрим, як виглядає класичний код пошуку підрядка в рядку в С ++:

Два циклу виконують кожен свою задачу. Один тупотить по рядку в надії знайти “голову” шуканого слова (перший символ). другий з'ясовує, чи є після знайденої “голови” “тело” шуканого. причому перевіряє, чи не лежить це “тело” в кінці рядка. Тобто,. чи не є довжина знайденого слова на одиницю більше довжини шуканої рядка, якщо враховувати, що в цю одиницю потрапляє Нулла-термінатор ( ' 0' ).

алгоритми пошуку з ++, подстрока пошуку інсульту, C ++, як знайти підрядок в рядку, програмування на с ++ для початківців, доповідь, курсова робота

Ми бачимо, яка програма знайшла починають подстрокуПроте, в осередках символьного масиву з індексом 0 і 4. Але чому? Адже в словіParapapaтака послідовність. Вся справа в ' 0' .

В цілому зміст самого алгоритму на цьому закінчується. Більше ніяких складнощів крім нуля в кінці рядка немає. Однак, слід звернути увагу на множинність пошуку. що, якщо нам необхідно знайти в рядку кілька позицій?

Скільки разів шукане слово зустрічається в рядку і в яких місцях? Саме це і покликаний контролювати третій параметр – Int N – номер входження в рядок. Якщо поставити туди одиницю – він знайде перший збіг шуканого. якщо двійку, він змусить перший цикл пропустити чергу, будуть знайдені, і шукати другу. якщо трійку – шукати третє і так далі. З кожним знайденим шуканим словом, цей лічильник входжень зменшується на одиницю. Це і дозволяє описати пошук в циклі:

Тобто знайти перше, друге, третій, четверте збіг… Поки функція не поверне -1, що вкаже на відсутність N-ного шуканого в рядку.

тепер, для порівняння, пошук підрядка в рядку С ++ з хедером string.

Все! клас string в С ++ забезпечений методом знайти(), повертає номер позиції, з якого починається тіло шуканої рядка в заданій стрічці. Результат:

алгоритми пошуку з ++, подстрока пошуку інсульту, C ++, як знайти підрядок в рядку, програмування на с ++ для початківців, доповідь, курсова робота

Як же множинність? Так будь ласка:

Функция знайти() приймає другим параметром номер символу, з якого почати пошук. Тобто,. знайшовши перше входження, його значення збільшується на одиницю і знайти() продовжує пошук з наступного символу після знайденої голови. Результат:

алгоритми пошуку з ++, подстрока пошуку інсульту, C ++, як знайти підрядок в рядку, програмування на с ++ для початківців, доповідь, курсова робота

Все це є в С ++, і сам класс string досить зручний для роботи з рядками саме, як рядками, а не просто з масивом символів.

9 думки про "Пошук підрядка в інсультом

  1. мені здається так краще, так як позбавляємося перевірки на нуль символ

    1. Взагалі то, в мові C, і успадковано в C ++, вважається, що числове значення 0 відповідає false (порушення умови), а будь-нульове значення – true (дотримання умови).
      Тому формально if( n – 1 ) еквівалентними, якщо( n != 1 ).

      P.S. формально тому, що в коректність коду взагалі я не вникав.

    2. До такого запису слід звикнути, тому що в реальному коді на C / C ++ такий запис зустрічається досить часто, особливо при порівнянні указателей з значенням NULL:

      int *ptr = ...
      ...
      if( ptr ) { ... }

      1. велике спасибі. надалі, буду знати

      2. тоді в 20 рядку !(п-1) значить n = 1?

залишити коментар

Ваша електронна адреса не буде опублікований. Обов'язкові поля позначені * *