Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0125· OpenAIAi2 WildChat-4.8M (AI2)

Напиши на C++ реализацию ориентированного взвешенного графа. Учти, что реализация списка…

  1. 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; } } };

  2. Assistant

    class Graph { private: int V; // количество вершин LinkedList* adjList; // массив списков смежности

    public: Graph(int V) // конструктор { this->V = V; adjList = new LinkedList[V]; }

    void addEdge(int u, int v, int weight) // добавление ребра в граф
    {
        adjList[u].addSorted(v, weight); // добавляем вершину v в список смежности вершины u с весом weight
    }
    
    void printGraph() // вывод графа
    {
        for (int i = 0; i < V; i++)
        {
            std::cout << "Смежные вершины с вершиной " << i << ":\n";
            adjList[i].print();
        }
    }
    

    };

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.