[C] Sortowanie na wskaźnikach

zakroq · 8 Listopad 2007 17:21

Witajcie

Pisze baze danych z dynamiczną alokacją tablicy etc na wskaźnikach i problem pojawia się przy sortowaniu.

int sortuj_1(struct baza *poczatek)

{

	struct baza *e, *tmp;

	e=poczatek;

	tmp=poczatek;

	e=e->nastepny;

	tmp=(struct baza*) calloc(1,sizeof(struct baza));

	for(e ; e!=NULL ; e=e->nastepny)

	{

	if(strcmp(e->imie,(e+1)->imie)<0)

		{

			memcpy(tmp,e,sizeof(struct baza));

			memcpy(e,(e+1),sizeof(struct baza));

			memcpy((e+1),tmp,sizeof(struct baza));

		}

	e=e->nastepny;

	};

	printf("\n\tDane zostaly posortowane\n");

	free(e);

	return 0;

};

Kompilator to Visual C++ 6.0, system XP, język to nie trudno się domyślić że C

Proszę o pomoc.

Ryan · 8 Listopad 2007 17:32

No ale po co napisać jaki, prawda? :roll:

e=e->nastepny;

Jeśli e jest NULL, to wysypie Ci się program. Nie rozumiem po co cokolwiek alokujesz przy sortowaniu. Wymieniaj wskaźniki i już. Bardzo prymitywny sposób:

OLD: 2 -> 6 -> 1 -> 9 -> 4 -> 7 -> NULL

NEW: NULL


znajdź najmniejszy w OLD i wstaw na koniec NEW

OLD: 2 -> 6 -> 9 -> 4 -> 7 -> NULL

NEW: 1 - > NULL


znajdź najmniejszy w OLD i wstaw na koniec NEW

OLD: 6 -> 9 -> 4 -> 7 -> NULL

NEW: 1 - > 2 -> NULL


itd.

Wypinanie z OLD to

// e->next->value jest najmniejsze

tmp = e->next;

e->next = tmp->next;

Używając ->next sprawdzaj zawsze, czy bazowa struktura nie jest NULL - są to warunki brzegowe, które musisz inaczej obsłużyć.

zakroq · 8 Listopad 2007 18:07

int sortuj_1(struct baza *poczatek)

{

struct baza *e, *f, *tmp;

e=poczatek;

f=poczatek;

tmp=NULL;

e=e->nastepny;

f=f->nastepny;

tmp=(struct baza*) calloc(1,sizeof(struct baza));

/*	for(e ; e!=NULL ; e=e->nastepny)

	{

	for(f ; f!=NULL ; f=f->nastepny)

	{

		if(strcmp(e->imie,f->imie)<0)

		{

		memcpy(tmp,e,sizeof(struct baza));

		memcpy(e,f,sizeof(struct baza));

		memcpy(f,tmp,sizeof(struct baza));

		}

	}

                };

*/	

                while(e!=NULL)

	{

	                 while(f!=NULL)

		{

			if(strcmp(e->imie,f->imie)<0)

			{

			memcpy(tmp,e,sizeof(struct baza));

			memcpy(e,f,sizeof(struct baza));

			memcpy(f,tmp,sizeof(struct baza));

			}

		f=f->nastepny;

		}

	e=e->nastepny;

	}

	};

	printf("\n\tDane zostaly posortowane\n");

	free(e);

	free(f);

	return 0;

};

a cos takiego? Tu są dwa pomysły ale niestety żaden nie działa.

twojego pomysłu nie rozumiem ;-/ sorry, może ciemny jestem.

GL1zdA · 8 Listopad 2007 20:14

Jeśli masz listę w której e->nastepny wskazuje na f, f->nastepny na g i okazuje się ze musisz zamienić miejscami f i g, to nie kopiuj ich zawartości między sobą, tylko każ wskazywać e->nastepny na g, a g->nastepny na f, a f->nastepny na to, na co wskazywało g->nastepny.

zakroq · 8 Listopad 2007 22:29

GL1zdA: ale powiedz mi dlaczego moj kod nie dziala? Przeciez to w sumie powinien byc taki sam efekt. Mam szybki komputer i baze 200osoba powinien obslugiwac mimo wszystko szybko (nie zalezy mi na wydajnosci ale na tym zeby to dzialalo).

GL1zdA · 8 Listopad 2007 22:42

A próbowałeś debugować ten kod? Inicjalizujesz wskaxniki za pomocą NULL? Bo porównania mogą się sypać - VC2005 nie inicjalizuje pamięci zerami tylko czymś w stylu 0xcdcdcdcd i później są problemy. Czemu używasz calloc?? Do pojedynczych obiektów jest malloc.

zakroq · 8 Listopad 2007 22:46

GL1zd4: wyslac Ci caly kod? ja ten program pisalem rok temu i teraz go tylko “upgraduje” bo koles powiedzial ze mozna zeby zaliczyc. Nie wiem czy tak na fragmentach sie polapiesz bo ja zeby ponownie go zrozumiec jakis czas siedzialem (za bardzo nie lubie pisac programow… denerwuje mnie to). Jest zrobione zabezpieczenie ze do funckji sortuj przesylam wskazniki juz bo jakby lista byal pusta to nie uruchomi sie wogole ta fukncja. tmp jest inicjalizowane NULL a do e i f przesylam wlasnie element pierwszy bazy.

GL1zdA · 8 Listopad 2007 22:46

Tu masz kod, który działa. Możesz go dopasować do swoich potrzeb.

#include 

#include 

#include 


#define TRUE 1

#define FALSE 0


//deklaracja structury

typedef struct record Record;


//definicja struktury

struct record {

	char* name;

	Record* next;

};


//Inicjalizuje pamiec dla rekordu

Record* new_Record(){

	Record* new_record = malloc(sizeof(Record));

	new_record->next = NULL;	//bo inaczej jest dziwnie inicjalizowane w Visual Studio

	return new_record;

}


//Zwalnia pamięc po rekordzie. 

//Uwaga - nie zwalnia pamieci po obiektach na które wskazuje Record

void delete_Record(Record* ptr){

	free(ptr);

}


//Porownuje rekordy

int cmp_Record(Record* a, Record* b){

	return strcmp(a->name, b->name);

}


//deklaracje

//sortowanie listy

void sort(Record** head_ptr);


//wyswietlanie listy

void print(Record** head_ptr);


//zwalnianie pamieci po liscie

void free_list(Record** head_ptr);


//main

int main(void){

	//Tworzymy rekordy

	Record *a = new_Record(),

		   *b = new_Record(),

		   *c = new_Record(),

		   *d = new_Record(),

		   *e = new_Record();


	//Deklarujemy wskaznik na glowe

	Record** head_ptr;


	//Ustawiamy tresc

	a->name = "aaa";

	b->name = "bbb";

	d->name = "ddd";

	c->name = "ccc";

	e->name = "eee";


	//Laczymy w liste

	e->next = d;

	d->next = c;

	c->next = b;

	b->next = a;

	a->next = NULL;


	//Wskazujemy glowe

	head_ptr = &e;


	//Wyswietalmy zawartosc przed sortowaniem

	printf("PRZED\n");

	print(head_ptr);


	//Sortowanie

	sort(head_ptr);


	//Wyswietlamy zawartosc po sortowaniu

	printf("PO\n");

	print(head_ptr);


	free_list(head_ptr);


	//Wszystko OK

	return 0;

}


//definicje

void print(Record** head_ptr){

	Record* i = *head_ptr;

	while(i != NULL){

		printf(i->name);

		putchar('\n');

		i = i->next;

	}

}


void sort(Record** head_ptr){

	int end = FALSE;

	Record **i, *tmp;


	while( !end ){

		end = TRUE;

		for( i = head_ptr; (*i)->next != NULL; i = &((*i)->next) ){

 			if( cmp_Record( *i, (*i)->next ) > 0 ){


				//zamiana wskaznikow

				tmp = (*i);

				(*i) = ((*i)->next);

				tmp->next = (*i)->next;

				(*i)->next = tmp;


				//zamienilismy cos miejscami w tej iteracji,

				//wiec w kolejnej moze znow cos znajdziemy

				end = FALSE;

			}

		}

	}


}


void free_list(Record** head_ptr){

	Record* tmp;

	Record* i = *head_ptr;

	do{

		tmp = i;

		i = i->next;

		delete_Record(tmp);

	} while( i != NULL );

}

zakroq · 8 Listopad 2007 22:55

error:

error C2440: ‘initializing’ : cannot convert from ‘void *’ to ‘struct record *’

przy inizjalizacji pamieci dla rekordu.

Pozatym nie chce przerabiac Twojego programu, poprostu chce poznac przyczyne dlaczego tamte fukncje nie dzialaja prawidlowo ;-/

Złączono Posta : 09.11.2007 (Pią) 12:07

GL1zd4: Po zastosowaniu Twojego kodu (troche zmodyfikowanego, nie bawilem sie z Record**) i tak nie dziala…

struct baza 

{

	char imie[20];

	char nazwisko[25];

	char telefon[15];

	struct baza *nastepny, *poprzedni;

} *wsk_osoba;

...


#define TRUE 1 

#define FALSE 0


int sortuj_1(struct baza *poczatek)

{

	struct baza *e, *tmp;

	int end = FALSE;

	tmp=NULL;

	while( !end )

	{ 

		end = TRUE;

		for( e = poczatek; (e->nastepny) != NULL; e = e->nastepny )

		{ 

			if( strcmp(e->imie,(e->nastepny)->imie) > 0 )

			{  

				tmp = e;

				e = e->nastepny; 

				tmp->nastepny = e->nastepny; 

				e->nastepny = tmp;

				end = FALSE; 

			} 

		} 

	} 

printf("\n\tDane zostaly posortowane\n");

free(tmp);

return 0;

};

.....

Przy wywolywaniu tej funckji przesyłam tylko jeden argument:

sortuj_1(element);

Program sie nie wysypuje, kompilator nadal nei zglasza blędu, ale nie sortuje ;-/