Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
doorss
0 / 0 / 0
Регистрация: 19.08.2013
Сообщений: 14
04.01.2014, 15:35     Массив указателей списков смежных вершин #1
Добрый день. Помогите пожалуйста в реализации списка смежности для графа. Знаю, в инете много примеров, но пока для своего не нашел подходящего. Вот у меня есть структура:

C++
1
2
3
4
struct list {
    int n;
    list *next;
};
для этой структуры определенны две функции, добавление элемента в конец и вывод списка.

В void main

C++
1
list* first[csize];
C++
1
2
3
4
5
6
  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]);

Что делается не так, у меня выдает ошибку связанную с указателями. Как грамотней все это реализовать?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.01.2014, 15:35     Массив указателей списков смежных вершин
Посмотрите здесь:

Массив из указателей на масив из указателей на массив из int) C++
C++ по поводу указателей. Как правильно задавать массив указателей и его удалять?
Массив строк как массив указателей на массивы чаров C++
C++ Шаблон структуры данных - массив указателей на заголовки списков
опп класс и массив (создать массив указателей по выборке животных, участвующих в забеге) C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
04.01.2014, 15:49     Массив указателей списков смежных вершин #2
Цитата Сообщение от doorss Посмотреть сообщение
list*&first
Это немного лишнее

Весь код в студию.
doorss
0 / 0 / 0
Регистрация: 19.08.2013
Сообщений: 14
04.01.2014, 15:56  [ТС]     Массив указателей списков смежных вершин #3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#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
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
04.01.2014, 16:15     Массив указателей списков смежных вершин #4
doorss, STL можно?
doorss
0 / 0 / 0
Регистрация: 19.08.2013
Сообщений: 14
04.01.2014, 16:26  [ТС]     Массив указателей списков смежных вершин #5
да.
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
04.01.2014, 16:43     Массив указателей списков смежных вершин #6
doorss, матрицу смежности я бы сделал так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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
0 / 0 / 0
Регистрация: 19.08.2013
Сообщений: 14
04.01.2014, 16:56  [ТС]     Массив указателей списков смежных вершин #7
outoftime , прошу прощение. Я думал, под stl вы имеете ввиду не вектор, а стандартный list. Мне хочется через списки реализовать. Это ведь не сложно. Всего надо сделать одномерный массив, размерности кол-во вершин, и чтобы он хранил указатели на начало нескольких списков. В свою очередь каждый список из матрицы смежности заполняется. У меня проблема вышла, когда я начал создавать функцию которая возвращает такой одномерный массив. И в итоге у меня ничего не вышло.

Добавлено через 8 минут
C++
1
2
3
4
5
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
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
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 интерфейс доступа по индексу и т.д.
doorss
0 / 0 / 0
Регистрация: 19.08.2013
Сообщений: 14
04.01.2014, 17:13  [ТС]     Массив указателей списков смежных вершин #9
я бы хотел бы так реализовать, причем с помощью своего списка. Это в идеальном варианте.

Задумка такова: В классе мы имеем функцию, которая возвращает нам этот массив списков.
C++
1
2
3
4
5
6
7
8
9
/* Эта функция в классе*/
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
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
04.01.2014, 17:19     Массив указателей списков смежных вершин #10
BTW: если вы хотите создать массив ваших структур list **array, т.е. массив указателей на структуры
doorss
0 / 0 / 0
Регистрация: 19.08.2013
Сообщений: 14
04.01.2014, 17:54  [ТС]     Массив указателей списков смежных вершин #11
т.е так

C++
1
2
3
4
5
6
7
8
    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++
1
2
3
4
5
6
7
8
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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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++
1
2
3
4
5
6
7
8
9
10
11
12
13
    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__
24 / 24 / 3
Регистрация: 04.01.2014
Сообщений: 91
Завершенные тесты: 2
04.01.2014, 18:05     Массив указателей списков смежных вершин #12
Цитата Сообщение от outoftime Посмотреть сообщение
Я пока не совсем понимаю зачем надо хранить список смежности если уже есть матрица смежности.
При хранении графа матрицей смежности расход памяти - O(n^2), где n - количество вершин.
При этом, если граф мало заполнен, т. е. ребер относительно немного, то в матрице смежности будет много нулей - несуществующих ребер, под которые расходуется память.
Поэтому матрицей смежности имеет смысл хранить только почти полный граф.

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

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

ХЕДР:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#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
0 / 0 / 0
Регистрация: 19.08.2013
Сообщений: 14
04.01.2014, 21:40  [ТС]     Массив указателей списков смежных вершин #13
__General__, спасибо за код, но мне бы хотелось услышать, где выше приведенном в моем коде ошибка, чтобы понять, что я не так делаю. Реализаций много, у меня по другому чуть сделано.

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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++
1
2
3
4
5
6
7
8
9
10
11
12
13
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]);
    }
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.01.2014, 04:05     Массив указателей списков смежных вершин
Еще ссылки по теме:

Создать специализацию для шаблона, которая принимает массив указателей на строки и количество этих указателей C++
Создать специфицированный шаблон функции, принимающей массив указателей на char и количество самих указателей C++
Двумерный символьный массив и массив указателей на строки C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
__General__
24 / 24 / 3
Регистрация: 04.01.2014
Сообщений: 91
Завершенные тесты: 2
05.01.2014, 04:05     Массив указателей списков смежных вершин #14
Ну в 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
и тд).

ну как-то так...
Yandex
Объявления
05.01.2014, 04:05     Массив указателей списков смежных вершин
Ответ Создать тему
Опции темы

Текущее время: 01:27. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru