C++ : liczenie powtórzeń w tablicy

0

Witam, mam problem z funkcją ( a właściwie z pętlą) zliczająca ilość powtórzeń w tablicy. Kod:
int duplikaty=0;
for(int i=0; i<rozmiar;++i){
for(int j=0;j<rozmiar; ++j){
if((tab[i]==tab[j]) && tab[i]!="0")* && tab[j]!="0" ) *unikniecie porownania dwoch zer
tab[i]="0"; //zastapienie duplikatu zerem
}
if(tab[i]=="0") duplikaty++;}

    cout<<endl<<"Wystepuje "<<duplikaty<<" duplikatow"<<endl;

Funkcja źle zlicza duplikaty,np. gdy występuję jeden, funkcja zliczyła 10. Jakby co to jest to dynamiczna tablica stringów.
Wie ktoś z Was może, gdzie jest błąd?
Z góry dziękuję.

1
  1. Popraw wcięcia: http://format.krzaq.cc/
  2. Wstaw kod między <code class="cpp"></code>
  3. Podaj dane wejściowe, dla których masz zły wynik.
2
#include <iostream>
#include <unordered_map>
#include <algorithm>
using namespace std;

int main() {
    int tab[] = {1, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 10, 10, 10, 10 };
    unordered_map<int, size_t> map;

    for(auto num : tab)
        map[num] += 1;
	
    for(const auto &pair : map)
        cout << pair.first << ": " << pair.second << endl;
    return 0;
}
0
for (int i = 0; i < rozmiar; ++i) {
    for (int j = 0; j < rozmiar; ++j) {
        if ((tab[i] == tab[j]) && tab[i] != "0") // && tab[j]!="0" )
            tab[i] = "0";
    }
    if (tab[i] == "0")
        duplikaty++;
}

Gdy w tablicy znajdują się wyrazy przykładowo: Anna, Anna, Maria, Maria,Maria, Anna, Anna efektem działania funkcji powinno być :
"duplikaty = 5 " (Anna,Maria,Maria,Anna,Anna), tymczasem program wyświetla "duplikaty= 10".

@spartanPAGE dzięki za pomoc, ale nie mogę używać map ani algorithm.

1

Bo liczysz również dla przypadku i == j.

0

Trochę pomogło :), ale nie do końca. Teraz wyświetla mi zawsze o jeden więcej, niż powinno. Pewnie jakiś głupi błąd, jednak ja go nie widzę.
tak czy inaczej dzięki @twonek.

Jednak potrzebuję jeszcze Waszej pomocy. Moja próba usunięcia powtórzeń polega na przepisaniu niepowtarzających się wyrazów do nowej tablicy, jednak program najpierw wywala krzaki,a potem się sypie, gdy chce wyświetlić elementy tej nowej tablicy.

Kod:

for (int i = 0; i < rozmiar; ++i) {
    for (int j = 0; j < rozmiar; ++j) {
        if ((tab[i] == tab[j]) && tab[i] != "0" && i != j) // && tab[j]!="0" )
            tab[i] = "0";
    }
    if (tab[i] == "0")
        ++duplikaty;
}

cout << endl << "Wystepuje " << rozmiar - duplikaty - 1 << " duplikatow" << endl;
string* tab2 = new string[duplikaty - 1]; //-duplikaty]

int j = 0;
for (int i = 0; i < rozmiar; ++i) {

    if (tab[i] != "0") {
        tab2[j] = tab[i];
        ++j;
    }
}
for (int k = 0; k < (duplikaty - 1); ++k)
    cout << "\t" << tab2[k];
rozmiar = duplikaty - 1;
delete[] tab2;
tab = tab2;

0

Odejmij 1 od wyniku i po sprawie :D

0

Odpal debuggera albo wyświetl sobie zmienne i i j w pętli to będziesz wiedział co jest kopiowane z którego miejsca na które.

0

Kopiowanie jest dobrze, chodzi o wyświetlanie. Program wyświetla krzaki zamiast stringów. Może gdzieś wychodzę poza zakres pamięci? Nie potrafię zlokalizować tego błędu.

0

Gdybyś zrobił tak jak sugerowałem, to byś odkrył np. że tworzysz tablicę na duplikaty-1 elementów, podczas gdy chcesz tam kopiować nie duplikaty tylko te pozostałe.

1

Z uwag dodałbym, że niepotrzebnie druga pętla liczy od 0, dodatkowo niepotrzebnie sprawdzane sa porownania, jesli w pierwszej petli trafimy na pusty element i nie potoba mi sie sposob zaznaczenia pustego elementu.

ponadto kuriozum:

delete[] tab2;
tab = tab2;
0

@kaczus Zaznaczanie pustego elementu jest tylko przykładowe, najłatwiej było mi wpisać 0. Jak to niepotrzebnie sprawdzane są porównania? Przecież muszę wiedzieć, który element skopiować. I o co chodzi z tym liczeniem od zera?

Miałobyc oczywiście

delete []tab;

Po tej poprawce działanie programu jest znośne, choć nie idealne. Ja na dziś daję sobie ( i przede wszystkim Wam ) spokój, wielkie dzięi za pomoc :)

0

chodzi o pętle wewnętrzną - niepotrzebnie porównujesz od 0, przeciez juz porównywałeś raz te wyrazy - porownuj nastepne, wtedy zabezpieczenie

i!= j

nie bedzie potrzebne.

1

A tak naprawdę to jest powód dlaczego ,,kopiesz się z koniem" aby implementować to na piechotę? W projekcie nie możesz użyć biblioteki standardowej?

Napisanie ,,szkolnie" tak aby zrozumieć...

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <string>

using namespace std;

static string wordTable[] = { "Anna", "Anna", "Maria", "Maria", "Maria", "Anna", "Anna" };

static unordered_map<string, int> wordMap;

using wordMap_t = decltype(wordMap)::value_type;

struct DuplicateCounter {
    static int sum;
    void operator()(const wordMap_t& pr) {
        sum += pr.second > 1 ? pr.second - 1 : 0;
    }
} duplicateCounter;

int DuplicateCounter::sum = 0;

int main(void) {
    for(const auto & word : wordTable) {
        wordMap[word] += 1;
    }
    for_each(wordMap.begin(), wordMap.end(), duplicateCounter);
    cout << "Duplicates = " << duplicateCounter.sum << endl;
}

Albo jeszcze szybciej lambdą:

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <string>

using namespace std;

static string wordTable[] = { "Anna", "Anna", "Maria", "Maria", "Maria", "Anna", "Anna" };

static unordered_map<string, int> wordMap;

using wordMap_t = decltype(wordMap)::value_type;

int main(void) {
    int duplicates = 0;

    for(const auto & word : wordTable) {
        wordMap[word] += 1;
    }

    auto duplicateCounter = [&](const wordMap_t& pr) {                                                     
        duplicates += pr.second > 1 ? pr.second - 1 : 0;                                                                     
    }; 

    for_each(wordMap.begin(), wordMap.end(), duplicateCounter);
    cout << "Duplicates = " << duplicates << endl;
}
0

Pewnie dlatego - bo takie zadanie dostał - i dobrze - zanim zacznie się korzystać z gotowców, dobrze poznać zasady ich działania. Tak samo jak implementuje się na piechotę w ramach zadań treningowych metody sortowania. W szkole na matematyce liczysz gdzie spotkają się pociągi, jak i tak wiadomo, że wg rozkładu w innym miejscu, a z doświadczenia jeszcze gdzie indziej. Ale potrzebujesz pewnych teoretycznych ćwiczeń, by później tą umiejętność wykorzystać w innym miejscu.

0

Kolego, może najpierw powiedz czego/jakich konstrukcji wolno Ci użyć. Bo to co robisz (pisanie po tablicach, zabawa indeksami itp), to techniki w C++ błędogenne i wołające o pomstę (oczywiście jestem daleki od jakichkolwiek wycieczek osobistych). Takie niskopoziomowe podejście" stosujesz tylko na platformach wbudowanych. A i tam stosuje się szablony żeby nie schodzić do poziomu Cy (surowego). Tu widzę że możesz użyć cout. Czegoś jeszcze możesz użyć? vector? stack? Czy niczego" i prawie surowe Cy?

1

@Mokrowski Wielkie dzięki za kod, pewnie jak już ogarnę to będę robić w ten właśnie sposób.
Źle się wyraziłem, nie chodzi o to,że NIE MOGĘ używać map, tylko bardziej nie chcę, gdyż jak wspomniał @kaczus chce się nauczyć działania różnych funkcji od podstaw, a wiadomo,że najlepiej zrobić to poprzez samodzielną implementację. Planuję napisać to na tak niskim poziomie, jak się da (może nie w asemblerze ), a potem ulepszać program. Używam

 new , cout , cin 

itd.,bo mniej z nimi zamieszania niż z malloc , printf , scanf

, no i pisze się dużo szybciej.

A tak w ogóle to nie jest program na zaliczenie, robię to dla siebie :)
0

Ok. Nawet udało się szybciej :-)
Tu masz naiwne podejście do problemu. Jak je zmienisz na struktury niskopoziomowe, to będziesz miał okazję zapoznać się z różnymi podejściami. Wystarczy teraz zastąpić vector<string>, tablicą string'ów. Tak jak napisałem, jak będziesz jeszcze chciał zastąpić string przez char *, to będziesz już miał baaardzo niskopoziomowo :-)
Tylko w jednym miejscu użyta składnia z C++11. Przy inicjalizacji wordVector.

#include <iostream>
#include <string>
#include <vector>

// Uwaga: Podejście naiwne, ze strukturami global i wyszukiwaniem liniowym ale trzeba od czegoś
// zacząć :-)

using namespace std;

// vector z napisami... Tu jest składnia z C++11 ale z łatwością zamienisz na tablicę :-)
static vector<string> wordVector { "Anna", "Anna", "Maria", "Maria", "Maria", "Anna", "Anna" };

// vector z unikalnymi słowami
static vector<string> uniqueVector;

// Dodawanie słowa do uniqueVector jeśli go w nim nie ma
static void addUniqueWord(const string& word);

// Prezentacja vector
static void showVector(const vector<string>& vec);

int main(void) {

    // Lepiej na iteratorach, ale tu zachowawczo tak jak w ,,starym dobrym" C++ 98 :-)
    for(unsigned i = 0; i < wordVector.size(); ++i) {
        addUniqueWord(wordVector[i]);
    }

    // Ilość duplikatów to różnica między wielkością wektora z danymi i słów unikalnych
    unsigned duplication = wordVector.size() - uniqueVector.size();
    cout << "Duplication = " << duplication << endl;

    cout << "\nwordVector\n------------" << endl;
    showVector(wordVector);
    cout << "\nuniqueVector\n------------" << endl;
    showVector(uniqueVector);
}

// Implementacja dodawania słowa do uniqueVector jeśli go w nim nie ma
static void addUniqueWord(const string& word) {
    // Wyszukiwanie liniowe słowa w wektorze
    for(unsigned i = 0; i < uniqueVector.size(); ++i) {
        if(uniqueVector[i] == word) {
            // Słowo jest w wektorze uniqueVector
            return;
        }
    }

    // Słowa nie ma w wektorze uniqueVector, dodajemy je
    uniqueVector.push_back(word);
}

// Implementacja prezentacji wektora
static void showVector(const vector<string>& vec) {
    for(unsigned i = 0; i < vec.size(); ++i) {
        cout << i << ": " << vec[i] << " ";
    }
    cout << endl;
}
2
Mokrowski napisał(a):

A tak naprawdę to jest powód dlaczego ,,kopiesz się z koniem" aby implementować to na piechotę? W projekcie nie możesz użyć biblioteki standardowej?

Napisanie ,,szkolnie" tak aby zrozumieć...

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <string>

using namespace std;

static string wordTable[] = { "Anna", "Anna", "Maria", "Maria", "Maria", "Anna", "Anna" };

static unordered_map<string, int> wordMap;

using wordMap_t = decltype(wordMap)::value_type;

struct DuplicateCounter {
    static int sum;
    void operator()(const wordMap_t& pr) {
        sum += pr.second > 1 ? pr.second : 0;
    }
} duplicateCounter;

int DuplicateCounter::sum = 0;

int main(void) {
    for(const auto & word : wordTable) {
        wordMap[word] += 1;
    }
    for_each(wordMap.begin(), wordMap.end(), duplicateCounter);
    cout << "Duplicates = " << duplicateCounter.sum << endl;
}

Albo jeszcze szybciej lambdą:

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <string>

using namespace std;

static string wordTable[] = { "Anna", "Anna", "Maria", "Maria", "Maria", "Anna", "Anna" };

static unordered_map<string, int> wordMap;

using wordMap_t = decltype(wordMap)::value_type;

int main(void) {
    int duplicates = 0;

    for(const auto & word : wordTable) {
        wordMap[word] += 1;
    }

    auto duplicateCounter = [&](const wordMap_t& pr) {                                                     
        duplicates += pr.second > 1 ? pr.second : 0;                                                                     
    }; 

    for_each(wordMap.begin(), wordMap.end(), duplicateCounter);
    cout << "Duplicates = " << duplicates << endl;
}

: DDDDD
Przede wszystkim ten kod nie robi tego co miał robić - nie liczy liczby duplikatów, tylko liczy... liczbę elementów w tablicy. No muszę przyznać, że to chyba najbardziej zawiłe zliczanie elementów kolekcji jakie w życiu widziałem. No nieźle, nieźle ; ]

Błąd masz w tym miejscu:

auto duplicateCounter = [&](const wordMap_t& pr) {                                                     
  duplicates += pr.second > 1 ? pr.second : 0;                                                                     
}; 

Jeśli już to powinno być tak:

auto duplicateCounter = [&](const wordMap_t& pr) {                                                     
  duplicates += pr.second > 1 ? pr.second - 1 : 0;                                                                     
}; 

Ad vocem tematu, można jeszcze tak ; >

std::string vec[] = { "Anna", "Anna", "Maria", "Maria", "Maria", "Anna", "Anna" };
std::cout << boost::size(vec) - boost::size(boost::unique(boost::sort(vec)));

Btw, chciałem to napisać w range-v3 (czyli range dla c++17) ale z tego co widzę Eric Niebler nie zaimplementował size : < (jest size ; p) (będzie za to syntax bind z Haskella : D ).

1 użytkowników online, w tym zalogowanych: 0, gości: 1