入れ子の問題

友達が仕事である作業をマンパワーでやっている、 という話しを聞いたので、 それってプログラムにやらせるのが正しいんじゃない? と思ったので作ってみました。 完成した時にはその友達は違う仕事にまわされたのでたいして意味は無いのですが(笑)
まあ、せっかく日記でいろいろ解説とかも作ったので、 それらをページにまとめてみました。

問題設定

手本の表と、分析したいデータがあたえられる。 以下手本の表を簡単に「手本」と、分析したいデータをオリジナルのバイト列、 と呼ぶ事にする。
オリジナルのバイト列は、
タグ、データの長さ、データ、タグ、データの長さ、データ、、、
という風になっている。 実際はフィールドの間は不明で、
37071234567
などのように16進の数字が並んでいるだけ。
データの後は(存在すれば)次のタグのはじまりとなっていて、 タグの長さは不明で、タグは手本のデータに与えられている。 タグには、あるタグをその先頭に含む物はない、とする。
たとえば32というタグがあれば、325というタグは存在しない。

手本には、タグの名前、タグの持つデータ、タグの親子関係が記述されている。
タグのデータの部分には子タグが存在している事があり、 その内部も親と同じように
タグ、長さ、データ
という構成になっている。 子供の子供も可能で、子供が二人いる事も可能。

以下具体例。 手本は、どのような形式でもかまわないが、今回は、

0,23,Component Portion,340812345678
1,34,Component Data,12345678
0,01,test3,020212030604021205041234
1,02,test4,12
1,03,test5,040212
2,04,test6,12
1,05,test7,1234
0,06,test8,5678
という形式とする。 最初の数字は深さ、つまり0が一番上の親の世代で、1がその子供、 という事。
2番目がタグで3番目が名前、4番目が本来のデータ。
その列の親は、上にたどっていった時にその列よりも深さが小さい、 最初の列とする。子供がいないのに孫がいる事は無い。
データは例えば、
2312340812345678012402021203060402120504123406045678
など。

やりたい事は、手本とオリジナルのバイト列を比べて、 手本と一致していたらタグとデータと長さに分解して、 その名前を出力する。
手本と違っている場合は、 違い方により2種類に処理を分ける。

  1. 一番親のタグとデータに分解出来ない時
    エラーと出力して終わる。
  2. 一番親のタグとデータには分解出来るが、少なくとも一つのデータ部分が手本と異る時
    分解出来る世代まで分解して、出来ない世代まできたら、そのデータと手本のデータをたてに並べて出力。
第一のエラーは、どこが間違いなのかを認識するのは不可能なので、 すべてを間違い、としてあきらめる。
子供(や孫など)にデータが分解できない、 という場合と、それの子供がいないで、しかもデータが手本と違う、 という場合は同じエラーとみなす。
具体例。
オリジナルのバイト列 2312340812345678012402021203060402120504123406045678
23 Component Portion
 340812345678
  34 Component Data
   12345678
01 test3
 020212030604021205041234
  02 test4
   12
  03 test5
   040212
    04 test6
     12
  05 test7
   1234
06 test8
 5678

オリジナルのバイト列 2312340812345678012402021203060402120504123406045687
23 Component Portion
  34 Component Data
   12345678
01 test3
  02 test4
   12
  03 test5
    04 test6
     12
  05 test7
   1234
06 test8
 5687
 5678

オリジナルのバイト列 23123408123456780124020212030604021305041234060556789
23 Component Portion
  34 Component Data
   12345678
01 test3
  02 test4
   12
  03 test5
    04 test6
     13
     12
  05 test7
   1234
06 test8
 56789
 5678
という感じです。上の例にはありませんが、エラー1は仕様は考えてません。 エラーとか出力して終了、でいいでしょう。

コード

#include <stdio.h>

#define FS ','

struct node{
  int depth;
  char tag[8];
  char name[256];
  char data[256];
  struct node *brother;
  struct node *child;
};

void PrintIndent(struct node *cur);

/* headがNULLの時は親の設定が面倒なので、
この関数のサポート外とする */
void AddBrother(struct node *head,struct node *newnode){
  struct node *temp;
  temp = head;
  while(temp->brother){
    temp = temp->brother;
  }
  temp->brother = newnode;
  newnode->brother = NULL;
}
	
void AddChild(struct node *parent,struct node *child){
  if(parent->child == NULL){
    parent->child = child;
  }
  else{
    AddBrother(parent->child,child);
  }
}

struct node *MakeNode(char *tag,char *name,char *data,int depth){
  struct node *newnode;
  newnode = (struct node *)malloc(sizeof(struct node));
  strcpy(newnode->tag,tag);
  strcpy(newnode->name,name);
  strcpy(newnode->data,data);
  newnode->depth = depth;
  newnode->brother = newnode->child = NULL;
  return newnode;
}

void PrintNode(struct node *data){
  PrintIndent(data);
  printf("%s %s\n", data->tag,data->name);
  PrintIndent(data);
  printf(" %s\n",data->data);
}

void PrintAllBrother(struct node *first){
  struct node *temp;
  temp = first;
  while(temp->brother){
    PrintNode(temp);
    temp = temp->brother;
  }
}

void PrintAllNode(struct node *head){
  if(head->depth != -1){
    PrintNode(head);
  }
  if(head->child !=NULL){
    PrintAllNode(head->child);
  }
  if(head->brother != NULL){
    PrintAllNode(head->brother);
  }
}

struct node *AddNode(struct node *head,struct node *new){
  struct node *temp;
  if(head==NULL){
    fprintf(stderr,"deb,head=NULL\n");
    exit(1);
  }
  if(head->child  == NULL){
    head->child = new;
  }

  temp = head;
  do{
    temp = temp->child;
    while(temp->brother){
      temp = temp->brother;
    }
  }while(temp->child && temp->depth < new->depth);
  if((temp->depth + 1) == new->depth){
    AddChild(temp,new);
  }
  else
    if(temp->depth == new->depth){
      AddBrother(temp,new);
    }
    else{
      fprintf(stderr,"error!\n");
      PrintNode(temp);
      PrintNode(new);
      exit(1);
    }
    
  return head;
}
    


struct node* MakeNodesFromFile(char *filename){
  FILE *fp;
  char c;
  char tag[256],name[256],data[256],buf[256];
  struct node *head,*temp;
  int i,j,depth;
  if((fp = fopen(filename,"r")) == NULL){
    fprintf(stderr,"can't open file %s in MakeNodesFromFile",filename);
    exit(1);
  }
  head = MakeNode("","","",-1);
  do{
    for(j = 0;j < 4;j++){
      i = 0;
      while((c = getc(fp)) != EOF && c != FS && c!= '\n'){
	buf[i] = c;
	i++;
      }
      if(c==EOF && j != 3){
	return head;
      }
      if(c == '\n' && j != 3){
	return head;
      }
      buf[i] = '\0';
      switch(j){
      case 0:
	depth = atoi(buf);
	break;
      case 1:
	strcpy(tag,buf);
	break;
      case 2:
	strcpy(name,buf);
	break;
      case 3:
	strcpy(data,buf);
	break;
      }
      i = 0;
    }
    temp = MakeNode(tag,name,data,depth);
    head = AddNode(head,temp);

  }while(c != EOF);
  return head;
}


int CheckOK(char *bytes,struct node *self){
  struct node *temp;
  int length;
  temp = self;
  if(bytes[0]){
    while(temp){
      if(strncmp(temp->tag,bytes,strlen(temp->tag))==0){
	length = GetLength(bytes,temp);
	bytes += length + strlen(temp->tag) +2;
	return CheckOK(bytes,self);
      }
      temp = temp->brother;
    }
    return 0;
  }
  return 1;
}

int GetLength(char *bytes,struct node *cur){
  char buf[3];/* tekito-*/
  buf[0] = bytes[strlen(cur->tag)];
  buf[1] = bytes[strlen(cur->tag)+1];
  buf[2] = '\0';
  return atoi(buf);
}

void PrintIndent(struct node *cur){
  int i;
  for(i=0;i< cur->depth;i++){
    printf("  ");
  }
}

/* parent->data == bytes? */
void DecodeData(char *bytes,struct node *parent){
  struct node *temp;
  char buf[256];
  int length;
  temp = parent->child;
  if(CheckOK(bytes,temp)){
    while(bytes[0]){
      while(temp){
	if(strncmp(temp->tag,bytes,strlen(temp->tag))==0){
	  length = (GetLength(bytes,temp));
	  strncpy(buf,bytes+strlen(temp->tag)+2,length);
	  buf[length] = '\0';
	  bytes += length + strlen(temp->tag) +2;
	  PrintIndent(temp);
	  printf("%s %s\n",temp->tag,temp->name);
	  DecodeData(buf,temp);
	}
	temp = temp->brother;
      }
    }
  }
  else{
    PrintIndent(parent);
    printf(" %s\n",bytes);
    if(strcmp(parent->data,bytes)!=0){
      PrintIndent(parent);
      printf(" %s\n",parent->data);
    }
  }
}


int main(int argc,char *argv[]){
  struct node *head,*temp;
  head = MakeNodesFromFile("/home/kazuma/source/c/signal/tehon.txt");
  if(head==NULL){
    fprintf(stderr,"head=NULL!\n");
  }
  DecodeData(argv[1],head);
  return 1;
}

らしい。手本はハードコードしてあるが、 これを直すのは簡単だから別にいいでしょう。

解説

struct node{
  int depth;
  char tag[8];
  char name[256];
  char data[256];
  struct node *brother;
  struct node *child;
};
これは、手本データをおさめる構造体。 これのリストで木構造を保存する。
あるノードは子供と兄弟を持つ。 全てのノードは共通の祖先を持つ。 これは、depthが-1で、他の要素は全部一文字目が'\0'。 リストの最後はNULLで、子供の最後もNULL。 子供は複数いる場合は長男へのポインタで、 その兄弟をたどる事により全ての子供にアクセス可能。 tagが8とかには深い意味は無い。適当。
次は関数の解説。デバッグ用もある。 とりあえず今回はここまで。 ここまでで、手本を構造体のリストに入れる事が出来る。 続きと内部の解説をそのうちやる予定。

  • 入れ子
    関数の解説の続き。ここからは、データのデコードと、 エラーチェック関係の関数。 以上で関数の解説を終わり。 次に実装を見ていく。

    void PrintIndent(struct node *cur){
      int i;
      for(i=0;i< cur->depth;i++){
        printf("  ");
      }
    }
    
    まあ見た通り。curのdepthの分だけスペースを二つづつ出力していく。

    void AddBrother(struct node *head,struct node *newnode){
      struct node *temp;
      temp = head;
      while(temp->brother){
        temp = temp->brother;
      }
      temp->brother = newnode;
      newnode->brother = NULL;
    }
    
    普通のリストを加えるだけ。 tempを長男にセットしたあとは、 弟がいる間はtempを弟にしする、 を繰返す事により、末の弟がtempになる。 そのtemp(末の弟)の弟にnewnodeを設定する事により、 新しい末の弟とする。

    void AddChild(struct node *parent,struct node *child){
      if(parent->child == NULL){
        parent->child = child;
      }
      else{
        AddBrother(parent->child,child);
      }
    }
    
    まずparentに子供がいるかどうかをチェックして、 いなければ、childをparentの子供として終了。 そして、兄弟がいれば、AddBrotherを呼び出す事により、 parent->childの末の弟にchildを加える。

    struct node *MakeNode(char *tag,char *name,char *data,int depth){
      struct node *newnode;
      newnode = (struct node *)malloc(sizeof(struct node));
      strcpy(newnode->tag,tag);
      strcpy(newnode->name,name);
      strcpy(newnode->data,data);
      newnode->depth = depth;
      newnode->brother = newnode->child = NULL;
      return newnode;
    }
    
    まあまんまですが。 まずmallocでstruct nodeの領域を確保して、 tag,name,dataをstrcpyでコピーして、depthを代入して、 brotherとchildをNULLで初期化して、 その構造体のポインタを返す。

    void PrintNode(struct node *data){
      PrintIndent(data);
      printf("%s %s\n", data->tag,data->name);
      PrintIndent(data);
      printf(" %s\n",data->data);
    }
    
    デバッグでしか使いませんが、PrintIndentの使い道をしるのにいいかも。 インデントで空白を出力した後はtagと名前を出力、 同様に次の行で空白とdataを出力する。 PrintIndentは同じだけ空白を出力するが、 printfの中で%sの前に空白があるので、dataの方が一マスだけ空白が多い訳だ。

    void PrintAllBrother(struct node *first){
      struct node *temp;
      temp = first;
      while(temp->brother){
        PrintNode(temp);
        temp = temp->brother;
      }
    }
    
    これもデバッグでしか使いませんが。 firstとその弟を全て出力します。 まあリストを理解しているか、 という情報2種とかに出そうな内容ですが。
    まずはtempにfirstを代入した後に、 弟がいる限りPrintNodeして、 弟をtempに代入します。 よく見ると、末の弟が出力されないので、 バグですね。正しくは
    do{
    	PrintNode(temp);
    	temp = temp->brother;
    }while(temp);
    
    とするべきですね。

    void PrintAllNode(struct node *head){
      if(head->depth != -1){
        PrintNode(head);
      }
      if(head->child !=NULL){
        PrintAllNode(head->child);
      }
      if(head->brother != NULL){
        PrintAllNode(head->brother);
      }
    }
    
    これもデバッグ用ですが、 内容的にはなかなか難しいかも。 これを解説なしで理解できるなら、 たぶん全てのソースが理解できるのでは?
    まずは、全員の祖先は出力しない。 まあこれはちょっと実装の汚ないところ。 それ以外なら自分を出力した後にまずは子供を引数に自分自信、 PrintAllNodeを呼びだす。 そして、子供がいる間はそれがずっと続くので、 子供が次々と出力されていく。 子供が終わると、 次はその兄弟、と続いていく訳です。 とあったとすると、 まずaがわたされると、aが出力されて、 次に子供に行く。 ところが子供はいないので、その兄弟、 bを引数にしてPrintAllNodeが呼びだされて、 bが出力される。 次にその子供cを引数にしてPrintAllNodeを呼びだして、 cが出力されて、またその子供dを引数にPrintAllNodeが呼び出される。
    次に子供がいないので兄弟を引数にPrintAllNodeを出力しようとするが、 兄弟もいないので、PrintAllNodeを終了する。
    すると、dを引数にしたPrintAllNodeが終了して、 それを呼びだしたcのPrintAllNodeで、 子供を入れたPrintAllNodeが終わったので、 次の弟のeを引数にしてPrintAllNodeを呼びだす。 eには弟も子供もいないのでeを出力した後にPrintAllNodeは終了して、 それを呼び出したcを引数にとったPrintAllNodeが終了する。 すると、それを呼びだしたbのPrintAllNodeの子供(c)を引数にしたPrintAllNodeが終了して、 bのPrintAllNodeの次の処理である弟のfを引数にしたPrintAllNodeを呼びだして、 fを出力して、 弟も子供もいないので、 これで全てが終了(本当は全ての親のPrintAllNodeが終わる)。
    次が要のAddNode。

    struct node *AddNode(struct node *head,struct node *new){
      struct node *temp;
      if(head==NULL){
        fprintf(stderr,"deb,head=NULL\n");
        exit(1);
      }
      if(head->child  == NULL){
        head->child = new;
      }
    
      temp = head;
      do{
        temp = temp->child;
        while(temp->brother){
          temp = temp->brother;
        }
      }while(temp->child && temp->depth < new->depth);
      if((temp->depth + 1) == new->depth){
        AddChild(temp,new);
      }
      else
        if(temp->depth == new->depth){
          AddBrother(temp,new);
        }
        else{
          fprintf(stderr,"error!\n");
          PrintNode(temp);
          PrintNode(new);
          exit(1);
        }
        
      return head;
    }
    
    どこに加えるのか、というのが少し難しい。 まず、
      if(head->child  == NULL){
        head->child = new;
      }
    
    一番祖先の子供がいない、という事は、 まだ誰もこのリストに加わっていない、 という事なので、 普通に子供に加える。 ここでreturnするべきだね。
    次が本命。
      temp = head;
      do{
        temp = temp->child;
        while(temp->brother){
          temp = temp->brother;
        }
      }while(temp->child && temp->depth < new->depth);
    
    まずは、 tempは全ての祖先を代入する。 そして、まずtempに子供を代入する。 そして、弟がいる間はtempに弟を代入する事により、 このdepthの一番の弟までいく。 そして、newのdepthの方がtempよりも大きくて、 tempに子供がいれば、子供にすすみます。
    これは、弟がいる段階で、もうそのノードには子供が加わる事はない、 という事を使っています。
    ループを抜けた時点で、 newとtempのdepthが同じ所まで来る事が出来れば、 そこの弟に加える。
    もしdepthが違うなら、tempに子供がいなかった、 という事なので、 tempの子供にnewを加える。 以上の処理をしている所は、
      if((temp->depth + 1) == new->depth){
        AddChild(temp,new);
      }
    
    ループを抜けてこの状況なら、子供を加える。
      else
        if(temp->depth == new->depth){
          AddBrother(temp,new);
        }
    
    depthが同じなら、弟に加える。 それ以外ならエラーにする。
    何故上記のアルゴリズムでいいのかは考えて下さい。

    struct node* MakeNodesFromFile(char *filename){
      FILE *fp;
      char c;
      char tag[256],name[256],data[256],buf[256];
      struct node *head,*temp;
      int i,j,depth;
      if((fp = fopen(filename,"r")) == NULL){
        fprintf(stderr,"can't open file %s in MakeNodesFromFile",filename);
        exit(1);
      }
      head = MakeNode("","","",-1);
      do{
        for(j = 0;j < 4;j++){
          i = 0;
          while((c = getc(fp)) != EOF && c != FS && c!= '\n'){
    	buf[i] = c;
    	i++;
          }
          if(c==EOF && j != 3){
    	return head;
          }
          if(c == '\n' && j != 3){
    	return head;
          }
          buf[i] = '\0';
          switch(j){
          case 0:
    	depth = atoi(buf);
    	break;
          case 1:
    	strcpy(tag,buf);
    	break;
          case 2:
    	strcpy(name,buf);
    	break;
          case 3:
    	strcpy(data,buf);
    	break;
          }
          i = 0;
        }
        temp = MakeNode(tag,name,data,depth);
        head = AddNode(head,temp);
    
      }while(c != EOF);
      return head;
    }
    
    まあ一行読んでnodeを作って、 AddNodeを読む、を繰返すだけ。 Cではよくあるプログラムだと思う。 ちょっと改善出来るけど、まあ素直に組んでみました。
      head = MakeNode("","","",-1);
    
    これが全ての祖先。 それで、次のdo-whileループは行を進めるループ。 次の
        for(j = 0;j < 4;j++){
    
    の部分のブロックで一カラムづつ進める。 合計4カラムという事。
       while((c = getc(fp)) != EOF && c != FS && c!= '\n'){
    	  buf[i] = c;
    	  i++;
       }
    
    これは、FS(','に定義されている)、\n、EOFにあたるまでは、 bufに入れていく。 まあそのまま。
    それで、jの値とcの値で処理を変更する。 jが3の時は最後のカラムなので、改行でもファイルの終わりでも、 そこで最後のカラムが終了になる訳で、特にエラーでは無い。 jが3じゃない時は途中のカラムのはずなので、 改行やEOFという事は手本が不完全だった、 という事になる。 ここでは、手本は完全だ、と仮定する。 つまり手本が不完全だと、動作はいい加減。 ちゃんとexitするべきな気がしてきた。
          if(c==EOF && j != 3){
    	return head;
          }
          if(c == '\n' && j != 3){
    	return head;
          }
    
    以上の所がそれに該当している。 次がカラムの処理。
          
    buf[i] = '\0';
    
    の一行で、bufを文字列にしている。まあCでは基本。
      switch(j){
       case 0:
    	  depth = atoi(buf);
    	  break;
       case 1:
    	  strcpy(tag,buf);
    	  break;
       case 2:
    	  strcpy(name,buf);
    	  break;
       case 3:
      	  strcpy(data,buf);
    	  break;
      }
    
    switch文は、何カラムか、 で処理をかえているが、 実際は文字列のポインタの配列使えば、switchはいらない。 ここらへんは少し手抜き、というか素人っぽさが目立つけど、 配列とか使ってなれてないと読みづらいだろうから、 勘弁してください(笑)。
    jが0ならbufにはdepthが、 jが1ならbufにはtagが、jが2ならbufにはnameが、 jが4ならbufにはdataが入っているので、 それぞれstrcpyしたりatoiしたりする。 atoiは、ascii-to-intという事で、 文字列からintを作る関数。
    以上でカラムの処理が終わる。 そのfor文が終わったら、 現在は行の最後のはずなので、 depth,name,tag,dataにはちゃんとしたデータが入っている(といいなぁ)ので、 ノードを作ってAddNodeする。
        temp = MakeNode(tag,name,data,depth);
        head = AddNode(head,temp);
    
    そのまんま。 これで、一行の処理が終わりで、 次はdo-whileの判定条件に行く。
      }while(c != EOF);
    
    まだファイルが終わってなければ、 doから繰返す訳だ。 このループから出たらreturn headして終わり。 ここまでで、手本のデータを読み込む事が終わったので、 次はバイト列の解析に入るが、 まずはここまでをデバッグしてみるのがいいと思う。 適当に

    int main(){
      struct node *head;
      head = MakeNodesFromFile("/home/kazuma/source/c/signal/tehon.txt");
      if(head==NULL){
        fprintf(stderr,"head=NULL!\n");
      }
      PrintAllNode(head);
      printf("end print all node\n");
      PrintAllBrother(head->child);
      printf("end head->child\n");
      PrintAllBrother(head->child->brother->child);
      return 1;
    }
    
    結果は、

    23 Component Portion
     340812345678
      34 Component Data
       12345678
    01 test3
     020212030604021205041234
      02 test4
       12
      03 test5
       040212
        04 test6
         12
      05 test7
       1234
    06 test8
     5678
    end print all node
    23 Component Portion
     340812345678
    01 test3
     020212030604021205041234
    06 test8
     5678
    end head->child
      02 test4
       12
      03 test5
       040212
      05 test7
       1234
    
    だって。うまくいってるようで。

    次からがオリジナルのバイト列の処理。

    int GetLength(char *bytes,struct node *cur){
      char buf[3];/* tekito-*/
      buf[0] = bytes[strlen(cur->tag)];
      buf[1] = bytes[strlen(cur->tag)+1];
      buf[2] = '\0';
      return atoi(buf);
    }
    
    まあそのまま。bytesのtagの部分の次の2バイトが長さなので、 そのままbufに代入してる。 buf[2]に'\0'を代入しているのは、文字列の終わりをあらわすCの決まり。 atoiは前回解説したが、文字列をintにする。34という文字列から34を返す訳だ。

    int CheckOK(char *bytes,struct node *self){
      struct node *temp;
      int length;
      temp = self;
      if(bytes[0]){
        while(temp){
          if(strncmp(temp->tag,bytes,strlen(temp->tag))==0){
    	length = GetLength(bytes,temp);
    	bytes += length + strlen(temp->tag) +2;
    	return CheckOK(bytes,self);
          }
          temp = temp->brother;
        }
        return 0;
      }
      return 1;
    }
    
    バイト列がノードの兄弟だけで全てを分解できるかどうか、 をチェックする。分解出来たら1を、出来なければ0を返す。
      if(bytes[0]){
    
    まず、バイト列の一文字目が'\0'かどうかをチェック。 この関数は、再帰的に使うので、 bytes[0]が'\0'までいけたら、 最後まで分解出来た、という事になっている。
    while(temp){
      if文
      temp = temp->brother;
    }
    
    結構そのまま。 まず、tempにはCheckOKで渡されたノードが入れられていて、 whileは、弟がいる間弟に進む、というループ。
      if(strncmp(temp->tag,bytes,strlen(temp->tag))==0){
    
    次のこのif文で、bytesのタグがtempと一致しているかどうかを調べる。
        length = GetLength(bytes,temp);
        bytes += length + strlen(temp->tag) +2;
        return CheckOK(bytes,self);
    
    一致していたら、このブロックが実行される。 まずデータの長さを取出して、 bytesをデータの長さの分だけ進める。 これで、最初のタグとデータの分だけスキップした事になるので、 残りをCheckOKに渡す。そしてCheckOKからかえってきた値を返す。
    CheckOKには、最初のタグとそのデータの分だけ進められたbytesが入っていて、 同じように、bytesの最初のタグとselfの兄弟のタグを比較して、 一致したらそのデータを取り出す、を繰返す。
    よく見ると、進められるかどうか、 というのはわからないので、ここにはエラーチェックが必要だね。
    	length = GetLength(bytes,temp);
    	if(strlen(bytes) < length+strlen(temp->tag)+2){
         return 0;
       }
    	bytes += length + strlen(temp->tag) +2;
    	return CheckOK(bytes,self);
    
    だね。
    先のwhileでヒットするタグがなければ、 0を返す。bytes[0]が'\0'までいけたなら1を返す。

    次が要2のDecodeData。デコードして、 正しいかどうかをチェックする。

    void DecodeData(char *bytes,struct node *parent){
      struct node *temp;
      char buf[256];
      int length;
      temp = parent->child;
      if(CheckOK(bytes,temp)){
        while(bytes[0]){
          while(temp){
    	if(strncmp(temp->tag,bytes,strlen(temp->tag))==0){
    	  length = (GetLength(bytes,temp));
    	  strncpy(buf,bytes+strlen(temp->tag)+2,length);
    	  buf[length] = '\0';
    	  bytes += length + strlen(temp->tag) +2;
    	  PrintIndent(temp);
    	  printf("%s %s\n",temp->tag,temp->name);
    	  DecodeData(buf,temp);
    	}
    	temp = temp->brother;
          }
        }
      }
      else{
        PrintIndent(parent);
        printf(" %s\n",bytes);
        if(strcmp(parent->data,bytes)!=0){
          PrintIndent(parent);
          printf(" %s\n",parent->data);
        }
      }
    }
    
    特に問題は無いと思うが、 それで理解できるなら、 おそらく解説もいらないだろう。 ようするに解説はほとんどの人にはいらない?(笑)。
    void DecodeData(char *bytes,struct node *parent)
    
    引数には、bytesをデータに持っているノードを渡す。 つまりbytesを分解するのは、parentの子供。
      if(CheckOK(bytes,temp)){
    
    分解出来るかどうかを調べる。 分解出来なければ、エラーを返す。 何番目の子タグがエラーなのかを知る方法は無いので、 全てがエラー、とみなす。 CheckOK出来ない、という事は(子タグがいるなら)エラー2に相当している。
    エラーなら、データを出力して、 parentと違うかどうかをチェックする。 CheckOKが0を返すのは、もう子供がいないか、 エラーかのどちらかなので、 もし子供がいないなら、エラーでは無い可能性もあるから。

    もし分解できるなら、 分解して、そのデータを子供に渡す。 まずは、データの先頭に一致するタグを探す。

        while(bytes[0]){
          while(temp){
           if(strncmp(temp->tag,bytes,strlen(temp->tag))==0){
             ifブロック
           }
          temp = temp->brother;      
    
    最初のbytes[0]が0じゃない間、というのは、もし0なら最後までいった、 という事になっている。説明しづらいので、後でソースを読んで。
    次のwhileとifの組みあわせは、CheckOKでも同じのがあったと思う。 つまり、bytesの最初のタグと一致するノードを兄弟から探す訳だ。 同じのがある場合は関数化すべきだったりするけど、 面倒なのでしていない。 でも、本当はするべきだったなぁ。CheckOK書いてる時は気付かなかった。
    	  length = (GetLength(bytes,temp));
    	  strncpy(buf,bytes+strlen(temp->tag)+2,length);
    	  buf[length] = '\0';
    	  bytes += length + strlen(temp->tag) +2;
    
    データの長さをlengthに入れて、 その分だけデータをコピーしている。タグの長さと、2を足しているのは、 タグと、データの長さのフィールドを飛ばす為。 buf[length]に0を入れるのはもういいでしょう。 bytes+=でbytesを進める。
      PrintIndent(temp);
      printf("%s %s\n",temp->tag,temp->name);
    
    インデントしたあとにタグと名前を出力している。 ifブロックの最初に書くのが筋だが、まあ気にしない。
    	  DecodeData(buf,temp);
    
    最初のデータと、そのデータの持ち主を引数にもう一度DecodeDataを呼びだす。 まずは子供にいき、次に兄弟にいっている。 PrintAllNodeと理屈は一緒だけど、なかなか複雑。
    ここまできて、bytesとタグが一致しなかったらどうなるのか? という疑問があるかもしれないけど、 それはCheckOKではじかれる(はず)なので処理していない。 まじめにやるなら一応チェックすべきかも。
    再帰呼出しは、子供が分解できる限りつづく。 それが終わって帰ってくると、 先ほどの
        while(bytes[0]){
    
    のループで最後まで行く訳だ。 一旦ヒットした後の
          while(temp){
    
    は無駄ループなので、continueするべきだね。 でもしてなくても問題はおこらないはず。 一応直しておこう。
      else{
        PrintIndent(parent);
        printf(" %s\n",bytes);
        if(strcmp(parent->data,bytes)!=0){
          PrintIndent(parent);
          printf(" %s\n",parent->data);
        }
      }
    
    これは、CheckOKが0だった場合。 タグと名前は、これの親の呼出しで出力されているはずなので、 データだけ出力。エラーなのか子供がいないだけなのかを区別する為に 次のif文がある。parentのデータと違ければparentのデータも出力する訳だ。
    以上で終わりだと思う。一応手抜きのmain関数をつけておきます。

    int main(int argc,char *argv[]){
      struct node *head,*temp;
      head = MakeNodesFromFile("/home/kazuma/source/c/signal/tehon.txt");
      if(head==NULL){
        fprintf(stderr,"head=NULL!\n");
      }
      DecodeData(argv[1],head);
      return 1;
    }
    
    まあまんまだやね。 argv[1]にデータを渡す訳です。 手本のファイルはハードコードしてます。 ちゃんとやりたいなら、argv[2]か何かにすればいいでしょう。 また、argcのチェックとかいれてません。 本当なら入れるべきでしょう。 修正版は面倒なのでアップしませんが、 問題ないでしょう。 必要ならメール下さい。
    これで一応全部のソースの解説を終わったけど、 どうかなぁ。 わかる人にしかわからない解説になってるおそれもあるので、 感想をメールとか直接とかくれると嬉しいです。
    ここがわからん、とか言われれば、 解説を加えます、たぶん。

    終わりに

    どうでしょうか? プログラム的にはおもちゃの長さですが。 内容的にも簡単だし、 何かのうつし、ではなくて自分で多少は考えないと解けないので、 プログラムの面白さは楽しめると思います。 次はrubyの予定。