#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;
}
連結リストから 先頭要素を削除→削除した要素を２分探索木への追加（挿入）→先頭要素を削除→・・・
としたいのです。つまり挿入したと同時に先頭要素を代入したいのです。
そこで、約４０行目のwhile文の中身をみてほしいのですが。これだと、最初の根であるtreeから右にいくともうずっと右にいったままでかえってこれませんよね？（まだ挿入したとこに削除した先頭要素であるデータを代入する命令はかいていませんが・・・）
どうやったらまた根にもどってきて左右を選んでいったりすることができるのでしょうか？調べてもあんまり出てこないし困ってます＞＜
どなたかお願いします。
メニュー
カレンダー
Clock
最新メンバー
投稿数
統計データ
Link to us
カウンター