[C] Sortowanie listy dwukierunkowej

Przytoczony tutaj algorytm jest jednym ze sposób jakie stosuje się w celu posortowania listy dwukierunkowej według danych. W naszym przypadku będzie wykonywane sortowanie według pola imię. Struktura, na której będziemy bazować wygląda następująco:

//Struktura z danymi studenta
typedef struct DANE
{
	char* imie;
	char* nazwisko;
}Dane;

//Struktura z listą dwukierunkową
typedef struct STUDENT Student;
struct STUDENT
{
	Dane dane;
	Student* next;
	Student* prev;
};     

Pierwsza struktura składa się z pola imie oraz nazwisko, które są łańcuchami znaków. Natomiast struktura reprezentująca listę posiada pole z danymi ucznia, pole next(następny), które odnosi się do następnego elementu oraz pole prev(poprzedni), który odnosi się do poprzedniego elementu.

void sortowanie_listy(Student **head)
{
	Student *nowa = NULL, *tmp, *pom;

	while (*head != NULL)
	{
		tmp = (Student*)malloc(sizeof(Student));
		tmp->dane.imie = (char*)malloc(sizeof(char)* strlen((*head)->dane.imie) + 1);
		strcpy(tmp->dane.imie, (*head)->dane.imie);
		tmp->dane.nazwisko = (char*)malloc(sizeof(char)* strlen((*head)->dane.nazwisko) + 1);
		strcpy(tmp->dane.nazwisko, (*head)->dane.nazwisko);
		tmp->next = NULL;
		tmp->prev = NULL;
		if (nowa == NULL)
			nowa = tmp;
		else if (strcmp(nowa->dane.imie, tmp->dane.imie) > 0)
		{
			tmp->next = nowa;
			nowa->prev = tmp;
			nowa = tmp;
		}
		else
		{
			pom = nowa;
			while (pom->next != NULL && strcmp(pom->next->dane.imie, tmp->dane.imie) < 0)
				pom = pom->next;
			tmp->prev = pom;
			tmp->next = pom->next;
			if (pom->next != NULL)
				pom->next->prev = tmp;
			pom->next = tmp;
		}
		pom = *head;
		*head = (*head)->next;
		if (pom->dane.imie)
			free(pom->dane.imie);
		if (pom->dane.nazwisko)
			free(pom->dane.nazwisko);
		free(pom);
	}
	*head = nowa;
}

Komentarze

  1. To w końcu to jest lista jedno- czy dwukierunkowa? W tytule – jest dwukierunkowa, a w opisie i komentarzach jest jednokierunkowa…

    • Poprawiłem błąd w opisie. Oczywiście jest to przykład z listą dwukierunkową.

  2. Obydwa wskaźniki do elementów są używane więc jest to lista dwukierunkowa
    Zastanawia mnie użyty algorytm wygląda na bąbelki chociaż bardziej efektywne byłoby scalanie bo kopcowanie do list się nie nadaje
    Nie jestem fanem tzw sortowania szybkiego bo może zwolnić i zatrzymać się w czasie porównywalnym z bąbelkami

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *