Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Задача: Модификация ф-ии strstr, возвращает все вхождения подстроки в строку

990
20 марта 2009 года
Stalcer
137 / / 15.08.2004
Задача состоит в модификации стандартной ф-ии для работы со строками strstr,
так, чтобы она возвращала указатель на массив, содержащий индексы всех вхождений подстроки в строку.

Пример:
строка: aaabbaaabb
подстрока: bb
результат: 3, 8

Моя реализация ниже, буду благодарен за комментарии.

Код:
#include <iostream>

using namespace std;
//добавление нового элемента в массив
void addElement(int*& ar, int el, int &N)
{
    int* temp = new int [N + 1], t=0;  

    for(int i=0; i<N; i++)
    {
        temp = ar[t];
        ++t;
    }
    temp[N] = el;  

    ++N;
    delete []ar;
    ar = temp; 
}
//cтрока, подстрока, массив индексов, размер массива индексов
void strstr(char* str, char* sub, int*& r, int& r_size)
{
//длина подстр и исх стр, счетчик эл-тов массива индексов и указ на результат
    int sub_l=0, str_l=0, rs=0, *res=0;
   
    while(str[str_l]!='\0') str_l++; //длина исходной строки
    while(sub[sub_l]!='\0') sub_l++; //длина подстроки   

    if(str_l == 1) return; //если 1 эл в строке
    else if(sub_l == 1)//если 1 эл в подстроке
    {
        for(int i = 0; i<str_l; i++)   
            if(sub[0] == str)          
                addElement(res,i,rs);                  
       
        r = res; //возврат массива индексов
        r_size = rs; //размерность массива индексов
        return;
    }

    for(int i=0; i<str_l; i++) 
        if(str==sub[0]) //если совпал символ с первым символом подстроки
        {
            int t = ++i, count=0;
            for(int j=1; j<sub_l; j++) //ищем вхождение
            {
                if(str[t] == sub[j])
                {
                    ++count;
                    if(count == sub_l-1) //если вхождение
             //выделяем ячейку и записываем индекс                  
                        addElement(res,i-1,rs);
                }              
                ++t;
            }
        }
   
    r = res; //возврат массива индексов
    r_size = rs; //размерность массива индексов  
}

int main()
{
    char str[50], sub[50];
    int *r, r_size;

    cout<<"String:"<<endl;
    cin.getline(str,49);

    cout<<"Sub string:"<<endl;
    cin.getline(sub,49);       

    strstr(str,sub,r,r_size);

    for(int i=0; i<r_size; i++) //вывод индексов
        cout<<r<<endl;

        delete []r;

    return 0;
}
3
20 марта 2009 года
Green
4.8K / / 20.01.2000
А почему бы не использовать C++ ?
990
20 марта 2009 года
Stalcer
137 / / 15.08.2004
Цитата: Green
А почему бы не использовать C++ ?



Вы имеете ввиду String? Если да, то задача стоит именно в работе со строками в стиле Си.

3
20 марта 2009 года
Green
4.8K / / 20.01.2000
Цитата: Stalcer
Вы имеете ввиду String? Если да, то задача стоит именно в работе со строками в стиле Си.


Я имею в виду в первую очередь алгоритмы <algorithm>.

842
21 марта 2009 года
sigmov
301 / / 16.09.2008
1.
 
Код:
//добавление нового элемента в массив
void addElement(int*& ar, int el, int &N)

Тут вы очевидно пытаетесь "расширять" динамический массив на 1, выделя место для n+1 элемента и перенося в него n первых элементов.
НО(!)
Такая функция в языке С существует - называется:
void* reallok(void* dest, int size) - расширяет область (dest) до нужного количества(size) в байтах и возвращает указатель на область.

2.
 
Код:
//cтрока, подстрока, массив индексов, размер массива индексов
bool strstr(char* str, char* sub, int*& r, int& r_size)

Если вы имеете r_size, то bool является лишним, так как r_size вполне достаточно: (r_size==0)~false; (r_size>0)~true;
В остальном функция довольно логично построена...

Когда то я такое же делал: :)
Вот вариант, как бы я реализовал это сегодня:
Код:
#include <iostream>
using namespace std;
#define _Out

int* strstr_arr(char* str_1, char* str_2, _Out int &count)
{
    count = 0;      //число нахождений
    int *indexs;    //масив индексов
    char* _It = str_1-1;    //Текущее положение
    while((_It = strstr(++_It, str_2))>str_1)                                       //До тех пора можно найти подстроку правее текущего положения приравневаем положение к найденному   
        *((indexs=(int*)realloc(indexs,(++count)*sizeof(int)))+count-1)=_It-str_1;  //Расширяем массив, увеличиваем count, последний элемент массива кладем равным разнице между положением и началом
    return indexs;
}
void main()
{
   
    char* str = "faaabaaadf";
    char* find = "aa";
    int count;
    int* Arr = strstr_arr(str,find,count);
    for(int i=0;i<count;i++)
        cout<<Arr<<endl;
    free(Arr);
}
1.9K
21 марта 2009 года
GreenRiver
451 / / 20.07.2008
Stalcer, ешё у Вас утечка в коде. Массив формируется в функции и передаётся наружу, где его никто не удаляет.
После того как r будет не нужен, его надо удалить.

В данном случае программа завершится и утечка не будет иметь значения, но лучше сразу привыкать затыкать дыры, чем потом искать их в огромном проекте :rolleyes:
990
21 марта 2009 года
Stalcer
137 / / 15.08.2004
sigmov, спасибо, учел, теперь ф-я void :)
Риалок не использовал в учебных целях. Сейчас буду разбирать ваш пример :)

GreenRiver, спасибо, учел :)
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог