隣接リストから指定した点を削除する関数

Question

下のコードは隣接リストを作成するものなのですが、そこに隣接リストから指定した点を削除するdelete関数を作りたいです。自分で考えてはみたのですが分からないので、方法を教えていただきたいです。

#include<stdio.h>
#include<stdlib.h>

#define VMAX 10 //最大点数
//枝
struct edge
{
  char label;
  struct edge *next;
};
//点
struct vertex
{
  char label;
  struct edge *link; //リンクリスト
};
//グラフ
struct graph
{
  int v,e;
  struct vertex vset[VMAX]; //点集合
};

//指定した点をグラフから削除する
　int delete(struct graph *g, char label)
{
　　//labelの点をリンクリストから削除
  return 0;
}


int main()
{
  struct graph grp; //グラフ
  int i,n;
  char c1,c2;
  struct edge *head,*p;
  for(i=0;i<VMAX;i++)grp.vset[i].link=NULL;
  //点数読み込み
  grp.v=scanf("%d%*c",&n);
  grp.v=n;
  printf("\n");
  //点ラベルを読み込み
  for(i=0;i<n;i++){
     char c;
     scanf("%c%*c",&c);
     grp.vset[i].label=c;
   }
   printf("\n");
  //枝数読み込み
  grp.e=scanf("%d%*c",&n);
  grp.e=n;
  printf("\n");
  //点ラベル対（枝）を読み込み
  struct edge ed[VMAX * (VMAX-1)];
  for(i=0;i<n;i++){
    scanf("%c%*c %c%*c",&c1,&c2);
    printf("\n");
    int C1,C2;
    for(C1=0; C1 < n && grp.vset[C1].label != c1;) C1++;
    for(C2=0; C2 < n && grp.vset[C2].label != c2;) C2++;
    ed[i*2].next = NULL;
    ed[i*2].label = c2;
    ed[i*2+1].next = NULL;
    ed[i*2+1].label = c1;

    struct edge **np;
    for( np = &grp.vset[C1].link; *np != NULL;) np = &(*np)->next;
    *np = &ed[i*2];
    for( np = &grp.vset[C2].link; *np != NULL;) np = &(*np)->next;
    *np = &ed[i*2+1];

  delete(&grp, 'D');
    
  }
  
  //グラフの確認
  for(i=0;i<grp.v;i++){
    printf("[%c]:",grp.vset[i].label);
    for(p=grp.vset[i].link; p!=NULL; p=p->next){
      printf("%c",p->label);
      if(p->next !=NULL) printf("->");
    }
    printf("\n");
}
}

コード

Comments

[episteme]

「分からない」で済まさないで。
なにが分からんですか？

Answer 1

だいたいこんな感じだと思います。

//指定した点をグラフから削除する
int delete(struct graph *g, char label)
{
　//labelの点をリンクリストから削除
  int di = g->v;
  //該当の点を探し
  for (int vi = 0; vi < g->v; vi++) {
    struct vertex *v = g->vset[vi];
    //見つけたら位置を記録
    if (v->label == label) di = vi;
    //他の点から該当の点との枝を落とし
    else {
      //該当の枝が先頭の場合
      if (v->link->label == label) {
        v->link = v->link->next;
      }
      //そうでない場合はpreを用意して
      //該当の枝(cur)をスキップする
      struct edge *pre = v->link;
      struct edge *cur = v->link;
      while(cur != NULL) {
        if (cur->label == label) {
          pre->next = cur->next;
          //curがmallocされたものならここでfree
        } else pre = cur;
        cur = cur->next;
      }
    }
  }
  //配列内の点を再配置
  //di < g->v ならばdiが該当の点の位置
  for (int vi = di; vi < g->v; vi++) {
    g->vset[vi] = g->vset[vi+1];
  }
  //di < g->v ならば点の数を更新
  if (di < g->v) g->v--;
  return 0;
}

１つめのforで、該当の点を探しつつ、そうでない点については枝を落としていく処理を行い、２つめのforで配列内の点の再配置を行っている。（anndonutさんより説明）

自信がありませんが、お役に立てたら幸いです。

余計な世話かもしれませんが、勉強するのなら、Rustをお勧めしたいです。Cよりずっと役立ちます。エラーメッセージがすごく丁寧で、参照とポインタを厳密にチェックしてくれます。ただモノ作りをしたい時に、stdにはリンクリストからハッシュマップまであるの上、サードパーティライブラリも簡単に用いられます。

Comments

[anndonut]

それで考え方的には合っていると思います。質問者のコードをきちんと読み解けてるので偉いと思います（私はすぐには読み解けなかった…）。点を削除するときにどうしてこの手順を踏まなければならないのかについては質問者さんにきちんと説明する必要があるかと思います。１つめのforで、該当の点を探しつつ、そうでない点については枝を落としていく処理を行い、２つめのforで配列内の点の再配置を行っている。この処理では点の配列については最適化されるが枝の配列については最適化を行っていないので削除した後に追加しようとするのは難しい、といったことですね。というより、どうして質問者さんが点の削除だけを行おうとしたのかが謎で仕方がないのですが…。

[YufanLou]

コードの説明ありがとうございます！良ければ回答に添えたいです。最適化のことはよくわかりませんが。初心者にはリンクリスト最も難しいのが削除だと思います。pre を用意するのを思いつかないとよく聞きます。質問者さんもそうでしょう。

[anndonut]

どうぞどうぞ！

Answer 2

隣接リストとリンクリストは違います。C言語にはガベージコレクタがないので何かを追加したり削除したりするにはmalloc, freeを用います。隣接リストはリンクリストを用いて表現することができます。貴殿のコードには動的生成の考えがないのでそれを平易に導入して、回答としたいと思います。

隣接リストというのはリンクリストよりも複雑な構造であり、隣接リストよりもまずリンクリストのコードをしっかりと構築する必要があると感じました。大きな問題を小さな問題に分けて考える、という考え方は重要です。そのため、私が書いたコードは関数の数が多いです。このことによりテスタビリティ（テストのしやすさ）が向上し、コーディングで詰まることは少なくなると思います。

ただし、大きな問題を小さな問題に分けて考えるとき、プログラミングの多くの概念を知っていなければなりません。わたしが書いたコードはLisp風のオブジェクトシステムが主体になっていますが、オブジェクトシステムという大仰なシステムを用意しなくとも、よりシンプルに書くことができたんだろうと思います。それはわーっと書き出してからリファクタリングをするとよいと思うのですが。

書いててつくづく思ったのは、複雑なデータ構造を取り扱うのにC言語では貧弱で、C++言語がどうしても欲しくなるということでしょうか。例えば、今回のコードではオブジェクトシステムという大仰なシステムを組んでいますがC++のテンプレートを使えば同じようなコードを２回かかなくて済むわけですね。また、単方向リストについてのライブラリはC++では充実しているので単方向リストのコードをわざわざ書きに行く必要はなかったのかなと。

最後に、コードを書く際はテスタビリティを意識していただきたいと思います。テスタビリティを上げるには、関数やクラスを小分けにする、プログラミング業界で一般的に使われている語彙を意識してできるだけ使うようにする、といった工夫が必要になると思います。

私が書いたコードは恐らく自己満足なのでしょうが、正しいコードを書くには概念を注意深く小分けにして少しずつデバッグを行っていくのが肝心なのだと思います。私からは以上です。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/*
 * リンクリストによるオブジェクトシステム
 */

typedef enum tag_ObjectType {
    OBJECT_TYPE_INTEGER,
    OBJECT_TYPE_LIST
} ObjectType;

struct tag_Object; // オブジェクト型の前方宣言

typedef struct tag_ListObjectComponent {
    struct tag_Object *car; // carはリストの要素(伝統的な概念)
    struct tag_Object *cdr; // cdrはリストの後続部(伝統的な概念)
} ListObjectComponent;

typedef struct tag_Object {
    ObjectType type;
    union {
        int i;
        ListObjectComponent list;
    } d;
} Object;

void object_print(Object *obj) {
    // 引数objはconst型でないので関数内部で書き換え可能であることに注意
    if (obj == NULL) {
        printf("[]");
        return;
    }
    if (obj->type == OBJECT_TYPE_INTEGER) {
        printf("%d", obj->d.i);
        return;
    }
    printf("[");
    object_print(obj->d.list.car);
    obj = obj->d.list.cdr;
    while (obj != NULL) {
        if (obj->type != OBJECT_TYPE_LIST) {
            printf(" . "); // .はドット対であることを表す記号
            object_print(obj);
            printf("]");
            return;
        }
        printf(", ");
        object_print(obj->d.list.car);
        obj = obj->d.list.cdr;
    }
    printf("]");
}

void object_println(Object *obj) {
    object_print(obj);
    printf("\n");
}

Object *object_allocateInteger(int n) {
    Object *obj = malloc(sizeof(Object));
    obj->type = OBJECT_TYPE_INTEGER;
    obj->d.i = n;
    return obj;
}
#define Int object_allocateInteger

Object *object_allocateList(Object *car, Object *cdr) {
    Object *obj = malloc(sizeof(Object));
    obj->type = OBJECT_TYPE_LIST;
    obj->d.list.car = car;
    obj->d.list.cdr = cdr;
    return obj;
}
#define List object_allocateList

void object_free(Object *obj) {
    if (obj == NULL) return;
    if (obj->type == OBJECT_TYPE_LIST) {
        object_free(obj->d.list.car);
        object_free(obj->d.list.cdr);
    }
    free(obj);
}

/*
 * 標準リストについての関数
 *
 *   ここでは、次のものを標準リストとする。
 *     1. NULL
 *     2. nを任意のint型として、List(Int(n), 標準リスト)
 *
 *   すなわち、標準リストとは要素が全て整数のリンクリストのこと
 */

Object *list_add(Object *list, int n) {
    return List(Int(n), list);
}

Object *list_remove(Object *list, int n) {
    if (list == NULL) return NULL;
    if (list->d.list.car->d.i == n) {
        Object *cdr = list->d.list.cdr;
        free(list->d.list.car);
        free(list);
        return list_remove(cdr, n);
    }
    list->d.list.cdr = list_remove(list->d.list.cdr, n);
    return list;
}

// Predicate型は、オブジェクト型とvoidポインタ型(環境を与えるために使用する)を
// 与えてbool型を返す関数のポインタ型
typedef bool (*Predicate)(Object *, void *);

// 述語(boolを返す関数)を与えて、trueならば要素を削除する関数
// (要素が整数でないリストにも適用することができる)
Object *list_remove_if(Object *list, Predicate pred, void *pEnv) {
    if (list == NULL) return NULL;
    if (pred(list->d.list.car, pEnv)) {
        Object *cdr = list->d.list.cdr;
        object_free(list->d.list.car);
        free(list);
        return list_remove_if(cdr, pred, pEnv);
    }
    list->d.list.cdr = list_remove_if(list->d.list.cdr, pred, pEnv);
    return list;
}

bool car_equals_n(Object *obj, void *pNum) {
    return (obj->d.list.car->d.i == *((int*)pNum)) ? true : false;
}

// MapFunc型はオブジェクト型とvoidポインタ型(環境を与えるために使用する)を
// 与えてオブジェクト型を返す関数のポインタ型
typedef Object *(*MapFunc)(Object *, void *);

// リストとMapFunc型の関数を与えてリストの各要素を破壊的に変換する関数
// (要素が整数でないリストにも適用することができる)
Object *list_map_into(Object *list, MapFunc fn, void *pEnv) {
    Object *p = list;
    while (p != NULL) {
        p->d.list.car = fn(p->d.list.car, pEnv);
        p = p->d.list.cdr;
    }
    return list;
}

Object *remove_n_for_cdr(Object *obj, void *pNum) {
    obj->d.list.cdr = list_remove(obj->d.list.cdr, *(int*)pNum);
    return obj;
}

// list_find関数は指定した整数nを見つけるとそれ以降の部分リストを返します。
// 整数nがリストにない場合はNULLを返します。
// (list_find関数は整数nがリスト内に存在するかどうかを判定するために使います)
Object *list_find(Object *list, int n) {
    while (list != NULL) {
        if (list->d.list.car->d.i == n) {
            return list;
        }
        list = list->d.list.cdr;
    }
    return NULL;
}

/*
 * 隣接リスト(無向グラフ)
 */

typedef struct tag_AdjacencyList {
    // 隣接リストの構造
    // [ [ 頂点1 . [隣接する頂点11, ..., 隣接する頂点1n] ],
    //   ...
    //   [ 頂点m . [隣接する頂点m1, ..., 隣接する頂点ml] ] ]
    Object *d;
} AdjacencyList;
#define Adj AdjacencyList

// ヘルパー関数: 頂点uに隣接する頂点のリストを取得する
static Object *adjacencyList_getEdges(Adj *adj, int u) {
    Object *d = adj->d;
    while (d != NULL) {
        if (d->d.list.car->d.list.car->d.i == u) {
            return d->d.list.car->d.list.cdr;
        }
        d = d->d.list.cdr;
    }
    return NULL;
}

// ヘルパー関数: 頂点uに隣接する頂点のリストをobjに設定する
static void adjacencyList_setEdges(Adj *adj, int u, Object *obj) {
    Object *d = adj->d;
    while (d != NULL) {
        if (d->d.list.car->d.list.car->d.i == u) {
            d->d.list.car->d.list.cdr = obj;
        }
        d = d->d.list.cdr;
    }
}

// 隣接リストadjが頂点nを持っているならばtrue, そうでなければfalse
bool hasNode(Adj *adj, int n) {
    Object *d = adj->d;
    while (d != NULL) {
        if (d->d.list.car->d.list.car->d.i == n) return true;
        d = d->d.list.cdr;
    }
    return false;
}

// 隣接リストadjに頂点nを追加
void addNode(Adj *adj, int n) {
    if (hasNode(adj, n)) {
        fprintf(stderr, "addNode: 隣接リストはすでに頂点%dを持っています.\n", n);
        return;
    }
    adj->d = List(List(Int(n), NULL), adj->d);
}

// 隣接リストadjに枝(u, v)を追加
void addEdge(Adj *adj, int u, int v) {
    if (!hasNode(adj, u)) {
        fprintf(stderr, "addEdge: 隣接リストは始点%dを持っていません.\n", u);
        return;
    }
    if (!hasNode(adj, v)) {
        fprintf(stderr, "addEdge: 隣接リストは終点%dを持っていません.\n", v);
        return;
    }
    Object *ue = adjacencyList_getEdges(adj, u);
    Object *ve = adjacencyList_getEdges(adj, v);
    if (list_find(ue, v)) {
        fprintf(stderr, "addEdge: 始点%dの隣接ノードとして終点%dがすでに登録されています.\n", u, v);
        return;
    }
    if (list_find(ve, u)) {
        fprintf(stderr, "addEdge: 終点%dの隣接ノードとして始点%dがすでに登録されています.\n", v, u);
    }
    adjacencyList_setEdges(adj, u, list_add(ue, v));
    adjacencyList_setEdges(adj, v, list_add(ve, u));
}

// 頂点uを削除(それに付随する枝も削除)
void removeNode(Adj *adj, int u) {
    adj->d = list_remove_if(adj->d, &car_equals_n, (void*)(&u));
    adj->d = list_map_into(adj->d, &remove_n_for_cdr, (void*)(&u));
}

int main() {
    Adj adj = { .d = NULL };
    addNode(&adj, 1);
    addNode(&adj, 2);
    addNode(&adj, 3);
    addEdge(&adj, 1, 2);
    addEdge(&adj, 1, 3);
    addEdge(&adj, 2, 3);
    object_println(adj.d);
    removeNode(&adj, 2);
    object_println(adj.d);
    return 0;
}

Answer 3

※ 回答ではありません

1. 単方向リストから'なにか'を削除する場合、

「p->next が'なにか'である edge* p を見つけなければならない」
ことは理解できますか?

1. p->next が'なにか'である edge* p が得られたなら、

その'なにか'を削除する手順は分かりますか?

Answer 4

コードは隣接リストを作成するものなのですが、そこに隣接リストから指定した点を削除するdelete関数を作りたい

……つまり，

1. リストを作ることはできる
2. リストから要素を削除することができない

という状況だということでしょうか．
そのような状況にあるのであれば，1.を利用して2.を達成してはどうでしょうか．

「あるリストの完全なるコピー：そのリストの全ての要素持つ別のリスト」を作る処理を考えましょう．
その手続きにおいて「特定の要素だけをコピーしない」ならば，作られたリストは，元のリストから特定の要素を「削除した」リストになるでしょう．
そうしたら，元のリストは捨てて，何食わぬ顔で新しいリストを採用すれば良いのです．