Тема: Проходження графу в ширину.

Компілятор не видає помилку... Але й програма не виконується. Скоріш за все написав якусь дурню. Подивіться будь ласка.

#include <conio.h>
#include <iostream>
#include <string>
using namespace std;
struct station {
    station* commonst;
    string namest;
    int way;
};
struct list {
    station* station;
    list* next;
};
void listt(list**first,station *roll) {
    list* fsroll = *first;
    if (fsroll->next == nullptr) {
        fsroll->next = new list;
        fsroll = fsroll->next;
        fsroll->station = roll;
        fsroll->next = nullptr;
    }
    else {
        while (fsroll->next!= nullptr) {
            fsroll = fsroll->next;
        }
        fsroll->next = new list;
        fsroll = fsroll->next;
        fsroll->station = roll;
        fsroll->next = nullptr;
    }
    

}

void mainnlist(station** main, int num,list **mainlistst) {
    if ((*mainlistst) == nullptr) {
        cout << "Введіть назву станції із якої Ви хочете обійти лінії метро в ширину: ";
        string name;
        cin >> name;
        for (int i = 0; i < num; i++) {
            if ((*main)->namest == name) {
                (*mainlistst) = new list;
                (*mainlistst)->station =(*main);
                (*mainlistst)->next = nullptr;
            }
        }
        
    }
    else {
        if ((*mainlistst) != nullptr) {

            list* filist = (*mainlistst);
            while (filist) {
                station* save = filist->station;
                while (save) {
                    listt(&filist, save);
                    save = save->commonst;
                }
                filist = filist->next;
            }
            

        }
    }

}
void printlist(list* print) {
    list* nm = print;
    while (nm) {
        cout << nm->station->namest;
        nm = nm->next;
    }
}
void print(station** mainst,int num) {
    for (int i = 0; i < num; i++) {
        cout << "Назва " << i + 1 << "-ої станції метро: " << mainst[i]->namest << endl;
    }
}
void cincommonst(station*** mainst, int num) {
    for (int i = 0; i < num; i++) {
        cout << "Введіть к-сть суміжніх пересадок для станції " << (*mainst)[i]->namest << ": ";
        int numm;
        cin >> numm;
        station* newst = (*mainst)[i];
        for (int q = 0; q < numm; q++) {
            cout << "Введіть назву " << q + 1 << "-ої пересадки із станції: " << (*mainst)[i]->namest << ": ";
            if (newst->commonst == nullptr) {
                (newst)->commonst = new station;
                (newst) = (newst)->commonst;
                cin >> (newst)->namest;
                cout << "Введіть довжину  " << q + 1 << "-ої пересадки із станції: " << (*mainst)[i]->namest << ": ";
                cin >> (newst)->way;
                newst->commonst = nullptr;
            }
            else {
                while (newst->commonst) {
                    newst = newst->commonst;
                }
                (newst)->commonst = new station;
                (newst) = (newst)->commonst;
                cin >> (newst)->namest;
                cout << "Введіть довжину  " << q + 1 << "-ої пересадки із станції: " << (*mainst)[i]->namest << ": ";
                cin >> (newst)->way;
                newst->commonst = nullptr;
            }
        }
        cout << endl;
    }
}

void printcommonst(station** mainst, int num) {

    for (int i = 0; i < num; i++) {
        station* printst = mainst[i];
        while (printst->commonst) {
            printst = printst->commonst;
            cout << "Із станції " << mainst[i]->namest << " можна патрапити у станцію " << printst->namest << " із довжиною шляху: " << printst->way << " км." << endl;
        
        }
        cout << endl;
    }
}

int main(void) {
    setlocale(LC_ALL, "Ukr");
    station** mainst = nullptr;
    list* mainlist = nullptr;
    list* list = nullptr;
    int num;
    cout << "Введіть к-сть станцій: ";
    cin >> num;
    mainst = new station * [num];
    for (int i = 0; i < num; i++) {
        cout << "Введіть назву " << i + 1 << "-ої станції метро: ";
        mainst[i] = new station;
        string name;
        cin >> name;
        mainst[i]->namest = name;
        mainst[i]->commonst = nullptr;
        mainst[i]->way = NULL;
    }
    print(mainst, num);
    cincommonst(&mainst, num);
    printcommonst(mainst, num);
    mainnlist(mainst, num, &mainlist);
    mainnlist(mainst, num, &mainlist);
    printlist(mainlist);
    _getch();
    return 0;
}

2

Re: Проходження графу в ширину.

де ТЗ?

3

Re: Проходження графу в ширину.

Прочитай про те як використовувати дебагер.

Тобі потрібно поставити брейкпоінт на початку функції main, або на тому місці де ти думаєш що може виникнути "зависання".

Пройдися покроково та виясни що саме не так в твоєму коді.

Для того щоб хтось тобі більш конкретніше відповів, принаймні скажи що цей код мав робити.

4 Востаннє редагувалося ch0r_t (06.12.2020 19:14:32)

Re: Проходження графу в ширину.

А...нащо ви намагаєтеся назвати поле так само як і новий тип(struct)?

struct list {
    station* station;
    list* next;
};

І чого ви не викладете вивід компілятору, дозвольте запитати? Чи навіть попереджень немає? Який це у вас компілятор, -clang? які параметри?

Прихований текст

*Компілювати не намагався бо воно явно не для Linux написане...

#include <conio.h> // мурашки по шкірі.
void cincommonst(station*** mainst, int num){} //плавно переходять в нервовий тік

5 Востаннє редагувалося Львовский сырник в мульти (06.12.2020 19:22:38)

Re: Проходження графу в ширину.


варіанта    Граф    Вершини    Ребра


7    Метро    Станції    Пересадки
Ось все завдання. Потрібно пройти граф в ширину. Знову ж таки як придумав так написав. Ось вся метода.

При пошуку "спочатку в ширину" для збереження вершин використовується черга, а не стек. Ітераційний процес продовжується доти, поки черга не спорожніє.
Видалити вершину V з черги і перевірити її наявність у списку оброблених вершин. Якщо вершини V немає в списку L, уключити її в цей список. Одночасно одержати всі суміжні з V вершини і вставити в чергу ті з них, що відсутні в списку оброблених вершин.
Якщо застосувати цей алгоритм до розглянутого в попередньому прикладі графу, то вершини будуть оброблятися в наступному порядку:



Я не знаю що таке Т3.
Про дебагер почитаю не знав.

6

Re: Проходження графу в ширину.

Почитайте, як треба оформлювати питання. Бо судячи з опису

Львовский сырник в мульти написав:

Компілятор не видає помилку... Але й програма не виконується

Ви або не увімкнули комп'ютер, або не запускали компілятор. Принаймні, я не бачу в цьому описі нічого, що б могло виключити цю проблему.

Re: Проходження графу в ширину.

tchort написав:

А...нащо ви намагаєтеся назвати поле так само як і новий тип(struct)?

struct list {
    station* station;
    list* next;
};

І чого ви не викладете вивід компілятору, дозвольте запитати? Чи навіть попереджень немає? Який це у вас компілятор, -clang? які параметри?

Прихований текст

*Компілювати не намагався бо воно явно не для Linux написане...

#include <conio.h> // мурашки по шкірі.
void cincommonst(station*** mainst, int num){} //плавно переходять в нервовий тік

А що там не так? Крім назви. Цікаво просто. visual studio використовую.

8 Востаннє редагувалося Львовский сырник в мульти (08.12.2020 15:17:28)

Re: Проходження графу в ширину.

.

9 Востаннє редагувалося Львовский сырник в мульти (08.12.2020 15:42:31)

Re: Проходження графу в ширину.

Переробив я функцію для пошуку в ширину, але видає помилку не можу виправити.

station** getname(station*** mainst, int num) {
    cout << "Введіть назву станції із якої Ви хочете почати обхід ліній метро в ширину: ";
    string name;
    cin >> name;
    station** mst = *mainst;
    for (int i = 0; i < num; i++) {
        if (mst[i]->namest == name) {
            return &mst[i];
        }
    }
}
station** search(station*** mainst, int num,station*nm) {
    station** mst = *mainst;
    for (int i = 0; i < num; i++) {
        if (mst[i]->namest == nm->namest) {
            return &mst[i];
        }
    }
}
void stlist( list** queue, list** main,station***mainst,int num) {
    station* sst = *getname(mainst, num);
    if ((*queue) == nullptr && *(main)== nullptr) {
        (*queue) = new list;
        (*queue)->st = sst;
        (*queue)->next = nullptr;
        (*main) = new list;
        (*main)->st = (*queue)->st;
        (*main)->next = nullptr;
    }

    while ((*queue)!= nullptr) {
        
        bool add = false;
        list* qlist = (*queue);
        list* mlist = (*main);
       station* save = (*queue)->st;
        while (mlist->next) {
            if (mlist->st == (*queue)->st) {
                save = (*queue)->st;
                add = false;
      
                break;
            }
            else {
                save = (*queue)->st;
                add = true;
                mlist = mlist->next;
            }
        }
        if (add == true) {
            while (mlist->next) {
                mlist = mlist->next;
            }
            mlist->next = new list;
            mlist->st = save;
            mlist->next = nullptr;
        }
   station* addd = *search(mainst, num, save);
        while (addd->commonst) {
            qlist = (*queue);
            while (qlist->next) {
                qlist = qlist->next;
            }
            qlist->next = new list; ------------------------------>Возникло необработанное исключение по адресу 0x76C29962 в lab8.1.1.exe: исключение Microsoft C++: std::bad_alloc по адресу памяти 0x00B7F9D8.
            qlist->st = save->commonst;
            qlist->next = nullptr;
            addd = addd->commonst;
        }
        if ((*queue)->next) {
        (*queue) = (*queue)->next;
    }
    }
}
void printlist(list** main) {
    list* plist = *main;
    while (plist->next) {
        cout << plist->st;
        plist = plist->next;
    }
}

10 Востаннє редагувалося koala (08.12.2020 15:45:41)

Re: Проходження графу в ширину.

std::bad_alloc - це значить, що пам'ять скінчилася. Чому? Сказати складно, код надто заплутаний, але, скажімо, ось тут

            mlist->next = new list;
            mlist->st = save;
            mlist->next = nullptr;

явно пам'ять тече. Настільки явно, що, швидше за все, про це навіть компілятор має попереджати. Коли вам уже не потрібна пам'ять - не забувайте її звільняти за допомогою delete.

Розкладіть усю роботу зі списком на окремі маленькі операції. Створення та ініціалізація - одна функція. Видалення елементу зі списку - друга. Пошук - третя. Обмін - четверта. І т.д. Вам самому буде значно легше.

Re: Проходження графу в ширину.

Виправив помилку, але цикл працює лиш раз чудеса. Дякую.

Re: Проходження графу в ширину.

Ось весь код

#include <conio.h>
#include <iostream>
#include <string>
using namespace std;
struct station {
    station* commonst;
    string namest;
    int way;
};
struct list {
    station* st;
    list* next;
};
station** getname(station*** mainst, int num) {
    cout << "Введіть назву станції із якої Ви хочете почати обхід ліній метро в ширину: ";
    string name;
    cin >> name;
    station** mst = *mainst;
    for (int i = 0; i < num; i++) {
        if (mst[i]->namest == name) {
            return &mst[i];
        }
    }
}
station** search(station*** mainst, int num,station*nm) {
    station** mst = *mainst;
    for (int i = 0; i < num; i++) {
        if (mst[i]->namest == nm->namest) {
            return &mst[i];
        }
    }
}
void stlist( list** queue, list** main,station***mainst,int num) {
    station* sst = *getname(mainst, num);
    if ((*queue) == nullptr && *(main)== nullptr) {
        (*queue) = new list;
        (*queue)->st = sst;
        (*queue)->next = nullptr;
        (*main) = new list;
        (*main)->st = (*queue)->st;
        (*main)->next = nullptr;
    }
    
    while ((*queue)) {
        
        
        bool add = false;
        list* qlist = (*queue);
        list* mlist = (*main);
        station* save = (*queue)->st;
        while (mlist->next) {
            if (mlist->st == (*queue)->st) {
                
                add = false;
                mlist = mlist->next;
            }
            else {
                
                add = true;
                mlist = mlist->next;
            }
        }
        if (add == true) {
            while (mlist->next) {
                mlist = mlist->next;
            }
            mlist->next = new list;
            mlist = mlist->next;
            mlist->st = save;
            mlist->next = nullptr;
        }
        station* addd = *search(mainst, num, save);

        while (addd) {
            cout << addd->namest;
            if (qlist->next) {
                while (qlist->next) {
                    qlist = qlist->next;
                }
            }
            qlist->next = new list;
            qlist->st = addd->commonst;
            qlist->next = nullptr;
            addd = addd->commonst;
        }
        (*queue) = (*queue)->next;
        
    }
}
void printlist(list* main) {
    list* plist = main;
    while (plist->next) {
        cout << plist->st->namest;
        plist = plist->next;
    }
}


void print(station** mainst,int num) {
    for (int i = 0; i < num; i++) {
        cout << "Назва " << i + 1 << "-ої станції метро: " << mainst[i]->namest << endl;
    }
}
void cincommonst(station*** mainst, int num) {
    for (int i = 0; i < num; i++) {
        cout << "Введіть к-сть суміжніх пересадок для станції " << (*mainst)[i]->namest << ": ";
        int numm;
        cin >> numm;
        station* newst = (*mainst)[i];
        for (int q = 0; q < numm; q++) {
            cout << "Введіть назву " << q + 1 << "-ої пересадки із станції: " << (*mainst)[i]->namest << ": ";
            if (newst->commonst == nullptr) {
                (newst)->commonst = new station;
                (newst) = (newst)->commonst;
                cin >> (newst)->namest;
                cout << "Введіть довжину  " << q + 1 << "-ої пересадки із станції: " << (*mainst)[i]->namest << ": ";
                cin >> (newst)->way;
                newst->commonst = nullptr;
            }
            else {
                while (newst->commonst) {
                    newst = newst->commonst;
                }
                (newst)->commonst = new station;
                (newst) = (newst)->commonst;
                cin >> (newst)->namest;
                cout << "Введіть довжину  " << q + 1 << "-ої пересадки із станції: " << (*mainst)[i]->namest << ": ";
                cin >> (newst)->way;
                newst->commonst = nullptr;
            }
        }
        cout << endl;
    }
}

void printcommonst(station** mainst, int num) {

    for (int i = 0; i < num; i++) {
        station* printst = mainst[i];
        while (printst->commonst) {
            printst = printst->commonst;
            cout << "Із станції " << mainst[i]->namest << " можна патрапити у станцію " << printst->namest << " із довжиною шляху: " << printst->way << " км." << endl;
        
        }
        cout << endl;
    }
}

int main(void) {
    setlocale(LC_ALL, "Ukr");
    station** mainst = nullptr;
    list* mainlist = nullptr;
    list* list = nullptr;
    int num;
    cout << "Введіть к-сть станцій: ";
    cin >> num;
    mainst = new station * [num];
    for (int i = 0; i < num; i++) {
        cout << "Введіть назву " << i + 1 << "-ої станції метро: ";
        mainst[i] = new station;
        string name;
        cin >> name;
        mainst[i]->namest = name;
        mainst[i]->commonst = nullptr;
        mainst[i]->way = NULL;
    }
    print(mainst, num);
    cincommonst(&mainst, num);
    printcommonst(mainst, num);
    stlist(&list, &mainlist, &mainst, num);
    printlist(mainlist);
    _getch();
    return 0;
}
Подякували: ch0r_t1

13 Востаннє редагувалося koala (08.12.2020 17:14:41)

Re: Проходження графу в ширину.

Навмання

            cout << "Введіть назву " << q + 1 << "-ої пересадки із станції: " << (*mainst)[i]->namest << ": ";
            if (newst->commonst == nullptr) {
                (newst)->commonst = new station;
                (newst) = (newst)->commonst;
                cin >> (newst)->namest;
                cout << "Введіть довжину  " << q + 1 << "-ої пересадки із станції: " << (*mainst)[i]->namest << ": ";
                cin >> (newst)->way;
                newst->commonst = nullptr;
            }
            else {
                while (newst->commonst) {
                    newst = newst->commonst;
                }
                (newst)->commonst = new station;
                (newst) = (newst)->commonst;
                cin >> (newst)->namest;
                cout << "Введіть довжину  " << q + 1 << "-ої пересадки із станції: " << (*mainst)[i]->namest << ": ";
                cin >> (newst)->way;
                newst->commonst = nullptr;
            }

У вас тут 2/3 коду повторюються. Оскільки повторення в кінці if-ів, винесемо з if і об'єднаємо:

            cout << "Введіть назву " << q + 1 << "-ої пересадки із станції: " << (*mainst)[i]->namest << ": ";
            if (newst->commonst == nullptr) {
            }
            else {
                while (newst->commonst) {
                    newst = newst->commonst;
                }

            }
            (newst)->commonst = new station;
            (newst) = (newst)->commonst;
            cin >> (newst)->namest;
            cout << "Введіть довжину  " << q + 1 << "-ої пересадки із станції: " << (*mainst)[i]->namest << ": ";
            cin >> (newst)->way;
            newst->commonst = nullptr;

Перша гілка не потрібна, міняємо умову на протилежну:

            cout << "Введіть назву " << q + 1 << "-ої пересадки із станції: " << (*mainst)[i]->namest << ": ";
            if (newst->commonst != nullptr) {
                while (newst->commonst) {
                    newst = newst->commonst;
                }

            }
            (newst)->commonst = new station;
            (newst) = (newst)->commonst;
            cin >> (newst)->namest;
            cout << "Введіть довжину  " << q + 1 << "-ої пересадки із станції: " << (*mainst)[i]->namest << ": ";
            cin >> (newst)->way;
            newst->commonst = nullptr;

if і while перевіряють, по суті, одну умову, їх можна об'єднати:

            while (newst->commonst) {
                newst = newst->commonst;
            }
            (newst)->commonst = new station;
            (newst) = (newst)->commonst;
            cin >> (newst)->namest;
            cout << "Введіть довжину  " << q + 1 << "-ої пересадки із станції: " << (*mainst)[i]->namest << ": ";
            cin >> (newst)->way;
            newst->commonst = nullptr;

Краса, правда? І я не перевіряв код усередині - лише глянув, що він однаковий. А якщо ви створите конструктор для station і функцію додавання в кінець списку, то це можна буде записати приблизно як

            cout << "Введіть назву " << q + 1 << "-ої пересадки із станції: " << (*mainst)[i]->namest << ": ";
            std::string namest;
            cin >> namest;
            cout << "Введіть довжину  " << q + 1 << "-ої пересадки із станції: " << (*mainst)[i]->namest << ": ";
            int wat;
            cin >> way;
            insert_last(newst, new station(namest, way, nullptr));

Правда, приємніше? Особливо якщо функцію для введення додасте.

Re: Проходження графу в ширину.

Звісно дякую. Але проблема не там. Мені вибиває що черга постійно пуста після виконання циклу (while((*queue))).

15

Re: Проходження графу в ширину.

Ну вибачте, я вам кажу, що ваш код складно читати. Поприбирайте його, одразу стане зрозуміло, де проблема. Ви не економите час, намагаючися продертися крізь поганий код замість переписати його, принаймні, місцями.

16 Востаннє редагувалося Львовский сырник в мульти (08.12.2020 21:04:27)

Re: Проходження графу в ширину.

Попробував переписати і стиснути. Але все одно вибиває  помилку що черга пуста, хоча я виділив пам'ять і помістив туди дані. Перегляньте будь ласка.

#include <conio.h>
#include <iostream>
#include <string>
using namespace std;


struct station {
  station* commonst;
  string namest;
  int way;
};


struct list {
  station* st;
  list* next;
};


station** getname(station*** mainst, int num) {
  cout << "Введіть назву станції із якої Ви хочете почати обхід ліній метро в ширину: ";
  string name;
  cin >> name;
  station** mst = *mainst;
  for (int i = 0; i < num; i++) {
    if (mst[i]->namest == name) {
      return &mst[i];
    }
  }
}


station** search(station*** mainst, int num, station* nm) {
  station** mst = *mainst;
  for (int i = 0; i < num; i++) {
    if (mst[i]->namest == nm->namest) {
      return &mst[i];
    }
  }
}


bool add(station* qst, list* main) {
  bool ret = true;
  if (main == nullptr) {
    return true;
  }
  if (main->next == nullptr) {
    if (qst->namest == main->st->namest) {
      return false;
    }
  }
  else {
    while (main->next) {
      if (qst->namest == main->st->namest) {
        return false;
      }
      else {
        main = main->next;
      }
    }
    if (ret == true) {
      return true;
    }
  }
}


void mlist(list** main,station*stt) {
  if ((*main) == nullptr) {
    (*main) = new list;
    (*main)->st = (stt);
    (*main)->next = nullptr;
  }
  else {
    list* last = (*main);
    while (last->next!= nullptr) {
      last = last->next;
    }
    last->next = new list;
    last = last->next;
    last->st = (stt);
    last->next = nullptr;
  }
}


void qlist(list** queue, station* stt) {
  if ((*queue) == nullptr) {
    (*queue) = new list;
    (*queue)->st = (stt);
    (*queue)->next = nullptr;
  }
  else {
    list* last = (*queue);
    while (last->next != nullptr) {
      last = last->next;
    }
    last->next = new list;
    last = last->next;
    last->st = (stt);
    last->next = nullptr;
  }
}  


void stlist(list** queue, list** main, station*** mainst, int num) {
  station* sst = *getname(mainst, num);
  if ((*queue) == nullptr) {
    (*queue) = new list;
    (*queue)->st = sst;
    (*queue)->next = nullptr;
    while ((*queue)) {
      station* addd = *search(mainst, num, (*queue)->st);
      bool addmlist = add(addd, (*main));
      if (addmlist == true) {
        mlist(main, addd);
      }
      while (addd != nullptr) {
        bool addqlist = add(addd, (*main));
        if (addqlist == true) {
          qlist(queue, addd);
        }
        addd = addd->commonst;
      }
      (*queue) = (*queue)->next;
    }
  }
}


void printlist(list* main) {
  list* plist = main;
  while (plist->next) {
    cout << plist->st->namest;
    plist = plist->next;
  }
}


void print(station** mainst, int num) {
  for (int i = 0; i < num; i++) {
    cout << "Назва " << i + 1 << "-ої станції метро: " << mainst[i]->namest << endl;
  }
}


void cincommonst(station*** mainst, int num) {
  for (int i = 0; i < num; i++) {
    cout << "Введіть к-сть суміжніх пересадок для станції " << (*mainst)[i]->namest << ": ";
    int numm;
    cin >> numm;
    station* newst = (*mainst)[i];
    for (int q = 0; q < numm; q++) {
      cout << "Введіть назву " << q + 1 << "-ої пересадки із станції: " << (*mainst)[i]->namest << ": ";
      if (newst->commonst == nullptr) {
        (newst)->commonst = new station;
        (newst) = (newst)->commonst;
        cin >> (newst)->namest;
        cout << "Введіть довжину  " << q + 1 << "-ої пересадки із станції: " << (*mainst)[i]->namest << ": ";
        cin >> (newst)->way;
        newst->commonst = nullptr;
      }
      else {
        while (newst->commonst) {
          newst = newst->commonst;
        }
        (newst)->commonst = new station;
        (newst) = (newst)->commonst;
        cin >> (newst)->namest;
        cout << "Введіть довжину  " << q + 1 << "-ої пересадки із станції: " << (*mainst)[i]->namest << ": ";
        cin >> (newst)->way;
        newst->commonst = nullptr;
      }
    }
    cout << endl;
  }
}


void printcommonst(station** mainst, int num) {

for (int i = 0; i < num; i++) {
    station* printst = mainst[i];
    while (printst->commonst) {
      printst = printst->commonst;
      cout << "Із станції " << mainst[i]->namest << " можна патрапити у станцію " << printst->namest << " із довжиною шляху: " << printst->way << " км." << endl;

    }
    cout << endl;
  }
}


int main(void) {
  setlocale(LC_ALL, "Ukr");
  station** mainst = nullptr;
  list* mainlist = nullptr;
  list* list = nullptr;
  int num;
  cout << "Введіть к-сть станцій: ";
  cin >> num;
  mainst = new station * [num];
  for (int i = 0; i < num; i++) {
    cout << "Введіть назву " << i + 1 << "-ої станції метро: ";
    mainst[i] = new station;
    string name;
    cin >> name;
    mainst[i]->namest = name;
    mainst[i]->commonst = nullptr;
    mainst[i]->way = NULL;
  }
  print(mainst, num);
  cincommonst(&mainst, num);
  printcommonst(mainst, num);
  stlist(&list, &mainlist, &mainst, num);
  printlist(mainlist);
  
  
  _getch();
  return 0;
}

17

Re: Проходження графу в ширину.

В якому саме рядку вибиває?

Re: Проходження графу в ширину.

Я через телефон не можу сказати номер рядку... Функція stlist. Рядок while(*queue) - тут

19

Re: Проходження графу в ширину.

Не бачу, чому. З того, що я бачу:

void stlist(list** queue, ...
...
stlist(&list, ...

Змінна list (про яку вам вже ніби робили зауваження) більше ніде в main не використовується. Нащо вона там проголошена? Викиньте параметр, перенесіть її в stlist як локальну змінну. Купа зірочок зникає.

20 Востаннє редагувалося Львовский сырник в мульти (09.12.2020 20:14:54)

Re: Проходження графу в ширину.

Ну чисто cout сила . Я звісно клоун, але знайшов помилку у фунції add провтикав else і тому bool завжи видавав false і цикл працював лиш раз. Дякую за поради буду акуратнішим.

#include <conio.h>
#include <iostream>
#include <string>
using namespace std;


struct station {
    station* commonst;
    string namest;
    int way;
};


struct list {
    station* st;
    list* next;
};


station** getname(station*** mainst, int num) {
    cout << "Введіть назву станції із якої Ви хочете почати обхід ліній метро в ширину: ";
    string name;
    cin >> name;
    station** mst = *mainst;
    for (int i = 0; i < num; i++) {
        if (mst[i]->namest == name) {
            return &mst[i];
        }
    }
}


station** search(station*** mainst, int num, station* nm) {
    station** mst = *mainst;
    for (int i = 0; i < num; i++) {
        if (mst[i]->namest == nm->namest) {
            return &mst[i];
        }
    }
}


bool add(station* qst, list* main) {
    bool ret = true;
    if (main == nullptr) {
        return true;
    }
    else {


        if (main->next == nullptr) {
            if (qst->namest == main->st->namest) {
                return false;
            }
            else {
                return true;
            }
        }
        else {
            while (main!= nullptr) {
                if (qst->namest == main->st->namest) {
                    return false;
                }
                else {
                    main = main->next;
                    ret = true;
                }
            }
            if (ret == true) {
                return true;
            }
        }
    }
}


void mlist(list** main,station*stt) {
    if ((*main) == nullptr) {
        (*main) = new list;
        (*main)->st = (stt);
        (*main)->next = nullptr;
    }
    else {
        list* last = (*main);
        while (last->next!= nullptr) {
            last = last->next;
        }
        last->next = new list;
        last = last->next;
        last->st = (stt);
        last->next = nullptr;
    }
}


void qlist(list** queue, station* stt) {
    if ((*queue) == nullptr) {
        (*queue) = new list;
        (*queue)->st = (stt);
        (*queue)->next = nullptr;
    }
    else {
        list* last = (*queue);
        while (last->next != nullptr) {
            last = last->next;
        }
        last->next = new list;
        last = last->next;
        last->st = (stt);
        last->next = nullptr;
    }
}  


void stlist(list** queue, list** main, station*** mainst, int num) {
    station* sst = *getname(mainst, num);
    
        (*queue) = new list;
        (*queue)->st = sst;
        (*queue)->next = nullptr;
        while ((*queue)) {
            station* addd = *search(mainst, num, (*queue)->st);
            bool addmlist = add(addd, (*main));
            if (addmlist == true) {
                mlist(main, addd);
                addd = addd->commonst;
            }
            
            while (addd != nullptr) {
                
                bool addqlist = add(addd, (*main));
                
                if (addqlist == true) {
                    qlist(queue, addd);
                }
                addd = addd->commonst;
            }
            (*queue) = (*queue)->next;
        }
    
}


void printlist(list* main) {
    list* plist = main;
    cout << '||';
    while (plist) {
        cout << '->';
        cout << plist->st->namest;
        plist = plist->next;
    }
    cout << "||" << endl;
}


void print(station** mainst, int num) {
    for (int i = 0; i < num; i++) {
        cout << "Назва " << i + 1 << "-ої станції метро: " << mainst[i]->namest << endl;
    }
}


void cincommonst(station*** mainst, int num) {
    for (int i = 0; i < num; i++) {
        cout << "Введіть к-сть суміжніх пересадок для станції " << (*mainst)[i]->namest << ": ";
        int numm;
        cin >> numm;
        station* newst = (*mainst)[i];
        for (int q = 0; q < numm; q++) {
            cout << "Введіть назву " << q + 1 << "-ої пересадки із станції: " << (*mainst)[i]->namest << ": ";
            if (newst->commonst == nullptr) {
                (newst)->commonst = new station;
                (newst) = (newst)->commonst;
                cin >> (newst)->namest;
                cout << "Введіть довжину  " << q + 1 << "-ої пересадки із станції: " << (*mainst)[i]->namest << ": ";
                cin >> (newst)->way;
                newst->commonst = nullptr;
            }
            else {
                while (newst->commonst) {
                    newst = newst->commonst;
                }
                (newst)->commonst = new station;
                (newst) = (newst)->commonst;
                cin >> (newst)->namest;
                cout << "Введіть довжину  " << q + 1 << "-ої пересадки із станції: " << (*mainst)[i]->namest << ": ";
                cin >> (newst)->way;
                newst->commonst = nullptr;
            }
        }
        cout << endl;
    }
}


void printcommonst(station** mainst, int num) {

    for (int i = 0; i < num; i++) {
        station* printst = mainst[i];
        while (printst->commonst) {
            printst = printst->commonst;
            cout << "Із станції " << mainst[i]->namest << " можна патрапити у станцію " << printst->namest << " із довжиною шляху: " << printst->way << " км." << endl;

        }
        cout << endl;
    }
}


int main(void) {
    setlocale(LC_ALL, "Ukr");
    station** mainst = nullptr;
    list* mainlist = nullptr;
    list* list = nullptr;
    int num;
    cout << "Введіть к-сть станцій: ";
    cin >> num;
    mainst = new station * [num];
    for (int i = 0; i < num; i++) {
        cout << "Введіть назву " << i + 1 << "-ої станції метро: ";
        mainst[i] = new station;
        string name;
        cin >> name;
        mainst[i]->namest = name;
        mainst[i]->commonst = nullptr;
        mainst[i]->way = NULL;
    }
    print(mainst, num);
    cincommonst(&mainst, num);
    printcommonst(mainst, num);
    stlist(&list, &mainlist, &mainst, num);
    printlist(mainlist);
    
    
    _getch();
    return 0;
}