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

Odpowiedz Nowy wątek
2017-01-04 19:20
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;
}
edytowany 2x, ostatnio: hauleth, 2017-01-04 21:06

Pozostało 580 znaków

2017-01-04 19:34
0

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

Pozostało 580 znaków

2017-01-04 20:25
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.

edytowany 1x, ostatnio: milekb, 2017-01-04 20:26

Pozostało 580 znaków

2017-01-05 01:24
0
  1. Odpal pod valgrindem.
  2. Odpal pod debugerem.

Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2017-01-05 09:42
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ą?

Pozostało 580 znaków

2017-01-06 17:36
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.

Każde odwołanie poza zakres tablicy to UB. Jeśli zwraca zero, to tylko w pewnych specyficznych okolicznościach - generalnie nie bierz UB za pewnik. - Patryk27 2017-01-06 17:38

Pozostało 580 znaków

2017-01-06 19:35
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.

Pozostało 580 znaków

2017-01-06 19:40
0

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

Pozostało 580 znaków

2017-01-06 19:56
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.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2017-01-06 21:03
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ę?

Pozostało 580 znaków

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

jakie m?

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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