Ĺadny brzuch
witam
czy moze ktos mi pokazac sortowanie przez scalanie
na listach.
troche sie zgubilem z tymi listami
z góry dzieki
witam
czy moze ktos mi pokazac sortowanie przez scalanie
na listach.
troche sie zgubilem z tymi listami
z góry dzieki
moze ee mam taka liste
struct lista
{
int liczba;
lista *next;
};
możę jeszcze inaczej mam taki sobie programik i chciałbym zeby zastosować w nim sortowanie przez scalanie
a oto on:
#include <iostream>
#include <stdlib.h>
#include <conio.h>
using namespace std;
struct T
{
int liczba;
T* nast;
T* poprz;
};
int main()
{
int i;
T* pom;
T* poczatek;
T* koniec;
poczatek=NULL; //ustawienie wskaznikow
koniec=NULL;
for (i=1; i<=10; i++)
{
if (poczatek==NULL)
{
poczatek=new T;
poczatek->liczba=i;
poczatek->nast=NULL;
poczatek->poprz=NULL;
koniec=poczatek;
}
else
{
koniec->nast=new T;
koniec->nast->poprz=koniec;
koniec=koniec->nast;
koniec->liczba=i;
}
}
pom=poczatek;
for (i=1; i<=10; i++)
{
cout<<pom->liczba<<endl;
pom=pom->nast;
}
getch ();
return 0;
}
void MergeSort(const int* aTablica, unsigned uRozmiar, unsigned uMinIndex = 0, unsigned uMaxIndex = uRozmiar - 1) { if (uMinIndex >= uMaxIndex) return; unsigned uPunktPodzialu = (uMinIndex + uMaxIndex) / 2; MergeSort (aTablica, uRozmiar, uMinIndex, uPunktPodzialu); MergeSort (aTablica, uRozmiar, uPunktPodzialu + 1, uMaxIndex); unsigned uRozmiarLewej = uPunktPodzialu - uMinIndex + 1; unsigned uRozmiarPrawej = uMaxIndex - uPunktPodzialu; int[] aLewa = new int [uRozmiarLewej + 1]; int[] aPrawa = new int [uRozmiarPrawej + 1]; for (unsigned i = 0; i < uRozmiarLewej; ++i) aLewa[i] = aTablica[uMinIndex + i]; for (unsigned i = 0; i < uRozmiarPrawej; ++i) aPrawa[i] = aTablica[uPunktPodzialu + 1 + i]; aLewa[uRozmiarLewej] = aPrawa[uRozmiarPrawej] = MAX_INT; unsigned i = 0, j = 0; for (unsigned k = uMinIndex; k <= uMaxIndex; ++k) if (aLewa[i] <= aPrawa[j]) { aTablica[k] = aLewa[i]; ++i; } else { aTablica[k] = aPrawa[j]; ++j } delete[] aLewa; delete[] aPrawa; }
Pisałem z głowy ten algorytm więc mogą być błędy. Mam nadzieję że pomogłem :)
dzieki to ja tez mam tylko jak go zastosowac w tym programiku z lista
a domyśl się .. :)
w moim kodzie jest coś takiego jak aLewa i aPrawa. Wystarczy pokombinować:]
heh, a mi sie wydaje, ze Twoj kod sie nie przyda :P przede wszystkim, to co na tablicach robione jest w czasie stalym na listach zajmuje czas liniowy, wiec ten algorytm bedzie mial wieksza zlozonosc niz merge sort
no to jak to zrobic bo mi juz dym uszami idzie
double b[N]; void merge(int n,int k,double t[], double b[]) { int i=0,j=k,l=0; while (i<k && j<n) {if(t[i]<t[j]) b[l++]=t[i++]; else b[l++]=t[j++]; } while(i<k) b[l++]=t[i++]; for(i=0;i<j;i++) t[i]=b[i]; } void merge_sort(int n, double t[]) {if(n>1) {int k=n/2; merge_sort(k,t); merge_sort(n-k,t+k); merge(n,k,t,b); } }
fakt można krócej ... :)
dzieki za pomoc tylko dalej niewiem jak mam to skleic do kupy :-(,
Po pierwsze nie napisze ci całego zadania (musisz sam dojść ;)).
Podpowiedziałem ci tylko na co masz zwracać w moim algorytmie.
I jak będziesz stosował metodę prób i błędów to ci wyjdzie.
no tak tylko o sam algorytm na to sortowanie to najmniejszy kłopot .
moj problem to jak wrzucić ta liste do tego sortowania.
lista to troche co innego niż tablica i tu mam error.
hmmmm............
a moze zrobic tablice obiektow tej struktury
np lista tablic[10];
i oprzeć działanie sortowania na tej tablicy?????
Użytkownik wolferin edytował ten post 23 maj 2005, 21:51
zanotowane.pl doc.pisz.pl pdf.pisz.pl zsf.htw.pl
czy moze ktos mi pokazac sortowanie przez scalanie
na listach.
troche sie zgubilem z tymi listami
z góry dzieki
witam
czy moze ktos mi pokazac sortowanie przez scalanie
na listach.
troche sie zgubilem z tymi listami
z góry dzieki
moze ee mam taka liste
struct lista
{
int liczba;
lista *next;
};
możę jeszcze inaczej mam taki sobie programik i chciałbym zeby zastosować w nim sortowanie przez scalanie
a oto on:
#include <iostream>
#include <stdlib.h>
#include <conio.h>
using namespace std;
struct T
{
int liczba;
T* nast;
T* poprz;
};
int main()
{
int i;
T* pom;
T* poczatek;
T* koniec;
poczatek=NULL; //ustawienie wskaznikow
koniec=NULL;
for (i=1; i<=10; i++)
{
if (poczatek==NULL)
{
poczatek=new T;
poczatek->liczba=i;
poczatek->nast=NULL;
poczatek->poprz=NULL;
koniec=poczatek;
}
else
{
koniec->nast=new T;
koniec->nast->poprz=koniec;
koniec=koniec->nast;
koniec->liczba=i;
}
}
pom=poczatek;
for (i=1; i<=10; i++)
{
cout<<pom->liczba<<endl;
pom=pom->nast;
}
getch ();
return 0;
}
void MergeSort(const int* aTablica, unsigned uRozmiar, unsigned uMinIndex = 0, unsigned uMaxIndex = uRozmiar - 1) { if (uMinIndex >= uMaxIndex) return; unsigned uPunktPodzialu = (uMinIndex + uMaxIndex) / 2; MergeSort (aTablica, uRozmiar, uMinIndex, uPunktPodzialu); MergeSort (aTablica, uRozmiar, uPunktPodzialu + 1, uMaxIndex); unsigned uRozmiarLewej = uPunktPodzialu - uMinIndex + 1; unsigned uRozmiarPrawej = uMaxIndex - uPunktPodzialu; int[] aLewa = new int [uRozmiarLewej + 1]; int[] aPrawa = new int [uRozmiarPrawej + 1]; for (unsigned i = 0; i < uRozmiarLewej; ++i) aLewa[i] = aTablica[uMinIndex + i]; for (unsigned i = 0; i < uRozmiarPrawej; ++i) aPrawa[i] = aTablica[uPunktPodzialu + 1 + i]; aLewa[uRozmiarLewej] = aPrawa[uRozmiarPrawej] = MAX_INT; unsigned i = 0, j = 0; for (unsigned k = uMinIndex; k <= uMaxIndex; ++k) if (aLewa[i] <= aPrawa[j]) { aTablica[k] = aLewa[i]; ++i; } else { aTablica[k] = aPrawa[j]; ++j } delete[] aLewa; delete[] aPrawa; }
Pisałem z głowy ten algorytm więc mogą być błędy. Mam nadzieję że pomogłem :)
dzieki to ja tez mam tylko jak go zastosowac w tym programiku z lista
a domyśl się .. :)
w moim kodzie jest coś takiego jak aLewa i aPrawa. Wystarczy pokombinować:]
heh, a mi sie wydaje, ze Twoj kod sie nie przyda :P przede wszystkim, to co na tablicach robione jest w czasie stalym na listach zajmuje czas liniowy, wiec ten algorytm bedzie mial wieksza zlozonosc niz merge sort
no to jak to zrobic bo mi juz dym uszami idzie
double b[N]; void merge(int n,int k,double t[], double b[]) { int i=0,j=k,l=0; while (i<k && j<n) {if(t[i]<t[j]) b[l++]=t[i++]; else b[l++]=t[j++]; } while(i<k) b[l++]=t[i++]; for(i=0;i<j;i++) t[i]=b[i]; } void merge_sort(int n, double t[]) {if(n>1) {int k=n/2; merge_sort(k,t); merge_sort(n-k,t+k); merge(n,k,t,b); } }
fakt można krócej ... :)
dzieki za pomoc tylko dalej niewiem jak mam to skleic do kupy :-(,
Po pierwsze nie napisze ci całego zadania (musisz sam dojść ;)).
Podpowiedziałem ci tylko na co masz zwracać w moim algorytmie.
I jak będziesz stosował metodę prób i błędów to ci wyjdzie.
no tak tylko o sam algorytm na to sortowanie to najmniejszy kłopot .
moj problem to jak wrzucić ta liste do tego sortowania.
lista to troche co innego niż tablica i tu mam error.
hmmmm............
a moze zrobic tablice obiektow tej struktury
np lista tablic[10];
i oprzeć działanie sortowania na tej tablicy?????
Użytkownik wolferin edytował ten post 23 maj 2005, 21:51