Odwracanie listy dwukierunkowej - C


(Phinsectoman) #1

Witam, próbuję stworzyć funkcję która odwróci mi moją listę dwukierunkową. Póki co to w wyniku dostaje pustą listę, lub nic, bo nic się nie wyswietla.

 

Poniżej cały kod programu:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h> 
#include<stdlib.h> 

struct element
{
	int key;
	struct element *next;
	struct element *prev;
};

struct element *lista_dodaj(struct element *head, struct element *nowy);
struct element *lista_szukaj(struct element *head, int szukana);
struct element *lista_usun(struct element *head, struct element *x);
struct element *lista_odwroc(struct element *head);
void lista_wyswietl(struct element *head);

main()

{
	struct element *head = NULL;
	struct element *nowy = NULL;
	int liczba;
	int szukana=0;
	struct element *wynik_szukania;
	int usuwana;
	struct element *wysz_usun;
	struct element *wynik_odw;
	char z;

	while (1)
	{
	printf("\n\nPodaj co chcesz zrobic: \nd - dodaj do listy\nq - wyjscie\nw - wyswietl cala liste\ns - szukaj elementu w liscie\nu - usun element z listy\no - odwroc liste\n\n");
	fflush(stdin);
	z = getchar();

	
		switch (z)
		{
		case 'd':
			nowy = (struct element*)malloc(sizeof(struct element));
			printf("\nPodaj liczbe do wstawienia. \n");
			scanf("%d", &liczba);
			nowy->key = liczba;
			head = lista_dodaj(head, nowy);
			break;
			
		case 'q':
			return 0;

		case 'w':
			lista_wyswietl(head);
			break;

		case 's':
			printf("\nPodaj liczbe ktorej bedziemy szukac w tekscie. \n");
			fflush(stdin);
			scanf("%d", &szukana);
			wynik_szukania = lista_szukaj(head, szukana);
			if (wynik_szukania != 0)
			{
				printf("Znaleziono element w liscie na adresie %d \n", wynik_szukania);
			}
			else
				printf("Nie znaleziono elementu w liscie.\n");
			break;

		case 'u':
			printf("\nPodaj liczbe ktorej bedziemy usuwac. \n");
			fflush(stdin);
			scanf("%d", &usuwana);
			wysz_usun = lista_szukaj(head, usuwana);
			lista_usun(head, wysz_usun);
			break;

		case 'o':
			wynik_odw = lista_odwroc(head);
			printf("Odwrocona lista: \n");
			lista_wyswietl(wynik_odw);
		}
	}
}

struct element *lista_dodaj(struct element *head, struct element *nowy)
{
	nowy->prev = NULL;
	nowy->next = head;
	if (head != NULL)
	{
		head->prev = nowy;
	}
	head = nowy;
	return head;
}

void lista_wyswietl(struct element *head)
{
	struct element *x = head;
	while (x != NULL)
	{
		printf("%d	", x->key);
		x = x->next;
	}
}

struct element *lista_szukaj(struct element *head, int szukana)
{
	struct element *x = head;
	while ((x != NULL) && ((x->key) != szukana))
	{
		x = x->next;
	}
	return x;
}

struct element *lista_usun(struct element *head, struct element *x)
{
	if (x->prev != NULL)
	{
		x->prev->next = x->next;
	}
	else
		head = x->next;
	if (x->next != NULL)
		x->next->prev = x->prev;
		free(x);
	return head;
}

struct element *lista_odwroc(struct element *head)
{
	struct element *head1=NULL;
	struct element *x=head;
	struct element *y = head1;
	y = (struct element*)malloc(sizeof(struct element));
	while (x->next!= NULL)
	{
		y->key = x->key;
		lista_dodaj(head1, y);
		x = x->next;
	}
	return head1;
}

Mógłby mi ktoś podpowiedzieć gdzie popełniam błąd?

 


(stasinek) #2

#pragma Rozumiem że to zadanie szkolne bo czepiłbym się wszystkiego gdyby nie było :slight_smile:

#include Podejrzewam nawet ze celowo popsute do naprawy?

 

main() {

Patrząc na funkcję dodaj i porównując z wyświetl nie widzę aby lista podążała we wspólnym kierunku i  tam jest błąd.  Zamieniłeś prev z next(null/nowy). Doczepiając “holownik” lepiej przypisać head->next=nowy za dziób a nie podczepiać się pod tył head->prev prawda? 

Poza tym nie if (head!=NULL)  ale while (x->next!=NULL) x = x->next; bo aby cokolwiek dodać na listę najpierw trzeba przelecieć wszystkie poprzednie i znaleźć tą jedyną na koniec.

Następnie x->next = nowy; nowy->prev = x;

return żyli długo i szczęśliwie;

}

 

/* Próbujesz w niezbyt intuicyjny sposób w ograniczającym możliwości C zbudować odpowiednik C++ stl::deque, okej bo C ma swoje biblioteczne zalety. Każda funkcja operuje na parametryzowanym head zamiast bazować na “this”, to niewielka różnica C/C++ czy head->dodaj(coś) czy dodaj(head,coś). 

Ale Twoja lista jest dziwaczna bo patrząc na “dodaj” głowa nie jest głową tylko poprzednim elementem? 

Gdzie tu sens gdzie logika? Niech jedynym parametrem wskaźnikowym będzie adres głowy (baza), reszta ma inicjować, usuwać iterować się sama i jedynymi wartościami dodawanymi, usuwanymi, szukanymi, wstawianymi, wyliczanymi niech będą <int> dodawanymi od d*** strony rzecz jasna ;) Zero wskaźników w parametrach funkcji poza struct element *baza;

 

Skoro masz już szukajkę i klucz, malloc i free powinien znajdował się wyłącznie! w ciałach funkcji z dala od main(). Funkcje szukaj zrobiłeś dla int ale dodaj i usuń dla wskaźnika :slight_smile:

Co gdyby element przechowywał wskaźniki zamiast int? mallokować element po to by przechowywać wskaźnik z innego malloka…można się zagubić operując na takiej liście. Funkcja usuń mogłaby sama wywoływać funkcję szukaj i usuwać znaleziony element(lub wcale) a nie usuwać po wskaźniku, zwracając przy okazji boola czy się udało czy nie…

Nieistniejąca jeszcze funkcja insert mogłaby mieć dwa parametry(poza head) tj. klucz<int> w którego miejsce ma wstawić coś<int> zwracając podobnie jak dodaj wskaźnik do nowego elementu.

W tej funkcji skorzystasz z zalet dwukierunkowości prev i next bo owszem poszukiwanie troche trwa ale nie trzeba przesuwać elementów żeby znaleźć miejsce nowemu elementowi w środku…

Nieistniejąca funkcja policz powinna iterować od początku do końca zwracając ilość elementów.

itd. wszystko byle z dala od nadmiaru wskaźników. 

*/