Kochani forumowicze, proszę o pomoc. Musze w C napisac program tworzący "macierz rzadką" to taka macierz która ma w sobie bardzo bardzo dużo zer i tylko kilka konkretynych liczb. Program musi sam wpisac 0 do macierzy, użytkownik musi sam wpisać kilka konkretnych liczb. Program musi zapamiętac jakie to były i w których miejscach się one znajdowały, a następnie dane te zapisać do pliku. prosze o pomoc bo nie wiem od czego zaczac a na czym skonczyc. z C nie potrafię za wiele, a zrobić musze. Pozdrawiam.
No dobra, to powiedz czego nie potrafisz? Sprecyzuj dokładnie wejście (DOKŁADNIE!), jakie informacje możemy wyciągnąć od użytkownika (np ile tych jedynek chce tam wstawić, jakich wymiarów ma być ta macierz), potem jak ma wyglądać wprowadzanie tych jedynek? Użytkownik ma je wprowadzać współrzędnymi w macierzy? Jak ma dokładnie wyglądać wyjście?
Do reprezentacji takiej macierzy można bez problemu użyć dwuwymiarowej tablicy (w tym wypadku pewnie stworzonej dynamicznie).
a wiec tak. na samym poczatku uzytkownik musi zdefiniowac rozmairy macierzy. konkretne liczby tez podaje uzytkownik, powiedzmy niech beda to 4 liczby, reszta pol w macierzy musi byc rowna zero. z tego co mowil mi nauczyciel to program ma zadbac o to aby te 0 wpisal w pola nasz program. Nastepnie ( po wpisaniu tych kilku liczb i reszty zer) program ma "wychwycic" w ktorym miejscu znajduja sie te liczby i jakie sa ich wartosci i zapisac je do pliku. jezeli to wysztsko bedzie zrobione to program ma sie zapytac uzytkownika o jakas liczbe, ktora bedzie wspolczynnikiem przez ktory wymnozymy te macierz i wynik zapiszemy w pliku (nowym pliku a w pliku maja byc rowniez same wartosci wraz z polozeniem tych wartosci w macierzy). sam jestem w stanie utowrzyc tablice dwuwymiarowa, zczytac jakies znaki z klawiatury. tylko ze najwiekszy problem to mam z instrukcjami bo przypuszczam ze one beda tak jakby rdzeniem programu a z tym sie jeszcze nie lapie do konca. bede wdzieczny za pomoc!!
Mi się wydaje, że reprezentacja tablicowa będzie do bani bo jak macierz ma 1000x1000 to pamięci może nie starczyć na taką operację. Po za tym jak będzie tylko 10 nie zerowych wartości w tej tablicy to będzie to marnowaniem pamięci przechowywanie takiej liczby zer. Dodatkowo tablica potrzebuje ciągłego obszaru pamięci co może być trudne do wygospodarowania przy dużych tablicach.
Moim zdaniem można rozwiązać problem stosując strukturę np.
struct rzadka{
int x;
int y;
int val;
};
Zerowych elementów oczywiście nie trzeba pamiętać.
Po utworzeniu struktury drzewiastej takich struktur będziemy mieli wszystkie nie zerowe elementy. Struktura drzewiasta zapewnia bardzo szybkie znalezienie elementu w drzewie, bo możemy dodawać elementy sortując je indeksami od razu. Trzeba by to opakować w ładne funkcje dostępu do danych tak żeby dostęp był realizowany poprzez indeksy.
Oczywiście takie rozwiązanie potrzebuje więcej pamięci na zapamiętanie jednego elementu bo musimy pamiętać oprócz wartości, jeszcze indeksy i dwa wskaźniki w strukturze drzewiastej, więc to rozwiązanie będzie opłacalne (przy założeniu, że wszystkie wartości i wskaźniki są np. 4 bajtowe) gdy liczba zer przekracza 5 krotnie liczbę pozostałych danych.
Bez sensu... totalne skomplikowanie problemu. Jak zrobimy tablice (tworząc dynamicznie, pamięci starczy nam nawet na miliardy komórek ) dostęp do elementów mamy natychmiastowy, podając po prostu indeksy. A w tym co kolega wyżej zaproponował, to nie dość że marnotrawienie miejsca (bierzemy najgorszy przypadek, czyli że będą prawie same jedynki) bo będzie zajmowała znacznie więcej miejsca, to na dodatek czas wyszukiwania będzie kosmicznie większy niż przy zwyczajnej tablicy, gdzie odwołujemy się bezpośrednio do elementu.
Pomijam już fakt, jak bardzo komplikuje to bardzo prosty programik... po co do czegoś takiego implementować drzewo?!
Podaje tutaj taki drobny przykład, reszte funkcjonalności można sobie samemu dopracować (jakieś tam operacje, zapisywanie do pliku itd...), mam nadzieje że o to chodziło Oczywiście macierz może być reprezentowana przez strukture, która w swoich polach zawiera dwuwymiarową tablice i np. wymiary x oraz y. To tylko taki szkic
Code:
#include <stdio.h>
#include <stdlib.h>
int main()
{
int x,y,i,j,a,b;
int **macierz;
Aha, i bym zapomniał... nie wiem jakie są założenia projektowe, ale po skończeniu korzystania z naszej macierzy (kiedy to nie będą nam już potrzebne dane siedzące w niej i np. użyjemy tego wskaźnika do utworzenia nowej macierzy) warto by zwolnić zajmowane przez nią zasoby, bo inaczej dojdzie do tak zwanego wycieku pamięci
lord_dagoth: poczytaj najpierw o macierzach rzadkich, bo twoje rozwiązanie z nimi nie ma nic kompletnie wspólnego. Rozwiązałeś problem dla macierzy zwykłych a nie rzadkich. Jeżeli masz tablicę o rozmiarach 10000 x 10000 i chcesz w niej przechowywać 50 zwykłych 4 bajtowych intów to Twoje rozwiązanie wykorzysta 400 mega pamięci a moje tylko 250 bajtów. Po za tym jak masz np. 512 mega ramu to możesz mieć duży problem z przydziałem tak dużej tablicy w pamięci. Twoja tablica będzie potrzebować 400 mega ciągłego obszaru pamięci. Wyobraź sobie swoje rozwiązanie na mikroprocesorze co ma np. 32 kilo ramu. Do reprezentacji macierzy rzadkich stosuje się właśnie różne algorytmy i struktury żeby zapobiec marnotrawstwu pamięci.
Sądząc po treści zadania to nie wydaje mi się, że nauczycielowi (czyli zadanie do szkoły?) chodziło o zaimplementowanie drzewa, a już tym bardziej nie o tworzenie tablicy o takich wymiarach...
Poza tym:
Program musi zapamiętac jakie to były i w których miejscach się one znajdowały, a następnie dane te zapisać do plik
Już to sugeruje, żeby pamiętać indeksy dla każdej nie zerowej liczby. Jestem pewny, że chodzi o reprezentację macierzy rzadkiej a nie zwykłej zresztą takie jest polecenie. Nie wiem jakim sposobem, ja podałem tylko rozwiązanie problemu, które zapewnia dość szybki dostęp do elementów. Najprostszy sposób to zrobienie tablic o wymiarze 3xN, gdzie N to liczba nie zerowych liczb. Pierwsze dwie wartości wiersza to byłby indeks, a następne to wartość liczby. Tylko, że to rozwiązanie jest mało optymalne bo wyszukiwanie jest rzędu O(n) a nie tak jak w przypadku drzewa O(sqrt(n)).
Quote:
Program musi sam wpisac 0 do macierzy
Wydaje mi się, że chodzi tylko o reprezentację 0 tak żeby model zwracał zera dla innych elementów.
Myślę, że kolega b-krupa sam wybierze najlepsze dla siebie rozwiązanie, bo patrząc na zdanie:
b-krupa wrote:
prosze o pomoc bo nie wiem od czego zaczac a na czym skonczyc. z C nie potrafię za wiele, a zrobić musze.
nie jestem do końca pewien, czy implementacja drzewa i związanych z nim funkcjami w C jest najlepszym pomysłem
No, a tak poza tym, to treść zadania potraktowałem DOSŁOWNIE, bo doświadczenie mnie nauczyło, że jak prowadzący coś powiedział, to miał na myśli DOSŁOWNIE to co powiedział A jako że kolega trzykrotnie powtórzył to założenie:
b-krupa wrote:
Program musi sam wpisac 0 do macierzy
b-krupa wrote:
z tego co mowil mi nauczyciel to program ma zadbac o to aby te 0 wpisal w pola nasz program. Nastepnie ( po wpisaniu tych kilku liczb i reszty zer)
ekstra, dzieki postaram sie teraz te informacje przeanalizowac i posklejac, nie spodziewalem sie takiego odzewu. jakbyscie mieli jeszcze jakies spostrzezenia badz uwagi - prosze - piszcie. dzieki jeszcze raz. zawsze to latwiej i blizej do celu.
To że program ma "wpisać" 0 we wszystkie pola nie musi oznaczać, że wszystkie komórki muszą się znaleźć w pamięci. Zależy na jakim poziomie abstrakcji operujemy: jeśli struktura przechowuje macierz (w jakiejś tam postaci), to chodzi o to, aby odczyt jakąś tam funkcją komórek które nie zostały przypisane dawał wartość równą 0 (lub dowolną inną, którą można przechować w zmiennej lub stałej). Funkcja może stwierdzić: "to pole nie istnieje, a więc zakłada się, że jest równe 0". Z poziomu funkcji dostępowych są prawie same zera, z poziomu struktury żadnych zer nie ma. Zresztą: operacje jak mnożenie macierzy rzadkich nie miało by żadnego sensu, gdyby przechowywać wszystkie komórki - wszystkie optymalizacje uzyskuje się dopiero wtedy, kiedy wiadomo które pola są niezerowe - obliczenia dla pozostałych pól można uciąć.
Drzewo może być trudne dla początkującego, styknie lista takich strukturek jak ktoś wyżej opisał (x,y,val), wtedy wyszukiwanie jest O(n) zamiast O(log n) za to dodawanie jest w czasie O(1) zamiast O(log n)
Zamieszczam prostą demonstracje działania programu na listach, ale wiadomo że nie ma tutaj co liczyć na dużą efektywność. Mamy drastycznie zmniejszone użycie pamięci kosztem zwiększenia czasu wyszukiwania danego indeksu, ale przynajmniej jest proste w implementacji Może wieczorem zamieszcze na drzewach poszukiwań binarnych, bo gdzieś miałem implementacje w C napisaną, tylko tam trzeba będzie już pomyśleć trochę więcej nad reprezentacją tej macierzy. W sumie mam też drzewa czerwono-czarne, ale nie chce mi się już ich modyfikować i potem sprawdzać, czy wszystko działa, bo jeszcze się okaże, że listy bądź tablice wystarczą do tego zadania i będzie to zdecydowany przerost formy nad treścią
printf("Ile chcesz wprowadzic do macierzy liczb roznych od zera? ");
scanf("%d",&a);
for(i=0;i<a;i++)
{
printf("Podaj wspolrzedne liczby oraz jej wartosc(x spacja y spacja val): ");
scanf("%d %d %d",&x,&y,&b);
//utworzenie nowego wezla listy
tempNode=(listNode*)malloc(sizeof(listNode));
tempNode->nextElement=NULL;
tempNode->previousElement=NULL;
tempNode->value=b;
tempNode->x=x;
tempNode->y=y;
//dowiazanie wezla do listy
if(myMatrix.myList.numberOfElements==0)
{
myMatrix.myList.firstElement=tempNode;
myMatrix.myList.lastElement=tempNode;
}
else
{
myMatrix.myList.lastElement->nextElement=tempNode;
tempNode->previousElement=myMatrix.myList.lastElement;
myMatrix.myList.lastElement=tempNode;
}
myMatrix.myList.numberOfElements++;
}
) dostęp do elementów mamy natychmiastowy, podając po prostu indeksy. A w tym co kolega wyżej zaproponował, to nie dość że marnotrawienie miejsca (bierzemy najgorszy przypadek, czyli że będą prawie same jedynki) bo będzie zajmowała znacznie więcej miejsca, to na dodatek czas wyszukiwania będzie kosmicznie większy niż przy zwyczajnej tablicy, gdzie odwołujemy się bezpośrednio do elementu.
