Commit: dbe36897620a065742219efa4aac94b0f3608c5f - star (git)

Commit MetaInfo

• Revisão: dbe36897620a065742219efa4aac94b0f3608c5f (tree)
• Hora: 2017-09-02 22:36:26
• Autor: dhrname <dhrname@user...>
• Commiter: dhrname

Mensagem de Log

New the ST_isLeaf function

Mudança Sumário

• modified: source_code/shadowstar.c
• modified: source_code/shadowstar.o
• modified: source_code/star.h
• modified: source_code/startest.c
• modified: source_code/startest.o

Diff

--- a/source_code/shadowstar.c
+++ b/source_code/shadowstar.c
@@ -439,13 +439,19 @@ const ST_Ordered_Pair ST_EMPTY = {
 /*ST_isEmpty 関数
  * 引数のlistがST_EMPTYかどうかをチェックするときに使う。ST_EMPTYならばtrue( = 1)
  * NULLは不具合が起きるので、入力すればエラー*/
-bool ST_isEmpty (ST_Ordered_Pair *list) {
-    if (list == NULL) {
+bool ST_isEmpty (ST_Ordered_Pair *list)
+{
+    if (list == NULL)
+    {
         eprintf("NULL argument error on the function ST_isEmpty");
         return false;
-    } else if (list == &ST_EMPTY) {
+    }
+    else if (list == &ST_EMPTY)
+    {
         return true;
-    } else {
+    }
+    else
+    {
         return false;
     }
 }
@@ -453,10 +459,13 @@ bool ST_isEmpty (ST_Ordered_Pair *list) {
 /*ST_first 関数
  * 順序対の一番目を返す
  * ST_pair関数で指定された第一引数（例えば、ST_pair(a,b)ならばa)を返す)*/
-ST_First_Type ST_first (ST_Ordered_Pair *list) {
-    if (ST_isEmpty(list)) {
+ST_First_Type ST_first (ST_Ordered_Pair *list)
+{
+    if (ST_isEmpty(list))
+    {
         return 0.0;
-    } else {
+    } else
+    {
         return list->first;
     }
 }
@@ -464,21 +473,27 @@ ST_First_Type ST_first (ST_Ordered_Pair *list) {
 /*ST_second 関数
  * 順序対の二番目を返す
  * ST_pair関数で指定された第二引数（例えば、ST_pair(a,b)ならばb)を返す)*/
-ST_Ordered_Pair *ST_second (ST_Ordered_Pair *list) {
-    if ( ST_isEmpty(list) || (list->second == NULL) ){
+ST_Ordered_Pair *ST_second (ST_Ordered_Pair *list)
+{
+    if ( ST_isEmpty(list) || (list->second == NULL) )
+    {
         /*ペアの二番目を取得できない場合は、自分自身を返す*/
         return list;
-    } else {
+    }
+    else
+    {
         return list->second;
     }
 }
 
 /*メモリ割り当てを呼び出す関数
  * 引数nはメモリのサイズ*/
-void *ST_emalloc(size_t n) {
+void *ST_emalloc(size_t n)
+{
     void *p;
     p = calloc(1, n);
-    if (p == NULL) {
+    if (p == NULL)
+    {
         eprintf("%u bytes failed on the function ST_emalloc", n);
     }
     return p;
@@ -487,17 +502,23 @@ void *ST_emalloc(size_t n) {
 /*ST_freelist関数
  * 引数のlistを解放させる
  * 他から参照されていない限り、ST_EMPTY以外のリストすべてが対象*/
-void ST_freelist (ST_Ordered_Pair *list) {
+void ST_freelist (ST_Ordered_Pair *list)
+{
     ST_Ordered_Pair *next;
-    for (;!ST_isEmpty(list) || (list->lifepoint >= 1);list = next) {
+    for (;!ST_isEmpty(list) || (list->lifepoint >= 1);list = next)
+    {
         next = ST_second(list);
-        if (list == next) {
+        if (list == next)
+        {
             break;
-        } else {
+        }
+        else
+        {
             free(list);
             list = NULL;
         }
-        if (!ST_isEmpty(next)) {
+        if (!ST_isEmpty(next))
+        {
             /*すでに死んだため参照カウンタを減らす*/
             next->lifepoint--;
         }
@@ -506,14 +527,16 @@ void ST_freelist (ST_Ordered_Pair *list) {
 
 /*ST_pair関数
  * 第一引数と第二引数とで順序対を作る*/
-ST_Ordered_Pair *ST_pair (ST_First_Type n, ST_Ordered_Pair *p) {
+ST_Ordered_Pair *ST_pair (ST_First_Type n, ST_Ordered_Pair *p)
+{
     ST_Ordered_Pair *s;
     s = (ST_Ordered_Pair *) ST_emalloc(sizeof(ST_Ordered_Pair));
     s->first = n;
     s->second = p;
     s->lifepoint = 0;
     s->first_tree = &ST_EMPTY;
-    if (!ST_isEmpty(p)) {
+    if (!ST_isEmpty(p))
+    {
         p->lifepoint++;
     }
     return s;
@@ -522,9 +545,12 @@ ST_Ordered_Pair *ST_pair (ST_First_Type n, ST_Ordered_Pair *p) {
 /*ST_getNumber関数
  * リストの項目に、関数fで指定された条件式を満たすものが一つでもあれば、その初めに満たす項目が何番目(n > 0)かを返す
  * なければ、0*/
-int_fast32_t ST_getNumber (ST_Ordered_Pair *list, Ord2bool_t f) {
-    for(int_fast32_t i = 1; !ST_isEmpty(list); list = ST_second(list)) {
-        if (f(list)) {
+int_fast32_t ST_getNumber (ST_Ordered_Pair *list, Ord2bool_t f)
+{
+    for(int_fast32_t i = 1; !ST_isEmpty(list); list = ST_second(list))
+    {
+        if (f(list))
+        {
             return i;
         }
         ++i;
@@ -537,7 +563,8 @@ int_fast32_t ST_getNumber (ST_Ordered_Pair *list, Ord2bool_t f) {
 ST_Ordered_Pair *ST_setChurchNumber (uint_fast32_t length, Ord2ST_Ordered_Pair f, ST_Ordered_Pair *list)
 {
     int32_t i;
-    for (i = 0; i < length; i++) {
+    for (i = 0; i < length; i++)
+    {
         /*lengthが4の場合、list = f(f(f(f(list))));*/
         list = (*f)(list);
     }
@@ -591,11 +618,35 @@ ST_First_Type ST_pop (ST_Stack_List stack)
 /*ST_getFirstTree 関数
  * 二分木の最初の枝を返す関数
  * first関数との違いは、数値型を返すか、ポインタ型を返すかの差*/
-ST_Ordered_Pair* ST_getFirstTree(ST_Ordered_Pair *list)
+ST_Binary_Tree ST_getFirstTree(ST_Binary_Tree node)
 {
-    if (ST_isEmpty(list)) {
+    if (ST_isEmpty(node))
+    {
         return &ST_EMPTY;
-    } else {
-        return list->first_tree;
     }
+    else
+    {
+        return node->first_tree;
+    }
+}
+
+/*ST_isLeaf 関数
+ * 与えられたノードが葉であるかどうかを調べる関数
+ * 葉であれば、true、枝であれば、false*/
+bool ST_isLeaf(ST_Binary_Tree node)
+{
+    /*ノードが葉であるためには、一番目の枝がない（first_treeメンバがST_Emptyである）ことが必要
+     * なお、二番目の枝は参考にしない*/
+    return ST_isEmpty(ST_getFirstTree(node));
+}
+
+/*ST_getSecondTree 関数
+ * 二分木の右の枝を返す関数*/
+ST_Binary_Tree ST_getSecondTree(ST_Binary_Tree node)
+{
+    if (ST_isLeaf(node))
+    {
+        /*葉であるならば、右の枝はST_EMPTYと考える*/
+    }
+    return node;
 }

Binary files a/source_code/shadowstar.o and b/source_code/shadowstar.o differ

--- a/source_code/star.h
+++ b/source_code/star.h
@@ -115,9 +115,24 @@ ST_Stack_List ST_push (ST_First_Type value, ST_Stack_List stack);
  * スタックからは取り除かれる*/
 ST_First_Type ST_pop (ST_Stack_List stack);
 
+/*以下では、二分木（binary tree)を順序対を使って、実装する
+ * ただし、ノードが枝の時は、ST_First_Type型の値を、
+ * ノードが葉(leaf)の時は、ST_Ordered_Pair型の値を保持するようにする
+ * こうすることで、連結リストを値として扱う*/
+typedef ST_Ordered_Pair* ST_Binary_Tree;
+
 /*ST_getFirstTree 関数
- * 二分木の最初の枝を返す関数*/
-ST_Ordered_Pair* ST_getFirstTree(ST_Ordered_Pair*);
+ * 二分木の左の枝を返す関数*/
+ST_Binary_Tree ST_getFirstTree(ST_Binary_Tree);
+
+/*ST_isLeaf 関数
+ * 与えられたノードが葉であるかどうかを調べる関数
+ * 葉であれば、true、枝であれば、false*/
+bool ST_isLeaf(ST_Binary_Tree);
+
+/*ST_getSecondTree 関数
+ * 二分木の右の枝を返す関数*/
+ST_Binary_Tree ST_getSecondTree(ST_Binary_Tree);
 
 /*トークン化したときの識別用のマジックナンバー*/
 typedef enum {

--- a/source_code/startest.c
+++ b/source_code/startest.c
@@ -401,6 +401,12 @@ int main(int argc, char **argv)
     assert(ST_getFirstTree(&dlist) == &ST_EMPTY);
     assert(ST_getFirstTree(&elist) == &dlist);
     assert(ST_getFirstTree(&flist) == &elist);
+    ST_Binary_Tree btree= &dlist;
+    assert(ST_isEmpty(ST_getFirstTree(btree)));
+    assert(ST_isLeaf(btree));
+    assert(!ST_isLeaf(&elist));
+    assert(!ST_isLeaf(&flist));
+    assert(ST_isLeaf(&ST_EMPTY));
 
     errno = 0;
     eprint_log("Error!\n");

Binary files a/source_code/startest.o and b/source_code/startest.o differ