Új hozzászólás Aktív témák

• #2377 cucka addikt Gerghu #2374

  Új Válasz 2006-12-07 08:32:48 #2377

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  cucka

  addikt

  válasz Gerghu #2374 üzenetére

  c-ben gondolkozva:
  
  a 10ezer csúcs miatt célszerű éllistával ábrázolni, ott pedig nem probléma a memórialimit.
  csúcsoknak lefoglalod előre a memóriát, akkor ugye tömbként kezeled, és a tömb indexe fogja megmutatni az illető csúcs ''nevét''. minden csúcsból kiindul egy lista, ami tartalmazza az éleket. egy élnek van végpontja, ami egy int és rákövetkező csúcsa, ami egy csúcsra mutató pointer, vagyis egy csúcs mérete nagyjából 12byte, össszes csúcs így 240kbyte-ot foglal. ha nagyon szorít az időlimit, akkor eltárolhatod minden csúcsnál az utolsó élre mutató pointert, így a beszúrás n idő helyett 1 idő alatt megtörténik.
  
  az élmátrix az egyébként micsoda? én csak a csúcsmátrixot és az éllistát ismerem/használtam.
  
  listákról minden könyvben olvashatsz, de a gúgle is sok hasznos találatot dob, főleg ha angolul keresel. ennek fényében nem értem, mi a probléma a file-ból való lista felépítéssel. (kulcsszó: linked list).

• #2376 Jester01 veterán Gerghu #2374

  Új Válasz 2006-12-07 02:40:30 #2376

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Jester01

  veterán

  válasz Gerghu #2374 üzenetére

  Hacsak egyéb ok nincs rá akkor a gráfot egyszerûen csomópontokkal és belõlük induló élekkel ábrázoljuk:
  
  class Node
  {
  public:
  vector<Node*> Edges;
  };
  
  Ez nálam mérve 12 byte csomópontonként, az kemény 120kB. A 200000 pointer az 800kB. A legrosszabb vector overhead-del számolva is belefér 2 megába az egész (64 bites gépen max. dupla ennyi).
  
  Ha valami egyéb információt is el kell tárolni a csomópontokról/élekrõl akkor az persze erre még rájön, de azt semmiképp nem úszod meg.
  
  (Az éleknek az egyszerûség kedvéért nem csináltam külön osztályt.)

Új hozzászólás Aktív témák