Naruszenie ochrony pamięci - sortowanie pozycyjne [C++]

0

Cześć.
Mam zadanie napisać program, który z pliku .txt będzie pobierać spis nazwisk. Następnie przy pomocy algorytmu sortowanie pozycyjne posortuje mi te nazwiska alfabetycznie. Napisałem kod, który powinien to zadanie wykonać, jednak niezależnie od tego ile nazwisk ma do posortowania następuje zrzut pamięci.
Problem ten zawsze występuje podczas 4/5/6 obiegu pętli w radixSort.

Byłbym wdzięczny za pomoc.

#include <iostream>
#include <ctime>
#include <string>
#include <time.h>
#include <cstdlib>
#include <fstream>
#include <cstdio>

using namespace std;

///////////////////////////////////////////////////////////////////////////////////////////////
void countSort(string wyrazy[], int n, int exp, int c) //n - maksymalna ilosc wyrazów,
// m - pozycja literki
{
    string *output = new string[n]; // output array
    int i, count[10] = {0};

    // Store count of occurrences in count[]
    for (i = 0; i < n; i++)
        count[ (((int)wyrazy[i][c])/exp)%10 ]++;

    // Change count[i] so that count[i] now contains actual
    //  position of this digit in output[]
    for (i = 1; i < 10; i++)
        count[i] += count[i - 1];

    // Budowanie tablicy pomocniczej
    for (i = n - 1; i >= 0; i--)
    {
        output[count[ (((int)wyrazy[i][c])/exp)%10 ] - 1] = wyrazy[i];
        count[ ((int)wyrazy[i][c]/exp)%10 ]--;
    }

    //Kopiowanie z tablicy pomocnicznej do głównej
    for (i = 0; i < n; i++)
    {
        wyrazy[i] = output[i];
      }
      cout << "Skonczylem countSort" << "\n";
      delete [] output;
}

void radixSort(string wyrazy[], int n, int c)//c - numer literki według ktorej sortujemy
{
  cout << "Zaczalem radixSort" << "\n";
  int m = 122;//getMax(wyrazy,n,c);     //Bedzie liczyć dla pierwszej literki;


  for (int exp = 1; m/exp > 0; exp *= 10)
  {
      countSort(wyrazy, n, exp, c);
  }
}
///////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////
int main()
{
  int n = 30;        // Wybieramy ile nazwisk z pliku nazwiskaASCII ma zostać posortowanych
  int popularnosc;
  string *wyrazy = new string[n];//ilosc wszystkich wyrazow
  clock_t s1,s2,f1,f2;
  double czas1, czas2 = 0;
  fstream plik;
  plik.open( "nazwiskaASCII.txt", ios::in);
  if( plik.good() == true )
  {
      cout << "Uzyskano dostep do pliku!" << endl;
      for(int i = 0; i < n; i++)
      {
        plik >> popularnosc;
        getline(plik, wyrazy[i],'\n');

     cout << wyrazy[i] << endl;
      }
      plik.close();
      cout << "Skonczylem ladowanie nazwisk" << "\n";
  }
  else cout << "Dostep do pliku zostal zabroniony!" << endl;
///////////////////////////////////////////////////////////////////////////////////////////////
for(int i = 20; i > 0; i--)    //Sortowanie od tyłu nazwisk - RadixSort
{
  radixSort(wyrazy,n,i);
}
cout << "Skonczylem radixsort" << "\n";
///////////////////////////////////////////////////////////////////////////////////////////////
return 0;
delete [] wyrazy;
}

0

Podczas czytania z pliku i zapisywania w tablicy wypisujesz nazwiska. Wypisało Ci wszystkie jak należy?

0

Jak wypisuję całą tablicę to mam wszystkie nazwiska poprawnie. Jedynie przed każdym nazwiskiem mam spację. Ale to raczej nie powinno powodować problemów.

0
  1. Odpal pod valgrindem.
  2. Odpal pod debugerem.
0
for(int i = 20; i > 0; i--)    //Sortowanie od tyłu nazwisk - RadixSort

Założyłeś sobie, że nazwiska składają się z co najmniej 20 liter, czy one faktycznie wszystkie tyle liter mają?

0

Założyłem, że mają tyle liter. Jednak jak stosuję rzutowanie i zdaży się taka sytuacja, że np. nazwisko ma 10 liter, a ja odwołuje się do 19 literki to i tak z rzutowania na int wynosi 0. Zaraz sprawdzę sobie sposobem Shalom'a.

0

Po zbadaniu tych wycieków okazało się, że problem leży właśnie po stronie odwoływania się poza zakres tablicy. Jednak z powodu braku czasu i robienia już innego projektu zmuszony jestem pójść na łatwiznę. Stworzyłem sobie funkcję, która w zadanym przedziale szuka najkrótszego nazwiska. Jednak jak np. mamy nazwiska: Król, Kowalski, Kowalczyk. Źle zostaną posortowane te dwa ostatnie.

Macie może jakiś pomysł jak można by było zmodyfikować kod(może dodać jakąś funkcję), tak aby sortował kod każdej długości nazwisko?
Nie koniecznie chodzi mi o gotowy kod. Może jakieś wskazówki, sugestie.

0

Dodaj spacje do każdego nazwiska, żeby mieć z góry zadaną długość (np. 20).

0

Wystarczyłoby te tablice wyzerować po prostu i wtedy nie będzie problemu pewnie bo będzie na koniec porównywało z 0.

0

Dobra. Taki pomysł na pewno wypali, ale jak sprawdzam funkcją length() np. nazwisko[1].length() to otrzymuję liczbę równą ilości liter danego nazwiska, tak jakby ta tablica stringów dla każdego nazwiska miała inną długość. Czyli, aby mieć każde nazwisko jednej długości to już podczas wgrywania nazwisk do tablicy muszę dopełniać stringa do określonej długości np. 20?

Chodzi mi o to, że przy pierwszej próbie oddania tego programu, prowadzący zarzucił mi, że moja tablica stringów jest jednakowej długości dla każdego nazwiska, tzn. że jak jest 30 nazwisk i najdłuższe nazwisko ma np. 14 liter
to definiowana jest tablica stringów nazwiska[30][14], przez co marnowane by było miejsce na puste znaki. Czy ma on rację?

0
void countSort(string wyrazy[], int n, int exp, int c) //n - maksymalna ilosc wyrazów,
// m - pozycja literki

jakie m?

0

Ktoś zabronił Ci używać std::vectora, czy po prostu lubisz biczować się parówkami? (string wyrazy[], int n)
Używając jakiegoś ludzkiego kontenera masz do dyspozycji metodę .at(), która rzuci wyjątkiem zamiast wybuchnąć wszystko w kosmos - na pewno twoje życie będzie wtedy łatwiejsze, bo zwyczajnie podpatrzysz sobie wszystkie wartości przed rzuceniem wyjątku.

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