プログラマ専用SNS ミクプラ


https://dixq.net/forum/

解決してませんでした＞＜

https://dixq.net/forum/viewtopic.php?f=3&t=10949

ページ 1 ／ 1

解決してませんでした＞＜

Posted: 2012年6月29日(金) 01:10
by れお

コード: 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct school_record SRec;
struct school_record {
    float gpa;
    int credit;
    char name[200];
    SRec *next;
    SRec *left,*right;
};

//連結リストの先頭要素を削除、さらにそれを返す
SRec* Delete(SRec head)
{
	SRec* tmp;
	tmp=head.next;				//tmpに先頭要素を保存
	tmp->next=NULL;
	head.next=head.next->next;	//先頭要素を削除
	return tmp;
}

//データを追加する
SRec* Insert(SRec *node, int (*comp)(const void *,const void *))
{
	SRec **p;
	SRec *tree=NULL,*newnode=NULL;
	SRec head;
	head.next = node;
	tree=(SRec*)malloc(sizeof(SRec));
	if (tree == NULL)
	{
		fprintf(stderr,"メモリ不足");
		return NULL;
	}
	tree->left=NULL;
	tree->right=NULL;
	tree=Delete(head);
	p=&tree;					//根から開始
	while(*p!=NULL)
	{
		if(comp(*p,node->next)>=0)
		{
			p = &(*p)->right;			// 追加データの方が大∴右へ進む
		}
		else
		{
			p = &(*p)->left;			// 追加データの方が小∴左へ進む
		}
		node=node->next;
	}

return tree;
}

SRec* Listsort(SRec *node,int (*comp)(const void *,const void *))
{
	SRec head; //ソート前リスト
	SRec top;  //ソート後リスト

	head.next = node;  // head.next はソート前のリストへのポインタ
    top.next = NULL;  // top.next はソート後のリストへのポインタ

    while (head.next != NULL)
    {  // head が空になるまで繰り返す
    	SRec *save1 = &head;        // 現在の最大値の一つ前を指す
    	SRec *save2 = head.next;    // 先頭要素を現在の最大値とする
    	SRec *p;                     // head を順に見ていくポインタ
    	for (p = &head; p->next != NULL; p = p->next)
    	{
    		if (comp(p->next, save2) > 0)
    		{  // 現在の最大値と比較
    			save1 = p;           // 新しい最大値の一つ前を指す
    			save2 = p->next;     // 新しい最大値を指す
    			}
    	}
    	save1->next = save2->next; // save2 を head から削除
    	save2->next = top.next;    // save2 を top の先頭に挿入
    	top.next = save2;          // save2 を top の先頭に挿入
    }
    return top.next;  // ソート後のリストへのポインタを返す
}


int compare_gpa(const void * a, const void * b)
{
    SRec* tmp1 = (SRec*) a;
    SRec* tmp2 = (SRec*) b;
    if (tmp1->gpa == tmp2->gpa)
        return 0;
    else if (tmp1->gpa > tmp2->gpa)
        return 1;
    else
        return -1;                         //これは - ではできない∵int
}
int compare_credit(const void* a, const void* b)
{
    SRec* tmp1 = (SRec*) a;
    SRec* tmp2 = (SRec*) b;
    return tmp1->credit - tmp2->credit;
}

int compare_name(const void * a, const void * b)
{
    SRec* tmp1 = (SRec*) a;
    SRec* tmp2 = (SRec*) b;
    return strcmp(tmp1->name, tmp2->name);
}

SRec* Input(FILE* fpi)
{
	SRec head;
    SRec *node;
    SRec *tail;
    head.next = NULL;/*これが NULL だとリストにはまだ 1つもノードがないことを表す。
                       これが NULL でないとリストに最低 1つはノードがあることになります。
                       実際にはまだリストは空っぽだから NULL する。*/

    tail = &head;
    while (1)
    {
        node = (SRec *) malloc(sizeof(SRec));//これは配列ではない
        if (node == NULL)
        {
            fprintf(stderr,"メモリ不足");
            return NULL;
        }
        if (fscanf(fpi, "%f%d%s", &node->gpa, &node->credit, node->name) != 3)
        {
            break;  // 読み込みに失敗したら EOF (feof は使わないほうがよい)
        }
        node->next = NULL;  // この node を末尾要素とする
        for (tail = &head; tail->next != NULL; tail = tail->next) ;// 現在のリストの末尾要素を探す
        tail->next = node;  // 見つかった末尾要素に node を追加する。
    }
    free(node);
    return head.next;  // リストの先頭要素へのポインタを返す。
}

void Output(SRec *node, FILE* fpo)
{
	SRec* list;
    for (list=node; list != NULL; list = list->next)
        fprintf(fpo,"%3.1f %d %s\n", list->gpa, list->credit, list->name);
}
void Free(SRec* node)
{
	SRec *list,*next;
	for(list=node;list != NULL;list = next)
	{
		next=list->next;
		free(list);
	}
}
int main(int argc, char *argv[])
{
    SRec *tree,*node=NULL;
    FILE *fpi, *fpo;
    int (*comp)(const void*,const void*);//比較関数へのポインタ
    if (argc != 4)
    {
        fprintf(stderr, "Illegal number of argument.\n");
        return (-1);
    }
    if ((fpi = fopen(argv[2], "r")) == NULL)
    {
        fprintf(stderr, "Can't open input file <%s>.\n", argv[2]);
        return (-1);
    }
    if ((fpo = fopen(argv[3], "w")) == NULL)
    {
        fprintf(stderr, "Can't open output file <%s>.\n", argv[3]);
        return (-1);
    }
    if (strcmp(argv[1], "gpa") == 0)
        comp=compare_gpa;//&はどちらでもいい
    else if (strcmp(argv[1], "credit") == 0)
        comp=compare_credit;
    else if (strcmp(argv[1], "name") == 0)
        comp=compare_name;
    node = Input(fpi);
    if (node == NULL) return 1;

    node=Listsort(node,comp);
    tree=Insert(node,comp);
    Output(node, fpo);
    Free(node);
    fclose(fpi);
    fclose(fpo);
    return 0;
}
ファイルにある成績データをInput関数で連結リストにいれて、Insert関数でその連結リストから二分探索木をつくりたいんですが、困ってます。

連結リストから 先頭要素を削除→削除した要素を２分探索木への追加（挿入）→先頭要素を削除→・・・

としたいのです。つまり挿入したと同時に先頭要素を代入したいのです。
そこで、約４０行目のwhile文の中身をみてほしいのですが。これだと、最初の根であるtreeから右にいくともうずっと右にいったままでかえってこれませんよね？（まだ挿入したとこに削除した先頭要素であるデータを代入する命令はかいていませんが・・・）
どうやったらまた根にもどってきて左右を選んでいったりすることができるのでしょうか？調べてもあんまり出てこないし困ってます＞＜
どなたかお願いします。

Re: 連結リストと二分探索木について

Posted: 2012年6月29日(金) 06:29
by beatle
つまり悩んでおられるのは「木探索」ですね。

いろいろ検索できるように用語を書いておきますね。
まず木探索には主に2種類あります。「深さ優先探索」と「幅優先探索」です。
次に、どうやってプログラムで実装するかというと「再帰関数」で実装することが多いと思います。
木構造を辿って行く事を「トラバース」といったりします。
--用語終了--

深さ優先探索の関数は大体次のような形の関数になります。

コード: 

void VisitTree(Tree* t)
{
    if (t == NULL) {
        return;
    }

    /* t自体の処理をする */

    /* t->leftとt->rightの処理を再帰的に行う */
    VisitTree(t->left);
    VisitTree(t->right);
}
この形にすると、まず与えられたノードtに対して処理を行い、次に左側のノードについて処理を行い、左側の処理がすべて終わったら右側の処理に移ります。
この関数は深さ優先探索をします。

tに対する処理、左側ノードの処理、右側ノードの処理の順番を入れ替えることで、探索の順番にバリエーションが発生します。
例えば、tの左側の木を全部探索し、次にt自体を処理し、最後にtの右側の木を全部探索する、という順番にもできますね。

頑張ってください。

Re: 連結リストと二分探索木について

Posted: 2012年7月01日(日) 13:06
by かずま
つまり悩んでおられるのは「二分探索木の作り方」ですね。

それなら、まずは「二分探索木の作り方」だけに注目してプログラムを作ってみてください。
ファイルから入力した単一データだけで二分探索木を作るんです。
連結リストからデータを移すことはそのあとです
また、構造体の 3つのメンバそれぞれについて比較関数を用意することも今の段階では不要です。

コード: 

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

typedef struct Node Node;
struct Node {
    int credit;
    Node *left, *right;
};

void printTree(Node *node)
{
    if (node == NULL) return;
    printTree(node->left);
    printf(" %d\n", node->credit);  // inorder traversal
    printTree(node->right);
}

void freeTree(Node *node)
{
    if (node == NULL) return;
    freeTree(node->left);
    freeTree(node->right);
    free(node);  // postorder traversal
}

void addTree(Node **root, Node *node)
{
    Node *p = *root;
    if (p == NULL) {
        *root = node;
        return;
    }
    if (node->credit < p->credit)  // compare_credit
        addTree(&p->left, node);
    else
        addTree(&p->right, node);
}

Node *makeTree(FILE *fp)
{
    Node *root = NULL;
    while (1) {
        Node *node = malloc(sizeof(Node));
        if (node == NULL) {
            fprintf(stderr, "out of memory\n");
            freeTree(root);
            return NULL;
        }
        if (fscanf(fp, "%d", &node->credit) != 1) {
            free(node);
            break;
        }
        node->left = node->right = NULL;
        addTree(&root, node);
    }
    return root;
}

int main(void)
{
    Node *root = makeTree(stdin);
    printTree(root);
    freeTree(root);
    return 0;
}
ただし、この作り方では、ランダムな入力について左右のバランスのとれた木が作られますが、
入力がソート済みだと右の枝にばかりノードが追加され、リストと同じ構造になってしまいます。
どちらにしても、できた木構造がソート済みになっていることには間違いありませんが。

ということで、木を作るときの入力がファイルでなくてリストの場合も、ソートしていないリストを
用いないといけないので、元のプログラムはダメです。Listsort は不要です。

また、Input の中で末尾要素を求めるのに、
常に先頭要素からたどっていくという愚をまた繰り返しています。
末尾要素は一つ前の要素を追加したときに分かっています。
それよりも、後でソートすることを考えたら、逆順になってもいいので、
入力データを先頭に挿入するだけで十分です。

main の中の Free(node) は、すべてのノード、すなわちリストを解放するもので、
Free の中の free(list) は、一つのノードを解放するものですが、
名前が反対のまま修正されていません。

Re: 連結リストと二分探索木について

Posted: 2012年7月01日(日) 15:04
by れお

コード: 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct school_record SRec;
struct school_record {
    float gpa;
    int credit;
    char name[200];
    SRec *next;
    SRec *left,*right;
};

//連結リストの先頭要素を削除、さらにそれを返す
SRec* Delete(SRec head)
{
	SRec* tmp;
	tmp=head.next;				//tmpに先頭要素を保存
	tmp->next=NULL;
	head.next=head.next->next;	//先頭要素を削除
	return tmp;
}

//データを追加する
SRec* Insert(SRec *node, int (*comp)(const void *,const void *))
{
	SRec **p;
	SRec *root=NULL,*newnode=NULL;
	SRec head;
	head.next = node;
	root=(SRec*)malloc(sizeof(SRec));
	if (root == NULL)
	{
		fprintf(stderr,"メモリ不足");
		return NULL;
	}
	root->left=NULL;
	root->right=NULL;
	root=Delete(head);
	p=&root;					//根から開始
	node=node->next;
	while(node!=NULL)
	{
		while(*p!=NULL)
		{
			if(comp(node, *p)>=0)
			{
				p = &(*p)->right;			// 追加データの方が大∴右へ進む
				}
			else
			{
				p = &(*p)->left;			// 追加データの方が小∴左へ進む
				}
		}
		if((newnode=(SRec*)malloc(sizeof(SRec)))==NULL)
			printf("out of memorry:newnode");
		newnode->left=NULL;
		newnode->right=NULL;
		newnode=Delete(head);
		printf("%3.1f %d %s\n", newnode->gpa, newnode->credit, newnode->name);
		*p=newnode;
		p=&root;
		node=node->next;
	}
return root;
}

int compare_gpa(const void * a, const void * b)
{
    SRec* tmp1 = (SRec*) a;
    SRec* tmp2 = (SRec*) b;
    if (tmp1->gpa == tmp2->gpa)
        return 0;
    else if (tmp1->gpa > tmp2->gpa)
        return 1;
    else
        return -1;                         //これは - ではできない∵int
}
int compare_credit(const void* a, const void* b)
{
    SRec* tmp1 = (SRec*) a;
    SRec* tmp2 = (SRec*) b;
    return tmp1->credit - tmp2->credit;
}

int compare_name(const void * a, const void * b)
{
    SRec* tmp1 = (SRec*) a;
    SRec* tmp2 = (SRec*) b;
    return strcmp(tmp1->name, tmp2->name);
}

SRec* Input(FILE* fpi)
{
	SRec head;
    SRec *node;
    SRec *tail;
    head.next = NULL;/*これが NULL だとリストにはまだ 1つもノードがないことを表す。
                       これが NULL でないとリストに最低 1つはノードがあることになります。
                       実際にはまだリストは空っぽだから NULL する。*/

    tail = &head;
    while (1)
    {
        node = (SRec *) malloc(sizeof(SRec));//これは配列ではない
        if (node == NULL)
        {
            fprintf(stderr,"メモリ不足");
            return NULL;
        }
        if (fscanf(fpi, "%f%d%s", &node->gpa, &node->credit, node->name) != 3)
        {
            break;  // 読み込みに失敗したら EOF (feof は使わないほうがよい)
        }
        node->next = NULL;  // この node を末尾要素とする
        for (tail = &head; tail->next != NULL; tail = tail->next) ;// 現在のリストの末尾要素を探す
        tail->next = node;  // 見つかった末尾要素に node を追加する。
    }
    free(node);
    return head.next;  // リストの先頭要素へのポインタを返す。
}

void Output(SRec *node, FILE* fpo)
{
	SRec* list;
    for (list=node; list != NULL; list = list->next)
        fprintf(fpo,"%3.1f %d %s\n", list->gpa, list->credit, list->name);
}

void Free(SRec* node)
{
	SRec *list,*next;
	for(list=node;list != NULL;list = next)
	{
		next=list->next;
		free(list);
	}
}

int main(int argc, char *argv[])
{
    SRec *root,*node=NULL;
    FILE *fpi, *fpo;
    int (*comp)(const void*,const void*);//比較関数へのポインタ
    if (argc != 4)
    {
        fprintf(stderr, "Illegal number of argument.\n");
        return (-1);
    }
    if ((fpi = fopen(argv[2], "r")) == NULL)
    {
        fprintf(stderr, "Can't open input file <%s>.\n", argv[2]);
        return (-1);
    }
    if ((fpo = fopen(argv[3], "w")) == NULL)
    {
        fprintf(stderr, "Can't open output file <%s>.\n", argv[3]);
        return (-1);
    }
    if (strcmp(argv[1], "gpa") == 0)
        comp=compare_gpa;//&はどちらでもいい
    else if (strcmp(argv[1], "credit") == 0)
        comp=compare_credit;
    else if (strcmp(argv[1], "name") == 0)
        comp=compare_name;
    node = Input(fpi);
    if (node == NULL) return 1;
    root=Insert(node,comp);
    Output(node, fpo);
    Free(node);
    fclose(fpi);
    fclose(fpo);
    return 0;
}
すみません。ちょっと疑問がおおすぎるので先にこっちをみてほしいです＞＜

Listsortは必要なかったのですが、Insertを作るときに参考にするためにおいてました。けしとくべきでしたm(__)m
いってませんでしたがm(__)m今回はソート前の連結リストを出力（入力したままの順序で出力）したいのでInput関数をまた前の状態にもどしました。
Delete関数は先頭要素をぬきだすとどんどん ->next　でうしろのものもついてくるので先頭のみをとりだす関数です。（Insert関数では、一度先頭要素は削除したので、次ループ内でよびだしたときは次の（先頭）要素を削除しているはず）
Insertの大部分は教科書を参考にしたのでほぼ間違ってないと思います。

ただDelete関数は自分で作ったもので、教科書は１つのデータしか挿入してなかったため、返り値などは自分で二分探索木の先頭であるrootにしてます。（のちにこの２分探索木を走査してソート済みの線形リストを作成するつもりです）


上のコードで実行したところ
入力ファイルは
3.5 27 jiro
2.7 24 taro
3.7 30 saburo
1 26 gyou
2.5 31 byou
のとき、
出力ファイルは
3.5 27 jiro
となり、（入力ファイルと同じものを出力したいのに・・・　１６７行目でかわってるからでしょうか？１６７と１６８行目の間にnode=Input(fpi)とすればいけそうですが、同じことを２回していいのか・・・？）
５９行目で標準出力してるつもりが標準出力にはなにも表示されていません。なぜ？？；

ちょっとかずまさんが言ってるFreeのことは理解できてません＞＜
またInsert関数内でもfreeがよくわからないので省いています（自分の中ではInseertの最後にfree(root)とfree(newnode)すればいいとおもっているのですが・・・）



あと、二分探索木がちゃんと作成されているかを知るためには　％ｐ　をつかったらできるようなのですがどうすればいいのかいまいちわかりません・・・

以上が今つまずいてるところです。
どなたかどうすれば解決できるのかおしえてくださいお願いしますm(__)m

Re: 連結リストと二分探索木について

Posted: 2012年7月01日(日) 18:17
by かずま
SRec は List用の next と、Tree用の left, right の両方を持っているので、
List から取り出した node がそのまま Tree の node として使えます。
だから、Insert の中では free も malloc も不要です。

コード: 

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

typedef struct school_record SRec;
struct school_record {
    float gpa;
    int credit;
    char name[200];
    SRec *next;
    SRec *left, *right;
};
 
// Tree の中の node をを通りがけ順 (inorder traversal) で出力する
void OutputTree(SRec *node, FILE *fp)
{
    if (node == NULL) return;
    OutputTree(node->left, fp);
    fprintf(fp, "%3.1f %2d %s\n", node->gpa, node->credit, node->name);
    OutputTree(node->right, fp);
}

// Tree の中の node を帰りがけ順 (postorder traversal) で解放する
void FreeTree(SRec *node)
{
    if (node == NULL) return;
    FreeTree(node->left);
    FreeTree(node->right);
    free(node);
}

// List の中の node をすべて出力する
void OutputList(SRec *list, FILE *fp)
{
    SRec* node;
    for (node = list; node != NULL; node = node->next)
        fprintf(fp, "%3.1f %2d %s\n", node->gpa, node->credit, node->name);
}
 
// List の中の node をすべて解放する
void FreeList(SRec* list)
{
    SRec *node, *next;
    for (node = list; node != NULL; node = next) {
        next = node->next;
        free(node);
    }
}
 
// Tree に node を追加する
void AddTree(SRec **root, SRec *node, int (*comp)(const void *, const void *))
{
    SRec *p = *root;
    if (p == NULL)
        *root = node;                   // leaf なので node をここに追加
    else if (comp(node, p) < 0)
        AddTree(&p->left, node, comp);  // node が小さいので左に追加
    else
        AddTree(&p->right, node, comp); // node が大きいので右に追加
}

// List から node を取り出して Tree に追加して、その Tree を返す
SRec* Insert(SRec *list, int (*comp)(const void *, const void *))
{
    SRec *root = NULL;  // node が一つもない Tree
    SRec *node, *next;
    for (node = list; node != NULL; node = next) {
        next = node->next;
        node->next = NULL;               // この node を List から削除
        node->left = node->right = NULL;
        AddTree(&root, node, comp);      // この node を Tree に追加    
    }
    return root;  // Tree の root を返す
}
 
int compare_gpa(const void *a, const void *b)
{
    SRec* tmp1 = (SRec*) a;
    SRec* tmp2 = (SRec*) b;
    if (tmp1->gpa == tmp2->gpa)
        return 0;
    else if (tmp1->gpa > tmp2->gpa)
        return 1;
    else
        return -1; // gpa が double なので return tmp1->gpa - tmp2->gpa; と書けない
}

int compare_credit(const void *a, const void *b)
{
    SRec* tmp1 = (SRec*) a;
    SRec* tmp2 = (SRec*) b;
    return tmp1->credit - tmp2->credit;
}
 
int compare_name(const void *a, const void *b)
{
    SRec* tmp1 = (SRec*) a;
    SRec* tmp2 = (SRec*) b;
    return strcmp(tmp1->name, tmp2->name);
}
 
SRec* Input(FILE* fp)
{
    SRec head;
    head.next = NULL;  // node が一つもない List
 
    while (1) {
        SRec *node = (SRec *) malloc(sizeof(SRec));
        if (node == NULL) {
            fprintf(stderr,"メモリ不足");
            FreeList(head.next);
            return NULL;
        }
        if (fscanf(fp, "%f%d%s", &node->gpa, &node->credit, node->name) != 3) {
            free(node);
            break;  // 読み込みに失敗したら EOF
        }
        node->next = head.next;  // この node を先頭要素とする
        head.next = node;        // この node を先頭要素とする
    }
    return head.next;  // リストの先頭要素へのポインタを返す。
}
 
int main(int argc, char *argv[])
{
    SRec *root, *list;
    FILE *fpi, *fpo;
    int (*comp)(const void*,const void*);  // 比較関数へのポインタ
    if (argc != 4) {
        fprintf(stderr, "Illegal number of argument.\n");
        return (-1);
    }
    if ((fpi = fopen(argv[2], "r")) == NULL) {
        fprintf(stderr, "Can't open input file <%s>.\n", argv[2]);
        return (-1);
    }
    if ((fpo = fopen(argv[3], "w")) == NULL) {
        fprintf(stderr, "Can't open output file <%s>.\n", argv[3]);
        return (-1);
    }
    if (strcmp(argv[1], "gpa") == 0)
        comp = compare_gpa;
    else if (strcmp(argv[1], "credit") == 0)
        comp = compare_credit;
    else if (strcmp(argv[1], "name") == 0)
        comp = compare_name;
    else { fprintf(stderr, "key は gpa, creait, name\n"); return 1; }

    list = Input(fpi);
    if (list == NULL) return 1;
    OutputList(list, fpo); fprintf(fpo, "---\n");
    root = Insert(list, comp);
    OutputTree(root, fpo);
    FreeTree(root);
    fclose(fpi);
    fclose(fpo);
    return 0;
}

Re: 連結リストと二分探索木について

Posted: 2012年7月01日(日) 21:05
by れお
ありがとうございます！！まだ解読しているとちゅうです。。。が、確認したいのですが

今回はソート前の連結リストを出力（入力したままの順序で出力）したいのでInput関数は前のにかえればいい。
Delete関数などつくらなくてもInsertとAddTreeでちゃんとnodeの後ろの要素は削除できてる。
で、教科書とかのははじめてListをつくってたけど、今回のはもともとできてるやつをもってくるだけだからmallocはいらない。
あと、二分探索木がちゃんと作成されているかを知るために通りがけ順で出力している。

list = Input(fpi);
if (list == NULL) return 1;
OutputList(list, fpo); fprintf(fpo, "---\n");
root = Insert(list, comp);
OutputTree(root, fpo);
FreeTree(root);
としてnode(かずまさんのではlist)をInsertする前にOutputListしてるからちゃんと出力できてる。


という感じでいいのでしょうか？


freeがどうもうまく理解できないです・・・もうちょっと調べてみます。

Re: 連結リストと二分探索木について

Posted: 2012年7月01日(日) 23:12
by れお
なるほどfree理解しました＾＾

Re: 連結リストと二分探索木について

Posted: 2012年7月02日(月) 00:20
by かずま
れお さんが書きました:あと１５４行目はrootじゃなくてlistですよね？
Insert で List の先頭の node がそのまま Tree の root になりますから、
main の list と root は同じノードを指しています。
だから、OutputTree(list); と書いても同じ結果になりますが、意味が違います。
Insert の中で、すべてのノードの next を NULL にしていますから、ノードは
リストとして連結されていません。
れお さんが書きました:あと、二分探索木がちゃんと作成されているかを知るために通りがけ順で出力している。
二分探索木を表示してみましょうか。

コード: 

#define DEPTH 8

// Tree の中の node を indent 付きで出力する
void DrawTree(SRec *node, FILE *fp, int indent)
{
    if (node == NULL) return;
    DrawTree(node->right, fp, indent + DEPTH);
    fprintf(fp, "%*s%3.1f %2d %s\n", indent, "", node->gpa, node->credit, node->name);
    DrawTree(node->left, fp, indent + DEPTH);
}

int main(void)
       :
    list = Input(fpi);
    if (list == NULL) return 1;
    OutputList(list, fpo); fprintf(fpo, "---\n");
    root = Insert(list, comp);
    OutputTree(root, fpo); fprintf(fpo, "---\n");
    DrawTree(root, fpo, 0);
    FreeTree(root);

コード: 

2.5 31 byou
1.0 26 gyou
3.7 30 saburo
2.7 24 taro
3.5 27 jiro
---
1.0 26 gyou
2.5 31 byou
2.7 24 taro
3.5 27 jiro
3.7 30 saburo
---
        3.7 30 saburo
                        3.5 27 jiro
                2.7 24 taro
2.5 31 byou
        1.0 26 gyou
右に90°回転、又は顔を左に 90°回転してみると、木が見えますよね。

コード: 

               2.5 (root)
           ／        ＼
       1.0              3.7
                     ／
                 2.7
                    ＼ 
                     3.5

Re: 連結リストと二分探索木について

Posted: 2012年7月02日(月) 21:24
by れお
DEFTHとかきいたことなくてわからないですがまぁできてるということはわかりました＾＾
でも、右に９０度回転させると木が見える　のいみがわかりません＾＾；
木ってただ根から２つにわかれていってたら木じゃないんですかね（回転しなくても）？

Re: 連結リストと二分探索木について

Posted: 2012年7月02日(月) 21:50
by box
れお さんが書きました:DEFTHとかきいたことなくてわからないですがまぁできてるということはわかりました＾＾
でも、右に９０度回転させると木が見える　のいみがわかりません＾＾；
木ってただ根から２つにわかれていってたら木じゃないんですかね（回転しなくても）？
DEFTHじゃなくて、DEPTH（DEEPの名詞、意味：深さ、枝分かれの段数）です。
かずまさんのコードでは、1段分を8文字分ずらすことで段数を表現しています。
また、回転した方が、木の形状（根っこが上にある、という意味では本来の木とは逆ですが）が
わかりやすい、ということでありましょう。
回転しなくても木に見えるのであれば、それでもかまわないと思います。

Re: 連結リストと二分探索木について

Posted: 2012年7月03日(火) 03:40
by れお
なるほどそういうことだったんですか！！
ありがとうございます＾＾

木とか意識するものなんですかね？

Re: 連結リストと二分探索木について

Posted: 2012年7月05日(木) 02:36
by かずま
れお さんが書きました:あと、二分探索木がちゃんと作成されているかを知るためには　％ｐ　をつかったらできるようなのですがどうすればいいのかいまいちわかりません・・・

コード: 

void DumpTree(SRec *node, FILE *fp)
{
    if (node == NULL) return;
    DumpTree(node->left, fp);
    fprintf(fp, "node=%p, left=%p, right=%p, gpa=%.1f\n",
        node, node->left, node->right, node->gpa);
    DumpTree(node->right, fp);
}

int main(int argc, char *argv[])
        :
    root = Insert(list, comp);
    DumpTree(root, fpo);
    fprintf(fpo, "root=%p\n", root);
実行結果

コード: 

node=002B14D0, left=00000000, right=00000000, gpa=1.0
node=002B15B8, left=002B14D0, right=002B13E8, gpa=2.5
node=002B1300, left=00000000, right=002B1218, gpa=2.7
node=002B1218, left=00000000, right=00000000, gpa=3.5
node=002B13E8, left=002B1300, right=00000000, gpa=3.7
root=002B15B8
ノードがどう繋がっているか分かりますよね。

Re: にぶんぎについて

Posted: 2012年7月12日(木) 18:32
by れお
なるほど！！
そうみるとわかりやすいですね＾＾
ありがとうございました！！

Re: 連結リストと二分探索木について

Posted: 2012年7月13日(金) 01:54
by れお
かずま さんが書きました:

コード: 

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

typedef struct school_record SRec;
struct school_record {
    float gpa;
    int credit;
    char name[200];
    SRec *next;
    SRec *left, *right;
};
 
// Tree の中の node をを通りがけ順 (inorder traversal) で出力する
void OutputTree(SRec *node, FILE *fp)
{
    if (node == NULL) return;
    OutputTree(node->left, fp);
    fprintf(fp, "%3.1f %2d %s\n", node->gpa, node->credit, node->name);
    OutputTree(node->right, fp);
}

// Tree の中の node を帰りがけ順 (postorder traversal) で解放する
void FreeTree(SRec *node)
{
    if (node == NULL) return;
    FreeTree(node->left);
    FreeTree(node->right);
    free(node);
}

// List の中の node をすべて出力する
void OutputList(SRec *list, FILE *fp)
{
    SRec* node;
    for (node = list; node != NULL; node = node->next)
        fprintf(fp, "%3.1f %2d %s\n", node->gpa, node->credit, node->name);
}
 
// List の中の node をすべて解放する
void FreeList(SRec* list)
{
    SRec *node, *next;
    for (node = list; node != NULL; node = next) {
        next = node->next;
        free(node);
    }
}
 
// Tree に node を追加する
void AddTree(SRec **root, SRec *node, int (*comp)(const void *, const void *))
{
    SRec *p = *root;
    if (p == NULL)
        *root = node;                   // leaf なので node をここに追加
    else if (comp(node, p) < 0)
        AddTree(&p->left, node, comp);  // node が小さいので左に追加
    else
        AddTree(&p->right, node, comp); // node が大きいので右に追加
}

// List から node を取り出して Tree に追加して、その Tree を返す
SRec* Insert(SRec *list, int (*comp)(const void *, const void *))
{
    SRec *root = NULL;  // node が一つもない Tree
    SRec *node, *next;
    for (node = list; node != NULL; node = next) {
        next = node->next;
        node->next = NULL;               // この node を List から削除
        node->left = node->right = NULL;
        AddTree(&root, node, comp);      // この node を Tree に追加    
    }
    return root;  // Tree の root を返す
}
 
int compare_gpa(const void *a, const void *b)
{
    SRec* tmp1 = (SRec*) a;
    SRec* tmp2 = (SRec*) b;
    if (tmp1->gpa == tmp2->gpa)
        return 0;
    else if (tmp1->gpa > tmp2->gpa)
        return 1;
    else
        return -1; // gpa が double なので return tmp1->gpa - tmp2->gpa; と書けない
}

int compare_credit(const void *a, const void *b)
{
    SRec* tmp1 = (SRec*) a;
    SRec* tmp2 = (SRec*) b;
    return tmp1->credit - tmp2->credit;
}
 
int compare_name(const void *a, const void *b)
{
    SRec* tmp1 = (SRec*) a;
    SRec* tmp2 = (SRec*) b;
    return strcmp(tmp1->name, tmp2->name);
}
 
SRec* Input(FILE* fp)
{
    SRec head;
    head.next = NULL;  // node が一つもない List
 
    while (1) {
        SRec *node = (SRec *) malloc(sizeof(SRec));
        if (node == NULL) {
            fprintf(stderr,"メモリ不足");
            FreeList(head.next);
            return NULL;
        }
        if (fscanf(fp, "%f%d%s", &node->gpa, &node->credit, node->name) != 3) {
            free(node);
            break;  // 読み込みに失敗したら EOF
        }
        node->next = head.next;  // この node を先頭要素とする
        head.next = node;        // この node を先頭要素とする
    }
    return head.next;  // リストの先頭要素へのポインタを返す。
}
 
int main(int argc, char *argv[])
{
    SRec *root, *list;
    FILE *fpi, *fpo;
    int (*comp)(const void*,const void*);  // 比較関数へのポインタ
    if (argc != 4) {
        fprintf(stderr, "Illegal number of argument.\n");
        return (-1);
    }
    if ((fpi = fopen(argv[2], "r")) == NULL) {
        fprintf(stderr, "Can't open input file <%s>.\n", argv[2]);
        return (-1);
    }
    if ((fpo = fopen(argv[3], "w")) == NULL) {
        fprintf(stderr, "Can't open output file <%s>.\n", argv[3]);
        return (-1);
    }
    if (strcmp(argv[1], "gpa") == 0)
        comp = compare_gpa;
    else if (strcmp(argv[1], "credit") == 0)
        comp = compare_credit;
    else if (strcmp(argv[1], "name") == 0)
        comp = compare_name;
    else { fprintf(stderr, "key は gpa, creait, name\n"); return 1; }

    list = Input(fpi);
    if (list == NULL) return 1;
    OutputList(list, fpo); fprintf(fpo, "---\n");
    root = Insert(list, comp);
    OutputTree(root, fpo);
    FreeTree(root);
    fclose(fpi);
    fclose(fpo);
    return 0;
}

解決してませんでした！！

これをファイルの中身のデータ数を１万でおこなうとちゃんとひょうじされません＞＜
データ数が少ないときはうごくのに多くなるとうごかないというのはなぜなのでしょうか？？

Re: 連結リストと二分探索木について

Posted: 2012年7月13日(金) 09:58
by かずま
れお さんが書きました:これをファイルの中身のデータ数を１万でおこなうとちゃんとひょうじされません＞＜
データ数が少ないときはうごくのに多くなるとうごかないというのはなぜなのでしょうか？？
こちらでは 1万個のデータでも動きます。
本当にこのプログラムですか？
最後に余計な FreeList(list); を追加しているのではありませんか？

Re: 解決してませんでした＞＜

Posted: 2012年7月13日(金) 14:32
by れお
上ではりつけたプログラムです、インプットの中のエラーの部分でしかフリーリストはしてません(/ _ ; )

もう一度家帰ってから試してみます…
Windowsだからでしょうか…Linuxでやってみます

Re: 解決してませんでした＞＜

Posted: 2012年7月13日(金) 16:11
by みけCAT
10000個のデータでも正しく表示されていると思います。（きちんとした確認はしていません）
しかし、100000個のデータでは強制終了してしまいました。
原因は再帰のしすぎによるスタックオーバーフローだと思います。
テストデータを添付します。
れお さんが書きました:Windowsだからでしょうか…Linuxでやってみます
Linuxでやる場合、実行前に

コード: 

$ ulimit -s unlimited
というコマンドを実行するとうまく動くかもしれません。

Re: 解決してませんでした＞＜

Posted: 2012年7月13日(金) 21:01
by れお
みけCAT さんが書きました:10000個のデータでも正しく表示されていると思います。（きちんとした確認はしていません）
しかし、100000個のデータでは強制終了してしまいました。
原因は再帰のしすぎによるスタックオーバーフローだと思います。
テストデータを添付します。
れお さんが書きました:Windowsだからでしょうか…Linuxでやってみます
Linuxでやる場合、実行前に

コード: 

$ ulimit -s unlimited
というコマンドを実行するとうまく動くかもしれません。
Linuxだと一万個うまくいきました！！

コード: 

$ ulimit -s unlimited
はどこで実行するのですか？はじめてみるもので・・・＞＜
これをコードの最初にかくとエラーがでます＾＾；
(10万個ではアウトプットファイルになにも表示されませんでした)

あと、二分探索木からnameについて昇順に並び替えたリストをつくり、その時間をはかりたいのですが、１万個のとき時間をはかると0.00000となります。下のコードでコマンドラインを
name data.txt output.txt
（data.txtはデータが１万〜１０万はいったファイル）
とするとソートにかかった時間が標準出力に表示されるはずなのですが・・・
先生もバグが起きてる、ちゃんとデバッグしてなかったから、としかいわないのでここしか頼れません＞＜お願いします＞＜
なにか疑問点、不明点などあれば言ってください！！

コード: 

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


typedef struct school_record SRec;
struct school_record {
    float gpa;
    int credit;
    char name[200];
    SRec *next;
    SRec *left, *right;
};

// Tree の中の node をを通りがけ順 (inorder traversal) で出力する
void OutputTree(SRec *node, FILE *fp)
{
    if (node == NULL) return;
    OutputTree(node->left, fp);
    fprintf(fp, "%f %d %s\n", node->gpa, node->credit, node->name);
    OutputTree(node->right, fp);
}

// Tree の中の node を帰りがけ順 (postorder traversal) で解放する
void FreeTree(SRec *node)
{
    if (node == NULL) return;
    FreeTree(node->left);
    FreeTree(node->right);
    free(node);
}

// List の中の node をすべて出力する
void OutputList(SRec *list, FILE *fp)
{
    SRec* node;
    for (node = list; node != NULL; node = node->next)
        fprintf(fp, "%f %d %s\n", node->gpa, node->credit, node->name);
}

// List の中の node をすべて解放する
void FreeList(SRec* list)
{
    SRec *node, *next;
    for (node = list; node != NULL; node = next) {
        next = node->next;
        free(node);
    }
}

// Tree に node を追加する
void AddTree(SRec **root, SRec *node, int (*comp)(const void *, const void *))
{
    SRec *p = *root;
    if (p == NULL)
        *root = node;                   // leaf なので node をここに追加
    else if (comp(node, p) < 0)
        AddTree(&p->left, node, comp);  // node が小さいので左に追加
    else
        AddTree(&p->right, node, comp); // node が大きいので右に追加
}

// List から node を取り出して Tree に追加して、その Tree を返す
SRec* Insert(SRec *list, int (*comp)(const void *, const void *))
{
    SRec *root = NULL;  // node が一つもない Tree
    SRec *node, *next;
    for (node = list; node != NULL; node = next) {
        next = node->next;
        node->next = NULL;               // この node を List から削除
        node->left = node->right = NULL;
        AddTree(&root, node, comp);      // この node を Tree に追加
    }
    return root;  // Tree の root を返す
}

int compare_gpa(const void *a, const void *b)
{
    SRec* tmp1 = (SRec*) a;
    SRec* tmp2 = (SRec*) b;
    if (tmp1->gpa == tmp2->gpa)
        return 0;
    else if (tmp1->gpa > tmp2->gpa)
        return 1;
    else
        return -1; // gpa が double なので return tmp1->gpa - tmp2->gpa; と書けない
}

int compare_credit(const void *a, const void *b)
{
    SRec* tmp1 = (SRec*) a;
    SRec* tmp2 = (SRec*) b;
    return tmp1->credit - tmp2->credit;
}

int compare_name(const void *a, const void *b)
{
    SRec* tmp1 = (SRec*) a;
    SRec* tmp2 = (SRec*) b;
    return strcmp(tmp1->name, tmp2->name);
}

SRec* Input(FILE* fp)
{
    SRec head;
    head.next = NULL;  // node が一つもない List

    while (1) {
        SRec *node = (SRec *) malloc(sizeof(SRec));
        if (node == NULL) {
            fprintf(stderr,"メモリ不足");
            FreeList(head.next);
            return NULL;
        }
        if (fscanf(fp, "%f%d%s", &node->gpa, &node->credit, node->name) != 3) {
            free(node);
            break;  // 読み込みに失敗したら EOF
        }
        node->next = head.next;  // この node を先頭要素とする
        head.next = node;        // この node を先頭要素とする
    }
    return head.next;  // リストの先頭要素へのポインタを返す。
}

SRec* ListMake(SRec* root,SRec* p)			//ソートしたリストの作成 pはリストの最後
{
	SRec* tree=root;
	SRec* node=NULL;
	if(tree == NULL) return tree;
	if(tree->left != NULL)
	{
		node = ListMake(tree->left , tree);
	}
	else
	{
		node = tree;
	}
	if(tree-> right != NULL)
	{
		tree->next=ListMake(tree->right,p);
	}
	else
	{
		tree->next=p;
	}

return node;
}


int main(int argc, char *argv[])
{
    SRec *root, *list;
    FILE *fpi, *fpo;
    clock_t clk_start, clk_end;
    int (*comp)(const void*,const void*);  // 比較関数へのポインタ
    if (argc != 4) {
        fprintf(stderr, "Illegal number of argument.\n");
        return (-1);
    }
    if ((fpi = fopen(argv[2], "r")) == NULL) {
        fprintf(stderr, "Can't open input file <%s>.\n", argv[2]);
        return (-1);
    }
    if ((fpo = fopen(argv[3], "w")) == NULL) {
        fprintf(stderr, "Can't open output file <%s>.\n", argv[3]);
        return (-1);
    }
    if (strcmp(argv[1], "gpa") == 0)
        comp = compare_gpa;
    else if (strcmp(argv[1], "credit") == 0)
        comp = compare_credit;
    else if (strcmp(argv[1], "name") == 0)
        comp = compare_name;
    else { fprintf(stderr, "key は gpa, credit, name\n"); return 1; }

    list = Input(fpi);
    if (list == NULL) return 1;
    root = Insert(list, comp);
    clk_start = clock();
    list=ListMake(root,NULL);
    clk_end = clock();
    printf("%f",(double)(clk_end - clk_start) / CLOCKS_PER_SEC);
    OutputList(list, fpo);
    FreeTree(root);
    fclose(fpi);
    fclose(fpo);
    return 0;
}

Re: 解決してませんでした＞＜

Posted: 2012年7月14日(土) 01:19
by へにっくす
れお さんが書きました:

コード: 

$ ulimit -s unlimited
はどこで実行するのですか？はじめてみるもので・・・＞＜
これをコードの最初にかくとエラーがでます＾＾；
とりあえずここだけ
unixのコマンドだからコードに書いても無意味なのは分かるよね？

UNIXの部屋 コマンド検索: ulimit
http://x68000.q-e-d.net/~68user/unix/pickup?ulimit

Re: 解決してませんでした＞＜

Posted: 2012年7月14日(土) 02:02
by れお
そのあたり全く知識ないのでよくわかりません・・・＞＜

コードをかえるのも怖いというか・・・

Re: 解決してませんでした＞＜

Posted: 2012年7月16日(月) 01:20
by れお
どなたか・・・
１０万はできなくてもいいので、なぜ時間はかれないかだけでも教えてください＞＜

Re: 解決してませんでした＞＜

Posted: 2012年7月16日(月) 02:04
by かずま
れお さんが書きました:どなたか・・・
１０万はできなくてもいいので、なぜ時間はかれないかだけでも教えてください＞＜
printf("%f",(double)(clk_end - clk_start) / CLOCKS_PER_SEC);
のあとに
printf(", start=%ld, end=%ld\n", clk_start, clk_end);
を入れてみてください。

Windows 7, CPU Core i5, M540 2.53MHz で
10000個の場合
C:\tmp>a gpa zzz yyy
0.001000, start=35, end=36

100000個の場合
C:\tmp>a gpa xxx yyy
0.013000, start=251, end=264

VC++ の clock() の精度は msec らしいので、
データが 10000個と少なく、CPU の性能が高い場合、
1ミリ秒未満で実行が終了するのでしょう。

その Windows 7 の VMware Player 上で動く Ubuntu 10.04LTS では、
次のようにデータが 10000個の場合は 0.000000 となりました。
$ ./a.out gpa zzz yyy
0.000000, start=30000, end=30000

$ ./a.out gpa xxx yyy
0.020000, start=200000, end=22000

Re: 解決してませんでした＞＜

Posted: 2012年7月16日(月) 02:13
by かずま
かずま さんが書きました: $ ./a.out gpa zzz yyy
0.000000, start=30000, end=30000

$ ./a.out gpa xxx yyy
0.020000, start=200000, end=22000
コピペの失敗で最後の 0 が落ちました。end=20000 です。

100000個のソートが 20msec できています。
100000個のソートは 10000個のソートの 約31.6倍でできるとすると、
10000個のソートは 1msec 未満になりますね。
Linux の clock() は単位は μsec ですが、精度は msec のようで
0.000000 となっています。

Re: 解決してませんでした＞＜

Posted: 2012年7月16日(月) 02:28
by かずま
かずま さんが書きました:
かずま さんが書きました: コピペの失敗で最後の 0 が落ちました。end=20000 です。

100000個のソートは 10000個のソートの 約31.6倍でできるとすると、
また、ミスった。end=220000 です。

それから、そのプログラムで計っているのは、ソートではなく
木からリストを作るところなので、ソートの O(n log n) では
O(n) のはずだから、100000個が 20 msec でできるのなら
10000個は 2msec でできそうですね。

SRec は 220バイトありますから、100000個だと 22メガバイト
以上のメモリを使うので、仮想記憶のオーバヘッドが加わって、
10000個の2.2メガバイトにくらべて 10倍よりももっと時間が
かかっているのかもしれません。

Re: 解決してませんでした＞＜

Posted: 2012年7月16日(月) 03:26
by れお
回答ありがとうございます！！＞＜
質問と確認があるのですが、

コード: 

    clk_start = clock();
    root = Insert(list, comp);
    list=ListMake(root,NULL);
    clk_end = clock();
とすればちゃんとソートの時間となりますよね？？たしかにあれだけでは木からリストをつくってるだけでした・・・
これだとO(nlogn)でいいんですか？ネットをみてると、似たようなものがありO(nlogn)というのとO(logn)という２つのがでてきてたんですが・・・


この測定は学校のPCでやらないといけないみたいで（他の人と条件をあわすため）
Linuxで時間の計測をしてます。そしてつかってるコンパイラ？はeclipsです。
CPUがどうかはわからないですが、ほかの人は何もすることなく普通に時間計測できてました。
僕が上に貼ったプログラムは間違っているわけではないですよね？
データ数が１０万のときoutputファイルに何も表示されないのはなぜなのでしょうか？

また学校でprintfを付け加えてやってみます＞＜

Re: 解決してませんでした＞＜

Posted: 2012年7月16日(月) 08:38
by みけCAT
れお さんが書きました:これだとO(nlogn)でいいんですか？ネットをみてると、似たようなものがありO(nlogn)というのとO(logn)という２つのがでてきてたんですが・・・
おそらく、（ある程度バランスを保った）二分探索木の挿入と検索1回がそれぞれO(log n)で、
挿入をn回繰り返すからO(n log n)ということだと思います。

「ある程度バランスを保った」とはどういうことでしょうか。
ヒントは、私の10万件のデータを見てみましょう。
（最初の20000行くらいを取り出して入力として与えてもいいです）
れお さんが書きました:データ数が１０万のときoutputファイルに何も表示されないのはなぜなのでしょうか？
Segmentation Faultなどと表示されて強制終了する場合は、

コード: 

$ ulimit -s unlimited
を試してみてください。
強制終了しない場合は、しばらく待ってみてください。自分の環境では400秒くらいかかりました。

追記
やはりバグがあるようですね。10万件のデータを与えて少なくとも1分は経っている状況でも、
0.010000と表示されます。
とりあえず、この関数を試してもらえますか？単位はミリ秒です。

コード: 

#if defined(__WIN32__) || defined(__WIN64__)
#include <windows.h>
unsigned long getzikan(void) {
	return (unsigned long)GetTickCount();
}
#else
#include <sys/time.h>
unsigned long getzikan(void) {
	struct timeval tv;
	gettimeofday(&tv,NULL);
	return (unsigned long)tv.tv_sec*1000+
		(unsigned long)tv.tv_usec/1000000;
}
#endif

Re: 解決してませんでした＞＜

Posted: 2012年7月16日(月) 14:39
by れお
lognの件は納得しました。

$ ulimit -s unlimited
がどこでどうすればいいのかがわかりません。調べたりもしたのですが単語がみたことないものばかりでてきてよくわかりません・・

コード: 

#if defined(__WIN32__) || defined(__WIN64__)
#include <windows.h>
unsigned long getzikan(void) {
    return (unsigned long)GetTickCount();
}
#else
#include <sys/time.h>
unsigned long getzikan(void) {
    struct timeval tv;
    gettimeofday(&tv,NULL);
    return (unsigned long)tv.tv_sec*1000+
        (unsigned long)tv.tv_usec/1000000;
}
#endif
これも＃の意味とかもしらないので、適当にプログラムの上の方にはりつけて実行したのですが何もおこりません・・・＞＜

できることならこういう自分の知らないことは使いたくないのですが・・・
他の同級生は１０万のデータで実行してもバグなどおきずにちゃんと時間表示できてるので（データのファイルも同じものをつかってます）プログラムにどこかおかしい点があるとしか思えないのですが・・・＞＜
でもみたところおかしい点もみあたらずご存じのとおり実行だけがおかしくなってます。

今windowsでやってるからかもしれませんが
コマンドラインを
name data output
として、そのあとで
name output data
とすれば、ソートされたデータファイルであるoutputをもう一度ソートしなおすことになりますが、このときの出力ファイルであるdataには何も表示されなかったりします。

CPUなどが原因ではなくプログラムに異常があるとしか考えられません＞＜

Re: 解決してませんでした＞＜

Posted: 2012年7月16日(月) 14:52
by みけCAT
れお さんが書きました:$ ulimit -s unlimited
がどこでどうすればいいのかがわかりません。調べたりもしたのですが単語がみたことないものばかりでてきてよくわかりません・・
プログラムを実行する前に、端末に

コード: 

ulimit -s unlimited
と入力し、Enterキーを押してください。
これは最初の1回だけでいいはずです。
れお さんが書きました:

コード: 

#if defined(__WIN32__) || defined(__WIN64__)
#include <windows.h>
unsigned long getzikan(void) {
    return (unsigned long)GetTickCount();
}
#else
#include <sys/time.h>
unsigned long getzikan(void) {
    struct timeval tv;
    gettimeofday(&tv,NULL);
    return (unsigned long)tv.tv_sec*1000+
        (unsigned long)tv.tv_usec/1000000;
}
#endif
これも＃の意味とかもしらないので、適当にプログラムの上の方にはりつけて実行したのですが何もおこりません・・・＞＜
当たり前です。
これは時間をミリ秒単位で計測するgetzikan()関数の定義なので、
これをプログラムの上の方に貼り付けた上で、時間の測定を

コード: 

    unsigned long clk_start,clk_end;
    clk_start = getzikan();
    root = Insert(list, comp);
    list=ListMake(root,NULL);
    clk_end = getzikan();
    printf("%lums\n",clk_end-clk_start);
としてみてください。#の意味はとりあえず気にしなくていいです。
[search=google]C言語 プリプロセッサ[/search]
れお さんが書きました:他の同級生は１０万のデータで実行してもバグなどおきずにちゃんと時間表示できてるので（データのファイルも同じものをつかってます）プログラムにどこかおかしい点があるとしか思えないのですが・・・＞＜
でもみたところおかしい点もみあたらずご存じのとおり実行だけがおかしくなってます。
おかしくなるとはどういう状況ですか？
れお さんが書きました:今windowsでやってるからかもしれませんが
コマンドラインを
name data output
として、そのあとで
name output data
とすれば、ソートされたデータファイルであるoutputをもう一度ソートしなおすことになりますが、このときの出力ファイルであるdataには何も表示されなかったりします。
もう一度言いますが、強制終了されましたか？
強制終了されていない場合、しばらく待ってみてください。
Windowsでコンパイラにgccを使用する場合、コンパイルオプションに

コード: 

-Wl,--stack,10485760
を加えてみてください。

自分が改良してみたプログラムを添付します。（余計なことをしてすみません）

Re: 解決してませんでした＞＜

Posted: 2012年7月16日(月) 15:22
by れお
みけCAT さんが書きました:プログラムを実行する前に、端末に

コード: 

ulimit -s unlimited
と入力し、Enterキーを押してください。
これは最初の1回だけでいいはずです。
すみませｎ＞＜　端末とはなんですか？？＞＜申し訳ないです　ほんとにそういう単語が全くわからないのです・・・
おかしくなるとはどういう状況ですか？
昨日まで、というか今はいけたのですが、１０万個のデータの時出力ファイルが表示されなかったのです。（今５万と１０万でやったらちゃんと秒が表示されました＾＾windowsですが）
みけCAT さんが書きました: もう一度言いますが、強制終了されましたか？
強制終了されていない場合、しばらく待ってみてください。
Windowsでコンパイラにgccを使用する場合、コンパイルオプションに

コード: 

-Wl,--stack,10485760
を加えてみてください。
おっしゃるとおりまだ終わってなかっただけでしたm(__)mただ前におっしゃってた通り時間がかかってるのに０．０３１秒とかになりますね。学校のでやるとうまくいくとかはないんですかね・・・笑
コンパイルオプションというのがなにか、どこにあるのかわからないですが・・・
自分が改良してみたプログラムを添付します。（余計なことをしてすみません）
全然余計なことはないですが、理解できそうにないです・・・

Re: 解決してませんでした＞＜

Posted: 2012年7月16日(月) 15:26
by れお
端末に入力するのはよくわからないのでやってませんが、データ数１万で先ほどかかれていたものを付け加えてやってみました。
１万個のデータでやると３１ｍｓとなりました！

コード: 

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


typedef struct school_record SRec;
struct school_record {
    float gpa;
    int credit;
    char name[200];
    SRec *next;
    SRec *left, *right;
};

#if defined(__WIN32__) || defined(__WIN64__)
#include <windows.h>
unsigned long getzikan(void) {
    return (unsigned long)GetTickCount();
}
#else
#include <sys/time.h>
unsigned long getzikan(void) {
    struct timeval tv;
    gettimeofday(&tv,NULL);
    return (unsigned long)tv.tv_sec*1000+
        (unsigned long)tv.tv_usec/1000000;
}
#endif

// Tree の中の node をを通りがけ順 (inorder traversal) で出力する
void OutputTree(SRec *node, FILE *fp)
{
    if (node == NULL) return;
    OutputTree(node->left, fp);
    fprintf(fp, "%f %d %s\n", node->gpa, node->credit, node->name);
    OutputTree(node->right, fp);
}

// Tree の中の node を帰りがけ順 (postorder traversal) で解放する
void FreeTree(SRec *node)
{
    if (node == NULL) return;
    FreeTree(node->left);
    FreeTree(node->right);
    free(node);
}

// List の中の node をすべて出力する
void OutputList(SRec *list, FILE *fp)
{
    SRec* node;
    for (node = list; node != NULL; node = node->next)
        fprintf(fp, "%f %d %s\n", node->gpa, node->credit, node->name);
}

// List の中の node をすべて解放する
void FreeList(SRec* list)
{
    SRec *node, *next;
    for (node = list; node != NULL; node = next) {
        next = node->next;
        free(node);
    }
}

// Tree に node を追加する
void AddTree(SRec **root, SRec *node, int (*comp)(const void *, const void *))
{
    SRec *p = *root;
    if (p == NULL)
        *root = node;                   // leaf なので node をここに追加
    else if (comp(node, p) < 0)
        AddTree(&p->left, node, comp);  // node が小さいので左に追加
    else
        AddTree(&p->right, node, comp); // node が大きいので右に追加
}

// List から node を取り出して Tree に追加して、その Tree を返す
SRec* Insert(SRec *list, int (*comp)(const void *, const void *))
{
    SRec *root = NULL;  // node が一つもない Tree
    SRec *node, *next;
    for (node = list; node != NULL; node = next) {
        next = node->next;
        node->next = NULL;               // この node を List から削除
        node->left = node->right = NULL;
        AddTree(&root, node, comp);      // この node を Tree に追加
    }
    return root;  // Tree の root を返す
}

int compare_gpa(const void *a, const void *b)
{
    SRec* tmp1 = (SRec*) a;
    SRec* tmp2 = (SRec*) b;
    if (tmp1->gpa == tmp2->gpa)
        return 0;
    else if (tmp1->gpa > tmp2->gpa)
        return 1;
    else
        return -1; // gpa が double なので return tmp1->gpa - tmp2->gpa; と書けない
}

int compare_credit(const void *a, const void *b)
{
    SRec* tmp1 = (SRec*) a;
    SRec* tmp2 = (SRec*) b;
    return tmp1->credit - tmp2->credit;
}

int compare_name(const void *a, const void *b)
{
    SRec* tmp1 = (SRec*) a;
    SRec* tmp2 = (SRec*) b;
    return strcmp(tmp1->name, tmp2->name);
}

SRec* Input(FILE* fp)
{
    SRec head;
    head.next = NULL;  // node が一つもない List

    while (1) {
        SRec *node = (SRec *) malloc(sizeof(SRec));
        if (node == NULL) {
            fprintf(stderr,"メモリ不足");
            FreeList(head.next);
            return NULL;
        }
        if (fscanf(fp, "%f%d%s", &node->gpa, &node->credit, node->name) != 3) {
            free(node);
            break;  // 読み込みに失敗したら EOF
        }
        node->next = head.next;  // この node を先頭要素とする
        head.next = node;        // この node を先頭要素とする
    }
    return head.next;  // リストの先頭要素へのポインタを返す。
}

SRec* ListMake(SRec* root,SRec* p)          //ソートしたリストの作成 pはリストの最後
{
    SRec* tree=root;
    SRec* node=NULL;
    if(tree == NULL) return tree;
    if(tree->left != NULL)
    {
        node = ListMake(tree->left , tree);
    }
    else
    {
        node = tree;
    }
    if(tree-> right != NULL)
    {
        tree->next=ListMake(tree->right,p);
    }
    else
    {
        tree->next=p;
    }

return node;
}


int main(int argc, char *argv[])
{
    SRec *root, *list;
    FILE *fpi, *fpo;
    unsigned long clk_start,clk_end;
    int (*comp)(const void*,const void*);  // 比較関数へのポインタ
    if (argc != 4) {
        fprintf(stderr, "Illegal number of argument.\n");
        return (-1);
    }
    if ((fpi = fopen(argv[2], "r")) == NULL) {
        fprintf(stderr, "Can't open input file <%s>.\n", argv[2]);
        return (-1);
    }
    if ((fpo = fopen(argv[3], "w")) == NULL) {
        fprintf(stderr, "Can't open output file <%s>.\n", argv[3]);
        return (-1);
    }
    if (strcmp(argv[1], "gpa") == 0)
        comp = compare_gpa;
    else if (strcmp(argv[1], "credit") == 0)
        comp = compare_credit;
    else if (strcmp(argv[1], "name") == 0)
        comp = compare_name;
    else { fprintf(stderr, "key は gpa, credit, name\n"); return 1; }

    list = Input(fpi);
    if (list == NULL) return 1;

    clk_start = getzikan();
    root = Insert(list, comp);
    list=ListMake(root,NULL);
    clk_end = getzikan();
    printf("%lums\n",clk_end-clk_start);

    OutputList(list, fpo);
    FreeTree(root);
    fclose(fpi);
    fclose(fpo);
    return 0;
}

Re: 解決してませんでした＞＜

Posted: 2012年7月16日(月) 15:28
by れお
そして、１万個のソートしたデータをもう一度ソートしたら
４３２１ｍｓとなりました！！

うまくいけてるようです。

１０万個でやりました。
普通にばらばらのをソートすると４２６ｍｓ
ソートしたものをソートすると252955ms
でした。

結局なにがいけなかったのでしょう？
学校で提示されたclock関数がいけなかったのですか？？

Re: 解決してませんでした＞＜

Posted: 2012年7月16日(月) 15:30
by かずま
れお さんが書きました:おっしゃるとおりまだ終わってなかっただけでしたm(__)mただ前におっしゃってた通り時間がかかってるのに０．０３１秒とかになりますね。学校のでやるとうまくいくとかはないんですかね・・・笑
Windows で次のコードを試してみてください。

コード: 

    clock_t clk_start, clk_start2, clk_end;
        :
    clk_start = clock();
    root = Insert(list, comp);
    clk_start2 = clock();
    list = ListMake(root,NULL);
    clk_end = clock();
    printf("%f\n",(double)(clk_start2 - clk_start) / CLOCKS_PER_SEC);
    printf("%f\n",(double)(clk_end - clk_start2) / CLOCKS_PER_SEC);
    printf("start=%ld, start2=%ld, end=%ld\n", clk_start, clk_start2, clk_end);
    OutputList(list, fpo);
10万個のデータ xxx をソートして yyy に出力

コード: 

C:\tmp>srec gpa xxx yyy
0.124000
0.014000
start=128, start2=252, end=266
ソート済みの10万個のデータ yyy をソートして zzz に出力

コード: 

C:\tmp>srec gpa yyy zzz
15.413000
0.007000
start=153, start2=15566, end=15573
ご覧のようにソート済みのファイルのソートにはすごく時間がかかります。
二分木を作ることによるソートは、
ランダムな入力に対しては O(n long n) ですが、
ソート済みの入力に対しては O(n^2) の時間がかかりますから、
このような結果になっているのでしょう。

Re: 解決してませんでした＞＜

Posted: 2012年7月16日(月) 16:21
by れお
なるほど！！
理解しました＾＾
All times are UTC+09:00
ページ 1 ／ 1
Powered by phpBB® Forum Software © phpBB Limited
https://www.phpbb.com/