Lista - sortowanie :: 4programmers.net

0

Witam,

mam za zadanie posortowanie listy przez wybieranie najmniejszego elementu :) Siedzę nad tą funkcją dzień ale nie daje rady... coś ciągle jest nie tak, w pierwszym obiegu pętli jest okej ale dalej jest jakiś szczegół i program się sypie, ktoś pomoże - zobaczy, gdzie jest błąd?

Lista jest jednokierunkowa, wszystkie funkcje oprócz sortowania wydają się działać poprawnie.

main

#include "stdafx.h"
#include "lista.h"
#include <cstdlib>
#include <iostream>
#include <stdio.h>
using namespace std;


int _tmain(int argc, _TCHAR* argv[])
{

	printf("Program nr 4 - LISTA JEDNOKIERUNKOWA \n");
	
	ListItem* lista = NULL;
	TworzListe(&lista);
	DodajElement(lista,15);
	DodajElement(lista, 3);
	DodajElement(lista, -15);
	DodajElement(lista, 5);
	DodajElement(lista, 2);
	DodajElement(lista, 8);
	DodajElement(lista, -2);
	DodajElement(lista, 5);
	DodajElement(lista, 2);
	WyswietlListe(lista);
	// printf("\n po usunieciu elementu 5 \n");
	sortuj_wybierajac(lista);
	//WyswietlListe(lista); - nie działa - czemu? 

	// Usun_z_Listy(lista, 1);

	system("pause");
	return EXIT_SUCCESS;
}

lista.h

#ifndef _LIST_INC_
#define _LIST_INC_

typedef struct tagListItem{
	int wartosc;
	tagListItem * next;
}ListItem, *LP_ListItem;


void TworzListe(ListItem** glowaL);
void DodajElement(ListItem* glowaL, int war);
void WyswietlListe(ListItem* glowaL); 
void Dodaj_do_Listy(ListItem* glowaL, int rozmiar);
void Uwolnij_liste(ListItem** glowaL);
void Usun_z_Listy(ListItem* glowaL, int element);
void sortuj_wybierajac(ListItem* glowaL);

#endif

lista.cpp - !

#include "stdafx.h"
#include <stdlib.h>
#include "lista.h"
#include <iostream>
#include <time.h>
#include <conio.h>

using namespace std;

void TworzListe(ListItem** glowaL)
{
	if (*glowaL == NULL)
	{
		ListItem *p = (ListItem*)malloc(sizeof(ListItem));
		memset(p, 0, sizeof(ListItem)); 
		*glowaL = p; 
	}
	else
		printf("Lista już istnieje ! ");
}


void DodajElement(ListItem* glowaL, int war)
{
	ListItem *p = (ListItem*)malloc(sizeof(ListItem));
		p->wartosc = war; 
		p->next = glowaL->next; 
		glowaL->next = p; 
	// glowaL = p; --> niepotrzebne?
}


void WyswietlListe(ListItem* glowaL)
{
	int i = 0;
	ListItem* lista = glowaL; 
	while (1)
	{
		printf("Wartosc elementu %d i wskaznik %p \n", lista->wartosc, lista->next);
		if (lista->next == NULL) break;
		lista = lista->next;
	};

}

void Dodaj_do_Listy(ListItem* glowaL, int rozmiar)
{
	srand((unsigned int)time(NULL));
	for (int i = 0; i < rozmiar; i++)
	{
		DodajElement(glowaL, rand() % 50);
	}
}

void Usun_z_Listy(ListItem* glowaL, int element)
{
	//przesuniecieGlowy o element jeden mniejszy
	for (int i = 0; i < (element-2); i++)
	{
		if (glowaL->next == NULL) break;
		glowaL = glowaL->next; 
	}


	//USUWANIE ELEMENTU
	ListItem* temp = glowaL->next->next; //wskaznik pokazujacy na element ktory PRZYPINAMY
	ListItem* temp2 = glowaL->next;
	glowaL->next = temp; 
	free(temp2);
	
}

ListItem* przesun_liste(ListItem* glowaL,int element)
{
	for (int i = 0; i < element ; i++)
	{
		if (glowaL->next == NULL) break;
		glowaL = glowaL->next;
	}
	return glowaL;
}

int ktory_element(ListItem* glowaL, ListItem* element)
{
	int i = 0; 
	printf("\n dwie wartosci %d %d \n", glowaL->wartosc, element->wartosc);
	while (1)
	{
		glowaL = glowaL->next; 
		if (glowaL == element) break; 
		i++; 
	}
	printf("\n wartosc i %d \n", i);
	return i; 
}

ListItem* min_element(ListItem* glowaL)
{
	ListItem* MinL = glowaL;
	while (1)
	{
		if (glowaL->wartosc < MinL->wartosc)
		{
			MinL = glowaL;
		}

		if (glowaL->next == NULL) break;
		glowaL = glowaL->next; //przesuwamy glowe
	}
	return MinL;
}

void sortuj_wybierajac(ListItem* glowaL)
{
	 ListItem* MinL = glowaL;
	 ListItem* PoczL = glowaL;
	 ListItem* przesuwany = glowaL;
	 ListItem* nast = glowaL;
	 int i = 0;
	 int j = 1;
	//szukamy minimum
	 while (1)
	 {
		 MinL = min_element(PoczL);
		 i = ktory_element(glowaL, MinL);
		 przesuwany = przesun_liste(glowaL, i);
		 // MAMY DO DYSPOZYCJI 3 WSKAZNIKI : MINL, POCZTL, CZWARTA
		 printf("wartosc minl: %d pokazujacy na wskaznik %p \n", MinL->wartosc, MinL->next);
		 printf("wartosc pocztl: %d pokazujacy na wskaznik %p \n", PoczL->wartosc, PoczL->next);
		 printf("wartosc czwarta: %d pokazujacy na wskaznik %p \n", przesuwany->wartosc, przesuwany->next);
		 printf("\n \n \n");

		 ListItem* temp2 = MinL->next;
		 ListItem* temp = glowaL;
		 // glowaL = MinL;
		 glowaL->next = PoczL->next;
		
		 
		 temp->next = temp2;
		 przesuwany->next = temp;
		 //MinL->next = temp; 
		 
		 printf("po zmianach \n");
		 printf("wartosc glowy: %d pokazujacy na wskaznik %p \n", glowaL->wartosc, glowaL->next);
		 printf("wartosc czwarta: %d pokazujacy na wskaznik %p \n \n \n", przesuwany->wartosc, przesuwany->next);
		 
		 
		 //printf("war czwarta: %d pokazujacy na wskaznik %p \n", czwarta->wartosc, czwarta->next);
		 if (j< 3) WyswietlListe(glowaL);
		 // PoczL->next = temp2; 
		 //glowaL->next = bezu;
		 
		 // glowa ta sama, poczatek listy inny
		 

		 // ustawienie nowe min
		 MinL->wartosc = glowaL->wartosc;
		 PoczL = przesun_liste(glowaL, j);
		 printf("wartosc glowy po PRZESUNIECIU: %d pokazujacy na wskaznik %p \n", glowaL->wartosc, glowaL->next);
		 printf("wartosc poczL po PRZESUNIECIU: %d pokazujacy na wskaznik %p \n", PoczL->wartosc, PoczL->next);
		 if (PoczL->next == NULL) break;
		 przesuwany = PoczL;
		 //PoczL = glowaL->next;
	 
		 if (j == 3) break;
		 j++;
	 }
	
}

0

Wyświetlanie na pewno Ci działa? Wskaźnik, którym masz zamiar pokazywać na początek listy w każdej operacji dodawania elementu przesuwasz na koniec listy. Tutaj http://www.p-programowanie.pl/cpp/lista-jednokierunkowa-c/ masz przyjaźnie wutłumaczoną listę jednokierunkową (nie weryfikowałem poprawności kodu).

0

tak, działami mi - teraz wyrzuciłem jedną linie bo chyba faktycznie mogło to być niejasne :)

Tak jak pisze - wszystkie funkcje na liście działają więc nie ma sensu jej robić od początku. Problem jest tylko w void sortuj_wybierajac(ListItem* glowaL). Prosiłbym jedną osobę o sprawdzenie kodu, wyjaśnienie błędów... byłbym wdzięczny - nauczy mnie to lepiej kodzić :)

2

Jeszcze raz, na pewno Ci działa? Bo ja nadal twierdzę że nie ;)

Ten kod to nie C, tylko takie udawane C w C++
Pierwszy węzeł będzie miał zawsze wartość zero, mimo że nigdy takiej wartości nie dodawałeś.
Po każdym dodaniu węzła zmieniasz wskaźnik glowaListy->next
W skutek powyższego po zakończeniu dodawaniu węzłów glowaListy->next pokazuje na ostatni element listy.
W skutek powyższego wyświetlanie w Twoim kodzie powinno zacząć się od ostatniego elementu listy. Mam rację?

W skutek powyższych punktów po jednokrotnym wyświetleniu zawartości listy Twój wskaźnik pokazuje na węzeł którego wartość next pokazuje na nic, dlatego powinieneś mieć błąd naruszenia pamięci przy próbie sortowania bądź ponownego wyświetlenie.

0

fakt - miałeś rację - wielkie dzięki !

mam pytanie, bo już trochę tą listę przemęczyłem, dużo razu już ją sprawdzałem ale mam jeden moment, przy sortowaniu, przy którym mi sieka, oznaczony w komentarzu

how
, aby było łatwiej znaleźć.

Bardzo zależy mi, aby ktoś wychwycił o co chodzi, pisanie tego programu zajeło mi długo i głupio by było teraz zrezygnować gdy już jestem blisko..

#include "stdafx.h"
#include <stdlib.h>
#include "lista.h"
#include <iostream>
#include <time.h>
#include <conio.h>
using namespace std;

void TworzListe(ListItem** glowaL)
{
	if (*glowaL == NULL)
	{
		ListItem *p = (ListItem*)malloc(sizeof(ListItem));
		p->next = NULL; 
		p->wartosc = 0; 
		*glowaL = p; 
	}
	else
		printf("Lista już istnieje ! ");
}


void DodajElement(ListItem* glowaL, int war)
{
	//glowa pokazuje na element w ktowym wartosc jest random a next->null; 
	ListItem *p = (ListItem*)malloc(sizeof(ListItem));
	ListItem *pomoc = przesun_liste_na_koniec(glowaL); // doczepiamy element listy na koniec
	
	p->wartosc = war;
	p->next = NULL; 
	pomoc->next = p; 

}


void WyswietlListe(ListItem* glowaL)
{
	int i = 0;
	ListItem* lista = glowaL; 
	while (1)
	{
		printf("Wartosc elementu %d i wskaznik %p \n", lista->wartosc, lista->next);
		if (lista->next == NULL) break;
		lista = lista->next;
	};

}

void Dodaj_do_Listy(ListItem* glowaL, int rozmiar)
{
	srand((unsigned int)time(NULL));
	for (int i = 0; i < rozmiar; i++)
	{
		DodajElement(glowaL, rand() % 50);
	}
}

void Usun_z_Listy(ListItem* glowaL, int element)
{
	//przesuniecieGlowy o element jeden mniejszy
	for (int i = 0; i < (element-2); i++)
	{
		if (glowaL->next == NULL) break;
		glowaL = glowaL->next; 
	}


	//USUWANIE ELEMENTU
	ListItem* temp = glowaL->next->next; //wskaznik pokazujacy na element ktory PRZYPINAMY
	ListItem* temp2 = glowaL->next;
	glowaL->next = temp; 
	free(temp2);
	
}

ListItem* przesun_liste(ListItem* glowaL,int element)
{
	for (int i = 0; i < element ; i++)
	{
		if (glowaL->next == NULL) break;
		glowaL = glowaL->next;
	}
	return glowaL;
}

ListItem* przesun_liste_na_koniec(ListItem* glowaL)
{
	ListItem* pomoc = glowaL;
	if (pomoc->next == NULL) return pomoc;
	while (1)
	{
		pomoc = pomoc->next;
		if (pomoc->next == NULL) break;
	}
	return pomoc;
}

int ktory_element(ListItem* glowaL, ListItem* element)
{
	ListItem* pomoc = glowaL;
	int i = 0; 
	printf("\n dwie wartosci %d %d \n", pomoc->wartosc, pomoc->wartosc);
	while (1)
	{
		pomoc = pomoc->next; 
		if (pomoc == element) break; 
		i++; 
	}
	printf("\n wartosc i %d \n", i);
	return i; 
}

ListItem* min_element(ListItem* glowaL)
{
	ListItem* MinL = glowaL;
	ListItem* pomoc = glowaL;
	while (1)
	{
		if (pomoc->wartosc < MinL->wartosc)
		{
			MinL = pomoc;
		}

		if (pomoc->next == NULL) break;
		pomoc = pomoc->next; //przesuwamy glowe
	}
	return MinL;
}

void sortuj_wybierajac(ListItem* glowaL)
{
	//zmienne do dyspozycji 
	ListItem* MinL = glowaL;
	ListItem* PoczL = glowaL;
	ListItem* przesuwany = glowaL;
	ListItem* nast = glowaL;
	ListItem* glowa = glowaL;
	int i = 0;
	int j = 1;

	while (1)
	{
		MinL = min_element(PoczL);
		i = ktory_element(glowaL, MinL);
		przesuwany = przesun_liste(glowaL, i);

		if (PoczL == przesuwany)
		{
			// jezeli elementy są obok siebie

			ListItem* temp = MinL->next;

			printf("TUTAJ \n"); 
			
			przesuwany = przesun_liste(glowaL, i-1);

			przesuwany->next = MinL; 
			MinL->next = PoczL; 
			PoczL->next = temp; 

			PoczL = przesun_liste(glowaL, j-1); // how? 

		}
		else {
			ListItem* temp2 = MinL->next;
			ListItem* temp = PoczL;

			if (j == 1)
			{
				glowaL = MinL;
				glowaL->next = PoczL->next;
				PoczL = MinL;
			}
			else{
				PoczL = MinL;
				glowaL->next = PoczL;
			}
			PoczL->next = temp->next;
			temp->next = temp2; 
			przesuwany->next = temp;

			MinL->wartosc = PoczL->wartosc;

			przesuwany = PoczL;
			PoczL = PoczL->next;
		}


		if (j == 5) break; 
		
		WyswietlListe(glowaL);

		if (glowa->next == NULL) break;

		j++;
	}
}

chodzi oczywiście o funkcje sortuj_wybierajac :)

Lista - sortowanie

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

Praca dla programistów

Forum dyskusyjne

Sprawy administracyjne

O nas

Skontaktuj się z nami