マルチフォークツリーの設計、作成、階層優先ループ、深さ優先ループ
18335 ワード
参照先:http://www.cnblogs.com/unixfy/p/3486179.html
ユーザのマルチフォークツリーデータは1つのファイルに格納され、aA 4 g cC z bBbB z 2 f i g 1 d 3 x e jの各行の最初の要素は1つのノードを指定し、2番目の要素はそのノードにいくつかのサブノードがあり、その後にいくつかのサブノードが付いていることを示す.
/*アルゴリズム1:階層優先マルチツリー(キュー)機能:マルチツリー内のノードをツリーの深さ(深さが大きいから小さい)で出力するため、スタック*/
/*アルゴリズム2:深度優先マルチフォーク(再帰)機能:ノードからリーフノードへのパス上のノード名のアルファベット数が最大のパスを見つける*/
実装:スタックのデータ構造;キューのデータ構造;マルチフォークツリーのデータ構造、マルチフォークツリーの作成、階層優先ループ(BFS)、深度優先ループ(DFS<再帰>)
まとめ:1.プログラム中(tmp=(char*)util_malloc((strlen(str)+strlen(head->name)*sizeof(char));//申請スペース、注意:ここのスペースは+1が必要で、tmp文字列の末尾の'0'を格納し、そうでなければ、裏面free(tmp)エラーを引き起こす)ここで注意2.freeは空のポインタ(p=NULL、free(p);)を解放することができるこれもなぜpのメモリを解放したのか、p=NULL(p=malloc(sizeof(...)、free(p)、p=NULL)と続く.これは主にp 3.mallocを再び解放した後に必ず手動でfreeを落とすことを避け、一般空間は少し大きく申請する
ユーザのマルチフォークツリーデータは1つのファイルに格納され、aA 4 g cC z bBbB z 2 f i g 1 d 3 x e jの各行の最初の要素は1つのノードを指定し、2番目の要素はそのノードにいくつかのサブノードがあり、その後にいくつかのサブノードが付いていることを示す.
/*アルゴリズム1:階層優先マルチツリー(キュー)機能:マルチツリー内のノードをツリーの深さ(深さが大きいから小さい)で出力するため、スタック*/
/*アルゴリズム2:深度優先マルチフォーク(再帰)機能:ノードからリーフノードへのパス上のノード名のアルファベット数が最大のパスを見つける*/
実装:スタックのデータ構造;キューのデータ構造;マルチフォークツリーのデータ構造、マルチフォークツリーの作成、階層優先ループ(BFS)、深度優先ループ(DFS<再帰>)
#include
");
exit(EXIT_FAILURE);
}
return ptr;
}
// fopen()
FILE *util_fopen(const char *name, const char *access)
{
FILE *fp = fopen(name, access);
if (fp == NULL)
{
printf("Open file %s failed
", name);
exit(EXIT_FAILURE);
}
return fp;
}
//
//
STACK *StackInit(int size)
{
STACK *tmp;
tmp = (STACK*)util_malloc(sizeof(STACK));// （ ， 4 （32 ）， ， ， ， ）
tmp->size = size;
tmp->index = 0;
tmp->array = (NODE**)util_malloc(size*sizeof(NODE*)); // void * NODE* NODE**( void ， NODE* )
return tmp; //
}
// ： 1， 0
int StackEmpty(STACK *sp)
{
if (sp->index <= 0 || sp == NULL)
return 1;
else return 0;
}
//
int Push(STACK *sp, NODE *data)
{
if (sp->index >= sp->size || sp == NULL)
{
return 1; //
}
else
{
sp->array[sp->index++] = data;
return 0;
}
}
//
int Pop(STACK *sp, NODE **data)
{
if (sp->index <= 0 || sp == NULL)
{
return 1;
}
else
{
*data = sp->array[--sp->index];
return 0;
}
}
//
void StackDestroy(STACK *sp)
{
free(sp->array);
free(sp);
}
//
//
QUEUE *QueueInit(int size)
{
QUEUE *tmp;
tmp = (QUEUE*)util_malloc(sizeof(QUEUE));
tmp->array = (NODE**)util_malloc(size*sizeof(NODE*));
tmp->size = size;
tmp->head = tmp->tail = tmp->num = 0;
return tmp;
}
// ：1 ，0
int QueueEmpty(QUEUE *qp)
{
if (qp->num <= 0 || qp == NULL)
return 1;
else return 0;
}
//
int Enqueue(QUEUE *qp, NODE *data)
{
if (qp->num >= qp->size || qp == NULL)
return 1;//
else
{
qp->array[qp->tail] = data;
qp->tail = (qp->tail + 1) % (qp->size); //
++qp->num;
return 0;
}
}
//
int Dequeue(QUEUE *qp, NODE **data)
{
if (qp->num <= 0 || qp == NULL)
return 1;
else
{
*data = qp->array[qp->head];
qp->head = (qp->head + 1) % (qp->size); //
--qp->num;
return 0;
}
}
//
void QueueDestory(QUEUE *qp)
{
free(qp->array);
free(qp);
}
//
NODE *CreatNode()
{
NODE *q;
q = (NODE *)util_malloc(sizeof(NODE));
q->name = NULL;
q->level = -1;
q->n_children = 0;
q->children = NULL;
return q;
}
//
NODE *SearchNode(const char *name, NODE *head)
{
NODE *tmp = NULL;
int i;
if (head != NULL)
{
if (strcmp(name, head->name) == 0)
tmp = head;
else
{
for (i = 0; i < head->n_children&&tmp==NULL; i++)
{
tmp = SearchNode(name, head->children[i]);// ， tmp ，
}
}
}
return tmp;
}
// ，
void ReadFile(NODE **head, const char *filename)
{
NODE *tmp = NULL;
int i = 0, n = 0;
char name[MAX], child[MAX];
FILE *fp;
fp = util_fopen(filename, "r");
while (fscanf(fp, "%s %d", name, &n) != EOF)
{
if (*head == NULL)
{
tmp = *head = CreatNode();// ，
tmp->name = _strdup(name);// ,strdup ， strcpy ， , strdup ， free ;
}
else
{
tmp = SearchNode(name, *head);// name , ， name
}
tmp->n_children = n;
tmp->children = (NODE**)util_malloc(n*sizeof(NODE*));
if (tmp->children == NULL)
{
fprintf(stderr, "Dynamic allocation error !
");
exit(EXIT_FAILURE);
}
// ， ，
for (i = 0; i < n; i++)
{
fscanf(fp, "%s", child);
tmp->children[i] = CreatNode();//
tmp->children[i]->name = _strdup(child);
}
}
fclose(fp);
}
/*
1： ( )
： （ ） ，
*/
void Bfs_Tree(NODE *head)
{
NODE *p = NULL;
QUEUE *q = NULL;//
STACK *s = NULL;//
int i = 0;
q = QueueInit(100);// 100
s = StackInit(100);// 100
head->level = 0;// 0
Enqueue(q, head);//
// level
// ，
while (QueueEmpty(q) == 0)//
{
Dequeue(q, &p);//
for (i = 0; i < p->n_children; i++)
{
p->children[i]->level = p->level + 1; // ： 1
Enqueue(q, p->children[i]);//
}
Push(s, p);// p ，
}
while (StackEmpty(s) == 0)
{
Pop(s, &p);
fprintf(stdout, "%d %s
", p->level, p->name);
}
//
QueueDestory(q);
StackDestroy(s);
}
/*
2： （ ）
：
*/
void DFS_Tree(NODE *head, char *str,char **iBest)
{
int i = 0;
char *tmp = NULL;
if (head == NULL)
return;
tmp = (char*)util_malloc((strlen(str) + strlen(head->name)+1)*sizeof(char)); // , ： ＋1， tmp '\0', ， free（tmp）
sprintf(tmp, "%s%s", str, head->name); // 5 printf
if (head->n_children == 0)
{
if (*iBest == NULL || strlen(*iBest) < strlen(tmp))
{
free(*iBest); // ， strdup ，
*iBest = _strdup(tmp);
}
}
for (i = 0; i < head->n_children; i++)
{
DFS_Tree(head->children[i], tmp,iBest);
}
free(tmp); //
}
// ( )
void Destoy_Tree(NODE *head)
{
int i;
if (head == NULL)
return;
else
{
for (i = 0; i < head->n_children; i++)
Destoy_Tree(head->children[i]);
free(head->name);// name strdup
free(head->children);//
free(head);
}
}
int main(int argc, char **argv)
{
NODE *head = NULL;
char *iBest = NULL;
if (argc != 2)
{
fprintf(stderr, "Lack of parameters!
");
exit(EXIT_FAILURE);
}
ReadFile(&head, argv[1]);
Bfs_Tree(head);
DFS_Tree(head, "", &iBest);
fprintf(stdout, "%s
", iBest);
free(iBest);
Destoy_Tree(head);
system("pause");
return 0;
}
まとめ:1.プログラム中(tmp=(char*)util_malloc((strlen(str)+strlen(head->name)*sizeof(char));//申請スペース、注意:ここのスペースは+1が必要で、tmp文字列の末尾の'0'を格納し、そうでなければ、裏面free(tmp)エラーを引き起こす)ここで注意2.freeは空のポインタ(p=NULL、free(p);)を解放することができるこれもなぜpのメモリを解放したのか、p=NULL(p=malloc(sizeof(...)、free(p)、p=NULL)と続く.これは主にp 3.mallocを再び解放した後に必ず手動でfreeを落とすことを避け、一般空間は少し大きく申請する