алгоритм — куча C ++, вектор & lt; string, int & gt;

Я не могу понять, где у меня проблемы с сортировкой кучи.
Программа берет имя файла из командной строки, импортирует слова в вектор, затем этот вектор превращается в векторную пару vector<string,int> где строка — это слово, а int — это количество экземпляров этого слова в файле.

vector<PAIR> затем сортируется либо по строке (значение или v), либо по int (ключ или k). Моя сортировка по ключу работает нормально, однако сортировка по значению отключена. Я подозреваю, что при сортировке по значению отсутствует оператор if в max_heapify. Вот мой код:

main.cpp

#include <fstream>
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <string>
#include <string.h>
#include <stdio.h>
#include <map>
#include <time.h>
#include "readwords.h"
using namespace std;

readwords wordsinfile;
vector<string> allwords;
bool times;
char *filename;
timespec timestart,timeend;
vector< pair<string,int> > allwords_vp;

timespec diffclock(timespec start, timespec end);

int main ( int argc, char *argv[] ) {

filename = argv[1];

//Lets open the file
ifstream ourfile2(filename);

//Lets get all the words using our requirements
allwords = wordsinfile.getwords(ourfile2);
//Convert all the words from file and count how many times they
//appear.  We will store them in a vector<string,int> string
//being the word and int being how many time the word appeared
allwords_vp = wordsinfile.count_vector(allwords);

cout << "HeapSort by Values" << endl;
if (times) {
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &timestart);
wordsinfile.heapsort(const_cast<char *>("v"));
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &timeend);
cout << "HeapSort by Values ran in "<< diffclock(timestart,timeend).tv_nsec << " nanosecond or "<< diffclock(timestart,timeend).tv_nsec/1000 << " millisecond"<< endl;
} else {
wordsinfile.heapsort(const_cast<char *>("v"));
}

cout << "HeapSort by Keys" << endl;
if (times) {
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &timestart);
wordsinfile.heapsort(const_cast<char *>("k"));
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &timeend);
cout << "HeapSort by Keys ran in "<< diffclock(timestart,timeend).tv_nsec << " nanosecond or "<< diffclock(timestart,timeend).tv_nsec/1000 << " millisecond"<< endl;
} else {
wordsinfile.heapsort(const_cast<char *>("k"));
}
}

timespec diffclock(timespec start, timespec end) {
timespec temp;
if ((end.tv_nsec-start.tv_nsec)<0) {
temp.tv_sec = end.tv_sec-start.tv_sec-1;
temp.tv_nsec = 1000000000+end.tv_nsec-start.tv_nsec;
} else {
temp.tv_sec = end.tv_sec-start.tv_sec;
temp.tv_nsec = end.tv_nsec-start.tv_nsec;
}
return temp;
}

readwords.h

#ifndef READWORDS_H
#define READWORDS_H

#include <vector>
#include <map>
#include <utility>
#include <time.h>

typedef std::pair<std::string, int> PAIR;

bool isasciifile(std::istream& file);

class readwords {
private:
std::vector<PAIR> vp;
public:
std::vector<std::string> getwords(std::istream& file);
std::vector<PAIR> count_vector(std::vector<std::string> sv);
void print_vectorpair(std::vector<PAIR> vp);
void print_vector(std::vector<std::string> sv);
void heapsort(char how[]);
void buildmaxheap(std::vector<PAIR> &vp, int heapsize, char how[]);
void max_heapify(std::vector<PAIR> &vp, int i, int heapsize, char how[]);
void swap_pair(PAIR &p1, PAIR &p2);
};

readwords.cpp

#include <fstream>
#include <iostream>
#include <map>
#include "readwords.h"#include <vector>
#include <string>
#include <utility>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

//using std::vector;
using namespace std;

typedef pair<string, int> PAIR;

// Do we have a ASCII file?
// Lets test the second 10 chars to make sure
// This method is flawed if the file is less than 10 chars
bool isasciifile(std::istream& file) {
int c = 0;
bool foundbin = false;
for(c=0; c < 10;c++) {
if(!isprint(file.get())){
// Looks like we found a non ASCII file, or its empty.
foundbin = true;
}
}
return foundbin;
}

// This is our workhorse as it splits up the words based on our criteria and
// passes them back as a vector of strings.
vector<string> readwords::getwords(std::istream& file) {
char c;
string aword;
vector<string> sv;

//Let go through the file till the end
while(file.good()) {
c = file.get();
if (isalnum(c)) {
//convert any uppercase to lowercase
if(isupper(c)) {
c = (tolower(c));
}
//if its a space lets go onto the next char
if(isspace(c)) { continue; }
//everything looks good lets add the char to our word
aword.insert(aword.end(),c);
} else {
//its not a alphnum or a space so lets skip it
if(!isspace(c)) { continue; }
//reset our string and increment
if (aword != "") {sv.push_back(aword);}
aword = "";
continue;
}
}
return sv;
}

vector<PAIR> readwords::count_vector(vector<string> sv) {
unsigned int i = 0;
int j = 0;
int match = 0;

// cout << "Working with these string: " << endl;
// print_vector(sv);

for (i=0; i < sv.size(); i++) {
// cout << "count of i: " << i << " word is: " << sv.at(i) << endl;

match = 0;
if(readwords::vp.size() == 0) {
readwords::vp.push_back(make_pair(sv.at(i),1)); continue;
}

for (j=readwords::vp.size() - 1; j >= 0; --j) {
if (sv.at(i) == readwords::vp.at(j).first) {
// cout << "Match found with: " << sv.at(i) << endl;;
readwords::vp.at(j).second = readwords::vp.at(j).second + 1;
match = 1;
}

// cout << "Value of j and match: " << j << match << endl;
if ( j == 0 && match == 0) {
// cout << "Match found at end with: " << sv.at(i) << endl;;
readwords::vp.push_back(make_pair(sv.at(i),1));
}
}
}

//Prob need to sort by first data type then second here, prior to sort functions.
//Might not be the best place as the sort functions would alter it, if not here
//then each sort requires to do secondary search

return readwords::vp;
}

void readwords::print_vectorpair(vector<PAIR> vp) {
unsigned int i = 0;

for (i=0; i < vp.size(); ++i) {
cout << vp.at(i).first << " " << vp.at(i).second << endl;
}
}

void readwords::print_vector(vector<string> sv) {
unsigned int i = 0;

for (i=0; i < sv.size(); ++i) {
cout << sv.at(i) << endl;
}
}

void readwords::heapsort(char how[]) {
int heapsize = (readwords::vp.size() - 1);

buildmaxheap(readwords::vp, heapsize, how);

for(int i=(readwords::vp.size() - 1); i >= 0; i--) {
swap(readwords::vp[0],readwords::vp[i]);
heapsize--;
max_heapify(readwords::vp, 0, heapsize, how);
}

print_vectorpair(readwords::vp);
}

void readwords::buildmaxheap(vector<PAIR> &vp, int heapsize, char how[]) {

for(int i=(heapsize/2); i >= 0 ; i--) {
max_heapify(vp, i, heapsize, how);
}
}

void readwords::max_heapify(vector<PAIR> &vp, int i, int heapsize, char how[]) {
int left = ( 2 * i ) + 1;
int right = left + 1;
int largest;

if(!strcmp(how,"v")) {
if(left <= heapsize && vp.at(left).second >= vp.at(i).second ) {
if( vp.at(left).first >= vp.at(i).first ) {
largest = left;
} else {
largest = i;
}
} else {
largest = i;
}

if(right <= heapsize && vp.at(right).second >= vp.at(largest).second) {
if( vp.at(right).first >= vp.at(largest).first) {
largest = right;
}
}
}

if(!strcmp(how,"k")) {
if(left <= heapsize && vp.at(left).first > vp.at(i).first) {
largest = left;
} else {
largest = i;
}

if(right <= heapsize && vp.at(right).first > vp.at(largest).first) {
largest = right;
}
}

if(largest != i) {
swap(vp[i], vp[largest]);
max_heapify(vp, largest, heapsize, how);
}
}

0

Решение

Сортировать vector<pair<string, int> > по значениям, рассмотреть возможность добавления vector<pair<int, string> >

vector<pair<int, string> > v(orignal.size());
for (int i = 0; i < v.size(); ++i) v[i] = make_pair(original[i].second, original[i].first);
sort(v.begin(), v.end());
0

Другие решения

Затем вектор сортируется либо по строке (значение или v), либо по int (ключ или k).

Это описание не соответствует коду, сортировка с how параметр "k" сортирует только по первому компоненту, который является stringи сортировка с "v" как how Параметр учитывает оба компонента.

Я думаю, что это довольно плохая идея, чтобы передать char[] Чтобы определить критерий сортировки, это должна быть функция сравнения, поэтому вам нужна только одна реализация в max_heapify,

Моя сортировка по ключу работает нормально, однако сортировка по значению отключена. Я подозреваю, что при сортировке по значению отсутствует оператор if в max_heapify.

Проблема в том, что сортировка кучи требует полного упорядочения, иначе сортировка не будет выполнена должным образом.

Ваши условия

if(left <= heapsize && vp.at(left).second >= vp.at(i).second ) {
if( vp.at(left).first >= vp.at(i).first ) {
largest = left;
} else {
largest = i;
}
} else {
largest = i;
}

проверить, являются ли оба компонента vp.at(left) (Соотв. right), по крайней мере, такого же размера, как и соответствующий компонент vp.at(i), в результате чего продукт частичный заказ, две общие пары не сопоставимы, и в этом случае ваш max_heapify ничего не делает

Пример для <"a",3>, <"b",2> а также <"c",1> в позициях i, left, rightв любом порядке, ваш max_heapify наборы largest в i,

Если ваша сортировка по "v" предназначен для сортировки на основе int компонент, а в случае галстука возьмите string компонент во внимание, вам нужно было бы различать случаи vp.at(left).second > vp.at(i).second и равенство (для right тоже конечно). Например

if(left <= heapsize && vp.at(left).second >= vp.at(i).second ) {
if(vp.at(left).second > vp.at(i).second || vp.at(left).first >= vp.at(i).first ) {
largest = left;
} else {
largest = i;
}
} else {
largest = i;
}
0

По вопросам рекламы [email protected]