Elektroda.pl
Elektroda.pl
X

Search our partners

Find the latest content on electronic components. Datasheets.com
Elektroda.pl
Please add exception to AdBlock for elektroda.pl.
If you watch the ads, you support portal and users.

[C] program tworzący macierz rzadką w C

b-krupa 02 Jun 2009 15:06 3936 12
  • #1
    b-krupa
    Level 10  
    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.
  • #2
    lord_dagoth
    Level 25  
    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).
  • #3
    b-krupa
    Level 10  
    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!!
  • #4
    User removed account
    User removed account  
  • #5
    lord_dagoth
    Level 25  
    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 :P
    Code:
    #include <stdio.h>
    
    #include <stdlib.h>
    int main()
    {
       int x,y,i,j,a,b;
       int **macierz;

       printf("Podaj wymiary macierzy (x spacja y): ");
       scanf("%d %d",&x,&y);

       //dynamiczne utworzenie macierzy
       macierz=(int**)malloc(sizeof(int*)*y);
       for(i=0;i<y;i++)
          macierz[i]=(int*)malloc(sizeof(int)*x);

       //wyzerowanie macierzy
       for(i=0;i<y;i++)
          for(j=0;j<x;j++)
             macierz[i][j]=0;

       printf("Ile chcesz wprowadzic jedynek? ");
       scanf("%d",&i);
       for(j=0;j<i;j++)
       {
          printf("Podaj wspolrzedne %d. jedynki (x spacja y): ",j+1);
          scanf("%d %d",&a,&b);
          macierz[b-1][a-1]=1;
       }
       printf("Wypisanie macierzy:\n");
       for(i=0;i<y;i++)
       {
          for(j=0;j<x;j++)
             printf("%d",macierz[i][j]);
          putchar('\n');
       }

        return 0;
    }


    Jeżeli chodzi o zerowanie tablic, to można to wykonać szybciej, np. memset'em ( http://www.cplusplus.com/reference/clibrary/cstring/memset/ ), ale to można wprowadzić w późniejszej fazie optymalizacji, o ile taka będzie potrzebna :P

    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 :P
  • #6
    User removed account
    User removed account  
  • #7
    lord_dagoth
    Level 25  
    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:
    b-krupa wrote:
    Program musi sam wpisac 0 do macierzy
  • #8
    User removed account
    User removed account  
  • #9
    lord_dagoth
    Level 25  
    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)

    to się jego trzymałem ;)
  • #10
    b-krupa
    Level 10  
    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.
  • #11
    BoskiDialer
    Level 34  
    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ąć.
  • #12
    lukego
    Level 17  
    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)
  • #13
    lord_dagoth
    Level 25  
    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ą :P
    Code:
    #include<stdio.h>
    
    #include<stdlib.h>

    typedef struct _listNode
    {
       int x,y,value;
       struct _listNode *nextElement;
       struct _listNode *previousElement;
    } listNode;

    typedef struct _list
    {
       listNode *firstElement;
       listNode *lastElement;
       int numberOfElements;
    } list;

    typedef struct _matrix
    {
       list myList;
       int x,y;
    } matrix;

    int main()
    {
       int a,b,i,j,x,y;
       matrix myMatrix;
       listNode *tempNode;

       myMatrix.myList.firstElement=NULL;
       myMatrix.myList.lastElement=NULL;
       myMatrix.myList.numberOfElements=0;

       printf("Podaj wymiary macierzy (x spacja y): ");
       scanf("%d %d",&myMatrix.x,&myMatrix.y);

       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++;
       }

       printf("\nWypisanie powstałej macierzy:\n");
       for(i=0;i<myMatrix.y;i++)
       {
          for(j=0;j<myMatrix.x;j++)
          {
             //wyszukanie elementu, o podanych wspolrzednych
             tempNode=myMatrix.myList.firstElement;
             while(tempNode!=NULL)
             {
                if(tempNode->x==j+1 && tempNode->y==i+1)
                   break;
                else
                   tempNode=tempNode->nextElement;
             }
             if(tempNode!=NULL)
                printf("%d",tempNode->value);
             else
                putchar('0');
          }
          putchar('\n');
       }

       return 0;
    }