int n, // число строк
m; // число элементов в строке
for(i=0; i<n-1; i++)
{
for(j=0; j<m; j++)
{
if(nm[j]==nm[i+1][j])
{
// j элемент i ой строки совпадает с
// j элементом i+1 ой строки
}
}
}
поиск одинаковых строк в матрице [C++]
Здравствуйте,подскажите пожалуйста, каким образом можно сравнить и найти соответствия всех строк в матрице.
Матрица двумерный массив n*m. Сравнить одну строку со следующей получается, т.е посимвольно, делаю так:
Но мне необходимо найти одинаковые строки, и вывести соответственно какие строки и сколько раз совпали.
Подскажите пожалуйста, а то никак не могу сообразить. Заранее спасибо за все советы.
upd:
Теперь проблема в том что, после сравнения первой строки и нахождения всех соответствий ей, когда цикл переходит на следующую строчку, он заново проверяет туже самую строку и говорит что она совпала еще несколько раз.
Как исключить из поиска уже идентичную строку которая уже проверена?
Матрица двумерный массив n*m. Сравнить одну строку со следующей получается, т.е посимвольно, делаю так:
Код:
Но мне необходимо найти одинаковые строки, и вывести соответственно какие строки и сколько раз совпали.
Подскажите пожалуйста, а то никак не могу сообразить. Заранее спасибо за все советы.
upd:
Код:
for(i=0; i<n-1; i++)
{
count=0;
fprintf(out," \n");
for(j=0; j<m; j++)
{
fprintf(out,"%2d",nm[j]);
}
fprintf(out,"-");
for (x=i;x<n-1;x++)
{
key=0;
for(j=0; j<m; j++)
{
if(nm[j]==nm[x+1][j])
{
key=key+1;
if(key==m)
{
hit=true;
fprintf(out, "%d,",x+1);
}
}
}
}
{
count=0;
fprintf(out," \n");
for(j=0; j<m; j++)
{
fprintf(out,"%2d",nm[j]);
}
fprintf(out,"-");
for (x=i;x<n-1;x++)
{
key=0;
for(j=0; j<m; j++)
{
if(nm[j]==nm[x+1][j])
{
key=key+1;
if(key==m)
{
hit=true;
fprintf(out, "%d,",x+1);
}
}
}
}
Теперь проблема в том что, после сравнения первой строки и нахождения всех соответствий ей, когда цикл переходит на следующую строчку, он заново проверяет туже самую строку и говорит что она совпала еще несколько раз.
Как исключить из поиска уже идентичную строку которая уже проверена?
Вариант 1:
Перебрать все пары строк и сравнить.
сложность - O(n*n*m)
Вариант 2:
Определить для строк сравнение (больше / меньше).
Отсортировать строки.
За один проход цикла найти повторяющиеся.
сложность - O(n*m* log n)
Перебрать все пары строк и сравнить.
сложность - O(n*n*m)
Вариант 2:
Определить для строк сравнение (больше / меньше).
Отсортировать строки.
За один проход цикла найти повторяющиеся.
сложность - O(n*m* log n)
Спасибо. Мне бы хотелось сделать так, чтобы бралась первая строка, сравнивалась со всеми остальными строками, потом соответственно должна сравниваться вторая строка с остальными. Не могу написать цикл, которыйбы проходил вначале по всей матрице и срванивал все с первой строкой, потом переходил на вторую строку и опять срванивал со всеми строками матрицы.
если строки типа char* то подойдет ф-я strcmp(char*, char*)
в принципе если и string то тоже подойдет
в принципе если и string то тоже подойдет
матрица из целых чисел int
Операция == проверяет на равенство векторы. Сделай матрицу как вектор векторов,где каждая строка вектор целых чисел и проверяй.Это ж С++ ?
Если я правильно понял, нужно создать класс вектор?
да,с++
А без классов можно реализовать?
да,с++
А без классов можно реализовать?
Цитата: netloger
Если я правильно понял, нужно создать класс вектор?
да,с++
А без классов можно реализовать?
да,с++
А без классов можно реализовать?
Не надо ничего создавать.Вот матрица на основе вектора.Используется контейнер vector.
Код:
#include <iostream>
#include <ctime>
#include <iomanip>
#include <vector>
using namespace std;
typedef vector< vector<int> > T;
ostream &operator<<(ostream &output,const T &mass)
{
for(size_t i = 0;i<mass.size();++i){
for(size_t j = 0;j<mass.size();++j)
output<<setw(5)<<mass[j];
output<<"\n\n";
}
return output;
}
int _tmain(int argc, _TCHAR* argv[])
{
srand((unsigned)time(0));
unsigned int row,col;
do{
cout<<"Enter rows > 0"<<endl;
cin>>row;
}while(row <= 0);
do{
cout<<"Enter col > 0"<<endl;
cin>>col;
}while(col <= 0);
T mass(row, vector<int>(col));
for(size_t i = 0;i < row;++i){
for(size_t j = 0;j < col;++j)
mass[j] = rand()%10;
}
cout<<mass;
return 0;
}
#include <ctime>
#include <iomanip>
#include <vector>
using namespace std;
typedef vector< vector<int> > T;
ostream &operator<<(ostream &output,const T &mass)
{
for(size_t i = 0;i<mass.size();++i){
for(size_t j = 0;j<mass.size();++j)
output<<setw(5)<<mass[j];
output<<"\n\n";
}
return output;
}
int _tmain(int argc, _TCHAR* argv[])
{
srand((unsigned)time(0));
unsigned int row,col;
do{
cout<<"Enter rows > 0"<<endl;
cin>>row;
}while(row <= 0);
do{
cout<<"Enter col > 0"<<endl;
cin>>col;
}while(col <= 0);
T mass(row, vector<int>(col));
for(size_t i = 0;i < row;++i){
for(size_t j = 0;j < col;++j)
mass[j] = rand()%10;
}
cout<<mass;
return 0;
}
Всем спасибо большое за советы, задача решена.
Ну вот.... я ожидал тут короткое решение с использованием STL... У самого получается только что-то типа:
Код:
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;
int main()
{
string s;
vector<string> coll, bufColl;
stringstream os;
int oldSize;
// Ввод строк
cout << "Input strings" << endl;
getline(cin, s, '\n');
os << s;
while(!os.eof()) {
os >> s;
coll.push_back(s);
}
// Сам подсчет строк
cout << "Result:" << endl;
bufColl = coll;
while (bufColl.size())
{
vector<string>::iterator pos;
s = bufColl[0];
oldSize = bufColl.size();
pos = remove(bufColl.begin(), bufColl.end(), s);
bufColl.erase(pos, bufColl.end());
cout << s << " : " << oldSize - bufColl.size() << endl;
}
return 0;
}
#include <sstream>
#include <vector>
using namespace std;
int main()
{
string s;
vector<string> coll, bufColl;
stringstream os;
int oldSize;
// Ввод строк
cout << "Input strings" << endl;
getline(cin, s, '\n');
os << s;
while(!os.eof()) {
os >> s;
coll.push_back(s);
}
// Сам подсчет строк
cout << "Result:" << endl;
bufColl = coll;
while (bufColl.size())
{
vector<string>::iterator pos;
s = bufColl[0];
oldSize = bufColl.size();
pos = remove(bufColl.begin(), bufColl.end(), s);
bufColl.erase(pos, bufColl.end());
cout << s << " : " << oldSize - bufColl.size() << endl;
}
return 0;
}