Sortowanie listy

0

Cześć, mam problem z sortowaniem listy dwukierunkowej, poprzez zwykły bubblesort. Niepoprawnie "przypinam" wskaźniki ogona listy, z czym męczę się już drugi dzień. Teoretycznie mógłbym pominąć wskaźnik na ogon i w funkcji dodającej na koniec użyć tylko wskaźnik na głowę. Jednak ta funkcja jest częścią większego programu, gdzie ogon bardzo mi się przydaje. W funkcji sort w komentarzach umieściłem to, w jaki sposób przypiąłem wskaźniki ogona, domyślam się że większość z nich nie jest poprawna. Ponadto podczas zwalniania tmp wyświetla się komunikat o nadpisaniu w pamięci. Proszę o pomoc

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 50
//-------------------------------------------------------------------------------------------------------------------------------------------------//
typedef struct osoba
{
	char * imie;
}osoba;

typedef struct node
{
	struct node *next, *prev;
	osoba data;
}node;

typedef struct list
{
	node *head, *tail;
}list;

void push_back(list *L, char *t);
void sort(node **head, node **tail);
void print(list *L);
//-------------------------------------------------------------------------------------------------------------------------------------------------//
int main()
{
	list L;
	L.head = NULL, L.tail = NULL;
	push_back(&L, "ccc");
	push_back(&L, "aaa");
	print(&L);
	sort(&(L.head), &(L.tail));
	printf("\n");
	print(&L);
	push_back(&L, "bbb");
	printf("\n");
	print(&L);
	system("pause");
	return 0;
}
//-------------------------------------------------------------------------------------------------------------------------------------------------//
void push_back(list *L, char *t) // dodaje element na koniec listy
{
	if (L->tail == NULL)
	{
		L->tail = (node*)malloc(sizeof(node));
		L->head = L->tail;
		L->tail->prev = NULL;
	}
	else
	{
		L->tail->next = (node*)malloc(sizeof(node));
		L->tail->next->prev = L->tail;
		L->tail = L->tail->next;
	}
	L->tail->data.imie = (char*)malloc(sizeof(char)*strlen(t) + 1);
	strcpy(L->tail->data.imie, t);
	L->tail->next = NULL;
}
//-------------------------------------------------------------------------------------------------------------------------------------------------//
void print(list *L)
{
	int i = 0;
	node *ptr = NULL;
	for (i = 1, ptr = L->head; ptr != NULL; ptr = ptr->next, i++)
	{
		printf("%s ", ptr->data.imie);
	}
}
//-------------------------------------------------------------------------------------------------------------------------------------------------//
void sort(node **head, node **tail)
{
	node* poprzedni = NULL;
	node *tmp = NULL, *aktualny;

	if (*head == NULL)
	{
		printf("Lista jest pusta!\n");
		return;
	}

	if (*head == *tail && *head != NULL)
	{
		printf("Lista zawiera tylko jeden element\n");
		return;
	}

	while (*head != NULL)
	{
		aktualny = (node*)malloc(sizeof(node));
		aktualny->data.imie = (char*)malloc(sizeof(char)* strlen((*head)->data.imie) + 1);
		strcpy(aktualny->data.imie, (*head)->data.imie);
		aktualny->next = NULL;
		aktualny->prev = NULL;

		if (poprzedni == NULL) poprzedni = aktualny;

		else if (strcmp(poprzedni->data.imie, aktualny->data.imie) > 0)//sortowanie rosnace
		{
			aktualny->next = poprzedni;
			poprzedni->prev = aktualny;
			poprzedni = aktualny;
			//*tail = poprzedni;
		}

		else
		{
			tmp = poprzedni;
			while (tmp->next != NULL && strcmp(tmp->next->data.imie, aktualny->data.imie) < 0)
				tmp = tmp->next;

			aktualny->prev = tmp;
			aktualny->next = tmp->next;

			if (tmp->next != NULL) tmp->next->prev = aktualny;

			//else  *tail = aktualny;
			tmp->next = aktualny;

		}
		tmp = *head;
		*head = (*head)->next;
		//if (tmp->data.imie) free(tmp->data.imie);
		//free(tmp);
	}
	*head = poprzedni;
}
0

Zacznij od przekazania struktury list do sort()
Narysuj sobie na kartce trzy sytuacje, wymieniasz: pierwszą parę, ostatnią parę, jakaś parę ze środka.

0

Przekazałem strukturę list do funkcji sortującej i poprawiłem wskaźniki. Wszystko wydaje się ok poza tym, że po wywołaniu funkcji sortującej następuje "przesunięcie" listy o jeden element, tak że głowa wskazuje na drugi element, a ogon na nieistniejący. Czy da się coś z tym zrobić ?

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 50
//-------------------------------------------------------------------------------------------------------------------------------------------------//
typedef struct osoba
{
	char * imie;
}osoba;

typedef struct node
{
	struct node *next, *prev;
	osoba data;
}node;

typedef struct list
{
	node *head, *tail;
}list;

void push_back(list *L, char *t);
void sort(list **L);
void print(list *L);
//-------------------------------------------------------------------------------------------------------------------------------------------------//
int main()
{
	list L;
	L.head = NULL, L.tail = NULL;
	push_back(&L, "ccc");
	print(&L);
	sort(&L);
	printf("\n");
	print(&L);
	push_back(&L, "bbb");
	printf("\n");
	print(&L);
	printf("\n");
	system("pause");
	return 0;
}
//-------------------------------------------------------------------------------------------------------------------------------------------------//
void push_back(list *L, char *t) // dodaje element na koniec listy
{
	if (L->tail == NULL)
	{
		L->tail = (node*)malloc(sizeof(node));
		L->head = L->tail;
		L->tail->prev = NULL;
	}
	else
	{
		L->tail->next = (node*)malloc(sizeof(node));
		L->tail->next->prev = L->tail;
		L->tail = L->tail->next;
	}
	L->tail->data.imie = (char*)malloc(sizeof(char)*strlen(t) + 1);
	strcpy(L->tail->data.imie, t);
	L->tail->next = NULL;
}
//-------------------------------------------------------------------------------------------------------------------------------------------------//
void print(list *L)
{
	if (L->head == NULL)
	{
		printf("Lista jest pusta\n");
		return;
	}
	node *ptr = NULL;
	for (ptr = L->head; ptr != NULL; ptr = ptr->next)
	{
		printf("%s ", ptr->data.imie);
	}
}
//-------------------------------------------------------------------------------------------------------------------------------------------------//
void sort(list **L)
{
	node* poprzedni = NULL;
	node *tmp = NULL;
	node *aktualny = NULL;
	//printf("p = %d", &(*L)->head);
	if (&(*L)->head == NULL)
	{
		printf("Lista jest pusta!\n");
		return;
	}

	while ((*L)->head != NULL)
	{
		aktualny = (node*)malloc(sizeof(node));
		aktualny->data.imie = (char*)malloc(sizeof(char)* strlen((*L)->head->data.imie) + 1);
		strcpy(aktualny->data.imie, (*L)->head->data.imie);
		aktualny->next = NULL;
		aktualny->prev = NULL;

		if (poprzedni == NULL) poprzedni = aktualny;

		else if (strcmp(poprzedni->data.imie, aktualny->data.imie) > 0)//sortowanie rosnace
		{
			aktualny->next = poprzedni;
			poprzedni->prev = aktualny;
			poprzedni = aktualny;
			if ((*L)->head->next == NULL)
			{
				poprzedni->next = NULL;
				(*L)->tail = poprzedni;
			}
		}

		else
		{
			tmp = poprzedni;
			while (tmp->next != NULL && strcmp(tmp->next->data.imie, aktualny->data.imie) < 0)
				tmp = tmp->next;

			aktualny->prev = tmp;
			aktualny->next = tmp->next;

			if (tmp->next != NULL) tmp->next->prev = aktualny;

			else  (*L)->tail = aktualny;
			tmp->next = aktualny;

		}
		tmp = (*L)->head;
		(*L)->head = (*L)->head->next;
		if (tmp->data.imie) free(tmp->data.imie);
		free(tmp);
	}
	(*L)->head = poprzedni;
}
0

Powiedziałem narysuj, to zobaczysz i się nauczysz, mam naprawdę sporę doświadczenie ale w niektórych trudnych przypadkach wciąż rysuje.
To jest naprawdę prymitywnie proste kiedy już sobie narysujesz, grunt aby najpierw zrobić podstawowe klocki:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 50

typedef struct person
  {
   char *name;
  }person;
 
typedef struct node
  {
   struct node *next,*prev;
   person data;
  }node;
 
typedef struct list
  {
   node *head,*tail;
  }list;

node *makePersonNode(const char *name) /* Jak to zrobisz to nie musisz to samo powtarzać w kilku miejscach */
  {
   node *tmp=(node*)malloc(sizeof(node));
   //tmp->next=tmp->prev=NULL; /* są zwolennicy programowania defiensywnego, ja nie */
   tmp->data.name=strdup(name); /* polecam, jeżeli brak to radzę napisać swoją `strdup` */
   return tmp;
  }
  
static void _unsafeInsertPersonNode_(list *L,node *next,node *prev,node *ins) /* uniwersalne wstawienie gdziekolwiek, niebezpieczne bo niepilnowane next,prev stąd static */
  {
   ins->prev=prev; /* ustawiamy poprzedni */
   ins->next=next; /* ustawiamy następny */
   if(prev) prev->next=ins; else L->head=ins; /* albo jestem za kimś a jak nikogo nie ma to jestem pierwszy */
   if(next) next->prev=ins; else L->tail=ins; /* jak wyżej tylko w drugim kierunku */
  }

void push_front(list *L,const char *name) /* po zrobieniu makePersonNode oraz _unsafeInsertPersonNode_ o tak wygładają push_* */
  {
   _unsafeInsertPersonNode_(L,L->head,NULL,makePersonNode(name));
  }

void push_back(list *L,const char *name) /* po zrobieniu makePersonNode oraz _unsafeInsertPersonNode_ o tak wygładają push_* */
  {
   _unsafeInsertPersonNode_(L,NULL,L->tail,makePersonNode(name));
  }

void inorderInsertPersonNode(list *L,node *ins)
  {
   node *next,*prev;
   for(prev=NULL,next=L->head;(next)&&(strcmp(next->data.name,ins->data.name)<0);next=next->next) prev=next; /* gdzie wstawiamy? */
   _unsafeInsertPersonNode_(L,next,prev,ins);
  }

void showPersonList(list *L) /* jak chcesz mazać po ekranie "Lista jest pusta" to rób to w main a nie w podstawowych funkcjach obsługi */
  {
   node *i;
   printf("{ ");
   for(i=L->head;i;i=i->next) printf("\"%s\" ",i->data.name);
   printf("}\n");
  }

int isEmptyPersonList(list *L) /* dla ułatwenia mazań po ekranie w main */
  {
   return (L->head==NULL);
  }

void sortPersonList(list *L) /* po kiego miałeś podwójny wskaźnik? */
  {
   node *curr,*next;
   curr=L->head; /* zapamiuętujemy początek listy */
   for(L->head=L->tail=NULL;curr;curr=next) /* odłączamy wszystko od aktualnej, i lecimy po zapamiętanej */
     {
      next=curr->next; /* trzeba zachować następny dla kolejnego kroku bo zaraz przełączymy ten węzeł do nowej */
      inorderInsertPersonNode(L,curr); /* wstawiamy do listy */
     }
  }

int main()
  {
   list L={NULL,NULL};
   showPersonList(&L);
   //sortPersonList(&L);  showPersonList(&L);
   push_back(&L,"ccc"); showPersonList(&L);
   //sortPersonList(&L);  showPersonList(&L);
   push_back(&L,"bbb"); showPersonList(&L);
   //sortPersonList(&L);  showPersonList(&L);
   push_back(&L,"aaa"); showPersonList(&L);
   sortPersonList(&L);  showPersonList(&L);
   return 0;
  }

1 użytkowników online, w tym zalogowanych: 0, gości: 1