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

Классы, грфы, операции на них - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ автоматная программа сортировки слиянием http://www.cyberforum.ru/cpp-beginners/thread827413.html
есть программа, реализующая сортировку слиянием. нужно написать автоматную сортировку слиянием void merge(int *A, int l, int s, int r) { //слияние упорядоченных частей массива int pos1=l; int pos2=s+1; int pos3=0; int *B;
C++ Задача с классом Здравствуйте. Имеется следующий класс. class CClass { private: int *arr; const int size; http://www.cyberforum.ru/cpp-beginners/thread827412.html
Переставить местами строки C++
Как в масиве строк поменять, например, первую и вторую строку местами?
Найти ошибку в коде C++
Помогите пж. найти ошибку в коде,он почему то последний символ не считывает. #include <iostream> #include <fstream> using namespace std; int main(){ char a; int bkv=0,cfr=0,ost=0; ifstream file("c.txt"); file.get(a);
C++ Лаба по археому (Реализовать имитационную модель процессора со стековой адресацией с двумя командами) http://www.cyberforum.ru/cpp-beginners/thread827398.html
Реализовать имитационную модель процессора со стековой адресацией с двумя командами - занесением в стек и нахождением дополнения к числу в дополнительном коде.
C++ Интрузивный и не интрузивный список Здорова господа! Что такое обычный список это понятно есть узел в котором находится указатель на соседний элемент и переменная которая содержит значение узла. А от интрузивный список хз. Там я от посмотрел в узле содержится токо два указателя на элементы, а где же хранятся данные? От примерчик из википедии: struct list_link { list_link *prev, *next; }; struct element подробнее

Показать сообщение отдельно
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
04.04.2013, 13:08     Классы, грфы, операции на них
Какие у вас ограничения? С сишными строками подойдет?
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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
#include <iostream>
#include <iomanip> // это для форматирования вывода
#include <cstring>  // это для работы с сишными строками
 
class Vertex {
 public:
  Vertex() : name(new char[1]) { name[0] = '\0'; }
  Vertex(const char *name) : name(0) { setName(name); }
  Vertex(const Vertex &other) : name(0) { setName(other.getName()); }
  virtual ~Vertex() { delete [] name; }
  Vertex &operator=(const Vertex &other) {
    if (this != &other) {
      setName(other.getName());
    }
    return *this;
  }
  const char *getName() const { return name; }
  void setName(const char *name) {
    delete [] this->name;
    this->name = strcpy(new char[strlen(name) + 1], name);
  }
 private:
  char *name;
};
 
// сравнение вершин
bool operator<(const Vertex &a, const Vertex &b) {
  return strcmp(a.getName(), b.getName()) < 0;
};
 
// для простоты, вывод вершины
std::ostream &operator<<(std::ostream &stream, const Vertex &v) {
  return stream << "Vertex{" <<
    "name='" << v.getName() << "'}";
};
 
struct Edge {
  Vertex begin, end;
  double weight;
  Edge() {}
  Edge(const Vertex &begin, const Vertex &end, double weight)
    : begin(begin), end(end), weight(weight) {}
};
 
// для простоты, вывод ребра
std::ostream &operator<<(std::ostream &stream, const Edge &e) {
  return stream << "Edge{" <<
    "begin=" << e.begin << "," <<
    "end=" << e.end << "," <<
    "weight=" << std::fixed << std::setprecision(3) << e.weight << "}";
};
 
// сравнение ребер
bool operator<(const Edge &a, const Edge &b) {
  if (a.begin < b.begin) {
    return true;
  } else if ((!(b.begin < a.begin)) && a.end < b.end) {
    return true;
  } else if ((!(b.begin < a.begin)) && (!(b.end < a.end))) {
    return a.weight < b.weight;
  } else {
    return false;
  }
};
 
// бинарным поиском находит первый элемент, не меньший заданного
Edge *lowerBound (Edge *first, Edge *last, const Edge &val) {
  size_t count = last - first;
  while (count > 0) {
    Edge *it = first;
    size_t step = count / 2;
    it += step;
    if (*it<val) {
      first = ++it;
      count -= step + 1;
    }
    else count = step;
  }
  return first;
}
 
// собственно, граф, заданный ребрами
class EdgeListGraph {
 public:
  EdgeListGraph() : size(0), capacity(10), capacityIncrement(10),
    edges(new Edge[capacity]) {}
  virtual ~EdgeListGraph() {
    delete [] edges;
  }
  void addEdge(const Edge &edge) {
    makeSureCapacityIsEnough();
    Edge *position = lowerBound(edges, edges + size, edge);
    if (position >= edges + size || edge < *position) {
      for (Edge *i = edges + size; i > position; --i) {
        *i = *(i - 1);
      }
      *position = edge;
      ++size;
    }
  }
  void addBidirectionalEdge(const Edge &edge) {
    addEdge(edge);
    addEdge(Edge(edge.end, edge.begin, edge.weight));
  }
  void removeEdge(const Edge &edge) {
    Edge *position = lowerBound(edges, edges + size, edge);
    if (position >= edges + size || edge < *position) {
      // нет такого элемента
      // возможно, стоит кинуть ошибку?
    } else {
      for (Edge *i = position; i < edges + size; ++i) {
        *i = *(i + 1);
      }
      --size;
    }
  }
  const Edge *begin() const { return edges; }
  const Edge *end() const { return edges + size; }
  void clear() {
    delete [] edges;
    capacity = capacityIncrement;
    edges = new Edge[capacity];
    size = 0;
  }
  int getSize() const { return size; }
  void addEdges(const EdgeListGraph &g) {
    for (const Edge *i = g.begin(); i != g.end(); ++i) {
      addEdge(*i);
    }
  }
 protected:
  void makeSureCapacityIsEnough() {
    if (size - 1 >= capacity) {
      capacity += capacityIncrement;
      Edge *newEdges = new Edge[capacity];
      for (int i = 0; i < size; ++i) {
        newEdges[i] = edges[i];
      }
      delete [] edges;
      edges = newEdges;
    }
  }
 private:
  // запрет копирования:
  EdgeListGraph(const EdgeListGraph &); // конструктором копирования
  EdgeListGraph &operator=(const EdgeListGraph&); // присваиванием
  int size;
  int capacity;
  int capacityIncrement;
  Edge *edges;
};
 
std::ostream &operator<<(std::ostream &stream, const EdgeListGraph &g) {
  stream << "EdgeListGraph{size=" << g.getSize() << ",Edges=[";
  for (const Edge *i = g.begin(); i != g.end(); ++i) {
    stream << std::endl << "    " << *i;
  }
  return stream << "]}";
};
 
EdgeListGraph &operator+=(EdgeListGraph &a, const EdgeListGraph &b) {
  a.addEdges(b);
  return a;
}
 
int main(int argc, char *argv[]) {
  EdgeListGraph a;
  a.addBidirectionalEdge(Edge(Vertex("a"), Vertex("b"), 1));
  a.addBidirectionalEdge(Edge(Vertex("a"), Vertex("c"), 1));
  a.addEdge(Edge(Vertex("b"), Vertex("d"), 0.5));
  a.addBidirectionalEdge(Edge(Vertex("c"), Vertex("d"), 1));
  std::cout << a << std::endl;
 
  EdgeListGraph b;
  b.addEdge(Edge(Vertex("a"), Vertex("b"), 1.3));
  b.addBidirectionalEdge(Edge(Vertex("a"), Vertex("c"), 1));
  b.addEdge(Edge(Vertex("b"), Vertex("c"), 0.5));
  std::cout << b << std::endl;
 
  EdgeListGraph c;
  c += a;
  c += b;
  std::cout << c << std::endl;
 
  std::cin.get();
  return 0;
}
 
Текущее время: 14:37. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru