Obsadzenie co drugiego indeksu na liście w C++

0

Witam,
mam problem z listą w C++. Mam do zaimplementowania algorytm szeregowania zadań na dwóch maszynach, gdzie tylko na pierwszej występują dziury(wyłączenie maszyny na konserwację) o stałej długości. Przerwy pomiędzy dziurami mogą mieć dowolną wartość. Algorytm ma zwrócić rozwiązanie z najmniejszym opóźnieniem - stąd jedna ze zmiennych to deadline. Wpadłem na taki pomysł aby maszyny były reprezentowane przez listy obiektów. Obiektów będą dwa typy - dziury i zadania. Na poniższym kodzie znajduje się moja próba umiejscowienia dziur na pierwszej maszynie. Chciałbym aby dziury zajmowały co drugi indeks czyli 0,2,4,6... itd. Niech pozostałe "wolne" indeksy będą dla zadań. Oczywiście może być tak że zadanie nie zmieści się w którąś z przerw pomiędzy dziurami - tutaj chciałem dać ifa, o błędnej instancji.
Reasumując:
Czy jest możliwe wstawienie obiektów na co drugie miejsca na liście, a potem wstawienie kolejnych w przerwy?
Drugie pytanie, czy będzie możliwe przeprowadzenie wszystkich możliwych permutacji obiektów-zdań bez "dotykania" dziur? Zastosuję algorytm brue force, ale zoptymalizuję go poprzez dodanie ograniczenia górnego i dolnego.
Oto kod:

 
#include <iostream>
#include <string>
#include <list>
#include <fstream>
#include <cstddef>
using namespace std;
class Zadanie
{
    public:
    int index, czas_wyk, deadline, okres;
    bool czy_zadanie;
    Zadanie(int czas_wyk, int okres){}
    Zadanie(int index, int okres, int czas_wyk, int deadline, bool czy_zadanie){}
};

int main()
{
    int index, czas_wyk, deadline, okres;
    bool czy_zadanie;
    list<Zadanie>::iterator i;
    list<Zadanie> M1;
    list<Zadanie> M2;
    int q=0;
    i = M1.begin();
   while(q != 3)
   {
       cin >> czas_wyk >> okres;
       czy_zadanie = false;
       Zadanie *dziura = new Zadanie(czas_wyk, okres);
       //M1.push_back(*dziura);
       M1.insert(i,*dziura);
       i++;
       i++;
       q++;
    }
    for(list<Zadanie>::iterator iter=M1.begin(); iter != M1.end(); ++iter)
    {
        cout << iter->czas_wyk << " " << iter->okres << endl;
    }
    cout << M1.size();


    return 0;
}

0

Do listy można łatwo wstawiać.

0

Może jakaś podpowiedź? plx ;p

0

Aha, dzięki za zmarnowany czas idę na inne forum ;>

0

to po co jest to forum?

0

to naprowadź, dobra nara, nie było tematu

0

lol nie mój kod? okeeej, wiesz ze wklepałem w google list insert C++ kilka razy? widzę, że po prostu nie wiesz co jest w kodzie nie tak, a może po prostu przedstawiłem opis problemu w zbyt skomplikowany dla Ciebie sposób? Nie mam czasu na takie dyskusje. Program zwraca "śmieci" z pamięci, a ja chciałbym tylko żeby zwrócił podane przeze mnie wartości na indeksach 0 2 i 4

0

Jak chcesz zwrócić podane przez Ciebie wartości to uzupełnij konstruktor tej klasy.

0

jeżeli dziury występują tylko na jednej z maszyn, użyj kolejnego vectora do zapisania tam dziur

0

Może rzeczywiście twój kod, w takim razie to powinno pomóc:

#include <iostream>
#include <list>
using namespace std;

class Item
  {
   private:
   int value;
   public:
   Item(int value=0):value(value) {}
   int Value()const { return value; }
  };

int main()
  {
   list<Item> Lst;
   for(int i=1;i<=3;++i) Lst.push_back(Item(i));
   for(list<Item>::iterator i=Lst.begin();i!=Lst.end();++i) cout<<i->Value()<<endl;
   cout<<endl;
   for(list<Item>::iterator i=Lst.begin();++i!=Lst.end();Lst.insert(i,Item(0))) {}
   for(list<Item>::iterator i=Lst.begin();i!=Lst.end();++i) cout<<i->Value()<<endl;
   return 0;
  }
0

Jeśli to zadanie na studiach to zrób do tego jakąś ładną wizualizację, bo takie rozwiązanie jedno-funkcyjne to trochę mało.

Poza tym:

  • nie opisałeś do czego służą elementy klasy Zadanie
  • używasz jednej linii do zapisania kilku atrybutów
  • gdy obsadzasz klasę w kontenerze to dobrze jest zdefiniować przynajmniej konstruktor kopiujący
  • atrybuty klasy są publiczne, więc defacto może to być też struktura

Zgadza się, możesz zrobić dwa typy obiektów (zadania i dziury), ale czy zastanowiłeś się jak reprezentować niezagospodarowaną przestrzeń?

Bo lista sama w sobie nie obsługuje przerw, możesz jedynie je jakoś symulować, masz kilka możliwości:

  • przez dodanie atrybutu "data i czas startu zadania/dziury"
  • poprzez dodanie atrybutu "długość niezagospodarowanego czasu po zadaniu/dziurze"
  • poprzez dodanie atrybutu "int typ_zadania;" - jeśli = 3 to jest to niezagospodarowany czas
0

Dziękuję za pomoc! Już się zabieram za poprawki! ;>

0

Mam jeszcze jedną prośbę o wskazówkę. Chciałbym odwoływać się do obiektów będących na poprzednim indeksie (i-1) niż ten rozważany w pętli. Potrzebuję tego ponieważ na dziurze znajduje się informacja o wolnej przestrzeni będącej pomiędzy dziurami. Jeśli długość zadania przewyższy długość "wolnego" okresu program musi o tym poinformować i przerwać działanie. Iteracja jak w tablicach wiadomo nie działa, i-1... Próbowałem z next i prev ale też bez skutku. Czy jest możliwość wykonania takiej operacji na listach jednokierunkowych? Dodam jeszcze, że pierwszym obiektem na maszynie - liscie jest dziura.

 
int j =0;
   for(list<Item>::iterator i=Lst.begin();i!=Lst.end();++i)
   {
       j = i -1; //poprzedni indeks, dziura z informacja o przerwie
       if(i->Czas()==0 && i->Okres()==0 && i->Indeks()==0 && i->Deadline()==0)  // jesli 'wolne' mniejsce
        if((j)->Okres()>=a) //jesli okres wiekszy rowny dlugosci zadania
    {

       {
           i = Lst.erase(i);
           cin >> a >> b >> c >> d; //wczytaj wartosci pol obiektu z klawiatury
           Lst.insert(i,Item(a,b,c,d)); //wstaw w wolne miejsce
       }

       }
   }
1

Tu masz przykład do std::list.insert: http://www.cplusplus.com/reference/list/list/insert/

ale:

  • nie wczytuj a skoro użyłeś tej zmiennej do wyszukania dziury
  • jeśli robisz insert taki jak zrobiłeś to upewnij się że masz konstruktor kopiujący (i/lub operator przypisania)
  • wartość j nie istnieje dla pierwszego wykonania pętli
  • coś tu masz za dużo klamerek
  • poprzedni indeks po prostu przechowuj osobno:
   list<Item>::iterator j = Lst.end();

   for(list<Item>::iterator i=Lst.begin();i!=Lst.end();++i)
   {
       if(i->Czas()==0 && i->Okres()==0 && i->Indeks()==0 && i->Deadline()==0)  // jesli 'wolne' mniejsce
        if((j != Lst.end()) && ((j)->Okres()>=a)) //jesli okres wiekszy rowny dlugosci zadania
        {
          i = Lst.erase(i);
          cin >> a >> b >> c >> d; //wczytaj wartosci pol obiektu z klawiatury
          Lst.insert(i,Item(a,b,c,d)); //wstaw w wolne miejsce
        }

    j = i; //poprzedni indeks, dziura z informacja o przerwie
  }

Poprawności całości nie sprawdzałem.

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