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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
doorss
0 / 0 / 0
Регистрация: 19.08.2013
Сообщений: 14
#1

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

04.01.2014, 15:35. Просмотров 687. Ответов 13
Метки нет (Все метки)

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

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]);

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

Массив указателей на заголовки списков - C++
Добрый день нужно реализовать подобный класс Список у меня реализован следующим образом: template &lt;typename T&gt; class elem { ...

Шаблон структуры данных - массив указателей на заголовки списков - C++
Мне выдали задание на курсовую работу: &quot;Шаблон структуры данных - массив указателей на заголовки списков. Элемент списка содержит...

Вывести количество вершин неориентированного графа, смежных с данной - C++
Есть задание по с++ совершенно не понимаю как делать. Кому не сложно, напишите прогу: Создать граф, используя список смежности....

Массив указателей на массив строк и сортировка массива указателей - C++
Добрый день. Поступил вопрос. Есть задача. У нас встроенный массив char mass;.Мы вводим строки до тех пор, пока не будет заполнен массив...

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

Создать специализацию для шаблона, которая принимает массив указателей на строки и количество этих указателей - C++
Нужно создать специализацию для шаблона, которая принимает массив указателей на строки и количество этих указателей. Эта специализация...

13
outoftime
║XLR8║
510 / 432 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
04.01.2014, 15:49 #2
Цитата Сообщение от doorss Посмотреть сообщение
list*&first
Это немного лишнее

Весь код в студию.
0
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;
}
0
outoftime
║XLR8║
510 / 432 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
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║
510 / 432 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
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";
    }
}
Теперь вопрос зачем тебе этот список и как ты его хочешь использовать?
0
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) ===|
0
outoftime
║XLR8║
510 / 432 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
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
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;
}
Но почему то не работает такая конструкция. Видимо, я не понимаю как имеено возвратить этот массив структур.

и потом следом, функция которая все это дело выводит.
0
outoftime
║XLR8║
510 / 432 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
04.01.2014, 17:19 #10
BTW: если вы хотите создать массив ваших структур list **array, т.е. массив указателей на структуры
0
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]);
    }
0
__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;
    }
}
Я, как видите, храню граф списком вершин, в каждой из которых - список выходящих из нее ребер.
0
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]);
    }
0
__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
и тд).

ну как-то так...
0
05.01.2014, 04:05
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.01.2014, 04:05
Привет! Вот еще темы с ответами:

Массив из указателей на масив из указателей на массив из int) - C++
Доброго времени суток! Возникла проблема - как на C++ создать массив из указателей на массив из указателей на int? То есть массив из n...

Чем отличаются двумерный символьный массив и массив указателей на строки - C++
Двумерный символьный массив и массив указателей на строки. Собственно чем они отличаются? Заранее спасибо.

опп класс и массив (создать массив указателей по выборке животных, участвующих в забеге) - C++
Здравствуйте! Есть задача... вкратце. Нужно создать массив указателей по выборке животных участвующих в забеге. Это Лошадь, Крокодил,...

Массив строк как массив указателей на массивы чаров - C++
Я всё правильно сделал? char* Files; Files = &quot;AHEAD&quot;; Files = &quot;LEFT&quot;; Files = &quot;RIGHT&quot;; Files = NULL; int searchFile()...


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

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru