[C] Usuwanie elementów z listy dwukierunkowej

W tym artykule przedstawię w jaki sposób usuwać elementy z listy dwukierunkowej. Tak jak w przypadku dodawania elementów do listy wszystkie algorytmy będą pisane w procedurach, do których można się odnieść w głównej części programu i będą oparte na poniższej strukturze:

//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.

Usuwanie całej listy

Polega na iteracyjnym usuwaniu pierwszego elementu listy, aż do momentu kiedy nie ma już więcej elementów na liście. Podstępowanie jest identyczne jak w przypadku listy jednokierunkowej.

void usun_liste(Student **head)
{
	Student *tmp;

	while (*head != NULL)
	{
		tmp = *head;
		*head = (*head)->next;
		if (tmp->dane.imie)
			free(tmp->dane.imie);
		if (tmp->dane.nazwisko)
			free(tmp->dane.nazwisko);
		free(tmp);
	}
}
Usuwanie wybranego elementu

W przypadku usuwania wybranego elementu najlepiej posłużyć się dodatkową funkcją wyszukującą element, który ma zostać usunięty(funkcja szukaj). Zakładamy, że chcemy usunąć element o podanym nazwisku. W tym celu pytamy się o dane nazwisko, a następnie szukamy takiego elementu na liście. Gdy podany element nie występuje to usunięcie nie zostaje wykonane, natomiast gdy taki element istnieje musimy odszukać go na liście i przepiąć wskaźnik z poprzedniego elementu tak, aby wskazywał na następny. Na samym końcu usuwamy wybrany element.

Student* wyszukaj_element(Student *head, char *nazwisko)
{
	Student *pom;

	pom = head;
	while (pom != NULL && strcmp(pom->dane.nazwisko, nazwisko) != 0)
		pom = pom->next;

	return pom;
}
void usuwan_wybrany_element(Student **head)
{
	Student *tmp, *pom;
	char *nazwisko;
	char bufor[30 + 1];
	
	system("cls");
	printf("Podaj nazwisko: ");
	gets(bufor);
	nazwisko = (char*)malloc(sizeof(char)* (strlen(bufor) + 1));
	strcpy(nazwisko, bufor);

	tmp = wyszukaj_element(*head, nazwisko);
	if (tmp == NULL)
		printf("Nie ma takiej osoby");
	else
	{
		if (tmp == *head)
		{
			*head = (*head)->next;
			if (tmp->dane.imie)
				free(tmp->dane.imie);
			if (tmp->dane.nazwisko)
				free(tmp->dane.nazwisko);
			free(tmp);
		}
		else
		{
			pom = *head;
			while ((strcmp(pom->next->dane.nazwisko, tmp->dane.nazwisko) != 0))
				pom = pom->next;
			if (tmp->next != NULL)
				pom->next->prev = tmp->prev;
			pom->next = tmp->next;
			if (tmp->dane.imie)
				free(tmp->dane.imie);
			if (tmp->dane.nazwisko)
				free(tmp->dane.nazwisko);
			free(tmp);
		}
	}
}                               
Usuwanie duplikatów

Polega na przeszukiwaniu listy w celu usunięcia powtarzających się elementów. Przykładowo dla pierwszego elementu przeszukujemy listę od elementu drugiego do ostatniego, a gdy napotkamy element zawierający te same dane co pierwszy to usuwamy go. Następnie bierzemy element drugi i szukamy elementów zaczynając od elementu trzeciego. Algorytm powtarzamy do znalezienia ostatniego elementu.

void usuwanie_duplikatow(Student **head)
{
	Student *tmp, *pom, *pom2;
	tmp = *head;
	while (tmp != NULL)
	{
		pom = tmp;
		while (pom->next != NULL)
		{
			if (strcmp(pom->next->dane.nazwisko, tmp->dane.nazwisko) == 0)
			{
				pom2 = pom->next;
				pom->next = pom2->next;
				if (pom2->next != NULL)
					pom2->next->prev = pom;
				if (pom2->dane.imie)
					free(pom2->dane.imie);
				if (pom2->dane.nazwisko)
					free(pom2->dane.nazwisko);
				free(pom2);
			}
			else
				pom = pom->next;
		}
		tmp = tmp->next;
	}
}                                                          

Dodaj komentarz

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