Граф в виде списка смежностей

302

19 декабря 2016, 19:55

UPD: Переписал код и не пойму, почему вылетает на for(j = gr[i].list.begin(); j != gr[i].list.end(); ++j)

Сам код http://pastebin.com/aHsGD2GK

Объявляю структуры

struct tlist {
    int inf;
    tlist *next;
};
struct orgraph {
    int top;
    tlist *first;
};
void insert(orgraph *gr, int x, int y) {
    tlist *cur = gr[x].first;
    tlist *pr = NULL;
    tlist* now = new tlist;
    now->inf = y;
    now->next = NULL;
    while(cur != NULL) {
        pr = cur;
        cur = cur->next;
    }
    if(pr == NULL) {
        gr[x].first = now;
    } 
    else {
        pr->next = now;
    }
}

И вроде всё хорошо, но мне нужно удалить дугу соединяющую вершины a и b. И тут я в ступоре, как поступить. Понимаю, что

  void delete_xy(orgraph *gr, int x, int y) {
     tlist *tmp = gr[x].first;
}

Ну а как же мне стереть Y ?

Answer 1

@Error, может быть более ясная формулировка вопроса:

Как удалить элемент односвязного списка с заданным ключем?

(Ключ - это inf в структуре tlist)

поможет Вам самостоятельно ее решить?

Чуть подскажу - при удалении надо помнить адрес предыдущего элемента списка.

Еще один маленький совет: для быстрой вставки в конец списка модифицируйте структуру

struct orgrahp {
   int top;
   tlist *first, *last;
};

А еще лучше - перейдите на двусвязный список.

Answer 2

Ээх, ударьте чем-нибудь вашего учителя по голове, например, книгой Страуструпа...

Но вы хоть опишите, какой смысл структуры tlist, а то без вдумчивого разбора кода непонятно.

Ну, std::vector там, std::set, или на крайний случай std::list. Для набора рёбер логично использовать std::set<edge*>, где edge — структура, представляющая ребро.