Массив указателей списков смежных вершин

@doorss · Регистрация: 19.08.2013

Author24 — интернет-сервис помощи студентам

Добрый день. Помогите пожалуйста в реализации списка смежности для графа. Знаю, в инете много примеров, но пока для своего не нашел подходящего. Вот у меня есть структура:

C++

struct list {
    int n;
    list *next;
};

для этой структуры определенны две функции, добавление элемента в конец и вывод списка.

В void main

C++

1	list* first[csize];

C++

  void listMatrix(list*&first) {
        for(int i=0; i<size; i++) {
            for(int j=0; j<size; j++) { if(adjacency_matrix[i][j]==1) add_el(first[i],j); }
    }
    }
void display(list* first) for(int i=0; i<size; i++) print_list(first[i]);

Что делается не так, у меня выдает ошибку связанную с указателями. Как грамотней все это реализовать?

@outoftime · 04.01.2014, 15:49

Сообщение от doorss

list*&first

Это немного лишнее

Весь код в студию.

@doorss · 04.01.2014, 15:56 **[ТС]**

C++

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <Windows.h>
#include <iostream>
#include <fstream>
#include <vector>
 
using namespace std;
 
struct list {
    int n;
    list *next;
};
 
list* add_el (list *first, int l) { /* функция добавляющая элемент */}
 
void print_list(list *first ) { /* функция выводящая список */}
 
class Graph {
    public:
    int size;
    int **adjacency_matrix;
 
    Graph(int csize, int**carray) {
        size=csize;
        adjacency_matrix= new int *[size];
        for (int i = 0; i < csize; i++) adjacency_matrix[i] = new int [csize];
        for(int i=0; i<size; i++) for (int j=0; j<size; j++) adjacency_matrix[i][j]=carray[i][j];
    }
   
 
    void listMatrix(list*&first) {
        for(int i=0; i<size; i++) {
            for(int j=0; j<size; j++) { if(adjacency_matrix[i][j]==1) add_el(first[i],j); }
    }
    }
    void display(list* first)
    {
        for(int i=0; i<size; i++) print_list(first[i]);
    }
};
 
 
int main()
{
   russian();
    int num=1;
 
 
ifstream iFile("input.txt", ios::in);
    int csize;
    iFile>>csize;
    int **carray = new int *[csize];
    for (int i = 0; i < csize; i++) carray[i] = new int [csize];
    for(int i=0; i<csize; i++) for (int j=0; j<csize; j++) iFile>>carray[i][j];
 
list* first[csize];
 
    return 0;
}

@outoftime · 04.01.2014, 16:15

doorss, STL можно?

@doorss · 04.01.2014, 16:26 **[ТС]**

да.

@outoftime · 04.01.2014, 16:43

doorss, матрицу смежности я бы сделал так:

C++

#include <iostream>
#include <vector>
#include <initializer_list>
 
class graph : public std::vector<std::vector<int>>
{
public:
    graph() : std::vector<std::vector<int>>() {}
    graph(const std::initializer_list<std::vector<int>> &list)
        : std::vector<std::vector<int>>(list) {}
};
 
int main()
{
    graph g = {
        {0,0,1},
        {1,0,0},
        {0,1,0}
    };
    for (const auto &row : g)
    {
        for (const auto &elem : row)
            std::cout << elem << " ";
        std::cout << "\n";
    }
}

Теперь вопрос зачем тебе этот список и как ты его хочешь использовать?

@doorss · 04.01.2014, 16:56 **[ТС]**

outoftime , прошу прощение. Я думал, под stl вы имеете ввиду не вектор, а стандартный list. Мне хочется через списки реализовать. Это ведь не сложно. Всего надо сделать одномерный массив, размерности кол-во вершин, и чтобы он хранил указатели на начало нескольких списков. В свою очередь каждый список из матрицы смежности заполняется. У меня проблема вышла, когда я начал создавать функцию которая возвращает такой одномерный массив. И в итоге у меня ничего не вышло.

Добавлено через 8 минут

C++

void listMatrix(list*&first) {
        for(int i=0; i<size; i++) {
            for(int j=0; j<size; j++) { if(adjacency_matrix[i][j]==1) add_el(first[i],j); } !!! - тут ругается первым делом!
    }
    }

||=== class-graph, Debug ===|
D:\class-graph\main.cpp||In member function 'void Graph::listMatrix(list*&)':|
D:\class-graph\main.cpp|127|error: cannot convert 'list' to 'list*' for argument '1' to 'list* add_el(list*, int)'|
D:\class-graph\main.cpp||In member function 'void Graph::display(list*)':|
D:\class-graph\main.cpp|132|error: cannot convert 'list' to 'list*' for argument '1' to 'void print_list(list*)'|
D:\class-graph\main.cpp||In function 'int main()':|
D:\class-graph\main.cpp|179|error: no matching function for call to 'Graph::display()'|
D:\class-graph\main.cpp|179|note: candidate is:|
D:\class-graph\main.cpp|130|note: void Graph::display(list*)|
D:\class-graph\main.cpp|130|note: candidate expects 1 argument, 0 provided|
D:\class-graph\main.cpp|154|warning: unused variable 'first' [-Wunused-variable]|
||=== Build finished: 3 errors, 1 warnings (0 minutes, 2 seconds) ===|

@outoftime · 04.01.2014, 17:06

doorss, написать то можно все что угодно, вопрос в том зачем оно надо.

Я пока не совсем понимаю зачем надо хранить список смежности если уже есть матрица смежности. Обычно надо одно из двух а не оба варианта сразу. Список смежности я обычно храню в std::vector<std::set<int>>, вместо std::set можете использовать std::list если по заданию оно лучше, только насколько я помню лучше использовать std::vector вместо std::list в силу того что прошлые версии STL давали низкую производительность для std::list, std::queue.

Добавлено через 5 минут

Сообщение от doorss

void listMatrix(list*&first) {
* * * * for(int i=0; i<size; i++) {
* * * * * * for(int j=0; j<size; j++) { if(adjacency_matrix[i][j]==1) add_el(first[i],j); } !!! - тут ругается первым делом!
* * }
* * }

Я не понимаю что выходите этим сделать, но если разименовать указатель first вы не получите указатель, это уже будет ссылка на объект, сразу вопрос если ли у first интерфейс доступа по индексу и т.д.

@doorss · 04.01.2014, 17:13 **[ТС]**

я бы хотел бы так реализовать, причем с помощью своего списка. Это в идеальном варианте.

Задумка такова: В классе мы имеем функцию, которая возвращает нам этот массив списков.

C++

/* Эта функция в классе*/
list* listMatrix() {
list* first[size];
 
for(int i=0; i<size; i++) {
            for(int j=0; j<size; j++) { if(adjacency_matrix[i][j]==1) first[i]=add_el(first[i],j); }
 }
return first;
}

Но почему то не работает такая конструкция. Видимо, я не понимаю как имеено возвратить этот массив структур.

и потом следом, функция которая все это дело выводит.

@outoftime · 04.01.2014, 17:19

BTW: если вы хотите создать массив ваших структур list **array, т.е. массив указателей на структуры

@doorss · 04.01.2014, 17:54 **[ТС]**

т.е так

C++

    list** listMatrix() {
        list** first[size];
 
        for(int i=0; i<size; i++) {
                for(int j=0; j<size; j++) { if(adjacency_matrix[i][j]==1) first[i]=add_el(first[i],j); }
        }
    return first;
    }

D:\class-graph\main.cpp|129|error: cannot convert 'list**' to 'list*' for argument '1' to 'list* add_el(list*, int)'|

Добавлено через 6 минут

C++

list** listMatrix() {
        list** first[size];
 
        for(int i=0; i<size; i++) {
                for(int j=0; j<size; j++) { if(adjacency_matrix[i][j]==1) *(first[i])=add_el(*(first[i]),j); }
        }
    return *(first); //* вот тут должен возвращаться массив указателей на структуры
    }

Добавлено через 19 минут
Вобщем вот, почему то вылетает. Правильно ли у меня заполняется массив?

C++

list* add_el (list *first, int m) {
        if(!first) {
            first=new list;
            first->n=m;
            first->next=0;
        }
        else {
            list *p=new list;
            p=first;
            while(p->next) {
            p=p->next;
            }
            list *w=new list;
            w->n=m;
            w->next=p->next;
            p->next=w;
        }
    return first;
}

C++

    list** listMatrix() {
        list** first[size];
 
        for(int i=0; i<size; i++) {
                for(int j=0; j<size; j++) { if(adjacency_matrix[i][j]==1) *(first[i])=add_el(*(first[i]),j); }
        }
    return *(first);
    }
 
    void display()
    {
        for(int i=0; i<size; i++) print_list(listMatrix()[i]);
    }

@__General__ · 04.01.2014, 18:05

Сообщение от outoftime

Я пока не совсем понимаю зачем надо хранить список смежности если уже есть матрица смежности.

При хранении графа матрицей смежности расход памяти - O(n^2), где n - количество вершин.
При этом, если граф мало заполнен, т. е. ребер относительно немного, то в матрице смежности будет много нулей - несуществующих ребер, под которые расходуется память.
Поэтому матрицей смежности имеет смысл хранить только почти полный граф.

Реализация списками смежности лучше тем, что при в этом случае мы не заказываем памяти под несуществующие ребра, и память здорово экономится.
(Расход памяти - O(n+m), где n - количество вершин в графе, m - кол-во ребер)

Добавлено через 9 минут
Нашел у себя реализацию:

ХЕДР:

C++

#ifndef GRAPH_H
#define GRAPH_H
 
#include <string>
 
using namespace std;
 
class edge;
class vertex;
class graph;
 
class edge
{
public:
    int price;
    edge *next_edge;
    vertex *neighbour;
 
    edge();
    edge(vertex*, vertex*, int);
    ~edge();
};
 
class vertex
{
public:
    string name;
    edge *edge_list;
    vertex *next_vert;
 
    vertex(string, vertex*);
    ~vertex();
};
 
class graph
{
public:
    vertex *vert_list;
    
    graph();
    ~graph();
 
    void add_edge(string, string, int);
    void del_edge(string, string);
    bool add_vert(string);
    bool del_vert(string);
private:
    int num_vert;
    int num_edge;
 
    vertex* SearchByName(string);
};
 
#endif

CPP:

C++

#include <iostream>
 
#include "Graph.h"
 
edge::edge()
{
    price = 0;
    next_edge = NULL;   
    neighbour = NULL;
}
 
edge::edge(vertex *vert_1, vertex *vert_2, int Price)
{
    price = Price;
    next_edge = vert_1->edge_list->next_edge;
    neighbour = vert_2;
}
 
edge::~edge()
{
}
 
 
vertex::vertex(string Name, vertex *NextVert)
{
    name = Name;
    priority = 0;
 
    edge_list = new edge;
    next_vert = NextVert;
 
    pred_vert = NULL;
}
 
vertex::~vertex()
{
}
 
int vertex::get_prior(vertex *pr_vert)
{
    if (pr_vert) {
        edge *cur_r = edge_list->next_edge;
        while (cur_r->neighbour != pr_vert) {
            cur_r = cur_r->next_edge;
        }
        return pr_vert->priority+cur_r->price;
    }
    else {
        return 0;
    }
}
 
 
graph::graph()
{
    vert_list = new vertex("0", NULL);
    Q = new queue;
 
    num_vert = 0;
    num_edge = 0;
}
 
graph::~graph()
{
    vertex *del_v = vert_list->next_vert, *cur_v = del_v->next_vert;
    while (del_v) {
        del_vert(del_v->name);
        del_v = cur_v;
        if (cur_v) {
            cur_v = cur_v->next_vert;
        }
    }
    delete vert_list;
 
    delete Q;
}
 
void graph::add_edge(string Name_1, string Name_2, int Price)
{
    vertex *vert_1 = SearchByName(Name_1);
    vertex *vert_2 = SearchByName(Name_2);
 
    vert_1->edge_list->next_edge = new edge(vert_1, vert_2, Price);
    vert_2->edge_list->next_edge = new edge(vert_2, vert_1, Price);
 
    num_edge++;
}
 
void graph::del_edge(string Name_1, string Name_2)
{
    vertex *vert_1 = SearchByName(Name_1);
    vertex *vert_2 = SearchByName(Name_2);
 
    edge *prev_r = vert_1->edge_list, *cur_r = vert_1->edge_list->next_edge;
    while (cur_r->neighbour != vert_2) {     //удаляем ребро из списка вершины vert_1. 
        prev_r = cur_r;
        cur_r = cur_r->next_edge;
    }
    prev_r->next_edge = cur_r->next_edge;
    delete cur_r;
 
    prev_r = vert_2->edge_list, cur_r = vert_2->edge_list->next_edge;
    while (cur_r->neighbour != vert_1) {     //удаляем ребро из списка вершины vert_2.
        prev_r = cur_r;
        cur_r = cur_r->next_edge;
    }
    prev_r->next_edge = cur_r->next_edge;
    delete cur_r;
 
    num_edge--;
}
 
bool graph::add_vert(string Name)
{
    vertex *check_v = SearchByName(Name);
 
    if (!check_v) {
        vert_list->next_vert = new vertex(Name, vert_list->next_vert);
        num_vert++;
 
        return true;
    }
    else {
        return false;
    }
}
 
bool graph::del_vert(string Name)
{
    vertex *del_v = SearchByName(Name);
 
    if (del_v) {
        if (del_v->edge_list->next_edge) {
            edge *del_r = del_v->edge_list->next_edge, *cur_r = del_r->next_edge;
            while (del_r) {
                del_edge(del_v->name, del_r->neighbour->name);  //удаляем инцидентные ребра.
                del_r = cur_r;
                if (cur_r) {
                    cur_r = cur_r->next_edge;
                }
            }
        }
 
        vertex *prev_v = vert_list, *cur_v = vert_list->next_vert;
        while (cur_v != del_v) { 
            prev_v = cur_v; 
            cur_v = cur_v->next_vert;
        }
        prev_v->next_vert = cur_v->next_vert;
        delete cur_v;     //удаляем саму вершину.
 
        num_vert--;
 
        return true;
    }
    else {
        return false;
    }
}

Я, как видите, храню граф списком вершин, в каждой из которых - список выходящих из нее ребер.

@doorss · 04.01.2014, 21:40 **[ТС]**

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

Добавлено через 3 часа 22 минуты
Помогите, я уже запутался, вылетает. Ошибка сегментации, возможно, я не правильно заполняю списки.

C++

list* add_el (list *first, int m) {
        if(!first) {
            first=new list;
            first->n=m;
            first->next=0;
        }
        else {
            list *p=new list;
            p=first;
            while(p->next) {
            p=p->next;
            }
            list *w=new list;
            w->n=m;
            w->next=p->next;
            p->next=w;
        }
    return first;
}

C++

list** listMatrix() {
        list** first[size];
 
        for(int i=0; i<size; i++) {
                for(int j=0; j<size; j++) { if(adjacency_matrix[i][j]==1) *(first[i])=add_el(*(first[i]),j); }
        }
    return *(first);
    }
 
    void display()
    {
        for(int i=0; i<size; i++) print_list(listMatrix()[i]);
    }

@__General__ · 05.01.2014, 04:05

Ну в add_el(...) я ошибок не нашел.
Единственное что - если вы хотите добавлять элементы в хвост списка, то было бы рационально помнить в самой структуре его хвост, чтобы не идти до последнего элемента каждый раз в цикле.
(В вашем случае добавление осуществляется за O(n), хотя можно за O(1)).
Ну или можно добавлять новые элементы в голову.

Теперь по поводу listMatrix().
Прежде всего, сразу бросается в глаза то, что тип возвращаемого значения не совпадает с объявленным типом функции: функция у вас имеет тип list**, а возвращаете вы *(first), то есть list*;
Потом, у вас ошибка при вызове add_el:

Сообщение от doorss

*(first[i])=add_el(*(first[i]),j);

first имеет тип list**, значит first[i] - list*, *(first[i]) - list. В то время как add_el - функция типа list*.
Собственно, у вас и в качестве аргумента add_elвыступает *(first[i]) вместо должного first[i].

Добавлено через 32 минуты
Ааа, я похоже неправильно понял. first у вас - массив указателей на указатель...
Короче, массив переменных типа list**, а не list*, как показалось мне сначала.
В таком случае, код, вроде, должен компилироваться.

Правда, я не совсем понимаю, зачем вы объявили такой массив... Вы, я так понял, хотите ,чтобы функция listMatrix() возвращала массив указателей на списки (то есть указатель на первый элемент массива, он же - его имя).
Однако, вы возвращаете первый(нулевой) элемент массива указателей на указатели на ваши списки, который не является указателем на первый элемент нужного массива.

PS
Сделайте first просто массивом указателей (list*).
Дальше подправьте все ,что нужно подправить (в конце тогда должно стоять просто

C++

1	return first

и тд).

ну как-то так...

@outoftime ║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,361 Записей в блоге: 5
	04.01.2014, 17:19	10
	BTW: если вы хотите создать массив ваших структур list **array, т.е. массив указателей на структуры 0

@outoftime ║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,361 Записей в блоге: 5
	04.01.2014, 15:49	2
	Сообщение от doorss list*&first Это немного лишнее Весь код в студию. 0

@outoftime ║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,361 Записей в блоге: 5
	04.01.2014, 16:15	4
	doorss, STL можно? 0

@doorss 0 / 0 / 0 Регистрация: 19.08.2013 Сообщений: 14
	04.01.2014, 16:26 [ТС]	5
	да. 0

@outoftime ║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,361 Записей в блоге: 5
	04.01.2014, 17:06	8
	doorss, написать то можно все что угодно, вопрос в том зачем оно надо. Я пока не совсем понимаю зачем надо хранить список смежности если уже есть матрица смежности. Обычно надо одно из двух а не оба варианта сразу. Список смежности я обычно храню в std::vector<std::set<int>>, вместо std::set можете использовать std::list если по заданию оно лучше, только насколько я помню лучше использовать std::vector вместо std::list в силу того что прошлые версии STL давали низкую производительность для std::list, std::queue. Добавлено через 5 минут Сообщение от doorss void listMatrix(list&first) { * * * for(int i=0; i<size; i++) { * * * * * * for(int j=0; j<size; j++) { if(adjacency_matrix[i][j]==1) add_el(first[i],j); } !!! - тут ругается первым делом! * * } * * } Я не понимаю что выходите этим сделать, но если разименовать указатель first вы не получите указатель, это уже будет ссылка на объект, сразу вопрос если ли у first интерфейс доступа по индексу и т.д. 0