Форум программистов, компьютерный форум CyberForum.ru

Найти первую повторяющуюся строку в массиве строк - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.80
ula
0 / 0 / 0
Регистрация: 04.12.2009
Сообщений: 26
01.03.2010, 11:39     Найти первую повторяющуюся строку в массиве строк #1
Здравствуйте, существует задача: найти первую повторяющуюся строку в массиве строк. Подскажите пожалуйста как правильно реализовать алгоритм. Я смутно себе это представляю, но точно думаю что все строки нужно сравнить между собой, а как дальше?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
insideone
Модератор
Автор FAQ
 Аватар для insideone
3623 / 901 / 48
Регистрация: 10.01.2010
Сообщений: 2,429
01.03.2010, 15:21     Найти первую повторяющуюся строку в массиве строк #2
А что если упорядочить? Тогда найти повтор будет проще, а потом найти его номер в исходном массиве
ula
0 / 0 / 0
Регистрация: 04.12.2009
Сообщений: 26
01.03.2010, 15:33  [ТС]     Найти первую повторяющуюся строку в массиве строк #3
Упорядочить каким образом, можно по-конкретнее? Просто я в этом абсолютный новичок. В книгах особо ничего не нашла.
insideone
Модератор
Автор FAQ
 Аватар для insideone
3623 / 901 / 48
Регистрация: 10.01.2010
Сообщений: 2,429
01.03.2010, 15:48     Найти первую повторяющуюся строку в массиве строк #4
C++
1
2
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
#include <iostream>
#include <string>
using namespace std; 
 
#define MAX_STRS 5
int main() 
{
    string* List[MAX_STRS]; memset(&List[0], 0, MAX_STRS); 
    string Strs[MAX_STRS];
    for (size_t i = 0; i < MAX_STRS; i++)
        cin >> Strs[i];
 
    size_t Count = 0; List[Count++] = &Strs[0];
    for (size_t i = 1; i < MAX_STRS; i++)
    {
        for (size_t j = 0; j < Count; j++)
        {
            if ( (*List[j]) == Strs[i] )
            {
                cout << "Rep at " << i + 1 << " line: \"" << Strs[i] << "\"" << endl;
            //i = MAX_STRS; break;
            }
        }
        List[Count++] = &Strs[i];
    }
return 0; 
}
В общем так решилось. В List мы сохраняем те строки которые уже прошли в цикле и по этим сохраненным проверяем есть ли в List текущая строка - если есть то повтор.
ula
0 / 0 / 0
Регистрация: 04.12.2009
Сообщений: 26
01.03.2010, 16:09  [ТС]     Найти первую повторяющуюся строку в массиве строк #5
Вот это да, вы еще студент, а уже пишите такие сложные программы, спасибо огромное, обязательно постараюсь разобраться в этом коде, вот бы мне научиться так понимать. Только можно вопрос: нам сказали, чтобы мы работали в этом алгоритме с символьными строками, наверное будут какие-то изменения в этом алгоритме или нужно просто сначала инициализировать массив как символьный типа char ar[]. Он наверное должен быть двумерным?
insideone
Модератор
Автор FAQ
 Аватар для insideone
3623 / 901 / 48
Регистрация: 10.01.2010
Сообщений: 2,429
01.03.2010, 17:02     Найти первую повторяющуюся строку в массиве строк #6
Если честно сначала начал писать с символьными строками но подумал что слишком сложно выйдет. Тут хоть алгоритм ясен. Различия будут в том что символьные строки уже так
C++
1
(*List[j]) == Strs[i]
Не сравнишь, а нужно будет использовать функцию strcmp
List будет таким
C++
1
char* List[MAX_STRS]; // указатели на первые символы строк
И вся работа со строкой будет сводиться к работе с указателем на первый символ строки
Цитата Сообщение от ula Посмотреть сообщение
Он наверное должен быть двумерным?
Да, ярусность получается.
C++
1
char Strs[тут_сколько_строк][сколько_букв_в_одной_строке_максимум];
Однако можно и по другому...

Кроме того обращаться к строке нужно будет так
C++
1
&Strs[i][0] // указатель на первый символ строки
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
02.03.2010, 00:35     Найти первую повторяющуюся строку в массиве строк #7
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <string>
#include <set>  
int main()
{ 
    std::set <std::string> S;
    std::string s, res = "there are no same strings";
    while (std::cin >> s)
        if (S.find(s) == S.end())
            S.insert(s);
        else
        {
            res = s;
            break;
        }
    std::cout << res << std::endl;
    system ("pause");
}
Добавлено через 1 минуту
insideone,
ula, скажите чем вам мой вариант не подходит?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.03.2010, 11:35     Найти первую повторяющуюся строку в массиве строк
Еще ссылки по теме:

C++ Нужно найти строку наибольшей длины и увеличить остальные строк в массиве к длине наибольшей строки, используя символ "!"
Найти количество строк, похожих на первую строку данной матрицы C++
C++ Найти самую повторяющуюся цифру в массиве цифр

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
ula
0 / 0 / 0
Регистрация: 04.12.2009
Сообщений: 26
02.03.2010, 11:35  [ТС]     Найти первую повторяющуюся строку в массиве строк #8
Никаких претензий нет, просто преподаватель сказал выполнять это задание в виде формы:"...задание состоит из целевой функции, т.е. функции, выполняющей задание, указанное в варианте, и теста в виде функции main(). Тестовые аргументы следует передавать в виде аргументов командной строки и/или вводить по приглашению...".
7. Пример выполнения задания
Исходный текст программы с комментариями

C++
1
2
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
// Ind1.cpp : Пример выполнения задания
//
 
#include "stdafx.h"
#include <conio.h>
 
// ----------------------------------------------
// функция подсчета строк, заканчивающихся цифрой,
// в массиве строк
// ----------------------------------------------
int CalcDigitFinish(char *ar[], int sz){
// параметры:
    // ar - массив строк
    // sz - размер этого массива        
    int cd = 0; // переменная счетчик нужных строк
    for (int i=0; i<sz; i++) { // цикл по строкам массива
        char *p=ar[i]; // берём указатель на строку массива
        while (*p) p++; // и угоняем его в конец строки
        if (p!=ar[i]){  // не пуста ли строка?
            char last = *(--p); // взяли последний символ
            if (last>='0' && last <='9')  // проверяем на цифру
                cd++; // увеличиваем счетчик
        }
    }
    return cd; // возвращаем результат
}
 
int _tmain(int argc, _TCHAR* argv[])
{
    // тестовые строки
    char *a[] = {"xcjv", "hsjdfh3", "jsd1", "", "63475", "hjdfh"};
    int sa = 6; // размер массива
    printf ("Arrays to check:\n"); // предисловие к выводу исходных строк
    for (int i=0; i<sa; i++) printf ("%d) %s\n", i+1, a[i]); // выводим строки, которые проверям
    printf("Digit ended lines count = %d\n", CalcDigitFinish(a,sa)); // сразу печатаем результат вызова ф-ции
    _getch();
    return 0;
}
Вывод на консоль
Arrays to check:
1) xcjv
2) hsjdfh3
3) jsd1
4)
5) 63475
6) hjdfh
Digit ended lines count = 3
Yandex
Объявления
02.03.2010, 11:35     Найти первую повторяющуюся строку в массиве строк
Ответ Создать тему
Опции темы

Текущее время: 16:22. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru