1

ペットの名前と種類を格納する既存のバイナリ ツリー内に関数を実装する際に、特定の混乱があります。最初に行ったことは次のとおりです。

宣言[tree.h]:

typedef struct item
{
    char petname[20];
    char petkind[20];
} Item;

#define MAXITEMS 10

typedef struct node
{
    Item item;
    struct node * left;    /* pointer to right branch  */
    struct node * right;   /* pointer to left branch   */
} Node;

typedef struct tree
{
    Node * root;           /* pointer to root of tree  */
    int size;              /* number of items in tree  */
} Tree;


void InitializeTree(Tree *ptree);

bool TreeIsEmpty(const Tree * ptree);

bool TreeIsFull(const Tree * ptree);

int TreeItemCount(const Tree * ptree);

bool AddItem(const Item * pi, Tree * ptree);

bool InTree(const Item * pi, const Tree * ptree);

bool DeleteItem(const Item * pi, Tree * ptree);

void Traverse (const Tree * ptree, void (* pfun)(Item item));

void DeleteAll(Tree * ptree);

ノードを追加するための関数:

typedef struct pair {
    Node * parent;
    Node * child;
} Pair;


bool AddItem(const Item * pi, Tree * ptree)
{
     Node * new_node;

     if(TreeIsFull(ptree))
     {
          fprintf(stderr,"Tree is full\n");
          return false;
     }


          if(SeekItem(pi,ptree).child!=NULL)
          {
               fprintf(stderr,"Attempted to add duplicate item\n");
               return false;
          }

     new_node=MakeNode(pi);

     if(new_node==NULL)
     {
          fprintf(stderr,"Couldn't create node\n");
          return false;
     }

     ptree->size++;

     if(ptree->root==NULL)
          ptree->root=new_node;
     else
          AddNode(new_node,ptree->root);

     return true;
}

static void AddNode(Node * new_node, Node * root)
{
     if((strcmp(new_node->item.petname, root->item.petname))==0)
     {
          if(root->same==NULL)
               root->same=new_node;
          else
               AddNode(new_node, root->same);
     }
     else
     {
          if(ToLeft(&new_node->item,&root->item))
          {
               if(root->left==NULL)
                    root->left=new_node;
               else
                    AddNode(new_node, root->left);
          }
          else if(ToRight(&new_node->item,&root->item))
          {
               if(root->right==NULL)
                    root->right=new_node;
               else
                    AddNode(new_node, root->right);
          }
          else
          {
               fprintf(stderr,"location error in AddNode()\n");
               exit(1);
          }
     }
}

static bool ToLeft(const Item * i1, const Item * i2)
{
     int comp;

     if((comp=strcmp(i1->petname,i2->petname))<0)
          return true;
     else if(comp==0)
          return true;
     else
          return false;
} 

static bool ToRight(const Item * i1, const Item * i2)
{
     int comp;

     if((comp=strcmp(i1->petname,i2->petname))>0)
          return true;
     else if(comp==0)
          return true;
     else
          return false;
}

static Node * MakeNode(const Item * pi)
{
     Node * new_node;

     new_node=(Node *) malloc(sizeof Node);

     if(new_node!=NULL)
     {
          new_node->item=*pi;
          new_node->left=NULL;
          new_node->right=NULL;
          new_node->same=NULL;
     }
     return new_node;
}

(もっと多くのコードが必要な場合は、もっと関数があるので投稿します) 主な混乱は、同じノード内のリストに同じ名前 (異なる種類) のすべてのペットを追加し、次のように入力するだけでそれらを見つける方法です。種類を取得する際のペット名

元のタスク: Pet Club プログラムを修正して、同じ名前のすべてのペットが同じノードのリストに格納されるようにします。ユーザーがペットを探すことを選択した場合、プログラムはペットの名前を要求し、その名前を持つすべてのペットを (その種類と共に) リストする必要があります。

本からの提案: *

別の可能なバリエーションとして、Nerfville Pet Club を検討してください。この例では、ツリーを名前と種類の両方で並べ替えたため、1 つのノードに猫のサム、別のノードに犬のサム、3 番目のノードにヤギのサムを保持できます。ただし、サムという猫を 2 匹飼うことはできません。もう 1 つの方法は、ツリーを名前だけで並べ替えることです。その変更を単独で行うと、種類に関係なく 1 つの Sam しか許可されませんが、Item を単一の構造体ではなく、構造体のリストとして定義できます。Sally が初めて現れると、プログラムは新しいノードを作成し、次に新しいリストを作成して、Sally とその種類をリストに追加します。次に現れる Sally は、同じノードに送られ、リストに追加されます。

*

4

1 に答える 1

1

リンクされたリストについてはすでに知っているはずです。その知識をここにあるツリーと組み合わせてください。Item をリンクされたリストに移動し、Node に直接 Item ではなくリストを保存させます。

typedef struct itemlistElement
{
    Item item;
    struct itemlistElement* nextItem;    /* pointer to next item on list */
} ItemlistElement;

typedef struct node
{
    ItemlistElement* listOfItems; /* pointer to first element of a linked list of Item */
    struct node * left;    /* pointer to right branch  */
    struct node * right;   /* pointer to left branch   */
} Node;

残りは把握できます。ツリーをたどるたびに、リストをたどる追加のステップが必要になります。アイテムを追加する場合、2 つの可能性があります。1 つのアイテムを含む新しいノードを追加するか、アイテムを既存のノードに追加します。それはまさにあなたの本が言ったことです：

(...) その後、単一の構造体ではなく、構造体のリストとして Item を定義できます。Sally が初めて現れると、プログラムは新しいノードを作成し、次に新しいリストを作成して、Sally とその種類をリストに追加します。次に現れる Sally は、同じノードに送られ、リストに追加されます。

まず、リストを作成して機能させます。最初は個別に練習しますItemlistElement*(ツリーの外では、別のプログラムでリストとリスト トラバーサル関数を作成することもできます)。次に、リストに格納するようにプログラムを変更しますItemが、常に 1 つの要素のリストを使用します。これは非常に簡単なはずです。最後の動きは、それらを一緒に結合することです。これは、コーディングが最も少ないステップですが、最も困難です。入力する前にすべてのことを考えてください。混乱してプログラムが乱雑になった場合に参照できるように、まだ動作している間に両方のプロジェクト (ツリーとリンクされたリスト) のコピーを作成します。

于 2012-05-10T11:29:16.040 に答える