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;
Алгоритм подсчета количества одинаковых строк
Есть ListBox, в котором находятся данные типа:
АА
АА
АА
АА
АБ
АБ
АБ
АВ
АГ
АГ
АД
Необходимо в EditBox вывести данные таким образом:
АА - позиция 0, кол-во 4; АБ - позиция 4, кол-во 3; АВ - позиция 7, кол-во 1; АГ - позиция 8, кол-во 1; АД - позиция 10, кол-во 1
Затруднение вызывает сам алгоритм правильного подсчета, а с выводом проблем нет.
Спасибо.
В твоем примере строки упорядочены. В общем случае как обстоит дело?
Действительно, строки уже отсортированы по алфавиту.
В смысле правильного. Это что бы количество правильно, или на столько правильно что бы было быстро?
Идея такая -
Берется первый элемент и сравнивается с последующим
если совпадают, то счетчик числа одинаковых увеличивается
Далее первый элемент сравнивается с элементом после следующего и т.д.
Если не совпадает, то у первого элемента индекс увеличивается на количество прошлых совпадений
Это образно, может и не так. Если есть возможность подскажите или направьте на путь истинный.
Цитата: avatara
я же конкретно написал "правильного", а не быстрого. У меня получается с ошибкой. Тут вроде просто всего 2 цикла, но голова уже не соображает.
Идея такая -
Берется первый элемент и сравнивается с последующим
если совпадают, то счетчик числа одинаковых увеличивается
Далее первый элемент сравнивается с элементом после следующего и т.д.
Если не совпадает, то у первого элемента индекс увеличивается на количество прошлых совпадений
Это образно, может и не так. Если есть возможность подскажите или направьте на путь истинный.
Идея такая -
Берется первый элемент и сравнивается с последующим
если совпадают, то счетчик числа одинаковых увеличивается
Далее первый элемент сравнивается с элементом после следующего и т.д.
Если не совпадает, то у первого элемента индекс увеличивается на количество прошлых совпадений
Это образно, может и не так. Если есть возможность подскажите или направьте на путь истинный.
А почему 2 цикла?
Код:
Не тестировал, но должно работать ;)
Это надо было, чтобы узнать начальный индекс данной строки и количество.
На самом деле все немного сложнее. В проекте есть 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;
}
{
// Подсчет количества и начала одинаковых записей
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 то часть данных просто изчезает, а вместо них появляются дубликаты имеющихся.
Посмотрите, в чем проблемы. На всякий случай прикрепляю файл с проектом. В папке ДЕБАГ есть текстовые файлики с данными для загрузки.
Задача поставлена не очень корректно, так что ждем-с ответа ;)
Может действительно надо было организовать все по другому
Цитата: 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;
}
#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;
}
http://algolist.manual.ru/sort/quick_sort.php, как по мне - красивое решение ;)
Кстати, вариант реализации сортировки с помощью шаблонов можно найти тут
Спасибо, пока разбираюсь.