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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Перевод из string в wstring. Неправильная кодировка http://www.cyberforum.ru/cpp-beginners/thread1062906.html
Здорова господа! Перевожу строку из string в wstring, в строке русские символы и они выводятся в консоли не крякозябрами а просто палочками. От код: #include <iostream> using std::wcout; using std::cout; using std::endl; #include <io.h>
C++ Алгоритм Дейкстры Что-то у меня Дейкстра не работает... прошу помощи у вас... Сам уже часа 1.5 сижу и не могу найти ошибку...#include <iostream> #include <cstring> #include <cmath> #include <stack> #include <queue> using namespace std; int n,m,a,s,f,p,h; bool used; int res; http://www.cyberforum.ru/cpp-beginners/thread1062900.html
C++ Шифрование методом цезаря
Здравствуйте, прошу вас о помощи. Это может показаться наглым, но, мне срочно нужна помощь с курсовым проектом, дело в том что с горем пополам я написал программу для шифрования методом цезаря, но меня ждал сюрприз, препод огорчил меня тем что нужно было делать все на билдере или подобие ему. Отправила на перездачу, а времени по просту не хватает, очень надеюсь на вашу помощь, нужна форма с...
Нужно заменить последнюю заглавную букву в строке на слово "Kukushechka" C++
То есть программа должна сама искать последнюю заглавную букву, определять ее номер в строке, ставить вместо нее и последующего текста слово "Kukushechka". В таком состоянии она только определяет номер и никак не хочет заменять. #include "stdafx.h" #include <conio.h> #include <stdio.h> #include <string.h> #include <iostream> using namespace std; char f( char *g, char* kuk);
C++ Странное поведение cin http://www.cyberforum.ru/cpp-beginners/thread1062879.html
Перегружаю оператор ввода следующим образом: #include <iostream> using namespace std; class Vector2D { public: long double x, y;
C++ Однонаправлений список. Операції: “[]” видалити елемент в заданій позиції, наприклад: int i; list L; L[i]; “[]” додати елемент в задану позицію, напр Помогите. Есть одна написаная. Условия: Черга. Операції: “+” додати елемент ; “-“ видалити елемент ; bool() перевірка «чи порожня черга?» В ней все работает, все запускается, не могу переделать на вот эту УСЛОВИЕ: Однонаправлений список. Операції: “” видалити елемент в заданій позиції, наприклад: int i; подробнее

Показать сообщение отдельно
__General__
24 / 24 / 3
Регистрация: 04.01.2014
Сообщений: 91
Завершенные тесты: 2
04.01.2014, 18:05     Массив указателей списков смежных вершин
Цитата Сообщение от 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;
    }
}
Я, как видите, храню граф списком вершин, в каждой из которых - список выходящих из нее ребер.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru