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

Ваш аккаунт

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

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

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

Алгоритм подсчета количества одинаковых строк

435
14 ноября 2007 года
avatara
188 / / 07.07.2003
Необходим Алгоритм подсчета количества одинаковых строк и определения начальной позиции данной строки в списке.
Есть ListBox, в котором находятся данные типа:
АА
АА
АА
АА
АБ
АБ
АБ
АВ
АГ
АГ
АД

Необходимо в EditBox вывести данные таким образом:
АА - позиция 0, кол-во 4; АБ - позиция 4, кол-во 3; АВ - позиция 7, кол-во 1; АГ - позиция 8, кол-во 1; АД - позиция 10, кол-во 1

Затруднение вызывает сам алгоритм правильного подсчета, а с выводом проблем нет.
Спасибо.
13K
14 ноября 2007 года
specter
113 / / 28.09.2007
В твоем примере строки упорядочены. В общем случае как обстоит дело?
435
14 ноября 2007 года
avatara
188 / / 07.07.2003
Действительно, строки уже отсортированы по алфавиту.
538
14 ноября 2007 года
AVDEY
188 / / 17.11.2005
"Затруднение вызывает сам алгоритм правильного подсчета, а с выводом проблем нет."
В смысле правильного. Это что бы количество правильно, или на столько правильно что бы было быстро?
435
14 ноября 2007 года
avatara
188 / / 07.07.2003
я же конкретно написал "правильного", а не быстрого. У меня получается с ошибкой. Тут вроде просто всего 2 цикла, но голова уже не соображает.
Идея такая -
Берется первый элемент и сравнивается с последующим
если совпадают, то счетчик числа одинаковых увеличивается
Далее первый элемент сравнивается с элементом после следующего и т.д.
Если не совпадает, то у первого элемента индекс увеличивается на количество прошлых совпадений
Это образно, может и не так. Если есть возможность подскажите или направьте на путь истинный.
13K
15 ноября 2007 года
specter
113 / / 28.09.2007
Цитата: avatara
я же конкретно написал "правильного", а не быстрого. У меня получается с ошибкой. Тут вроде просто всего 2 цикла, но голова уже не соображает.
Идея такая -
Берется первый элемент и сравнивается с последующим
если совпадают, то счетчик числа одинаковых увеличивается
Далее первый элемент сравнивается с элементом после следующего и т.д.
Если не совпадает, то у первого элемента индекс увеличивается на количество прошлых совпадений
Это образно, может и не так. Если есть возможность подскажите или направьте на путь истинный.


А почему 2 цикла?

Код:
int count = 1;
int pos = 0;
for (int i = 1; i < N; ++i)
{
    if (list == list[pos])
        count++;
    else
    {
        std::cout<<"string = "<<list[pos]<<"; pos = "<<pos<<"; count = "<<count<<std::endl;
        pos = i;
        count = 1;
    }
}
std::cout<<"string = "<<list[pos]<<"; pos = "<<pos<<"; count = "<<count<<std::endl;

Не тестировал, но должно работать ;)
435
15 ноября 2007 года
avatara
188 / / 07.07.2003
Предложенный Вами метод Работает правильно
Это надо было, чтобы узнать начальный индекс данной строки и количество.
На самом деле все немного сложнее. В проекте есть ListCtrl, в котором 2 столбца - Серия и Номер
например
ЖХ 222222
ЖЦ 222223
ЖЦ 333333
ЖЦ 222221
ЖЦ 444440
ЖЦ 344444
ЖЦ 322222
ЖЦ 311111
ЖЧ 332222
ЖЧ 355555
ЖЧ 111111
ЖЧ 355555
ЖЧ 322221
ЖЧ 355555
ЖЧ 355554
ЖЧ 355553
ЖЧ 366666
ЖЧ 366667
ЖЧ 366669
ЖЧ 366668
ЖЧ 300000
ЖЧ 363910
ХЩ 295363
в первом столбце данные уже отсортированы по алфавиту, и нужно отсортировать данные во втором столбце соответственно внутри СЕРИИ
Вот две функции

Код:
void CNewMarkDlg::OnBnClickedButton2()
{
    // Подсчет количества и начала одинаковых записей
    int kol;
    kol = m_list.GetItemCount();
    CString Seria, num, Sstart;
    int count = 1;
    int pos = 0;
    for (int i = 1; i < kol; ++i)
    {
        if (m_list.GetItemText(i, 0) == m_list.GetItemText(pos, 0))
            count++;
        else
        {
            //Seria = m_list.GetItemText(pos, 0);
            //num.Format("%i", count);
            //Sstart.Format("%i", pos);
           
            PuzirikSort(pos, count); // если вместо рos и count указывать числа, то все нормально работает
            //m_str = m_str + Seria + ' ' + "поз - " + Sstart + ' ' + "кол-во - " + num;
            pos = i;
            count = 1;
        }
    }
    UpdateData(FALSE);
}
// Сортировка методом пузырька
void CNewMarkDlg::PuzirikSort(int StartIndex, int Size)
{
    int *ListAr;
    ListAr = new int[Size];
    for (int i = 0; i < Size; i++)
    {
        ListAr = StrToInt(m_list.GetItemText(i, 1));
    }
    int temp;
    for (int pass = 1; pass < Size; pass++)
    {
        for (int j = 0; j < Size - 1; j++)
        {
            if (ListAr[j] > ListAr[j+1])
            {
                temp = ListAr[j];
                ListAr[j] = ListAr[j + 1];
                ListAr[j + 1] = temp;
            }
        }
    }
    CString strmass, element;
    for (i = 0; i < Size; i++)
    {
        strmass.Format("%i", ListAr);
        m_list.SetItemText(StartIndex + i, 1, strmass);
    }
    delete []ListAr;

}

Сама функция сортировки PuzirikSort работает правильно, если указывать числовые значения в ее параметрах, а если использовать переменные pos и count то часть данных просто изчезает, а вместо них появляются дубликаты имеющихся.
Посмотрите, в чем проблемы. На всякий случай прикрепляю файл с проектом. В папке ДЕБАГ есть текстовые файлики с данными для загрузки.
13K
15 ноября 2007 года
specter
113 / / 28.09.2007
avatara, столбцы всегда разделены одним пробелом? Если да - то первая часть задачи вообще не нужна. Можно сразу сортировать строки и получить правильный результат... я бы посоветовал быструю сортировку, так как первый столбец уже упоряочен, следовательно перестановок будет минимум.

Задача поставлена не очень корректно, так что ждем-с ответа ;)
435
15 ноября 2007 года
avatara
188 / / 07.07.2003
Столбцы в текстовом файле разделены символом табуляции. В самом ЛИСТКоНТРОЛе находятся 2 столбца. При загрузке данных из файла Серии попадают в первый столбец, а Номера во второй. Серии уже отсортированы по алфавиту. Номера в серии также должны быть отсортированы по возрастанию (что и пытаюсь сделать).
Может действительно надо было организовать все по другому
13K
15 ноября 2007 года
specter
113 / / 28.09.2007
Цитата: avatara
Столбцы в текстовом файле разделены символом табуляции. В самом ЛИСТКоНТРОЛе находятся 2 столбца. При загрузке данных из файла Серии попадают в первый столбец, а Номера во второй. Серии уже отсортированы по алфавиту. Номера в серии также должны быть отсортированы по возрастанию (что и пытаюсь сделать).
Может действительно надо было организовать все по другому


Вот пример решения ;)

Код:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <iostream>

void quickSort(std::string * a, long N)
{
    // На входе - массив a[], a[N] - его последний элемент.

    long i = 0, j = N;      // поставить указатели на исходные места
    std::string temp, p;

    p = a[ N>>1 ];      // центральный элемент

    // процедура разделения
    do {
        while ( a < p ) i++;
        while ( a[j] > p ) j--;

        if (i <= j)
        {
            temp = a;
            a = a[j];
            a[j] = temp;
            i++; j--;
        }
    } while ( i<=j );


    // рекурсивные вызовы, если есть, что сортировать
    if ( j > 0 ) quickSort(a, j);
    if ( N > i ) quickSort(a+i, N-i);
}

void main()
{
    std::string list[] =
    {
        "ЖХ 222222",
        "ЖЦ 222223",
        "ЖЦ 333333",
        "ЖЦ 222221",
        "ЖЦ 444440",
        "ЖЦ 344444",
        "ЖЦ 322222",
        "ЖЦ 311111",
        "ЖЧ 332222",
        "ЖЧ 355555",
        "ЖЧ 111111",
        "ЖЧ 355555",
        "ЖЧ 322221",
        "ЖЧ 355555",
        "ЖЧ 355554",
        "ЖЧ 355553",
        "ЖЧ 366666",
        "ЖЧ 366667",
        "ЖЧ 366669",
        "ЖЧ 366668",
        "ЖЧ 300000",
        "ЖЧ 363910",
        "ХЩ 295363" };

    int size = 23;
   
    for (int i = 0; i<size; i++)
        std::cout << list << "\n";


    std::cout << "\n\n\n\n";

    quickSort(list, size-1);

    for (int i = 0; i<size; i++)
        std::cout << list << "\n";

    system("PAUSE");
    return;
}
13K
15 ноября 2007 года
specter
113 / / 28.09.2007
Кстати, вариант реализации сортировки с помощью шаблонов можно найти тут http://algolist.manual.ru/sort/quick_sort.php, как по мне - красивое решение ;)
435
16 ноября 2007 года
avatara
188 / / 07.07.2003
Спасибо, пока разбираюсь.
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог