Реализация списка смежности в С++ с использованием связанного списка

Я видел много реализаций списка смежности. Здесь я пытаюсь реализовать это с помощью С++. Как вы можете понять из моей структуры C++, я новичок в C++. Здесь я изо всех сил пытаюсь запустить свой код. Моя текущая проблема в том, что она не проходит через весь график. и я получаю ошибку сегментации. Результат:

вершина: 0

1->

вершина: 1

2->3->

вершина: 2

вершина: 3

вершина: 4

Ошибка сегментации

Мне нужна помощь, чтобы запустить это. Я хочу реализовать алгоритм DFS. Любые советы будут отличными!!!

Вот заголовок:

#ifndef DFS_H
#define DFS_H

class DFS{
private:
    struct vertex{
        int data;
        bool visited;
        struct vertex* next;
    };  
    int V;
    struct vertex* G[20];
public:
    DFS(int vertices);
    vertex* addVertex(int data);
    void addEdge(int index, int data);
    void dfs(int vertex);
    void printGraph();
};

#endif

СРР-файл:

#include "DFS.h"
#include <iostream>
#include <cstdlib>
using namespace std;
DFS:: DFS(int vertices){
    this->V=vertices;
    for(int i=0; i<V; i++){
        G[i]= NULL; 
    }
}
DFS::vertex* DFS::addVertex(int data){
    struct vertex* newNode= new vertex;
    newNode->data= data;
    newNode->next= NULL;
    newNode->visited=false;
    return newNode;
}
void DFS:: addEdge(int index, int data){
    struct vertex* cursor;
    struct vertex* newVertex= addVertex(data);

    if(G[index]==NULL)
        G[index]=newVertex;
    else{
        cursor=G[index];
        while(cursor->next!=NULL)
            cursor=cursor->next;
        cursor->next= newVertex; 
    }
}
void DFS::printGraph(){
    for(int i=0; i<V; i++){
        struct vertex* cursor= G[i];
        cout<<"vertex: "<<i<<endl;
        while(cursor->next!=NULL){
            cout<<cursor->data<<"->";
            cursor=cursor->next;    
        }
        cout<<endl;
    }
}
void DFS:: dfs(int vertex){
}
int main(){
    DFS dfs(5);
    dfs.addEdge(0,1);
    dfs.addEdge(0,4);
    dfs.addEdge(1,2);
    dfs.addEdge(1,3);
    dfs.addEdge(1,4);
    dfs.addEdge(2,3);
    dfs.addEdge(3,4);

    dfs.printGraph();
    return 0;   
}

*

Спасибо за помощь сообществу Stackoverflow!


person Jose Ortiz    schedule 19.09.2016    source источник
comment
Вам нужно пересмотреть, как работают массивы. struct vertex* G[]; недействителен.   -  person NathanOliver    schedule 19.09.2016
comment
Да я вижу, что. Вот почему я спрашиваю здесь. Я пытаюсь сделать массив вершин. Итак, как бы вы это сделали?   -  person Jose Ortiz    schedule 19.09.2016
comment
Вы знаете, сколько вам нужно? Если нет, вместо использования массива вы должны рассмотреть std::vector.   -  person NathanOliver    schedule 19.09.2016
comment
Нет, пользователь должен указать, сколько вершин он хочет вставить. Количество вершин, которые они хотят передать, передается в конструкторе. где «V» — количество вершин. пример этого можно найти здесь, sanfoundry.com/cpp-program-implement -смежный-список   -  person Jose Ortiz    schedule 19.09.2016
comment
Изучайте одну новую вещь за раз. Если вы хотите изучить массивы, поэкспериментируйте с int, int* и int[]. Пока вы не освоите это, не пытайтесь vertex[]. И пока вы не освоите это, не пытайтесь использовать DFS.   -  person Beta    schedule 19.09.2016
comment
Ладно, извините, вы злитесь, что я неправильно использовал массив. Спасибо за вашу помощь!   -  person Jose Ortiz    schedule 19.09.2016
comment
@JoseOrtiz - вы в основном взяли какой-то код, который либо является попыткой C программиста, пытающегося написать C++ (ключевое слово struct, используемое в разных местах, является мертвой раздачей, это может быть так), или вы получили код от очень старого (или очень плохая) книга C++ или образец. Ваш класс вершин выглядит как std::forward_list, поэтому все, что вам нужно, это std::forward_list‹vertex› и избавьтесь от переменной-члена next в вершине, так как в ней нет необходимости, если используется forward_list.   -  person PaulMcKenzie    schedule 19.09.2016
comment
хахаха! отлично! Ну, я просмотрел много кода как на C, так и на C++ и попытался создать свой собственный с нуля. Я действительно не хочу использовать что-то вроде forward_list. Я хочу создать все с нуля   -  person Jose Ortiz    schedule 19.09.2016
comment
Итак, ваша цель — создать объект графа или сохранить связанный список? Если это последнее, напишите класс связанного списка. Если первое, то используйте уже написанный класс связанного списка, чтобы начать работу по созданию графического объекта. Кроме того, и я собираюсь сказать это - я еще не видел, чтобы новичок правильно написал класс связанного списка, без ошибок, без побочных эффектов и т. д. Почти каждый день на SO возникает вопрос о связанном списке, о как правильно реализовать. Если вы хотите пойти по этому пути, я желаю вам удачи.   -  person PaulMcKenzie    schedule 19.09.2016
comment
И теперь ваш объект графа полон утечек памяти, не соответствует правилу 3 и т. д. Просто используйте std::vector для реализации динамического массива, и большинство, если не все, эти проблемы исчезнут.   -  person PaulMcKenzie    schedule 19.09.2016
comment
Я хочу создать график. Список смежности. Вот почему я создаю массив вершинной структуры в конструкторе. с вершинами, являющееся количеством вершин, необходимых для графа   -  person Jose Ortiz    schedule 19.09.2016
comment
@JoseOrtiz -- Вот ваш код (или то, что, как мне кажется, эквивалентно вашему коду) с использованием стандартных контейнеров. Вы видите, что не используется ни один указатель и нет утечек памяти.   -  person PaulMcKenzie    schedule 19.09.2016
comment
Если бы вам пришлось реализовать список смежности так, как я это делаю здесь, со связанным списком, как бы вы это сделали? без использования вектора или чего-то еще   -  person Jose Ortiz    schedule 19.09.2016
comment
@JoseOrtiz как бы ты это сделал. без использования вектора или чего-то еще -- Помните, что я и другие, помогающие вам, не новички в C++. Что бы я и другие сделали, так это создали бы наши собственные классы векторов и списков и использовали бы их, если бы это было необходимо. Мы бы не разбрасывали вызовы new[] / delete[] повсюду — у нас было бы знание, чтобы инкапсулировать их в наш собственный класс и согласованно управлять памятью. Это отвечает на ваш вопрос?   -  person PaulMcKenzie    schedule 20.09.2016
comment
Я понимаю, что вы говорите. Это то, что я хотел бы сделать. Я хотел бы создать свой собственный список и векторный класс. Пример того, что я хотел бы видеть.   -  person Jose Ortiz    schedule 20.09.2016


Ответы (1)


Segfault исходит от printGraph, который предполагает наличие всех V вершин, что неверно в вашем случае. Обратите внимание, что dfs.addEdge(4, ...) не инициализирует 5-ю вершину.

В общем, подход, согласно которому длина должна соответствовать количеству элементов, установленных позже, вызывает проблемы, я бы реорганизовал этот код, используя vector для хранения.

Другая проблема заключается в том, что addEdge всегда создает новый экземпляр vertex, что означает, что после dfs.addEdge(1,3) и dfs.addEdge(2,3) вершины 1 и 2 будут указывать на разные экземпляры вершины 3.

Еще одно: addEdge(1,2) и addEdge(1,3) оставят вам ребра 1->2 и 2->3. Я предполагаю, что результатом должны быть ребра 1->2 и 1->3.

Не говоря уже о том, что возврат голого указателя newed из addVertex вызывает утечку памяти; Я бы предложил использовать auto_ptr (unique_ptr, если вы используете С++ 11).

Другое дело, что вы повторно реализуете список с прямыми ссылками, когда доступен std::forward_list.

Это всего лишь несколько проблем, которые я заметил, просто взглянув на ваш код. Я уверен, что их больше, потому что, честно говоря, это выглядит довольно плохо (без обид, мы все когда-то были новичками). Я предлагаю то, что сказал @Beta: изучать и практиковать одну вещь за раз (создайте список вершин, когда вам это удобно, выясните, как представлять ребра, затем попробуйте пройти по нему, построить простой алгоритм и т. д.).

person Tomek Sowiński    schedule 19.09.2016
comment
Да, новичок в С++, я перешел с Java. хаха. Ну это довольно неловко. Спасибо за помощь. Я ценю это. - person Jose Ortiz; 19.09.2016