Напиши на C++ реализацию взвешенного ориентированного графа при учёт следующей…
- User
Напиши на C++ реализацию взвешенного ориентированного графа при учёт следующей реализации списка смежности: class ListNode //элемент списка { public: int data; ListNode* prev, * next; public: ListNode(int data) { this->data = data; this->prev = this->next = NULL; } }; class LinkedList //список { public: ListNode* head;
public: LinkedList() //1.Инициализация { head = NULL; }
void freeMemory() //2.Освобождение памяти { if (head == NULL) return;
ListNode* current = head;
ListNode* nextNode;
do { nextNode = current->next; delete current; current = nextNode; } while (current != head); head = NULL; }
void addSorted(int data) //3.Добавление элемента в порядке возрастания { ListNode* newNode = new ListNode(data);
if (head == NULL) //если список пустой { head = newNode; newNode->next = newNode->prev = newNode; } else if (data < head->data) //если новый элемент меньше головы списка {
newNode->next = head; newNode->prev = head->prev; head->prev->next = newNode; head->prev = newNode; head = newNode; } else if (data > head->prev->data) //если новый элемент больше хвоста списка { newNode->next = head; newNode->prev = head->prev; head->prev->next = newNode; head->prev = newNode; head->prev = newNode; } else //если новый элемент располагается где-то в середине списка { ListNode* current = head->next;
while (current != head && current->data < data) //поиск элемента, значение которого больше нового { current = current->next; }
newNode->next = current; newNode->prev = current->prev; current->prev->next = newNode; current->prev = newNode; } }
void removeBefore(int data) //4.Удаление элемента перед каждым вхождением заданного { if (head == NULL) { return; }
if (head->data == data) { if (head->prev->data == head->next->data) { head = NULL; return; } else { ListNode* nodeToRemove = head->prev; nodeToRemove->prev->next = head; head->prev = nodeToRemove->prev; delete nodeToRemove; } }
ListNode* current = head->next;
while (current != head) { if (current->data == data) { ListNode* nodeToRemove = current->prev; nodeToRemove->prev->next = current; current->prev = nodeToRemove->prev; delete nodeToRemove; }
current = current->next; } }
void remove(int data) //Удаление заданного элемента { if (head == NULL) { return; }
if (head->data == data) { if (head->prev->data == head->next->data && head->data == head->next->data) { head = NULL; return; } else { ListNode* nodeToRemove = head; head->next->prev = head->prev; head->prev->next = head->next; head = head->next; delete nodeToRemove; } }
ListNode* current = head->next;
while (current != head) { if (current->data == data) { ListNode* nodeToRemove = current; current->next->prev = current->prev; current->prev->next = current->next; current = current->next; delete nodeToRemove; } else current = current->next; } }
bool search(int data) //5.Поиск заданного элемента по значению { if (head == NULL) return false;
ListNode* current = head;
do { if (current->data == data) return true;
current = current->next; } while (current != head);
return false; }
void print() //6.Печать { if (head == NULL) return;
ListNode* current = head;
do { cout << current->data << endl; current = current->next; } while (current != head);
cout << endl; }
LinkedList difference(LinkedList list1, LinkedList list2) //7.Дополнительная операция – разность двух списков { if (head != NULL) { LinkedList result;
ListNode* current = list1.head;
do { if (list2.search(current->data) == false) result.addSorted(current->data); current = current->next; } while (current != list1.head); return result; } } }; и следующей реализации вершины графа(если необходимо - можешь что-то исправить в ней): class GraphNode { public: int data; LinkedList* adjList; public: GraphNode(int data) { this->data = data; adjList = new LinkedList(); } };
- Assistant
#include #include
using namespace std;
class ListNode { public: int data; ListNode* prev, * next; public: ListNode(int data) { this->data = data; this->prev = this->next = NULL; } };
class LinkedList { public: ListNode* head;
public: LinkedList() { head = NULL; }
void addSorted(int data) { ListNode* newNode = new ListNode(data); if (head == NULL) { head = newNode; newNode->next = newNode->prev = newNode; } else if (data < head->data) { newNode->next = head; newNode->prev = head->prev; head->prev->next = newNode; head->prev = newNode; head = newNode; } else if (data > head->prev->data) { newNode->next = head; newNode->prev = head->prev; head->prev->next = newNode; head->prev = newNode; } else { ListNode* current = head->next; while (current != head && current->data < data) { current = current->next; } newNode->next = current; newNode->prev = current->prev; current->prev->next = newNode; current->prev = newNode; } } void print() { if (head == NULL) return; ListNode* current = head; do { cout << current->data << " "; current = current->next; } while (current != head); cout << endl; }};
class GraphNode { public: int data; vector<pair<GraphNode*, int>> adjList; // Pair of pointer to adjacent node and weight
public: GraphNode(int data) { this->data = data; } };
int main() { GraphNode* nodeA = new GraphNode(1); GraphNode* nodeB = new GraphNode(2);
nodeA->adjList.push_back(make_pair(nodeB, 5)); // Edge from A to B with weight 5 for (auto& pair : nodeA->adjList) { cout << pair.first->data << " Weight: " << pair.second << endl; } return 0;}
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.