0

C の学習を始めたばかりで、自己学習の演習として、C でデータ構造とアルゴリズムを実装しています。現在、グラフに取り組んでおり、これがそのデータ構造表現です。

typedef int graphElementT;
typedef struct graphCDT *graphADT;

typedef struct vertexTag
{
    graphElementT element;
    int visited;
    struct edgeTag *edges;
    struct vertexTag *next; 
} vertexT;

typedef struct edgeTag
{
    int weight;
    vertexT *connectsTo;
    struct edgeTag *next;
} edgeT;

typedef struct graphCDT
{
    vertexT *vertices;
} graphCDT;

このグラフに addVertex 関数を追加しました。

int addVertex(graphADT graph, graphElementT value)
{
    vertexT *new = malloc(sizeof(*new));

    vertexT *vert;
    new->element = value;
    new->visited = 0;
    new->edges = NULL;
    new->next = NULL;

    int i = 0;

    for(vert=graph->vertices; vert->next != NULL; vert=vert->next)
    {
        if(vert->element == value)
        {
            printf("already exists\n");
            return 0;
        }
    }   

    vert->next = new;

    //free(new);
    printf("\ninserted %d\n", vert->element);   

    return 1;       
}

これは、3つのことを除いて正常に機能します。

  1. 新しく追加された頂点がリストの最後の頂点と同じである場合、それは認識されません。これを防ぐために、for ループの制限条件を に変更しましたvert != NULLが、これにより seg fault が発生します。

  2. 一時的に割り当てられたポインターを解放しようとすると、ポインターによってメモリ ポインターがリセットされ、頂点リストの最後に無限ループが追加されます。ポインタが指すメモリを上書きせずにポインタを解放する方法はありませんか? それとも、ポインターを解放する必要はありませんか?

  3. また、グラフを破棄すると、すべてのエッジと頂点が破棄されることになりますか? またはより良いアプローチがありますか？

また、グラフのこのデータ構造が適切なものではなく、より良い実装があれば、指摘していただければ幸いです。

4

2 に答える 2

1

1

制限条件を vert!=NULL に変更し、ループが vert==NULL で終了する場合、つまり、追加する頂点が存在しない場合、次のステートメントを読むことになります。

vert->next = new;

つまり、NULL ,vert ポインターにアクセスしているため、seg fault が発生します。

最後の要素が追加される頂点ではないかどうかをチェックできるようにし、またセグメント違反を防止するには、次のようにします。

for(vert=graph->vertices; vert->next != NULL; vert=vert->next)
{
    if(vert->element == value)
    {
        printf("already exists\n");
        return 0;
    }
}   

if(vert->element == value)
    {
        printf("already exists\n");
        return 0;
    }

vert->next = new;

2

一時的な「新しい」ポインターは、追加した頂点に割り当てられたメモリの場所です。解放することは、追加したばかりの頂点を削除したことを意味するため、解放することはできません:O .

3

はい、本質的にグラフを破壊することは同じことを意味します。

リンクされたリストをグラフの隣接リストの実装として実装することは常に良い習慣です。

于 2013-06-02T08:12:56.770 に答える
0

これは、使用できる機能する addVertex 関数です。元の宣言をそのまま保持しています。テストするコマンド ライン引数を指定できる main () を追加しました。

int addVertex(graphADT graph, graphElementT value)
{
   vertexT *tmpvert , *vert ;
   vert=graph->vertices ;
  /*check to see whether we really need to create a new vertex*/
   tmpvert = vert;
     while(tmpvert != NULL)
     {
       /* U can put a debug printf here to check what's there in graph:
        *  printf("tmpvert->elem=%d   ", tmpvert->element);
        */
        vert = tmpvert;
        if(tmpvert->element == value)
             return 0;
        tmpvert=tmpvert->next ;
    }
   /*If we are here , then we HAVE to allocate memory and add to our graph.*/
   tmpvert = (vertexT*)malloc(sizeof(vertexT));
   if ( NULL == tmpvert )
        return 0; /* malloc failure */
   tmpvert->element = value;
   tmpvert->visited = 0;
   tmpvert->edges = NULL;
   tmpvert->next = NULL;

   if ( NULL == vert )
        graph->vertices = tmpvert; /*Notice that I dont use virt=tmpvert */
   else
        vert->next = tmpvert; /*putting stuff in next is fine */

    return 1;
/* Dont try printing vert->element here ..vert will be NULL first time */
/*return code for success is normally 0 others are error.
 *That way you can have your printfs and error code
 *handling outside this function.But its ok for a test code here */
}

次に、テスト用のメインの () スニペット:

int main (int argc , char* argv[]) {
        graphADT graph ;
        graph =(graphADT) malloc ( sizeof(struct graphCDT) );
        graph->vertices = NULL;
        while ( --argc >0)
        {
                int value = atoi(argv[argc]);
                addVertex(graph,value);
        }
}
于 2013-06-02T09:25:08.017 に答える