Problem z tablicą struktur.

secretservice112
2012-11-25 15:14
secretservice112
0

Witam. Mam zaimplementować graf w postaci połączonych list sąsiadów.
Ma to wyglądać w implementacji jak na rysunku na stronie 9 z tego linku:
ftp://sith.ict.pwr.wroc.pl/Teleinformatyka/BOT/4_Wyklad_Grafy.pdf

// piotr.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    struct E
    {
        int nr_wierzcholka;
        int waga;
        // wskaznik na kolejny wierzcholek wychodzacy z danego
        E* Next;
    };

    // przypisane na stale do testow
    int liczba_wierzcholkow=5;

    // utworzenie tablicy wskaznikow (poszczegolne elementy odpowiadaja wierzcholkom)
    E* List = new E [liczba_wierzcholkow];
    for (int i=0; i<liczba_wierzcholkow; i++)
    {
        List[i]; // tutaj uzupelnic na co wskazywac ma ten wskaznik

    }

    // deklaracja tablicy struktur
    E** tablica_list = new E* [liczba_wierzcholkow];
    for (int i=0; i<liczba_wierzcholkow; i++)
    {
        tablica_list[i]=new E[liczba_wierzcholkow];
    }

    // przypisywanie wartosci polom struktury
    for (int i=0; i<liczba_wierzcholkow; i++)
    {
        for (int j=0; j<liczba_wierzcholkow; j++)
        {

            tablica_list[i][j].nr_wierzcholka=i;
            tablica_list[i][j].waga=i;

            // jezeli nie ma wiecej wychodzacyh wierzcholkow to wstaw NULL
            if (i==(liczba_wierzcholkow-1))
            {
                tablica_list[i][j].Next=NULL;
            }
            else
            {
            // wskaznik na nastepny element tablicy struktur
            tablica_list[i][j].Next=List+i+1;
            }
        }
    }

    // do poprawy
    E* temp = new E;
    temp=List;

    while (temp!=NULL)
    {
        cout << temp->nr_wierzcholka;
        cout << "\n";
        cout << temp->waga;
        cout << "\n";

        temp=temp->Next;
        //temp++;
    }

    // usuwanie
    for (int i=0; i<liczba_wierzcholkow; i++)
    {
        delete [] tablica_list[i];
    }
    delete [] tablica_list;

    return 0;
}

Mógłbym prosić o jakieś wskazówki jak to sensownie zaimplementować? Nie jestem mistrzem programowania, a rzucili nas od razu na dość głęboką wodę i ciężko mi dojść do rozwiązania tego problemu.

edytowany 1x, ostatnio: olesio, 2016-12-13 18:26

Pozostało 580 znaków

2012-11-25 17:54

Rejestracja: 14 lat temu

Ostatnio: 17 godzin temu

0
#include <iostream>
#include <sstream>
using namespace std;

struct E
  {
   int nr_wierzcholka;
   int waga;
   E *Next;
  };

int main()
  {
   stringstream s("1 2 5 1 3 3 1 4 4 1 6 9 2 1 3 2 6 -8 3 1 3 4 2 4",ios::in);
   int liczba_wierzcholkow=6;
   E **Wezly=new E*[liczba_wierzcholkow+1]; // Wezly - nie używamy
   for(int i=0;i<=liczba_wierzcholkow;++i) Wezly[i]=0;
   int from,to,weight;
   while(s>>from>>to>>weight)
     {
      E *tmp=new E;
      tmp->nr_wierzcholka=to;
      tmp->waga=weight;
      tmp->Next=Wezly[from];
      Wezly[from]=tmp;
     }
   for(int i=1;i<=liczba_wierzcholkow;++i)
     {
      cout<<i<<':'<<endl;
      for(E *tmp=Wezly[i];tmp;tmp=tmp->Next)
        {
         cout<<"\t=> "<<tmp->nr_wierzcholka<<'('<<tmp->waga<<')'<<endl;
        }
     }   
   cin.sync(); cin.get();
   return 0;
  }

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

secretservice112
2012-11-25 23:21
secretservice112
0

A jeżeli chciałbym w ten sposób zaimplementować dowolny graf to wystarczy do tego stringstreama dopisać więcej wartości? Można to zrobić jakoś w sposób automatyczny? Bo program z założenie ma liczyć dla dużych grafów, tak aby potem dało się zaimplementować algorytm prima na tej strukturze. I jakbyś mógł to bardzo bym był wdzięczny za parę linijek komentarza do programu, bo nie wszystko jest dla mnie tutaj oczywiste.

Pozostało 580 znaków

2012-11-25 23:39

Rejestracja: 14 lat temu

Ostatnio: 17 godzin temu

0

Zamiast stringstream możesz użyć cin lub iftream. lub to co w while włożyć do funkcji z parametrami int from,to,weight;
Jeżeli działasz na grafie z ukierunkowanymi krawędziami to ok z tym że lepiej to zawrzeć do jakieś klasy.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

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